Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл (16,20Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 231

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

14.1.	ПОЛНОСТЬЮ	ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ	303
Ш а г 2. Выбрать К >		0 (правило выбора будет описано даль
ше) и написать	внизу таблицы дополнительную строку

Эта строка выбирается в качестве ведущей.

Ш а г 3. Провести шаг двойственного симплекс-метода, вычерк нуть дополнительную строку и вернуться к шагу 1 .

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

Если а00 уменьшается, то уменьшается на целое число, поскольку

все числа остаются целыми, и, следовательно, через конечное

число шагов а00 станет меньше х0. Если алгоритм	бесконечен,
то п00 должно оставаться неизменным для всех t > t0.	Рассмотрим

тогда компоненту а10 столбца а„. Если а10 уменьшается, то на целое число. Когда а10 становится отрицательным, первая строка

должна быть выбрана в качестве производящей. Если а1;- ^ 0 для всех j, то задача неразрешима. Если же a{j <С 0 для некоторого ;, то в дополнительной строке

нее гарантируется правилом выбора Л.) Итерация с выбранной ведущей строкой строго увеличит ai0. Поскольку cc[) > a j + 1, должно уменьшиться, что противоречит предположению о неизмен

ности б 00 для	t >	t0.	Поэтому а10 (если алгоритм бесконечен)
должно стать постоянным для				всех £><i,	где tx> ta. Аналогич
ные рассуждения можно провести и для					второй, третьей и т. д.
компонент вектора		а 0-	Таким	образом,	после	конечного числа
шагов все а;0 (г =	1 ,	.. .,	п + т) станут неотрицательными целыми. н
Теперь опишем правило выбора К в шаге 2 полностью цело
численного алгоритма.			Пусть	производящая		строка имеет вид

х= а0+ 2 aJ( —xi)

идополнительная строка

304	14. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ а л г о р и т м

Для любого а, <С 0 всегда можно выбрать Я достаточно большим,

чтобы — 1. Согласно лексикографическому двойственному

симплекс-методу, ведущий столбец a s выбирается по правилу

- 1	= min	— 1	х)	( a j < 0 ) .
[в«Д] “ s	i	К-A] щ
Поскольку [а8/Я] ==— 1 и [%/Я] —отрицательные целые,					т. е. — 1,
— 2 , . . ., — [xj, имеем
	«3 V	«/•	V_«7_		( И )
	1

Таким образом, a s должен быть лексикографически минималь ным столбцом. Последнее означает, что среди всевозможных столбцов (с a V j < L 0 ) ведущий столбец должен быть лексикографи

чески минимальным вне зависимости от того, какое значение Я выбирается.

Теперь рассмотрим два значения Я, при каждом из которых

выполняется условие	[asAi] = — 1	и [ а в/ Я 2 ] = — 1. Столбец а 0
изменяется следующим образом:
< n =	a< + [^ g - ]« ;	(Яг = Я1( Яг).

Следовательно, чем меньше Я, тем сильнее лексикографически уменьшится нулевой столбец. Значение Я следует выбирать так, чтобы, во-первых, ведущий элемент стал равным — 1 и, во-вторых,

чтобы Я давало максимальное уменьшение столбцу а0. Правило формулируется следующим образом.

Ш а г	0.	Пусть строка с номером v является производящей.
Ш а г	1.	Пусть		a s — лексикографически минимальный стол
бец среди столбцов с aVj <					0 .
Ш аг	2.	Для	каждого		ав]-< 0	пусть р.;— наибольшее целое,
		v ai	■
такое, что a s -<			■
Ш аг	3 .	Пусть		Г ~~a°J I = pj,		а Kj— —	(строка v — про-
изводящая).		Тогда		L A j	J		Ц]
изводящая).		Тогда

у«7

“s ^

^ Минимум берется в лексикографическом смысле.— Прим, перев.

14.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ		305
Ш а г 4. Положить X — max Xj для	avj <С 0.
з	позволяет сделать веду
Правило выбора X, описанное выше,	позволяет сделать веду

щий элемент равным —1 , при этом будет сохраняться двойствен

ная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться. Следует заметить, что отсечение Гомори не является самым «сильным» возможным неравенством. Оно также может быть «сильнее» или «слабее» самого производящего неравенства. Например, пусть производя

щей	строкой		будет
			х = —4 — 3 (—ц )			-	5 { - х 2).			(12)
Если	использовать			X =	2, получим		отсечение
			s =	—2 — 2 (—zj) -		3 ( ~ х 2) >			0.	(13)
Для X =		3 имеем
			s =	<-т-2 — 1 (—а*) -		2	(—х2)	>	0.	(14)
