1. The problem statement, all variables and given/known data

enter image description here


I am looking at this quesiton attached part c).

  1. Relevant equations

  2. The attempt at a solution

I can by my notes which tell me that if I reach a column with a negative reduced cost and also all of that column is negative, then to stop, as z is unbounded, to conclude that the variable $x_l$ - non-basic variable is unbounded and thus z is too.

However I am

a) confused trying to understand the argument as to why this variable is unbounded. It says via the equation:

$x_i+a_i x_l =(B^{-1}b)_i $ for each basic variable $i$ which is used to argue the minimum ratio rule i.e. for $x_l$ non-basic want to increase $x_l$ whilst keeping all other non-basic variables zero. Non-basic variables have value zero in the basic feasible solution so the variable leaving the basis must be able to be set to zero. and $x_i=(B^{-1}b)_i-a_ix_l$ it is clear that as $x_l$ is increased for $a_i <0 , x_i $ is unbound. But to know claim that $x_l$ is unbounded and can be increased indefinitely is to me switching the logic and the arguement around- i.e. when deriving the minimum ratio test rule, $x_i$ is sort of the independent variable and $x_l$ the dependent. So I have: $x_l=\frac{B^{-1}b)_i x_i }{a_i}$ and so if $ x_i \to \infty $ then it will eventually be greater than $B^{-1}b_i$# making the numerator negative and also dividing by a negative then of as $ x_i \to \infty$ so will $x_l$. HOWEVER in order to conclude that $ x_i \to \infty $ is to use the logic of that used in deriving the ratio rule, so we're now role-reversing what is dependent/independent in the same argument, which i'm confused about. Or is there another way to argue why $x_l \to \infty ? $

b) why we stop as soon as we reach a variable with a negative reduced cost and it's entire column negative, even though there may be another reduced cost negative with a row that we can pivot on- could this pivot not bring the other column to not all be negative?

(the notation used is consistent with what I belive is standard, definitions of variables etc, but in case not, I am following that of Hillier and Liberman , an introduction to operations research)

So to apply the above to the question at hand, i would conclude that table (3), $x_4$ is unbound and therefore so is $z$. However I am asking in a) above how you know to stop here,and not try to pivot on column $x_5$ in hope that this may yield a not fully negative entries in the column of $x_4$?

Many thanks in advance


Remember that the only constraints other than the equations represented in the tableau are the nonnegativity restrictions on the variables. Consider tableau (3), in which $x_1, x_2, x_3$ are basic and $x_4, x_5$ are nonbasic (and equal to zero). Leaving $x_5=0$, we can rewrite the solution as $(x_1,x_2,x_3)=(20,20,20)+(3,4,5)x_4$. As $x_4$ increases, so do $x_1, x_2, x_3$ (with $x_5$ still locked at 0). So everybody stays nonnegative, no matter how large $x_4$ gets, and you thus have an infinite ray in the feasible region. The reduced cost of $x_4$ is -2, so the objective value decreases monotonically as $x_4$ increases. This apparently being a minimization problem, the problem itself (meaning the objective value) is unbounded.

As to why you stop, you've just proved that the objective value has no minimum over the feasible region. Further pivoting cannot change that; it's fundamentally a geometric property, not an artifact of the tableau. If you keep pivoting, you might find another ray along which the objective function decreases, but with rare (and somewhat advanced) exceptions that's not a matter of particular interest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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