|
|
|
|
PERFECTED SIMPLEX - by Tyasno Nurhadi
I am teaching the simplex method to my students in STMB (Sekolah Tinggi Manajemen Bandung - Indonesia) in this second semester. Together with my 100 students, I work with the simplex method both in cases of maximizing revenue or profit and also cases of finding the minimum of cost. I recognize that the simplex method is, especially, useful in cases with more than two products/activity variables. Even so, we found out that the simplex method has a serious weakness when we were facing cases with multiple optimum solutions.
Consider the following case that I made-up and presented on April 8, 1998.
A printing company received inquiries from three magazine publishers to print their magazines "X", "Y" and "Z". The raw materials needed for each magazines are shown in the following table.
Paper (sheets) |
Ink (ml) |
Print-time (minute) |
|
| Magazine "X" | 50 |
20 |
4 |
| Magazine "Y" | 100 |
30 |
6 |
| Magazine "Z" | 125 |
40 |
8 |
From its calculation the printing company knows that every "X" yields 1000 rupiah, while each "Y" and "Z" yields 1500 and 2000 rupiah respectively. Even though this printing company would not like to disappoint its customers, they have to maximize their profit with 7000 sheets of paper and 2500 ml of ink left. With eight hours of printing machine in operation, let’s find the maximum profit and the best decision for this company.
Well, do not bother with 125 pages of magazine "Z". It is just a simple case to see the accuracy of the simplex method in finding the optimum solution. Suppose that x represents the number of magazine "X" produced by the company, y for the number of magazine "Y" and, similarly, z for the number of "Z". The objective funcion here is to find the maximum profit p :
p = 1000x + 1500y + 2000z (profit equation)
The inequalities representing the requirement and the availability of raw materials are:
50x + 100y + 125z £ 7000 (paper)
20x + 30y + 40z £ 2500 (ink)
4x + 6y + 8z £ 480 (print-time).
I believe that you see the multiple optimum solution for my case, because we have three parallel planes namely :
As you know we can reconstruct all functions to suit the simplex method :
p - 1000x - 1500y - 2000z = 0 (new profit equation)
50x + 100y +125z + s1 = 7000 (s1 is the slack for paper)20x + 30y + 40z + s2 = 2500 (s2 is the slack for ink)
4x + 6x + 8z + s3 = 480 (s3 is the slack for print-time)
The first tableau :
| x | y | z | s1 | s2 | s3 | RHS | |
| p | -1000 |
-1500 |
-2000 |
0 |
0 |
0 |
0 |
| s1 | 50 |
100 |
125 |
1 |
0 |
0 |
7000 |
| s2 | 20 |
30 |
40 |
0 |
1 |
0 |
2500 |
| s3 | 4 |
6 |
8 |
0 |
0 |
1 |
480 |
With the simplex method we choose z column as the pivot column because it has the most negative value (which is expected to contribute the highest profit). As you will see, this pivot column will not give us the most optimum solution for my case. Instead of selecting the pivot element only from this pivot colum, I was calculating all quotients for x column, y column and z column, in order to get the accurate pivot element.
x column |
p |
y column |
p |
z column |
p |
|
| quotient for s1 row | 140 |
70 |
105000 |
56 |
112000 |
|
| quotient for s2 row | 125 |
83.33333 |
62.5 |
|||
| quotient for s3 row | 120 |
120000 |
80 |
60 |
Now you see that selecting z column (means
producing "Z") will give us 112,000 rupiah, while
selecting x column (means producing "X") will be
resulting a profit of 120,000 rupiah.
The second tableau for simplex and
perfected simplex are shown below.
The second tableau for simplex :
| x | y | z | s1 | s2 | s3 | RHS | |
| p | -200 |
100 |
0 |
16 |
0 |
0 |
112000 |
| z | 0.4 |
0.8 |
1 |
0.008 |
0 |
0 |
56 |
| s2 | 4 |
-2 |
0 |
-0.32 |
1 |
0 |
260 |
| s3 | 0.8 |
-0.4 |
0 |
-0.064 |
0 |
1 |
32 |
The second tableau for perfected simplex :
| x | y | z | s1 | s2 | s3 | RHS | |
| p | 0 |
0 |
0 |
0 |
0 |
250 |
120000 |
| s1 | 0 |
25 |
25 |
1 |
0 |
-12.5 |
1000 |
| s2 | 0 |
0 |
0 |
0 |
1 |
-5 |
100 |
| x | 1 |
1.5 |
2 |
0 |
0 |
0.25 |
120 |
At this point we can see that the perfected-simplex method has found out the optimum solution for my case only with two tableaus ! The profit for the company if they produce 120 of "X" will be 120,000 rupiah. 1,000 sheets of paper and 100 ml of ink will still be left.
Let’s continue with the simplex method.
x column |
|
| quotient for z row | 140 |
| quotient for s2 row | 65 |
| quotient for s3 row | 40 |
The third tableau for simplex :
| x | y | z | s1 | s2 | s3 | RHS | |
| p | 0 |
0 |
0 |
0 |
0 |
250 |
120000 |
| z | 0 |
1 |
1 |
0.04 |
0 |
-0.5 |
40 |
| s2 | 0 |
0 |
0 |
0 |
1 |
-5 |
100 |
| x | 1 |
-0.5 |
0 |
-0.08 |
0 |
1.25 |
40 |
We see that producing 40 "X" and 40 "Z" give a same profit (120,000 rupiah), but we use up papers. @
Copyright © 2000 - tyasno nurhadi
All Rights Reserved
Webmaster : tyasno nurhadi
