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



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


Бесконечно уменьшаться она не может (она никак не может стать меньше нуля!), значит, рано или поздно мы придем к оптимальному плану. Для такого плана уже не остается ни одной свободной клетки с отрицательной ценой цикла. Это — признак того, что оптимальное решение найдено.

Таблица 10.4

ПН

ПО

B1

B2

B3

B4

B5

Запасы

аi

A1

13

18

7

12-

14

7

5

+

30

A2

11

8

15+

12

22

6

11

      -

8

48

A3

6

10

10

20

8

11

20

A4

14

8

10

10

4+

15

-26

30

Заявки

bj

18

27

42

15

26

128

В теории линейного программирования существуют способы, позволяющие автоматически, без размышлений, выделять свободные клетки с отрицательной ценой цикла (так называемый «метод потенциалов»), но мы на них останавливаться не будем, так же как и на ряде других способов решения транспортной задачи, с которыми читатель может ознакомиться, но специальным руководствам [5, 7, 8].

В заключение скажем несколько слов о так называемой «транспортной задаче с неправильным балансом», когда сумма заявок не равна сумме запасов:

         (10.7)

Если

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

          (10.8)

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

         (10.9)

Возникает вопрос: а каковы же стоимости перевозок из пунктов отправления Ai в «фиктивный» пункт назначения Bф? Естественно положить их равными нулю (ведь фактически в пункт Вф

ничего перевозиться не будет!). Поэтому для любого пункта отправления стоимость сiф = 0.




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