Для связи в whatsapp +905441085890

Приложения задач о многопродуктовом потоке

Приложения задач о многопродуктовом потоке

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

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

Приложения задач о многопродуктовом потоке

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

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

Приложения задач о многопродуктовом потоке

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

Приложения задач о многопродуктовом потоке

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

В качестве примера рассмотрим задачу, описанную в табл. 5.9. Число судов каждого типа равно 2. Соответствующая сеть изображена на рис. 5.5. Отметим, что в таком классе задач узлы служат для обозначения места и времени.

Приложения задач о многопродуктовом потоке
Приложения задач о многопродуктовом потоке

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

Приложения задач о многопродуктовом потоке

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

минимизировать

Приложения задач о многопродуктовом потоке

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

Приложения задач о многопродуктовом потоке
Приложения задач о многопродуктовом потоке

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

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

минимизировать

Приложения задач о многопродуктовом потоке

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

Приложения задач о многопродуктовом потоке

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

Эта теория взята со страницы лекций по предмету «математическое программирование»:

Предмет математическое программирование

Возможно эти страницы вам будут полезны:

Специальный класс целочисленных задач о многопродуктовом потоке
Приближенное решение многопродуктовой транспортной задачи методом агрегирования
Эвристический алгоритм решения задачи синтеза сети связи
Методы внутренней точки для задачи математического программирования