6.2. Транспортная задача в матричной постановке.

Имеется mпунктов производства иnпунктов потребления некоторого однородного продукта. Заданы объемы производстваa_i, i=1,2,3,…,m, в каждом пункте производства и размеры спроса b_j,j=1,2,3,…,n в каждом пункте потребления. Известны также транcпортные расходыc_i,j, связанные с перевозом единицы продукта из пунктаi в пунктj. Требуется определить объемы перевозокx_i,j изi–го пункта вj–ый для всехi=1,2,3,…,m, j=1,2,3,…,n, при минимальных общих транспортных издержках, при этом весь груз из пунктов производства должен быть вывезен, и весь спрос в пунктах потребления должен быть удовлетворен.

Приведем математическую постановку транспортной задачи:

,	(6.6)
при ограничениях ,	(6.8)
	(6.9)
.	(6.10)

Транспортная задача имеет решение тогда и только тогда, когда выполняется соотношение :

,

(6.10)

т.е. объем производства должен быть равен объему потребления. В реальных задачах условие (6.10) часто нарушается, если имеет место соотношение

,

(6.11)

то в этом случае необходимо ввести в рассмотрение фиктивного (внешнего) потребителя j₁c

.

Для всех i=1,2,3,…,m полагают равным достаточно большому числу. Этот пункт иммитирует экспорт продукции. Аналогично, если

,

(6.12)

то вводится дополнительный (внешний) пункт производства i1.

Транспортные задачи, в которых выполняется соотношение (6.10) называют замкнутыми, в случаях (6.11) (6.12) открытыми.

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

1.  Определяют исходное базисное решение.

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

Опишем алгоритм решения транспортной задачи более детально. Запишем ее условия в таблицу следующего вида:

j=1

j=2

j=3

j=4

b1

b2

b3

b4

i=1

a1

u1

i=2

a2

u2

i=3

a3

u3

v1

v2

v3

v4

Будем называть клеткой (i,j) клетку, находящуюся на пересеченииi– той строки иj–го столбца. Каждую клетку (i,j) будем заполнять следующей информацией:

cij	xij
dij	

Описание позиций d_ijи будет приведено ниже.

Определение исходного базисного решения. Для определения исходного базиса можно использовать алгоритм северо–западного угла.

Алгоритм северо–западного угла.

1. k:=1; p:=1; (клетка (k, p) находится в северо–западном углу рассматриваемой таблицы)

2. x_kp:=min (a_k, b_p);a_k:= a_k– x_kp;b_k:= b_k– x_kp.

3. Если a_k=0, то вычеркиваем из таблицы k–ю строку, в противном случае (в этом случаеb_p=0) вычеркиваемp– ый столбец. Если одновременноa_k=b_p= 0, то вычеркиваем, либотолькостолбец, либотолькостроку.

4. Если в таблице все столбцы и все строки вычеркнуты, то алгоритм заканчивает работу, в противном случае в качестве (k, p) берем координаты клетки северо–западного угла получившейся таблицы и переходим к выполнению 2.

Клетки с заполненной информацией x_ijявляются базисными, все остальные внебазисные, для нихx_ij=0 (в целях наглядности для внебазисных переменных значенияx_ij=0 не заносятся). Среди базисных переменных может оказаться, что некоторыеx_ij=0 (при вырожденном базисе базисные нули заносятся обязательно). В этом случае базис вырожденный.

Чтобы убедиться в том, что исходный базис найден верно, проверьте:

1. Количество базисных клеток (переменных) должно быть равно n+m–1.

2. Должны выполняться ограничения (6.8) – (6.10).

Для проверки найденного решения на оптимальность необходимо вычислить потенциалы всех пунктов и производства, и потребления. Под потенциалами будем понимать числа u_i , i= 1,2,3,...,m, иv_j, j= 1,2,3,...,n, определяемые по формуле:

v_j=u_i+c_ij,

где клетка (i, j) базисная клетка.

Алгоритм расчета потенциалов

В данном алгоритме введен механизм пометок. Строка или столбец помечены знаком '+', если соответствующий потенциал найден, знаком '–' в противном случае.

В начале все строки и столбцы таблицы помечаем символом '–'

