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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

15.3. ПРИЛОЖЕНИЯ

323

при условиях

щ4н2 2 и3^ 5,

 

щ, щ, и3^ 0 .

 

 

 

 

Решением ее является и4 = 5 ,

ц2 = 0, и3

=

0, 2щ + 8 н2

+

Зн3

=

= 10. Так как 10 =

z — (2,

2) у =

12

— 2>1 — 2-10 =

10,

то

решение оптимально.

Подставляя z/t

= 1,

у2 = 0 в (9),

получим

минимизировать

при условиях

~ 1 “

4

_ 2 _

Ъх

“

2 "

х ^

00

1 СО 1

Решением будет х = 2 , Ъх = 5-2 =

1 0 , как и предполагалось,

Оптимальным решением задачи (8 )

является х = Я* г/Л= 1 ,

г/ 2 = 0 и z* = 1 2 .

 

1 5.3. Приложения

В этом параграфе будут приведены некоторые задачи, которые могут быть сформулированы как задачи целочисленного програм­ мирования. Они могут служить примерами, иллюстрирующими стандартные методы превращения задач в задачи целочисленного

программирования.

Более подробно

об

этом можно прочитать

у Балинского [6 ] и

Данцига [33],

[34].

Многие целочисленные

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

Эдмондс [54], [55], [56], Витцгалл и Зан [216] х). Другим классом являются так называемые задачи о рюкзаке, которые будут обсуждены в гл. 18.

Как было показано в части 1, оптимальное решение задачи линейного программирования отнюдь не обязательно целочислен­ но, и в то же время существует много задач, природа которых требует целочисленности решения. Некоторые из этих задач на первый взгляд не являются задачами целочисленного • про­ граммирования, однако они могут быть сформулированы как таковые. Если требуется, чтобы только некоторые переменные были целочисленными, то задача называется задачей смешанного программирования (см. § 15.1, 15.2).

В этом параграфе будут обсуждены как раз некоторые из клас­ сов таких задач, которые можно представить в виде задач цело-

J) См. также К орбут и Финкельш тейн [9 *].— П р и м . р е д .

21*

324 ГЛ. 15. СМЕШАННЫЙ АЛГОРИТМ

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

К первому классу относятся задачи, в которых некоторая пере­ менная может принимать лишь конечное множество значений. Например, грузоподъемность грузовика может иметь лишь опре­

деленное

стандартное

значение.

 

которые

может принимать

Пусть

Ъп ,

. . .,

bih — значения,

переменная xj.

Тогда в задаче

 

 

 

 

 

X1 =

 

+ 6 2&12

+ •

• • +

 

 

 

 

 

6 i + . . • + бй = 1 .

 

 

 

6 г ^

О

(целые)

(г =

1, . . .,

к).

Переменная Xj может принимать лишь указанные значения. Такой же метод можно использовать, когда х представляет собой векторную переменную, принимающую значения из конечного множества векторов. Если bj, . . ., ЬА— возможные значения переменной х, то задачу можно записать как

х =

8 ^ +

. . . +

8 i + . . . + 6 ^ = 1 ,

8 ; ^ 0

(целые)

(г = 1 , . . ., к).

Ко второму классу относятся такие задачи, в которых не тре­ буется, чтобы ограничения выполнялись одновременно, в отличие от задач линейного программирования, где необходимо учитывать сразу все ограничения. Каждое ограничение определяет полупро­ странство, которое является выпуклым множеством. Множество решений, будучи пересечением всех полупространств, также выпукло. Если не требуется, чтобы все ограничения выполнялись одновременно, то множество решений может быть объединением некоторых выпуклых множеств и в силу этого может быть невы­ пуклым и даже несвязным. Рассмотрим множество решений сле­ дующей задачи:

найти максимум

 

 

 

 

Xi +

х2

 

 

 

на множестве X

=

Xi

