Linear Programming Problem -- a walk through
Reading the data file: lp_demo_01c4.txt
Number of variables set to 2
line 1: -3 1 le 4 ---> Inequality is: -3 x1
+ 1 x2
≤
4
line 2: -1 1 le 6 ---> Inequality is: -1 x1
+ 1 x2
≤
6
line 3: -1 3 le 24 ---> Inequality is: -1 x1
+ 3 x2
≤
24
line 4: 2 3 le 42 ---> Inequality is: 2 x1
+ 3 x2
≤
42
line 5: 3 2 le 43 ---> Inequality is: 3 x1
+ 2 x2
≤
43
line 6: 5 2 le 65 ---> Inequality is: 5 x1
+ 2 x2
≤
65
line 7: maximize -1 4 ---> set Maximize:
-1 x1
+ 4 x2
Create the Initial Tableau
After reconfiguring the objective function and converting any '≥' constraints
to a '≤' form, we can produce the following tableau:
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| s1 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
-1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
6 |
| s3 |
-1 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
24 |
| s4 |
2 |
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
42 |
| s5 |
3 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
43 |
| s6 |
5 |
2 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
65 |
| |
1 |
-4 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Processing
There is at least one negative value in the
last row (excluding the final column). Therefore we need to start the
regular simplex processing algorithm.
The lowest negative value in the last row is -4 and
that is in column 2. So make column 2 the work column.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| s1 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
-1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
6 |
| s3 |
-1 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
24 |
| s4 |
2 |
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
42 |
| s5 |
3 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
43 |
| s6 |
5 |
2 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
65 |
| |
1 |
-4 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
The lowest ratio between positive values in column 2 and corresponding values in the the final column is 4 and
that is in row 1. So make row 1 the work row.
That makes the item in row 1 and column 2 the pivot item.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| s1 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
-1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
6 |
| s3 |
-1 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
24 |
| s4 |
2 |
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
42 |
| s5 |
3 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
43 |
| s6 |
5 |
2 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
65 |
| |
1 |
-4 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Since this is alread the value 1 we need not change it.
Now use the elementary row operation *row+ to change the
other items in column 2 to 0.
- multiply row 1 by -1 and add to row 2.
- multiply row 1 by -3 and add to row 3.
- multiply row 1 by -3 and add to row 4.
- multiply row 1 by -2 and add to row 5.
- multiply row 1 by -2 and add to row 6.
- multiply row 1 by 4 and add to row 7.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| s1 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
2 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
| s3 |
8 |
0 |
-3 |
0 |
1 |
0 |
0 |
0 |
0 |
12 |
| s4 |
11 |
0 |
-3 |
0 |
0 |
1 |
0 |
0 |
0 |
30 |
| s5 |
9 |
0 |
-2 |
0 |
0 |
0 |
1 |
0 |
0 |
35 |
| s6 |
11 |
0 |
-2 |
0 |
0 |
0 |
0 |
1 |
0 |
57 |
| |
-11 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
16 |
Now we need to copy the heading for the work column (column 2) to the
heading for the work row (row 1).
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
2 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
| s3 |
8 |
0 |
-3 |
0 |
1 |
0 |
0 |
0 |
0 |
12 |
| s4 |
11 |
0 |
-3 |
0 |
0 |
1 |
0 |
0 |
0 |
30 |
| s5 |
9 |
0 |
-2 |
0 |
0 |
0 |
1 |
0 |
0 |
35 |
| s6 |
11 |
0 |
-2 |
0 |
0 |
0 |
0 |
1 |
0 |
57 |
| |
-11 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
16 |
Having finished the steps of the processing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the processing steps.
The lowest negative value in the last row is -11 and
that is in column 1. So make column 1 the work column.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
2 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
| s3 |
8 |
0 |
-3 |
0 |
1 |
0 |
0 |
0 |
0 |
12 |
| s4 |
11 |
0 |
-3 |
0 |
0 |
1 |
0 |
0 |
0 |
30 |
| s5 |
9 |
0 |
-2 |
0 |
0 |
0 |
1 |
0 |
0 |
35 |
| s6 |
11 |
0 |
-2 |
0 |
0 |
0 |
0 |
1 |
0 |
57 |
| |
-11 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
16 |
The lowest ratio between positive values in column 1 and corresponding values in the the final column is 1 and
that is in row 2. So make row 2 the work row.
That makes the item in row 2 and column 1 the pivot item.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
2 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
| s3 |
8 |
0 |
-3 |
0 |
1 |
0 |
0 |
0 |
0 |
12 |
| s4 |
11 |
0 |
-3 |
0 |
0 |
1 |
0 |
0 |
0 |
30 |
| s5 |
9 |
0 |
-2 |
0 |
0 |
0 |
1 |
0 |
0 |
35 |
| s6 |
11 |
0 |
-2 |
0 |
0 |
0 |
0 |
1 |
0 |
57 |
| |
-11 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
16 |
Use the elementary row operation *row to change the
pivot item to be 1. That is, multiply row 2 by
1 / 2.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
-3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
| s2 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
| s3 |
8 |
0 |
-3 |
0 |
1 |
0 |
0 |
0 |
0 |
12 |
| s4 |
11 |
0 |
-3 |
0 |
0 |
1 |
0 |
0 |
0 |
30 |
| s5 |
9 |
0 |
-2 |
0 |
0 |
0 |
1 |
0 |
0 |
35 |
| s6 |
11 |
0 |
-2 |
0 |
0 |
0 |
0 |
1 |
0 |
57 |
| |
-11 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
16 |
Now use the elementary row operation *row+ to change the
other items in column 1 to 0.
- multiply row 2 by 3 and add to row 1.
- multiply row 2 by -8 and add to row 3.
- multiply row 2 by -11 and add to row 4.
- multiply row 2 by -9 and add to row 5.
- multiply row 2 by -11 and add to row 6.
- multiply row 2 by 11 and add to row 7.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
-1/2 |
3/2 |
0 |
0 |
0 |
0 |
0 |
7 |
| s2 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
| s3 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
5/2 |
-11/2 |
0 |
1 |
0 |
0 |
0 |
19 |
| s5 |
0 |
0 |
5/2 |
-9/2 |
0 |
0 |
1 |
0 |
0 |
26 |
| s6 |
0 |
0 |
7/2 |
-11/2 |
0 |
0 |
0 |
1 |
0 |
46 |
| |
0 |
0 |
-3/2 |
11/2 |
0 |
0 |
0 |
0 |
1 |
27 |
Now we need to copy the heading for the work column (column 1) to the
heading for the work row (row 2).
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
-1/2 |
3/2 |
0 |
0 |
0 |
0 |
0 |
7 |
| x1 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
| s3 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
5/2 |
-11/2 |
0 |
1 |
0 |
0 |
0 |
19 |
| s5 |
0 |
0 |
5/2 |
-9/2 |
0 |
0 |
1 |
0 |
0 |
26 |
| s6 |
0 |
0 |
7/2 |
-11/2 |
0 |
0 |
0 |
1 |
0 |
46 |
| |
0 |
0 |
-3/2 |
11/2 |
0 |
0 |
0 |
0 |
1 |
27 |
Having finished the steps of the processing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the processing steps.
The lowest negative value in the last row is -3 / 2 = -1.5 and
that is in column 3. So make column 3 the work column.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
-1/2 |
3/2 |
0 |
0 |
0 |
0 |
0 |
7 |
| x1 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
| s3 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
5/2 |
-11/2 |
0 |
1 |
0 |
0 |
0 |
19 |
| s5 |
0 |
0 |
5/2 |
-9/2 |
0 |
0 |
1 |
0 |
0 |
26 |
| s6 |
0 |
0 |
7/2 |
-11/2 |
0 |
0 |
0 |
1 |
0 |
46 |
| |
0 |
0 |
-3/2 |
11/2 |
0 |
0 |
0 |
0 |
1 |
27 |
The lowest ratio between positive values in column 3 and corresponding values in the the final column is 4 and
that is in row 3. So make row 3 the work row.
That makes the item in row 3 and column 3 the pivot item.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
-1/2 |
3/2 |
0 |
0 |
0 |
0 |
0 |
7 |
| x1 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
| s3 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
5/2 |
-11/2 |
0 |
1 |
0 |
0 |
0 |
19 |
| s5 |
0 |
0 |
5/2 |
-9/2 |
0 |
0 |
1 |
0 |
0 |
26 |
| s6 |
0 |
0 |
7/2 |
-11/2 |
0 |
0 |
0 |
1 |
0 |
46 |
| |
0 |
0 |
-3/2 |
11/2 |
0 |
0 |
0 |
0 |
1 |
27 |
Since this is alread the value 1 we need not change it.
Now use the elementary row operation *row+ to change the
other items in column 3 to 0.
- multiply row 3 by 1 / 2
and add to row 1.
- multiply row 3 by 1 / 2
and add to row 2.
- multiply row 3 by -5 / 2
and add to row 4.
- multiply row 3 by -5 / 2
and add to row 5.
- multiply row 3 by -7 / 2
and add to row 6.
- multiply row 3 by 3 / 2
and add to row 7.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
9 |
| x1 |
1 |
0 |
0 |
-3/2 |
1/2 |
0 |
0 |
0 |
0 |
3 |
| s3 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
0 |
9/2 |
-5/2 |
1 |
0 |
0 |
0 |
9 |
| s5 |
0 |
0 |
0 |
11/2 |
-5/2 |
0 |
1 |
0 |
0 |
16 |
| s6 |
0 |
0 |
0 |
17/2 |
-7/2 |
0 |
0 |
1 |
0 |
32 |
| |
0 |
0 |
0 |
-1/2 |
3/2 |
0 |
0 |
0 |
1 |
33 |
Now we need to copy the heading for the work column (column 3) to the
heading for the work row (row 3).
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
9 |
| x1 |
1 |
0 |
0 |
-3/2 |
1/2 |
0 |
0 |
0 |
0 |
3 |
| s1 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
0 |
9/2 |
-5/2 |
1 |
0 |
0 |
0 |
9 |
| s5 |
0 |
0 |
0 |
11/2 |
-5/2 |
0 |
1 |
0 |
0 |
16 |
| s6 |
0 |
0 |
0 |
17/2 |
-7/2 |
0 |
0 |
1 |
0 |
32 |
| |
0 |
0 |
0 |
-1/2 |
3/2 |
0 |
0 |
0 |
1 |
33 |
Having finished the steps of the processing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the processing steps.
The lowest negative value in the last row is -1 / 2 = -0.5 and
that is in column 4. So make column 4 the work column.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
9 |
| x1 |
1 |
0 |
0 |
-3/2 |
1/2 |
0 |
0 |
0 |
0 |
3 |
| s1 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
0 |
9/2 |
-5/2 |
1 |
0 |
0 |
0 |
9 |
| s5 |
0 |
0 |
0 |
11/2 |
-5/2 |
0 |
1 |
0 |
0 |
16 |
| s6 |
0 |
0 |
0 |
17/2 |
-7/2 |
0 |
0 |
1 |
0 |
32 |
| |
0 |
0 |
0 |
-1/2 |
3/2 |
0 |
0 |
0 |
1 |
33 |
The lowest ratio between positive values in column 4 and corresponding values in the the final column is 2 and
that is in row 4. So make row 4 the work row.
That makes the item in row 4 and column 4 the pivot item.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
9 |
| x1 |
1 |
0 |
0 |
-3/2 |
1/2 |
0 |
0 |
0 |
0 |
3 |
| s1 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
0 |
9/2 |
-5/2 |
1 |
0 |
0 |
0 |
9 |
| s5 |
0 |
0 |
0 |
11/2 |
-5/2 |
0 |
1 |
0 |
0 |
16 |
| s6 |
0 |
0 |
0 |
17/2 |
-7/2 |
0 |
0 |
1 |
0 |
32 |
| |
0 |
0 |
0 |
-1/2 |
3/2 |
0 |
0 |
0 |
1 |
33 |
Use the elementary row operation *row to change the
pivot item to be 1. That is, multiply row 4 by
2 / 9.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
0 |
-1/2 |
1/2 |
0 |
0 |
0 |
0 |
9 |
| x1 |
1 |
0 |
0 |
-3/2 |
1/2 |
0 |
0 |
0 |
0 |
3 |
| s1 |
0 |
0 |
1 |
-4 |
1 |
0 |
0 |
0 |
0 |
4 |
| s4 |
0 |
0 |
0 |
1 |
-5/9 |
2/9 |
0 |
0 |
0 |
2 |
| s5 |
0 |
0 |
0 |
11/2 |
-5/2 |
0 |
1 |
0 |
0 |
16 |
| s6 |
0 |
0 |
0 |
17/2 |
-7/2 |
0 |
0 |
1 |
0 |
32 |
| |
0 |
0 |
0 |
-1/2 |
3/2 |
0 |
0 |
0 |
1 |
33 |
Now use the elementary row operation *row+ to change the
other items in column 4 to 0.
- multiply row 4 by 1 / 2
and add to row 1.
- multiply row 4 by 3 / 2
and add to row 2.
- multiply row 4 by 4 and add to row 3.
- multiply row 4 by -11 / 2
and add to row 5.
- multiply row 4 by -17 / 2
and add to row 6.
- multiply row 4 by 1 / 2
and add to row 7.
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
0 |
0 |
2/9 |
1/9 |
0 |
0 |
0 |
10 |
| x1 |
1 |
0 |
0 |
0 |
-1/3 |
1/3 |
0 |
0 |
0 |
6 |
| s1 |
0 |
0 |
1 |
0 |
-11/9 |
8/9 |
0 |
0 |
0 |
12 |
| s4 |
0 |
0 |
0 |
1 |
-5/9 |
2/9 |
0 |
0 |
0 |
2 |
| s5 |
0 |
0 |
0 |
0 |
5/9 |
-11/9 |
1 |
0 |
0 |
5 |
| s6 |
0 |
0 |
0 |
0 |
11/9 |
-17/9 |
0 |
1 |
0 |
15 |
| |
0 |
0 |
0 |
0 |
11/9 |
1/9 |
0 |
0 |
1 |
34 |
Now we need to copy the heading for the work column (column 4) to the
heading for the work row (row 4).
| |
x1 |
x2 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
z |
|
| x2 |
0 |
1 |
0 |
0 |
2/9 |
1/9 |
0 |
0 |
0 |
10 |
| x1 |
1 |
0 |
0 |
0 |
-1/3 |
1/3 |
0 |
0 |
0 |
6 |
| s1 |
0 |
0 |
1 |
0 |
-11/9 |
8/9 |
0 |
0 |
0 |
12 |
| s2 |
0 |
0 |
0 |
1 |
-5/9 |
2/9 |
0 |
0 |
0 |
2 |
| s5 |
0 |
0 |
0 |
0 |
5/9 |
-11/9 |
1 |
0 |
0 |
5 |
| s6 |
0 |
0 |
0 |
0 |
11/9 |
-17/9 |
0 |
1 |
0 |
15 |
| |
0 |
0 |
0 |
0 |
11/9 |
1/9 |
0 |
0 |
1 |
34 |
Having finished the steps of the processing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the processing steps.
There are no more negative values is the final column.
Therefore, regular processing is done...
Display the answers. Note that if a variable does not
appear in the following list then it should be given the value 0.
The list is generated from the final tableau by reading down the
labels on the left and assigning to each the value in the rightmost
column. Any slack variables in the labels on the left will be
included in the list, but they can be ignored.
When
- x2 = 10
- x1 = 6
- s1 = 12
- s2 = 2
- s5 = 5
- s6 = 15
the objective function has a
Maximum = 34
©Roger M. Palay Saline, MI 48176 October, 2010