8 Transport tasks. (Or Hitchcock problems, or T-problems)

A general representation of the transport problem (or the Hitchcock problem, or T-problem) is shown in the figure.

The transport task is shown as a network with m points of departure and n destinations, which are shown as network nodes.

The arcs connecting the network nodes correspond to the routes connecting the points of departure and destination. Two types of data are connected with arc (i, j) connecting point of departure i with destination j: the cost c _{ij of} transportation of a unit of cargo from point i to point j and the amount of cargo carried x _ij . The cargo volume at the point of departure i is equal to a _i , and the cargo at destination point j is b _j . The task is to determine the known values ​​of x _ij , minimizing the total transportation costs and satisfying the constraints on supply and demand.

So: , (one)

under restrictions

(2) (full withdrawal condition)

(3) (condition for full satisfaction of demand)

Thus, the T-problem is an LP problem.

It is usually assumed that the total stock of cargo at the points of departure is equal to its total demand at the points of consumption. In this case, the T-problem is called balanced: . (four)

The T-problem as an LP problem has mn variables and m + n constraints in the form of equalities. It turns out that not all m + n equations of the formulated problem are linearly independent. Indeed, summing all equations (2) and all equations (3), by virtue of condition (4), we get the same thing. Consequently, conditions (2) and (3) are interconnected by one linear dependence and the initial plan of the problem must contain m + n-1 non-zero components.

An example . The car company has three factories: in Los Angeles, Detroit and New Orleans and two warehouses in Denver and Miami. Production volumes for the quarter are respectively: 100, 1500 and 1200 cars. The weekly need for warehouses is 2300 and 1400 cars. Distances are shown in the table:

The transport company estimates its services at 8 cents for transporting one car for one mile. The cost of transportation is as follows (rounded to the dollar):

The task of the LP is formed as follows:

z = 80x ₁₁ + 215x ₁₂ + 100x ₂₁ + 108x ₂₂ + 102x ₃₁ + 68x ₃₂

under restrictions:

x ₁₁ + x ₁₂ = 1000 (L-A)

x ₂₁ + x ₂₂ = 1500 (Det)

x ₃₁ + x ₃₂ = 1200 (N.O.)

x ₁₁ + x ₂₁ + x ₃₁ = 2300 (Den)

x ₁₂ + x ₂₂ + x ₃₂ = 1400 (M)

x _ij ≥0, i = 1,2,3; j = 1,2.

The task is balanced. T-task is recorded in the form of a so-called transport table.

The optimal solution is:

The minimum cost of transportation is 3/3 200 dollars.

When The transport problem is called unbalanced. Any unbalanced task can be made balanced. For this, fictitious points of departure and destination are introduced.

Example. Let the plant in Detroit reduced production to 1,300 cars (instead of 1,500). The total quantity (3500) is less than the total quantity ordered (3700). Some orders of warehouses will not be fulfilled.

Since demand exceeds supply, in order to restore balance, we introduce a fictitious plant (point of departure) producing 3700-3500 = 200 machines. Since a fictitious plant does not exist, we assign a zero cost of transportation from it to the warehouses. In principle, this value can be any positive number. For example, to guarantee all orders for a warehouse in Miami, you can assign a very high shipping cost (fine) from a fictitious plant to Miami. This is a balanced model and its solution.

The solution shows that a fictitious plant will deliver 200 cars to Miami (i.e., from an order of 1,400,200 vehicles will not be delivered)

Suppose a warehouse in Denver has ordered only 1,900 vehicles (supply exceeds demand). You must enter a fictitious destination, absorbing the difference. The cost of transportation may be zero, or a penalty (large), if you need to remove all products from this plant.

400 cars from Detroit are not in demand.

The solution of the transport problem.

In principle, as an LP problem, the T-problem can be solved by the simplex method. But it is solved by a special method, repeating the steps of the simplex method, but using transport tables.

Example. The transport company transports grain from 3 elevators to 4th mills. Task conditions are presented in the table. Shipping costs are in hundreds of dollars.

The sequence of solutions of the T-problem exactly repeats the scheme of the simplex algorithm.

Step 1. Determine the initial basic solution. Go to step 2.

