# Service for Solving Linear Programming Problems

and other interesting typical problems
Русский

## Example №1. Transportation Problem by the Least Cost Method (Balanced problem)

This solution has been made using 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 5 3 1 10 A 2 3 2 4 20 A 3 4 1 2 30 Customer   needs 15 20 25
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.

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.
First of all we will use the routes with the lowest cost of delivery.
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 1 10 A 2 3 2 4 20 A 3 4 ? 1 2 30 Customer   needs 15 20 25
20 = min { 20, 30 }
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 ? 1 10 A 2 3 2 4 20 A 3 4 20 1 2 30   10 Customer   needs 15 20 No 25
10 = min { 25, 10 }
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10   No A 2 3 2 4 20 A 3 4 20 1 ? 2 30   10 Customer   needs 15 20 No 25 15
10 = min { 15, 10 }
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10   No A 2 ? 3 2 4 20 A 3 4 20 1 10 2 30   10   No Customer   needs 15 20 No 25 15 5
15 = min { 15, 20 }
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10   No A 2 15 3 2 ? 4 20   5 A 3 4 20 1 10 2 30   10   No Customer   needs 15 No 20 No 25 15 5
5 = min { 5, 5 }
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10   No A 2 15 3 2 5 4 20   5   No A 3 4 20 1 10 2 30   10   No Customer   needs 15 No 20 No 25 15 5 No
Let's calculate the total cost of delivery for the initial solution.

## 10*1 + 15*3 + 5*4 + 20*1 + 10*2 = 115

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 u2 = 0.
 A2B1 : v1 + u2 = 3 v1 = 3 - 0 = 3 A2B3 : v3 + u2 = 4 v3 = 4 - 0 = 4 A3B3 : v3 + u3 = 2 u3 = 2 - 4 = -2 A1B3 : v3 + u1 = 1 u1 = 1 - 4 = -3 A3B2 : v2 + u3 = 1 v2 = 1 - (-2) = 3
 Supplier Consumer U B 1 B 2 B 3 A 1 5 3 10 1 u1 = -3 A 2 15 3 2 5 4 u2 = 0 A 3 4 20 1 10 2 u3 = -2 V v1 = 3 v2 = 3 v3 = 4
Let's find evaluations of unused routes (cij - cost of delivery). ?
 A1B1 : Δ11 = c11 - ( u1 + v1 ) = 5 - ( -3 + 3 ) = 5 A1B2 : Δ12 = c12 - ( u1 + v2 ) = 3 - ( -3 + 3 ) = 3 A2B2 : Δ22 = c22 - ( u2 + v2 ) = 2 - ( 0 + 3 ) = -1 A3B1 : Δ31 = c31 - ( u3 + v1 ) = 4 - ( -2 + 3 ) = 3
There is negative evaluation. Therefore it is possible to reduce the total cost of delivery.
STEP №1.
The cell A2B2 (unused route) is selected because its evaluation is negative.
Please, move the mouse cursor to the selected cell A2B2. Only horizontal and vertical cursor movements can be used.
Connect the filled cells with a continuous line so that you return to the cell A2B2.
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 A2B2.
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10 A 2 15 3 -1 2 5 4 20 A 3 4 20 1 10 2 30 Customer   needs 15 20 25
5 = min { 5, 20 } ?
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10 A 2 15 3 -1 2 5 4 20 A 3 4 20 1 10 2 30 Customer   needs 15 20 25
This transformation will not change the balance.
But this transformation will change the total cost of delivery by:
2 * 5 - 4 * 5 + 2 * 5 - 1 * 5 = ( 2 - 4 + 2 - 1 ) * 5 = -1 * 5
You correctly noted that   -1 * 5 = Δ22 * 5 ?
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10 A 2 15 3 +5 -1 2 5 - 5 4 20 A 3 4 20 - 5 1 10 + 5 2 30 Customer   needs 15 20 25
We have a new solution. ?
 Supplier Consumer Supply B 1 B 2 B 3 A 1 5 3 10 1 10 A 2 15 3 5 2 4 20 A 3 4 15 1 15 2 30 Customer   needs 15 20 25
We will calculate the total cost of delivery of the new solution.

## S = 115 + Δ22 * 5 = 115 -1 * 5 = 110

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 u2 = 0.
 A2B1 : v1 + u2 = 3 v1 = 3 - 0 = 3 A2B2 : v2 + u2 = 2 v2 = 2 - 0 = 2 A3B2 : v2 + u3 = 1 u3 = 1 - 2 = -1 A3B3 : v3 + u3 = 2 v3 = 2 - (-1) = 3 A1B3 : v3 + u1 = 1 u1 = 1 - 3 = -2
 Supplier Consumer U B 1 B 2 B 3 A 1 5 3 10 1 u1 = -2 A 2 15 3 5 2 4 u2 = 0 A 3 4 15 1 15 2 u3 = -1 V v1 = 3 v2 = 2 v3 = 3
Let's find evaluations of unused routes (cij - cost of delivery). ?
 A1B1 : Δ11 = c11 - ( u1 + v1 ) = 5 - ( -2 + 3 ) = 4 A1B2 : Δ12 = c12 - ( u1 + v2 ) = 3 - ( -2 + 2 ) = 3 A2B3 : Δ23 = c23 - ( u2 + v3 ) = 4 - ( 0 + 3 ) = 1 A3B1 : Δ31 = c31 - ( u3 + v1 ) = 4 - ( -1 + 3 ) = 2
There are no negative evaluations. Therefore it is not possible to reduce the total cost of delivery.
Result:

## X opt = 0 0 10 15 5 0
0 15 15