XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 24
Текст из файла (страница 24)
Прекратить вычисления, если список задач, порожденных исходной задачей целочисленного программирования, пуст. В противном случае выбрать одну задачу и, вычеркнув ее из списка, перейти к этапу 2. Этап 2. Решить задачу линейного программирования с ослабленными ограничениями, соответствующую выбранной на этапе 1 задаче целочисленного программирования. Если множество ее допустимых решений пусто или полученное оптимальное значение целевой функции не превосходит )е ', то принять 1е = ~е и вернуться к этапу 1.' В противном случае С вЂ” 1 перейти к этапу 3. Э т а п 3 .
Если полученное оптимальное решение задачи линейного программирования с ослабленными ограничениями 173 4 3 Метод яетвеи и границ 172 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ удовлетворяет требованию целочисленности, то зафиксировать его, принять Д равным соответствующему значению целевой функции и вернуться к этапу 1. В противном случае перейти к этапу 4. Э т ап 4. Выбрать любое базисное переменное у;, значение которого Д в полученном оптимальном решении не является целым числом.
В список задач, порожденных исходной задачей целочисленного программирования, внести еще две задачи. Первая из них отличается от задачи, выбранной на этапе 1, лишь наличием дополнительного ограничения у; ( [Д], а вторая — наличием дополнительного ограничения у; > Щ + 1. Принять Д = Д 1 и вернуться к этапу 1.
Замечание 4.1. Обратим внимание на специфику описания этапов итерации: не предполагается полная целочисленность исходной задачи, равно как и целочисленность ее коэффициентов. Если же исходная задача является полностью целочисленной и коэффициенты сь ее целевой функции — целые числа, то процесс решения может быть ускорен за счет видоизменения второго этапа в каждой итерации: а) решить задачу линейного программирования с ослабленными ограничениями, соответствующую полностью целочисленной задаче, выбранной на этапе 1; б) если ее множество допустимых решений пусто или целая часть оптимального значения целевой функции не превосходит Д 1, то принять Д = Д,' 1 и вернуться к этапу 1. В противном случае перейти к этапу 3.
Пример 4.6. Рассмотрим полностью целочисленную задачу следующего вида: 2х1+ Зхо -+ шах; 5х1 + 7хз ( 35, 4х1+ Охо ( 36, хы хз ) 0 хы хо е 1ч О 1,0). На рис. 4.7 графически изображен один из возможных вариантов ее решения методом ветвей и границ с использованием Рис. 4.7 175 4.3. Метод ветвей и границ 174 4.
ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ дерева решений, представляющего собой граф специального вида. У дерева решений, изображенного на рис. 4.7, исходной является вершина 1. Так как коэффициенты целевой функции с1 — — 2 > 0 и ст = 3 > О, то полагаем /ее = О. Оба переменных т1 и яз в оптимальном решении / 12 6 1 , 12 „ 6 Х'= ~3 — 2 — ), я1 — — 3 —, хт — — 2 —, 17 17) ' 17' 17 задачи линейного программирования с ослабленными ограничениями, соответствующей рассматриваемой полностью целочисленной задаче, принимают нецелочисленные значения и любое из них может быть использовано для инициирования процесса ветвления. Если выбрать яе, то этот выбор порождает задачи 2 и 3, связанные с условиями хе < 2 и хя > 3 соответственно, так как 1п1(хя) = 2. Порожденные задачи охватывают все допустимые решения исходной целочисленной задачи.
Полагаем / = /ее = О. Теперь о нужно выбрать одну из порожденных задач (2 или 3) для решения и, прн необходимости, для дальнейшего ветвления. Различные варианты выбора одной задачи из совокупности порожденных задач приводят к разным последовательностям порожденных задач и, следовательно, к различным количествам итераций, необходимых для нахождения оптимального решения исходной задачи целочисленного программирования. Для иллюстрации этих особенностей метода ветвей и границ вернемся к полностью целочисленной задаче, рассмотрение которой начато в примере 4.6.
Пример 4.7. Предположим, что в первую очередь решено рассмотреть вершину 2 дерева решений, представленного на рис. 4.7. Находим оптимальное решение Х" = ~4- 2), я~ — — 4-, я2 —- 2, ~ 5 ) соответствующей задачи линейного программирования с ослабленными ограничениями. В оптимальном решении Х' переменное модели я1 принимает нецелочисленное значение я", = 21/5 и Ы1я') = 4.
Полагаем /ет = /е1 = О. Учет ограничений я1 < 4 и х1 > 5 порождает задачи 4 и 5 соответственно. Предположим, что решено рассмотреть задачу 4 из списка задач (3, 4, 5), порожденных исходной полностью целочислент ной задачей. Оптимальное решение Х' = (4 2) соответствующей задачи линейного программирования с ослабленными ограничениями удовлетворяет требованию целочисленности, а оптимальное значение целевой функции / = 14. Полагаем /оз = = 14.
Заметим, что наличие оптимального решения задачи 4, удовлетворяющего требованию целочисленности, не означает нахождения решения рассматриваемой полностью целочисленной задачи, так как список порожденных задач (3, 5) не является пустым. Обратившись к задаче 3, порожденной ограничением хя > 3, находим оптимальное решение соответствующей задачи линейного программирования и оптимальное значение целевой функции / = 13,5, которое не превышает /ез = 14. Таким образом, задача 3 не будет порождать новые задачи. Полагаем /4 = /з = 14, На следующей итерации необходимо исследовать задачу 5, для которой оптимальное значение целевой функции соответствующей ей задачи линейного программирования с ослабленными ограничениями равно 100/7 > /е4 = 14.
В рассматриваемом случае (см. пример 4.6) коэффициенты целевой функции и переменные задачи являются целочисленными. Кроме того, 1п1(100/7) = 14 = /е4. Поэтому, согласно замечанию 4.1, задачи, порожденные задачей 5, не могут иметь оптимальных решений, удовлетворяющих требованию целочисленности, лучших в смысле оптимального значения целевой функции, чем т Х' = (4 2) . Ветвление из вершины 5 дерева решений, представленного на рис. 4.7, не проводится и решение исходной задачи завершено.
176 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 4 3 Метод ветвеи и границ 177 Е1=(Ц, Уо1=0 1=4, В =(3,8>, 7 =14 1=2, Ег=(2,3>, уз=о о г=з Яз=(3 4 8) Уо=14 (решение фиксировать) г=з, Яо=(8), У~~=14 Рис. 4.8 Понятно, что в общем случае оптимальному значению целевой функции рассматриваемой задачи целочисленного программирования могут соответствовать несколько оптимальных решений, удовлетворяющих требованию целочисленности. Позтому, если необходимо найти все оптимальные решения исходной задачи, то при реализации метода ветвей и границ нельзя использовать правило, сформулированное в замечании 4.1, так как прекращение процесса ветвления при найденном оптимальном решении может привести к потере других оптимальных решений, если они есть.
Для наглядного описания последовательности, в которой рассматриваются вершины дерева решений при использовании метода ветвей и границ, вводят понятие лизни, формализованное представление которого имеет следующий вид: (1-+ п1 — > -+ пг — +... -+ пм), где пь -+ по+1 означает, что после вершины с номером пь необходимо переходить к вершине с номером по+1, а М на единицу меньше количества вершин у дерева решений.
Так, в примере 4.7 рассмотрен путь (1 — ь 2-+ 4-+ 3-+ 5). Если через 51 обозначить список задач, порожденных исходной задачей целочисленного программирования к началу итерации 1, то геометрическая иллюстрация зтого пути может быть представлена так, как изображено на рис. 4.8. Этот рисунок легко сопоставляется с рис. 4.7, если учесть, что итерация 1 соответствует вершине 1 дерева решений, итерация 2 — вершине 2, итерация 3 — вершине 4, итерация 4 — вершине 3, а итерация 5 — вершине 5. Продолжим рассмотрение решения полностью целочисленной задачи, начатое в примерах 4.6, 4.7.
Пример 4.8. Предположим, что на итерации 2 выбрана задача 3, т.е. начало пути 1-+ 3 (см. рис. 4.7). Задача 3 порождает две новые задачи: 6 и 7. Теперь нужно выбрать для решения одну задачу из множества (2, 6, 7) н т.д. Один из возможных вариантов пути 1-+ 3-+ 6-+ 9-+ 8-+ 7-+ 2-+ 4-+ 5 представлен на рис. 4.9 (всю необходимую информацию можно найти на рис. 4.7). Я!=(Ц, 7"01=0 2, Яг=(2,3) 7ог=0 1=6, Язв - (2,7) У~=13 о 1=7, Ег=(2>, Уз=1 о 1=8, Яо=(4, 8>, Уо= 14 (решение фиксировать) 1=9 Е =(6) уо о 3, лз=(2,6,7), У~=0 4' Яо (2'7'8'9) У~о 12 (решение фиксировать) 1=6, Е;(2,7,8>, Уо= (решение фиксировать) Рис.
4.9 Этот путь предполагает девять итераций. Сначала фиксируется оптимальное решение задачи 9, удовлетворяющее требованию целочисленности и соответствующее оптимальном У значению целевой функции ~4 = 12. Затем фиксируется оптимальное решение задачи 8 с оптимальным значением целевой функции (оо = 13 и на итерации 8 фиксируется оптимальное решение задачи 4, которое и является решением исходной полностью целочисленной задачи. Рассмотренные примеры наглядно демонстрируют основные недостатки метода ветвей и границ, обусловленные как произволом выбора последовательности рассмотрения задач из списка задач, порожденных исходной задачей целочисленного программирования, так и произволом выбора переменного модели, которое используется для получения порождаемых за ач д 178 4.
ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ на этапе 4 каждой итерации. Для повышения эффективности метода ветвей и границ разработаны специальные эвристические (от греческого йеигЫхб — открываю, отыскиваю) правила, связанные как с выбором переменных модели, инициирующих процессы ветвления в вершинах дерева решений, так и с выбором на каждой итерации задачи для рассмотрения из списка порожденных задач. Ход итераций можно представить графически в виде дерева решений (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
