Сетевая модель транспортного потока

4. Модели распределения транспортных потоков

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

Существуют две основные формулировки этой задачи: в матричной и сетевой формах. При постановке в матричной форме задача распределения транспортных потоков сводится к транспортной задаче линейного программирования. При сетевой постановке задачи ее условия определяются на ориентированном мультиграфе с множествами узлов и ориентированных дугс тем условием, что не пусты подмножествавсех дуг, входящих в узели— всех дуг, выходящих из узла. Такая система называется транспортной сетью.

Через обозначим величину потока на дугев соответствии с ее ориентацией и через— коэффициент транспортных затрат. Тогда транспортная задача в сетевой форме описывается соотношениями

, (4.1.)

, ,(4.2.)

Для разрешимости задачи необходимо

. (4.3.)

Говорят, что величиной при положительном знаке определяется мощность стока, а при отрицательном – мощность источника. Кроме того, в сети могут быть транзитные узлы, для которых.

В случаях, когда неравенство (4.3.) выполняется строго, модель называется открытой, при выполнении же (4.3.) как равенства – закрытой (замкнутой). Присоединяя к открытой задаче сток с мощностью , и соединяя его ориентированными дугами со всеми источниками, можно перейти от открытой задачи к закрытой. Для их эквивалентности достаточно потребовать, чтобы на всех дополнительных дугах коэффициенты транспортных затрат были равны нулю. Иногда тот же прием используют и в несовместной задаче, присоединяя ко всем ее стокам источник с мощностью. Затраты на дополнительных дугах в этом случае должны вводится из экономических соображений. Например, вследствие высокой стоимости приобретения продукта со стороны. Модели распределения транспортных потоков в сетевой постановке с одним источником и одним стоком единичной мощности, расположенными в некоторых вершинах сети, представляется задачу о минимальном маршруте.

Иногда – при отождествлении величины с расстояниями на дугах— говорят также о маршрутах минимальной длины.

Если сеть моделирует реальную структуру перевозок, то транспортные затраты должны рассчитываться в соответствии с тарифами. Обычно тариф представляет функцию , монотонно не убывающую с ростом дальности перевозоки субаддитивную, т.е., если, то имеет место равенство

. (4.4.)

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

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

Затем на втором этапе ставится транспортная задача в матричной форме.

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

(4.5.)

Отмечая на сети два узла , можно дополнить условия (4.2.), (4.5.) равенствами

и заменить критерий (4.1.) требованием .

Эта модель известна как задача о максимальной пропускной способности сети.

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

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

В зависимости от отрасли производства и используемого оборудования учитываются ограничения на допустимые виды раскроев. С задачами раскроя совпадает постановка некоторых задач размещения грузов в сушильных печах, в вагонах, на палубах и трюмов судов. В массовом производстве при поступлении одинаковых кусков материал, если можно перечислить все () доступные способы раскроя одного куска материала на некоторые изнужных видов заготовок, задача раскроя сводится к решению задачи линейного программирования: найти интенсивность (кратность) применениякаждого из раскроев, при которых и для каждого соблюдено условие , где — количество заготовокв раскрое; — необходимое на одно изделие количество этих заготовок. На практике обычно нельзя перечислить все допустимые раскрои. Упомянутую задачу решают исходя из некоторого набора допустимых раскроев методами линейного программирования.