logo
Технические средства автоматизизированных систем управления в строительстве

Транспортная задача

Исходные данные:

а1=20; а2=25; а3=40; а4=35; а5=50; а6=30; а7=30; а8=52;

b1=40; b2=55; b3=45; b4=30; b5=35; b6=35; b7=42;

Таблица 1 - Исходные данные.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

5

9

6

12

7

2

13

2

25

12

13

3

9

8

10

11

3

40

8

9

10

13

19

7

9

4

35

9

4

7

8

6

12

10

5

50

10

11

9

12

15

5

2

6

30

7

16

1

5

9

17

10

7

30

17

14

9

7

11

1

4

?=

230

Задача относится к типу «транспортных». Следует найти такую совокупность перевозок, которая полностью обеспечивает потребности пунктов назначения при вывозе всего продукта из пунктов отправления.

Для определения исходных данных следует заполнить матрицу. Обозначение аi соответствует запасам продукта на пункте отправления i, а обозначение bi потребности в продукте на пункте получения J.

Перенумерованными клетками матрицы моделируются пути между пунктами отправления i и пунктами получения J.

Для решения задачи необходимо выполнения условия:

Данное условие не выполняется , следовательно необходимо к столбцу I добавить недостающий объем запаса продукции.

Таблица 2 - Исходная матрица.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

+5

9

6

12

7

+2

13

2

25

12

13

+3

9

8

10

11

3

40

8

9

10

13

19

7

9

4

35

9

++4

7

8

+6

12

10

5

50

10

11

9

12

15

5

++2

6

30

7

16

++1

+5

9

17

10

7

30

17

14

9

7

11

++1

4

8

52

13

++4

19

8

7

15

12

?=

282

Составим первоначальный базисный план.

Матрицу решаем методом двойного предпочтения.

Таблица 3 - Базисный план.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

+5

(15)

9

6

12

7

+2

(5)

13

0

2

25

12

13

+3

(15)

9

(7)

8

(3)

10

11

1

3

40

8

(25)

9

10

13

(15)

19

7

9

-3

4

35

9

++4

(35)

7

8

+6

12

10

2

5

50

10

11

9

12

(8)

15

5

++2

(42)

-2

6

30

7

16

++1

(30)

+5

9

17

10

3

7

30

17

14

9

7

11

++1

(30)

4

1

8

52

13

++4

(20)

19

8

7

(32)

15

12

2

?=

282

5

6

4

10

9

2

0

Проверяем количество заполненных клеток, которое должно быть равно m+n-1, т.е. суммарному количеству строк и столбцов без единицы.

8+7-1=14, количество заполненных клеток N=14, условие выполняется.

Целевая функция плана:

Для улучшения первоначального базисного плана применяется метод потенциалов. Потенциалами называются такие численные характеристики строк Ui и столбцов Vj, при которых соблюдается условие оптимальности плана. Математически это условие записывается так:

(условие для занятых клеток);

(условие для свободных клеток);

,

Подбор потенциалов начинаем с первой строки. Принимаем U1=0.

U1=0

V1=0+5=5

U2=10-9=1

V2=2+4=6

U3=5-8=-3

V3=1+3=4

U4=6-4=2

V4=-3+13=10

U5=1+8=9

V5=10-12=-2

U6=4-1=3

V6=0+2=2

U7=2-1=1

V7=9-7=2

U8=9-7=2

Далее производим проверку условия для свободных клеток по формуле:

Таким образом, проверка показала, что первоначальный план не является оптимальным, так как условия для отдельных свободных клеток не выполняются.

Оптимизируем план.

Итерация 1.

Для этого от клетки ?6,4 строим контур перераспределения.

Получаем: до перераспределения условные затраты на перевозку

15*3+7*9+30*1=138;

После перераспределения условные затраты на перевозку составили

22*3+23*1+7*5=124.

Таблица 4 - Оптимизированный базисный план.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

+5

(15)

9

6

12

7

+2

(5)

13

2

25

12

13

+3

(22)

9

8

(3)

10

11

3

40

8

(25)

9

10

13

(15)

19

7

9

4

35

9

++4

(35)

7

8

+6

12

10

5

50

10

11

9

12

(8)

15

5

++2

(42)

6

30

7

16

++1

(23)

+5

(7)

9

17

10

7

30

17

14

9

7

11

++1

(30)

4

8

52

13

++4

(20)

19

8

7

(32)

15

12

?=

282

Далее от клетки ?1,5 строим контур перераспределения

Получаем: до перераспределения условные затраты на перевозку

15*5+3*8+22*3+23*1+7*5+15*13+25*8=618;

После перераспределения условные затраты на перевозку составили

12*5+3*7+25*3+20*1+10*5+12*13+28*8=606.

Таблица 5 - Оптимизированный базисный план.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

+5

(12)

9

6

12

7

(3)

+2

(5)

13

2

25

12

13

+3

(25)

9

8

10

11

3

40

8

(28)

9

10

13

(12)

19

7

9

4

35

9

++4

(35)

7

8

+6

12

10

5

50

10

11

9

12

(8)

15

5

++2

(42)

6

30

7

16

++1

(20)

+5

(10)

9

17

10

7

30

17

14

9

7

11

++1

