Общая постановка транспортной задачи.

Таблица 5.1

Задача о перевозках.

ТРАНСПОРТНАЯ ЗАДАЧА.

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

Имеется m пунктов отправления А₁, А₂,..., А_m, в которых сосредоточен некоторый груз в количествах а₁,а₂,...,а_m и n пунктов назначения В₁, В₂,..., В_n, в которые требуется завезти этот груз в количествах b₁,b₂,...,b_n , причем

. Известны стоимости c_ij перевозки единицы

груза из пунктов А_i в пункты В_j (; ). Предполагается, что

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

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

Требуется составить такой план перевозок из пунктов А_i в пункты В_j, при котором затраты на перевозки были бы наименьшими.

Исходные данные задачи обычно представляются в виде транспортной таблицы (табл. 5.1).

П_н П_о	В₁	В₂	_{. . .}	В₃	Запасы
А₁	^С₁₁	^С₁₂	_{. . .}	^С₁_n	а₁
А₂	^С₂₁	^С₂₂	_{. . .}	^С₂_n	а₂
_{. . .}	_{. . .}	_{. . .}	_{. . .}	_{. . .}	_{. . .}
А_m	^С_m₁	^С_m₂	_{. . .}	^С_mn	а_m
Потребности	в₁	в₂	_{. . .}	в_n

Стоимости c_ij проставляются в правых верхних углах соответствующих клеток.

Составим математическую модель задачи. Пусть x_ij – количество груза, перевозимого из пункта А_i в пункт В_j. Целевая функция задачи (общая стоимость перевозок) записывается следующим образом:

Систему ограничений записываем, руководствуясь тем, что:

а) запасы пунктов отправления должны быть исчерпаны;

б) потребности пунктов назначения должны быть удовлетворены;

в) перевозки могут быть только неотрицательными.

Таким образом, ограничения задачи имеют вид:

Мы видим, что задача о перевозках является ЗЛП.

Транспортной задачей называется ЗЛП следующего вида:

Отметим следующую особенность транспортной задачи как ЗЛП специального вида: система уравнений разбита на две группы (5.2) и (5.3) так, что каждая переменная входит ровно в одно уравнение группы с коэффициентом 1.

Уравнения (5.2) называются горизонтальными, уравнения (5.3) -вертикальными.

Любой набор значений переменных x_ij называется планом перевозок. План перевозок называется допустимым, оптимальным или опорным, если он является допустимым, оптимальным или опорным планом ЗЛП (5.1 - 5.4).

Транспортная задача, как и любая задача линейного программирования, может быть решена симплекс-методом. Однако
благодаря указанной выше особенности транспортной задачи, для неё
существуют более простые методы решения, один из которых – метод
потенциалов - мы изучим.