1. Постановка и особенности задач дискретного
 Скачать 177.02 Kb.
|
|
4. Метод ветвей и границ Суть метода ветвей и границ. Метод ветвей и границ относится к группе комбинаторных методов. Комбинаторные методы исходят из конечности числа допустимых планов задачи и заменяют полный перебор всех планов их частичным направленным перебором. Комбинаторные методы в значительно меньшей степени подвержены в процессе вычислений влиянию ошибок округления, поэтому являются более предпочтительными по сравнению с методами отсечения. Метод ветвей и границ – один из наиболее эффективных методов решения задач комбинаторного типа. Рассмотрим общую задачу дискретного программирования ) x f Z = max , (4.1) Ω ∈ x , (где Ω - конечное множество допустимых планов. 1. Находим верхнюю границу (оценку) функции ( ) Ω ∈ x x f , , те. такое число ( ) Ω 0 ϕ , что для любых Ω ∈ x ( ) ( Если при этом удается найти такой план 0 x задачи (4.1)-(4.2), для которого выполняется равенство ( ) ( ) Ω = 0 то 0 x - оптимальный план задачи (4.1)-(4.2). 2. Если оптимальный план не найден, то некоторым способом разбиваем множество Ω наконечное число непересекающихся подмножеств 1 1 1 r r r = Ω = Ω , = Ω = 1 и находим для каждого из этих подмножеств верхнюю границу ( ) ( ) 1 1 1 ,..., 2 , 1 r r r = Ω ϕ . Если при этом удастся найти такой план ( ) 1 1 1 1 r r x r l ≤ ≤ Ω ∈ , что выполняется соотношение ) ( ) ( )( ) 1 то 1 l x - оптимальный план задачи (4.1)-(4.2.). Если же такой план не найден, то выбираем подмножество 1 r Ω с наибольшей верхней границей перспективное подмножество) и разбиваем его на несколько непересекающихся подмножеств ( ) 1 2 ,..., 2 , 1 s s s = Ω . Для каждого нового подмножества находим верхнюю границу ( ) 2 s Ω ϕ . Если будет найден такой план 2 k x , что ( ) ( ) ( ) 2 то 2 k x - оптимальный план задачи. Если оптимальный план не найден, то дальнейшему ветвлению подвергаем подмножество с наибольшей верхней границей, и т.д. Процесс продолжается дополучения оптимального плана. Способы ветвления и нахождения верхних границ выбираются для каждой конкретной задачи дискретного программирования. Процесс сопровождается построением дерева ветвления (рис … … … Рис. Задача целочисленного (частично целочисленного) линейного программирования (2.1)-(2.4). В качестве верхней границы на множестве планов рассматривают значение целевой функции на оптимальном плане соответствующей ЗЛП (2.1)-(2.3). Пусть, далее, r x - целочисленная переменная, значение ∗ r x которой в оптимальном решении задачи (2.1)-(2.3) является дробным. Интервал [ ] [ ] 1 + < < ∗ ∗ r r r x x x не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение r x должно удовлетворять одному из неравенств [ ] ∗ ≤ r r x x или [ ] 1 + ≥ ∗ r r x x . Введение этих условий в задачу с отброшенным условием целочисленности порождает две несвязанные между собой задачи. Говорят, что исходная задача разветвляется на две подзадачи. Затем каждая подзадача решается как ЗЛП с целевой функцией исходной задачи ] , , ∗ ≤ Ω ∈ r r x x x , [ Если полученное оптимальное решение оказывается допустимым для целочисленной задачи, то его следует зафиксировать как наилучшее. При этом нет необходимости продолжать ветвление подзадачи, поскольку улучшить полученное решение не удастся. В противном случае подзадача должна быть разбита на две подзадачи и т.д. Как только полученное 27 1 1 Ω 1 2 Ω 1 r Ω 1 1 r Ω 2 1 Ω 2 s Ω 2 1 s Ω допустимое целочисленное решение одной из подзадач оказывается лучше имеющегося, оно фиксируется вместо зафиксированного ранее. Процесс ветвления продолжается до тех пор, пока каждая подзадача не приведет к целочисленному решению или пока не будет установлена невозможность улучшения имеющегося решения. Пример 4.1. 2 1 3 2 max x x Z + = ; , 36 9 4 , 35 7 5 2 1 2 1 ≤ + ≤ + x x x x , , 0 , 0 2 1 2 1 целые х х х х − ≥ ≥ Р е ш е ни е Решим исходную задачу (задачу 0) как ЗЛП с отброшенным условием целочисленности. Оптимальное решение достигается в точке = ∗ 17 6 2 ; 17 12 3 нц х Так как обе переменные принимают нецелые значения, то любая из них может быть выбрана в качестве переменной, продолжающей процесс ветвления. Выбор, например, переменной х порождает две подзадачи, связанные с условием [ ] ∗ ≤ 2 2 х х или [ ] 1 2 2 + ≥ ∗ х х . Так как [ ] [ ] 2 17 / 40 х, имеем две подзадачи 1.1 и 1.2: a. 1.2 ; 3 2 max 2 1 x x Z + = ; 3 2 max 2 1 x x Z + = , 35 7 5 2 1 ≤ + x x , 35 7 5 2 1 ≤ + x x , 36 9 4 2 1 ≤ + x x , 36 9 4 2 1 ≤ + x x , 2 2 ≤ x , 3 2 ≥ x , 0 , 2 1 целые х х − ≥ 0 , 2 1 целые х х − ≥ Порожденные подзадачи содержат все допустимые целочисленные решения исходной задачи, те. исходное множество допустимых 28 целочисленных решений остается неизменным в процессе ветвления. Их оптимальные решения 2 14 , 2 ; 5 1 4 = = ∗ ∗ Z х нц 2 1 13 , 3 ; 4 1 2 = = ∗ ∗ Z х нц соответственно. На следующем шаге осуществляется выбор одной из подзадач 1.1 или 1.2 для рассмотрения и при необходимости для дальнейшего ветвления. Отметим, что не существует точных способов реализации указанного выбора. Причем выбор различных альтернатив приводит к разным последовательностям подзадача, следовательно, к различным количествам итераций, обеспечивающих получение оптимального целочисленного решения. Предположим, что в первую очередь рассматривается задача 1.1. Оптимальное решение этой задачи достигается в точке = ∗ 2 ; 2 1 4 нц х . Так как значение 2 1 4 х остается нецелым, задача 1.1 порождает подзадачи 2.1 и 2.2 с дополнительными ограничениями соответственно [ ] ∗ ≤ 1 1 х х , тех и [ ] 1 1 1 + ≥ ∗ х х , тех 2 1 ≤ + х х , 35 7 5 2 1 ≤ + х х , 36 9 4 2 1 ≤ + х х , 36 9 4 2 1 ≤ + х х , 2 , 4 2 1 ≤ ≤ х х , 2 , 5 2 1 ≤ ≥ х х , 0 , 2 1 целые х х − ≥ целые х х − ≥ 0 , 2 Оптимальные решения этих подзадач ) 14 , 2 ; 4 = = ∗ ∗ Z х нц и 7 2 14 , 7 3 1 ; 5 = = ∗ ∗ Z x нц соответственно. Наличие у подзадачи 2.1 целочисленного решения не означает, что найдено оптимальное целочисленное решение исходной задачи 0, потому 29 что еще не решены подзадачи 1.2 и 2.2, которые могут дать лучшее решение, чем 2.1. Целочисленное решение подзадачи 2.1 определяет нижнюю границу 14 = Z значений целевой функции. Нет необходимости рассматривать те последующие подзадачи, для которых оптимальные значения Z меньше указанной нижней границы. Обратимся к подзадаче 1.2. Для нее 5 , 13 = ∗ Z , что не превышает значения 14 = Z , поэтому поиск вдоль ветви 3 2 ≥ x следует прекратить. Исследуем вершину 2.2, которой соответствует 7 2 14 = ∗ Z . Несмотря на то, что полученное значение превышает нижнюю границу 14 = Z , дальнейшее ветвление осуществлять нецелесообразно, поскольку 1 14 7 2 14 < − и все коэффициенты целевой функции целые. Итак, найдено оптимальное решение задачи ( ) ( ) 14 , 2 ; 4 = = ∗ ∗ ц ц x Z х . К нему привела цепочка задач 2 2 1 2 2 1 1 Если для исследования выбрать подзадачу 1.2, то получим следующие оптимальные целочисленные решения ( ) 13 , 3 ; 2 = = ∗ ∗ Z х ц и ( ц. Они явно хуже, чем решение подзадачи Упражнения для самостоятельного решения Методом ветвей и границ найти оптимальные решения задач. max 3 2 2 1 → + x x ; 4.3. min 3 2 1 → + x x ; 1 2 2 2 1 ≥ + x x , 29 4 2 1 ≤ + − x x , 15 4 2 1 ≤ − x x , 15 3 2 1 ≤ − x x , 16 3 2 1 ≤ + x x , 38 2 5 целые целые 1 30 Список использованной литературы. Акулич ИЛ. Математическое программирование в примерах и задачах. – М Высш.шк., 1993. 2. Кузнецов А.В., Холод НИ. Математическое программирование. – Минск Высш.шк., 1984. 3. Кузнецов А.В., Холод НИ, Костевич Л.С. Руководство к решению задач по математическому программированию. – Минск Высш.шк., 2001. 4. Морозов В.В. и др. Исследование операций в задачах и упражнениях. – М Высш.шк., 1986. 5. Саати Т.Л. Целочисленные методы оптимизации и связанные сними экстремальные проблемы. – М, Мир, 1973. 6. Сергиенко ИВ. Математические модели и методы решения задач дискретной оптимизации. – Киев Наукова думка, 1988. 7. Сигал ИХ, Иванова А.П. Введение в прикладное дискретное программирование. М ФИЗМАТЛИТ, 2002. 8. Схрейвер А. Теория линейного и целочисленного программирования. Т. – М Мир, 1991. 31 Подписано в печать 14.10.2009. Усл. печ. л. 1,75. Тираж 10 экз. Заказ Тверской государственный университет |