Файл: М.А. Тынкевич Потоки в сетях и транспортная задача по критерию времени.pdf

6

определяющую

величину

потока

в найденном пути;

поочередно добавляем

и вычитаем Θ

из значений X i j в цепочке

(

i

0

j* ) ( i

0

j

1

) ( i

1

j

1

) ( i

1

j

2

) ( i

2

j

2

) ...( i

k-1

j

k

) ( i

k

j

k

)

где

=

=

= 0 )

i0

= l * , j1

mi

,i1

l j

1

, j2

= mi

, i2

= l j ,.. ,ik

= l j

k

(mi

j

0

1

2

k

и вновь продолжаем процесс отмечаний.

Если не удастся отметить

ни одного из

ненасыщенных столбцов,

то пере-

страиваем сеть.

от минимального из значений tij, а от максимального

среди

минимальных

времен в строках и столбцах матрицы T .

Пример1. Пусть задача определена следующими данными.

Минимальные значения ti j в строках равны

T =

1

13

17

18

18

1, 2, 1 и в столбцах 1 , 1 , 4 , 10.

2

18

10

10

10

Выбираем t*=10, строим вспомогательную

16

1

4

12

12

сеть по tij ≤

t* и отыскиваем в ней начальное

11

9

13

7

B\A

приближение для потока методом северо-

западного угла.

0

Так как

найденный поток

X

не является

11

18

o

0

10

0

10

насыщающим, пытаемся

его

улучшить с ис-

X =

пользованием процесса

отмечаний

9

3

12

µ 1 = 0, υ 1 = 18 - 11 = 7;

λ

1 =1, ω 1 = υ 1 = 7.

11

9

13

7

B\A

Дальнейшее

отмечание

невозможно

и

приходится расширить сеть,

взяв t*=12 (появится возможность перевозки на

маршруте 1 – 4 , поток Xo′).

11

18

Очевидно, что это расширение ничего ново-

Xo′=

0

10

0

10

го не даст; берем t*=13 , поток

X

′′).

o

9

3

0

12

Отталкиваясь от ранее выбранного потока,

11

9

13

7

B\A

пытаемся его улучшить.

Продолжая процесс отмечаний, имеем

λ 2 = 1 , ω 2 = υ 1 = 7 ;

11

0

18

µ 3

= 2 ,

υ 3 = min(X3 2 , ω 2) = 7 ;

Xo′′=

0

10

0

10

λ 2 = 3 , ω 4 = υ 3 = 7 .

9 3

0

12

Так как

отмечен ненасыщенный столбец,

11

9

13

7

B\A

отыскиваем

цепочку [ X34

X32

X12 ] и

кор-

ректируем ее на

величину

Θ

= min (ω 4

,B4 )

11

7

18

= 7.

X1 =

0

2

10

0

10

В итоге

мы

получаем

насыщающий

по-

3

7

12

ток и можем утверждать, что

минимальное

11

9

13

7

B\A

время транспортировки составляет 13 единиц.

10

13

17

18

10

25

и столбцах

равны 10. Соответственно

T = 12

18

10

10

10

35

выбираем t*=10, строим вспомога-

16

10

14

12

11

15

тельную сеть

и отыскиваем

в ней на-

17

10

10

13

19

25

чальное приближение X0.

X0 не

20

20

13

7

40

B\A

Так как найденный поток

яв-

ляется

насыщающим, пытаемся

его

улучшить

с использованием процесса отмечаний

µ 4 = 0,

υ 4= 25 - 5 = 20;

Xo =

20

5

25

13 7

15

35

λ 2 =4, ω 2 =υ 4 = 20; λ 3 =4, ω 3 =υ 4 = 20;

15

15

µ 3 = 2,

υ 3=min( 20,15) = 15;

5

0

25

µ 2 = 3,

υ 2=min( 20,13) = 13;

20

20

13

7 40

B\A

λ 5 =2, ω 5 =υ 2 = 13.

цепочку [X43

X23

X25 ] и поочередно увеличиваем и уменьшаем элементы це-

почки на θ , получая поток X1.

20

5

25

X1 =

Выполняя процесс отмечаний, имеем

0

7

28

35

µ 4 = 0,

υ 4= 25 – 5-13 = 7;

15

15

λ 2 =4, ω 2 =υ

4 = 7; λ 3 =4, ω 3 =υ 4 = 7;

5

13

25

µ 3 = 2,

υ 3=min( 7,15) = 7.

20

20

13

7

40

B\A

Дальнейшее отмечание невозможно и

маршруте 3 – 5 , поток X2).

Продолжая процесс отмечаний, начатый

X2 =

20

0

7

5

25

выше, получаем возможность отметить

28

35

ненасыщенный столбец

15

0

15

λ 5 =3, ω

5 =υ

