Linear Programming

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 – 6×3 + (13/8)x4 <= 1

      4×1 + 2×2 + 2×3 <= 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.