Operations Research: Simplex table, unbound optimal solution

[binbagsss]

Homework Statement

Hi

I am looking at this question attached part c).


2. Homework Equations

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 argument 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 believe 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.

 

[Ray Vickson]

Homework Statement

View attachment 224464

Hi

I am looking at this question attached part c).


2. Homework Equations

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 argument 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 believe 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.

Write out the equations explicitly for tableau (3):

$$\begin{array}{rclr}
x_1 - 3 x_4 + 7 x_5 = 20& \Rightarrow& x_1 = 20 + 3 x_4 - 7 x_5 & (1)\\
x_2 - 4 x_4 + 8 x_5 = 20 & \Rightarrow& x_2 = 20 + 4 x_4 - 8 x_5 & (2) \\
x_3 - 5 x_4 + 9 x_5 = 20 & \Rightarrow& x_3 = 20 + 5 x_4 - 9 x_5 & (3) \\
z - 2x_4 - 6 x_5 = 10 &\Rightarrow& z = 10 + 2x_4 + 6 x_5 & (4)
\end{array}
$$
Look at eq.(4): $z$ will increase if we increase either $x_4$ or $x_5$ up from zero. Notice also that we can keep $x_5 = 0$ and increase $x_4$ as much as we want while maintaining feasibility ($x_1, x_2 \geq 0$). Therefore, the problem is unbounded---there is no finite maximum value of $z$ among the feasible solutions, partly because there is no bound on the feasible solutions. (However, you can have an unbounded feasible region but a bounded objective, so be careful.)

Rather than memorizing "tableau rules", I suggest you go back to basics and remind yourself what a tableau really stands for---a shorthand way of writing out the equations, without having to write things like $x_j$ over and over again.

 

[binbagsss]

---there is no finite maximum value of $z$ among the feasible solutions, partly because there is no bound on the feasible solutions. (However, you can have an unbounded feasible region but a bounded objective, so be careful.)

.[/QUOTE]

Many thanks , can you give me such an example or point me towards some text that highlights this point and perhaps has examples to compare differing cases ?

 

[Ray Vickson]

---there is no finite maximum value of $z$ among the feasible solutions, partly because there is no bound on the feasible solutions. (However, you can have an unbounded feasible region but a bounded objective, so be careful.)

.

Many thanks , can you give me such an example or point me towards some text that highlights this point and perhaps has examples to compare differing cases ?[/QUOTE]

See, eg., http://www.uobabylon.edu.iq/eprints/publication_11_6246_31.pdf
or
http://eee.guc.edu.eg/Courses/Networks/NETW904%20Linear%20and%20Nonlinear%20Optimization/Tutorials/Lectures3_4.pdf

The first one covers all these special cases for two-variable examples, but does so using the simplex tablueau (rather than graphical methods, for example).

 

[Statjana]

Dear all,

My area of expertise is elsewhere and I do not intent to become expert in the simplex method, just tryitng to understand the steps from my initial problem forumlation Tableau #1, to the final solution Tableau #4, the final solution is correct, btw. I also understand the steps from Tableau #1 to Tableau #2 (I guess that since this is the first step, even without negative values in the bottom row, we want to interate once, so chose smallest value -10). But then why in the next iteration do we chose 20 and not -15? No need to talk me through row manipulations. Could you just explain for me each time, why we choose the pivot coloumn and row? - Thanks alot! Help is much appreciated on this! I guess in Tableau #1, the equality had to be slpit to two equalities, with slacks, because otherwise there is not a pivot for every row?

Tableau #1
x y z s1 s2 s3 s4 -p
2/3 1/3 0 1 0 0 0 0 100
1/3 2/3 0 0 1 0 0 0 100
1 1 1 0 0 1 0 0 181
1 1 1 0 0 0 -1 0 181
10 12 20 0 0 0 0 1 0

Tableau #2
x y z s1 s2 s3 s4 -p
1 1/2 0 3/2 0 0 0 0 150
0 1/2 0 -1/2 1 0 0 0 50
0 1/2 1 -3/2 0 1 0 0 31
0 1/2 1 -3/2 0 0 -1 0 31
0 7 20 -15 0 0 0 1 -1500

