What’s the optimal solution to
What’s the optimal solution to this linear programmingproblem?
Max | 2X + 3Y |
s.t. | 4X + 9Y ≤ 72 |
10X + 11Y ≤ 110 | |
17X + 9Y ≤ 153 | |
X,Y ≥ 0 |
Answer:
We have,
Max | 2X + 3Y |
s.t. | 4X + 9Y ≤ 72 |
10X + 11Y ≤ 110 | |
17X + 9Y ≤ 153 | |
X,Y ≥ 0 |
To convert the problem to canonical form we will add addingslack variable to each constraint as all constraints areof type ‘≤’After introducing slack variables
Max | 2X + 3Y+0S1 +0S2 + 0S3 |
s.t. | 4X + 9Y + S1≤ 72 |
10X + 11Y + S2 ≤ 110 | |
17X + 9Y +S3 ≤ 153 | |
X,Y ≥ 0 |
Iteration-1 | Cj | 2 | 3 | 0 | 0 | 0 | ||
B | CB | XB | X | Y | S1 | S2 | S3 | Min RatioXB / Y |
S1 | 0 | 72 | 4 | (9) | 1 | 0 | 0 | 72 /9=8→ |
S2 | 0 | 110 | 10 | 11 | 0 | 1 | 0 | 110 /11=10 |
S3 | 0 | 153 | 17 | 9 | 0 | 0 | 1 | 153 /9=17 |
Z=0 | Zj | 0 | 0 | 0 | 0 | 0 | ||
Zj–Cj | -2 | -3↑ | 0 | 0 | 0 |
Negative minimum Zj–Cj is -3 and its columnindex is 2. So, the entering variable is Y.Minimum ratio is 8 and its row index is 1. So, the leaving basisvariable is S1.∴ The pivot element is 9.
Iteration-2 | Cj | 2 | 3 | 0 | 0 | 0 | ||
B | CB | XB | X | Y | S1 | S2 | S3 | Min RatioXB / X |
Y | 3 | 8 | 0.4444 | 1 | 0.1111 | 0 | 0 | 8 / 0.4444 = 18 |
S2 | 0 | 22 | (5.1111) | 0 | -1.2222 | 1 | 0 | 22 / 5.1111 = 4.3043→ |
S3 | 0 | 81 | 13 | 0 | -1 | 0 | 1 | 81 / 13 = 6.2308 |
Z=24 | Zj | 1.3333 | 3 | 0.3333 | 0 | 0 | ||
Zj–Cj | -0.6667↑ | 0 | 0.3333 | 0 | 0 |
Negative minimum Zj–Cj is -0.6667 and itscolumn index is 1. So, the entering variable is X.Minimum ratio is 4.3043 and its row index is 2. So, the leavingbasis variable is S2.∴ The pivot element is 5.1111.
Iteration-3 | Cj | 2 | 3 | 0 | 0 | 0 | ||
B | CB | XB | X | Y | S1 | S2 | S3 | Min Ratio |
Y | 3 | 6.087 | 0 | 1 | 0.2174 | -0.087 | 0 | |
X | 2 | 4.3043 | 1 | 0 | -0.2391 | 0.1957 | 0 | |
S3 | 0 | 25.0435 | 0 | 0 | 2.1087 | -2.5435 | 1 | |
Z=26.8696 | Zj | 2 | 3 | 0.1739 | 0.1304 | 0 | ||
Zj–Cj | 0 | 0 | 0.1739 | 0.1304 | 0 |
Since all Zj-Cj≥0Hence, the optimal solution is:X=4.3043,
Y=6.087Max Z=26.8696