Постановка задачи. Транспортные задачи линейного программирования

Транспортные задачи линейного программирования

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них яв­ляется, как правило, распределение ресурсов, находящихся у т производителей (поставщиков), по п потребителям этих ресурсов.

На автомобильном транспорте наиболее часто встречаются сле­дующие задачи, относящиеся к транспортным:

• прикрепление потребителей ресурса к производителям;

• привязка пунктов отправления к пунктам назначения;

• взаимная привязка грузопотоков прямого и обратного направле­ний;

• отдельные задачи оптимальной загрузки промышленного оборудования;

• оптимальное распределение объемов выпуска промышленной
продукции между заводами-изготовителями и др.

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются т пунктов отправления груза и объемы отправления по каждому пункту а₁, а₂,…а_m. Известна потребность в грузах b₁, b₂,…b_n по каждому из п пунктов назначения. Задана матрица стоимостей доставки по каж­дому варианту c_ij, i = , j = . Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого i–го пункта отправления (от поставщи­ка) в каждый j-й пункт назначения (до потребителя) x_ij с мини­мальными транспортными издержками. В общем виде исходные данные представлены в табл. 7.1.

Таблица 7.1 – Исходные данные

Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения :

(1)

Если такого равенства нет (потребности выше запасов или на­оборот), задачу называют открытой, т. е.:

(2)

Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений. Все грузы из i-х пунктов должны быть отправлены, т. е.:

(3)

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

(4)

Суммарные объемы отправления должны равняться суммар­ным объемам назначения:

(5)

Должно выполняться условие неотрицательности переменных: x_ij ≥0,, i = , j = . Перевозки необходимо осуществить с ми­нимальными транспортными издержками (функция цели):

(6)

В модели (3) — (6) вместо матрицы стоимостей перевозок (C_ij) могут задаваться матрицы расстояний. В таком случае в каче­стве целевой функции рассматривается минимум суммарной транс­портной работы. Как видно из выражения (5), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если

o потребности по пунктам назначения превышают запасы пунктов
отправления, то вводится фиктивный поставщик с недостающим
объемом отправления;

o запасы поставщиков превышают потребности потребителей, то
вводится фиктивный потребитель с необходимым объемом по­требления.

Варианты, связывающие фиктивные пункты с реальными, име­ют нулевые оценки. После введения фиктивных пунктов задача ре­шается как закрытая.

Транспортным задачам присущи следующие особенности:

o распределению подлежат однородные ресурсы;

o условия задачи описываются только уравнениями;

o все переменные выражаются в одинаковых единицах измерения;

o во всех уравнениях коэффициенты при неизвестных равны еди­нице;

o каждая неизвестная встречается только в двух уравнениях системы ограничений.

Транспортные задачи могут решаться симплекс-методом. Од­нако перечисленные особенности позволяют для транспортных за­дач применять более простые методы решения.

Дата добавления: 2014-01-04