Question 1153399
<pre>
Let x = number of grams of soybean meal
Let y = number of grams of meat byproducts
Let z = number of grams of grain
We are to minimize:
{{{C=7x+9y+11z}}}
subject to the constraints:
{{{system(
2.5x+4.5y+5z>=60,
5x+3y+10z>=66,
"x,y,z">=0)}}}
We use the simplex method.
We form the initial matrix
{{{(matrix(4,5,
2.5,4.5, 5,"|",60,
  5,  3,10,"|",66,
"--","--","--","--","--",
  7,  9, 11,"|","*"))}}}
Since this is a minimizing problem, we form the dual
maximizing problem.  We form the transpose of the
above matrix:
{{{(matrix(5,4,
2.5,5,"|",7,
4.5,3,"|",9,
5,10, "|",11,
"--","--","--","--",
60,66,"|","*"))}}}
The dual maximizing problem:
Maximize:
{{{P=60u+66v}}}
subject to the constraints:
{{{system(2.5u+5v<=7,
4.5u+3v<=9,
5u+10v<=11,
"u,v">=0)}}}
{{{matrix(4,13,
2.5u,""+"",5v,""+"",s[1],   "",  "",    "",  "",   "", "", ""="", 7,
4.5u,""+"",3v,   "",  "",""+"",s[2],    "",  "",   "", "", ""="", 9,
  5u,""+"",10v,  "",  "",   "",  "", ""+"",s[3],   "", "", ""="",11,
-60u,""-"",66v,  "",  "",   "",  "",    "",  "",""+"",  P, ""="",0)}}}

We form the initial tableau:

{{{matrix(6,9,

  u,v,s[1],s[2],s[3],"|",0,"|","*",
2.5,5,  1 ,  0 ,  0 ,"|",0,"|",7,
4.5,3,  0 ,  1,   0 ,"|",0,"|",9,
  5,10, 0,   0,   1, "|",0,"|",11,
"--","--","--","--","--","--","--","--","--",
-60,-66,0,0,0,"|",1,"|",0 )}}}

The most negative number on the bottom row is -66.
It is in column 2, so we call column 2 "the pivot column".
We divide each positive number above the pivot element INTO the number
at the right to see which gives the smallest positive answer.

  1.4         3           1.1
5)7.0       3)9       10)11.0

We get the smallest value when we divide 10 into the number at the far
right, so 10 is the pivot element.

Now we make the pivot element become 1, by dividing the pivot row
through by 10.  Then we make 0's elsewhere in the pivot column, using
the pivot row. Making an element of a column become 1 and all the other
elements in the column become 0 is called "pivoting" on the element
that we caused to become 1.

{{{matrix(6,9,

  u,v,s[1],s[2],s[3],"|",0,"|","*",
  0,0,  1 ,  0 , -0.5 ,"|",0,"|",1.5,
  3,0,  0 ,  1,  -0.3 ,"|",0,"|",5.7,
0.5,1, 0,   0,   0.1, "|",0,"|",1.1,
"--","--","--","--","--","--","--","--","--",
-27,0,0,0,6.6,"|",1,"|",72.6 )}}}


Now the only negative number on the bottom row is -27. It is in 
column 1, so now column 1 is the pivot column. We divide each 
positive number above the pivot element INTO the number
at the right to see which gives the smallest positive answer.

  1.9           2.2
3)5.7       0.5)1.1

We get the smallest value when we divide 3 into the number at the far
right, so 3 is the pivot element.

Now we make the pivot element become 1, by dividing the pivot row
through by 3.  Then we use it to make 0's elsewhere in the pivot column,
using the pivot row.

{{{matrix(6,9,

  u,v,s[1],s[2],s[3],"|",0,"|","*",
  0,0,  1 ,  0 , -0.5 ,"|",0,"|",1.5,
  1,0,  0 ,  1/3,  -0.1 ,"|",0,"|",5.7,
  0,1,  0,  -1/6,   0.15, "|",0,"|",1.1,
"--","--","--","--","--","--","--","--","--",
  0,0,0,9, 3.9,"|",1,"|",123.9 )}}}

There are no more negative numbers on the bottom row, so
we have reached the final tableau:
 
So the minimum cost is 123.9, or $123.90 and this occurs when
x<sub>1</sub> = 0, the number at the bottom of the s<sub>1</sub> column. x<sub>2</sub> = 9, 
the number at the bottom of the s<sub>2</sub> column.  x<sub>3</sub> = 3.9
the number at the bottom of the s<sub>3</sub> column.

Note this is the same answer that Ikleyn got using a different technique.

Edwin</pre>