(J Х 2,

 

 

 

 

 

где

=

{х

| 3xi

+

хг <

4;

 

х2 >

0},

Xi

Xi,

Х 2

— {х

| 2xi

+

Зх2

5;

Xi,

х2 ^

0'}.

Множество решений изображено невыпуклой затененной обла­ стью на рис. 15.3.

15.3. ПРИЛОЖЕНИЯ

325

Для того чтобы сформулировать эту задачу как задачу цело­ численного программирования, нужно знать какую-нибудь верх­ нюю границу величин 3xi + х2 — 4 и 2х4 + Зх2 — 5 на множестве

решений. Такую границу нетрудно получить. Достаточно взять

некоторое большое положительное число, в нашем случае, скажем, 100. Теперь можно сформулировать задачу в следующем виде:

найти максимум

X! X2

при условиях

3xi + х2 — 4 — 1006 ^ 0,

2Х! + 3;г2 — 5 — 100 (1 — 6) < 0,

 

 

xi,

х2 ^ 0 ,

0 <

6 < 1 (целое).

 

Заметим, что

если

6 = 1 ,

то первое ограничение выполняется,

поскольку 3 ^ 1

+

х 2

— 4 ^

100, а второе примет вид 2 x t

+ З х 2 —

— 5 ^ 0 . Если 6 = 0 ,

второе ограничение выполняется,

а первое

превратится в

3

x i

+

х 2 — 4 ^ 0 .

Заметим также, что

если на

переменную 6 не наложено условие целочисленности, то множе­

ство решений с компонентами x l t х 2 и 6

выпукло.

(J

Если множество решений задается

как

{х | gi (х) ^ 0 }

(J (х ) g 2 (х) ^ 0 ), то нужно знать нижнюю

границу для gi

(х),

скажем Zj, и нижнюю границу g2 (х), скажем 12, на этом множе­ стве. Тогда множество решений можно описать как

gi(x) — Д6 > 0 , |Г2 (х) — /26 ^ 0 ,

0 ^ 6 ^ 1 (целое).

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

326

ГЛ. 15.

СМЕШАННЫЙ АЛГОРИТМ

 

 

ограничения имеют вид gi(x);> 0 , . . . , g m( x ) ^ О,

gm+1 (x)sc;0 , . . .

. . . , g p ( x ) ^ 0 , и

пусть

1и . .. ,

1т— нижние границы

^ (х ), . . .

.. ., gm(x), а ит+и . . .,

ир— верхние границы £т+1 (х),

.. ., gp (x).

Тогда ограничения можно записать как

 

 

 

 

 

gl (x) —81h ^ 0 ,

 

 

 

 

 

grn(х)

6mZm JJ-sО,

 

 

 

 

 

gm+l(x)

 

 

О?

 

 

 

 

§ р (х)

брПр^О,

 

 

 

 

 

• S

Si = Р —

 

 

 

 

 

 

г=1

 

 

 

 

 

 

 

1 ^ б г- ^ 0

(целые).

 

 

 

Заметим, что если б; =

1 для некоторого ограничения, то огра­

ничение выполняется автоматически. Если 8 г =

0, то Z-e ограни­

чение принимает вид g t (х) ^

0 (g; (х)

^

0 ).

 

 

Идея использования

переменной

б,

принимающей

значения

0 или 1 , можрт быть применена к задачам, где решение х должно

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

/ i ( x ) < 0 ,

g-Д х Х 0 ,

М х ) > 0 ,

' / 2 ( х ) < 0 ,

?2 ( х } < 0 ,

/i2 ( x )> 0 ,

}т ( х )< 0 ,

gn( x X 0 ,

А р (х )> 0 . ■

Множество решений поставленной задачи можно записать как

А(х) —бщ ^ О ,

gi(x) —б2щ < 0 ,

hi {x) — 63ll ^ 0 ,

/ 2 (х) — бща^О,

^г(х) —62u ;^ 0 ,

h2(x) — 63Z2 > 0 ,

fm (х) — бЩщ^О,

(X) 62Un^ 0 ,

hp (x) 63Zp^3iO,

61 + б2 + б3 = 2 ,

0 < б, < 1 (целые).

К третьему классу относятся такие задачи, в которых целевая функция может быть представлена как сумма нескольких функций, каждая из которых есть нелинейная функция относительно пере­

менной х ?, т. е. z = 2 %i (X))• Типичной задачей этого класса

з

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