Service for Solving Linear Programming Problems

and other interesting typical problems		 Ðóññêèé

Example ¹5. Transportation Problem by North-West Corner Method
(Unbalanced problem. Fictitious supplier)

This solution was made using the calculator presented on the site.
Go to the solution of your problem
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 B 4
A 1
4
5
3
6
   30  
A 2
7
2
1
5
   25  
A 3
6
1
4
2
   20  
  Customer  
needs 		20 15 25 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: 30 + 25 + 20 = 75 units.
The total needs of consumers: 20 + 15 + 25 + 20 = 80 units.
The difference is 5 units.
Let's enter a fictitious supplier A4 into use. Let supplier A4 has 5 units.
Let the cost of delivery from supplier A4 to all consumers 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.
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.
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
?
4
5
3
6
   30  
A 2
7
2
1
5
   25  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Customer  
needs 		20 15 25 20
20 = min { 20, 30 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
?
5
3
6
   30   10  
A 2
7
2
1
5
   25  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Customer  
needs 		20
No		 15 25 20
10 = min { 15, 10 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   No  
A 2
7
?
2
1
5
   25  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Customer  
needs 		20
No		 15
5 		25 20
5 = min { 5, 25 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   No  
A 2
7
5
2
?
1
5
   25   20  
A 3
6
1
4
2
   20  
A 4
0
0
0
0
   5  
  Customer  
needs 		20
No		 15
5
No		 25 20
20 = min { 25, 20 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   No  
A 2
7
5
2
20
1
5
   25   20   No  
A 3
6
1
?
4
2
   20  
A 4
0
0
0
0
   5  
  Customer  
needs 		20
No		 15
5
No		 25
5 		20
5 = min { 5, 20 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   No  
A 2
7
5
2
20
1
5
   25   20   No  
A 3
6
1
5
4
?
2
   20   15  
A 4
0
0
0
0
   5  
  Customer  
needs 		20
No		 15
5
No		 25
5
No		 20
15 = min { 20, 15 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   No  
A 2
7
5
2
20
1
5
   25   20   No  
A 3
6
1
5
4
15
2
   20   15   No  
A 4
0
0
0
?
0
   5  
  Customer  
needs 		20
No		 15
5
No		 25
5
No		 20
5
5 = min { 5, 5 }
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30   10   No  
A 2
7
5
2
20
1
5
   25   20   No  
A 3
6
1
5
4
15
2
   20   15   No  
A 4
0
0
0
5
0
   5   No  
  Customer  
needs 		20
No		 15
5
No		 25
5
No		 20
5
No
Let's calculate the total cost of delivery for the initial solution.

20*4 + 10*5 + 5*2 + 20*1 + 5*4 + 15*2 + 5*0 = 210

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
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 u1 = 0.
A1B1 :   v1 + u1 = 4     v1 = 4 - 0 = 4
A1B2 :   v2 + u1 = 5     v2 = 5 - 0 = 5
A2B2 :   v2 + u2 = 2     u2 = 2 - 5 = -3
A2B3 :   v3 + u2 = 1     v3 = 1 - (-3) = 4
A3B3 :   v3 + u3 = 4     u3 = 4 - 4 = 0
A3B4 :   v4 + u3 = 2     v4 = 2 - 0 = 2
A4B4 :   v4 + u4 = 0     u4 = 0 - 2 = -2
More info about finding UV
  Supplier   Consumer   U  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   u1 = 0  
A 2
7
5
2
20
1
5
   u2 = -3  
A 3
6
1
5
4
15
2
   u3 = 0  
A 4
0
0
0
5
0
   u4 = -2  
  V   v1 = 4 v2 = 5 v3 = 4 v4 = 2
Let's find evaluations of unused routes (cij - cost of delivery). ?
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 3 - ( 0 + 4 ) = -1
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 6 - ( 0 + 2 ) = 4
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 7 - ( -3 + 4 ) = 6
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 5 - ( -3 + 2 ) = 6
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 6 - ( 0 + 4 ) = 2
A3B2 :   Δ32 = c32 - ( u3 + v2 ) = 1 - ( 0 + 5 ) = -4
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -2 + 4 ) = -2
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -2 + 5 ) = -3
A4B3 :   Δ43 = c43 - ( u4 + v3 ) = 0 - ( -2 + 4 ) = -2
There are negative evaluations. Therefore it is possible to reduce the total cost of delivery.
STEP ¹1.
The cell A3B2 (unused route) is selected ? because its evaluation is negative.
Please, move the mouse cursor to the selected cell A3B2. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A3B2.
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 A3B2.
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
5
2
20
1
5
   25  
A 3
6
-4
1
5
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
5 = min { 5, 5 } ?
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
5
2
20
1
5
   25  
A 3
6
-4
1
5
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
This transformation will not change the balance.
But this transformation will change the total cost of delivery by:
1 * 5 - 4 * 5 + 1 * 5 - 2 * 5 = ( 1 - 4 + 1 - 2 ) * 5 = -4 * 5
You correctly noted that   -4 * 5 = Δ32 * 5 ?
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
5 - 5
2
20 + 5
1
5
   25  
A 3
6
+5
-4
1
5 - 5
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
We have a new solution. ?
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   30  
A 2
7
0
2
25
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
We will calculate the total cost of delivery of the new solution.

S = 210 + Δ32 * 5 = 210 -4 * 5 = 190

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
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 u1 = 0.
A1B1 :   v1 + u1 = 4     v1 = 4 - 0 = 4
A1B2 :   v2 + u1 = 5     v2 = 5 - 0 = 5
A2B2 :   v2 + u2 = 2     u2 = 2 - 5 = -3
A2B3 :   v3 + u2 = 1     v3 = 1 - (-3) = 4
A3B2 :   v2 + u3 = 1     u3 = 1 - 5 = -4
A3B4 :   v4 + u3 = 2     v4 = 2 - (-4) = 6
A4B4 :   v4 + u4 = 0     u4 = 0 - 6 = -6
More info about finding UV
  Supplier   Consumer   U  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
3
6
   u1 = 0  
A 2
7
0
2
25
1
5
   u2 = -3  
A 3
6
5
1
4
15
2
   u3 = -4  
A 4
0
0
0
5
0
   u4 = -6  
  V   v1 = 4 v2 = 5 v3 = 4 v4 = 6
Let's find evaluations of unused routes (cij - cost of delivery). ?
A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 3 - ( 0 + 4 ) = -1
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 6 - ( 0 + 6 ) = 0
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 7 - ( -3 + 4 ) = 6
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 5 - ( -3 + 6 ) = 2
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 6 - ( -4 + 4 ) = 6
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 4 - ( -4 + 4 ) = 4
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -6 + 4 ) = 2
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -6 + 5 ) = 1
A4B3 :   Δ43 = c43 - ( u4 + v3 ) = 0 - ( -6 + 4 ) = 2
There is negative evaluation. Therefore it is possible to reduce the total cost of delivery.
STEP ¹2.
The cell A1B3 (unused route) is selected because its evaluation is negative.
Please, move the mouse cursor to the selected cell A1B3. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A1B3.
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 A1B3.
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
-1
3
6
   30  
A 2
7
0
2
25
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
10 = min { 10, 25 } ?
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10
5
-1
3
6
   30  
A 2
7
0
2
25
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
This transformation will not change the balance.
But this transformation will change the total cost of delivery by:
3 * 10 - 5 * 10 + 2 * 10 - 1 * 10 = ( 3 - 5 + 2 - 1 ) * 10 = -1 * 10
You correctly noted that   -1 * 10 = Δ13 * 10 ?
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
10 - 10
5
+10
-1
3
6
   30  
A 2
7
0 + 10
2
25 - 10
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
We have a new solution. ?
Supplier Consumer   Supply  
B 1 B 2 B 3 B 4
A 1
20
4
5
10
3
6
   30  
A 2
7
10
2
15
1
5
   25  
A 3
6
5
1
4
15
2
   20  
A 4
0
0
0
5
0
   5  
  Customer  
needs   		  20     15     25     20  
We will calculate the total cost of delivery of the new solution.

S = 190 + Δ13 * 10 = 190 -1 * 10 = 180

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
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 u1 = 0.
A1B1 :   v1 + u1 = 4     v1 = 4 - 0 = 4
A1B3 :   v3 + u1 = 3     v3 = 3 - 0 = 3
A2B3 :   v3 + u2 = 1     u2 = 1 - 3 = -2
A2B2 :   v2 + u2 = 2     v2 = 2 - (-2) = 4
A3B2 :   v2 + u3 = 1     u3 = 1 - 4 = -3
A3B4 :   v4 + u3 = 2     v4 = 2 - (-3) = 5
A4B4 :   v4 + u4 = 0     u4 = 0 - 5 = -5
More info about finding UV
  Supplier   Consumer   U  
B 1 B 2 B 3 B 4
A 1
20
4
5
10
3
6
   u1 = 0  
A 2
7
10
2
15
1
5
   u2 = -2  
A 3
6
5
1
4
15
2
   u3 = -3  
A 4
0
0
0
5
0
   u4 = -5  
  V   v1 = 4 v2 = 4 v3 = 3 v4 = 5
Let's find evaluations of unused routes (cij - cost of delivery). ?
A1B2 :   Δ12 = c12 - ( u1 + v2 ) = 5 - ( 0 + 4 ) = 1
A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 6 - ( 0 + 5 ) = 1
A2B1 :   Δ21 = c21 - ( u2 + v1 ) = 7 - ( -2 + 4 ) = 5
A2B4 :   Δ24 = c24 - ( u2 + v4 ) = 5 - ( -2 + 5 ) = 2
A3B1 :   Δ31 = c31 - ( u3 + v1 ) = 6 - ( -3 + 4 ) = 5
A3B3 :   Δ33 = c33 - ( u3 + v3 ) = 4 - ( -3 + 3 ) = 4
A4B1 :   Δ41 = c41 - ( u4 + v1 ) = 0 - ( -5 + 4 ) = 1
A4B2 :   Δ42 = c42 - ( u4 + v2 ) = 0 - ( -5 + 4 ) = 1
A4B3 :   Δ43 = c43 - ( u4 + v3 ) = 0 - ( -5 + 3 ) = 2
There are no negative evaluations. Therefore it is not possible to reduce the total cost of delivery.
Result:

X opt =

Çíàê ñèñòåìû 20 0 10 0Çíàê ñèñòåìû
0 10 15 0
0 5 0 15
0 0 0 5

Smin = 180


Go to the solution of your problem
Back to top





© 2010-2024

If you have any comments, please write to matematika1974@yandex.ru