Simplex method lp

Problema 2

Use the simplex algorithm to solve the following LP:

Max z = 2x1 + x2
s.t. 3x1 + x2 ≤ 6
x1 + x2 ≤ 4
x1 ≥ 0, x2 urs

Due to x2 is urs:
X2 = x’2 – x’’2Max z = 2x1 + x’2 – x’’2
3x1 + x’2 – x’’2 ≤ 6
x1 + x’2 – x’’2 ≤ 4
x1, x’2, x’’2 ≥ 0

Standard Form:

z – 2x1 – x’2 + x’’2 = 0
3x1 + x’2 – x’’2 +s1 = 6
x1 + x’2 – x’’2 + s2 = 4

Using: BV={z, s1, s2} NBV={x1, x’2, x’’2}

|z|x1|x'2|x''2|s1|s2|rhs|BV|Ratio|
Row 0|1|-2|-1|1|0|0|0|z=0| |
Row1|0|3|1|-1|1|0|6|s1=6|2*|
Row 2|0|1|1|-1|0|1|4|s2=4|4|

We choose x1 as the entering variable.

Then, to make x1 coefficient = 0 in Row 0:

Dividing Row 1 by 3:

Row1’ --> x1 + 1/3x’2 – 1/3 x’’2 + s1 = 2Replacing Row 0 by 2(Row 1’) + Row 0:

2x1 + 2/3x’2 – 2/3x’’2 + 2/3s1 – 4 + z – 2x1 – x’2 + x’’2 = 0
Row 0’ --> z – 1/3x’2 + 1/3x’’2 + 2/3s1 = 4

Replacing Row 2 by -1(Row 1’) + Row2:

-x1 – 1/3x’2 + 1/3x’’2 – 1/3s1 + 2 + x1 + x’2 – x’’2 + s2 – 4 = 0
Row 2’ --> 2/3x’2 – 2/3x’’2 – 1/3s1 + s2 = 2

Using: BV={z, x1, s2} NBV={s1, x’2, x’’2}

|z|x1|x'2|x''2|s1|s2|rhs|BV|Ratio|
Row 0'|1|0|-1/3| 1/3| 2/3|0 |4 |z=4| |
Row 1'|0|1| 1/3|- 1/3| 1/3|0 |2 |x1=2|6|
Row 2'|0|0| 2/3|- 2/3|- 1/3|1 |2 |s2=2|3*|

We choose x’2 as the entering variable.

Then, to make x’2coefficient = 0 in Row 0’:

Multiplying Row 2’ by 3/2:

3/2(2/3x’2 – 2/3x’’2 – 1/3s1 + s2 – 2) = 0
Row 2’’ --> x’2 – x’’2 – 1/2s1 + 3/2s2 = 3

Replacing Row 0’ by 1/3(Row 2’’) + Row 0’:1/3(x’2 – x’’2 – 1/2s1 + 3/2s2 – 3) + z – 1/3x’2 + 1/3x’’2 + 2/3s1 – 4 = 0
Row 0’’ --> z + 11/18s1 + 3/2s2 = 7

Replacing Row 1’ by -1/3(Row 2’’) + Row 1’:

-1/3(x’2 – x’’2 – 1/2s1 + 3/2s2 – 3) + x1 +1/3x’2 – 1/3 x’’2 + s1 – 2 = 0
Row 1’’ --> x1 + 7/18s1 – 1/2s2 = 1

|z|x1|x'2|x''2|s1|s2|rhs|BV|
Row 0''|1|0|0 |0 |11/18|3/2|7 |z=7|
Row 1''|0|1|0 |0 | 7/8|- 1/2|1...