1 –ыйшаг.u₁:=0 , 1–ую строку помечаем символом '+' (это означает, что потенциал для данной строки найден ).

k –ый шаг.

a) Для каждой строкиi, помеченной символом '+', выполнить:

для каждого столбца j=1,2,3,...,nтакого, что клетка (i,j) базисная иj– ый столбец помечен символом '–'v_j :=u_i+c_ij, столбец помечаем символом '+'.

b) Для каждого столбцаj, помеченного символом '+', выполнить:

для каждой строки i=1,2,3,...,n такой, что клетка (i,j) базисная, иi–я строка помечена символом '–'u_i:=v_j–c_ij, строку помечаем символом '–'.

k –шагвыполняем до тех пор, пока все строки и столбцы не станут помеченными символами '+'.

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

Для того, чтобы базисное решение x_ij, i=1,2,3,...,m,j=1,2,3,...,n, было оптимальным, необходимо и достаточно, чтобы для всехi=1,2,3,...,m, j=1,2,3,...,nбыло справедливо неравенствоd_ij=v_j–u_i–c_ij0.Таким образом, для проверки найденного решения на оптимальность достаточно выполнить следующий алгоритм

1. Для всех i=1,2,3,...,m, j=1,2,3,...,n положитьd_ij=v_j–u_i–c_ij.

2. Найти такие (k, p), чтоd _kp =max{ d_ij| i=1,2,3,...,n, j=1,2,3,...,m }

3. Если d_kp0, то полученное базисное решение является оптимальным и транспортная задача решена, иначе необходимо перейти к новому базису.

Алгоритм перехода к новому базису.

Вводим в базис клетку (k, p).Для определения клетки (q,l), выводимой из базиса, воспользуемся следующим алгоритмом:

1. Строим последовательность клеток

П={(i₁, j1), (i₂, j₂),...(i, j),... )} такую, что

a) (k,p)П;

b) все остальные клетки базисные;

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

2. Задаем направление обхода этого цикла, совпадающего с направлением kp. В клетку (k, p) заносим символ '+'. Для остальных клеток (i, j)П, если направлениеijсовпадает с направлением обхода цикла с направлением обхода цикла, то заносим в позициюсимвол '+', в противном случае заносим '–' .

3. Определяем клетку (q,l), для которойх(q,l)=min x_ij , где (i,j) – пробегает все клетки изП, помеченные символом '–'.

Полагаем Q=x(q,l).Из базиса выводится клетка (q,l).

4. Для всех (i,j)П, если клетка помечена символом '+', то полагаемx_ij=x_ij+Q, в противном случае x_ij=x_ij–Q.

5. Перейти к выполнению проверки критерия оптимальности.

Замечание 1. Иногда минимум достигается на нескольких клетках одновременно. В этом случае в качестве клетки (q,l) выбирается произвольно только одна из них.

Замечание 2. При заполнение таблицы для нового базиса значенияx_ijвносятся только в базисные клетки.

Пример.Рассмотрим пример, в котором требуется решить транспортную задачу методом потенциалов. Значенияa_i, b_j,c_ij (i=1,2,3, j=1,2,3,4), заданы в таблице

			j=1		j=2		j=3		j=4
			b1		b2		b3		b4
			10		16		14		12
i=1	a1	11	2		7		6		4			u1
i=2	a2	17	6		4		3		3			u2
i=3	a3	24	5		6		3		7			u3
			v1		v2		v3		v4

Начинаем с определения исходного базиса методом северо–западного угла. Таковым является клетка (1,1), для нее x₁₁=min (11,10)=10, это число заносим в эту клетку. Изменяемa₁ иb₁. Так какb₁=0, затемняем столбецj=1.

			j=1		j=2		j=3		j=4
			b1		b2		b3		b4
			0		16		14		12
i=1	a1	1	2	10	7		6		4			u1
i=2	a2	17	6		4		3		3			u2
i=3	a3	24	5		6		3		7			u3
			v1		v2		v3		v4

