Problem 1. (Degeneracy)
Consider the following dictionary, which we may have encountered when solving an LP with the simplex method.
ζ = c1*x1 + c3*x3 + d3*w3 + c4*x4
w1 = 5 -6*x1 + 2*x3 w3 3*x4
w2 = 2 +4*x1 -6*x3 + 2*w3 – 2*x4
x2 = 0 +3*x1 -w3 +2*x4
where
c1 = -361
c3 = 0
d3 = 0
c4 = -1083
Determine these parameters and write down the resulting dictionary. We denote it by (EXAM-Dict).
We use (P-sol) and (D-sol) to respectively denote the primal and dual basic solutions given in (EXAM-Dict). Answer the following questions:
i. Write the components of (P-sol) and (D-sol). Is the dictionary (EXAM-Dict) primal feasible? Is it dual feasible?
ii. Is (EXAM-Dict) primal degenerate? Why?
iii. If (EXAM-Dict) is primal degenerate, show how to find an alternative dual feasible basic solution (denoted by (D-sol-alt)) such that (P-sol) and (D-sol-alt) have complementary slackness. Moreover, show how to find yet another dual feasible solution (D-sol-3) such that (P-sol) and (D-sol-3) have complementary slackness; (D-sol-3) should be different from both (D-sol) and (D-sol-alt).
iv. Is (EXAM-Dict) dual degenerate? Why?
v. If (EXAM-Dict) is dual degenerate, show how to find an alternative primal feasible basic solution (denoted by (P-sol-alt)) such that (P-sol-alt) and (D-sol) have the same objective function value. Then find another primal feasible solution (different from both (P-sol) and (P-sol-alt)) that also has the same objective function value.
Problem 2 (lexicographic simplex method)
Consider the following LP
max 4×1 + x2 + 5×3 +3×4
s.t. -6×1 + x2-x3-2×4 <= 0
(-17/8)x2 - 6x3 + (13/8)x4 <= 1
4x1 + 2x2 + 2x3 <= 0
x1,x2,x3,x4 >=0
Now solve the LP with the perturbation/lexicographic variant of the primal simplex method to ensure that no degeneracy can occur.
In each iteration of the simplex method, clearly write down the following things: dictionary, current basic feasible solution (BFS), current objective value, the entering variable, the leaving variable, how you did the ratio test (noting in particular the features of the perturbation/lexicographic method), the basic variables, the non-basic variables.
