Question

4.9) Consider the linear programming problem

minimize z = c^Tx

subject to Ax = b x ≥ 0.

Let a₁, … , a_m be the artificial variables, and suppose that at the end of phase 1 a basic feasible solution to the problem has been found (no artificial variables are in the basis). Prove that, in the final phase-1 basis, the reduced costs are zero for the original variables x₁ , … , x_n and are one for the artificial variables.

Answer 1

Any doubt then comment below...

Main focus is that when we apply phase 1 method... Then in objective function....coefficient of all ordinary variables is 0 and coefficient of all artificial variables is -1 ...

Now at end table of phase 1... Since all basic variable is ordinary variable then their corresponding cost coefficient also 0... So for reduced cost for all variable is Zj - Cj .. where Zj= 0 because costs of basic variable is 0 in objective function of phase 1...

So it means for ordinary variable , reduced cost = Zj-Cj = 0-0 = 0

And for artificial variable , reduced costs = Zj-Cj = 0-(-1) = 1