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

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

Пусть в m пунктах отправления А₁, А₂, …А_m(поставщики) сосредоточенно соответственно а₁, а₂, …а_m единицу однородного груза. Этот груз следует доставить в n пунктов назначения – В₁, В₂,…В_n. (потребители) в количествах b₁, b₂,…b_n единиц. Заданны стоимости C_ik перевозок единицы груза из пункта отправления i в пункт назначения k. Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится и запросы всех потребителей удовлетворяются (закрытая модель), а суммарные транспортные расходы минимальны.

Все данные задачи и неизвестные удобно задать в виде таблицы 6.1

Таблица 6.1

Поставщики и их запасы		Потребители и потребительский спрос
		В1	В2	……	Вn
		b1	b2	……	bn
А1,	a1	С11 х11	С12 х12	……	С1n х1n
А2,	а2,	С21 х21	С22 х22	……	С2n х2n
……	……	……	……	……	……
Аm	аm	Сm1 хm1	Сm2 хm2	……	Сmn хmn

Здесь х_ij – количество груза, перевозимого от i-того поставщика j-тому потребителю. С помощью этих переменных можно записать математическую модель задачи.

Найти минимум целевой функции

Z=, при ограничениях

(6.1)

где все x_ij≥0. Как следует из этих соотношений, данная задача относится к классу задач Л.П. и может быть решена симплекс-методом.

Как и в симплекс-методе, здесь сначала строится опорное решение, в котором все переменные разбиваются на свободные и базисные. Затем последовательно переходят от одного базиса к другому, чтобы значение целевой функции улучшалось до тех пор, пока оно не достигнет оптимального значения.

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

Методику решения транспортной задачи рассмотрим на конкретном примере.

Таблица 6.2

вj аj	b1=20	b2=40	b3=50	b4=30	U1 U2 U3
a1=60	1 20	1 40	5 ––	3 0
a2=20	5 ––	2 ––	5 ––	5 20
a3=60	3 ––	4 ––	1 50	2 10

V₁ V₂ V₃ V₄

1. Построение опорного решения

Для построение опорного решения используем метод минимального элемента. В этом методе заполнения табл. 6.2 начинают с клетки с наименьшей величенной С_ij . В нашем примере можно начать с клетки (1.1). Запишем в эту клетку максимально возможное число х_II=min=20. Так как потребности пункта В₁ полностью удовлетворенны, в остальные клетки первого столбца ставим прочерки – столбец "закрыт". Далее заполняются клетки (1,2) и (3,3). Клетки 4-го столбца заполняем автоматически с учетом требований (6.1).

В транспортной задаче ранг системы ограничений, а следовательно, и число базисных неизвестных всегда на единицу меньше числа уравнений (6.1), т.е. суммарного числа строк и столбцов таблицы. В нашем случае число базисных переменных равно 6, а число клеток с не нулевыми значениями переменных – 5. Следовательно, одну из нулевых переменных мы должны считать базисной. Пусть х₁₄ является базисной переменной. Обоснование такого выбора приведем позднее. Вместо прочерка в соответствующую клетку запишем нуль.

2. Построение последовательных итераций.

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

Z=γ₀+ γ₁₃x₁₃+ γ₂₁x₂₁+ γ₂₂x₂₂+ γ₂₃x₂₃+ γ₃₁x₃₁+ γ₃₂x₃₂ (6.2)

Так как свободные переменные равны нулю, то транспортные расходы при первоначальном плане перевозок равны

γ ₀=1·20+1·40+3·0+5·20+1·50+2·10=230.

Для нахождения коэффициентов γij` при свободных переменных в целевой функции сопоставим каждому пункту А_i некоторую величину Ui, а пунктам назначения Вj-Vj, Ui, Vj – потенциалы пунктов отправления и назначения определяют из системы уравнений

Ui+Vj=Cij, соответствующих базисным переменным (заполненным клеткам).

В нашем случае

U₁+V₁=1 U₁=0 V₁=1

U₁+V₂=1 V₂=1

U₁+V₄=3 V₄=3

U₂+V₄=5 U₂=2 (6.3)

U₃+V₄=2 U₃=–1

U₃+V₃=1 V₃=2

В этой системе число неизвестных на единицу больше числа уравнений. Поэтому одну из переменных выбираем произвольно. Пусть U₁=0, тогда все остальные потенциалы определяются однозначно из системы (6.3)

Недостающую базисную переменную Х₁₄ мы ввели с таким расчетом, чтобы система (6.3) была разрешима. Нетрудно убедиться, что эта система не разрешается, если вместо Х₁₄ в базис ввести другую нулевую переменную Х₂₃

Доказывается, что коэффициенты целевой функции при свободных переменных определяются равенствами =C_ij– где C^'_ij=U_i+Vi – косвенные стоимости. Для нашего примера

С'₁₃= U₁+V₃=2 γ₁₃ =С₁₃-С'₁₃=5-2= 3

С'₂₁= U₂+V₁=3 γ₂₁ =С₂₁-С'₂₁=5-3= 2

С'₂₂= U₂+V₂=3 γ₂₂ =С₂₂-С'₂₂=2-3= -1

С'₂₃= U₂+V₃=4 γ₂₃ =С₂₃-С'₂₃=5-4= 1

С'₃₁= U₃+V₁=0 γ₃₁=С₃₁-С'₃₁=3-0= 3

С'₃₂= U₃+V₂=0 γ₃₂ =С₃₂-С'₃₂=4-0= 4

Z=230+3x₁₃+2x₂₁–x₂₂+x₂₃+3x₃₁+4x_32.

Так как среди коэффициентов целевой функции имеется отрицательный, то ее значение может быть улучшено переводом свободной переменной x₂₂ в базис. Для этого построим цикл пересчета х₂₂. Цикл пересчета образуется ходом шахматной ладьи из данной клетки, соответствующей свободной переменной, по клеткам базисных переменных. В нашем случае в вершинах цикла находятся базисные переменные х₁₂; х₁₄; х₂₄ и исходная свободная переменная х₂₂ (табл. 6.2 и табл. 6.3).

Таблица 6.3.

20	40 –α		0+ α
	α		20- α
		50	10

Из цикла пересчета видно, что максимально возможное значение

х₂₂= α =20. Таким образом, следующее решение имеет вид.

Таблица 6.4.

1 20	1 20	5 ––	3 20
5 –––	2 20	5 ––	5 ––
3 –––	4 –––	1 50	2 10

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

Z=210+3х₁₃+3х₂₁+2х₂₃+х₂₄+3х₃₁+4х_32.

Так как все коэффициенты в целевой функции положительны, то дальнейшее уменьшение целевой функции невозможно и Z_min=210.

Примечание.

До сих пор мы рассматривали случаи, когда сумма запасов груза в пунктах отправления равна суммарной потребности в пунктах назначения.

. (6.4)

На практике встречаются открытые транспортные задачи, в которых это не выполняется. Эти задачи сводятся к рассмотренной выше, если ввести фиктивного поставщика или получателя, чтобы выполнялось условие (6.4). Стоимости Cij, соответствующие фиктивным пунктам, полагаются равными нулю.