 | Service for Solving Linear Programming Problemsand other interesting typical problems |
Ðó |
Example ¹6. Transportation Problem by North-West Corner Method
(Unbalanced problem. Fictitious consumer)
This solution was made using the calculator presented on the site.
Example ¹1. Transportation problem by the Least Cost Method (Balanced problem)
Example ¹2. Transportation problem by the Least Cost Method (Unbalanced problem. Fictitious supplier)
Example ¹3. Transportation problem by the Least Cost Method (Unbalanced problem. Fictitious consumer)
Example ¹4. Transportation problem by the North-West Corner Method (Balanced problem)
Example ¹5. Transportation problem by the North-West Corner Method (Unbalanced problem. Fictitious supplier)
Example ¹2. Transportation problem by the Least Cost Method (Unbalanced problem. Fictitious supplier)
Example ¹3. Transportation problem by the Least Cost Method (Unbalanced problem. Fictitious consumer)
Example ¹4. Transportation problem by the North-West Corner Method (Balanced problem)
Example ¹5. Transportation problem by the North-West Corner Method (Unbalanced problem. Fictitious supplier)
X
Problem:
The cost of delivery of a unit of production from the supplier to the consumer is located in the lower right corner of the cell.
| Supplier | Consumer | Supply | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
3
|
5
|
4
| 20 |
| A 2 |
6
|
3
|
1
| 40 |
| A 3 |
3
|
2
|
7
| 30 |
| Customer needs | 30 | 35 | 20 | |
It is necessary to find a transport plan in which the total cost of delivery will be the lowest.
Solution:
This is a necessary condition for solving the problem:
the total supply of suppliers should be equal to the total needs of consumers.
Let's check it.
The total supply of suppliers: 20 + 40 + 30 = 90 units.
The total needs of consumers: 30 + 35 + 20 = 85 units.
the total supply of suppliers should be equal to the total needs of consumers.
Let's check it.
The total supply of suppliers: 20 + 40 + 30 = 90 units.
The total needs of consumers: 30 + 35 + 20 = 85 units.
The difference is 5 units.
Let's enter a fictitious consumer B4 into use. Let customer needs B4 is 5 units.
Let the cost of delivery from all suppliers to the consumer B4 is zero (see the table below).
Now the total supply of suppliers equals the total needs of consumers.
Let's enter a fictitious consumer B4 into use. Let customer needs B4 is 5 units.
Let the cost of delivery from all suppliers to the consumer B4 is zero (see the table below).
Now the total supply of suppliers equals the total needs of consumers.
This is a necessary condition for solving the problem:
number of used routes = number of suppliers + number of consumers - 1.
Therefore, if we have a situation where it is necessary to exclude a column and a row at the same time, we will exclude one thing.
number of used routes = number of suppliers + number of consumers - 1.
Therefore, if we have a situation where it is necessary to exclude a column and a row at the same time, we will exclude one thing.
We will start filling the table from the upper left corner and gradually move to the lower right corner.
From the North-West to South-East.
From the North-West to South-East.
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | ?
3
|
5
|
4
|
0
| 20 |
| A 2 |
6
|
3
|
1
|
0
| 40 |
| A 3 |
3
|
2
|
7
|
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
20 = min { 30, 20 }
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 No |
| A 2 | ?
6
|
3
|
1
|
0
| 40 |
| A 3 |
3
|
2
|
7
|
0
| 30 |
| Customer needs | 30 10 | 35 | 20 | 5 | |
10 = min { 10, 40 }
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 No |
| A 2 | 10
6
| ?
3
|
1
|
0
| 40 30 |
| A 3 |
3
|
2
|
7
|
0
| 30 |
| Customer needs | 30 10 No | 35 | 20 | 5 | |
30 = min { 35, 30 }
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 No |
| A 2 | 10
6
| 30
3
|
1
|
0
| 40 30 No |
| A 3 |
3
| ?
2
|
7
|
0
| 30 |
| Customer needs | 30 10 No | 35 5 | 20 | 5 | |
5 = min { 5, 30 }
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 No |
| A 2 | 10
6
| 30
3
|
1
|
0
| 40 30 No |
| A 3 |
3
| 5
2
| ?
7
|
0
| 30 25 |
| Customer needs | 30 10 No | 35 5 No | 20 | 5 | |
20 = min { 20, 25 }
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 No |
| A 2 | 10
6
| 30
3
|
1
|
0
| 40 30 No |
| A 3 |
3
| 5
2
| 20
7
| ?
0
| 30 25 5 |
| Customer needs | 30 10 No | 35 5 No | 20 No | 5 | |
5 = min { 5, 5 }
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 No |
| A 2 | 10
6
| 30
3
|
1
|
0
| 40 30 No |
| A 3 |
3
| 5
2
| 20
7
| 5
0
| 30 25 5 No |
| Customer needs | 30 10 No | 35 5 No | 20 No | 5 No | |
Let's calculate the total cost of delivery for the initial solution.
20*3 + 10*6 + 30*3 + 5*2 + 20*7 + 5*0 = 360
Is the initial solution optimal?
Let's check this using the MODI method (UV method).
To each supplier A i we associate a some number U i
To each consumer B j we associate a some number V j
To each consumer B j we associate a some number V j
For the routes used: U + V = cost of delivery.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u3 = 0.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u3 = 0.
| A3B2 : | v2 + u3 = 2 | v2 = 2 - 0 = 2 |
| A3B3 : | v3 + u3 = 7 | v3 = 7 - 0 = 7 |
| A3B4 : | v4 + u3 = 0 | v4 = 0 - 0 = 0 |
| A2B2 : | v2 + u2 = 3 | u2 = 3 - 2 = 1 |
| A2B1 : | v1 + u2 = 6 | v1 = 6 - 1 = 5 |
| A1B1 : | v1 + u1 = 3 | u1 = 3 - 5 = -2 |
| Supplier | Consumer | U | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| u1 = -2 |
| A 2 | 10
6
| 30
3
|
1
|
0
| u2 = 1 |
| A 3 |
3
| 5
2
| 20
7
| 5
0
| u3 = 0 |
| V | v1 = 5 | v2 = 2 | v3 = 7 | v4 = 0 | |
Let's find evaluations of unused routes (cij - cost of delivery). ?
|
There are negative evaluations. Therefore it is possible to reduce the total cost of delivery.
STEP ¹1.
The cell A2B3 (unused route) is selected ? because its evaluation is negative.
Please, move the mouse cursor to the selected cell A2B3. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A2B3.
The cells located at the vertices of the plotted line form a loop for the selected cell (see highlighted cells in the table below).
There is only one loop for cell A2B3.
Please, move the mouse cursor to the selected cell A2B3. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A2B3.
The cells located at the vertices of the plotted line form a loop for the selected cell (see highlighted cells in the table below).
There is only one loop for cell A2B3.
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 | 10
6
| 30
3
|
-7
1
|
0
| 40 |
| A 3 |
3
| 5
2
| 20
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
20 = min { 30, 20 } ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 | 10
6
| 30
3
|
-7
1
|
0
| 40 |
| A 3 |
3
| 5
2
| 20
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
This transformation will not change the balance.
But this transformation will change the total cost of delivery by:
1 * 20 - 3 * 20 + 2 * 20 - 7 * 20 = ( 1 - 3 + 2 - 7 ) * 20 = -7 * 20
You correctly noted that -7 * 20 = Δ23 * 20 ?
But this transformation will change the total cost of delivery by:
1 * 20 - 3 * 20 + 2 * 20 - 7 * 20 = ( 1 - 3 + 2 - 7 ) * 20 = -7 * 20
You correctly noted that -7 * 20 = Δ23 * 20 ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 | 10
6
| 30 - 20
3
| +20
-7
1
|
0
| 40 |
| A 3 |
3
| 5 + 20
2
| 20 - 20
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
We have a new solution. ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 | 10
6
| 10
3
| 20
1
|
0
| 40 |
| A 3 |
3
| 25
2
|
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
We will calculate the total cost of delivery of the new solution.
S = 360 + Δ23 * 20 = 360 -7 * 20 = 220
Is the new solution optimal?
Let's check this using the MODI method (UV method).
To each supplier A i we associate a some number U i
To each consumer B j we associate a some number V j
To each consumer B j we associate a some number V j
For the routes used: U + V = cost of delivery.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u2 = 0.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u2 = 0.
| A2B1 : | v1 + u2 = 6 | v1 = 6 - 0 = 6 |
| A2B2 : | v2 + u2 = 3 | v2 = 3 - 0 = 3 |
| A2B3 : | v3 + u2 = 1 | v3 = 1 - 0 = 1 |
| A3B2 : | v2 + u3 = 2 | u3 = 2 - 3 = -1 |
| A3B4 : | v4 + u3 = 0 | v4 = 0 - (-1) = 1 |
| A1B1 : | v1 + u1 = 3 | u1 = 3 - 6 = -3 |
| Supplier | Consumer | U | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| u1 = -3 |
| A 2 | 10
6
| 10
3
| 20
1
|
0
| u2 = 0 |
| A 3 |
3
| 25
2
|
7
| 5
0
| u3 = -1 |
| V | v1 = 6 | v2 = 3 | v3 = 1 | v4 = 1 | |
Let's find evaluations of unused routes (cij - cost of delivery). ?
|
There are negative evaluations. Therefore it is possible to reduce the total cost of delivery.
STEP ¹2.
The cell A3B1 (unused route) is selected ? because its evaluation is negative.
Please, move the mouse cursor to the selected cell A3B1. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A3B1.
The cells located at the vertices of the plotted line form a loop for the selected cell (see highlighted cells in the table below).
There is only one loop for cell A3B1.
Please, move the mouse cursor to the selected cell A3B1. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A3B1.
The cells located at the vertices of the plotted line form a loop for the selected cell (see highlighted cells in the table below).
There is only one loop for cell A3B1.
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 | 10
6
| 10
3
| 20
1
|
0
| 40 |
| A 3 |
-2
3
| 25
2
|
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
10 = min { 25, 10 } ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 | 10
6
| 10
3
| 20
1
|
0
| 40 |
| A 3 |
-2
3
| 25
2
|
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
This transformation will not change the balance.
But this transformation will change the total cost of delivery by:
3 * 10 - 2 * 10 + 3 * 10 - 6 * 10 = ( 3 - 2 + 3 - 6 ) * 10 = -2 * 10
You correctly noted that -2 * 10 = Δ31 * 10 ?
But this transformation will change the total cost of delivery by:
3 * 10 - 2 * 10 + 3 * 10 - 6 * 10 = ( 3 - 2 + 3 - 6 ) * 10 = -2 * 10
You correctly noted that -2 * 10 = Δ31 * 10 ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 | 10 - 10
6
| 10 + 10
3
| 20
1
|
0
| 40 |
| A 3 | +10
-2
3
| 25 - 10
2
|
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
We have a new solution. ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 |
6
| 20
3
| 20
1
|
0
| 40 |
| A 3 | 10
3
| 15
2
|
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
We will calculate the total cost of delivery of the new solution.
S = 220 + Δ31 * 10 = 220 -2 * 10 = 200
Is the new solution optimal?
Let's check this using the MODI method (UV method).
To each supplier A i we associate a some number U i
To each consumer B j we associate a some number V j
To each consumer B j we associate a some number V j
For the routes used: U + V = cost of delivery.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u3 = 0.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u3 = 0.
| A3B1 : | v1 + u3 = 3 | v1 = 3 - 0 = 3 |
| A3B2 : | v2 + u3 = 2 | v2 = 2 - 0 = 2 |
| A3B4 : | v4 + u3 = 0 | v4 = 0 - 0 = 0 |
| A1B1 : | v1 + u1 = 3 | u1 = 3 - 3 = 0 |
| A2B2 : | v2 + u2 = 3 | u2 = 3 - 2 = 1 |
| A2B3 : | v3 + u2 = 1 | v3 = 1 - 1 = 0 |
| Supplier | Consumer | U | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| u1 = 0 |
| A 2 |
6
| 20
3
| 20
1
|
0
| u2 = 1 |
| A 3 | 10
3
| 15
2
|
7
| 5
0
| u3 = 0 |
| V | v1 = 3 | v2 = 2 | v3 = 0 | v4 = 0 | |
Let's find evaluations of unused routes (cij - cost of delivery). ?
|
There is negative evaluation. Therefore it is possible to reduce the total cost of delivery.
STEP ¹3.
The cell A2B4 (unused route) is selected because its evaluation is negative.
Please, move the mouse cursor to the selected cell A2B4. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A2B4.
The cells located at the vertices of the plotted line form a loop for the selected cell (see highlighted cells in the table below).
There is only one loop for cell A2B4.
Please, move the mouse cursor to the selected cell A2B4. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A2B4.
The cells located at the vertices of the plotted line form a loop for the selected cell (see highlighted cells in the table below).
There is only one loop for cell A2B4.
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 |
6
| 20
3
| 20
1
|
-1
0
| 40 |
| A 3 | 10
3
| 15
2
|
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
5 = min { 20, 5 } ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 |
6
| 20
3
| 20
1
|
-1
0
| 40 |
| A 3 | 10
3
| 15
2
|
7
| 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
This transformation will not change the balance.
But this transformation will change the total cost of delivery by:
0 * 5 - 3 * 5 + 2 * 5 - 0 * 5 = ( 0 - 3 + 2 - 0 ) * 5 = -1 * 5
You correctly noted that -1 * 5 = Δ24 * 5 ?
But this transformation will change the total cost of delivery by:
0 * 5 - 3 * 5 + 2 * 5 - 0 * 5 = ( 0 - 3 + 2 - 0 ) * 5 = -1 * 5
You correctly noted that -1 * 5 = Δ24 * 5 ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 |
6
| 20 - 5
3
| 20
1
| +5
-1
0
| 40 |
| A 3 | 10
3
| 15 + 5
2
|
7
| 5 - 5
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
We have a new solution. ?
| Supplier | Consumer | Supply | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| 20 |
| A 2 |
6
| 15
3
| 20
1
| 5
0
| 40 |
| A 3 | 10
3
| 20
2
|
7
|
0
| 30 |
| Customer needs | 30 | 35 | 20 | 5 | |
We will calculate the total cost of delivery of the new solution.
S = 200 + Δ24 * 5 = 200 -1 * 5 = 195
Is the new solution optimal?
Let's check this using the MODI method (UV method).
To each supplier A i we associate a some number U i
To each consumer B j we associate a some number V j
To each consumer B j we associate a some number V j
For the routes used: U + V = cost of delivery.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u2 = 0.
Let's find U i and V j step by step.
To do this, we need to enter the value of one of them. Let u2 = 0.
| A2B2 : | v2 + u2 = 3 | v2 = 3 - 0 = 3 |
| A2B3 : | v3 + u2 = 1 | v3 = 1 - 0 = 1 |
| A2B4 : | v4 + u2 = 0 | v4 = 0 - 0 = 0 |
| A3B2 : | v2 + u3 = 2 | u3 = 2 - 3 = -1 |
| A3B1 : | v1 + u3 = 3 | v1 = 3 - (-1) = 4 |
| A1B1 : | v1 + u1 = 3 | u1 = 3 - 4 = -1 |
| Supplier | Consumer | U | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 20
3
|
5
|
4
|
0
| u1 = -1 |
| A 2 |
6
| 15
3
| 20
1
| 5
0
| u2 = 0 |
| A 3 | 10
3
| 20
2
|
7
|
0
| u3 = -1 |
| V | v1 = 4 | v2 = 3 | v3 = 1 | v4 = 0 | |
Let's find evaluations of unused routes (cij - cost of delivery). ?
|
There are no negative evaluations. Therefore it is not possible to reduce the total cost of delivery.
Result:X opt = |  | 20 | 0 | 0 | 0 |  | |
| 0 | 15 | 20 | 5 | ||||
| 10 | 20 | 0 | 0 |
Smin = 195
© 2010-2026 If you have any comments, please write to matematika1974@yandex.ru