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?