2. Проверка оптимальности транспортного плана методом потенциалов

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

Рассмотрим опорный план, построенный в таблице 2. Предположим, что мы хотим сделать свободную клетку (A₄, B₂) базисной клеткой или запланировать перевозку с четвертой базы во второй магазин. С этой целью запишем в клетку положительное значение, равное а еди­ниц:

Таблица 3

Базы	Магазины								Запас
	B1		B2		B3		A4
A1		7		3		4		2	15
							15
A2		6		1		4		6	31
			17–a		14+a
A3		6		9		5		3	25
	6+a				14–a		5
A4		10		4		7		9	22
	22–a		+a
Спрос	28		17		28		20

Тогда, чтобы сумма объемов перевозок в каждой строке остава­лась равной ее запасу, а в столбце – заявке, нужно

уменьшить на а единиц объем перевозки в клетке (A₄, B₁),

увеличить на а единиц объем перевозки в клетке (A₃, B₁),

уменьшить на а единиц объем перевозки в клетке (A₃, B₃),

увеличить на а единиц объем перевозки в клетке (A₂, B₃),

уменьшить на а единиц объем перевозки в клетке (A₂, B₂).

Таким образом, осуществляется «переброска» а единиц товара по замкнутому контуру, изображенному пунктиром в таблице 3. Такой контур называется циклом.

Цикл — это замкнутая ломаная, соединяющая несколько клеток таблицы и совершающая в каждой из них поворот на 90°. Две последовательные вершины цикла лежат либо в одной строке, либо в одном столбце. В одной из них объем перевозки увеличивается (в клетке ставится знак +), в другой — уменьшается на столько же единиц (в клетке ставится знак –). Примеры циклов различ­ных конфигураций показаны на рис. 1:

–	+				–	+				–	+
					+
		–	+					–
+			–				–	+		+	–

Рис. 1 Примеры циклов

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

Можно доказать, что для любой свободной клетки в опорном плане перевозок существует единственный цикл пересчета. Для того, чтобы одна из базисных клеток после переброски стала свободной, значение перевозки в этой клетке должно стать равным нулю. Ясно, что это может быть только клетка, в которой стоит знак (–). Поэтому количество товара, перебрасываемого по циклу пересчета, должно быть равно наименьшей из величин перевозок, стоящих в отрицатель­ных вершинах цикла. Например, если в таблице 3 положить а=min(22, 14, 17)=14, то, перебросив 14 единиц товара по ука­занному циклу пересчета, приходим к новому опорному плану:

Таблица 4

Базы	Магазины									Запас
	B1		B2		B3			A4
A1		7		3			4		2	15
								15
A2		6		1			4		6	31
			3		28
A3		6		9			5		3	25
	20							5
A4		10		4		7			9	22
	8		14
Спрос	28		17		28			20

Осталось уяснить, в каком случае переброска по циклу позво­ляет уменьшить суммарную стоимость всех перевозок.

Назовем ценой цикла, начинающегося в клетке (A_i, B_k), величину _ik, равную приращению сум­марной стоимости перевозок в результате переброски по циклу одной единицы товара. Цена цикла равна сумме стоимостей, стоящих в вершинах цикла, причем стоимость берется со знаком плюс, если перевозка от базы к магазину увеличивается (в клетке стоит знак +), и минус – в противном случае.

Например, цена цикла, изображенного пунктирной линией в таблице 3, равна:

₄₂ = 4 – 10 + 6 – 5 + 4 – 1 = – 2.

При переброске по циклу, начинающемуся в клетке (A_i, B_k), а единиц товара приращение суммарной стоимости перевозок равно

E=a_ik.

Очевидно, что улучшение плана происходит только в случае, если E < 0, а это равносильно тому, что _ik < 0.

При переходе к плану, приведенному в таблице 4, приращение суммарной стоимости перевозок равно

E= 14(–2) = –28,

то есть, значение целевой функции уменьшается на 28 единиц. Поскольку для первого плана суммарная стоимость перевозок равнялась E = 444, для нового плана будем иметь:

E= E+a₄₂ = 444 – 28 = 416.

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

Существует метод, который позволяет находить свободные клетки с отрицательной ценой цикла. Этот метод называет­ся методом потенциалов. Он состоит в следующем.

Предположим, что мы построили опорный план перево­зок. Сопоставим каждой базе A_i число _i и каждому магазину B_k число _k так, чтобы для любой базисной клетки плана выполнялось условие

