You get a bonus - 1 coin for daily activity. Now you have 1 coin

9 Algorithm for solving the transportation problem

Lecture



The transport problem is solved by the method of potentials. Solve the problem with the transportation of grain. As an initial, we use the solution obtained by the northwest corner method.

one

2

3

four

Sentence

one

ten

five

2

ten

20

eleven

15

2

12

7

five

9

15

20

five

25

3

four

14

sixteen

18

ten

ten

Demand

five

15

15

15

In the method of potentials, each row i and each column j are assigned numbers, called potentials u i and v j . For each basic variable x ij, the potentials must satisfy the equation:

u i + v j = c ij

In our problem there are 7 unknown variables (potentials) and 6 equations corresponding to the basic variables. An arbitrary value is assigned to one of the potentials (u 1 = 0 is usually assumed), and then the values ​​of the remaining potentials are calculated sequentially.

Base variables

Equations with respect to potentials

Decision

x 11

u 1 + v 1 = 10

u 1 = 0 v 1 = 10

x 12

u 1 + v 2 = 2

u 1 = 0 v 2 = 2

x 22

u 2 + v 2 = 7

v 2 = 2 u 2 = 5

x 23

u 2 + v 3 = 9

u 2 = 5 v 3 = 4

x 24

u 2 + v 4 = 20

u 2 = 5 v 4 = 15

x 34

u 3 + v 4 = 18

v 4 = 15 u 3 = 3

So, we have: u 1 = 0, u 2 = 5, u 3 = 3

v 1 = 10, v 2 = 2, v 3 = 4, v 4 = 15.

Further, for each nonbasic variable, the quantities u i + v j -c ij are calculated.

Nonbasic variables

Values ​​u i + v j -c ij

x 13

u 1 + v 3 -c 13 = 0 + 4-20 = -16

x 14

u 1 + v 4 -c 14 = 0 + 15-11 = 4

x 21

u 2 + v 1 -c 21 = 5 + 10-12 = 3

x 31

u 3 + v 1 -c 31 = 3 + 10-4 = 9

x 32

u 3 + v 2 -c 32 = 3 + 2-14 = -9

x 33

u 3 + v 3 -c 33 = 3 + 4-16 = -9

Since the minimum cost of transportation is sought, the variable that has the largest positive coefficient will be entered into the basis.

In this case, it will be x 31 (9).

v 1 = 10

v 2 = 2

v 3 = 4

v 4 = 15

Sentence

u 1 = 0

ten

five

2

ten

20

-sixteen

eleven

four .

15

u 2 = 5

12

3

7

five

9

15

20

five

25

u 3 = 3

four

9 .

14

-9 .

sixteen

-9 .

18

ten

ten

Demand

five

15

15

15

Calculations begin with the assignment u 1 = 0. The v-potentials are then calculated for all columns that have basic variables in the first row. Further, on the basis of the equation of potentials corresponding to x 22 , u 2 is determined. Knowing u 2, we calculate v 3 and v 4 , and finally u 3 . The potentials are determined, then the quantities u i + v j -c ij are calculated for each nonbasic variable x ij .

We determined the variable x 31 introduced into the basis. We must find the excluded.

Choosing x 31 as the input variable, we want traffic on routes 3 - 1 to reduce the total cost of transportation. How much cargo can be transported on this route? Denote by 9 Algorithm for solving the transportation problem the amount of cargo transported along the route (3.1), that is, x 31 = 9 Algorithm for solving the transportation problem . 9 Algorithm for solving the transportation problem determine the conditions:

1. Restrictions on supply and demand must be met.

2. No route should be shipped with a negative volume.

Construct a loop that starts and ends in a cell (3.1). The cycle consists of consecutive horizontal and vertical segments connecting the cells corresponding to the current basis variables.

9 Algorithm for solving the transportation problem

Find the value 9 Algorithm for solving the transportation problem . In order to meet the supply-demand constraints, it is necessary to take and add alternately 9 Algorithm for solving the transportation problem to the values ​​of variables located in the corner cells of the cycle. New values ​​of the basic variables will remain non-negative if the inequalities hold:

x 11 = 5- 9 Algorithm for solving the transportation problem ≥0

x 22 = 5- 9 Algorithm for solving the transportation problem ≥0

x 34 = 10- 9 Algorithm for solving the transportation problem ≥0

Hence it is clear that the greatest value 9 Algorithm for solving the transportation problem = 5. x 11 and x 22 then vanish. You can exclude both x 11 and and x 22 . Exclude x 11 .

So x 31 = 5. Adjust the base variables in the corner cells.

9 Algorithm for solving the transportation problem

The cost of transporting a unit of cargo decreased by u 3 + v 1 -c 31 = 9 dollars, the total cost by 95 = 45 dollars.

Repeat the calculation of potentials. The new variable entered will be x 14 . From the loop x 14 = 10, the excluded variable x 24 .

New solution:

9 Algorithm for solving the transportation problem

will be optimal, since u i + v j -c ij is negative for all nonbasic variables.

In terms of the original problem, the solution makes sense:

From the elevator

To the mill

Number of grain trucks

one

2

five

one

four

ten

2

2

ten

2

3

15

3

one

five

3

four

five

The total cost of transportation = 435 dollars.

The dual problem to the T-problem.

According to the general rule for the construction of dual tasks, the dual task for the transport one will be written as follows:

