# Refer to Example 9 in book ( page 521 - copied below ). (Diet problem) A dietician has to develop a special diet using two foods P and Q. Each packet (containing 30 g) of food P contains 12 units of calcium, 4 units of iron, 6 units of cholesterol and 6 units of vitamin A. Each packet of the same quantity of food Q contains 3 units of calcium, 20 units of iron, 4 units of cholesterol and 3 units of vitamin A. The diet requires atleast 240 units of calcium, atleast 460 units of iron and at most 300 units of cholesterol. How many packets of each food should be used to minimise the amount of vitamin A in the diet? What is the minimum amount of vitamin A?How many packets of each food should be used to maximise the amount of vitamin A in the diet? What is the maximum amount of vitamin A in the diet?

Toolbox:
• First formulate the objective function and identify the constraints from the problem statement, To solve a Linear Programming problem graphically, first plot the constraints for the problem. This is done by plotting the boundary lines of the constraints and identifying the points that will satisfy all the constraints.
• One we graphically plot the area bounded by the constraints, it’s easy to see which points satisfy all constraints. This common region determined by all the constraints including non-negative constraints of a linear programming problem is called the $\textbf{Feasible Region (or solution region).}$
• Now, any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an $\textbf{Optimal Solution.}$ We see that every point in the feasible region satisfies all the constraints, and there are infinitely many points.
• Since we know from theory that the optimal value must occur at a corner point (vertex) of the feasible region, calculate the objective function values associated with the coordinates of all the extreme points. This method is called the $\textbf{Corner Point Method.}$
• If the feasible region is bounded (if it can be enclosed), the point with the best objective function value is the best optimal solution. If the feasible region is unbounded (means that the feasible region does extend indefinitely in any direction), the then a maximum or a minimum value of the objective function may not exist. However, if it exists, it must occur at a corner point of the feasible region, which can be calculated.
This is a typical diet problem. Let the mixture contain x kg of Food ‘P’ and y kg of Food ‘Q’. Clearly, x, y ≥ 0. Let us construct the following table from the given data:
$\begin{array}{llllll} \textbf{Foods} & \textbf{Packets} & \textbf{Calcium} &\textbf{Iron} &\textbf{Cholesterol} &\textbf{Vitamin A} \\ P & x & 12x & 4x & 6x & 6x \\ Q & y & 3y & 20y & 4y & 3y\\ \text{Total} & x+y & 12+3y & 4x+20y & 6x+4y & 6x+3y\\ \textbf{Requirements}& & \text{Atleast 240}& \text{Atleast 460} & \text{Atmost 300} & \end{array}$
We need to maximize Z = 6x+3y given the following constraints:
$(1):\qquad$ 12x+3y $\geq$ 240 $\to$ 4x+y $\geq$ 80
$(2):\qquad$ 4x+20y $\geq$ 460 $\to$ x+5y $\geq$ 115
$(3):\qquad$ 6x+4y $\leq$ 300 $\to$ 3x+2y $\leq$ 150
$(4):\qquad$ x $\geq$ 0 and $(5):\qquad$ y $\geq$ 0.
$\textbf{Plotting the constraints}$
First draw the graph of the line 4x+y = 80.
If x = 0 $\to$ y = 80, and if y = 0 $\to$ 4x = 80 $\to$ x = 20.
At (0,0), in the inequality, we have 0 + 0 = 0 which is not ≥ 80. So the area associated with this inequality is unbounded and away from the origin
Next, draw the line x+5y = 115.
If x = 0 $\to$ 5y = 115 $\to$ y = 23, and if y = 0 $\to$ x = 115.
At (0,0), in the inequality, we have 0 + 0 = 0 which is not ≥ 115. So the area associated with this inequality is unbounded and away from the origin
Next, plot the line 3x+2y = 150.
If x = 0 $\to$ 2y = 150 $\to$ y = 75, and if y = 0, 3x = 150 $\to$ x = 50.
At (0,0), in the inequality, we have 0 + 0 = 0 which is $\leq$ 150. So the area associated with this inequality is bounded and towards the origin
$\textbf{Finding the feasible region}$
Since x and y are $\geq$ 0, the feasible region is in the first quadrant.
On solving equations 4x+y = 80 and x+5y = 115, we get:
Substituting for x = 115-5y $\to$ 4 $\times$ (115-5y) + y = 80 $\to$ 460 - 20y + y = 80 $\to$ 19y = 380 $\to$ y = 20.
Therefore, x = 115 - 5 $\times$ 20 = 115 - 100 = 15.
$\to$ Point G (15, 20)
On solving equations 3x+2y = 150 and x + 5y = 115, we get:
Substituting for x = 115 - 5y $\to$ 3 \times (115-5y) + 2y = 150 $\to$ 345 - 15y + 2y = 150 $\to$ 13y = 195 $\to$ y = 15.
Therefore, x = 115 - 5 $\times$ 15 = 115 - 75 = 40.
$\to$ Point H (40, 15).
On solving equations 3x+2y = 150 and 4x+y = 80, we get:
Substituting for y = 80-4x $\to$ 3x + 2 $\times$ (80-4x) = 150 $\to$ 3x + 160 - 8x = 150 $\to$ 5x = 10 $\to$ x = 2.
Therefore, y = 80 - 4 $\times$ 2 = 80 - 8 = 72.
$\to$ Point I (2, 72).
Therefore the feasible region is the area bounded by GIHG,
$\textbf{Solving the objective function using the corner point method}$
The values of Z at the corner points are calculated as follows:
$\begin{array}{ll} \textbf{Corner Point} & \textbf{ Z = 6x+3y} \\ (15,20) & 150 \\ (40,15) & 285 \; \textbf{(Max Value)} \\ (2,72) & 228 \end{array}$
$\textbf{A) The maximum value of Z is 285 at (40,15).}$
$\textbf{B) To maximize the amount of Vitamin A, 40 packets of P and 15 packets of Q should be used.}$