A sausage company makes two brands of sausages: Link and Patty. Link brand uses 1 pound of pork and 3 pounds of beef while the Patty brand uses 2 pounds of pork and 3 pounds of beef. A case of Link sausage requires 3 hours of labor while a case of Patty sausages requires 1 hour of labor. The company has at most 1000 pounds of pork and 1800 pounds of beef available to make sausages. The total work hours are restricted to no more than 1200 hours. The profit on a pound of Link sausage is $3 while the profit on a pound of Patty sausage is $2. How many pounds are required to maximize profit? 1. How many pounds of each should be produced to maximize profit? Use a table 2. What is the maximum profit.
A sausage company makes two brands of sausages: Link and Patty. Link brand uses 1 pound of pork and 3 pounds of beef while the Patty brand uses 2 pounds of pork and 3 pounds of beef. A case of Link sausage requires 3 hours of labor while a case of Patty sausages requires 1 hour of labor. The company has at most 1000 pounds of pork and 1800 pounds of beef available to make sausages. The total work hours are restricted to no more than 1200 hours. The profit on a pound of Link sausage is $3 while the profit on a pound of Patty sausage is $2. How many pounds are required to maximize profit?
1. How many pounds of each should be produced to maximize profit? Use a table
2. What is the maximum profit.
Let pound of Link sausage be X1 while pound of Patty sausage be X2.
|
||||||||||||||||||||||||
| subject to | ||||||||||||||||||||||||
|
||||||||||||||||||||||||
| and x1,x2≥0; |
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate
1. As the constraint-1 is of type '≤' we should add slack variable S1
2. As the constraint-2 is of type '≤' we should add slack variable S2
3. As the constraint-3 is of type '≤' we should add slack variable S3
After introducing slack variables
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
| subject to | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
| and x1,x2,S1,S2,S3≥0 |
| Iteration-1 | Cj | 3 | 2 | 0 | 0 | 0 | ||
| B | CB | XB | x1 | x2 | S1 | S2 | S3 | MinRatio XBx1 |
| S1 | 0 | 1000 | 1 | 2 | 1 | 0 | 0 | 10001=1000 |
| S2 | 0 | 1800 | 3 | 3 | 0 | 1 | 0 | 18003=600 |
| S3 | 0 | 1200 | (3) | 1 | 0 | 0 | 1 | 12003=400→ |
| Z=0 | Zj | 0 | 0 | 0 | 0 | 0 | ||
| Zj-Cj | -3↑ | -2 | 0 | 0 | 0 |
Negative minimum Zj-Cj is -3 and its column index is 1. So, the entering variable is x1.
Minimum ratio is 400 and its row index is 3. So, the leaving basis variable is S3.
∴ The pivot element is 3.
Entering =x1, Departing =S3, Key Element =3
R3(new)=R3(old) ÷3
R1(new)=R1(old) - R3(new)
R2(new)=R2(old) - 3R3(new)
| Iteration-2 | Cj | 3 | 2 | 0 | 0 | 0 | ||
| B | CB | XB | x1 | x2 | S1 | S2 | S3 | MinRatio XBx2 |
| S1 | 0 | 600 | 0 | 1.6667 | 1 | 0 | -0.3333 | 6001.6667=360 |
| S2 | 0 | 600 | 0 | (2) | 0 | 1 | -1 | 6002=300→ |
| x1 | 3 | 400 | 1 | 0.3333 | 0 | 0 | 0.3333 | 4000.3333=1200 |
| Z=1200 | Zj | 3 | 1 | 0 | 0 | 1 | ||
| Zj-Cj | 0 | -1↑ | 0 | 0 | 1 |
Negative minimum Zj-Cj is -1 and its column index is 2. So, the entering variable is x2.
Minimum ratio is 300 and its row index is 2. So, the leaving basis variable is S2.
∴ The pivot element is 2.
Step by step
Solved in 2 steps
