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

Кроме того, имеются затраты (отрицательная полезность), связанные с перегоном судна из порта, где оно было разгружено, в порт погрузки. Задача заключается в максимизации функции полезности путем составления оптимальных маршрутов и расписания движения судов.
Данная задача может быть сформулирована в виде следующей сетевой задачи. Каждый узел у сети соответствует прибытию судна в порт назначения в один из допустимых сроков доставки. Каждый узел соответствует исходному порту и моменту, равному разности срока доставки и времени транспортировки, которое по предположению является детерминированным. Дуга
соответствует перевозке груза, а дуга
— перегону судна из порта доставки в исходный порт. Суда
-го типа первоначально располагают в источнике
и дуги
, таким образом, соответствуют началу их эксплуатации. Далее вводят фиктивный сток
и дугу
, соответствуюшие завершению эксплуатации судов. И наконец, суммарный поток перевозимого груза но всем лугам, соответствующим различным датам перевозки и типам судов, не должен превосходить некоторой заданной величины. Математически эта задача формулируется следующим образом: максимизировать

при условии, что

Здесь через обозначена полезность, соответствующая отдельному судну, перевозимому грузу и маршруту;
— это множество допустимых маршрутов для данного груза;
— грузоподъемность судна
-го типа на маршруте
. Суммарный перевозимый груз не может превышать спроса на него
. Ограничения (5.12) описывают условие сохранения потока по числу судов
, а величина
равна 0 или
в зависимости от того, может ли быть использовано на дуге
судно
-го типа или нет.
В качестве примера рассмотрим задачу, описанную в табл. 5.9. Число судов каждого типа равно 2. Соответствующая сеть изображена на рис. 5.5. Отметим, что в таком классе задач узлы служат для обозначения места и времени.


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

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

при условии, что


В задаче (5.14) было сделано одно важное допущение, касающееся поведения водителя. Оно основано на классическом принципе распределения транспортных средств: водители выбирают маршруты таким образом, что суммарное время поездок для всей системы является минимальным. Как правило, целевая функция задачи (5.14) является нелинейной и выпуклой.
Модели вычислительных систем. Очень похожи на только что рассмотренную нами модель городской транспортной сети многие модели вычислительных систем. В этих моделях дуги соответствуют каналам, а узлы — терминалам, системным и запоминающим устройствам и т.п. Каждая дуга имеет фиксированную пропускную способность , которая может быть увеличена на
единиц вплоть до максимального значения
. Стоимость увеличения пропускной способности на единицу равна
. Роль продуктов вновь играют потоки (информация) из источника во все пункты назначения, а вместо матрицы поездок
вводят матрицу, элементы
которой соответствуют объему информации, передаваемой из узла
в узел
. Стоимость передачи единицы информации по дуге
равна
. Математически эта задача может быть сформулирована следующим образом:
минимизировать

при условии, что

Описанная модель может быть использована для определения пропускной способности каналов, при которой заданные требования удовлетворяются с минимальными затратами. В этом случае значения обычно полагают равными 0, если
=0, а величины
выбирают достаточно большими. Другим примером использования этой модели является задача минимизации стоимости передачи информации при фиксированных пропускных способностях дуг. В этом случае
= 0.
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны: