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

Скачать файл
Заказать решение

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

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

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

Добавлен: 15.10.2024

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

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

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

336

 

ГЛ.

16.

ЦЕЛОЧИСЛЕННОЕ

ПРОГРАММИРОВАНИЕ

 

Применив

это

преобразование

к

линейной

форме а00—a0ix1 —

— d02x2— . .. — а0пхп,

получим

 

 

 

 

 

 

 

 

 

 

^ 00

a 0iX i .

*

• •

&or%r

•

• •

 

&0n%ni

 

где

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

« 0 0

— « 0 0

 

Po«Orj

 

 

 

 

 

 

 

 

 

 

«о; = a 0j

+ P j d o r

(для

j Ф

 

г ) ,

(2)

 

 

 

 

aor —

г»

 

 

 

 

 

 

 

 

 

Заметим,

что

если

pj

и

a0j

 

( /=

0, 1,

п) —целые,

то

д0у- (/ = 0 , 1 ,

. . ., п) —тоже целые.

 

 

 

 

 

Квадратичная

форма —6S (asixi + . . . +

asnxn)2 после преобразо­

вания

(1)

перейдет в

— bs (aSiX1-\-

.. . -\-азпхпф p0aSr)2, где

 

 

 

 

 

a Sj

=

a sj

+ a STP i

(для

/ Ф

г ) ,

(3)

 

 

 

 

&sr — &sr*

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Или, переписав более подробно, получим

 

 

 

— bs (asix i

 

 

dsnx n

p0dsr)2 =

 

— bs ( f l s i ^ i

- | -

 

4

• • ■^ ds„xn)2— 2bsp0asr (drlxl +

. . . ±

asnxn) — bs {p0dsr)2-

(4)

Уравнение (4) выражает результат преобразования (1), произ­ веденного над одной строкой, т. е. —bs (Ls (х))2. Для того чтобы выразить параболическое ограничение типа (8 ) в § 16.1 через

новые переменные xj, воспользуемся таблицей 16.3, где

 

 

 

h

 

^

 

 

 

