HW2-solutions

IEOR 4004: Optimization Models and Methods Homework 2 Solutions Instructor: Shipra Agrawal 1. (10 points) Convert the following linear program (LP) to standard form: min x 1 + x 2 + 8 x 3 + x 4 x 1 + x 2 + x 3 + x 4 ≤ 12 x 1 + x 2 + x 3 + x 4 ≥ 1 x 1 + x 2 − x 3 + 5 x 4 = 10 x 1 ≥ 0 , x 2 ≤ 0 , x 3 ≥ 0 , x 4 unrestricted SOLUTION. The standard form is max c ⊤ x such that Ax = b and x ≥ 0. Converting the above LP into standard form: We transform the minimization to a maximization. Add slack variables s 1 to the ≤ constraint, and a surplus variable s 2 to the ≥ constraint. Next, we let − x 2 = y 2 and x 4 = x + 4 − x − 4 such that y 2 , x + 4 , x − 4 ≥ 0 max − x 1 + y 2 − 8 x 3 − x + 4 + x − 4 x 1 − y 2 + x 3 + x + 4 − x − 4 + s 1 = 12 x 1 − y 2 + x 3 + x + 4 − x − 4 − s 2 = 1 x 1 − y 2 − x 3 + 5 x + 4 − 5 x − 4 = 10 x 1 ≥ 0 , y 2 ≥ 0 , x 3 ≥ 0 , x + 4 ≥ 0 , x − 4 ≥ 0 2. (15 points) Consider the following linear program (LP): max 12 x 1 + 11 x 2 + 8 x 3 + 6 x 4 8 x 1 + 8 x 2 + 6 x 3 + 5 x 4 ≤ 12 x i ≥ 0 , i = 1 , 2 , 3 , 4 (a) Convert the above LP to standard form. (b) Perform one iteration of the simplex method starting with the bfs where x 1 = x 2 = x 3 = x 4 = 0. Show your work: show the dictionary, identify the entering and leaving variable, write the new bfs, transform the constraints (so that the columns of basic variables in the new bfs form the standard basis) and objective (so that it is written in terms of non-basic variables in the new bfs). (c) Is the new bfs optimal? Why? SOLUTION. (a) We just need to add a slack variable to the ≤ constraint. max 12 x 1 + 11 x 2 + 8 x 3 + 6 x 4 8 x 1 + 8 x 2 + 6 x 3 + 5 x 4 + s 1 = 12 x i ≥ 0 , i = 1 , 2 , 3 , 4 s 1 ≥ 0 1

(b) At the basic feasible solution x 1 = x 2 = x 3 = x 4 = 0, we have s 1 = 12. Using the greedy rule, we pick x 1 to be the entering variable and s 1 will be the leaving variable. The transformed LP is: max 18 − x 2 − x 3 − 3 / 2 x 4 − 3 / 2 s 1 x 1 + x 2 + 3 / 4 x 3 + 5 / 8 x 4 + 1 / 8 s 1 = 3 / 2 x i ≥ 0 , i = 1 , 2 , 3 , 4 s 1 ≥ 0 (c) The new bfs is optimal as the coefficients of all non-basic variables in the objective are negative. 3. (20 points) Consider the following LP: max 10 x 1 + x 2 s.t. x 1 ≤ 1 20 x 1 + x 2 ≤ 100 x 1 , x 2 ≥ 0 (a) Convert above LP to standard form. (b) Enumerate all the basic feasible solutions (bfs) for the standard form LP. Hint: For an LP in standard form with m constraints and n variables, there are at most ( n m ) basic feasible solutions. To find all bfs, you can check all the ( n m ) potential ways of setting n − m out of the n variables to 0. (c) Show the feasible region ( x 1 , x 2 ) graphically, and for each bfs found in part (b), plot the point ( x 1 , x 2 ) on this graph. (d) For each bfs found in part (b), transform the LP to be in ”tableau form”. That is, transform the constraints so that the columns for basic variables to form standard basis; and substitute the basic variables in the objective so that it is written in terms of the non-basic variables only. You may use a matrix inversion calculator or row reductions to perform this transform. (e) Use simplex method to solve the LP. For every bfs solution you find in the simplex method iterations, you may look up and reuse the tableau form you computed in part (d). SOLUTION. (a) max 10 x 1 + x 2 s.t. x 1 + s 1 = 1 20 x 1 + x 2 + s 2 = 100 x 1 , x 2 , s 1 , s 2 ≥ 0 (b) The basic feasible solutions are (0 , 0 , 1 , 100) , (1 , 0 , 0 , 80) , (0 , 100 , 1 , 0) , (1 , 80 , 0 , 0) (c) See image below (d) For bfs (0 , 0 , 1 , 100): max 10 x 1 + x 2 s.t. x 1 + s 1 = 1 20 x 1 + x 2 + s 2 = 100 x 1 , x 2 , s 1 , s 2 ≥ 0 2

