Linear Programming degenerate case

[zcd]

Homework Statement

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$

Homework Equations

2-phase simplex method

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.

 

[Ray Vickson]

Homework Statement

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$

Homework Equations

2-phase simplex method

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.

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

 

[zcd]

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

 

[Ray Vickson]

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

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

 

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

 

[Ray Vickson]

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$

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

 

[zcd]

For phase 1, I rewrote the problem as minimize z₁+z₂+z₃ 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.

 

[Ray Vickson]

For phase 1, I rewrote the problem as minimize z₁+z₂+z₃ 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.

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

 

[Ray Vickson]

For phase 1, I rewrote the problem as minimize z₁+z₂+z₃ 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.

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

 

[zcd]

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

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

 

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

 

[Ray Vickson]

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

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