About Simplex method in Introduction to Algorithms (CLRS)

179 Views Asked by At

I am reading "Introduction to Algorithms 3rd Edition" by CLRS.
I think it is obvious that $28$ is the optimal objective value from the objective function $z = 28 - \frac{1}{6} x_3 - \frac{1}{6} x_5 - \frac{2}{3} x_6$ .

But CLRS didn't write it was obvious from the objective function.

Why?

enter image description here

CLRS wrote as follows in "Introduction to Algorithms 3rd Edition":

"At this point, all coefficients in the objective function are negative. As we shall see later in this chapter, this situation occurs only when we have rewritten the linear program so that the basic solution is an optimal solution."

But I think it is obvious that the basic solution $x_3 = x_5 = x_6 = 0, x_1 = 8, x_2 = 4, x_4 = 18$ is an optimal solution and it is not necessary for the authors to prove this fact later in this chapter.

The authors proved this fact later in this chapter by using duality.

But it is too obvious.