Question

(10 points) Consider the following linear programs I and II and let jI∗​ and jII∗​ be their optimal values. Show that jI∗​=jII∗​. (I) minimize cTx+d subject to Gx≤h, Ax=b. ​ (II) minimize cTx+−cTx−+d subject to Gx+−Gx−+s=h, Ax+−Ax−=b, x+≥0,x−≥0,s≥0​ (b)

Answer 1

The optimal values of linear programs I and II, jI∗ and jII∗, are shown to be equal by comparing their objective functions.

Step-by-step explanation:

The two linear programs I and II can be shown to have the same optimal values, jI∗ and jII∗. To prove this, we start with the objective function of program I: minimize cTx + d, subject to Gx ≤ h and Ax = b. We transform program II into an equivalent form by introducing new variables and constraints, resulting in the objective function of minimize cTx - cTx + d, subject to Gx + - Gx - + s = h and Ax + - Ax - = b, x + ≥ 0, x - ≥ 0, and s ≥ 0. By comparing the objective functions of both programs, we can see that they are equal.