Исследование операций. Линейное, динамическое программирование



грузовые перевозки недорого |

Исследование операций - часть 60


Проверим, является ли этот план допустимым: да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу — заявке соответствующего пункта назначения; значит, все в порядке — все заявки удовлетворены, все запасы израсходованы (сумма запасов равна сумме заявок и выражается числом 128, стоящим в правом нижнем углу таблицы).

Здесь и в дальнейшем мы проставляем в таблице только отличные от нуля перевозки, а клетки, соответствующие нулевым перевозкам, оставляем «свободными». Проверим, является ли план перевозок, данный в таблице 10.2, опорным (не слишком ли много там отличных от нуля, «базисных» перевозок?). Число свободных клеток с нулевыми перевозками в таблице 10.2 равно как раз (m-1)(n-1) = 3•4 = 12, так что план — опорный. Вот как нам его удалось легко построить!

          Таблица 10.2

           Пн

по

В1

В2

В3

В4

В5

Запасы аi

A1

13

18

7

12

14

7

5

30

A2

11

 

8

15

12

33

6

8

48

A3

6

10

10

9

8

11

11

20

A4

14

8

10

10

4

15

26

30

Заявки bj

18

27

42

15

26

128

Теперь пора подумать о том, является ли этот план оптимальным — т. е. минимальна ли для него общая стоимость перевозок? Скорее всего, нет (ведь составляя опорный план, мы совсем не думали о стоимостях). Так и есть — план не оптимальный. Например, сразу видно, что можно его улучшить, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы, уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12, но зато увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6. Чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных — свободной. Сколько единиц груза можем мы перенести по циклу (2.4) > (3.4) > (3.3) > (2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая — в четных? Очевидно, не больше, чем 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными).


Содержание  Назад  Вперед