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*x4w1 =  5   -6*x1 + 2*x3     – w3 – 3*x4w2 =  2  +4*x1   -6*x3 + 2*w3  – 2*x4x2 =   0   +3*x1                   -w3  +2*x4wherec1 = -361c3 = 0d3 = 0c4 = -1083Determine 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 LPmax 4×1 + x2 + 5×3 +3x4s.t. -6×1 + x2-x3-2×4 <= 0(-17/8)x2 - 6x3 + (13/8)x4 <= 14x1 + 2x2 + 2x3 <= 0x1,x2,x3,x4 >=0Now 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.