Tableau #3
x y z s1 s2 s3 s4 -p
1 1/2 0 3/2 0 0 0 0 150
0 1/2 0 -1/2 1 0 0 0 50
0 0 0 0 0 1 1 0 0
0 1/2 1 -3/2 0 0 -1 0 31
0 -3 0 15 0 0 20 1 -2120

Tableau #4
x y z s1 s2 s3 s4 -p
1 0 -1 3 0 0 1 0 119
0 0 -1 1 1 0 1 0 19
0 0 0 0 0 1 1 0 0
0 1 2 -3 0 0 -2 0 62
0 0 6 6 0 0 14 1 -1934

 

[Ray Vickson]

Dear all,

My area of expertise is elsewhere and I do not intent to become expert in the simplex method, just tryitng to understand the steps from my initial problem forumlation Tableau #1, to the final solution Tableau #4, the final solution is correct, btw. I also understand the steps from Tableau #1 to Tableau #2 (I guess that since this is the first step, even without negative values in the bottom row, we want to interate once, so chose smallest value -10). But then why in the next iteration do we chose 20 and not -15? No need to talk me through row manipulations. Could you just explain for me each time, why we choose the pivot coloumn and row? - Thanks alot! Help is much appreciated on this! I guess in Tableau #1, the equality had to be slpit to two equalities, with slacks, because otherwise there is not a pivot for every row?

Tableau #1
x y z s1 s2 s3 s4 -p
2/3 1/3 0 1 0 0 0 0 100
1/3 2/3 0 0 1 0 0 0 100
1 1 1 0 0 1 0 0 181
1 1 1 0 0 0 -1 0 181
10 12 20 0 0 0 0 1 0

Tableau #2
x y z s1 s2 s3 s4 -p
1 1/2 0 3/2 0 0 0 0 150
0 1/2 0 -1/2 1 0 0 0 50
0 1/2 1 -3/2 0 1 0 0 31
0 1/2 1 -3/2 0 0 -1 0 31
0 7 20 -15 0 0 0 1 -1500

Tableau #3
x y z s1 s2 s3 s4 -p
1 1/2 0 3/2 0 0 0 0 150
0 1/2 0 -1/2 1 0 0 0 50
0 0 0 0 0 1 1 0 0
0 1/2 1 -3/2 0 0 -1 0 31
0 -3 0 15 0 0 20 1 -2120

Tableau #4
x y z s1 s2 s3 s4 -p
1 0 -1 3 0 0 1 0 119
0 0 -1 1 1 0 1 0 19
0 0 0 0 0 1 1 0 0
0 1 2 -3 0 0 -2 0 62
0 0 6 6 0 0 14 1 -1934

Your tableaus are almost unreadable, because the columns do not line up well, and you never state exactly what your objective is, or whether you are maximizing or minimizing. Looking at your first tableau (which is almost readable) I guess your original LP is (after multiplying the first two constraints by 3 on both sides):
$$\begin{array}{rrrrcl}
\max/\min&Z = 10 x +12 y + 20 z & & \\
\text{s.t.} & 2x + y &\leq&300 \\
&x + 2y & \leq & 300 \\
& x+y+z&=& 181\\
& x,y,z &\geq & 0
\end{array}
$$
These two LPs can be easily solved using a package, and the solutions are:
(1) For the maximization problem: x = y = 0, z = 181, Z = 3620.
(2) For the minimization problem: x=119, y = 62, z = 0, Z = 1934
So, it looks like the right-hand-side entries x, y and Z in Tableau 4 are correct, and the problem is one of minimization. However, it also looks like some of the other Tableau entries are wrong.

As to your question: write out the Tableau entries as equations, so your objective equation for Tableau 2 would be
$-P + 7y + 20 z -15 s1 = -1500,$ or $-P = -1500 -7y -20 z + 15 s1$, so to decrease $-P$ we need to choose variables whose coefficients on the right are < 0. Note that because you introduce two "fake" slack/surplus variables in the equality constraint, you are dealing with an infeasible solution in Tableau 2, hence your objective value $P = 1500$ is super-optimal--less than the actual minimum among feasible solutions. Also, I your tableaus exhibit non-monotone behavior: in Tableaus 1--4 your $P$ values are 0, 1500, 2120 and 1934. I would have expected them to rise steadily.

