Nonnegativity of Slack Variable Coefficients in Row 0 of Optimal Tableau (Simplex Algorithm) 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?
 A: 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.
A: 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.