(e) Starting with the original LP, that has bsf (0 , 0 , 1 , 100): max 10 x 1 + x 2 s.t. x 1 + s 1 = 1 20 x 1 + x 2 + s 2 = 100 x 1 , x 2 , s 1 , s 2 ≥ 0 Pick x 1 as entering variable, so s 1 will be the leaving variable. The new bfs is (1 , 0 , 0 , 80) and the LP is: max 10 + x 2 − 10 s 1 s.t. x 1 + s 1 = 1 x 2 − 20 s 1 + s 2 = 80 x 1 , x 2 , s 1 , s 2 ≥ 0 Pick x 2 as entering variable, so s 2 will be leaving variable. The new bfs is (1 , 80 , 0 , 0) and the LP is: max 90 + 10 s 1 − s 2 s.t. x 1 + s 1 = 1 x 2 − 20 s 1 + s 2 = 80 x 1 , x 2 , s 1 , s 2 ≥ 0 . Now pick s 1 as entering variable and x 1 is leaving variable. the new bfs is (0 , 100 , 1 , 0). The LP is: max 100 − 10 x 1 − s 2 s.t. x 1 + s 1 = 1 20 x 1 + x 2 + s 2 = 100 x 1 , x 2 , s 1 , s 2 ≥ 0 Since the coefficients in the objective are negative, the simplex procedure stops here. We have found the optimal solution x 1 = 0 , x 2 = 80. 4. (15 points) At the end of an intermediate step of the simplex method, you have the following LP after transforming it in ”tableau form” for the current bfs: max cx 1 − 2 x 2 +10 − x 1 + a 1 x 2 + x 3 = 4 a 2 x 1 − 4 x 2 + x 4 = 1 a 3 x 1 +3 x 2 + x 5 = b List the basic variables and non-basic variables in the current bfs. Give conditions on the unknowns a 1 , a 2 , a 3 , b and c that make the following statement true: a) The current solution is optimal. b) The current solution is optimal, and there are alternative optimal solution. c) The LP is unbounded (in this part, assume b ≥ 0) 4

SOLUTION. The basic variables are x 3 , x 4 , x 5 and the non-basic variables are x 1 , x 2 . We need b ≥ 0 as x 5 is a basic variable. (a) If c ≤ 0, then we cannot improve the LP as the coefficients of non-basic variables are both negative. So the current solution will be optimal when c < 0. (b) If c = 0, then we can pick x 1 as entering variable without changing the objective. if a 2 > 0 , a 3 > 0 then the critical value of x 1 min (1 /a 2 , b/a 3 ). So, b > 0. (c) If c > 0, a 2 ≤ 0 and a 3 ≤ 0 then x 1 can be chosen as entering variable, but there is no critical value for it. Thus, the LP is unbounded. 5. (20 points) In this problem we use two-phase simplex method to find an optimal solution of the following LP or declare the LP infeasible. (We refer to this LP as the ’original LP’). max 5 x 1 − x 2 s.t. 2 x 1 + x 2 = 6 x 1 + x 2 ≤ 4 x 1 + 2 x 2 ≤ 5 x 1 , x 2 ≥ 0 (a) Formulate the Phase I LP. (b) Solve the Phase I LP using a solver. Make sure to use a solver that finds a basic feasible optimal solution. Write down the basic feasible optimal solution and optimal value of Phase I LP found by the solver. Remark: The default optimization algorithm used by cvxpy is an interior-point method that may not return a corner point (i.e., basic feasible) optimal solution. In order to get a basic feasible optimal solution, you can explicitly set the solver as ”dual-simplex method” using the following options in the solve( · ) method: prob.solve(solver=cp.SCIPY, scipy_options={"method": "highs-ds"}) (c) Use the Phase I LP solution found in part (b) to either find a bfs of the original LP or argue that the original LP is infeasible. In the former case, use the basic feasible solution found as a starting bfs and solve the original LP using simplex method. You may use a matrix inversion calculator or row-reductions to do the transform step in the simplex method. Show your work. SOLUTION. (a) Phase I LP is to min a 1 (same as max − a 1 ). min a 1 s.t. 2 x 1 + x 2 + a 1 = 6 x 1 + x 2 + s 2 = 4 x 1 + 2 x 2 + s 3 = 5 x 1 , x 2 , a 1 , s 2 , s 3 ≥ 0 The optimal value of Phase 1 LP is 0, and the optimal bfs is: 7 / 3 , 4 / 3 , 0 , 1 / 3 , 0 for x 1 , x 2 , a 1 , s 2 , s 3 respectively. (b) The original LP in standard form is: max 5 x 1 − x 2 s.t. 2 x 1 + x 2 = 6 x 1 + x 2 + s 2 = 4 x 1 + 2 x 2 + s 3 = 5 x 1 , x 2 , s 2 , s 3 ≥ 0 5