Example: Minimise
\[O_1=9x_1+12x_2+15x_3\]
subject to the constraints\[2x_1+2x_2+x_3 \geq 10\]
\[2x_1+3x_2+x_3 \geq 12\]
\[x_1+x_2+5x_3 \geq 14\]
\[x_1, \: x_2, \: x_3 \geq 0\]
The dual; to this problem is: Maximise
\[O_2=10y_1+12y_2+14y_3\]
subject to the constraints\[2y_1+2y_2+y_3 \leq 9\]
\[2y_1+3y_2+y_3 \leq 12\]
\[y_1+y_2+5y_3 \leq 15\]
\[y_1, \: y_2, \: y_3 \geq 0\]
We change these inequalities into equalities by adding slack variables
\[y_4, \: y_5, \: y_6 \geq 0\]
The system becomes: Maximise
\[O_2=10y_1+12y_2+14y_3\]
subject to the constraints\[2y_1+2y_2+y_3+y_4 = 9\]
\[2y_1+3y_2+y_3+y_5= 12\]
\[y_1+y_2+5y_3+y_6 15\]
\[y_1, \: y_2, \: y_3, y_4 \: y_5, \: y_6 \geq 0\]
The initial tableau is
\[y_1\] |
\[y_2\] |
\[y_3\] |
\[y_4\] |
\[y_5\] |
\[y_6\] |
||
\[y_4\] |
2 | 2 | 1 | 1 | 0 | 0 | 9 |
\[y_5\] |
2 | 3 | 1 | 0 | 1 | 0 | 12 |
\[y_6\] |
1 | 1 | 5 | 0 | 0 | 1 | 15 |
| ) \[O_2\] |
-10 | -12 | 15 | 0 | 0 | 0 | 0 |
\[O_2\]
the lowest extreme right cell is zero and we can increase it by adding multiples of the other rows. To choose which row, choose the column with the most negative entry in the objective \[O_2\]
row. It is the fourth column. Find the minimum value of the row entries for that column divided by the corresponding entries in the last column.\[MIN(9/1,12/1,15/3)=15/3=5\]
At this point we are said to pivot on the fourth row. Divide the fourth row by 5 and subtract/add multiples of this row to the other rows so that every entry in that column is zero. We have pivoted on the fourth row in the table, so the leading column entry replaces the leading row entry. The result is
\[y_1\] |
\[y_2\] |
\[y_3\] |
\[y_4\] |
\[y_5\] |
\[y_6\] |
||
\[y_4\] |
9/5 | 9/5 | 0 | 1 | 0 | -1/5 | 6 |
\[y_5\] |
9/5 | 14/5 | 0 | 0 | 1 | -1/5 | 9 |
\[y_3\] |
1/5 | 1/5 | 1 | 0 | 0 | 1/5 | 3 |
| ) \[O_2\] |
-36/5 | -46/5 | 0 | 0 | 0 | 14/5 | 42 |
\[MIN(6/(9/5),9/(14/5),3/(1/5))=9/(14/5)\]
We divide this row by 14/5 and pivot on the third row, adding/subtracting multiples of this row to other rows so that all other entries in this column become zero. We have pivoted on the third row, so the ladybug column entry becomes the leading row entry.
\[y_1\] |
\[y_2\] |
\[y_3\] |
\[y_4\] |
\[y_5\] |
\[y_6\] |
||
\[y_4\] |
9/14 | 0 | 0 | 1 | -9/14 | -1/14 | 3/14 |
\[y_2\] |
9/14 | 1 | 0 | 0 | 5/14 | -1/14<*/td> | 45/14 |
\[y_3\] |
1/14 | 0 | 1 | 0 | -1/14 | 3/14 | 33/14 |
| ) \[O_2\] |
-9/7 | 0 | 0 | 0 | 23/7 | 15/7 | 501/7 |
\[MIN((3/14)/(9/14),(45/14)/(9/14),(33/14)/(1/14))=(3/14)/(9/14)\]
We divide the second row by 9/14 and pivot on the second row, adding/subtracting multiples of this row to other rows so that all other entries in this column become zero. We have pivoted on the second row, second column so the leading column entry becomes the leading row entry.
\[y_1\] |
\[y_2\] |
\[y_3\] |
\[y_4\] |
\[y_5\] |
\[y_6\] |
||
\[y_1\] |
1 | 0 | 0 | 14/9 | -1 | -1/9 | 1/3 |
\[y_2\] |
0 | 1 | 0 | -1 | 1 | 0 | 3 |
\[y_3\] |
0 | 0 | 1 | -1 | 0 | 2/9 | 7/3 |
| ) \[O_2\] |
0 | 0 | 0 | 2 | 2 | 2 | 72 |
\[y_1, \: y_2, \: y_3 \geq 0\]
, and is optimal solution since all the entries in the objective row are non negative. Then \[y_1=1/3, \: y_2=3, \: y_3=7/3, \: O_2=72\]
.From the Fundamental Theory of Linear Programming, linear programming solution and dual have the same optimal objective value. From the 'Complementary Slackness Theorem', the corresponding values of
\[x_1, \: x_2, \: x_3\]
are the final values of \[y_4, \: y_5, \: y_6\]
in the final tableau of the dual row, read of from the objective rowWe have
\[x_1=2, \: x_2=2, \: x_3=2\]
.