under restrictions:

u i + v i ≤c ij ,,

The meaning of dual variables:

u i ( 9 Algorithm for solving the transportation problem ) - assessment of the unit of inventory (the potential of the i-th supplier);

v j ( 9 Algorithm for solving the transportation problem ) - assessment of the unit of demand (potential of the j-th supplier).

Assignment task

In practice, it is often necessary to solve the following tasks: distribute workers to workplaces so that the product manufacturing time is minimal, place sensors on objects so that information about the work of objects is maximum, distribute aircraft crews on flights so that LA downtime is minimal and etc.

The peculiarity of this task is that each resource (worker, sensor, crew) is used exactly once and one object is assigned to each object.

The solution of the problem is represented by a two-dimensional array or matrix x ij , i = 9 Algorithm for solving the transportation problem j = 9 Algorithm for solving the transportation problem where m is the number of objects or resources. Desired variable

1, if the i-th resource is assigned to the j-th object,

x ij = 9 Algorithm for solving the transportation problem

0 otherwise.

The costs associated with assigning the i-th resource to the j-th object are denoted by the elements of the cost matrix c ij . For any undesirable assignment, the corresponding value is assumed to be equal to a sufficiently large number M. The admissible solution of the problem is called assignment . In total, for a m × m matrix, there is m! making. A valid solution is built by selecting exactly one element in each row of the matrix x ij and exactly one element in each of its columns.

Thus, the assignment problem is formulated as follows:

Z = 9 Algorithm for solving the transportation problem

under restrictions:

a) each resource is used exactly once: 9 Algorithm for solving the transportation problem for all i;

b) exactly one resource is assigned to each object: 9 Algorithm for solving the transportation problem for all j.

Obviously, the assignment problem is a special case of the transport problem with single values ​​of the parameters a i and b i . To solve it, you can use any LP algorithm or potential method. But given its specificity, the so-called Hungarian method is used to solve it. It was first proposed by the Hungarian mathematician Egerwari in 1931. For a long time his work remained unknown. In 1953 The mathematician G. Kun translated the work of Egerwari into English, developed the ideas of Egerwari and called the method Hungarian. The Hungarian method was developed for manual calculations and is now of purely historical interest.

Example 1 Place 3 sensors in 3 objects in such a way that the cost of such placement is minimal. The cost matrix is:

one

2

3

one

15

ten

9

2

9

15

ten

3

ten

12

eight

Algorithm of the Hungarian method.

Stage 1. In the initial cost matrix, we define the minimum cost in each row and subtract it from the other elements of the row.

Stage 2. In the matrix obtained in the first stage, we find the minimum cost in each column and subtract it from the other elements of the column.

Stage 3. The optimal purpose will correspond to zero elements obtained in step 2.

Let p i and q i be the minimum values ​​in row i and column j, respectively.

15

ten

9

9

15

ten

ten

12

eight

p 1 = 9, p 2 = 9, p 3 = 8

Subtract p i from the elements of the corresponding rows.

6

2

0

0

6

2

2

four

0

q 1 = 0, q 2 = 2, q 3 = 0.

Perform step 2.

6

0

0

0

four

one

2

2

0

Underlined zeros define the optimal solution. The cost of placement is equal to 9 + 10 + 8 = 27 USD Note that this amount is always equal to

(p 1 + p 2 + p 3 ) + (q 1 + q 2 + q 3 ).

Sometimes you can not immediately find a valid solution and need to resort to additional actions.

Example2.

one

2

3

four

one

one

four

6

3

2

9

7

ten

9

3

four

five

eleven

7

four

eight

7

eight

five

p 1 = 1, p 2 = 7, p 3 = 4, p 4 = 5

one

2

3

four

one

0

3

five

2

2

2

0

3

2

3

0

one

7

3

four

3

2

3

0

q 1 = 0, q 2 = 0, q 3 = 3, q 4 = 0

one

2

3

four

one

0

3

2

2

2

2

0

0

2

3

0

one

four

3

four

3

2

0

0

It is impossible to assign 1 object for each sensor. It is necessary to add another step to the procedure of the Hungarian method.

Stage 2.1. If after completing the first and second stages no valid solution is obtained, perform the following actions:

1) In the last matrix hold the minimum number of horizontal and vertical straight lines in order to cross out all zero elements in the matrix.

2) Find the smallest not crossed out element and subtract it from the remaining not crossed out elements, and add to the elements standing at the intersection of straight lines.

3) If the new distribution does not allow finding a feasible solution, repeat step 2.1. Otherwise, go to step 3.

one

2

3

four

one

0

3

2

2

2

2

0

0

2

3

0

one

four

3

four

3

2

0

0

Underline the smallest element.

one

2

3

four

one

0

2

one

one

2

3

0

0

2

3

0

0

3

2

four

four

2

0

0

The optimal solution is underlined.

Z = 1 + 10 + 5 + 5 = 21 USD

The justification of the Hungarian method is based on the fact that if a number γ i (= - p i ) is added to each element of the i-th row, and a real number δ j (= - q j ) is added to each element of the j-th column, then minimization of the function 9 Algorithm for solving the transportation problem equivalent to minimizing the function 9 Algorithm for solving the transportation problem where d ij = c ij + γ i + δ i


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Mathematical methods of research operations. The theory of games and schedules.

Terms: Mathematical methods of research operations. The theory of games and schedules.