Таблица 5.51

1 2 3 4 5

5.3. Десять лет назад некий предприниматель организовал доставку оптовых фармацевтических товаров с центрального склада (ЦС) на автофургонах. С тех пор значительно увеличился спрос на фармацевтическую продукцию и появились два новых товарных склада (С1 и С2). Центральный склад, традиционно имеющий больший ассортимент товаров, время от времени выручал новые склады в обеспечении кратковременных заказов. Такая взаимовыручка со временем привела к тому, что треть своих заказов новые склады выполняли за счет товаров, полученных с центрального склада. В табл. 5.52 приведено количество заказов, выполняемых тремя товарными складами для шести потребителей, обозначенных П1-П6.

Таблица 5.52

Маршрут

Откуда

Куда

Количество заказов

Предприниматель постоянно совершенствовал способы доставки заказов, придерживаясь принципа децентрализации, когда каждому товарному складу была определена своя зона доставки товара, покрывающая всех потребителей, получающих заказы с этого склада. Но управляющие складами комплектовали заказы согласно своим сферам влияния . Например, менеджеры центрального склада гордились тем, что поставляют товары не только обычным потребителям, но и другим товарным складам. Поэтому зачастую разные склады поставляют заказы одному и тому же потребителю.

В табл. 5.53 приведены расстояния (в милях) между складами и потребителями. В автофургон обычно помещается 100 товарных заказов.

Оцените организацию перевозок предпринимателя и предложите свой план перевозок.

5.4. Авиакомпания KeeWee выполняет полеты между городами А и В согласно расписанию, приведенному в табл. 5.54. Экипаж может вернуться в свой город не ранее чем через 90 минут после прилета либо на следующий день. Составьте расписание назначения экипажей на рейсы, минимизирующее суммарное время простоев всех экипажей.

Таблица 5.54

Рейс Отлет из города А Прилет в город В Рейс Отлет из города В Прилет в город А

Таблица 5.53

ГЛАВА 6

СЕТЕВЫЕ МОДЕЛИ

В рамках теории исследования операций рассматривается большое количество практических задач, которые можно сформулировать и решить как сетевые модели. Недавние исследования показывают, что не менее 70% реальных задач математического программирования можно представить в виде сетевых моделей. Приведем несколько конкретных примеров.

1. Проектирование газопровода, соединяющего буровые скважины морского базирования с находящейся на берегу приемной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода.

2. Поиск кратчайшего маршрута между двумя городами по существующей сети дорог.

3. Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям.

4. Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.

5. Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).

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

1. Алгоритм нахождения минимального остовного дерева (пример 1).

2. Алгоритм поиска кратчайшего пути (пример 2).

3. Алгоритм определения максимального потока (пример 3).

4. Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью (пример 4).

5. Алгоритм определения критического пути (пример 5).

Задачи, вытекающие из перечисленных примеров, можно сформулировать и решать как задачи линейного программирования. Однако специфическая структура этих задач позволяет разработать специальные сетевые алгоритмы, более эффективные, чем стандартный симплекс-метод.