Maximization Transportation Problem
There are certain types of transportation problems where the objective function is to be maximized instead of being minimized.
These problems can be solved by converting the maximization problem into a minimization problem by subtracting all the elements from maximum element
Find Solution using Voggel's Approximation method (Maximization)
| D1 | D2 | D3 | Supply |
| S1 | 8 | 5 | 6 | 120 |
| S2 | 15 | 10 | 12 | 80 |
| S3 | 3 | 9 | 10 | 80 |
| Demand | 150 | 80 | 50 | |
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 8 | 5 | 6 | | 120 |
| `S_2` | 15 | 10 | 12 | | 80 |
| `S_3` | 3 | 9 | 10 | | 80 |
| |
| Demand | 150 | 80 | 50 | | |
Problem is Maximization, so convert it to minimization by subtracting all the elements from max element (15)
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 7 | 10 | 9 | | 120 |
| `S_2` | 0 | 5 | 3 | | 80 |
| `S_3` | 12 | 6 | 5 | | 80 |
| |
| Demand | 150 | 80 | 50 | | |
Table-1
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty |
| `S_1` | 7 | 10 | 9 | | 120 | `2=9-7` |
| `S_2` | 0 | 5 | 3 | | 80 | `3=3-0` |
| `S_3` | 12 | 6 | 5 | | 80 | `1=6-5` |
| |
| Demand | 150 | 80 | 50 | | | |
Column
Penalty | `7=7-0` | `1=6-5` | `2=5-3` | | | |
The maximum penalty, 7, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_21`=0.
The maximum allocation in this cell is min(80,150) = 80.
It satisfy supply of `S_2` and adjust the demand of `D_1` from 150 to 70 (150 - 80=70).
Table-2
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty |
| `S_1` | 7 | 10 | 9 | | 120 | `2=9-7` |
| `S_2` | 0(80) | 5 | 3 | | 0 | -- |
| `S_3` | 12 | 6 | 5 | | 80 | `1=6-5` |
| |
| Demand | 70 | 80 | 50 | | | |
Column
Penalty | `5=12-7` | `4=10-6` | `4=9-5` | | | |
The maximum penalty, 5, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_11`=7.
The maximum allocation in this cell is min(120,70) = 70.
It satisfy demand of `D_1` and adjust the supply of `S_1` from 120 to 50 (120 - 70=50).
Table-3
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty |
| `S_1` | 7(70) | 10 | 9 | | 50 | `1=10-9` |
| `S_2` | 0(80) | 5 | 3 | | 0 | -- |
| `S_3` | 12 | 6 | 5 | | 80 | `1=6-5` |
| |
| Demand | 0 | 80 | 50 | | | |
Column
Penalty | -- | `4=10-6` | `4=9-5` | | | |
The maximum penalty, 4, occurs in column `D_3`.
The minimum `c_(ij)` in this column is `c_33`=5.
The maximum allocation in this cell is min(80,50) = 50.
It satisfy demand of `D_3` and adjust the supply of `S_3` from 80 to 30 (80 - 50=30).
Table-4
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty |
| `S_1` | 7(70) | 10 | 9 | | 50 | `10` |
| `S_2` | 0(80) | 5 | 3 | | 0 | -- |
| `S_3` | 12 | 6 | 5(50) | | 30 | `6` |
| |
| Demand | 0 | 80 | 0 | | | |
Column
Penalty | -- | `4=10-6` | -- | | | |
The maximum penalty, 10, occurs in row `S_1`.
The minimum `c_(ij)` in this row is `c_12`=10.
The maximum allocation in this cell is min(50,80) = 50.
It satisfy supply of `S_1` and adjust the demand of `D_2` from 80 to 30 (80 - 50=30).
Table-5
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty |
| `S_1` | 7(70) | 10(50) | 9 | | 0 | -- |
| `S_2` | 0(80) | 5 | 3 | | 0 | -- |
| `S_3` | 12 | 6 | 5(50) | | 30 | `6` |
| |
| Demand | 0 | 30 | 0 | | | |
Column
Penalty | -- | `6` | -- | | | |
The maximum penalty, 6, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_32`=6.
The maximum allocation in this cell is min(30,30) = 30.
It satisfy supply of `S_3` and demand of `D_2`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty |
| `S_1` | 7(70) | 10(50) | 9 | | 120 | 2 | 2 | 1 | 10 | -- | |
| `S_2` | 0(80) | 5 | 3 | | 80 | 3 | -- | -- | -- | -- | |
| `S_3` | 12 | 6(30) | 5(50) | | 80 | 1 | 1 | 1 | 6 | 6 | |
| |
| Demand | 150 | 80 | 50 | | | |
Column
Penalty | 7
5
--
--
--
| 1
4
4
4
6
| 2
4
4
--
--
| | | |
Allocations in the original problem
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 8 (70) | 5 (50) | 6 | | 120 |
| `S_2` | 15 (80) | 10 | 12 | | 80 |
| `S_3` | 3 | 9 (30) | 10 (50) | | 80 |
| |
| Demand | 150 | 80 | 50 | | |
The maximum profit `=8 xx 70+5 xx 50+15 xx 80+9 xx 30+10 xx 50=2780`
Here, the number of allocated cells = 5 is equal to m + n - 1 = 3 + 3 - 1 = 5
`:.` This solution is non-degenerate
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
