Optimization Methods - Recitation 2 - Solutions

Solutions 2 Example 1 x is a basic feasible solution to the standard form problem with corresponding basis B. Consider a direction d such that y = x + d is also a feasible solution. Find the change in the objective cost. Solution
z = c
d = c
dB + c
dN . B N Ay = b, thus Ad = 0. � B N � � × dB dN � = BdB + NdN = 0 Thus dB = −B−1 NdN . Therefore
z = c
B (−B−1 NdN ) + c
N dN or

z = (c
N − cB B−1 N)dN Example 2 If dN is a unit vector in Rn−m . Find the direction d. Solution Ad = 0 or BdB + NdN = 0. NdN = Aj , thus BdB + Aj = 0. Therefore, dB = −B−1 Aj . Example 3 Solve the following problem using the full tableau simplex method: x1 min s.t. x1 + x2 ≤ 2 −x1 + x2 ≤ 0 x1 , x2 ≥ 0 (1) Solution The standard form with slack variables: min s.t. −x1 − x2 x1 + x2 + s1 = 2 −x1 + x2 + s2 = 0 x1 , x2 , s1 , s2 ≥ 0 1 (2) 6 @ @ � � @ � @ � @ A � @ � � @ � @ � @ O � @ � @ B � @ - Figure 1 Feasible region of the original problem The first tableau with slack variables as basis variables: −1 1∗ −1 0 s1 = 2 s2 = 0 −1 1 1 0 1 0 0 0 1 The solution is not optimal. Select x1 as the entering variable. θ ∗ = 2 and s1 will be the leaving variable. The next tableau is: 2 x1 = 2 s2 = 2 0 1 0 0 1 2 1 1 1 0 0 1 The solution is optimal. However, this might not be the only optimal solution. In this case, we can see that there are multiple optimal solutions. The additional basic optimal solution can be found in the next tableau: 2 x1 = 1 x2 = 1 0 1 0 0 0 1 1 1/2 1/2 0 −1/2 1/2 Now in the first step, choose x2 as entering variable instead of x1 . θ ∗ = 0 and s2 is leaving. This is clear that degeneracy makes the simplex method chooses the same basic feasible solution (with different basis of course) in this case: −2 2∗ −1 0 s1 = 2 x2 = 0 0 0 1 0 1 0 1 −1 1 The solution is not optimal. x1 is entering the basis. We have, θ ∗ = 1 and s1 is leaving. The next tableau is shown below: 2 x1 = 1 x2 = 1 0 1 0 0 0 1 1 1/2 1/2 0 −1/2 1/2 This is the additional basic optimal solution calculated above and we can see that c4 = 0 again indicates that there might be multiple optimal solutions. Now what if the objective function is x1 . The initial tableau will be: 2 0 s1 = 2 s2 = 0 1 1 −1 0 1 1 0 1 0 0 0 1 This solution is optimal and we have c2 = 0. However, the θ ∗ here is zero, which means there are not multiple optimal solutions in this case. Example 4 Construct the dual of the following problem and then the dual of its dual: min s.t. 2x1 + 3x2 + 8x3 x1 − x2 − x3 ≥ 1 3x2 + x3 = 4 x3 ≤ 1 x1 , x2 , x3 ≥ 0 Solution The dual problem is: (3) p1 + 4p2 + p3 max s.t. p1 ≥ 0, p2 free, p3 ≤ 0 p1 ≤ 2 −p1 + 3p2 ≤ 3 −p1 + p2 + p3 ≤ 8 (4) The minimization format of the dual problem: − min s.t. −p1 − 4p2 − p3 p1 ≥ 0, p2 free, p3 ≤ 0 p1 ≤ 2 −p1 + 3p2 ≤ 3 −p1 + p2 + p3 ≤ 8 The dual of the dual problem: − max s.t. (5) 2x1 + 3x2 + 8x3 x1 − x2 − x3 ≤ −1 3x2 + x3 = −4 x3 ≥ −1 x1 , x2 , x3 ≤ 0 (6) Change the variables yi = −xi for i = 1, 3 and change the problem to the minimization format, we obtain the primal problem. 3