Example ¹4. Transportation Problem by North-West Corner Method (Balanced problem)This solution is done by the program 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 ¹5. Transportation problem by the North-West corner method (Unbalanced problem. Fictitious supplier) Example ¹6. Transportation problem by the North-West corner method (Unbalanced problem. Fictitious consumer) 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.
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: 10 + 20 + 30 = 60 units. The total needs of consumers: 15 + 20 + 25 = 60 units. 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.
10 = min { 15, 10 }
5 = min { 5, 20 }
15 = min { 20, 15 }
5 = min { 5, 30 }
25 = min { 25, 25 }
Let's calculate the total cost of delivery for the initial solution. 10*5 + 5*3 + 15*2 + 5*1 + 25*2 = 150Is 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 u_{2} = 0.
There are negative evaluations. Therefore it is possible to reduce the total cost of delivery. STEP ¹1.
The cell A_{1}B_{3} (unused route) is selected because its evaluation is negative.
Move the mouse cursor to the selected cell A_{1}B_{3}. Using the horizontal and vertical cursor movements, connect the filled cells with a continuous line so that you return to the cell A_{1}B_{3}. 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 A_{1}B_{3}.
10 = min { 10, 15, 25 }
This transformation will not change the balance.
But this transformation will change the total cost of delivery by: 1 * 10 - 5 * 10 + 3 * 10 - 2 * 10 + 1 * 10 - 2 * 10 = ( 1 - 5 + 3 - 2 + 1 - 2 ) * 10 = -4 * 10 You correctly noticed that -4 * 10 = Δ_{13} * 10
We got a new solution.
Let's calculate the total cost of delivery for the new solution. S = 150 + Δ_{13} * 10 = 150 -4 * 10 = 110Is 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 u_{2} = 0.
There are not any negative evaluations. Therefore it is not possible to reduce the total cost of delivery. Result:
S_{min} = 110© 2010-2020 If you have comments, please write to matematika1974@yandex.ru |