Для X =		4
		.	s =	- 1 -	l 7 - z j ) -	2	( - х 2)	>	0.	(15)

Как видно, неравенство (14) сильнее, чем (12), (12) сильнее,

чем (13), а (13) сильнее, чем (15).

Другое замечание касается того, что если величина X, полу чаемая указанным выше способом, может быть увеличена так, чтобы [а0/А,] и [a,jlX] (aj > 0) оставались без изменения, то отсече

ние Гомори можно усилить, несмотря на то, что нулевой столбец уменьшится на ту же величину.

Выпишем производящую строку

X = d 0 + 2	d j { — X j ) + 2 а 'з ( —хз)‘	(16)
а * < 0	а '. > 0
j	о

Чем больше величина X, тем меньше абсолютная величина коэффи циентов отсечения. Естественно, что мы хотели бы иметь абсо лютную величину [a„MJ большой, а абсолютные величины [а;-Ш — малыми. Если значение X (полученное по приведенному выше правилу) может быть увеличено так, чтобы значения [aj/X] и [а0М,]

не изменялись, то используется большее значение для X. Тем самым по возможности уменьшится абсолютная величина [а;/Х] для некоторых /, и отсечение станет сильнее.

Например, пусть целевая функция имеет вид

X q

2 0 — х1

2 х 2 — Зх2

и производящая строка

х = —20'+ (—7) (—Xi) + (—8) (—х 2) + (—15) (—х 3) + 18 (—ж4).

20 Т. Ху

306 14. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ а л г о р и т м

Используя описанную выше процедуру выбора X, получим X — 7. Соответствующее отсечение

s = —3 + х4 + 2х2 + Зх3 — 2х4 ^ 0.

Если использовать X = 9 вместо' X = 7, получим отсечение s* = —3 + х4 + х2 + 2 х3 — 2х4 ^ 0 ,

являющееся более сильным (см. [214]).

Интересная особенность полностью целочисленного алгоритма состоит в том, что для его использования не обязательно требовать целочисленности всех аг^. Пусть задача целочисленного програм мирования имеет вид

максимизировать ,

			П
Хо =		Поо	2!
•при условиях			i=l
•при условиях
п
Xn+i — Q-iO 2	a U x i		^ 0 0 = 1 > • • • i m ')i
J= 1		0 = 1,
X j >	о	0 = 1,

где o-oo и Cj — целые, ai0 и atj могут быть произвольными действи тельными числами. Таблица 14.1 содержит в первых п + 1 строках только целые числа.

		Таблица 14.1
		—Я*1	Д?2	• • •	хп
^0	а оо	си	с2->	* ■*»	сп
X i	0	— 1
х 2	0		— 1
хп	6			’	- 1
хп+1	а 10
	•		a ij
хп+т	ато

Выпишем произвольную производящую строку (опуская обо значение строки)

х == ао	2 а1( —xj)"
Вне зависимости от того, являются ли а0 и		целыми или дей
ствительными, коэффициенты	отсечения

-[* ]+ 2 [*](-*л

14.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

307

всегда целые, а ведущий элемент равен —1. В результате итера ции с таким ведущим элементом первые п + 1 строк таблицы

останутся целочисленными. Заметим, что переменная s — неотри цательная целая. В силу приведенных рассуждений доказатель ство конечности в данном случае мало чем отличается от описан ного выше. Когда в нулевом столбце ai0 (i = 1, . . ., п) становятся неотрицательными целыми, а остальные элементы нулевого столб ца — неотрицательными, то получается оптимальное решение.

В последних главах были обсуждены два алгоритма целочис ленного программирования, первый из которых называется цик лическим алгоритмом Ц = 1 ), а второй — полностью целочис

ленным (X > 1). В приведенной ниже таблице перечислены раз личия этих алгоритмов.

Циклический алгоритм

Полностью целочисленный алгоритм

В исходной таблице все aij цело численные

at- ф 0 (mod 1) в текущей таблице

Для получения оптимума ЛП ис пользуется прямой или двойствен ный симплекс-метод. Затем исполь зуется двойственный симплекс-метод

Строка с индексом г становится про изводящей, если diо —нецелое

Ведущей строкой является

s = /о 2 / 7 ( xj)’

0 < / о < 4 , 0 < / , < 1

Ведущий s-й столбец оцределяется из условия

1	v	1	aj
T	a s <	—	aj
Js		JJ

для всех /

В исходной таблице a-Lj могут быть действительными (a0j —должны быть целыми)

Если aij —целое в		исходной		табли
це,	то afj остается целым и			в по
следующих
На	протяжении	всех	вычислений
используется двойственный				симп
лекс-метод
Строка с индексом i		(i Ф	0) становится