3 = 7.

5

13

25

Здесь

θ =min

(ω 5

=7,

40-5-28)=7,

20

20

13

7

40

B\A

строим цепочку [X42

X32

X35 ] и в ре-

зультате аналогичной корректуры полу-

20

5

25

3

X3 =

0

7

28

35

чаем насыщающий поток X .

Соответственно можем

утверждать,

8

7

15

что минимальное

время транспорти-

12

13

25

ровки составляет 11 единиц.

20

20

13

7

40

B\A

Оба приведенных

примера показы-

1.

B=

15

15

20

10

A=

2.

B=

7

7

7

7

7

A=

3

7

9

4

11

8

3

2

6

5

15

T=

1

5

10

5

29

T=

4

3

5

8

2

5

4

1

2

8

10

5

6

3

8

2

7

7

3

6

5

10

4

4

7

5

4

8

3.

B=

A=

4.

B=

A=

30

45

70

90

12

8

5

6

1

2

3

7

60

5

8

3

4

11

T=

9 1

4

1

80

T=

6

2

1

8

7

6

3

1

7

40

0

9

10

5

4

2

1

5

4

90

5

6

4

7

3

5.

B=

A=

6.

B=

A=

12

18

14

20

20

20

15

15

5

7

6

4

10

1

3

6

4

15

T=

2

1

3

8

14

T=

3

4

4

3

20

6

8

6

4

16

6

5

2

2

15

11

6

7

8

18

9

8

6

7

20

7.

B=

A=

8.

B=

11

12

3

8

15

A=

9

10

7

13

8

18

17

16

15

10

5

6

4

3

2

17

5

8

4

3

2

15

T=

1

8

3

5

6

8

T=

1

3

7

8

2

10

4

3

7

8

6

5

6

4

5

1

7

5

3

2

1

8

5

14

8

3

4

9

5

20

9.

B=

A=

10.

B=

A=

5

7

8

9

4

9

10

11

12

7

3

4

5

6

7

15

8

1

9

3

6

5

T=

8

9

10

1

2

6

T=

4

5

1

7

7

6

3

2

7

4

5

7

3

6

2

4

3

7

3

4

2

1

6

8

2

7

8

5

1

8

11.

B=

A=

12.

B=

A=

15

28

35

10

7

14

12

10

9

3

10

12

21

1

4

5

8

8

T=

1

7

13

15

28

T=

7

8

3

5

16

7

5

3

4

35

3

0

4

6

14

8

2

9

1

10

2

4

9

1

12

9

13.

B=

A=

14.

B=

A=

10

30

50

10

10

10

15

5

10

10

5

4

9

11

11

5

8

6

3

4

1

12

T=

7

1

8

3

40

T=

8 7

6

3

4

2

18

2

10

3

4

20

1

8

3

7

2

9

10

5

6

5

7

9

2

7

4

6

3

8

10

15.

B=

A=

16.

B=

A=

5

8

11

12

18

14

16

20

30

20

8

9

0

7

1

3

3

4

5

6

7

13

T=

5

4

3

1

5

4

T=

2

8

9

6

11

23

6

7

10

2

8

17

3

4

4

5

1

33

3

6

6

8

4

20

1

2

3

4

7

43

17.

B=

A=

18.

B=

A=

7

3

8

9

10

16

26

30

10

1

0

7

4

5

11

8

5

6

7

17

T=

8

9

3

1

2

10

T=

3

4

2

1

27

5

6

3

7

9

20

9

10

11

2

37

5

6

3

4

7

1

8

3

4

10

19.

B=

A=

20.

B=

A=

5

15

10

20

27

31

45

19

3

4

1

2

10

5

7

6

8

45

T=

2

1

7

5

10

T=

3

4

5

7

17

6

2

4

1

15

2

1

9

11

13

5

6

3

4

15

15

13

3

1

28

21.

B=

A=

22.

B=

A=

20

20

30

60

13

15

17

19

8

3

5

1

18

2

7

4

8

14

T=

3

4

8

5

28

T=

5

8

3

1

16

4

1

6

10

36

7

12

4

9

18

12

7

9

2

48

4

5

10

7

20

23.

B=

A=

24.

B=

A=

10

11

12

18

8

10

12

12

5

3

4

5

6

11

5

4

3

2

1

11

T=

7

8

9

9

12

T=

1

2

3

4

5

18

1

2

3

4

13

7

8

3

4

5

13

5

6

7

8

14

8

9

6

11

3

14

25.

B=

A=

26.

B=

A=

3

7

9

2

15

15

20

40

2

5

2

2

4

5

8

3

4

20

T=

4 3

7

5

5

T=

1

2

5

6

10

6

2

1

8

6

3

4

7

8

30

3

7

3

9

8

8

9

5

3

10