SOLUTION: One gram of soybean meal provides at least 2.5 units of vitamins and 5 calories. One gram of meat byproducts provides at least 4.5 units of vitamins and 3 calories. One gram of gra

Let X = the mass of soybean meal consumed (in grams);

    Y = the mass of meat;

    Z = the mass of grain.


The objective function to minimize is the cost


    C(X,Y,Z) = 7*X + 9*Y + 11*Z  cents.      (1)


The constraints are


    2.5*X + 4.5*Y + 5*Z  >= 60  units of vitamins,    (2)

    
    5*X   + 3*Y   + 10*Z >= 66  calories.             (3)


Other constraints are  X >= 0;  Y>= 0,  and  Z >= 0.  (4)


Now, a remarkable fact is that the solution to this  3D  minimax problem can be obtained ANALYTICALLY.


Constraints (2) and (3) represent two planes in 3D:


    2.5*X + 4.5*Y + 5*Z   = 60                        (5)

    5*X   + 3*Y   + 10*Z  = 66                        (6)


These planes are not parallel -- hence, their intersection is a straight line.

The idea is to present this straight line in a parametric form - then the solution of the minimax problem
on this straight line will be easy.


Multiply equation (5) by 2 (both sides) and then subtract equation (6) from the obtained equation.
You will get


    3Y - 9Y = 66 - 2*60,   or     -6Y = -54.  

Hence,  

    Y = 9.                                            (7)


Thus we found that the intersection of two planes (5) and (6) is a straight line, which lies on the plane Y = 9.

Subctitute Y =9 into equations (5) and (6). You will get then


    2.5*X + 4.5*9 + 5Z  = 60            (5')

    5*X   + 3*9   + 10Z = 66,           (6')


or, collecting all constant terms on the right side


    2.5*X + 5Z   = 19.5,                (5'')

    5*X   + 10*Z = 39,                  (6'')


Equations (5'') and (6'') are DEPENDENT (which is OBVIOUS).

Hence, two equations (5'') and (6'') represent THE SAME plane.


So, our straight line is the intersection of planes (7) and (6'').


Now, from equation (6''),

     X = 7.8 - 2Z.


Thus our stright line in parametric form is


    X = 7.8 - 2Z,  Y = 9.               (8)


Substitute (8) into the objective function (1). You will get

    C(X,Y,Z) = 7*X + 9*Y + 11*Z = 7*(7.8 - 2Z) + 9*9 + 11*Z = 54.6 - 14Z + 81 + 11Z = -3Z + 135.6.    (9)


Thus, on our line the objective function is presented as the linear function (9) of Z.

We see that when Z increases from 0 to positive values, the function  (9) decreases.
But Z can increase only till  X = 7.8 - 2Z  is >= 0    (is non-negative).
Hence, the linear function (9) has the minimum at Z = 7.8/2 = 3.9.

Then X = 7.8 - 2*3.9 = 0, according to (8).


Thus we just obtained the solution to our minimax problem:

    The minimum solution point is X= 0;  Y= 9  and  Z= 3.9 

    and the mimimum cost is  -3*Z + 135.6 = -3*3.9 + 135.6 = 123.9.


ANSWER.  The minimum cost is 123.90 cents (or, after rounding, $1.24) and it is achieved at this diet:

         0 gram of soybean meal;  9 gram of meat,  and 3.9 gram of grain.

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:

subject to the constraints:

We use the simplex method.
We form the initial matrix

Since this is a minimizing problem, we form the dual
maximizing problem.  We form the transpose of the
above matrix:

The dual maximizing problem:
Maximize:

subject to the constraints:



We form the initial tableau:



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.




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.



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
x1 = 0, the number at the bottom of the s1 column. x2 = 9, 
the number at the bottom of the s2 column.  x3 = 3.9
the number at the bottom of the s3 column.

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

Edwin