Service for Solving Linear Programming Problems

Let good people see good solutions

Example 6. Transportation Problem by North-West Corner Method
(Unbalanced problem. Fictitious consumer)

This solution has been done by the calculator presented on the site.
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 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.
This is a necessary condition for solving the problem:
number of used routes = number of suppliers + number of consumers - 1.

So if there is 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 out the table from the upper left corner and gradually move to the lower right corner.
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 it.
To each supplier A i we associate a some number u i called a potential of the supplier.
To each consumer B j we associate a some number v j called a potential of the consumer.
For used routes: potential of the supplier + potential of the consumer = cost of delivery.
Let's find potentials sequentially.
We must enter the value of one potential. 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).
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( -2 + 2 ) = 5  
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 4 - ( -2 + 7 ) = -1  
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 0 - ( -2 + 0 ) = 2  
A2B3 :   Δ23 = c23 - ( u2 + v3 ) = 1 - ( 1 + 7 ) = -7  
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 0 - ( 1 + 0 ) = -1  
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 3 - ( 0 + 5 ) = -2  
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.
Move the mouse cursor to the selected cell A2B3.
Using the horizontal and vertical cursor movements, 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 cycle for the selected cell (see the highlighted cells in the table below).
There is only one cycle 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 noticed 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 got 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  
Let's calculate the total cost of delivery for the new solution.

S = 360 + Δ23 * 20 = 360 -7 * 20 = 220

Is the new solution optimal?
Let's check it.
To each supplier A i we associate a some number u i called a potential of the supplier.
To each consumer B j we associate a some number v j called a potential of the consumer.
For used routes: potential of the supplier + potential of the consumer = cost of delivery.
Let's find potentials sequentially.
We must enter the value of one potential. 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).
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( -3 + 3 ) = 5  
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 4 - ( -3 + 1 ) = 6  
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 0 - ( -3 + 1 ) = 2  
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 0 - ( 0 + 1 ) = -1  
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 3 - ( -1 + 6 ) = -2  
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 7 - ( -1 + 1 ) = 7  
There are negative evaluations. Therefore it is possible to reduce the total cost of delivery.
STEP 2.
The cell A2B4 (unused route) is selected because its evaluation is negative.
Move the mouse cursor to the selected cell A2B4.
Using the horizontal and vertical cursor movements, 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 cycle for the selected cell (see the highlighted cells in the table below).
There is only one cycle for cell A2B4.
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
-1
0
  40  
A 3
3
25
2
7
5
0
  30  
  Customer  
needs  
  30     35     20     5  
5 = min { 10, 5 }
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
-1
0
  40  
A 3
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:
0 * 5 - 3 * 5 + 2 * 5 - 0 * 5 = ( 0 - 3 + 2 - 0 ) * 5 = -1 * 5
You correctly noticed 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
10
6
10 - 5
3
20
1
+5
-1
0
  40  
A 3
3
25 + 5
2
7
5 - 5
0
  30  
  Customer  
needs  
  30     35     20     5  
We got 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
5
3
20
1
5
0
  40  
A 3
3
30
2
7
0
  30  
  Customer  
needs  
  30     35     20     5  
Let's calculate the total cost of delivery for the new solution.

S = 220 + Δ24 * 5 = 220 -1 * 5 = 215

Is the new solution optimal?
Let's check it.
To each supplier A i we associate a some number u i called a potential of the supplier.
To each consumer B j we associate a some number v j called a potential of the consumer.
For used routes: potential of the supplier + potential of the consumer = cost of delivery.
Let's find potentials sequentially.
We must enter the value of one potential. 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
A2B4 :   v4 + u2 = 0     v4 = 0 - 0 = 0
A3B2 :   v2 + u3 = 2     u3 = 2 - 3 = -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
5
3
20
1
5
0
  u2 = 0  
A 3
3
30
2
7
0
  u3 = -1  
  V   v1 = 6 v2 = 3 v3 = 1 v4 = 0
Let's find evaluations of unused routes (cij - cost of delivery).
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( -3 + 3 ) = 5  
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 4 - ( -3 + 1 ) = 6  
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 0 - ( -3 + 0 ) = 3  
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 3 - ( -1 + 6 ) = -2  
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 7 - ( -1 + 1 ) = 7  
A3B4 :   Δ34 = c34 - ( u3 + v4 ) = 0 - ( -1 + 0 ) = 1  
There are negative evaluations. Therefore it is possible to reduce the total cost of delivery.
STEP 3.
The cell A3B1 (unused route) is selected because its evaluation is negative.
Move the mouse cursor to the selected cell A3B1.
Using the horizontal and vertical cursor movements, 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 cycle for the selected cell (see the highlighted cells in the table below).
There is only one cycle 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
5
3
20
1
5
0
  40  
A 3
-2
3
30
2
7
0
  30  
  Customer  
needs  
  30     35     20     5  
10 = min { 30, 10 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
3
5
4
0
  20  
A 2
10
6
5
3
20
1
5
0
  40  
A 3
-2
3
30
2
7
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 noticed 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
5 + 10
3
20
1
5
0
  40  
A 3
+10
-2
3
30 - 10
2
7
0
  30  
  Customer  
needs  
  30     35     20     5  
We got 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  
Let's calculate the total cost of delivery for the new solution.

S = 215 + Δ31 * 10 = 215 -2 * 10 = 195

Is the new solution optimal?
Let's check it.
To each supplier A i we associate a some number u i called a potential of the supplier.
To each consumer B j we associate a some number v j called a potential of the consumer.
For used routes: potential of the supplier + potential of the consumer = cost of delivery.
Let's find potentials sequentially.
We must enter the value of one potential. 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).
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( -1 + 3 ) = 3  
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 4 - ( -1 + 1 ) = 4  
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 0 - ( -1 + 0 ) = 1  
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 6 - ( 0 + 4 ) = 2  
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 7 - ( -1 + 1 ) = 7  
A3B4 :   Δ34 = c34 - ( u3 + v4 ) = 0 - ( -1 + 0 ) = 1  
There are not any 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-2020 If you have comments, please write to matematika1974@yandex.ru