Транспортная задача

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

На станциях находится однородной груз, который нужно перевезти потребителям . Тарифы перевозок , запасы грузов на страницах , потребности в грузах потребителей известны и задаются таблицей перевозок. Спланировать их так, чтобы общая сумма транспортных расходов была минимальной.

Станц. назн Станц. отправ.	В1	В2	В3	…	Вn	Запасы
А1	с11	с12	с13	…	с1n	a1
А2	с21	с22	с23	…	с2n	a2
M	…	…	…	…	…	…
Аm	сm1	сm2	сm3	…	сmn	am
Потребности	b1	b2	b3	…	bn

Будем считать, что . (12)

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

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

(13)

При этом функция (14)

должна быть минимальной. Таким образом, среди неотрицательных решений системы (13) нужно найти такое, при котором функция (14) будет минимальной.

В силу симметрии системы (13) ее исследование проводится просто. Доказывается, что ранг этой системы r=m+n–1. Применяя симплекс-метод, первое опорное решение можно очень просто найти по таблице перевозок методом «северо-западного угла» или методом «минимальной стоимости» (это покажем на примере). При этом число базисных (заполненных) клеток должно равняться r. Проверка первого опорного решения (первого допустимого плана перевозок) осуществляется так же просто. С каждой свободной неизвестной связываем ее цикл пересчета – замкнутую ломаную линию, звенья которой идут вдоль строк и столбцов, и все вершины, кроме одной, соответствующей этой свободной неизвестной, находятся в базисных клетках. Вершинам цикла пересчета присваиваем знаки: «+» для свободной неизвестной, а далее в порядке чередования «–», «+», и т.д.

Справедлива теорема: Коэффициент при свободной неизвестной в целевой функции (14), т.е. оценка этой свободной неизвестной равна алгебраической сумме тарифов по циклу пересчета этой свободной неизвестной. В этом суть так называемого распределительного метода.

Если связать со станциями отправления систему чисел , а со станциями назначения – систему чисел так, чтобы для базисной клетки, то такая система чисел называется потенциалами. Составим систему потенциалов для всех базисных клеток и решаем ее (это делается просто). Для каждой свободной клетки проведем сравнение ее тарифа и суммы соответствующих потенциалов.

Справедлива теорема: оценка свободной неизвестной целевой функции (13) равна разности между тарифом этой неизвестной и суммой соответствующих потенциалов.

Таким образом, если мы определили (методом потенциалов или распределительным методом), что оценки всех свободных неизвестных неотрицательны, то полученное первое опорное решение (первый допустимый план) является оптимальным. Если же хотя бы для одной свободной неизвестной оценка отрицательна, то найденный план можно улучшить, производя сдвиг по циклу пересчета этой свободной неизвестной на число, являющееся наименьшим среди отрицательных вершин цикла. Это значит, что в положительных вершинах цикла это число прибавляется, а в отрицательных вычитается от стоящих там величин грузов. При этом свободная клетка становится базисной (занятой), а клетка, содержащая наименьшее число среди отрицательных вершин цикла, становится свободной. Таким образом, мы перейдем к новой таблице (плану) перевозок и повторим проверку его на оптимальность и т.д. до получения оптимального плана перевозок.

Замечание. Если в ходе преобразований число базисных (заполненных) клеток окажется меньше r, то свободной неизвестной оставляем ту, тариф которой наибольший, а остальные свободные клетки заполняем нулями, считая их базисными.

Пример: найти оптимальный план перевозок для исходной таблицы перевозок.

Станц. назн Станц. отправ.	В1	В2	В3	В4	Запасы
А1	^7	^4	^15	^9	120
А2	^11	^12	^7	^3	80
А3	^4	^5	^12	^8	100
Потребности	85	65	90	60	300

Найдем первый допустимый план методом «северо-западного угла». Получим

Станц.назн Станц. отправ.	В1	В2	В3	В4	Запасы
А1	85^7	35^4	^15	^9	120
А2	^11	30 ^12	50 ^7	^3	80
А3	^4	^5	40 ^12	60 ^8	100
Потребности	85	65	90	60	300

Все запасы вывезены, все потребности удовлетворены, число базисных неизвестных (число заполненных клеток) равно r = m + n – 1 = 3 + 4 – 1 = 6.

Стоимость перевозок по этому плану будет:

.

Найдем допустимый план методом «минимальной стоимости», осуществляя максимальные перевозки в те пункты, где тариф наименьший. Получим

Станц. назн Станц. отправ.	(7) В1	(4) В2	(15) В3	(11) В4	Запасы
А1 (0)	^7	65^4	55 ^15 ^+	^9 ^–	120
А2 (-8)	^11	^12	^– 20 ^7	^+ 60 ^3	80
А3 (-3)	85 ^4	^5	15 ^12	^8	100
Потребности	85	65	90	60	300

Стоимость перевозок по этому плану будет:

.

Т.к. стоимость перевозок по этому плану меньше, чем по предыдущему, то возьмем его за основу и проверим на оптимальность методом потенциалов. Введем числа так, чтобы

; ; ; ; ; .

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

; ; ; ; ; .

Мы видим, что только одна оценка для свободной неизвестной х₁₄ отрицательна. Построим цикл пересчета этой свободной неизвестной (см. пунктирные линии).

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

Станц. назн Станц. отправ.	(5) В1	(4) В2	(13) В3	(9) В4	Запасы
А1 (0)	^7	65^4	^15	55 ^9	120
А2 (-1)	^11	^12	75 ^7	5 ^3	80
А3 (-1)	85 ^4	^5	15 ^12	^8	100
Потребности	85	65	90	60

Составим систему потенциалов для этого плана перевозок

; ; ; ; ; .

Пусть тогда , , , , , ,

Вычислим оценки свободных неизвестных ; ; ; ; ; .

Так как все оценки свободных неизвестных неотрицательны, то последний план перевозок оптимален. Стоимость транспортных расходов по этому плану будет ед. стоимости.