Homework Help: Linear Programming degenerate case

1. Sep 19, 2011

zcd

1. The problem statement, all variables and given/known data
Choose the number $\omega$ so that the following program has a solution. Then write down the optimal solution.

$$\begin{bmatrix} -1 & 2 & 3 \\ 2 & 3 & 1 \\ -5 & -4 & 1 \end{bmatrix} x = \begin{bmatrix} 1 \\ 5 \\ \omega \end{bmatrix}$$
$min=x_2$
$x\geq 0$
2. Relevant equations
2-phase simplex method

3. The attempt at a solution
We've only covered the simplex method for nondegenerate cases of matrices with more columns than rows. Any indication of a direction I can take to start the problem will be much appreciated.

2. Sep 19, 2011

Ray Vickson

You could write the third equation as $-5x_1 - 4x_2 + x_3 - \omega = 0,$ and then regard $\omega$ as another variable. However, you should allow for the fact that $\omega$ can be < 0 or >= 0, so re-write it as $\omega = \omega^+ - \omega^-,$ where $\omega^+, \omega^- \geq 0.$ Now you have a problem with more variables than constraints.

RGV

3. Sep 19, 2011

zcd

So I'm basically creating a surplus variable to avoid violating the n>m rule?

4. Sep 19, 2011

Ray Vickson

I have no idea what you are talking about. You were asked to produce a value of omega. Since you are not told what omega is (and are free to make it whatever you want) it might as well just be another variable in the problem.

RGV

5. Sep 19, 2011

zcd

I made the substitution as follows
$$\begin{bmatrix} -1 & 2 & 3 & 0 & 0\\ 2 & 3 & 1 & 0 &0 \\ -5 & -4 & 1 & -1 & 1\\ \end{bmatrix} x = \begin{bmatrix} 1 \\ 5 \\ 0 \end{bmatrix}$$

but when I run phase I, I don't have sufficient vectors to make a basis matrix from because one of the b vector terms is 0. If i choose to continue anyway and let the basis matrix be the identity in R3 one term in the tested x goes negative and eventually it drives the cost vector to $-\infty$

Last edited: Sep 19, 2011
6. Sep 19, 2011

Ray Vickson

There are Two types of costs here: the Phase I objective, or the Phase II objective x_2. Which do you mean?

Anyway, I get a perfectly legitimate finite optimal solution when I solve the problem. Perhaps if you show your work I could give you some hints.

RGV

7. Sep 20, 2011

zcd

For phase 1, I rewrote the problem as minimize z1+z2+z3 subject to
$$\begin{bmatrix} -1 & 2 & 3 & 0 & 0 & 1 & 0 & 0\\ 2 & 3 & 1 & 0 & 0 & 0 & 1 & 0\\ -5 & -4 & 1 & -1 & 1 & 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ u\\ v\\ z_1\\ z_2\\ z_3\\ \end{bmatrix} = \begin{bmatrix} 1 \\ 5 \\ 0 \\ \end{bmatrix}$$
where $\omega=u-v$ and $x_1,x_2,x_3,u,v,z_1,z_2,z_3\geq 0$.

