256 Solutions3x 3 + x 4 <20 (2/3)
-xi < -1 (2/4)
x\ < 6 (1/5)£2 < 10 (l/e)
-x 3 < -3 (2/T)
X3 < 9 (j/ 8 )
x 4 < 5 (2/9)
Xi,x 2 ,x 3 ,x 4 > 0
(D):min302/i + 13t/ 2 + 2O2/3 - 2/4 + 62/5 + Kfye - 32/7 + 92/ 8 + 5?/9s.t.
2/i + 2/2 - 2/4 + 2/5 > 2 (xi)22/i + 2/2 + 2/6 > 3 (x 2 )
3i/i + 3y 2 - 2/7 + 2/8 > 1 (x 3 )
52/i + 2/3 + 2/9 > 4 (2:4)
2/1,2/2,2/3,2/4,2/5,2/6,2/7,2/8,2/9 > 0
The optimal primal solution, x = (xi,X2,X3,X4)T = (5,8,3,0)T, satisfies
constraints (2/1,2/2,2/7) as binding, i.e. the corresponding slacks are zero. By
complementary slackness, the dual variables 2/1,2/2,2/7 might be in the optimal
dual basis. The other primal constraints have positive surplus values at the
optimality, therefore 2/3 = 2/4 = Vt — 2/6 = V& = Vl = 0- Moreover, the
reduced costs of the surplus variables at the optimal primal solution are both
1 for s\ and S2, which are the optimal values of y\ = 2/2 = 1- Since the
optimal primal basis contains the nonzero valued x\ and X2, the corresponding
dual constraints are binding: 1 + 1 — 0 + 0 = 2-/ and 2 + 1 + 0 = 3A/-
Furthermore, the optimal primal solution has nonbasic variables X3 and X4,
then the corresponding dual surplus variables may be in the dual basis: 3 + 3 —
2/7 + 0 > 1, and 5 + 0 + 0>4=> the corresponding surplus, say t\ = 1 in the
dual optimal basis. The optimal primal objective function value is z* = 37,
which is equal to the optimal dual objective function value by the strong
duality theorem. Then, 37 = 30(1) +13(1) + 20(0) - (0) + 6(0) +10(0) - 3j/J +
9(0) + 5(0) + 0t\ + 0^0^ + 0tl, yielding 2/7 = 2.