# Operations Research: Simplex Table Unbound Optimal Solution

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

Hi

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

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.