(Hamburger). A fast-food store grinds three dierent cuts of beef to make its ham
ID: 3116413 • Letter: #
Question
(Hamburger). A fast-food store grinds three dierent cuts of beef to make its hamburg. Each pound of chuck has 2 units of fat, 4 units of protein and costs $.32. Each pound of rump has 2 units of fat, 8 units of protein and costs $.40; and each pound of ank has 1 unit of fat, 3 units of protein and costs $.25. The store wants each pound to have no more than 2 units of fat and at least 7 units of protein. Let x1,x2,x3 be the proportions of chuck, rump and ank. Find the proportions of each cut which will cost the least. (Note: Don’t forget the equality x1 +x2 +x3 = 1. To use the dual simplex method negate this inequality and add an articial variable. Then use the dual simplex approach to drive the articial variable out of the basis.)
Explanation / Answer
Let x1,x2,x3 be the proportion of chunk, rump and flank ,then the problem can be written in form:
MIN Z = 0.32x1 + 0.4x2 + 0.25x3
subject to
2x1 + 2x2 + x3 <= 2
4x1 + 8x2 + 3x3 >= 7
x1 + x2 + x3 = 1
and x1,x2,x3 >= 0
In order to apply the dual simplex method, convert Min Z to Max Z and all constraint to constraint by multiply -1.
Problem is
and x1,x2,x30;
After introducing slack,artificial variables
and x1,x2,x3,S1,S2,A10
ratio=(Cj-Zj)/S2,j
and S2,j<0
Minimum negative XB is -7 and its row index is 2. So, the leaving basis variable is S2.
Minimum positive ratio is -3333.25 and its column index is 3. So, the entering variable is x3.
The pivot element is -3.
Entering =x3, Departing =S2, Key Element =-3
R2(new)=R2(old)÷-3
R1(new)=R1(old)-R2(new)
R3(new)=R3(old)-R2(new)
Minimum negative XB is -4/3 and its row index is 3. So, the leaving basis variable is A1.
Minimum positive ratio is 9999.84 and its column index is 2. So, the entering variable is x2.
The pivot element is -5/3.
Entering =x2, Departing =A1, Key Element =-5/3
R3(new)=R3(old)×-3/5
R1(new)=R1(old)+2/3R3(new)
R2(new)=R2(old)-8/3R3(new)
Since all Cj-Zj0 and all XBi0 thus the current solution is the optimal solution.
Hence, optimal solution is arrived with value of variables as :
x1=0,x2=4/5,x3=1/5
Max Z=-0.37
since we change the minimization problem to maximization problem so now we need to change it to minimization again ,therefore minimum cost = 0.37 dollars
Max Z = - 0.32 x1 - 0.4 x2 - 0.25 x3 subject to 2 x1 + 2 x2 + x3 2 - 4 x1 - 8 x2 - 3 x3 -7 x1 + x2 + x3 = 1and x1,x2,x30;
After introducing slack,artificial variables
Max Z = - 0.32 x1 - 0.4 x2 - 0.25 x3 + 0 S1 + 0 S2 - M A1 subject to 2 x1 + 2 x2 + x3 + S1 = 2 - 4 x1 - 8 x2 - 3 x3 + S2 = -7 x1 + x2 + x3 + A1 = 1and x1,x2,x3,S1,S2,A10
iteration1 Cj -0.32 -0.4 -0.25 0 0 -M B CB XB X1 X2 X3 S1 S2 A1 S1 0 2 2 2 1 1 0 0 S2 0 -7 -4 -8 (-3) 0 1 0 A1 -M 1 1 1 1 0 0 1 Z=0 ZJ -M -M -M 0 0 -M Cj-Zj M-8/25 M-2/5 M-1/4 0 0 0ratio=(Cj-Zj)/S2,j
and S2,j<0
-62498/25 -24999/20 -13333/4 ------ ------ -------Minimum negative XB is -7 and its row index is 2. So, the leaving basis variable is S2.
Minimum positive ratio is -3333.25 and its column index is 3. So, the entering variable is x3.
The pivot element is -3.
Entering =x3, Departing =S2, Key Element =-3
R2(new)=R2(old)÷-3
R1(new)=R1(old)-R2(new)
R3(new)=R3(old)-R2(new)
Minimum negative XB is -4/3 and its row index is 3. So, the leaving basis variable is A1.
Minimum positive ratio is 9999.84 and its column index is 2. So, the entering variable is x2.
The pivot element is -5/3.
Entering =x2, Departing =A1, Key Element =-5/3
R3(new)=R3(old)×-3/5
R1(new)=R1(old)+2/3R3(new)
R2(new)=R2(old)-8/3R3(new)
Since all Cj-Zj0 and all XBi0 thus the current solution is the optimal solution.
Hence, optimal solution is arrived with value of variables as :
x1=0,x2=4/5,x3=1/5
Max Z=-0.37
since we change the minimization problem to maximization problem so now we need to change it to minimization again ,therefore minimum cost = 0.37 dollars
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.