Linear Programming Problem -- a walk through
Reading the data file: lp_demo_17.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: maximize -7 3 5 3 ---> set Maximize:
-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...
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 -8 / 119 = -0.0672268907563025 and
that is in column 10. So make column 10 the work column.
| |
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 |
The lowest ratio between positive values in column 10 and corresponding values in the the final column is 1071 and
that is in row 1. So make row 1 the work row.
That makes the item in row 1 and column 10 the pivot item.
| |
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 |
Use the elementary row operation *row to change the
pivot item to be 1. That is, multiply row 1 by
1071 / 596.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
0 |
0 |
1071/596 |
0 |
275247/264028 |
629/886 |
0 |
1 |
0 |
1/2 |
0 |
1071 |
| 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 |
Now use the elementary row operation *row+ to change the
other items in column 10 to 0.
- multiply row 1 by -2 / 3
and add to row 2.
- multiply row 1 by 0 and add to row 3.
- multiply row 1 by 2 / 1071
and add to row 4.
- multiply row 1 by 596 / 1071
and add to row 5.
- multiply row 1 by 1 / 153
and add to row 6.
- multiply row 1 by 0 and add to row 7.
- multiply row 1 by 1 / 119
and add to row 8.
- multiply row 1 by 8 / 119
and add to row 9.
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s1 |
0 |
0 |
0 |
0 |
1071/596 |
0 |
275247/264028 |
629/886 |
0 |
1 |
0 |
1/2 |
0 |
1071 |
| s2 |
0 |
0 |
0 |
0 |
-357/298 |
1 |
121023/132014 |
-113/443 |
0 |
0 |
0 |
0 |
0 |
0 |
| x1 |
1 |
0 |
0 |
0 |
0 |
0 |
-4/443 |
-137/474453 |
0 |
0 |
0 |
1/1071 |
0 |
12 |
| x4 |
0 |
0 |
0 |
1 |
1/298 |
0 |
555/132014 |
-3/443 |
0 |
0 |
0 |
0 |
0 |
8 |
| s5 |
0 |
0 |
0 |
0 |
1 |
0 |
-48/443 |
278332/474453 |
1 |
0 |
0 |
298/1071 |
0 |
596 |
| x2 |
0 |
1 |
0 |
0 |
7/596 |
0 |
-1777/264028 |
1393/135558 |
0 |
0 |
0 |
1/306 |
0 |
19 |
| s7 |
0 |
0 |
0 |
0 |
0 |
0 |
-137/443 |
40826/474453 |
0 |
0 |
1 |
-298/1071 |
0 |
0 |
| x3 |
0 |
0 |
1 |
0 |
9/596 |
0 |
525/264028 |
6563/948906 |
0 |
0 |
0 |
-1/2142 |
0 |
12 |
| |
0 |
0 |
0 |
0 |
18/149 |
0 |
4328/66007 |
22354/474453 |
0 |
0 |
0 |
1/1071 |
1 |
57 |
Now we need to copy the heading for the work column (column 10) to the
heading for the work row (row 1).
| |
x1 |
x2 |
x3 |
x4 |
s1 |
s2 |
s3 |
s4 |
s5 |
s6 |
s7 |
s8 |
z |
|
| s6 |
0 |
0 |
0 |
0 |
1071/596 |
0 |
275247/264028 |
629/886 |
0 |
1 |
0 |
1/2 |
0 |
1071 |
| s2 |
0 |
0 |
0 |
0 |
-357/298 |
1 |
121023/132014 |
-113/443 |
0 |
0 |
0 |
0 |
0 |
0 |
| x1 |
1 |
0 |
0 |
0 |
0 |
0 |
-4/443 |
-137/474453 |
0 |
0 |
0 |
1/1071 |
0 |
12 |
| x4 |
0 |
0 |
0 |
1 |
1/298 |
0 |
555/132014 |
-3/443 |
0 |
0 |
0 |
0 |
0 |
8 |
| s5 |
0 |
0 |
0 |
0 |
1 |
0 |
-48/443 |
278332/474453 |
1 |
0 |
0 |
298/1071 |
0 |
596 |
| x2 |
0 |
1 |
0 |
0 |
7/596 |
0 |
-1777/264028 |
1393/135558 |
0 |
0 |
0 |
1/306 |
0 |
19 |
| s7 |
0 |
0 |
0 |
0 |
0 |
0 |
-137/443 |
40826/474453 |
0 |
0 |
1 |
-298/1071 |
0 |
0 |
| x3 |
0 |
0 |
1 |
0 |
9/596 |
0 |
525/264028 |
6563/948906 |
0 |
0 |
0 |
-1/2142 |
0 |
12 |
| |
0 |
0 |
0 |
0 |
18/149 |
0 |
4328/66007 |
22354/474453 |
0 |
0 |
0 |
1/1071 |
1 |
57 |
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
- s6 = 1071
- s2 = 0
- x1 = 12
- x4 = 8
- s5 = 596
- x2 = 19
- s7 = 0
- x3 = 12
the objective function has a
Maximum = 57
©Roger M. Palay Saline, MI 48176 October, 2010