$\begin{array}{1 1} 100 \\ 200 \\ 104 \\ 320/3 \end{array} $

- 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

Let x be the units of food F1 and y be the unit of food F2. Clearly, x, y ≥ 0. Let us construct the following table from the given data

Clearly, x, y ≥ 0. Let us construct the following table from the given data

F1(x) | F2(x) | Requirements | |

Vitamin A/unit | 3 | 6 | At least 80 units |

Minerals/unit | 4 | 3 | At least 100 units |

Cost Rs. | 4 | 6 |

We have the following constraints: 3x + 6y $\geq$ 80 and 4x + 3y$\geq$ 100

We need to minimize the cost of diet given that F1 costs 4Rs and F2 6Rs, i.e, Z = 4x+6y.

$\textbf{Plotting the constraints}$:

Plot the straight lines 3x + 6y =80 and 4x + 3y =100

First draw the graph of the line 3x+6y = 80.

If x = 0, y = 80/3 and if y = 0, x = 80/6 = 40/3. So, this is a straight line between (0,80/3) and (40/3,0).

At (0,0), in the inequality, we have 0 + 0 = 0 which is not ≥ 0. So the area associated with this inequality is unbounded and away from the origin.

Similarly, draw the graph of the line 4x+3y = 100.

If x = 0, y = 100/3 and if y =0, x = 100/4 = 25. So, this is a straight line between (0,100/3) and (25,0).

At (0,0), in the inequality, we have 0 + 0 = 0 which is not ≥ 0. So the area associated with this inequality is unbounded and away from the origin.

$\textbf{Finding the feasible region}$:

We can see that the feasible region is bounded and in the first quadrant.

On solving the equations 3x + 6y =80 and 4x + 3y =100, we get,

3x + 2 (100-4x) = 80 $\to$3x + 200 – 8x = 80 $\to$-5x = -120 $\to$x = 24.

If x = 24, y = (80 – 3x24)/6 = 8/6 = 4/3.

$\Rightarrow x = 24, y = 4/3 $

Therefore the feasible region has the corner points (0,100/3), (24,4/3), (80/3, 0) as shown in the figure.

$\textbf{Solving the objective function using the corner point method}$

The values of Z at the corner points are calculated as follows:

Corner Point | Z = 4x+6y |

(0, 100/3) | 200 |

(24, 4/3) | 104 (Min Value) |

(80/3, 0) | 320/3 |

However, we still don’t know if 104 is indeed the minimum value for Z. We have to check through the inequality Z $\leq$ 104, i.e, 4x + 6y $\leq$ 104.

If we graph this, we can see that there is no common point w/ the feasible region.

Therefore the minimum cost has to be 104.

$\textbf{The minimum feasible value for the mixture is Rs. 104.}$

Ask Question

Tag:MathPhyChemBioOther

Take Test

...