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

Транспортная задача (ТЗ) ЛП может быть сформулирована следующим образом. Имеет- ся m пунктов отправления (производства) A 1 ,..., Am, в которых имеется товар в количе- стве a 1 ,..., am соответственно. Кроме того, имеется n пунктов назначения (потребления) B 1 ,..., Bn, в которых имеются заявки на этот товар в количестве b 1 ,..., bn соответственно. Предполагается, что

m

i =1

ai =

n

j =1

bj,

т.е. все, что произведено, должно быть получено. Приведенное уравнение называется усло- вием баланса.

Известна стоимость cij перевозки единицы товара из пункта отправления Ai в пункт по- требления Bj. Требуется составить такой план перевозок товара, при котором весь товар из пунктов производства вывезен, все заявки в пунктах потребления удовлетворены и общая стоимость перевозок минимальна.

Математическая модель ТЗ состоит в следующем. Обозначим через xij количество товара, перевозимого из Ai в Bj. Составим задачу ЛП:

m n

cij xij → min,

i =1 j =1

n

j =1

m i =1

xij = ai, i = 1 ,..., m,

xij = bj, j = 1 ,..., n, xij≥ 0, ∀i, j.

На практике условие баланса может не выполняться. Что делать? Если

m

i =1

ai>

n

j =1

bj, (производится больше, чем потребляется),

то вводим новый пункт потребления Bn +1 с запросом

Полагаем

bn +1 =

m i =1

ai−

n j =1

bj.

Если же

m i =1

ai<

n j =1

ci,n +1= 0, i = 1 ,..., m.

bj, (потребляется больше, чем производится),

то вводим новый пункт производства Am +1 с предложением

am +1 =

n j =1

bj−

m i =1

ai.

Полагаем

cm +1 ,j = 0, j = 1 ,..., n.

В дальнейшем будем считать, что условие баланса выполнено.

Отметим, что ранг системы ограничений ТЗ равен m + n − 1 (на 1 меньше m + n за счет

связующего условия баланса). Поэтому количество базисных переменных также равно

m + n − 1.

Исходные данные ТЗ удобно представлять в виде транспортной таблицы (ТТ), см. ниже.

Ai/Bj	B 1	B 2	...	Bn	Запасы ai
A 1	c 11	c 12	...	c 1 n	a 1
A 2	c 21	c 22	...	c 2 n	a 2
...	...	...	...	...	...
Am	cm 1	cm 2	...	cmn	am
Заявки bj	b 1	b 2	...	bn	ai = bj

Опорным планом ТЗ называется такое распределение объемов перевозок в ТЗ, что

– это распределение является допустимым,

– число базисных переменных (xij> 0) равно m + n− 1,все остальные (свободные) перемен-

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

нулю,

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

Метод потенциалов решения ТЗ. Основные этапы:

Этап 1. Отыскание начального опорного плана.

Этап 2. Проверка текущего опорного плана на оптимальность.

Этап 3. Переход к лучшему опорному плану.

Этап 1. Известны 2 основных метода отыскания начального опорного плана: метод северо-западного угла и метод минимальной стоимости.

В методе северо-западного угла каждый раз определяется максимальный объем перевозок, соответствующий северо-западной допустимой клетке таблицы. При этом, если необходи-

мо, полагаем xij = 0. Поясним на примере.

Ai/Bj	B 1	B 2	B 3	B 4	B 5	Запасы ai
A 1
A 2
A 3
A 4
Заявки bj						= 125

c = 1039

В методе минимальной стоимости каждый раз определяется максимальный объем перево- зок, соответствующий допустимой клетке таблицы с наименьшей стоимостью cij. Поясним на примере.

Ai/Bj	B 1	B 2	B 3	B 4	B 5	Запасы ai
A 1
A 2
A 3
A 4
Заявки bj						= 125

c = 745

В базис ввели 7 < m + n − 1 = 8 положительных переменных. Нужно ввести еще одну переменную, равную нулю, так, чтобы не образовался цикл. Например, x 42 = 0.

Этап 2. Проверка на оптимальность В методе потенциалов вводятся в рассмотрение двойственные переменные – потенциалы ui, i = 1 ,..., m, (дополнительный столбец в матрице ТЗ) и vj, j = 1 ,..., n, (дополнительная строка в ТТ).

Для клеток, соответствующих базисным переменным, должно выполняться

ui + vj = cij.

Вначале один из потенциалов можно выбрать произвольно, например, u 1 = 0, остальные подсчитать по формуле ui + vj = cij для клеток, соответствующих базисным переменным.

Ai/Bj	B 1	B 2	B 3	B 4	B 5	Запасы ai	Потенциалы ui
A 1	+ 10	− 148	+ 225		+ 9
A 2		+ 7	+ 8	+ 6			-3
A 3			+ 10	+ 8	+ 7		-1
A 4	+ 7	− 2 + 5	− 204	+ 6	+ 8		-1
Заявки bj						= 125
Потенциалы vj

Критерий оптимальности: если

∆ ij = cij− (ui + vj) ≥ 0 для всех клеток ТТ,

то построенный опорный план является оптимальным. В левый верхний угол каждой клетки ТТ, соответствующей небазисной переменной, запишем значение ∆ ij.

Этап 3. Переход к лучшему опорному плану Если существует ∆ ij < 0, то переходим

к лучшему опорному плану следующим образом.

Определяем переменную, которая будет введена в базис, и переменную, которая будет из него выведена. В базис введем переменную xi 0 j 0 такую, что

∆ i 0 j 0 = min { ∆ ij|∀i,j}.

Ai/Bj	B 1	B 2	B 3	B 4	B 5	Запасы ai	Потенциалы ui
A 1	+ 10				+ 9
A 2		+ 7	+ 8	+ 6			-1
A 3			+ 10	+ 8	+ 7
A 4	+ 7			+ 6	+ 8		-1
Заявки bj						= 125
Потенциалы vj

c = 721 − (8 + 4 − 5 − 5) · 14 = 693

Обозначим клетку (i 0, j 0) знаком “+”. Рассмотрим цикл, образованный этой клеткой и клетками, соответствующими базисным переменным. Припишем клеткам цикла знаки “+” и “-” так, что они чередуются при каком-либо обходе этого цикла. Вычислим

xi∗j∗ = Q = min {xij| клетка (i, j) отмечена “-” }.

Переменную xi∗j∗ выводим из базиса.

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

Пересчитываем новые объемы перевозок для элементов цикла:

xij = xij + Q, если клетка (i, j) помечена ”+”, и

xij = xij − Q, если клетка (i, j) помечена ”-”.

Для нового опорного плана определяем новые потенциалы и проверяем его на оптималь-

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

В нашем примере меняется лишь v 2 = 6. Все ∆ ij ≥ 0. Следовательно, построенное решение

оптимально.

Дата добавления: 2015-07-08