Hello everybody, I am trying to understand the simplex algorithm using LU Decomposition. I have looked for a complete example through many books but haven't found one anywhere.
I am encountering a problem after the first update in U through the LU Decomposition method.
I hope my notation is not very hard to understand. I'm a newbie to Latex.
I'm working on this simplex example:
(min)f(x)=x1+x2+2*x3
constraints:
2*x1+2*x2+3*x3=4
x1+2*x2+2*x3=3
First I introduce 2 artificial variables: x4 and x5
Using simplex with pivoting would lead to the following tables:
A b theta
2 2 1 1 0 4 2
1 2 2 0 1 3 1.5
-3 -4 -3 0 0 delta
x5 is out, x2 is in
A b theta
1 0 -1 1 -1 1 1
0.5 1 1 0 0.5 1.5 3
-1 0 1 0 0 0
x4 is out, x1 is in
A b theta
1 0 -1 1 -1 1
0 1 1.5 -0.5 1 1
0 0 0 0 0 0
this leads to optimal result for phase 1
phase 2:
A b
1 0 -1 1
0 1 3/2 1
0 0 3/2 delta
so x1=1, x2=1 is the optimal result for the problem.
I am using the following LU Decomposition implementation:
1.
L*U*xB=b
solved this way:
first L*c=b
then U*xB=c
2. \lambda*L*U=cB (the coefficients of the function to be minimized corresponding to the current base)
solved c*U=cB
then \lambda*L=c
rD is the modification to the function resulting from the entrance of one unit of a variable
rD=cD-\lambda*D (D is the matrix including the nonbasis columns)
3. determine which vector aQ is to enter the basis (min rD <0)
and find its value in the current basis
L*U*yQ=aQ
where yQ is aQ in the current basis.
4. determine the vector to exit the basis (min xB/yiQ yQ - the column to enter the basis)
then eliminate this vector from the basis and add the new vector to the end of U.
this requires again ellimination to keep U in the upper triangular form.
the elimination changes the value of U and subsequently the value of L.
with this method the problem will go like this (i am skipping step 2, cos it works well in this example) .
first step:
initial U includes 2 columns: the two artificial variables
U =
1 0
0 1
L has also, the values of I.
xB is b
As before, x5 is out, x2 is in
x5 in this basis has the same value as before: 2 2
so U gets
1 2
0 2
U keeps upper triangular form so no change.
step 2
(1 2) *xB = 4
0 2 3
so xB in the current base is (1 1.5)
x4 is out, x1 is in
(1 2)*y = 2
0 2 1
x1 in the current base is (1 0.5)
this updates U to
2 1
2 0.5
to get U into upper triangular form I multiply it with
(1 0 )
-1 1
so the new U is
2 1
0 -0.5
L=I* (1 0)
-1 1
step 3
the new xB is found out this way
L*U*xB=b
L*c=b
so
(1 0 )*(c1 c2)=(4 3)
-1 1
so c1=4, c2=-1
then U*xb=c
so
(2 1 )*(x1 x2)=(4 -1)
0 0.5
so xB is (1 2). This one differs from the result found through solving using pivoting.
This value of xB breaks both of the constraints.
I see this happens after the update of U so it has to be related with it. Do you have any idea where am I wrong?