(30)

4

8

52

13

++4

(20)

19

8

7

(32)

15

12

?=

282

Далее от клетки ?7,4 строим контур перераспределения

Получаем: до перераспределения условные затраты на перевозку

12*5+5*17+30*1+12*13+28*8=555;

После перераспределения условные затраты на перевозку составили

17*2+18*1+12*7+40*8=456.

Таблица 6 - Оптимизированный базисный план.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

+5

9

6

12

7

(3)

+2

(17)

13

2

25

12

13

+3

(25)

9

8

10

11

3

40

8

(40)

9

10

13

19

7

9

4

35

9

++4

(35)

7

8

+6

12

10

5

50

10

11

9

12

(8)

15

5

++2

(42)

6

30

7

16

++1

(20)

+5

(10)

9

17

10

7

30

17

14

9

7

(12)

11

++1

(18)

4

8

52

13

++4

(20)

19

8

7

(32)

15

12

?=

282

Проверяем количество заполненных клеток для оптимизированного плана, которое должно быть равно m+n-1, т.е. суммарному количеству строк и столбцов без единицы.

8+7-1=14, количество заполненных клеток N=13, условие не выполняется, поэтому вводим фиктивную перевозку ?1,1 равную 0.

Таблица 6 - Оптимизированный базисный план.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

+5

(0)

9

6

12

7

(3)

+2

(17)

13

0

2

25

12

13

+3

(25)

9

8

10

11

-1

3

40

8

(40)

9

10

13

19

7

9

-3

4

35

9

++4

(35)

7

8

+6

12

10

0

5

50

10

11

9

12

(8)

15

5

++2

(42)

-4

6

30

7

16

++1

(20)

+5

(10)

9

17

10

3

7

30

17

14

9

7

(12)

11

++1

(18)

4

1

8

52

13

++4

(20)

19

8

7

(32)

15

12

0

?=

282

5

4

2

8

7

2

-2

Целевая функция плана:

Проверяем условия оптимальности плана.

Подбор потенциалов начинаем с первой строки. Принимаем U1=0.

U1=0

V1=0+5=5

U2=2-3=-1

V2=1+4=5

U3=5-8=-3

V3=3-1=2

U4=4-4

V4=1+7=8

U5=8-12=-4

V5=0+7=7

U6=8-5=3

V6=0+2=2

U7=2-1=1

V7=-4+2=-2

U8=7-7=2

Далее производим проверку условия для свободных клеток по формуле:

Таким образом, проверка показала, что план не является оптимальным, так как условия для отдельных свободных клеток не выполняются.

Итерация 2.

Для клетки ?5,6 строим контур перераспределения.

Получаем: до перераспределения условные затраты на перевозку

8*12+12*7+18*1=198;

После перераспределения условные затраты на перевозку составили

8*5+20*7+10*1=190.

Таблица 7 - Оптимизированный базисный план.

J

1

2

3

4

5

6

7

?=

i

40

55

45

30

35

35

42

282

1

20

+5

(0)

9

6

12

7

(3)

+2

(17)

13

2

25

12

13

+3

(25)

9

8

10

11

3

40

8

(40)

9

10

13

19

7

9

4

35

9

++4

(35)

7

8

+6

12

10

5

50

10

11

9

12

15

5

(8)

++2

(42)

6

30

7

16

++1

(20)

+5

(10)

9

17

10

7

30

17

14

9

7

(20)

11

++1

(10)

4

8

52

13

++4

(20)

19

8

7

(32)

15

12

?=

282

Для клетки ?4,5 строим контур перераспределения.

Получаем: до перераспределения условные затраты на перевозку

35*4+20*4+32*7=444;

После перераспределения условные затраты на перевозку составили

3*5+32*6+52*4=415.

Таблица 8 - Оптимизированный базисный план.

J

1

2

3

4

5

6

7

U?=

i

40

55

45

30

35

35

42

282

1

20

+5

(0)

9

6

12

7

(3)

+2

(17)

13

0

2

25

12

13

+3

(25)

9

8

10

11

1

3

40

8

(40)

9

10

13

19

7

9

-3

4

35

9

++4

(3)

7

8

+6

(32)

12

10

1

5

50

10

11

9

12

15

5

(8)

++2

(42)

-3

6

30

7

16

++1

(20)

+5

(10)

9

17

10

3

7

30

17

14

9

7

(20)

11

++1

(10)

4

1

8

52

13

++4

(52)

19

8

7

15

12

1

V?=

282

5

5

4

8

7

2

-1

Проверяем условия оптимальности плана.

Подбор потенциалов начинаем с первой строки. Принимаем U1=0.

U1=0

V1=0+5=5

U2=4-3=1

V2=1+4=5

U3=5-8=-3

V3=3+1=4

U4=7-6=1

V4=1+7=8

U5=2-5=-3

V5=0+7=7

U6=8-5=3

V6=0+2=2

U7=2-1=1

V7=-3+2=-1

U8=5-4=1

Далее производим проверку условия для свободных клеток по формуле:

Проверка показала, что план является оптимальным, так как условия для отдельных свободных клеток выполняются.

Целевая функция оптимизированного плана:

Оптимизация первоначального базисного плана позволила сократить затраты на перевозку на