Diet is to contain at least 80 units of vitamin a and 100 units of minerals. Two foods f1 and f2 are available. Food f1 costs rs 4 per unit food and food f2 costs rs 6 per unit. One unit of food f1 contains 3 units of vitamin a and 4 units of minerals. One unit of food f2 contains 6 units of vitamin a and 3 units of minerals. Formulate this as a linear programming problem. Find the minimum cost for diet that consists of mixture of these two foods and also meets the minimal nutritional requirements.
Answers
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 Feasible Region (or solution region).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 Optimal SolutionOptimal 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 Corner Point MethodCorner 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 ≥≥ 80 and 4x + 3y≥≥ 100
We need to minimize the cost of diet given that F1 costs 4Rs and F2 6Rs, i.e, Z = 4x+6y.
Plotting the constraintsPlotting 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.
Finding the feasible regionFinding 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 →→3x + 200 – 8x = 80 →→-5x = -120 →→x = 24.
If x = 24, y = (80 – 3x24)/6 = 8/6 = 4/3.
⇒x=24,y=4/3⇒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.
Solving the objective function using the corner point methodSolving 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 ≤≤ 104, i.e, 4x + 6y ≤≤ 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.
The minimum feasible value for the mixture is Rs. 104.The minimum feasible value for the mixture is Rs. 104.