zcd said:
For phase 1, I rewrote the problem as minimize z1+z2+z3 subject to
\begin{bmatrix} <br />
-1 & 2 & 3 & 0 & 0 & 1 & 0 & 0\\ <br />
2 & 3 & 1 & 0 & 0 & 0 & 1 & 0\\ <br />
-5 & -4 & 1 & -1 & 1 & 0 & 0 & 1\\ <br />
\end{bmatrix} <br />
\begin{bmatrix} <br />
x_1\\ <br />
x_2\\ <br />
x_3\\<br />
u\\<br />
v\\<br />
z_1\\<br />
z_2\\<br />
z_3\\ <br />
\end{bmatrix}<br />
= <br />
\begin{bmatrix} <br />
1 \\ <br />
5 \\ <br />
0 \\<br />
\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=<br />
\begin{bmatrix} <br />
0\\ <br />
0\\ <br />
0\\<br />
0\\<br />
0\\<br />
1\\<br />
5\\<br />
0\\ <br />
\end{bmatrix}
solving y=(M^T)^{-1}\hat{c}=\begin{bmatrix} <br />
1\\ <br />
1\\ <br />
1\\ <br />
\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} <br />
3\\ <br />
1\\ <br />
1\\ <br />
\end{bmatrix} and this helps me find a new
x=<br />
\begin{bmatrix} <br />
0\\ <br />
0\\ <br />
\lambda\\<br />
0\\<br />
0\\<br />
1-3\lambda\\<br />
5-\lambda\\<br />
0-\lambda\\ <br />
\end{bmatrix}<br />
\to x=<br />
\begin{bmatrix} <br />
0\\ <br />
0\\ <br />
1/3\\<br />
0\\<br />
0\\<br />
0\\<br />
14/3\\<br />
-1/3\\ <br />
\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=<br />
\begin{bmatrix} <br />
0\\ <br />
0\\ <br />
1/3-0\lambda\\<br />
0\\<br />
\lambda\\<br />
0\\<br />
14/3-0\lambda\\<br />
-1/3-1\lambda\\ <br />
\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
