Mie Midterm

MIE376 – Mathematical Programming Mid-Term Exam February 15, 2011 Note: Clearly state any assumptions you make in answering any of the questions below. 1) Consider the following LP problem: Max 5x1 + 3x2 + x3 subject to 3x1 + 2x2 + x3 ≤ 7 ; x2 + x3 ≤ 3; x1 + x3 ≤ 2 ; and x1, x2, x3 ≥ 0

10 5 5 5

a) b) c) d)

Determine the optimal solution using 3 iterations of the Revised Simplex method Evaluate and interpret the Shadow Prices and Reduced Costs Formulate the Dual of this LP Derive the optimal solution of the Dual from the Optimal Solution of the Primal. Z = cBTB-1b – (cBTB-1N – cN)

2) Consider the following Bi-level LP problem: Min 3x1 + x2 such that 1 ≤ x2 ≤ 6; and x1 is the optimal solution of the following LP Max x1 subject to x1 + x2 ≤ 8; 4x1 + x2 ≥ 8; 2x1 + x2 ≤ 13; and x1 ≥ 0

15 10

a) Use KKT conditions to derive an equivalent mathematical programming problem. b) Identify the entering and departing variables in the first Phase 1 iteration of Wolfe’s algorithm for solving this problem. 3) The Alva Electric Co., a major public utility, has scheduled the construction of new hydroelectric plants 5, 10 and 20 years from now to meet the needs of the growing population. To cover the construction costs the company needs to invest now to meet its future cash flow requirements. They can purchase only three types of financial assets, each of which costs $1 million per unit. Fractional units may be purchased. The assets produce income 5, 10, and 20 years from now, and that income will be used to cover the cash flow requirements in those years. Any excess income above the construction cost cash flow requirements will be used to increase share holders dividends. The table shows the amount of income generated per $1 million invested now in each of the asset types, for each of the three target years, as well as the cash flow requirements for those years. Formulate an LP to help Alva decide how much to invest in each of the asset types to cover its future...