I start the phase 2 with $$x= \begin{bmatrix} 0\\ 0\\ 0\\ 0\\ 0\\ 1\\ 5\\ 0\\ \end{bmatrix}$$
solving $$y=(M^T)^{-1}\hat{c}=\begin{bmatrix} 1\\ 1\\ 1\\ \end{bmatrix}$$ and it shows wrong way inequalities during $A^T y\leq c$ on row 3 and 5. To find a new x vector, I use the 3rd row $$t=M^{-1}a^3= \begin{bmatrix} 3\\ 1\\ 1\\ \end{bmatrix}$$ and this helps me find a new
$$x= \begin{bmatrix} 0\\ 0\\ \lambda\\ 0\\ 0\\ 1-3\lambda\\ 5-\lambda\\ 0-\lambda\\ \end{bmatrix} \to x= \begin{bmatrix} 0\\ 0\\ 1/3\\ 0\\ 0\\ 0\\ 14/3\\ -1/3\\ \end{bmatrix}(\lambda \to \frac{1}{3}$$. Running this new x through a 2nd iteration of phase 2 gives me all inequalities correct except row 5. This gives me $$x= \begin{bmatrix} 0\\ 0\\ 1/3-0\lambda\\ 0\\ \lambda\\ 0\\ 14/3-0\lambda\\ -1/3-1\lambda\\ \end{bmatrix}$$
Since I can only crank lambda more and more positive, the last row will never reach 0.

8. Sep 21, 2011

Ray Vickson

I find it more straightforward to use "dictionaries" (essentially, the equations xB = B^(-1)b -B^(-1)N*xN and z = cb*B^(-1)b + [cN - cB*B^(-1)N]*xN, written out explicitly). Furthermore, being lazy I let Maple do all the work. Although strictly speaking you don't need the third artificial variable a3 (since v can serve just as well), I will include it. So, the variables are x1,x2,x3,wp,wn,a1,a2,a3 (wp, wn are the omega^(+) and omega^(-) variables), and the a_i are the three artificials. I will let z1 and z2 be the PhaseI and Phase II objectives, always regarded as basic variables. I will follow your steps: first basis = (a1,a2,a3,z1,z2), second is (x3,a2,a3,z1,z2).
>eqs:={-1*x1+2*x2+3*x3+a1=1,2*x1+3*x2+x3+a2=5,-5*x1-4*x2+x3+a3=wp-wn};
eqs := {-x1 + 2 x2 + 3 x3 + a1 = 1, 2 x1 + 3 x2 + x3 + a2 = 5,
-5 x1 - 4 x2 + x3 + a3 = wp - wn}
>S1:=solve(eqs union {z1=a1+a2+a3, z2=x2},{a1,a2,a3,z1,z2});
S1 := {z2 = x2, a1 = x1 - 2 x2 - 3 x3 + 1,
a2 = -2 x1 - 3 x2 - x3 + 5, a3 = 5 x1 + 4 x2 - x3 + wp - wn,
z1 = 4 x1 - x2 - 5 x3 + 6 + wp - wn}
(Note: this solves for a1,a2,a3,z1,z2 as functions of the others).
>S2:=solve(S1,{a1,a2,x3,z1,z2});
S2 := {z1 = -21 x1 - 21 x2 + 5 a3 - 4 wp + 4 wn + 6,
a1 = -14 x1 - 14 x2 + 3 a3 - 3 wp + 3 wn + 1, z2 = x2,
a2 = -7 x1 - 7 x2 + a3 - wp + wn + 5,
x3 = 5 x1 + 4 x2 - a3 + wp - wn}
Now you are running into trouble: you try to increase wn, and are stuck. Well, if you look at the current z1 equation z1 = -21x1 -21 x2 + 5a3 - 4pn + 4wn + 6, you can see that increasing wn is the wrong thing to do: it wants to increase z1 instead of decreasing it. Instead, try to increase x1 or x2 or pn, all of which have negative z1 coefficients. Just for fun, let's increase x1. When x1 increases to 1/14, a1 is driven to zero, so we swap x1 and a1:
>S3:=solve(S2,{x1,a2,x3,z1,z2});
{z2 = x2, x1 = (1/14)-x2 -(1/14)a1 + (3/14)a3 - (3/14)wp + (3/14)wn,
x3 = (5/14) - x2 - (5/14)a1 + (1/14)a3 - (1/14)wp + (1/14)wn,
a2 = (9/2) + (1/2)a1 - (1/2)a3 + (1/2)wp - (1/2)wn,
z1 = (9/2) + (3/2)a1 + (1/2)a3 + (1/2)wp -(1/2)wn, z2 = x2}
So, indeed, z1 has decreased from 6 to 9/2 in the current basic solution. We can decrease it further by increasing wn, and you can figure out what happens after that.

RGV

Last edited: Sep 21, 2011
9. Sep 22, 2011

Ray Vickson

Your problem lies with the second x-solution: you are not allowed to take \lambda > 0 because there is a 0 - \lambda in the last component, and you don't want any variable to become < 0. So, you need to limit the "increase" to lambda = 0; this means that the last variable leaves the basis, while x3 enters; but this will give a degenerate solution with basic variable x3 = 0 and with no change in the Phase I objective. However, if you do that basis change anyway, you will see that at the *next* basic solution you *can* make non-zero reductions in the value of the phase I objective.

RGV

10. Sep 22, 2011

zcd

So I change $a^8 \to a^3$ while keeping $\lambda=0$?

11. Sep 22, 2011

zcd

I made the switch, and the resulting value for $A^T y=\begin{bmatrix} 21\\ 21\\ 0\\ 4\\ -4\\ 1\\ 1\\ -4\\ \end{bmatrix}$

It seems like the cost went way up; is it safe to continue to apply phase 2?

12. Sep 22, 2011

Ray Vickson

Yes, exactly. I have done it and it works. Alternatively, you could have looked at row 5 instead of row 3, and you might not have encountered this problem at all.

Re: your next question: don't worry about the Phase II objective right now; you are still trying to find a feasible solution (or to show that the problem is infeasible). The only objective you should be concerned with now is the Phase I objective (although some authors try to combine the two in the so-called "big-M Method"---but that is never used in real-world computer codes).

RGV