ао о ~ аоо— 2 bs (Poasrf,

 

 

 

 

$=1

 

 

 

 

 

 

 

 

k

 

 

 

 

 

a'oj =

aoj — 2

2

bsp0dSTaSj

(/ = 1,

(5)

 

 

 

S = i

 

 

 

 

&ij =

dij

(£,

j =

1,

• • • j

 

 

 

 

 

 

Таблица 16.3

 

 

1

- X i

—

x2

. ..

...

xn

 

 

a '00 a'01

a'02

. ..

••• “On

 

 

0

a'

a'

...

■■■

“in

b i

 

 

и

 

12

 

 

 

0

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

0

ahl

a'h2

 

••• “ftn

b k

16.4. АЛГОРИТМ

337

Заметим, что a задаваемые соотношениями (2) и (3), получаются в том случае, когда все строки рассматриваются как линейные ограничения. Уравнения (5) восстанавливают таблицу в стандарт­ ном виде параболических ограничений типа (8 ) § 16.1.

16.4. Алгоритм

Алгоритм состоит из следующих шагов.

Ш а г 0. Начать с двойственно допустимой таблицы, подобной табл. 16.1. Каждое параболическое ограничение ранга к зани­ мает к + 1 строк, a ai0 (i = 1, . . ., к) равны нулю. Такая таб­

лица называется таблицей стандартного вида.

Ш а г 1. Если не существует ни одного отрицательного эле­ мента в.нулевом столбце, то текущее решение, получаемое посред­ ством приравнивания нулю всех небазисных переменных, является оптимальным. В противном Случае выбрать в нулевом столбце первый ^отрицательный элемент и использовать строку, в кото­ рой он стоит, в качестве производящей (производящей строкой может стать только линейная часть а00 — Ь0 (х) ^ 0 или линей­ ное ограничение, потому что в квадратичных частях все ai0 = 0 ).

Ш а г 2. Пусть а00 — aoixi — . . . — a0rx r — • • • — а опх п есть

производящая строка. Поскольку все условия в таблице выра­ жены через (—xj), имеем

 

 

 

 

<Хоо a0i а02 . • . йоп

 

 

Выбрать

среди

a0j <

0 элемент, стоящий

в лексикографически

минимальном столбце,

и этот столбец а тсделать ведущим. Пусть

p,j — наибольшее целое

число,

для которого

( — ) ау- >

а г.

Определим

 

 

 

 

' W >

 

 

 

 

 

 

 

 

 

 

X = max ^

^а°; ^

(а0;- < 0 ).

 

Заметим, что цг= 1 , и ведущий элемент всегда равен

— 1 .

Ш аг

3.

Получим

отсечение Гомори:

 

 

 

s =

[t

] — [ х ] Ж1—

•••+ * г — •• •— [ i r ] ^ ^ 0.

Это отсечение записать внизу таблицы в виде2

 

 

 

 

[?] И :.....-

1 -[т ]

 

22 т. ху

3 38

ГЛ. 16. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Ш а г 4. Использовать отсечение Гомори в качестве ведущей строки, а ведущим элементом взять (—1 ), после чего преобразовать

все строки так, как если бы это были линейные ограничения. Для параболического ограничения получим

^00

а01

• • • I

• ■■у

а 0п

 

«10

«11

• ■• >

• *• »

«1гс

bi

a h0

a h i

• ■• »

• * * j

«fen

bk

где ai0 (i

= 1 , . . .,

к) не могут быть

нулями.

Ш а г

5. Восстановить таблицу в

стандартном виде, исполь­

зуя соотношения (5)

из § 16.3. Вернуться к шагу 1.

16.5.Примеры

Решим два числовых примера, прежде чем дать доказатель­ ство конечности. Рассмотрим задачу

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

Z = — 3^! — Х 2

при условиях

—3 - (—6*! + 2х2) — ж* > О,

—16 — (—5xi

— 5х2) — (Xi — х2)2 ^ О,

хи

х2 ^ 0 (целые).

Запишем задачу :в табл. 16.4 (ч—и f обозначают производящую строку и ведущий столбец соответственно). После преобразования получается табл. 16.5. Чтобы восстановить таблицу в стандартной форме, вычислим

а'00= «оо — 2

 

( Р о « м ) 2 =

3 —

1 ( — 1 • l ) 2 = 2 ,

flot = «01 — 2

2

bsp0asl’asi =

—6 —2 - 1 ( — 1 ) (1 ) (1 ) = —4,

o-Q2 —« 0 2 — 2

^

bsPodsidsr — 2

2 * 1 (

l ) - l - 0 = 2 .

Подобным же образом для

второго параболического ограничения

 

аоо= —

1 1

— 1

( — 1 • 1 ) 2

= — 1 2 ,

 

«01= - 5

— 2 - 1

( — 1 )*1

2'= —3,

 

«о2 = —5 — 2 - 1 ( — 1 ) • 1 ( — 1 ) = —7.

После произведенных вычислений получаем табл. 16.6. Таблицы 16.7, 16.8 и 16.9 представляют последовательные

стандартные таблицы, причем табл. 16.9 является оптимальной.

 

 

Т а б л и ц а 1 6 . 4

 

 

 

 

Т а б л и ц а 1 6 . 5

 

1 ~ xi — х2

 

 

 

 

 

1

-S3

— х2

 

0

3

 

1

 

 

 

 

 

- 3

3

1

 

0

- 1

 

0

 

 

 

 

 

1

- 1

0

 

0

0

- 1

 

 

 

 

 

0

0

- 1

 

- 3

- 6

 

2

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

 

3

- 6

2

 

0

1

 

0

1

 

 

 

 

- 1

1

0

1

- 1 6 - 5

- 5

 

 

 

 

 

- 1 1

- 5

- 5

 

0

1

—1

1

 

 

 

 

- 1

1

- 1

1

- 1

- 1

 

0

 

 

 

 

 

0

- 1

0

 

 

t

столбец

 

 

 

 

 

 

 

 

Ведущий

 

 

 

 

 

 

 

 

 

 

Таблица 16.6

 

 

 

Таблица 16.7

 

 

 

 

1

 

- s 3

-^2

 

 

1

- s 3

- s 4

 

 

Z

 

- 3

 

3

1

 

z

- 5

2

1

 

 

х1

 

l

 

- 1

0

 

Xl

1

- 1

0

 

 

Х 2

 

0

 

0

-1

 

x2

2

1

- 1

 

 

н

.

2

 

- 4

2

 

Sl

- 2

- 6

2

Ч1—

 

 

 

0

 

1

0

1

 

0

1

0

1

 

S2

 

- 1 2

 

- 3

-7

-

s2

- 2

- 4

- 3

 

 

 

 

0

 

1 /

-1

1

 

0

■ 2

- 1

1

 

S4

 

- 2

 

- 1

-1

 

S5

- 1

- 1

0

 

 

 

 

 

 

 

t

 

 

 

t

 

 

 

 

 

Таблица 16.8

 

 

 

Таблица 16.9

 

 

 

 

1

 

- s 5

-s4

 

 

1

-Sg

- s 6

 

 

z -

 

- 7

 

2

1

 

z

- 8

2

1

 

 

X i

 

2

 

- 1

0

 

Xl

2

- 1

0

 

 

x2

 

1

 

1

1

 

x2

. 2

1

- 1

 

 

Si

 

3

 

- 4

2

 

Sl

1

- 4

2

 

 

 

 

0

 

1

0

1

 

0

1

0

1

 

S 2

 

- 2

 

4

7

-

S2

4

0

- 5

 

 

 

 

0

 

2

1

1

 

0

2

- 1

1

 

S 6

 

- 1

 

- 0 - - 1

 

s6

0

0

- 1

 

 

 

 

 

 

 

t

 

 

 

 

 

 

 

22*

340

ГЛ. 16. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Рассмотрим задачу целочисленного программирования: минимизировать

z = х\ + За:! + 2 х\

при условиях

 

 

 

х± + 2а:г — х3 ^

5,

—3xt +

х2

+ х 3 >

—2 ,

xlt х\,

х3 ^

0 (целые).

Для того чтобы преобразовать эту задачу в целочисленную задачу

спараболическим ограничением, введем новую переменную х4 =

=—w.

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

w = —а;4,

 

при условиях

 

—5 — (—X! — 2 а:2 + х3) > 0 ,

2 — (За?! — хг — а:3) ^

0 ,

Xi — xl — За;! — 2 а:! >

0 .

 

Таблица 16.10

 

 

1

Таблица 16.11

 

 

 

 

 

 

 

 

s 5

— х 2

- * 3

- * 4

0

0

0

0

+ 1

 

0

0

0

0 + 1

 

2

1

1

1 - 1

 

-1

1

0

1 -1

 

0 - 1

0

0

0

 

3 -1

1

0

0

0

0

- 1

0

0

 

0

0 -1

0

0

0

0

0

- 1

0

 

0

0

0 -1

0

0

0

0

0 - 1

 

0

0

0

0 -1

 

- 5

- 1

- 2

+ 1

0

 

- 2 -1

-1

0

0

-

2

3

- 1

- 1

0

 

- 7

3

- 4

-1

0

 

0

0

0

0 - 1

 

0

0

0

0 -1

 

0

1

0

0

0

1

- 3

1 -1

0

0

1

0

0

1

0

0

3

0

0

1

0

0

3

0

0

0

1

0

2

0

0

0

1

0

2

- 3

- 1

- 1

0

0

 

0 -1

0

0

0

 

 

t

 

 

 

 

 

t

 

 

 

 

Смотрите также файлы