Discussion
Consider the following transportation problem :
| Warehouse | |||||
|---|---|---|---|---|---|
| Factory | W1 | W2 | W3 | W4 | |
| F1 | 1 | 2 | 3 | 4 | 6 |
| F2 | 4 | 3 | 2 | 0 | 8 |
| F3 | 0 | 2 | 2 | 1 | 10 |
| 4 | 6 | 8 | 6 | ||
A solution to the problem is given below :
| 6 | |||
| 2 | 6 | ||
| 4 | 6 |
Which of the following is true about the solution ?
Answer: B
The solution is degenerate and optimal.
Supply (6 + 8 + 10 = 24) equals demand (4 + 6 + 8 + 6 = 24). A basic solution of a 3 × 4 problem needs m + n - 1 = 6 occupied cells, but this one has only 5: (F1, W2) = 6, (F2, W3) = 2, (F2, W4) = 6, (F3, W1) = 4 and (F3, W3) = 6. So it is degenerate.
To test optimality, place a zero allocation (epsilon) in cell (F1, W1) and solve \(u_i + v_j = c_{ij}\) on the six basic cells. Taking \(u_3 = 0\) gives \(v_1 = 0, v_3 = 2, u_2 = 0, v_4 = 0, u_1 = 1, v_2 = 1\).
The reduced costs \(c_{ij} - u_i - v_j\) of the empty cells are then 0 (F1, W3), 3 (F1, W4), 4 (F2, W1), 2 (F2, W2), 1 (F3, W2) and 1 (F3, W4). None is negative, so the solution is optimal, with total cost 12 + 4 + 0 + 0 + 12 = 28. Optimality can be tested once the degeneracy is resolved, so the last option is wrong too.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development