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




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


Очевидно, в результате циклического переноса допустимый план остается допустимым — баланс запасов и заявок не нарушается. Ну что же, произведем этот перенос и запишем новый, улучшенный план перевозок в таблице 10.3.

Теперь посмотрим, чего мы добились, сколько сэкономили? Общая стоимость плана, показанного в таблице 10.2, равна L1 = 18 • 13 + 12 • 7 + 15 • 8+33 • 12 + +9 • 10+11-8+4-10+26-15 =1442;

Таблица 10.3

        ПН

ПО

В1

В2

В3

В4

В5

Запасы аi

А1

18 13

12  7

14

7

5

30

А2

11

15   8

22  12

11  6

8

48

А3

6

10

20  10

8

11

20

А4

14

8

10

4   10

26   15

30

Заявки bj

18

27

42

15

26

128

Общая стоимость плана, показанного в таблице 10.3, равна L2  = 18•13 +12.7 +15•8 + 22•12 +11•6 +20•10+ 4•10 + 26•15 = 1398.

Таким образом, нам удалось уменьшить стоимость перевозок на 1442 — 1398 = 44 единицы. Это, впрочем, можно было предсказать и не подсчитывая полную стоимость плана. Действительно, алгебраическая сумма стоимостей, стоящих в вершинах цикла, со знаком плюс, если перевозки в этой вершине увеличиваются, и со знаком минус — если уменьшаются (так называемая «цена цикла»), в данном случае равна: 6 - 8+10 - 12 = - 4. Значит, при переносе одной единицы груза по этому циклу стоимость перевозок уменьшается на четыре. А мы их перенесли целых 11; значит, стоимость должна была уменьшиться на 11•4 = 44 единицы, что и произошло.

Значит, весь секрет оптимизации плана перевозок в том, чтобы переносить («перебрасывать») перевозки по циклам, имеющим отрицательную цену.

В теории линейного программирования доказывается, что при опорном плане для каждой свободной клетки транспортной таблицы существует цикл, и притом единственный, одна вершина которого (первая) лежите данной свободной клетке, а остальные — в базисных клетках. Поэтому, отыскивая «выгодные» циклы с отрицательной ценой, мы должны высматривать — нет ли в таблице соблазнительных, «дешевых» свободных клеток.


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