Question

Consider the following LP: max cTx s.t. Ax ≤b P x ≤q x ≥0 You are given that the optimal value of the above is 100. Prove that the optimal value of the following LP is at least 200. (Assume that it has an optimal solution.) min bTy s.t. ATy ≥2c y ≥0

Answer 1

The question deals with proving that the optimal value of a dual linear programming problem is at least 200 when the primal problem's optimal value is 100, by utilizing the principles of LP duality.

Step-by-step explanation:

The question concerns Linear Programming (LP), which is a method used to achieve the best outcome in a mathematical model. The student has provided an optimal value of 100 for the maximization problem and is asking to prove that the optimal value of a dual minimization problem is at least 200. Using duality in linear programming, we can argue that the optimal value of the dual problem is a lower bound to the primal problem. Thus, if the given primal LP has an optimal value of 100, the dual LP's optimal solution, which minimizes bTy, under the constraints ATy ≥ 2c and y ≥ 0, must be at least 200, because the decision variable coefficients in the objective function of the dual are at least twice those in the primal LP's constraints, implying that their product with any feasible solution of the dual will be at least double the primal's optimal value