i +k = cik.

(1)

Числа _i и _k называются потенциалами баз (строк) и магазинов (столбцов). Так как в опорном плане имеется т + п – 1 базисных клеток, то для нахождения потенциалов нужно решить систему из т + п – 1 уравнений с т + п неизвестными. Поскольку число неизвестных на 1 больше числа уравнений, значение одного потенциала можно выбрать произвольно (например, положить его равным нулю).

Рассмотрим опорный план, полученный в таблице 4. Составим систему уравнений для вычисления потенциалов, соот­ветствующих этому плану:

(2)

Выбирая, например, ₁=0, из (2) последовательно получаем:

₄=2, ₃=1, ₁=5, ₄=5, ₂=–1, ₂=2, ₃=2.

Обычно потенциалы записываются в дополнительных строке и столбце таблицы, в которой записан опорный план. Перепишем таблицу 4, заменив в ней стол­бец обозначений баз стол­бцом для потенциалов a_i и строку обозначений магазинов строкой для потенциалов b_k:

Таблица 5

Потенциалы баз	Потенциалы магазинов									Запас
	b1=5		b2=–1		b3=2			b4=2
a1=0		7		3			4		2	15
								15
a2=2		6		1			4		6	31
			3		28
a3=1		6		9			5		3	25
	20							5
a4=5		10		4		7			9	22
	8		14
Спрос	28		17		28			20

На практике, как правило, система (2) для определения потенциалов строк и столбцов не выписывается. Для их нахождения поступают следующим образом:

в таблице, содержащей опорный план, ищут строку (столбец) с наибольшим количеством базисных клеток,

ее (его) потенциал полагают равным нулю,

используя соотношение (1) и стоимости базисных клеток, последовательно (визуально) определяют остальные потенциалы.

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

Назовем псевдостоимостью c_ik* клетки (A_i, B_k) сумму потенциалов, соот­ветствующих этой клетке

c_ik* = _i +_k.

Очевидно, что для базисных клеток c_ik*=c_ik. Можно доказать, что для любой свободной клетки (A_i, B_k) в опорном плане перевозок справедливо равенство

_ik = c_ik – c_ik*,

где _ik – цена цикла пересчета для клетки (A_i, B_k). Отсюда следует, что если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, то цена цикла пересчета для этой клетки отрицательна, и план можно улучшить.

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

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

Проверим оптимальность рассматриваемого опорного плана. Рассчитаем псевдо­стоимости свободных клеток и запишем их в левом верхнем углу свободных клеток таблицы 5:

Таблица 6

Потенциалы баз	Потенциалы магазинов									Запас
	b1=5		b2=–1		b3=2			b4=2
a1=0	5	7	–1	3	2		4		2	15
								15
a2=2	7	6		1			4	4	6	31
			3		28
a3=1		6	0	9	3		5		3	25
	20							5
a4=5		10		4	7	7		7	9	22
	8		14
Спрос	28		17		28			20

Проверим условие оптимальности плана, сравнивая псевдостоимости и стоимости свободных клеток (для базисных клеток они по построению совпадают). Поскольку в клетке (A₂, B₁) псевдостоимость превышает стоимость, план, записанный в таблице 6, не оптимален.

Построим цикл пересчета для этой клетки:

Таблица 7

Базы	Магазины									Запас
	B1		B2		B3			A4
A1		7		3			4		2	15
								15
A2		6		1			4		6	31
	+a		3–a		28
A3		6		9			5		3	25
	20							5
A4		10		4		7			9	22
	8–a		14+a
Спрос	28		17		28			20

Используя данные таблицы 6, найдем цену цикла:

₂₁ = c₂₁ – c₂₁* = 6 – 7 = – 1.

Определим величину перевозки по новому маршруту: а=min(8, 3)=3.

Таким образом, клетка (A₂, B₁) становится базисной, а клетка (A₂, В₂) – свободной. Выпишем новый план перевозок:

Таблица 8

Базы	Магазины								Запас
	B1		B2		B3		A4
A1		7		3		4		2	15
							15
A2		6		1		4		6	31
	3				28
A3		6		9		5		3	25
	20						5
A4		10		4		7		9	22
	5		17
Спрос	28		17		28		20

Вычислим стоимость полученного плана:

E= E+a₂₁ = 416 – 3 = 413.

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

Таблица 9

Потенциалы баз	Потенциалы магазинов									Запас
	b1=0		b2=–6		b3=–2			b4=–3
