Let x* j for j = 1, 2, . . . , n be an optimal solution to the linear program with two groups of…
Let x*j for j = 1, 2, . . . , n be an optimal solution to the linear program with
two groups of constraints, the ai j constraints and the ei j constraints. Let yi for i = 1, 2, . . . , m and wi for i = 1, 2, . . . , q denote the shadow prices (optimal dual variables) for the constraints.
a) Show that x*j for j = 1, 2, . . . , n also solves the linear program:
in which the ai j constraints have been incorporated into the objective function as in the method of Lagrange multipliers. [Hint: Apply the optimality conditions developed in Section 4.5 to the original problem and this ‘‘Lagrangian problem.’’]
b) Illustrate the property from part (a) with the optimal solution x*1 = 2, x*2 = 1, and shadow prices y1 = 1 2 , w1 = 1 2 , w2 = 0, to the linear program:
c) Show that an optimal solution xj for j = 1, 2, . . . , n for the ‘‘Lagrangian problem’’ from part (a) need not be optimal for the original problem [see the example in part (b)]. Under what conditions is an optimal solution to the Lagrangian problem optimal in the original problem?
d) We know that if the ‘‘Lagrangian problem’’ has an optimal solution, then it has an extreme-point solution. Does this imply that there is an extreme point to the Lagrangian problem that is optimal in the original problem?