Linear Programming Problem -- a walk through
Reading the data file: lp_demo_16.txt
Number of variables set to 4
line 1: -39 3 -57 -52 ge -1511 ---> Inequality is: -39 x1
+ 3 x2
+ -57 x3
+ -52 x4
≥
-1511
line 2: 151 -29 99 13 le 2553 ---> Inequality is: 151 x1
+ -29 x2
+ 99 x3
+ 13 x4
≤
2553
line 3: 131 -33 31 -24 ge 1125 ---> Inequality is: 131 x1
+ -33 x2
+ 31 x3
+ -24 x4
≥
1125
line 4: 62 -19 -9 107 ge 1131 ---> Inequality is: 62 x1
+ -19 x2
+ -9 x3
+ 107 x4
≥
1131
line 5: 43 -95 17 -42 le -825 ---> Inequality is: 43 x1
+ -95 x2
+ 17 x3
+ -42 x4
≤
-825
line 6: 218 -205 72 -142 le -480 ---> Inequality is: 218 x1
+ -205 x2
+ 72 x3
+ -142 x4
≤
-480
line 7: 95 -99 93 -72 ge -201 ---> Inequality is: 95 x1
+ -99 x2
+ 93 x3
+ -72 x4
≥
-201
line 8: 215 -325 297 -199 ge -1623 ---> Inequality is: 215 x1
+ -325 x2
+ 297 x3
+ -199 x4
≥
-1623
line 9: minimize -7 3 5 3 ---> set Minimize:
-7 x1
+ 3 x2
+ 5 x3
+ 3 x4
Create the Initial Tableau
After reconfiguring the objective function and converting any '≥' constraints
to a '≤' form, we can produce the following tableau:
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
39 |
-3 |
57 |
52 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1511 |
| s2 |
151 |
-29 |
99 |
13 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2553 |
| s3 |
-131 |
33 |
-31 |
24 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1125 |
| s4 |
-62 |
19 |
9 |
-107 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1131 |
| s5 |
43 |
-95 |
17 |
-42 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-825 |
| s6 |
218 |
-205 |
72 |
-142 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-480 |
| s7 |
-95 |
99 |
-93 |
72 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
201 |
| s8 |
-215 |
325 |
-297 |
199 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1623 |
| |
-7 |
3 |
5 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Preprocessing
There is at least one negative value in the
last column (excluding the final row). Therefore we need to start the
preprocessing algorithm.
The lowest negative value in the last column is -1131 and
that is in row 4. Therefore, make row 4 the work row.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
39 |
-3 |
57 |
52 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1511 |
| s2 |
151 |
-29 |
99 |
13 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2553 |
| s3 |
-131 |
33 |
-31 |
24 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1125 |
| s4 |
-62 |
19 |
9 |
-107 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1131 |
| s5 |
43 |
-95 |
17 |
-42 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-825 |
| s6 |
218 |
-205 |
72 |
-142 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-480 |
| s7 |
-95 |
99 |
-93 |
72 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
201 |
| s8 |
-215 |
325 |
-297 |
199 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1623 |
| |
-7 |
3 |
5 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
The lowest negative value in row 4 is -107 and
that is in column 4. Therefore, make column 4 the work column.
That makes the item in row 4 and column 4 the pivot item.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
39 |
-3 |
57 |
52 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1511 |
| s2 |
151 |
-29 |
99 |
13 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2553 |
| s3 |
-131 |
33 |
-31 |
24 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1125 |
| s4 |
-62 |
19 |
9 |
-107 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1131 |
| s5 |
43 |
-95 |
17 |
-42 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-825 |
| s6 |
218 |
-205 |
72 |
-142 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-480 |
| s7 |
-95 |
99 |
-93 |
72 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
201 |
| s8 |
-215 |
325 |
-297 |
199 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1623 |
| |
-7 |
3 |
5 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Use the elementary row operation *row to change the
pivot item to be 1. That is, multiply row 4 by
-1 / 107.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
39 |
-3 |
57 |
52 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1511 |
| s2 |
151 |
-29 |
99 |
13 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2553 |
| s3 |
-131 |
33 |
-31 |
24 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1125 |
| s4 |
62/107 |
-19/107 |
-9/107 |
1 |
0 |
0 |
0 |
-1/107 |
0 |
0 |
0 |
0 |
0 |
1131/107 |
| s5 |
43 |
-95 |
17 |
-42 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-825 |
| s6 |
218 |
-205 |
72 |
-142 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-480 |
| s7 |
-95 |
99 |
-93 |
72 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
201 |
| s8 |
-215 |
325 |
-297 |
199 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1623 |
| |
-7 |
3 |
5 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Now use the elementary row operation *row+ to change the
other items in column 4 to 0.
- multiply row 4 by -52 and add to row 1.
- multiply row 4 by -13 and add to row 2.
- multiply row 4 by -24 and add to row 3.
- multiply row 4 by +42 and add to row 5.
- multiply row 4 by +142 and add to row 6.
- multiply row 4 by -72 and add to row 7.
- multiply row 4 by -199 and add to row 8.
- multiply row 4 by -3 and add to row 9.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
949/107 |
667/107 |
6567/107 |
0 |
1 |
0 |
0 |
52/107 |
0 |
0 |
0 |
0 |
0 |
102865/107 |
| s2 |
15351/107 |
-2856/107 |
10710/107 |
0 |
0 |
1 |
0 |
13/107 |
0 |
0 |
0 |
0 |
0 |
258468/107 |
| s3 |
-15505/107 |
3987/107 |
-3101/107 |
0 |
0 |
0 |
1 |
24/107 |
0 |
0 |
0 |
0 |
0 |
-147519/107 |
| s4 |
62/107 |
-19/107 |
-9/107 |
1 |
0 |
0 |
0 |
-1/107 |
0 |
0 |
0 |
0 |
0 |
1131/107 |
| s5 |
7205/107 |
-10963/107 |
1441/107 |
0 |
0 |
0 |
0 |
-42/107 |
1 |
0 |
0 |
0 |
0 |
-40773/107 |
| s6 |
32130/107 |
-24633/107 |
6426/107 |
0 |
0 |
0 |
0 |
-142/107 |
0 |
1 |
0 |
0 |
0 |
109242/107 |
| s7 |
-14629/107 |
11961/107 |
-9303/107 |
0 |
0 |
0 |
0 |
72/107 |
0 |
0 |
1 |
0 |
0 |
-59925/107 |
| s8 |
-35343/107 |
38556/107 |
-29988/107 |
0 |
0 |
0 |
0 |
199/107 |
0 |
0 |
0 |
1 |
0 |
-51408/107 |
| |
-935/107 |
378/107 |
562/107 |
0 |
0 |
0 |
0 |
3/107 |
0 |
0 |
0 |
0 |
1 |
-3393/107 |
Now we need to copy the heading for the work column (column 4) to the
heading for the work row (row 4).
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
949/107 |
667/107 |
6567/107 |
0 |
1 |
0 |
0 |
52/107 |
0 |
0 |
0 |
0 |
0 |
102865/107 |
| s2 |
15351/107 |
-2856/107 |
10710/107 |
0 |
0 |
1 |
0 |
13/107 |
0 |
0 |
0 |
0 |
0 |
258468/107 |
| s3 |
-15505/107 |
3987/107 |
-3101/107 |
0 |
0 |
0 |
1 |
24/107 |
0 |
0 |
0 |
0 |
0 |
-147519/107 |
| x4 |
62/107 |
-19/107 |
-9/107 |
1 |
0 |
0 |
0 |
-1/107 |
0 |
0 |
0 |
0 |
0 |
1131/107 |
| s5 |
7205/107 |
-10963/107 |
1441/107 |
0 |
0 |
0 |
0 |
-42/107 |
1 |
0 |
0 |
0 |
0 |
-40773/107 |
| s6 |
32130/107 |
-24633/107 |
6426/107 |
0 |
0 |
0 |
0 |
-142/107 |
0 |
1 |
0 |
0 |
0 |
109242/107 |
| s7 |
-14629/107 |
11961/107 |
-9303/107 |
0 |
0 |
0 |
0 |
72/107 |
0 |
0 |
1 |
0 |
0 |
-59925/107 |
| s8 |
-35343/107 |
38556/107 |
-29988/107 |
0 |
0 |
0 |
0 |
199/107 |
0 |
0 |
0 |
1 |
0 |
-51408/107 |
| |
-935/107 |
378/107 |
562/107 |
0 |
0 |
0 |
0 |
3/107 |
0 |
0 |
0 |
0 |
1 |
-3393/107 |
Having finished the steps of the preprocessing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the preprocessing steps.
The lowest negative value in the last column is -147519 / 107 = -1378.68224299065 and
that is in row 3. Therefore, make row 3 the work row.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
949/107 |
667/107 |
6567/107 |
0 |
1 |
0 |
0 |
52/107 |
0 |
0 |
0 |
0 |
0 |
102865/107 |
| s2 |
15351/107 |
-2856/107 |
10710/107 |
0 |
0 |
1 |
0 |
13/107 |
0 |
0 |
0 |
0 |
0 |
258468/107 |
| s3 |
-15505/107 |
3987/107 |
-3101/107 |
0 |
0 |
0 |
1 |
24/107 |
0 |
0 |
0 |
0 |
0 |
-147519/107 |
| x4 |
62/107 |
-19/107 |
-9/107 |
1 |
0 |
0 |
0 |
-1/107 |
0 |
0 |
0 |
0 |
0 |
1131/107 |
| s5 |
7205/107 |
-10963/107 |
1441/107 |
0 |
0 |
0 |
0 |
-42/107 |
1 |
0 |
0 |
0 |
0 |
-40773/107 |
| s6 |
32130/107 |
-24633/107 |
6426/107 |
0 |
0 |
0 |
0 |
-142/107 |
0 |
1 |
0 |
0 |
0 |
109242/107 |
| s7 |
-14629/107 |
11961/107 |
-9303/107 |
0 |
0 |
0 |
0 |
72/107 |
0 |
0 |
1 |
0 |
0 |
-59925/107 |
| s8 |
-35343/107 |
38556/107 |
-29988/107 |
0 |
0 |
0 |
0 |
199/107 |
0 |
0 |
0 |
1 |
0 |
-51408/107 |
| |
-935/107 |
378/107 |
562/107 |
0 |
0 |
0 |
0 |
3/107 |
0 |
0 |
0 |
0 |
1 |
-3393/107 |
The lowest negative value in row 3 is -15505 / 107 = -144.906542056075 and
that is in column 1. Therefore, make column 1 the work column.
That makes the item in row 3 and column 1 the pivot item.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
949/107 |
667/107 |
6567/107 |
0 |
1 |
0 |
0 |
52/107 |
0 |
0 |
0 |
0 |
0 |
102865/107 |
| s2 |
15351/107 |
-2856/107 |
10710/107 |
0 |
0 |
1 |
0 |
13/107 |
0 |
0 |
0 |
0 |
0 |
258468/107 |
| s3 |
-15505/107 |
3987/107 |
-3101/107 |
0 |
0 |
0 |
1 |
24/107 |
0 |
0 |
0 |
0 |
0 |
-147519/107 |
| x4 |
62/107 |
-19/107 |
-9/107 |
1 |
0 |
0 |
0 |
-1/107 |
0 |
0 |
0 |
0 |
0 |
1131/107 |
| s5 |
7205/107 |
-10963/107 |
1441/107 |
0 |
0 |
0 |
0 |
-42/107 |
1 |
0 |
0 |
0 |
0 |
-40773/107 |
| s6 |
32130/107 |
-24633/107 |
6426/107 |
0 |
0 |
0 |
0 |
-142/107 |
0 |
1 |
0 |
0 |
0 |
109242/107 |
| s7 |
-14629/107 |
11961/107 |
-9303/107 |
0 |
0 |
0 |
0 |
72/107 |
0 |
0 |
1 |
0 |
0 |
-59925/107 |
| s8 |
-35343/107 |
38556/107 |
-29988/107 |
0 |
0 |
0 |
0 |
199/107 |
0 |
0 |
0 |
1 |
0 |
-51408/107 |
| |
-935/107 |
378/107 |
562/107 |
0 |
0 |
0 |
0 |
3/107 |
0 |
0 |
0 |
0 |
1 |
-3393/107 |
Use the elementary row operation *row to change the
pivot item to be 1. That is, multiply row 3 by
-107 / 15505.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
949/107 |
667/107 |
6567/107 |
0 |
1 |
0 |
0 |
52/107 |
0 |
0 |
0 |
0 |
0 |
102865/107 |
| s2 |
15351/107 |
-2856/107 |
10710/107 |
0 |
0 |
1 |
0 |
13/107 |
0 |
0 |
0 |
0 |
0 |
258468/107 |
| s3 |
1 |
-9/35 |
1/5 |
0 |
0 |
0 |
-107/15505 |
-24/15505 |
0 |
0 |
0 |
0 |
0 |
333/35 |
| x4 |
62/107 |
-19/107 |
-9/107 |
1 |
0 |
0 |
0 |
-1/107 |
0 |
0 |
0 |
0 |
0 |
1131/107 |
| s5 |
7205/107 |
-10963/107 |
1441/107 |
0 |
0 |
0 |
0 |
-42/107 |
1 |
0 |
0 |
0 |
0 |
-40773/107 |
| s6 |
32130/107 |
-24633/107 |
6426/107 |
0 |
0 |
0 |
0 |
-142/107 |
0 |
1 |
0 |
0 |
0 |
109242/107 |
| s7 |
-14629/107 |
11961/107 |
-9303/107 |
0 |
0 |
0 |
0 |
72/107 |
0 |
0 |
1 |
0 |
0 |
-59925/107 |
| s8 |
-35343/107 |
38556/107 |
-29988/107 |
0 |
0 |
0 |
0 |
199/107 |
0 |
0 |
0 |
1 |
0 |
-51408/107 |
| |
-935/107 |
378/107 |
562/107 |
0 |
0 |
0 |
0 |
3/107 |
0 |
0 |
0 |
0 |
1 |
-3393/107 |
Now use the elementary row operation *row+ to change the
other items in column 1 to 0.
- multiply row 3 by -949 / 107
and add to row 1.
- multiply row 3 by -15351 / 107
and add to row 2.
- multiply row 3 by -62 / 107
and add to row 4.
- multiply row 3 by -7205 / 107
and add to row 5.
- multiply row 3 by -32130 / 107
and add to row 6.
- multiply row 3 by 14629 / 107
and add to row 7.
- multiply row 3 by 35343 / 107
and add to row 8.
- multiply row 3 by 935 / 107
and add to row 9.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
298/35 |
298/5 |
0 |
1 |
0 |
949/15505 |
7748/15505 |
0 |
0 |
0 |
0 |
0 |
30694/35 |
| s2 |
0 |
51/5 |
357/5 |
0 |
0 |
1 |
2193/2215 |
761/2215 |
0 |
0 |
0 |
0 |
0 |
5253/5 |
| s3 |
1 |
-9/35 |
1/5 |
0 |
0 |
0 |
-107/15505 |
-24/15505 |
0 |
0 |
0 |
0 |
0 |
333/35 |
| x4 |
0 |
-1/35 |
-1/5 |
1 |
0 |
0 |
62/15505 |
-131/15505 |
0 |
0 |
0 |
0 |
0 |
177/35 |
| s5 |
0 |
-596/7 |
0 |
0 |
0 |
0 |
1441/3101 |
-894/3101 |
1 |
0 |
0 |
0 |
0 |
-7152/7 |
| s6 |
0 |
-153 |
0 |
0 |
0 |
0 |
918/443 |
-382/443 |
0 |
1 |
0 |
0 |
0 |
-1836 |
| s7 |
0 |
2682/35 |
-298/5 |
0 |
0 |
0 |
-14629/15505 |
7152/15505 |
0 |
0 |
1 |
0 |
0 |
25926/35 |
| s8 |
0 |
1377/5 |
-1071/5 |
0 |
0 |
0 |
-5049/2215 |
2987/2215 |
0 |
0 |
0 |
1 |
0 |
13311/5 |
| |
0 |
9/7 |
7 |
0 |
0 |
0 |
-187/3101 |
45/3101 |
0 |
0 |
0 |
0 |
1 |
360/7 |
Now we need to copy the heading for the work column (column 1) to the
heading for the work row (row 3).
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
298/35 |
298/5 |
0 |
1 |
0 |
949/15505 |
7748/15505 |
0 |
0 |
0 |
0 |
0 |
30694/35 |
| s2 |
0 |
51/5 |
357/5 |
0 |
0 |
1 |
2193/2215 |
761/2215 |
0 |
0 |
0 |
0 |
0 |
5253/5 |
| x1 |
1 |
-9/35 |
1/5 |
0 |
0 |
0 |
-107/15505 |
-24/15505 |
0 |
0 |
0 |
0 |
0 |
333/35 |
| x4 |
0 |
-1/35 |
-1/5 |
1 |
0 |
0 |
62/15505 |
-131/15505 |
0 |
0 |
0 |
0 |
0 |
177/35 |
| s5 |
0 |
-596/7 |
0 |
0 |
0 |
0 |
1441/3101 |
-894/3101 |
1 |
0 |
0 |
0 |
0 |
-7152/7 |
| s6 |
0 |
-153 |
0 |
0 |
0 |
0 |
918/443 |
-382/443 |
0 |
1 |
0 |
0 |
0 |
-1836 |
| s7 |
0 |
2682/35 |
-298/5 |
0 |
0 |
0 |
-14629/15505 |
7152/15505 |
0 |
0 |
1 |
0 |
0 |
25926/35 |
| s8 |
0 |
1377/5 |
-1071/5 |
0 |
0 |
0 |
-5049/2215 |
2987/2215 |
0 |
0 |
0 |
1 |
0 |
13311/5 |
| |
0 |
9/7 |
7 |
0 |
0 |
0 |
-187/3101 |
45/3101 |
0 |
0 |
0 |
0 |
1 |
360/7 |
Having finished the steps of the preprocessing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the preprocessing steps.
The lowest negative value in the last column is -1836 and
that is in row 6. Therefore, make row 6 the work row.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
298/35 |
298/5 |
0 |
1 |
0 |
949/15505 |
7748/15505 |
0 |
0 |
0 |
0 |
0 |
30694/35 |
| s2 |
0 |
51/5 |
357/5 |
0 |
0 |
1 |
2193/2215 |
761/2215 |
0 |
0 |
0 |
0 |
0 |
5253/5 |
| x1 |
1 |
-9/35 |
1/5 |
0 |
0 |
0 |
-107/15505 |
-24/15505 |
0 |
0 |
0 |
0 |
0 |
333/35 |
| x4 |
0 |
-1/35 |
-1/5 |
1 |
0 |
0 |
62/15505 |
-131/15505 |
0 |
0 |
0 |
0 |
0 |
177/35 |
| s5 |
0 |
-596/7 |
0 |
0 |
0 |
0 |
1441/3101 |
-894/3101 |
1 |
0 |
0 |
0 |
0 |
-7152/7 |
| s6 |
0 |
-153 |
0 |
0 |
0 |
0 |
918/443 |
-382/443 |
0 |
1 |
0 |
0 |
0 |
-1836 |
| s7 |
0 |
2682/35 |
-298/5 |
0 |
0 |
0 |
-14629/15505 |
7152/15505 |
0 |
0 |
1 |
0 |
0 |
25926/35 |
| s8 |
0 |
1377/5 |
-1071/5 |
0 |
0 |
0 |
-5049/2215 |
2987/2215 |
0 |
0 |
0 |
1 |
0 |
13311/5 |
| |
0 |
9/7 |
7 |
0 |
0 |
0 |
-187/3101 |
45/3101 |
0 |
0 |
0 |
0 |
1 |
360/7 |
The lowest negative value in row 6 is -153 and
that is in column 2. Therefore, make column 2 the work column.
That makes the item in row 6 and column 2 the pivot item.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
298/35 |
298/5 |
0 |
1 |
0 |
949/15505 |
7748/15505 |
0 |
0 |
0 |
0 |
0 |
30694/35 |
| s2 |
0 |
51/5 |
357/5 |
0 |
0 |
1 |
2193/2215 |
761/2215 |
0 |
0 |
0 |
0 |
0 |
5253/5 |
| x1 |
1 |
-9/35 |
1/5 |
0 |
0 |
0 |
-107/15505 |
-24/15505 |
0 |
0 |
0 |
0 |
0 |
333/35 |
| x4 |
0 |
-1/35 |
-1/5 |
1 |
0 |
0 |
62/15505 |
-131/15505 |
0 |
0 |
0 |
0 |
0 |
177/35 |
| s5 |
0 |
-596/7 |
0 |
0 |
0 |
0 |
1441/3101 |
-894/3101 |
1 |
0 |
0 |
0 |
0 |
-7152/7 |
| s6 |
0 |
-153 |
0 |
0 |
0 |
0 |
918/443 |
-382/443 |
0 |
1 |
0 |
0 |
0 |
-1836 |
| s7 |
0 |
2682/35 |
-298/5 |
0 |
0 |
0 |
-14629/15505 |
7152/15505 |
0 |
0 |
1 |
0 |
0 |
25926/35 |
| s8 |
0 |
1377/5 |
-1071/5 |
0 |
0 |
0 |
-5049/2215 |
2987/2215 |
0 |
0 |
0 |
1 |
0 |
13311/5 |
| |
0 |
9/7 |
7 |
0 |
0 |
0 |
-187/3101 |
45/3101 |
0 |
0 |
0 |
0 |
1 |
360/7 |
Use the elementary row operation *row to change the
pivot item to be 1. That is, multiply row 6 by
-1 / 153.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
298/35 |
298/5 |
0 |
1 |
0 |
949/15505 |
7748/15505 |
0 |
0 |
0 |
0 |
0 |
30694/35 |
| s2 |
0 |
51/5 |
357/5 |
0 |
0 |
1 |
2193/2215 |
761/2215 |
0 |
0 |
0 |
0 |
0 |
5253/5 |
| x1 |
1 |
-9/35 |
1/5 |
0 |
0 |
0 |
-107/15505 |
-24/15505 |
0 |
0 |
0 |
0 |
0 |
333/35 |
| x4 |
0 |
-1/35 |
-1/5 |
1 |
0 |
0 |
62/15505 |
-131/15505 |
0 |
0 |
0 |
0 |
0 |
177/35 |
| s5 |
0 |
-596/7 |
0 |
0 |
0 |
0 |
1441/3101 |
-894/3101 |
1 |
0 |
0 |
0 |
0 |
-7152/7 |
| s6 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
2682/35 |
-298/5 |
0 |
0 |
0 |
-14629/15505 |
7152/15505 |
0 |
0 |
1 |
0 |
0 |
25926/35 |
| s8 |
0 |
1377/5 |
-1071/5 |
0 |
0 |
0 |
-5049/2215 |
2987/2215 |
0 |
0 |
0 |
1 |
0 |
13311/5 |
| |
0 |
9/7 |
7 |
0 |
0 |
0 |
-187/3101 |
45/3101 |
0 |
0 |
0 |
0 |
1 |
360/7 |
Now use the elementary row operation *row+ to change the
other items in column 2 to 0.
- multiply row 6 by -298 / 35
and add to row 1.
- multiply row 6 by -51 / 5
and add to row 2.
- multiply row 6 by 9 / 35
and add to row 3.
- multiply row 6 by 1 / 35
and add to row 4.
- multiply row 6 by 596 / 7
and add to row 5.
- multiply row 6 by -2682 / 35
and add to row 7.
- multiply row 6 by -1377 / 5
and add to row 8.
- multiply row 6 by -9 / 7
and add to row 9.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
298/5 |
0 |
1 |
0 |
391/2215 |
1071608/2372265 |
0 |
298/5355 |
0 |
0 |
0 |
3874/5 |
| s2 |
0 |
0 |
357/5 |
0 |
0 |
1 |
2499/2215 |
1901/6645 |
0 |
1/15 |
0 |
0 |
0 |
4641/5 |
| x1 |
1 |
0 |
1/5 |
0 |
0 |
0 |
-23/2215 |
-26/263585 |
0 |
-1/595 |
0 |
0 |
0 |
63/5 |
| x4 |
0 |
0 |
-1/5 |
1 |
0 |
0 |
8/2215 |
-19661/2372265 |
0 |
-1/5355 |
0 |
0 |
0 |
27/5 |
| s5 |
0 |
0 |
0 |
0 |
0 |
0 |
-305/443 |
90890/474453 |
1 |
-596/1071 |
0 |
0 |
0 |
0 |
| s6 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
0 |
-298/5 |
0 |
0 |
0 |
209/2215 |
7748/263585 |
0 |
298/595 |
1 |
0 |
0 |
-894/5 |
| s8 |
0 |
0 |
-1071/5 |
0 |
0 |
0 |
3213/2215 |
-451/2215 |
0 |
9/5 |
0 |
1 |
0 |
-3213/5 |
| |
0 |
0 |
7 |
0 |
0 |
0 |
-19/443 |
383/52717 |
0 |
1/119 |
0 |
0 |
1 |
36 |
Now we need to copy the heading for the work column (column 2) to the
heading for the work row (row 6).
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
298/5 |
0 |
1 |
0 |
391/2215 |
1071608/2372265 |
0 |
298/5355 |
0 |
0 |
0 |
3874/5 |
| s2 |
0 |
0 |
357/5 |
0 |
0 |
1 |
2499/2215 |
1901/6645 |
0 |
1/15 |
0 |
0 |
0 |
4641/5 |
| x1 |
1 |
0 |
1/5 |
0 |
0 |
0 |
-23/2215 |
-26/263585 |
0 |
-1/595 |
0 |
0 |
0 |
63/5 |
| x4 |
0 |
0 |
-1/5 |
1 |
0 |
0 |
8/2215 |
-19661/2372265 |
0 |
-1/5355 |
0 |
0 |
0 |
27/5 |
| s5 |
0 |
0 |
0 |
0 |
0 |
0 |
-305/443 |
90890/474453 |
1 |
-596/1071 |
0 |
0 |
0 |
0 |
| x2 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
0 |
-298/5 |
0 |
0 |
0 |
209/2215 |
7748/263585 |
0 |
298/595 |
1 |
0 |
0 |
-894/5 |
| s8 |
0 |
0 |
-1071/5 |
0 |
0 |
0 |
3213/2215 |
-451/2215 |
0 |
9/5 |
0 |
1 |
0 |
-3213/5 |
| |
0 |
0 |
7 |
0 |
0 |
0 |
-19/443 |
383/52717 |
0 |
1/119 |
0 |
0 |
1 |
36 |
Having finished the steps of the preprocessing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the preprocessing steps.
The lowest negative value in the last column is -3213 / 5 = -642.6 and
that is in row 8. Therefore, make row 8 the work row.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
298/5 |
0 |
1 |
0 |
391/2215 |
1071608/2372265 |
0 |
298/5355 |
0 |
0 |
0 |
3874/5 |
| s2 |
0 |
0 |
357/5 |
0 |
0 |
1 |
2499/2215 |
1901/6645 |
0 |
1/15 |
0 |
0 |
0 |
4641/5 |
| x1 |
1 |
0 |
1/5 |
0 |
0 |
0 |
-23/2215 |
-26/263585 |
0 |
-1/595 |
0 |
0 |
0 |
63/5 |
| x4 |
0 |
0 |
-1/5 |
1 |
0 |
0 |
8/2215 |
-19661/2372265 |
0 |
-1/5355 |
0 |
0 |
0 |
27/5 |
| s5 |
0 |
0 |
0 |
0 |
0 |
0 |
-305/443 |
90890/474453 |
1 |
-596/1071 |
0 |
0 |
0 |
0 |
| x2 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
0 |
-298/5 |
0 |
0 |
0 |
209/2215 |
7748/263585 |
0 |
298/595 |
1 |
0 |
0 |
-894/5 |
| s8 |
0 |
0 |
-1071/5 |
0 |
0 |
0 |
3213/2215 |
-451/2215 |
0 |
9/5 |
0 |
1 |
0 |
-3213/5 |
| |
0 |
0 |
7 |
0 |
0 |
0 |
-19/443 |
383/52717 |
0 |
1/119 |
0 |
0 |
1 |
36 |
The lowest negative value in row 8 is -1071 / 5 = -214.2 and
that is in column 3. Therefore, make column 3 the work column.
That makes the item in row 8 and column 3 the pivot item.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
298/5 |
0 |
1 |
0 |
391/2215 |
1071608/2372265 |
0 |
298/5355 |
0 |
0 |
0 |
3874/5 |
| s2 |
0 |
0 |
357/5 |
0 |
0 |
1 |
2499/2215 |
1901/6645 |
0 |
1/15 |
0 |
0 |
0 |
4641/5 |
| x1 |
1 |
0 |
1/5 |
0 |
0 |
0 |
-23/2215 |
-26/263585 |
0 |
-1/595 |
0 |
0 |
0 |
63/5 |
| x4 |
0 |
0 |
-1/5 |
1 |
0 |
0 |
8/2215 |
-19661/2372265 |
0 |
-1/5355 |
0 |
0 |
0 |
27/5 |
| s5 |
0 |
0 |
0 |
0 |
0 |
0 |
-305/443 |
90890/474453 |
1 |
-596/1071 |
0 |
0 |
0 |
0 |
| x2 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
0 |
-298/5 |
0 |
0 |
0 |
209/2215 |
7748/263585 |
0 |
298/595 |
1 |
0 |
0 |
-894/5 |
| s8 |
0 |
0 |
-1071/5 |
0 |
0 |
0 |
3213/2215 |
-451/2215 |
0 |
9/5 |
0 |
1 |
0 |
-3213/5 |
| |
0 |
0 |
7 |
0 |
0 |
0 |
-19/443 |
383/52717 |
0 |
1/119 |
0 |
0 |
1 |
36 |
Use the elementary row operation *row to change the
pivot item to be 1. That is, multiply row 8 by
-5 / 1071.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
298/5 |
0 |
1 |
0 |
391/2215 |
1071608/2372265 |
0 |
298/5355 |
0 |
0 |
0 |
3874/5 |
| s2 |
0 |
0 |
357/5 |
0 |
0 |
1 |
2499/2215 |
1901/6645 |
0 |
1/15 |
0 |
0 |
0 |
4641/5 |
| x1 |
1 |
0 |
1/5 |
0 |
0 |
0 |
-23/2215 |
-26/263585 |
0 |
-1/595 |
0 |
0 |
0 |
63/5 |
| x4 |
0 |
0 |
-1/5 |
1 |
0 |
0 |
8/2215 |
-19661/2372265 |
0 |
-1/5355 |
0 |
0 |
0 |
27/5 |
| s5 |
0 |
0 |
0 |
0 |
0 |
0 |
-305/443 |
90890/474453 |
1 |
-596/1071 |
0 |
0 |
0 |
0 |
| x2 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
0 |
-298/5 |
0 |
0 |
0 |
209/2215 |
7748/263585 |
0 |
298/595 |
1 |
0 |
0 |
-894/5 |
| s8 |
0 |
0 |
1 |
0 |
0 |
0 |
-3/443 |
451/474453 |
0 |
-1/119 |
0 |
-5/1071 |
0 |
3 |
| |
0 |
0 |
7 |
0 |
0 |
0 |
-19/443 |
383/52717 |
0 |
1/119 |
0 |
0 |
1 |
36 |
Now use the elementary row operation *row+ to change the
other items in column 3 to 0.
- multiply row 8 by -298 / 5
and add to row 1.
- multiply row 8 by -357 / 5
and add to row 2.
- multiply row 8 by -1 / 5
and add to row 3.
- multiply row 8 by 1 / 5
and add to row 4.
- multiply row 8 by 0 and add to row 5.
- multiply row 8 by 0 and add to row 6.
- multiply row 8 by 298 / 5
and add to row 7.
- multiply row 8 by -7 and add to row 9.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
0 |
0 |
1 |
0 |
257/443 |
11026/27909 |
0 |
596/1071 |
0 |
298/1071 |
0 |
596 |
| s2 |
0 |
0 |
0 |
0 |
0 |
1 |
714/443 |
290/1329 |
0 |
2/3 |
0 |
1/3 |
0 |
714 |
| x1 |
1 |
0 |
0 |
0 |
0 |
0 |
-4/443 |
-137/474453 |
0 |
0 |
0 |
1/1071 |
0 |
12 |
| x4 |
0 |
0 |
0 |
1 |
0 |
0 |
1/443 |
-226/27909 |
0 |
-2/1071 |
0 |
-1/1071 |
0 |
6 |
| s5 |
0 |
0 |
0 |
0 |
0 |
0 |
-305/443 |
90890/474453 |
1 |
-596/1071 |
0 |
0 |
0 |
0 |
| x2 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
0 |
0 |
0 |
0 |
0 |
-137/443 |
40826/474453 |
0 |
0 |
1 |
-298/1071 |
0 |
0 |
| s8 |
0 |
0 |
1 |
0 |
0 |
0 |
-3/443 |
451/474453 |
0 |
-1/119 |
0 |
-5/1071 |
0 |
3 |
| |
0 |
0 |
0 |
0 |
0 |
0 |
2/443 |
290/474453 |
0 |
8/119 |
0 |
5/153 |
1 |
15 |
Now we need to copy the heading for the work column (column 3) to the
heading for the work row (row 8).
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
0 |
0 |
1 |
0 |
257/443 |
11026/27909 |
0 |
596/1071 |
0 |
298/1071 |
0 |
596 |
| s2 |
0 |
0 |
0 |
0 |
0 |
1 |
714/443 |
290/1329 |
0 |
2/3 |
0 |
1/3 |
0 |
714 |
| x1 |
1 |
0 |
0 |
0 |
0 |
0 |
-4/443 |
-137/474453 |
0 |
0 |
0 |
1/1071 |
0 |
12 |
| x4 |
0 |
0 |
0 |
1 |
0 |
0 |
1/443 |
-226/27909 |
0 |
-2/1071 |
0 |
-1/1071 |
0 |
6 |
| s5 |
0 |
0 |
0 |
0 |
0 |
0 |
-305/443 |
90890/474453 |
1 |
-596/1071 |
0 |
0 |
0 |
0 |
| x2 |
0 |
1 |
0 |
0 |
0 |
0 |
-6/443 |
382/67779 |
0 |
-1/153 |
0 |
0 |
0 |
12 |
| s7 |
0 |
0 |
0 |
0 |
0 |
0 |
-137/443 |
40826/474453 |
0 |
0 |
1 |
-298/1071 |
0 |
0 |
| x3 |
0 |
0 |
1 |
0 |
0 |
0 |
-3/443 |
451/474453 |
0 |
-1/119 |
0 |
-5/1071 |
0 |
3 |
| |
0 |
0 |
0 |
0 |
0 |
0 |
2/443 |
290/474453 |
0 |
8/119 |
0 |
5/153 |
1 |
15 |
Having finished the steps of the preprocessing routine, we need
to see if there are any remaining negative values in the final
column. If so, then we restart the preprocessing steps.
There are no more negative values is the final column.
Therefore, preprocessing is done...
Regular Processing
Nothing to be done since there are no negative values in
the last row, excluding the final column.
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
- s1 = 596
- s2 = 714
- x1 = 12
- x4 = 6
- s5 = 0
- x2 = 12
- s7 = 0
- x3 = 3
the objective function has a
Minimum = -15
©Roger M. Palay Saline, MI 48176 October, 2010