I don't agree in detail with all the entries in your Tableau 4. Rather than using the outdated (and NOT recommended) method of converting an equality into two opposite inequalities, I just leave it as is. Thus, my tableaus would have a different number of columns from yours, if I used tableaus at all (which I do not). I use equations instead, but let the computer algebra package Maple do all the work. I supply slack variables s1 and s2 for the two inequality constraints but leave the third equation alone. Here are the steps:

eqs:={2*x+y+s1=300, x + 2*y + s2 = 300, x+y+z=181, Z-10*x-12*y-20*z=0}; <== input
eqs := {x + y + z = 181, x + 2 y + s2 = 300, 2 x + y + s1 = 300, Z - 10 x - 12 y - 20 z = 0} <== output

S1:=solve(eqs,{z,s1,s2,Z});
S1 := {Z = -10 x - 8 y + 3620, s1 = -2 x - y + 300, s2 = -x - 2 y + 300, z = -x - y + 181} <== first basic feasible solution (bfs)

S2:=solve(S1,{z,x,s2,Z});
S2 = {Z = -3*y+2120+5*s1, s2 = -3/2*y+150+1/2*s1, x = -1/2*y+150-1/2*s1, z = -1/2*y+31+1/2*s1} <== second bfs

S3:=solve(S2,{y,x,s2,Z});
S3 := {Z = 6 z + 1934 + 2 s1, s2 = 3 z + 57 - s1, x = z + 119 - s1, y = -2 z + 62 + s1} <== third bfs (optimal)

The first basic solution was obtained by letting s1, s2 and z be basic (and also Z, which is always kept basic). It happens to be feasible as well, but if some of the basic variables had come out < 0 we could have dealt with that. (Alternatively, I could have introduced and artificial variable "a" and written the third constraint as $x+y+z+a=181$, then require that $a \geq 0$ come out as zero. That would be a two-phase approach, where Phase I is to minimize a, and if a comes out as zero, go on to Phase II (the actual optimzation), starting with the tableau/equations left at the end of Phase I. However, I did not bother with all that.)

