15.093J Optimization Methods, Mid-Term Exam (Solutions)

MIT, 2.098/6.255/15.093J Optimization Methods Mid-Term Exam Solutions 1. This is a 90 minute exam. 2. It is open book, open notes. No computers allowed. 3. Good luck! Problem 1. (40 Points) Classify each one of the following as either True or False. All answers must be supported with a justification or counterexample as appropriate. Unsupported answers will be awarded zero marks. Each of the 10 questions is worth 4 points. a) If two different basic feasible solutions of a linear program are optimal, then they must correspond to adjacent vertices of the feasible region. b) The problem max n X cj |xj | subject to j=1 n X aj |xj | ≤ b, with cj , aj ≥ 0, can be j=1 modeled as a linear optimization problem. ( k ) k X X  c) Let P = λi xi λi = 1, λi ≥ 0, i = 1, . . . , k , where S = x1 , x2 , . . . , xk i=1 i=1 is a set of given vectors. Then the set of extreme points of P is S. d) If the dual of a linear optimization problem has a degenerate basic feasible solution, then the primal problem must have multiple optimal solutions. e) The only way that the simplex method can get to a degenerate basic feasible solution at some iteration is when there is a tie in the min-ratio test in the previous iteration. f) The dual simplex method can detect whether a linear optimization problem is infeasible or unbounded. 1 g) The column geometry shows that the number of simplex pivots to find an optimal basic feasible solution is linear in the dimension n. h) Suppose the feasible space of an optimization problem is the union of two polyhe­ dra. The problem can be modeled as an integer optimization problem. i) In a network flow problem, the objective function coefficients are fractional, but the demands and supplies are integral. The optimal solution is fractional. j) If the reduced cost of a non-basic variable in an optimal basis is zero, then the corresponding BFS is degenerate. Solution a) FALSE. Let c = 0. Then every BFS is optimal, and in general every BFS is clearly not adjacent. b) TRUE. Let yj = |xj |, ∀j and a linear optimization problem in y follows. We can then form an optimal solution by taking x = y, but any x with xj = ±yj , ∀j will be a solution. c) FALSE. Consider the case where S consists of 3 distinct colinear points. Then the middle one is not an extreme point. d) FALSE. This need only be true if the degenerate basic feasible solution of dual is optimal and corresponds to two or more distinct bases, in which case corresponding system of equations leads to multiple optima in the primal. a counterexample, let the dual be unbounded with a degenerate BFS. Then primal has no optimal solutions. the the As the e) FALSE. Degeneracy can also occur when there is no tie but we move zero distance from an already degenerate solution. f) FALSE. The dual simplex method can detect whether the primal linear optimiza­ tion problem is infeasible by the unboundedness termination criterion in the algo­ rithm. It cannot detect unboundedness of the primal, since to do this we would need to show feasibility of the primal, and infeasibility of the dual. The latter occurs if we cannot find a starting basis in Phase I of the algorithm, but the former is not checked if we do not find such a basis. g) FALSE. The tilted hypercube example shows that the number of pivots the simplex method takes may be be exponential in n in the worst case. h) TRUE. Suppose the problem is min c′ y s.t. y 2 ∈ P1 ∪ P2 , where P1 = {y : A1 y ≥ b1 }, and P2 = {y : A2 y ≥ b2 }. We can write this problem as the following MIP: min s.t. c′ y A1 y A2 y x ≥ b1 − M xe, ≥ b2 − M (1 − x)e, ∈ {0, 1}, where M is a sufficiently large constant, and e is a vector of all ones. i) FALSE. This follows since xB = B −1 b, which is independent of c. j) FALSE. Consider a nondegenerate BFS in a problem with cost vector c = 0 (here all reduced costs are zero). Problem 2. (30 Points) a) (15 points) Consider the robust optimization problem min max {x: Dx≥f } {c: Ac≤b} c′ x, that is the feasible space is {x : Dx ≥ f }, but the vector of objective function coefficients c is uncertain and the possible c vectors satisfy Ac ≤ b. Applying duality in the inner problem, formulate the above problem as a linear optimization problem. b) (15 points) Consider another robust optimization problem min c′ x s.t. a′ x x ≥ b, ∀a ∈ U, ≥ 0, where n U = {a ∈ R : n X aj = Γ, aj ≥ 0} j=1 is the uncertainty set to which the coefficients a belong, and Γ is some positive constant. Formulate this robust optimization problem as a linear optimization problem. 3 Solution a) (15 points) Firstly, we assume the inner problem is feasible, otherwise the problem is not well-defined. Applying strong duality in the case where it has a finite optimal cost, the problem is ( ) ′ min p b, x is s.t. the inner problem is bounded, {p: A′ p=x, p≥0} min . {x: Dx≥f } ∞, x is s.t. the inner problem is unbounded So we have the following linear optimization problem: min p′ b s.t. Dx Ap−x p p, x ≥ f, = 0, ≥ 0. ′ b) (15 points) We need the constraints to be satisfied ∀a ∈ U, so we need b≤ min {a: e′ a=Γ, a≥0} a′ x = max {φ: φ≤xj , ∀j} −b ≥ min φΓ = − {φ: φ≤xj , ∀j} min {φ: φ≤xj , ∀j} −φΓ, −φΓ, So we need −b ≥ −φΓ, ∀φ s.t. φ ≤ xj , ∀j, i.e. b ≤ φΓ, ∀φ s.t. φ ≤ xj , ∀j. The first equality uses strong duality and hence requires that the LP on the lefthand-side has an optimal solution. But clearly this is true, since it is feasible (take aj = Γ1 , ∀j), and its objective value is bounded below (since a, x >= 0). So we finally have the following linear optimization problem: min c′ x s.t. φΓ ≥ xj − φ ≥ x ≥ φ, x b, 0, 0. ∀j ∈ {1, . . . , n}, Problem 3. (30 Points) A company makes four products 1, 2, 3, and 4 and uses 3 resources A, B, and C. The company decides on the product mix by solving the following linear optimization prob­ lem: 4 Z ∗ = max s/t. 16x1 + 14x2 + 15x3 + 50x4 2x1 + 2x2 + 5x3 + 16x4 3x1 + 2x2 + 2x3 + 5x4 2x1 + 1.2x2 + x3 + 4x4 x1 , x2 , x3 , x4 ≤ ≤ ≤ ≥ 800 1000 680 0 (A) (B) (C) The company solves the problem using the simplex method, and obtains the following optimal tableau: -6000 0 0 -14 -40 -5 -2 0 200 0 1 5.5 19 1.5 -1 0 200 1 0 -3 -11 -1 1 0 40 0 0 0.4 3.2 0.2 -0.8 1 a) (2 points) What is the optimal solution, and the optimal solution value? b) (2 points) What is the optimal basis B, and what is B −1 ? c) (2 points) In one sentence, what is the optimal strategy? d) (2 points) Is the optimal solution unique? e) (4 points) What are the optimal dual variables? f) (3 points) By how much should the profit of product 3 change, so that it is used in an optimal solution? g) (5 points) What should the minimum profit of product 2 be, so that the company continues to produce it? h) (3 points) Find the range on resource B, so that the current basis remains optimal. i) (4 points) Suppose that resource B becomes 1000 + θ. Describe in as much detail as possible how the optimal profit changes with θ. j) (3 points) A new product requiring 4 units of resource A, 4 units of resource B and 1 unit of resource C is proposed. What should the profit of this product be in order to produce it? Solution a) (2 points) x′ = (200, 200, 0, 0, 0, 0, 40), Z ∗ = 6000. 5 b) (2 points)  2 2 0 B =  2 3 0 , 1.2 2 1  B −1  1.5 −1 0 1 0 . = −1 0.2 −0.8 1  c) (2 points) The company should produce 200 units of product 1, and 200 units of product 2, at a cost of 6000. d) (2 points) Yes. Since the reduced cost of every nonbasic variable is negative (re­ member, we are maximizing), moving positive distance to “another optimal solu­ tion” must stricly decrease the cost, so this other optimal solution must not exist. e) (4 points) p′ = c′B B −1 f) (3 points)  1.5 −1 0 1 0 = (5, 2, 0) = (14, 16, 0) −1 0.2 −0.8 1    5 ′  c̄3 = c3 − p A3 = c3 − (5, 2, 0) 2 = c3 − 29 ≥ 0 =⇒ Δc3 ≥ 29 − 15 = 14. 1 g) (5 points) Firstly, p′ = c′B B −1  1.5 −1 0 1 0 = (1.5c2 − 16, 16 − c2 , 0) = (c2 , 16, 0) −1 0.2 −0.8 1   5 16 1 0 c̄′N = c′N − p′ N = (15, 50, 0, 0) − (1.5c2 − 16, 16 − c2 , 0) 2 5 0 1 1 4 0 0  = (15, 50, 0, 0) − (7.5c2 − 80 + 32 − 2c2 , 24c2 − 256 + 80 − 5c2 , 1.5c2 − 16, 16 − c2 ) = (15, 50, 0, 0) − (5.5c2 − 48, 19c2 − 176, 1.5c2 − 16, 16 − c2 ) = (−5.5c2 + 63, −19c2 + 226, −1.5c2 + 16, −16 + c2 ) ≤ 0 =⇒ c2 ≥ 226 . 19 h) (3 points) We require        1200 − B 1200 − B 1.5 −1 0 800  =  B − 800  ≥ 0 B − 800 1 0  B  =  B −1 b = −1 840 − 0.8B 160 − 0.8B + 680 0.2 −0.8 1 680 =⇒ 800 ≤ B ≤ 1050. 6 i) (4 points) The optimal profit in a linear maximization problem is a concave function in the right-hand-side. For 800 ≤ 1000 + θ ≤ 1050, i.e. −200 ≤ θ ≤ 50, our basis remains optimal, and hence so do our dual variables, so this function is   800 f (b) = p∗′ b = (5, 2, 0) 1000 + θ = 4000 + 2(1000 + θ) = 6000 + 2θ. 680 Outside of this range the optimal basis will change and we cannot give any more detail without solving for p∗ for some such b. j) (3 points) These resources are valued at   4 p∗′ b = (5, 2, 0) 4 = 28, 1 so the profit of this product must be at least 28 in order to produce it. 7