Step 2. On the basis of the optimality condition of the simplex method among the nonbasic variables, we determine what is introduced into the basis . If all nonbasic variables satisfy the optimality condition, the calculations are complete. If not, go to step 3.

Step 3. Using the admissibility condition among the current basis variables, we determine the excluded one . We find a new basic solution. Go to step 2.

Definition of the initial decision.

As we said, there are m + n constraints in the form of equalities. Since the transport model is balanced, one of them should be redundant. Independent constraints m + n-1, the same number should be basic variables in the initial solution.

The special structure of the T-model for constructing the initial solution allows the following three methods to be applied.

1. Northwest corner method.

2. Least Cost Method

3. Vogel Method

Northwest corner method.

Execution starts from the top left cell (northwest corner) of the transport table, that is, with the variable x ₁₁ .

Step 1. The variable x _{11 is} assigned the maximum value allowed by the constraints on supply and demand.

Step 2. A line (or column) is deleted with a fully realized proposal (with satisfied demand). This means that in the crossed out row (column) we will not assign values ​​to the other variables (except the one defined in Step 1). If both supply and demand are satisfied at the same time, only the row or column is deleted.

Step 3. If only one row or only one column is not crossed out, the process is terminated. Otherwise, go to the cell on the right, if the column is crossed out, or to the cell down, if the row is crossed out. Then we return to the first stage. Last example:

Received initial baseline solution.

x ₁₁ = 5; x ₁₂ = 10; x ₂₂ = 5; x ₂₃ = 15; x ₂₃ = 5; x ₃₄ = 10.

Corresponding shipping cost: Doll.

The lowest cost method (minimum element method).

This method finds the best solution because it selects variables with which the minimum costs correspond. The entire table is searching for a cell with a minimum cost. The variable in this cell is assigned the maximum value of supply and demand. (If there are several such variables, the choice is arbitrary). The corresponding column (line) is deleted and the demand-supply is corrected accordingly.

If both demand and supply constraints are met at the same time, either the column or row is deleted. Not crossed out cells are viewed, a new cell is selected with a minimum cost. The process continues until only one row or column not crossed out remains.

1. Cell (1,2) ($ 2). Cross out the second column. The demand supply of the first row of the second column is zero.

2. Further a cell (3,1). Cross out the first column. The restriction of the third line on the proposal was 5

3. Cell (2,3) 15

4. Further , x ₃₄ = 5, x ₂₄ = 10.

x ₁₂ = 15; x ₁₄ = 0; x ₂₃ = 15; x ₂₄ = 10; x ₃₁ = 5; x ₃₄ = 5.

Doll.

This is better than with the NW angle method.

Vogel method.

This is a variation of the minimum cost method, and in general gives the best solution.

Step 1. For each row (column), which corresponds to strictly positive supply (demand), the penalty is calculated by subtracting the lowest cost from the next highest value in the given row (column).

Step 2. Select the row or column with the highest penalty. If there are several, the choice is arbitrary. From the selected row or column, a variable is selected that corresponds to the minimum value, and it is assigned the highest value allowed by the constraints. Adjusted supply demand. The row or column corresponding to the constraint executed is deleted from the table. If both demand and supply constraints are fulfilled simultaneously, only one row or one column is deleted, and the remaining row (column) is assigned zero supply (demand).

Step 3.

a) If only one row or one column with zero demand and supply is not crossed out, the calculations end

b) If only one row (column) with a positive supply (demand) is not crossed out, basic variables are found in this row (column) using the least-cost method and the calculations are terminated.

c) If all unfused rows and columns correspond to zero volumes of supply and demand, the zero basis variables are found using the lowest cost method and the calculations are terminated.

d) In all other cases, go to step 1.

The third line has the largest penalty (10). x ₃₁ (min. cost) 5 Cross out the first column. Recalculated fines.

Now the first line (9) has the greatest penalty.

x ₁₂ (min cost 2) 15. Constraints are performed for both the first row and the second column. Cross out the second column. The resource of the first row is zero. In the next step, the second line will have the largest penalty (20-9 = 11). x ₂₃ (9) 10. Only the fourth column with a positive unsatisfied demand of 15 units is not crossed out. We apply the least cost method to it and we have x ₁₄ = 0, x ₃₄ = 5 and x ₂₄ = 10.

Doll

The same value as in the previous method. But approximation is usually better.