John Hughes's baker problem

Quantities of ingredients (A, B, & C) available:-
A 685; B 720; C 860

Product composition (products X, Y & Z):-
     X = 2 A + 2 B + C
     Y = A + 3 C
     Z = A + 2 B + C

Profit per unit of product:-
     X_p = 5.20
     Y_p = 5.40
     Z_p = 4.30

Question: How much of each product should the baker make in order to maximise his profit?

The amount of raw material A used is:
           A = 2 X + Y + Z
The amount of raw material B used is:
           B = 2 X + 2 Z
The amount of raw material C used is:
           C = X + 3 Y + Z

Let the vector of ingredients be called S (S for stuff — I is traditionally used for the unit matrix)
and let the vector of products be called P

         S    =    (


A
B
C
)
         P    =    (


X
Y
Z
)

and the recipe is the 3 × 3 matrix:

         R    =    (


2 1 1
2 0 2
1 3 1
)

and the profit vector is:

         G    =    (


X_p
Y_p
Z_p
)
       =    (


5.2
5.4
4.3
)

      S = R P
      g = G^T P
           where g is the total gain (i.e. profit).

      P = R^-1 S
      g = G^T R^-1 S = Z^T S
           where Z = R^-1 ^T G
      Z^T = G^T R^-1
      Z^T R = G^T
      R^T Z = G

              (


2 2 1
1 0 3
1 2 1
)
   (


Z_a
Z_b
Z_c
)
   =    G    =    (


X_p
Y_p
Z_p
)

Take the bottom row from the top:

              (


1 0 0
1 0 3
1 2 1
)
   (


Z_a
Z_b
Z_c
)
   =    (


X_p - Z_p
Y_p
Z_p
)

Take the top row from the middle row:

              (


1 0 0
0 0 3
1 2 1
)
   (


Z_a
Z_b
Z_c
)
   =    (


X_p - Z_p
Y_p - X_p + Z_p
Z_p
)

Take the top row from the bottom row:

              (


1 0 0
0 0 3
0 2 1
)
   (


Z_a
Z_b
Z_c
)
   =    (


X_p - Z_p
Y_p - X_p + Z_p
2 Z_p - X_p
)

Multiply the bottom row by 3 and then subtract the middle row

              (


1 0 0
0 0 3
0 6 0
)
   (


Z_a
Z_b
Z_c
)
   =    (


X_p - Z_p
Y_p - X_p + Z_p
5 Z_p - 2 X_p - Y_p
)

Put in the numbers

              (


1 0 0
0 0 3
0 6 0
)
   (


Z_a
Z_b
Z_c
)
   =    (


5.2 - 4.3
5.4 - 5.2 + 4.3
5×4.3 - 2×5.2 - 5.4
)
   =    (


0.9
4.5
5.7
)

Multiply out the matrices:
      2 Z_a = 0.9
      3 Z_c = 4.5
      6 Z_b = 5.7

      Z^T = ( 0.45 0.95 1.5 )

Planes of constant profit in the A, B, C space g are given by:
g = 0.45 A + 0.95 B + 1.5 C

The maximum will be in one of the 8 corners, but as all elements of Z are positive, the maximum will be at:
( 685, 720, 860 )
... subject to the proviso that the amount of each of the products must be not negative.

      P = R^-1 S
           . . . but as inverses are hard to calculate, it is easier to solve the siultaneous linear equations for P :
      R P = S

              (


2 1 1
2 0 2
1 3 1
)
   (


X
Y
Z
)
   =    (


A
B
C
)

Double the bottom row and subtract the middle row from it:

              (


2 1 1
2 0 2
0 6 0
)
   (


X
Y
Z
)
   =    (


A
B
2 C - B
)

Top row times 6 and minus the bottom row, also middle times 6:

              (


12 0 6
12 0 12
0 6 0
)
   (


X
Y
Z
)
   =    (


6 A + B - 2 C
6 B
2 C - B
)

Top row from middle:

              (


12 0 6
0 0 6
0 6 0
)
   (


X
Y
Z
)
   =    (


6 A + B - 2 C
5 B - 6 A + 2 C
2 C - B
)

And now middle from top and divide the top row by 2:

              (


6 0 0
0 0 6
0 6 0
)
   (


X
Y
Z
)
   =    (


6 A - 2 B - 2 C
5 B - 6 A + 2 C
2 C - B
)
   ≥    (


0
0
0
)

For the values ( 685, 720, 860 ) the above vector becomes ( 950, 1000, 1210 ), i.e. all positive, which gives the rather boring result that the baker should use all of each raw material.

The problem is more interesting if the amount of B available exceeds 1194, then none of the 8 corners gives positive amounts of all products. In fact there is no mix that uses all the raw material, and some of B will have to be left unused.

Amounts 685, 1196 and 861 give a rather more interesting problem.