Nonnegativity of Slack Variable Coefficients in Row 0 of Optimal Tableau (Simplex Algorithm)

Question

I have a general question regarding the simplex algorithm for a maximization LP. When performing the simplex algorithm, one has arrived at an optimal tableau when all of the coefficients in Row 0 are nonnegative. Do the coefficients of the slack variables in Row 0 need to be nonnegative too? If so, can someone explain to me why this must be?

Answer 1

Yes, all coefficient in row $0$ must be negative. Let denote $a_{0s}$ the negative coefficient of a slack variable in row $0$ and $a_{is}$ the correspoding positive pivot element. Then the objective value after the i-th transformation is

$z_i=z_{i-1}- \large{\frac{a_{0s}\cdot b_i}{a_{is}}}$

Now $a_{0s}$ is negative, $b_i$ is nonnegative and $a_{is}$ is positive. If $b_i$ is positive then $\large{\frac{a_{0s}\cdot b_i}{a_{is}}}$ is negative and therefore $-\large{\frac{a_{0s}\cdot b_i}{a_{is}}}$ is positive.

In total the objective value can be increased.

Answer 2

Yes, they need to be nonnegative. This is easy to see if you just perform one simplex iteration: the objective value will improve (or, at least, not deteriorate).

Another way to look at it is the following. The coefficients in row 0 corresponding to the slacks are the shadow prices in the final tableau. They show how much the objective improves if the right hand side is increased (for $\leq$ constraints) by $1$. It would not make sense if the shadow prices are negative, since relaxing the constraints increases the feasible region and therefore cannot worsen the objective value.