Transportation problem
Transportation problem is to find the optimal transportation plan certain volumes of resources from suppliers to consumers, taking into account the cost of transportation. The plan is a table (matrix), whose rows and columns correspond to the suppliers and consumers, the cells are placed in cargo volume.
Example of the transportation problem:
Consumer 1, need 20 kg |
Consumer 2, need 30 kg |
Consumer 3, need 10 kg | |
---|---|---|---|
Supplier 1, supply 25 kg |
$3 per kg | $5 per kg | $7 per kg |
Supplier 2, supply 35 kg |
$3 per kg | $2 per kg | $5 per kg |
For the first time this problem mathematically studied the Soviet mathematician A. N. Tolstoy. In 1930 he published his work on finding the minimum total mileage in rail transportation, which used the redistributive cycles. The main contribution to the development of the mathematical apparatus of the transport problem introduced Soviet economist L. V. Kantorovich during the Great Patriotic War (published in 1939 and 1942). The way to solve the transportation problem by the potential method was it published in conjunction with M. K. Gavurin in 1949.
The program is to solve the classical transport problem using the method of potentials (with redistributive cycle) with the preparation of the initial transportation plan by the north-west corner of the features to be implemented in this task. The input is the number of suppliers and customers, inventory levels, needs and cost matrix transport cargo. The output of the program is the optimal plan. If necessary, enter a fictitious vendor or customer.
The solution for the above example would be the plan:
Consumer 1 | Consumer 2 | Consumer 3 | |
---|---|---|---|
Supplier 1 | 20 kg | - | 5 kg |
Supplier 2 | - | 30 kg | 5 kg |