a1=5	5	7	–1	3	3		4		2	15
								15
a2=6		6	0	1			4	3	6	31
	3				28
a3=6		6	0	9	4		5		3	25
	20							5
a4=10		10		4	8	7		7	9	22
	5		17
Спрос	28		17		28			20

Поскольку в клетке (A₄, B₃) псевдостоимость превышает стоимость, транспортный план не оптимален.

Построим цикл пересчета для этой клетки:

Таблица 10

Базы	Магазины								Запас
	B1		B2		B3		A4
A1		7		3		4		2	15
							15
A2		6		1		4		6	31
	3+a				28–a
A3		6		9		5		3	25
	20						5
A4		10		4		7		9	22
	5–a		17		+a
Спрос	28		17		28		20

Используя данные таблицы 9, найдем цену цикла:

₄₃ = c₄₃ – c₄₃* = 7 – 8 = – 1.

Определим величину перевозки по новому маршруту:

а=min(28, 5)=5.

Таким образом, клетка (A₄, B₃) становится базисной, а клетка (A₄, В₁) – свободной. Выпишем новый план перевозок:

Таблица 11

Базы	Магазины								Запас
	B1		B2		B3		A4
A1		7		3		4		2	15
							15
A2		6		1		4		6	31
	8				23
A3		6		9		5		3	25
	20						5
A4		10		4		7		9	22
			17		5
Спрос	28		17		28		20

Вычислим стоимость полученного плана:

E= E + a₄₃ = 413 – 5=408.

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

Таблица 12

Потенциалы баз	Потенциалы магазинов									Запас
	b1=0		b2=–5		b3=–2			b4=–3
a1=5	5	7	0	3	3		4		2	15
								15
a2=6		6	1	1			4	3	6	31
	8				23
a3=6		6	1	9	4		5		3	25
	20							5
a4=9	9	10		4		7		6	9	22
			17		5
Спрос	28		17		28			20

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

является оптималь­ным. Стоимость плана x (минимальные транспортные издер­жки) равна 408.

Задания для контрольной работы

В контрольную работу по математическому программированию входят две задачи. Номер выполняемого варианта совпадает с последней цифрой студенческой зачетной книжки. Если эта цифра 0, выполняется 10 вариант.

 1 Задача планирования товарооборота

П ри продаже товаров А и В используется три вида ресурсов: R₁, R₂, R₃. Сведения о количестве ресурсов, необходимых для продаж и единицы каждого товара, обеспеченности торго­вого предприятия этими ресурсами и ценах, по которым товары продаются, приведены в следующей таблице:

	Товары
Ресурсы	A	B	Запас ресурсов
R1	a1	b1	c1
R2	a2	b2	c2
R3	a3	b3	c3
Цена товара	p1	p2

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

• Полученную задачу математического программирования решите

• геометрически,

• симплекс-методом.

Номер варианта	Технология продажи товаров		Запас ресурсов	Цены товаров
	(a1, a2, a3)	(b1, b2, b3)	(c1, c2, c3)	(p1, p2)
1	2 4 2	1 5 4	120 280 200	3 4
2	1 6 0	2 2 3	30 60 42	3 4
3	1 4 1	2 2 0	80 140 30	3 2
4	3 5 2	2 2 6	42 60 84	8 7
5	1 2 0	2 1 1	70 80 30	9 6
6	1 3 1	2 2 4	12 24 20	3 4
7	1 5 4	6 2 2	620 600 500	11 5
8	3 1 3	2 6 4	600 720 720	11 9
9	5 2 3	2 6 2	600 960 390	11 9
10	1 1 5	1 0 2	210 100 600	10 5

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

Решите транспортную задачу, условия которой представлены ее матрицей:

Номер варианта	Матрица транспортной задачи
1
2
3
4
5
6
7
8
9
10

Оглавление

§1. Математическая формализация оптимизационной проблемы	4
§2. Геометрическая интерпретация стандартной задачи линейного программирования	10
§3. Симплекс-метод	13
§4. Постановка транспортной задачи	20
§5. Алгоритм решения транспортной задачи	23
Задания для контрольной работы	38

Подписано в печать 17.11.2004 г. Зак. № Тир. 500 экз. Объем 2,5 п.л. Бумага офсетная. Формат 60x80/16. Печать офсетная.

Типография ТЭИ 194021, Санкт-Петербург, Новороссийская ул., 50.