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

 

Имеется n пунктов производства и m пунктов потребления некоторого однородного продукта. Заданы объемы производства a[i], iÎ [1..n], в каждом пункте производства и размеры спроса b[j], jÎ [1..m] в каждом пункте потребления. Известны также транcпортные расходы c[i, j], связанные с перевозом единицы продукта из пункта i в пункт j. Требуется определить объемы перевозок x[i, j] из i -го пункта в j -ый для всех iÎ [1..n], jÎ [1..n], при минимальных общих транспортных издержках, при этом весь груз из пунктов производства должен быть вывезен, и весь спрос в пунктах потребления должен быть удовлетворен.

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

L(x)= S {с[i, j]´ x[i, j] | iÎ [1..n], jÎ [1..n]} ® min

при ограничениях

S { x[i, j] | jÎ [1..m]} = a[i] для всех iÎ [1..n], (5.6)

S { x[i, j] | iÎ [1..n]} = b[j] для всех jÎ [1..m], (5.7)

x[i, j]³ 0, для всех iÎ [1..n], jÎ [1..m]. (5.8)

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

S { a[i] | iÎ [1..n]} = S { b[j] | jÎ [1..m]}, (5.9)

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

S { a[i] | iÎ [1..n]} ³ S { b[j] | jÎ [1..m]}, (5.10)

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

b[j1]= S{ a[i] | iÎ [1..n]} - S{ b[j] | jÎ [1..m]}.

Для всех iÎ [1..n] с[i, j1] полагают равным достаточно большому числу. Аналогично, если

S{ a[i] | iÎ [1..n]} £ S{ b[j] | jÎ [1..m]}, (5.11)

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

Транспортные задачи, в которых выполняется соотношение (5.9) называют замкнутыми, в случаях (5.10-5.11) открытыми.

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

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

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

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

Конец алгоритма.

 

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

 

	j	1	...	j	...	m
i	b[j] a[i]	b[1]	...	b[j]	...	b[m]	b[j] u[j]
1	a[1]	...	...	...	...	...	u[1]
2	a[2]	...	...	...	...	...	u[2]
... ... ...	... ... ...	... ... ...	... ... ...	... ... ...	... ... ...	... ... ...	... ... ...
i	a[i]	...	...	...	...	...	u[i]
... ... ...	... ... ...	... ... ...	... ... ...	... ... ...	... ... ...	... ... ...	... ... ...
n	a[n]	...	...	...	...	...	u[n]
	a[i] v[j]	v[1]		v[j]		v[m]	u[j] v[j]

 

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

 

c[i, j]	x[i, j]
d[i, j]	q

 

Описание позиций d[i, j] и q будет приведено ниже.