Постановка и математическая модель транспортной задачи

 

Транспортная задача ставится следующим образом. Некоторый однородный продукт, сосредоточенный у m поставщиков A_i в количестве a_i (i = 1, 2,..., m) у каждого, необходимо доставить к потребителю В_j в количестве b_j (j = 1, 2,.., n). Известна стоимость C_ij перевозок (поставок) единицы груза от i - го поставщика j - му потребителю.

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

Будем рассматривать так называемую закрытую модель транспортной задачи (Т3), когда сумма запасов равна сумме заявок потребителей, т.е. . В противном случае ТЗ называется открытой транспортной задачей.

Возможны два случая открытой транспортной задачи (ОТЗ):

1) , то есть сумма запасов больше суммы потребностей.

В этом случае вводят фиктивный пункт B_n+1 клиента с потребностью b_n+1= и стоимостью доставки единицы продукта ему c_{i, n+1}=0.

2) , то есть сумма запасов меньше суммы потребностей клиентов.

В этом случае вводят фиктивный пункт запаса A_m+1 c объемом запаса a_m+1= и стоимостью доставки единицы продукта с_{m+1, j}=0.

Таким образом, открытая транспортная задача преобразуется в закрытую ТЗ.

Постановочную часть ТЗ удобно давать в так называемой транспортной таблице (ТТ). (Табл.5.1.)

 

Таблица 5. 1

Транспортная таблица

Поставщики	Потребители	Запасы
B1	B2	B3	…	Вn
А1	C11	C12	C13	…	C1n	a1
А2	C21	C22	C23	…	C2n	a2
…	…	…	…	…	…	…
Аm	Cm1	Cm2	Cm3	…	Cmn	am
Потребности	b1	b2	b3	…	bn

 

Математическая модель ТЗ:

Пусть х_{i j} - количество единиц груза, отправленного от A_i поставщика к B_j клиенту.

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

(5.1)

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

(5.2)

х_ij≥0,

Суммарная стоимость перевозок

w = c₁₁x₁₁ + c₁₂x₁₂ +... + c_mnx_mn ® min.

Краткая запись математической модели ТЗ:

w = (5.3)

;

;

x _ij ³ 0

 

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

В линейном программировании доказывается, что закрытая ТЗ имеет оптимальный план. При этом, если исходные величины поставок А_i и В_j являются целыми числами, то и все переменные в оптимальном плане будут целыми величинами. Свойство целочисленности оказывается важным, например, при перевозках неделимых грузов.

Система ограничений ТЗ содержит mn неизвестных и m + n ограничений. Если первую группу ограничений просуммировать по i, а вторую - по j, то в левых частях полученных двух уравнений будет находиться одна и та же величина åå x_ij.

Следовательно, должны быть равны и правые части, а именно:

.

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

Если план задачи включает меньше, чем m+n-1 положительных переменных, то он называется вырожденным планом. План ТЗ является опорным тогда и только тогда, когда в транспортной таблице:

1) ровно m+n-1 занятых клеток:

2) не существует цикл, все вершины которого лежат в занятых клетках.

Рассмотрим методы нахождения первоначального опорного плана.

Метод северо-западного угла: в транспортнойтаблице заполняют левую верхнюю клетку (северо-западную) максимльно возможным объемом груза (перевозки) и исключают либо поставщика, если весь его запас исчерпан, либо потребителя, если его заявка полностью удовлетворена, либо того и другого вместе. Затем снова выбирают левую верхнюю клетку в оставшейся таблице и процедуру заполнения клеток повторяют до тех пор, пока все заявки клиентов не будут удовлетворены. Недостаток метода в том, что он не зависит от стоимости доставки единицы груза.

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

Метод двойного предпочтения: в каждой строке транспортной таблицы отмечают наименьший элемент символом V, аналогично отмечают и в каждом столбце. В начале заполняют клетки с двойным символом, затем с одним и, если таблица большая, то процедуру повторяют.

Метод Фогеля (метод штрафов). Штрафом называется разность между двумя наименьшими элементами строки или столбца транспортной таблицы. Метод состоит в том, что определяют штрафы каждой строки и каждого столбца транспортной таблицы. Затем выбирают строку или столбец с наибольшим штрафом и заполняют максимально возможной перевозкой клетку с наименьшей стоимостью доставки единицы груза, т.е. по методу минимального элемента. В оставшейся таблице снова определяют штрафы по всем строкам и столбцам и аналогично заполняют клетку в ряду с наибольшим штрафом и т.д. Процедуру повторяют до тех пор, пока все запасы будут исчерпаны и заявки клиентов будут удовлетворены. [11].