4.3. Транспортная задача (т-задача)

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

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

m – число производителей;

n – число потребителей;

p_i – объем производства на i-м предприятии (мощность i-го производителя);

d_i – объем потребления на складе j-го потребителя (мощность j-го потребителя);

c_ij – стоимость доставки одной единицы продукции от i-го производителя к j-му потребителю, все стоимости известны;

x_ij – количество единиц продукции, доставляемой от i-го производителя к j-му потребителю.

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

Математическая постановка

Пусть матрица стоимостей ||c_ij|| задана. Известны также мощности производителей и потребителей: p_i и d_j.

Тогда модель ЛП будет выглядеть следующим образом:

(1)

при ограничениях:

(2)

(3)

Заметим, что в этой модели число уравнений в ограничениях равно (m + n). Следовательно, число переменных, отличных от тождественного нуля (т.е. число загруженных клеток в таблице ||x_ij||), равно (m + n).

Требуется определить (m + n) переменных x_ij  0 из матрицы ||x_ij||, удовлетворяющих (1), при условиях (2) и (3).

Если выполняется уравнение баланса то Т-задача называется сбалансированной. При этом число независимых уравнений и соответствующих переменных (а значит, и число загруженных клеток матрицы ||x_ij||) становится равным (m + n – 1).

Методы решения разработаны именно для сбалансированной задачи. Несбалансированная задача приводится к сбалансированной введением в матрицу ||с_ij|| фиктивного столбца или строки с нулевыми стоимостями.

Решение Т-задачи

(распределительный метод)

Пусть заданы все c_ij, p_i, d_j.

Пример:

				pi
	20	28	32	50
||сij|| =	48	36	40	100
	35	55	22	150
dj	100	70	130	300

Этап I. Построение опорного (исходного) плана в качестве нулевого приближения методом «СЗ угла» или по min элементу с_ij.

Условие: сохранение всех p_i и d_j, т.е. соблюдение баланса.

В результате p_i распределяются по столбцам (т.е. по складам потребителей), а d_j – по строкам (т.е. по предприятиям производителей). Возникают «маршруты перевозок» от i-го производителя к j-му потребителю.

Пример (продолжение).

Построим исходный план методом «СЗ угла». Суть метода заключается в том, что в качестве очередной загружаемой клетки выбирается левая верхняя клетка образовавшейся прямоугольной подматрицы матрицы ||х_ij||. Для данного примера исходный план строится следующим образом:

Число маршрутов: (m + n – 1) = 3 + 3 – 1 = 5.

Этап II. Оценка оптимальности плана.

Делается проверкой на оптимальность каждого неиспользованного маршрута. При этом, чтобы убедиться, возрастает или убывает общая стоимость перевозок, если использовать неиспользованный маршрут, достаточно оценить изменение стоимости перевозки для одной единицы продукции (Δ_ij), т.е. использовать элименты матрицы ||с_ij|| как матрицы цен.

Оценка Δ_ij возникает в результате пробной загрузки незагруженной клетки в матрице ||х_ij||. При этом для сохранения баланса приходится менять значения х_ij уже загруженных клеток по определенной знакопеременной замкнутой цепочке, начиная с оцениваемой клетки. Получаем знакопеременный цикл. Например, для маршрута (1, 2) имеем такой фрагмент матрицы ||х_ij||:

Возникает цикл: (1, 2) → (2, 2) → (2, 1) → (1, 1). Подставим в этот цикл цены перевозок из матрицы ||с_ij||:

Получим Δ₁₂ = 28 – 36 + 48 – 20 = 20.

Это означает, что если использовать маршрут (1, 2), то стоимость перевозок возрастет на 20 ед. на каждую единицу продукции, перевозимой по этому маршруту. А следовательно, возрастет и общая стоимость перевозок.

Выполнив эту операцию для каждого неиспользованного маршрута, т.е. для незагруженных клеток матрицы ||х_ij||, получим таблицу 3.

Таблица 3

Если имеются Δ_ij < 0, то план можно улучшить, т.е. уменьшить F_ц. Иначе – КОНЕЦ, т.е. план оптимальный.

Лемма 1. Схема изменения перевозок для любого нового маршрута единственна.

Следовательно, единственна и оценка Δ_ij.

Этап III. Улучшение плана путем перезагрузки маршрутов.

Выбираем Δ_ij = min. В примере min Δ_ij = Δ₃₁ = –32. Желательно направить по этому маршруту наибольшее количество продукции, т.е. назначить х₃₁ = max.

Лемма 2. Максимальное количество продукции, которое можно назначить, равно минимуму, взятому из числа загруженных клеток x_ij в цикле с отрицательным индексом.

В примере для маршрута (3. 1) имеем:

max x₃₁ = min (x₂₁, x₃₂) = min (50, 20) = 20,

В результате получаем новый план:

Поскольку Δ₃₁ = –32, х₃₁ = 20, то F¹ = F⁰ + Δ₃₁ · х₃₁ = 9160 – 32 · 20 = = 8520. Суммарные затраты на доставку уменьшились.

Переход на этап II. И так далее, пока все Δ_ij не станут  0.