Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 81
Текст из файла (страница 81)
пгиложкние с я г= ~ сгх. ч. у=1 (2) при ограничениях зихен)Ь,, 1=1, ...,т, ю 1 1) х;)О (целые), [ = 1, ..., и. Множество хг с хг=1, )ЕЛг„и хг=О, уб с Х вЂ” Л', (Л'~ с= Лг = (1, 2,..., и)) пазовем решением. Решение называется допустимым, если оно удовлетворяет также ограничениям (3). Не теряя общности, можно предположить, что О < < с1 < с, «... с„. (Если некоторое сг < О, мы могкем произвести замену переменных х,' = 1 — хр) Подход, испольаованный адесь, может быть пазван геявныгг переборол, поскольку мы систематически перебираем решения. Будем говорить, что допустимое решение доминируется другим допустимым решением, если последнее имеет меныпее аначение целевой функции. Для удобства мы используем оо в качестве значения целевой функции для недопустимых решений.
Таким образом, недопустимое решение всегда домипируется допустимым решением. Если мы последовательно проверяем решения па допустимость, некоторые из решений, которые еще не были проверены, могут доминироваться текущим наилучшим допустимым решением. В этом случае нет необходимости проверять все допустимые реп|ения. Для задачи булевого программирования с и переменными имеется 2" реп1ений.
Мы разобьем 2" решений на и + 1 подмпо- 2. Если два допустимых целочисленных решения, первое с у~ = [у~[ + 1, а второе с у~ — — [у~[ + 2, имеют одно предшествующее, то оптимальное значение целевой функции для первого решения мепьше, чем оптимальное значение второго (если с~ ) О). Иными словами, чем дальше у~ от решения задачи линейного программирования, тем хуже значение целевой функции. Продолжая вычисления методом ветвей и границ, мы получаем оптимальное значение г*, наилучлтее для найденных пока целочисленных решений. Если вершина с нецелочисленным решением имеет оптимальное значение, большее чем г*, то все следующие за ней веригины долягны иметь оптимальные значения, большие чем г*.
Следовательно, не имеет смысла производить ветвление иа этой вершины. Этот факт может быть использован для решения задач частично целочисленного программирования. Рассмотрим аддитивный алгоритм решения задачи булевого программирования. Минимизировать АЛГОРИТМЫ ТИПА ДВРВ А ПОИСКА жеста; й-е подмножество (я = О, 1,..., п) содерн1ит все решения, в каждом из которых я переменных равны 1, а остальные п — я равны О. Таким образом, нулевое подмножество содержит одно нулевое решение: х1 = О (1 = 1,..., и). Первое под- (и) множество содерл1ит ~ ~ ре1пений: х1 — — 1, х1 = О (1 М 1); хз = = 1, хг = О (~ чА 2);.... В общемслучае к-еподмножествосодер- 11 Й'1 жит ~ ~ решений.
Упорядочим все 2" решений при помощи диаграммы, как это показано на рис. С-1(а) для и = 4. Рас. С-1 Каждая вершина на рис. С-1(а) представляот решение. Внутри каждой вершины указываются индексы 1, для которых х1 = 1 (х1 — — О для остальных). Например, верп1ина с индексами 1,3 внутри представляет собой решение х1 — — хт = 1, хт = х, = О. С каждой дугой также сопоставляется свой индекс 1. Зтот индекс оаначает, что х; = 1 в вершине, где дуга кончается, и х1 —— О в верп1ипо, где дуга начинается.
Значения всех других переменных в двух вершинах, связанных дугой, одинаковы. Кажду1о вершину можно достичь из самой верхней вер1пины посредством многих различных цепей, соответствующих различным способам, которыми можно придавать значения х, = 1. Если существует цепь из вершины Х1 в вершину Л'П то Л1; называется предшествующей вершине 11';, а ДГ~ называется следующей за вершиной Х1. Все вершины явля1отся следующими за самой верхней вершиной и предшествующими самой нижней.
Все верп1ины частично упо- 464 пгилоя«вник с рядочеиы отношением «предшествует — следует». Проверяя решения иа допустимость, мы ие используем никакой техники линейного программирования. Решения непосредственно подставляем в ограничение (3). Начипаем с самой верхней вершипы (х; = О, у = 1,..., п), а затем ищем бли«кайшую вершину, следующую за ией. Вершина называется висячей, если мы пе проверяем ыи одну из следующих за пей вершин. Ниже приводятся 4 правила, которые могут быть использованы при проверке. П р а в и л о 1.
Поскольку О (с« (~с«(... (с„, значемие целевой фупкции сх для произвольного решения всегда больше значения целевой функции для решения, ему предшествующего. Таким образом, если вершина допустима, пет необходимости проверять все вершины, следующие за пей. На рис. С-Цб) предполагается, что х, = х, = х, = О, х, = 1 — допустимое ре«пеппе. Этот факт непосредственно исключает из рассмотрения 7 решений. П р а в и л о 2. Пусть з* — минимальное среди эпачсний целевой функции для расс»«отрепкых пока допустимых значений. Пусть эс — значение целевой функции верпшпы Хс с х; = 1, ?гаях~ — — О,УЕЛ вЂ” ф Еслизо+с»)з*, то мы можепРассматривать только те следующие эа Л'с вершины, у которых х« — — хаы =...
= х„= О, так как сд (с«+«»4... (~с„. Любые другие решения, следующие за Хс, будут доминироваться допустимым решением с г*. П р а в и л о 3. Рассмотрим вершину Хо с х~ = 1 1 с 0 и х. = О, у с Х вЂ” ч. Все вершины, следующие за Дго, должны иметь хт = 1, ? с ф Эти переменные хп у с «), будем называть фиксированными для вершин, следующих аа Хо, все остальные перемеппые будем называть свободными, так как опи могут принимать зпачепие О либо 1. Если )Уо недопустимо, то можно считать, что нет достаточного числа свободных пере»«епных, которые бы удовлетворяли данному ограничению. Пусть, например, таким ограничением является — х, — х» + х» + х, ) 1 и Ло имеет .х, = х, = 1. Даже если х, = х« = 1, неравенство пе выполпяется.
Когда это происходит, проверять следующие за ДГо вершины пет надобности. П р а в и л о 4. Когда подмножество переменных фиксировано, то данное ограничение может заставить некоторые другие переменные таьпке стать фиксированными. Пусть, например, ограничением является Зх, — х, — 2х» = О, а соответствующая вершина имеет х« — — 1, х, =... = х„= О. Все вершины, следующие эа ней, должпы иметь х, = х» — — 1. Таким образом нет необходимости проверять вершину х« —— х, = 1, х» — — О, х« —— ?,....
ПРИЛОЖКНИК О Р (Вв (0)) Грани Р(ВИ (3В Грани 7! 7в 7в 7171 71 71 7з 7в 71 Строка Строка 54321 42342 24324 12345 10101 21321 12321 12312 2 3 4 Ве шин .=-(3) ьь) =- «,1) Юь) = «,2) =(6) (с „(о)) Грань Ввршьша Р (бв~ (5)) Грани Р (Ов (4)) Грани 71 71 7в 71 7в 70 Строка 71 7в 7в 71 7ь 7о 101011 120122 23455 Строка Грань Вершина 12345678 Вершины 1. (ь,) =-(6) 6.
(ь,) 2. (ьь) .=(3) 7 «1 3. (ьв) =-(2) 8. (11 4. (ьь, ьь)=(2«) 9. (ьь) 5. (Рш ь,)=-«,1) Матрица инциденций Р 123456789 000101111 010110111 111111011 001101101 111110101 101011101 111101110 110010110 100011110 1 ~ 2 1 0 2 1 ~ 2 Вершины 1, (ьв) =(4) 4. (ьь) =«) 2. (11) =(2) 5. (ьь) =(2) 3.' (11, М)=«,1) Матрица инциденций Р (6„(4)) | грань 1234567 ВеРшина 010111 1110111 1101011 1111101 1111110 р и 1 (ьь) =(3) 5. (11 ьь) = — (2.1) 2. (11, ьь)=«,1) 6. (ьь, ьь)=«,1) 3.
(ьь) =«) 7. (ьь) =(3) 4, (ьь, ьь) = «,2) Матрица инциденций Р(Св, (3)) 123456789 001101111 111100111 111111011 100101101 110010110 111111100 011011110 Вершины 1. (11) =(5) 5. (ь„ь,) = «,1) 2. (В, Ьь)=«,2) 6. (ьв, Ьь)==«,2) 3. (ьр ьв)=(2,1) 7. (ь,) =«) 4, (ю„ь,)=«,1) Матрица инциденций Р(01, (5)) 00101111 10100111 01101011 11110011 11101101 11011001 11111110 470 Р(07 (6)) Грани СтРеав 7в 7а 7з 7в 7в 7в 1 2 3 б 5 4 4 8 5 9 4 б 4 5 б 3 2 8 2 610 8 3 12 6 8 10 12 Вершины 1. (аа) = (б) 2.
(а,) = (3) 3, (зз) = (2) 4. (зп ав) = (2, 1) 5 (зь ав) = (1. 1) б. (зв) = (5) 7. (аы з,) = (1, 1) 8. (ав, з,)= (г, 1) 9. (зв) = (4) 10. (вв) = (1) Матрица инциденций Р(Ст, (6]) 1 2 3 4 7 8 9 10 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 Ставка 7в 7а 7з 7в 7з 7в 71 7о 9 (аз зз)=(1 1) 10. (зн з,)=(1, 3) 1 1. (аз) = (8) 12, (зн ав)=(2 1) 13.
(З„З,) =(1, 1) 14. (зз, зв) =(2, 1) 15. (св) =(4) =(8) = (4) =(2, 2) =(1, 2) =(8) =(г) =(3, 1) ав) = (1,' 1, 1) 16. (зп з,) =(1,1) 17. (аз, Зт) = (3 1) 18 (зз1 зв зт) = (1, 1, 1) 19. (аа, зт) = (1, 2) 20. (зы а,) = (2, 2) 21. (зз, зт) = (1, 3) 22. (В) =(8) 1 2 3 4 5 6 7 8 9 10 Вершины 1. (аа) 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
