Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 57
Текст из файла (страница 57)
Коли п(Ь вЂ” Азу) ) п(Ь вЂ” Азу), то и ~'и, а это означает, что либо мы всегда получаем нову1о вершину при каждом повторении шага 2, либо получена оптимальная вершина. Для доказательства того, что алгоритм приводит к оптимальному решению, необходимо заметить, что если все и" выписаны в задаче (1'), то оптимальное решение будет получено.
Чтобы убедиться, что можно получать верхнюю и нижнюю границы, рассмотрим в задаче (Г) з, которое является нижней границей оптимального значения г*. Поскольку в задаче (т ) выписаны не все ограниченна, для получения верхней границы зе дополним результат шага 2 решением задачи минимизировать с,х 15.2. метод РАзвие1!ня 321 при условиях Агх>Ь вЂ” Ау, х>0, Минимизировать 5х+ 2УГ + 2уг при условиях х — 'Зу,+2у,>5, 4х — УГ + уг>7, 2х+ Уà — уг> 4. >О, у„у,>0, у,=у,=о ( а1). Перепишем (8), считая у произвольно заданным (как указывалось в начале параграфа.) минимизировать при условиях х> Е! 5 — ЗУà — 2у, 5 г У! У2 4 — УГ-Р уг х>0 (9) Двойственная задача для задачи (9) имеет внд максимизировать Зуг 2уг 7+ у,— уг 4 — у,'; у, (И1~ И2 Из) при условиях и1+ 4иг+ 2из(5, иь иг из>0.
Одним из допустимых репзений задачи (10) является 5 и1 0 иг 4 из 0 (10) Из задачи (8) получим следующую задачу: минимизировать 21 т хт где у — значение у, используемое па шаге 2. Тогда допустимым решением задачи (1) является (х, у), а с,х —, с,у — требуемыл1 значением верхней границы на каждом шаге. Решим следующий пример, используя алгоритм разбиения: ГЛ. 15. СМЕШАННЫЙ АЛГОРИТМ 322 при условиях 5 8 уз — 2уз 7+ у,— уз 4 — Уз+ Уз (8') г)~2уз+2уз — , '5пах и" из, из, из) О. Подставляя решение (О, 5/з, 0) задачи'(10) в (8'), получаем минимизировать при условиях 5' г)~ 2У, + 2Уз+ — (7+ Уз — Уз), (8") уз -уз~0. 25 Решепиелз задачи (8 ) является г= 4, у,=уз= О.
Подставляя у,=уз=О в (10), получаем максимизировать 5и,+7из-1-4из при условиях из+ 4из+ 2из(5, и1 из, из)0 (10') минимизировать при условиях 5 г)2уз+2уз+ 4 (7+уз — уз) г'-: 2У1+ 2уз+ 5 (5 — Зу, — 2У,), у„у,~О. Решением является уз 1, уз=О, 5=12. Подставляя У,=-1, У,=О в (10), получаем задачу: максимизировать 2и, + Зиз+ Зиз* Решением этой задачи является вектор (5, О, 0), при котором 5и, -Г 7из+ 4из — — 25. Поскольку 4 — (2, 2)(0,0)(25, добавим в (8') новое условие и получим: 323 !з.з. пРилОжения при условиях и, + 4из+ 2из( 5, ио пз пз~~О. Решением ее является и, = 5, из = О, из = О, 2и; + 8из + Зиз = =10. Так как 10=э — (2,2)у=12 — 21 — 210.=10, то решение оптимально.
Подставляя уз — — 1, уз = 0 в (9), получим минимизировать 5х при условиях Ц , х)0. Решением будет х = 2, 5х =- 5 2 = 10, как и предполагалось. Оптимальным решением задачи (8) является х = 2, уз — — 1, у, = 0 и э* = 12. 1 5.3. Приложения ') См. также Корбут и Фннкеэьпгхейн [9*].— Прим. ред. 2зе В этом параграфе будут приведены некоторые задачи, которые могут быть сформулировапы как задачи целочисленного программировапия. Они могут слузкить примерами, иллюстрирующими стандартные методы превращения задач в задачи целочислепного программирования.
Более подробпо об этом можно прочитать у Балинского (61 и Данцига (33], (34). Многие целочисленные задачи имеют особую структуру и должны решаться с помощью специальных методов. Типичный класс таких задач составляют задачи о покрытиях и паросочетакиях (см. Балинский (6], Эдиокдс [541, [55), [56], Витцгалл и Зап [216] '). Другим классом являются так называемые задачи о рюкзаке, которые будут обсуждены в гл. 18.
Как было показано в части 1, оптииальпое решение задачи линейного программирования отпюдь не обязательно целочислекно, и в то же время существует иного задач, природа которых требует целочисленности резпония. Некоторые из этих задач па первый взгляд не являются задачами целочисленного программирования, однако оии могут быть оформулировапы как таковые. Если требуется, чтобы только кокоторые переменные были целочисленпыми, то задача называется задачей смешанного программирования (см. э 15.1, 15.2).
В этом параграфе будут обсуждены как раэ некоторые из классов таких задач, которыо можно представить в виде задач цело- гл. »». смв»»»Аннын Аг»гогитм численного программирования. В большинстве из нижеприведенных задач требуется, чтобы определенные переменнь»е принимали в качестве значений пуль влн единицу. 11 первому классу относятся задачи, в которых некоторая переменная мов»ет принимать ли»пь конечное мнонсество значений.
Наприа»ер, грузоподъемность грузовика может иметь лишь определенное стандартное значение. Пусть Ьм,..., Ь»ь — зпаче»»ия, которые может принимать переменная х;. Тогда в задаче х» -— - б»Ь„+ б»Ь»з +... + ЬаЬ»ю б, +... +б, =1. б; ) О (цель»е) (» = 1, ..., 1»). Переменная х, может припимать лишь указанные значения. Такой же метод можно использовать, когда х представляет собой векторную переменную, принимающую значепия из конечного множества векторов. Если Ъ»,..., Ъа — воаможные значения переменной х, то задачу можно записать как х = б»Ъ» + + баЪю б +...+б б; ~) О (целые) (» = 1,..., Ь). Ко второму классу относятся такие задачи, в которых ие требуетсн, чтобы ограничения выполнялись одновременно, в отличие от задач линейного программирования, где необходимо учитывать сразу все ограничения.
Ка»кдое ограничение определяет полупространство, которое является выпуклым множеством. Мно'кество решений, будучи пересечением всех полупрострапств, также выпукло. Если не тробуется, чтобы все ограничения выполнялись одновременно, то множество решепий моя»ет быть объединением некоторых выпуклых множеств и в силу етого может быть невыпуклым и дая»е несвязным.
рассмотрим множество решений слодующей задачи: найти максимум х,+х, на множестве Х = Х» Ц Х„ где Х» =.(х ! Зх» + хз ~( 4; х„х» ) 0), Хз = (х 1 Зх» + Зх, ( 5; х», х, ~ >О'). Множество решений иаображено невыпуклой затененной областью па рис. 15.3. ы.з.
Пгиложкння 323 Для того чтобы сформулировать зту задачу как задачу целочисленного программирования, нужно знать какую-нибудь верхнюю границу величин Зх~ + х, — 4 и 2х, + Зх, — 5 па множестве решений. Такую границу нетрудно получить. Достаточно взять хз Р в с 15.3. некоторое большое поло;кктельное число, в пашем случае, скажем, 100. Теперь можно сформулировать задачу в следующем виде: найти максимум х~ + хз при условиях Зх -(-х, — 4 — 1006 ( О, 2х -(- Зх, — 5 — 100(1 — 6) (О, х„ х, ) О, О ( 6 ( 1 (целое). Заметим, что если 6 †.
— 1, то первое ограничение выполняется, цоскольку Зх~ + хз — 4 ~ (100, а второе примет вид 2х~ + Зхз— — 5 ~ О. Если 6 =- О, второе ограничение выполняется, а первое превратится в Зх, + хз — 4 ( О. Заметим также, что если на переменную 6 не наложено условие целочисленности, то множество решений с компонентами хы х, и 6 выпукло. Если множество решений задается как (л ( у~ (л) ~ >0) Ц () (л ~ дт (л) ) 0), то нужно знать нижнюю границу для д (л), скажем (ы и нижнюю границу д, (х), скажем )„на атом множестве.
Тогда множество решений можно описать как д, (х) — (~6)0, д,(к) — (,6) О, 0< 6~~1 (целое). Та же идея может быть обобщена на случай задач, где лишь й из р ограничений должны выполняться одновременно. Пусть ГЛ. Нь СМЕШАННЫЙ АЛГОРИТМ ограничения имеют вид ~5(х))0, ..., д (х))0, у .„5(х)(0, ...
..., ур(х)(0, и пусть 1„..., 1 — нижние границы д(х), ... ..., дм(Х), а и тм ..., ир — ВЕРХНИЕ ГРаНИЦЫ У +5(Х), ..., др(Х). Тогда ограничения можно записать как Е5 (х) — 6515)0, (х) — б 1~)0, дм м(х) — 6 +5и„„~(0, ур (х) — брир(0, р ~ Ь,=р — й, 1) 65) 0 (целые). И5 (х)(0, й, (х) )О, д,(х)~0, йз(х))0, 1,(х) я О, 1,(х)(0, /щ (х)~(0> ррр (х)~(01 йр (х))~О Множество решений поставленной аадачи можно записать как 1,(х) — б,и,(0, д,(х) — б,и,'(О, й,(х) — 6,1, )О, 15 (х) — 65из(0, дз (х) — Ьзи, ( (О, йз (х) — 654) О, 1 (х) — Ь,и„,(0, я„(х) — бзи„'(О, йр(х) — 651р вО, 65+65+65=2, 0 ( 6; (1 (целые).
К третьему классу относятся такие задачи, в которых целевая функция может быть представлена как сумма нескольких функций, каждая из которых есть нелинейная функция относительно переменной хь т. е. х = ~ зт (хт). Типичной аадачей этого класса 1 Заметим, что если 6; =. $ для некоторого ограничения, то ограничение выполняется' автоматически. Если б; = О, то 1-е ограничение принимает вид у; (х) ) 0 (д, (х) ( 0). Идея использования переменной 6, принимающей значения 0 или 1, может' быть применена к аадачамс где решение х должно удовлетворять одному из нескольких подмножеств ограничений. Для примера рассмотрим три подмножества ограничений (каждое подмножество ограничений определяет выпуклое подмножество решений, а все множество решений может быть несвяаным): ПЕЗ.
пРилОжения 327 является транспортная задача, в которой стоимость перевовки по некоторому маршруту складывается из двух частей. Первую часть составляют фиксированные расходы, связанные с используемым маршрутом. Они не зависят от количества груза. Вторая часть пропорциональна количеству груза, провозимого по данному маршруту. Таким образом, общая стоимость з, перевозки по данному маршруту ? задается как -( ?5?+ох;, если х?- О, г;= О, если х?=0, где й? — фиксированные расходы, а х? — количество груза, перевозимого по маршруту ?. Стоимость з? можно записать по-другому: з, =6?5?+схя хт(6М, О ( 6 ( 1 (целое), где М вЂ” верхняя граница х,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
