- •Власов м. П.
- •1.Постановка задачи
- •2. Задача максимизации выпуска в заданном ассортименте
- •3. Задача загрузки оборудования
- •4. Модели распределения транспортных потоков
- •5. Простейшая задача размещения на сети
- •6. Математические модели спроса и потребления
- •7. Модели равновесия при неравновесных ценах
- •8. Модели рационируемого равновесия
- •9. Особенности метода решения распределительной задачи
- •10. Задачи с разрывной целевой функцией
- •Литература
4. Модели распределения транспортных потоков
Модели распределения транспортных потоков относятся к классу моделей, используемых для решения задач по оптимизации перевозок. В них, как правило, разыскивается оптимальный план перевозок между некоторой совокупностью производителей и потребителейоднородного продукта. Предполагается, что каждый поставщикспособен поставить в транспортную сеть не более чемединиц продукта, а каждый потребительдолжен получить не менее чемединиц. Критерии могут быть различными, но наиболее часто минимизируется сумма транспортных затрат.
Существуют две основные формулировки этой задачи: в матричной и сетевой формах. При постановке в матричной форме задача распределения транспортных потоков сводится к транспортной задаче линейного программирования. При сетевой постановке задачи ее условия определяются на ориентированном мультиграфе с множествами узлов и ориентированных дугс тем условием, что не пусты подмножествавсех дуг, входящих в узели- всех дуг, выходящих из узла. Такая система называется транспортной сетью.
Через обозначим величину потока на дугев соответствии с ее ориентацией и через- коэффициент транспортных затрат. Тогда транспортная задача в сетевой форме описывается соотношениями
, (4.1.)
, ,(4.2.)
Для разрешимости задачи необходимо
. (4.3.)
Говорят, что величиной при положительном знаке определяется мощность стока, а при отрицательном – мощность источника. Кроме того, в сети могут быть транзитные узлы, для которых.
В случаях, когда неравенство (4.3.) выполняется строго, модель называется открытой, при выполнении же (4.3.) как равенства – закрытой (замкнутой). Присоединяя к открытой задаче сток с мощностью , и соединяя его ориентированными дугами со всеми источниками, можно перейти от открытой задачи к закрытой. Для их эквивалентности достаточно потребовать, чтобы на всех дополнительных дугах коэффициенты транспортных затрат были равны нулю. Иногда тот же прием используют и в несовместной задаче, присоединяя ко всем ее стокам источник с мощностью. Затраты на дополнительных дугах в этом случае должны вводится из экономических соображений. Например, вследствие высокой стоимости приобретения продукта со стороны. Модели распределения транспортных потоков в сетевой постановке с одним источником и одним стоком единичной мощности, расположенными в некоторых вершинах сети, представляется задачу о минимальном маршруте.
Иногда – при отождествлении величины с расстояниями на дугах- говорят также о маршрутах минимальной длины.
Если сеть моделирует реальную структуру перевозок, то транспортные затраты должны рассчитываться в соответствии с тарифами. Обычно тариф представляет функцию , монотонно не убывающую с ростом дальности перевозоки субаддитивную, т.е., если, то имеет место равенство
. (4.4.)
В силу (4.4.) нельзя определить на дугах сети никакой системы коэффициентов транспортных затрат с тем, чтобы сумма их на любой последовательности дуг соответствовала тарифу. Поэтому модели распределения транспортных потоков обычно решается в два этапа.
На первом в реальной конфигурации сети определяют маршрут минимальной длины между всеми возможными парами поставщик – потребитель и по полученному набору дальностей – тарифные стоимости перевозок.
Затем на втором этапе ставится транспортная задача в матричной форме.
В сетевой задаче обычно существует много различных маршрутов, связывающих пару узлов сети. Поэтому она допускает ограничения на пропускные способности дуг
(4.5.)
Отмечая на сети два узла , можно дополнить условия (4.2.), (4.5.) равенствами
,
и заменить критерий (4.1.) требованием .
Эта модель известна как задача о максимальной пропускной способности сети.
Задача раскроя заключается в выборе такого размещения заготовок в кусках материала, которое дает заготовки, как правило, в требуемой комплектности при минимальном расходе материала. В соответствии с особенностями в технологии и организации раскроя различаются математические модели рационального раскроя для массового и индивидуального производства:
для прямых (отрезки, прямоугольники, параллелепипеды) и фигурных заготовок;
для случая кусков материала постоянных размеров и форм и с разбросом формы.
В зависимости от отрасли производства и используемого оборудования учитываются ограничения на допустимые виды раскроев. С задачами раскроя совпадает постановка некоторых задач размещения грузов в сушильных печах, в вагонах, на палубах и трюмов судов.
В массовом производстве при поступлении одинаковых кусков материал, если можно перечислить все () доступные способы раскроя одного куска материала на некоторые изнужных видов заготовок, задача раскроя сводится к решению задачи линейного программирования: найти интенсивность (кратность) применениякаждого из раскроев, при которых
и для каждого соблюдено условие
,
где - количество заготовокв раскрое;
- необходимое на одно изделие количество этих заготовок.
На практике обычно нельзя перечислить все допустимые раскрои. Упомянутую задачу решают исходя из некоторого набора допустимых раскроев методами линейного программирования.