# Simplex method : Improving a basic feasible solution by Bazaraa

My question is about improving a basic feasible solution according to Bazaraa's explanation (Linear Programming and Network Flows ed II p94)

Improving a basic feasible solution

$$z_{0}=c_{B}B^{-1}b$$

$$x_{B}=B^{-1}b-B^{-1}Nx_{N}=B^{-1}b-\sum_{j \epsilon R}^{} B^{-1}a_{j}x_{j}$$

where R is the current set of the indices of the nonbasic variales

$$z = cx = c_{B}x_{B} + c_{N}x_{N} = c_{B}(B^{-1}b - \sum_{j \epsilon R}^{} B^{-1}a_{j}x_{j}) + \sum _{j \epsilon R}^{}c_{i}x_{j} = z_{0}-\sum_{j \epsilon R}^{}(z_{j}-c_{j})x_{j}$$

where $z_{j}=c_{B}B^{-1}a_{j}$ for each nonbasic variable.

In conclusion:

$$z=z_{0}-\sum_{j \epsilon R}^{}(z_{j}-c_{j})x_{j}$$

Ideas

I really can't understand what's the idea behind $z_{j}$. First of all the formula for $z_{j}$ doesn't look like the one for $z_{0}$. Second, why in the formula we have a mix corresponding to basic variables ($c_{B}$, $B^{-1}$) and nonbasic variables ($a_{j}$)

-
@MikeSpivey, Thanks, fixed –  com Nov 19 '11 at 18:06

It may help to remember the big picture here. When you choose the entering variable you want one that makes the objective function decrease. If you've got the objective function in the form $$z = z_{0}-\sum_{j \epsilon R}^{}(z_{j}-c_{j})x_{j}$$ then it's easy to see which nonbasic variables would cause the objective function to decrease if they were to enter the basis: It's the ones for which $z_j - c_j > 0$. Since $c_j$ is a constant, it's convenient to give the part that changes with the basis some variable name, like $z_j$. Then it's a matter of finding a formula for $z_j$.
1. The quantities $z_0$ and $z_j$ (for $j \geq 1$) mean different things, and so it's not surprising that their formulas are slightly different. The value of $z_0$ is the value of the objective function for the current basis, while the value of $z_j$ is the part of the reduced cost $c_j-z_j$ for variable $x_j$ that depends on the basis. However, there is some nice symmetry to their formulas: $z_0 = c_B B^{-1} b$, and $z_j = c_B B^{-1}a_j$. The only difference is that $z_0$ has the right-hand side of the constraint equations, while $z_j$ has the column of the constraint equations corresponding to the nonbasic variable $x_j$.
2. Part of what it means for $B$ to be a basis for the current solution is that all the important aspects of the current solution can be expressed in terms of $B$. That includes quantities that relate to the nonbasic variables, like $z_j$. (Think "basis" from linear algebra, if that helps.) From this point of view, then, it's not surprising that $z_j$ can be expressed in terms of basic variable "stuff" and nonbasic variable "stuff": the basic part is for the reason I just said, and then you need at least some quantity, like $a_j$, associated with $x_j$ to indicate which nonbasic variable the basic "stuff" should be applied to. (This is the high level view: It just explains why we should expect some basic "stuff" and some nonbasic "stuff" in an expression for any quantity related to a nonbasic variable; it doesn't explain why the particular quantity $c_B B^{-1} a_j$ is needed. You can look up the reason for the latter in the Bazaraa text you're using.)