Постановка транспортной задачи

Большое число разнообразных экономических ситуаций может быть смоделировано с помощью транспортной задачи.

Модель в общем виде Требуется перевезти с наименьшими затратами однородную продукцию от n поставщиков к m потребителям. Заданы объемы запасов продукции у каждого из поставщиков ai, , и объемы потребностей у каждого из потребителей bj, . Затраты на перевозку единицы продукции от i-го поставщика к j-му потребителю равны cij; , . Составить план перевозок.

Пример Компания производит коммерческие холодильные установки на трех основных производствах (n = 3) – в Стокгольме, Триесте и Руане – соответственно по 120, 40 и 90 шт. (a1 = 120, a2 = 40, a3 = 90). Основными центрами сбыта являются Лейпциг и Лион (m = 2), которые нуждаются в поставках соответственно 150 и 90 установок (b1 = 150, b2 = 90). Перевозка одной установки в эти города из Стокгольма обходится соответственно в 25 и 14, из Триеста – в 18 и 8, и из Руана – в 12 и 6 ф.ст. (c11 = 25, c12 = 14, …, c32 = 6). Составить наиболее дешевый план перевозок.

Введем переменные х_ij –

- количество продукции, перевозимой от i-го поставщика к j-му потребителю; , . Тогда cijхij - затраты на перевозку продукции от i-го поставщика к j-му потребителю. Просуммировав их по всем i и j, получим общие затраты, которые необходимо минимизировать: min От i-го поставщика к различным потребителям вывозится продукции. При этом нельзя увезти большее количество продукции, чем имеется у него в запасе, и это должно выполняться для всех n поставщиков (): К j-му потребителю привозят продукции, и эта сумма должна быть не меньше его потребностей (для любого потребителя ): По смыслу задачи .

- число установок, перевозимых из i-го центра производства в j-й центр сбыта; , . Тогда в 25х11 ф.ст. обходятся перевозки из Стокгольма в Лейпциг, в 14х12 ф.ст. - из Стокгольма в Лион и т.д. Минимизируем все затраты на перевозку: min (25x11 + 14x12 + 18x21 + 8x22 + 12x31 + 6x32) В два центра сбыта из Стокгольма будет вывезено x11 + x12 установок. Эта сумма не может превысить 120, т.е. числа установок, производимых в Стокгольме: x11 + x12 120 Аналогичные условия должны выполняться для Триеста и Руана: x21 + x22 40 x31 + x32 90 Из трех центров производства в Лейпциг поставляют x11 + x21+ x31 установок. Так как Лейпцигу необходимо по крайней мере 150 установок, x11 + x21+ x31 150 Аналогично для Лиона x12 + x22+ x32 90 По смыслу задачи , так как количество установок не может быть отрицательным или дробным.

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

Построенная модель является задачей линейного программирования, включающей m+n ограничений на m*n неотрицательных переменных.

Для рассмотренного примера – задачи о холодильных установках – транспортная модель примет вид:

min (25x₁₁ + 14x₁₂ + 18x₂₁ + 8x₂₂ + 12x₃₁ + 6x₃₂)

x₁₁ + x₁₂ 120

x₂₁ + x₂₂ 40

x₃₁ + x₃₂ 90

x₁₁ + x₂₁+ x₃₁ 150

x₁₂ + x₂₂+ x₃₂ 90

Построенная задача линейного программирования включает 5 = 3 + 2 ограничений на 6 = 3 * 2 неотрицательных переменных.

Отметим, что перевозка продукции - не единственная экономическая ситуация, которая может быть смоделирована с помощью такой задачи. Транспортные задачи имеют более широкую область применения и представляют собой отдельный класс задач линейного программирования, для которого разработаны специальные методы решения. Конечно, ее можно решить и симплекс-методом, но в связи с большой размерностью (особенно с большим числом переменных) это бывает невыгодно. В самом деле, в симплексной таблице будет храниться более чем m*n*(m+n) значений (даже если размерность задачи всего 5 х 5, то это 10 ограничений на 25 основных переменных).

Пример использования транспортной модели в экономической ситуации, не связанной с перевозками, будет рассмотрен далее.