Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


$$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}$$


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}$)

share|cite|improve this question
@MikeSpivey, Thanks, fixed – com Nov 19 '11 at 18:06
up vote 3 down vote accepted

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$.

As far as your specific questions...

  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.)
share|cite|improve this answer
Thanks for the hint, looks like you are right, the "basis" from linear algebra is the good analogue – com Nov 19 '11 at 18:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.