So, S1 is the first system of equations, putting basic variables on the left of the "=" and non-basics on the right. (A system written that way is called a dictionary in Chvatal's book.) S1 is the first dictionary. If I really wanted to use a tableau I could get it from dictionary 1:
$$\begin{array}{r|rrrrr|r}
Z & x & y & z & s1 & s2 & \text{rhs} \\ \hline
1 & 10 & 8 &0 & 0&0 & 3620\\
0 & 2 & 1 & 0 & 1 & 0 & 300 \\
0 & 1 & 2 & 0 & 0 & 1 & 300 \\
0 & 1 & 1 & 1 & 0 & 0 & 181 \\
\end{array}$$
However, doing that is a waste of time, and so I will stop. BTW: if you want to see how I made the table, just right-click on the image and ask for a display of math at tex commands; that will show you the details.

Dictionary S2 is obtained by swapping x and s1 in S1; that is, we let x become basic, and then s1 becomes non-basic (by the usual ratio test). Of course, moving away from S1 we could have chosen to increase y instead, but increasing x decreases Z at the fastest rate, and is what is normally done in introductory discussions (but usually not in practice on LPs having hundreds of thousands of variables and constraints---as found in real-world industrial applications).

When we look at S2, the only favorable non-basic variable is y, because it is the only right-hand-side variable whose increase from 0 will decrease the value of Z. So we increase y and find that z leaves the basis---again by the standard minimum-ratio test. Swapping y and z in S2 gives the dictionary in S3, which is optimal. If you compare S3 with your Tableau 4 you will see some differences. In particular, it looks like your s2 is 19 while mine is 57.

 

[Statjana]

Thank you, my problem statement is as follows:
Minimize p=10x+12y+20z subject to 2/3 x + 1/3 y <= 100, 1/3 x + 2/3 y <= 100, x + y + z = 181

Since I did not get anywhere by hand, I turned to the solution given by this calculator (see link), which is the tables I had copied in - I am sorry the formating is bad, I am now trying to upload screenshot. I happen to know that 119 and 62 is the solution I expect. However I cannot make sense of the steps taken to get from tableau to tableau. While I do not need to be an expert in Simplex method, I want to walk my students through this example only, so I want to do the tableaus and not a package or Maple. I am happy to work with different set of tableaus, as long as I can see how to determine the steps to get from one to the next.

https://www.zweigmedia.com/RealWorld/simplex.html

 

[Ray Vickson]

Thank you, my problem statement is as follows:
Minimize p=10x+12y+20z subject to 2/3 x + 1/3 y <= 100, 1/3 x + 2/3 y <= 100, x + y + z = 181

Since I did not get anywhere by hand, I turned to the solution given by this calculator (see link), which is the tables I had copied in - I am sorry the formating is bad, I am now trying to upload screenshot. I happen to know that 119 and 62 is the solution I expect. However I cannot make sense of the steps taken to get from tableau to tableau. While I do not need to be an expert in Simplex method, I want to walk my students through this example only, so I want to do the tableaus and not a package or Maple. I am happy to work with different set of tableaus, as long as I can see how to determine the steps to get from one to the next.

https://www.zweigmedia.com/RealWorld/simplex.html

You forgot to list the non-negativity constraints $x,y,z \geq 0.$ Those are absolutely crucial, and if you are teaching this material you should never, ever allow your students to forget them.

The tableaux you show deal with the equality constraint in the worst possible way, and then go on to violate just about all the rules of the simplex method. No wonder you cannot figure out how they did it, because their steps seem arbitrary and (as I said) violate all the rules.

If you want to teach your students the basics of the simplex, please, please, please stay away from the formulation given in your link---you will only confuse the students and lead them down wrong paths. A MUCH better way would be to introduce a single "artificial" variable in the equality and treat that as a non-negative variable that you want to drive to zero (in order to get a feasible solution). That is the actual way that standard LP computer packages used to treat such problems in the early days, and even now are standard part of every textbook introduction to linear programming and the simplex method. It is even the case that many modern non-commercial LP computer packages still use that method in practice, but with some variations.

So, we write the problem as
$$ \begin{array}{rccl}
\min p =& 10 x +12 y + 20 z&& \\
\text{s.t.}& 2/3 \: x + 1/3 \: y + s_1 &= &100\\
& 1/3 \: x + 2/3 \: y + s_2 &=& 100 \\
& x+y+z + a &=& 181 \end{array}$$
and $x,y,z \geq 0, a = 0.$ We treat these last restrictions separately from all the others, and initially we replace $a=0$ by $a \geq 0$; the aim is to drive $a$ to zero. In fact, one way to do this would be to introduce $a$ into the minimization objective, but with a large penalty if it is positive. That means that we would replace the objective by
$$\min Z = 10 x + 12 y + 20 z + M a,$$
and replace the restriction $a=0$ by $a \geq 0$ throughout. Here, $M > 0$ is a large number. If $M$ is large enough, driving $a$ to zero will take precedence, so if the problem is feasible (that is, if it is possible to have $a=0$) that is what the simplex method will give. Of course, when $a=0$ we are back to the original problem with an equation constraint having no variable $a$ in it, so we will be solving the original problem. This method is called the "Big-M" method, and is used in many introductory treatments of LP (but rarely in practice in real LP packages).

The equations above have basic variables $s_1 = 100, s_2 = 100, a = 181,$ and $p = 0.$ From now on we shall include the expression for $p$ as part of the system, by writing it as $p - 10 x - 12 y - 20 z = 0$, or $p - 10 x - 12 y - 20 z - M a$ if we employ the big-M method.

The current basis is feasible for the $a \geq 0$ problem, but is not feasible for the $a = 0$ problem. Note that since $a = 181 - x-y-z$ we can drive $a$ towards 0 by increasing any of $x,y$ or $z$. Rather than increasing $x$ (as in your link), it would be preferable to increase $z$ (because it does not appear in any other of the constraints, so would not affect feasibility of the other variables), In other words, in a single step we could achieve a feasible solution where $a = 0$ and all other variables $\geq 0$. However, the link you provide does it another way: it increases $x$ (possibly because its $p$-coefficient is the smallest, so increasing $x$ increases $p$ at the smallest rate).

At this point I suggest you try to carry on yourself---yes, manually! It really is not that bad. Go ahead and let $x$ become basic; use the least-ratio rule to figure out which variable $s_1, s_2, a$ will become non-basic, etc. That will give you a correct Tableau to use instead of Tableau 2 that your link provides.