В незатемненной части таблицы северо–западный угол (1,2), для нее x₁₂=min (1,16)=1, это число заносим в эту клетку. Изменяемa₁ иb₂. Так какa₁=0, затемняем строкуi=1.

			j=1		j=2		j=3		j=4
			b1		b2		b3		b4
			0		15		14		12
i=1	a1	0	2	10	7	1	6		4			u1
i=2	a2	17	6		4		3		3			u2
i=3	a3	24	5		6		3		7			u3
			v1		v2		v3		v4

Продолжая аналогично далее, получим следующую таблицу:

			j=1		j=2		j=3		j=4
			b1		b2		b3		b4
			10		16		14		12
i=1	a1	11	2	10	7	1	6		4			u1
i=2	a2	17	6		4	15	3	2	3			u2
i=3	a3	24	5		6		3	12	7	12		u3
			v1		v2		v3		v4

В ней восстановлены значения a_i,b_j, а также затемнены базисные клетки. Значение функционала на этом решении будет равно

F=210+71+415+32+312+712=213.

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

1.,

2. Число базисных клеток должно быть равно n+m–1.

Расчет потенциалов и проверка критерия оптимальности, переход к новому базису

Для базисных переменных должно выполняться v_j:=u_i+c_ij.Положимu₁=0, тогда по этой формуле по клетке (1,2)v₂=0+2=2, по клетке (1,2)v₂=0+7=7. Из клетки (2,2)u₂=7–4=3. Продолжая аналогичным образом, получим информацию, приведенную в следующей таблице

			j=1		j=2		j=3		j=4
			b1		b2		b3		b4
			10		16		14		12
i=1	a1	11	2	10	7	1	6		4		0	u1
			0				0		6
i=2	a2	17	6		4	15	3	2	3		3	u2
			–7		0
i=3	a3	24	5		6		3	12	7	12	3	u3
			–6		–2		0		0
			2		7		6		10
			v1		v2		v3		v4

Подсчитываем значения d_ijпо формулеd_ij=v_j–u_i–c_ij и заносим в таблицу. Для базисных клетокd_ij=0. В клетке (1,4)d_ij>0, поэтому включаем эту клетку в базис, но нам нужно определить клетку, выходящую из базиса. Выполним это на следующей таблице, в ней клетка (1,4) затемнена. Легко видеть, что затемненные клетки образуют цикл (1,4)(3,4)(3,3)(2,3)(2,2,)(1,2)(1,4)

			j=1		j=2		j=3		j=4
			b1		b2		b3		b4
			10		16		14		12
i=1	a1	11	2	10	7	1	6		4	«+»	0	u1
			0			«–»	0		6
i=2	a2	17	6		4	15	3	2	3		3	u2
			–7		0	«+»		«–»
i=3	a3	24	5		6		3	12	7	12	3	u3
			–6		–2		0	«+»	0	«–»
			2		7		6		10
			v1		v2		v3		v4

Заносим в позицию  клетки значения «+» и «–». В каждой строке и в каждом столбце их должно быть ровно по одному значению. Начинаем с клетки (1,4), далее идет чередование. В соответствии с этим, положимx_1,4=x_1,4+Q, x _3,4=x _3,4– Q, x_3,3=x_3,3+ Q, x_2,3=x_2,3–Q, x_2,2=x_2,2+ Q, x _1,2=x _1,2– Q.Увеличиваем значение от нуля до значения, когда одна из этих переменных обратится в 0, это будет приQ=min(x₃₄, x₂₃, x₁₂)=1. Этот минимум достигается на клетке (1,2), поэтому она исключается из базиса (если минимум достигнут на нескольких клетках, то исключается из базиса только одна). Выполним преобразования и данные внесем в таблицу

			j=1		j=2		j=3		j=4
			b1		b2		b3		b4
			10		16		14		12
i=1	a1	11	2	10	7	0	6		4	1		u1
i=2	a2	17	6		4	16	3	1	3			u2
i=3	a3	24	5		6		3	13	7	11		u3
									0
			v1		v2		v3		v4

Значение функционала на этом решении будет равно

F=210+41+416+31+313+711=191.

Этот алгоритм повторяем до тех пор, пока не окажется, что все значения d_ij0. Оптимальным решением будут значенияx_ijпоследней таблицы.