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

122 0 1 3 1.5

-3 -4 -3 0 0 delta

x5 is out, x2 is in

A b theta

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