Bruce's Material Company hauls gravel to a construction site, using a small truck and a large truck. The carrying capacity and operating cost per load are given in the accompanying table. Bruce must deliver a minimum of 630 cubic yards per day to satisfy her contract with the builder. The union contract with her drivers requires that the total number of loads per day is a minimum of 10. How many loads should be made in each truck per day to minimize the total cost? Capacity (yd³) Cost per Load Small Truck Large Truck 70 90 $76 $63 In order to minimize the total cost, the number of loads in a small truck that should be made is be made is. and the number of loads in a large truck that should
Let number of loads of Small truck per day be X1 and number of loads of Large truck per day 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 subtract surplus variable S1 and add artificial variable A1
2. As the constraint-2 is of type '≥' we should subtract surplus variable S2 and add artificial variable A2
After introducing surplus,artificial variables
|
||||||||||||||||||||||||||||||||||||||||
| subject to | ||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||
| and x1,x2,S1,S2,A1,A2≥0 |
| Iteration-1 | Cj | 76 | 63 | 0 | 0 | M | M | ||
| B | CB | XB | x1 | x2 | S1 | S2 | A1 | A2 | MinRatio XBx2 |
| A1 | M | 630 | 70 | (90) | -1 | 0 | 1 | 0 | 63090=7→ |
| A2 | M | 10 | 1 | 1 | 0 | -1 | 0 | 1 | 101=10 |
| Z=640M | Zj | 71M | 91M | -M | -M | M | M | ||
| Zj-Cj | 71M-76 | 91M-63↑ | -M | -M | 0 | 0 |
Positive maximum Zj-Cj is 91M-63 and its column index is 2. So, the entering variable is x2.
Minimum ratio is 7 and its row index is 1. So, the leaving basis variable is A1.
∴ The pivot element is 90.
Entering =x2, Departing =A1, Key Element =90
R1(new)=R1(old) ÷90
R2(new)=R2(old) - R1(new)
| Iteration-2 | Cj | 76 | 63 | 0 | 0 | M | ||
| B | CB | XB | x1 | x2 | S1 | S2 | A2 | MinRatio XBx1 |
| x2 | 63 | 7 | (0.7778) | 1 | -0.0111 | 0 | 0 | 70.7778=9→ |
| A2 | M | 3 | 0.2222 | 0 | 0.0111 | -1 | 1 | 30.2222=13.5 |
| Z=3M+441 | Zj | 0.2222M+49 | 63 | 0.0111M-0.7 | -M | M | ||
| Zj-Cj | 0.2222M-27↑ | 0 | 0.0111M-0.7 | -M | 0 |
Positive maximum Zj-Cj is 0.2222M-27 and its column index is 1. So, the entering variable is x1.
Minimum ratio is 9 and its row index is 1. So, the leaving basis variable is x2.
∴ The pivot element is 0.7778.
Entering =x1, Departing =x2, Key Element =0.7778
R1(new)=R1(old) ÷0.7778
R2(new)=R2(old) - 0.2222R1(new)
| Iteration-3 | Cj | 76 | 63 | 0 | 0 | M | ||
| B | CB | XB | x1 | x2 | S1 | S2 | A2 | MinRatio XBS1 |
| x1 | 76 | 9 | 1 | 1.2857 | -0.0143 | 0 | 0 | --- |
| A2 | M | 1 | 0 | -0.2857 | (0.0143) | -1 | 1 | 10.0143=70→ |
| Z=M+684 | Zj | 76 | -0.2857M+97.7143 | 0.0143M-1.0857 | -M | M | ||
| Zj-Cj | 0 | -0.2857M+34.7143 | 0.0143M-1.0857↑ | -M | 0 |
Positive maximum Zj-Cj is 0.0143M-1.0857 and its column index is 3. So, the entering variable is S1.
Minimum ratio is 70 and its row index is 2. So, the leaving basis variable is A2.
∴ The pivot element is 0.0143.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
