1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 15
Текст из файла (страница 15)
Так как симплекс-таблицы с номерами tn , v = 1,2,Ktnпрямо допустимы, то z10³ 0 . Поэтому, последовательность с номерами tn ,v = 1,2,K является монотонно убывающей и ограниченной снизу. Тогда суtществует T1 ³ T0 такой, что для всех t ³ T1 выполняется z10= z10 .Аналогичные рассуждения верны и для оставшихся компонент вплоть доn -ой. Следовательно, существует такой номер Tn , что для t ³ Tn и дляi = 1, K , n справедливо zit0 = zi 0 , где zi0 Î Z + .Подобное утверждение противоречит предположению о бесконечностичисла итераций.
Тем самым доказана конечность первого алгоритма Гомори.82§ 4. Метод ветвей и границРассмотрим задачуf ( x ) ® min .QДопустим, что множество допустимых решений Q является конечным, тогдаодним из алгоритмов решения этой задачи является полный перебор, когданаилучшее найденное решение, которое назовем рекордом, сравнивается сочередным допустимым решением. Понятно, что это очень неэффективныйспособ решения экстремальных задач. Так как приходится сравнивать друг сдругом все решения, которых может оказаться слишком много. А в случае,когда задача непрерывна и множество допустимых решений континуально,не очень понятно как реализовать такую стратегию решения.
Возникающиетрудности можно попытаться обойти, если воспользоваться методом ветвей играниц (МВГ). Данный метод основан на переборе допустимых решений, впроцессе которого рекорд сравнивается с подмножествами допустимых решений. Этот алгоритм осуществляет поиск оптимального решения посредством последовательного разбиения множества допустимых решений на подмножества меньшей мощности. Нижние оценки на значения целевой функции на этих подмножествах сравниваются с текущим рекордным значениемцелевой функции.
Ясно, что подмножества решений, у которых нижниеоценки больше текущего рекордного значения, не могут содержать оптимального решения и должны быть отброшены. В приводимом ниже описанииметода ветвей и границ предположение о конечности множества Q не используется. Более важно свойство разложимости, которое описывается ниже,и предположение о конечности числа атомарных множеств.Атомарным множеством назовем подмножество Q , на котором исходнаязадача легко решается точно или приближенно.
Подмножество Q допустимых решений назовем разложимым, если оно представимо в виде объединения некоторого конечного набора атомарных множеств.Обозначим через x (d ) наилучшее решение задачи на атомарном множестве d , найденное с помощью некоторого алгоритма.Функцией ветвления b(d ) назовем функцию, определенную на разложимых подмножествах множества Q и ставящую в соответствие множеству dопределенное его разбиение на несобственные разложимые подмножества.Нижней границей назовем вещественную функцию H (d ) , определеннуюна разложимых подмножествах множества Q и такую, что0 < H ( d ) £ min f ( x ) .xÎdФункция H (d ) невозрастающая, то есть H ( d1 ) ³ H ( d 2 ), если d1 Í d 2 .834.1 Схема методаАлгоритм, реализующий метод ветвей и границ, состоит из конечной последовательности однотипных шагов.
На каждом шаге рассматривается некоторое разбиение d1,K, d L множества еще непросмотренных допустимых решений и некоторый рекорд x 0 .На первом шаге положим d1 = Q , а в качестве x 0 выберем произвольноедопустимое решение.Пусть к очередному шагу имеется разбиение d1,K, d L и рекорд x 0 . Шагначинается с проверки элементов разбиения (не обязательно всех) на выполнение следующих условий: содержится ли в нем решение со значением лучше рекорда; какое решение в подмножестве является наилучшим? Пусть проверяется множество d l . Это множество считается проверенным и отбрасывается, если выполняется одно из условий:1.
f ( x 0 ) £ H ( d l ) ;2. функция x (d ) определена на множестве d l .При этом если реализуется второй случай и f ( x (d l )) £ f ( x 0 ) , то устанавливается новое значение рекорда x 0 = x (dl ) . Если отброшенными оказываются все элементы разбиения, то алгоритм заканчивает работу и текущий рекорд x0 является оптимальным решением.Пусть d1¢ ,K, d L¢ ¢ , 0 < L¢ £ 1 − множества, не отброшенные в результатепроверок.
Выберем среди них некоторое «перспективное» подмножество d l¢0 .Применим к нему функцию ветвления b , в результате получим разбиениеd1,K, d N этого множества и, следовательно, новое разбиение d1¢ ,K, d l¢0 -1 ,d1,K, d N , d l¢0 +1,K, d L¢ ¢ множества неотброшенных решений. После этого начинается следующий шаг алгоритма.Чтобы завершить описание метода, уточним способ выбора «перспективного» подмножества. Имеется два основных правила: одновременного ветвления и одностороннего ветвления.
При одновременном ветвлении функцияветвления может быть применена к любому элементу разбиения. Чаще всеговыбор элемента d l¢0 производится по правилу l0 = arg min H ( d l¢ ).1£ l £ L¢При одностороннем ветвлении выбор разбиваемого подмножества предписан от начала до конца. Перспективным является, например, первый илипоследний элемент разбиения.84Конечность алгоритма следует из того, что на каждом шаге алгоритма хотя бы один из элементов разбиения либо отбрасывается, либо разбивается наподмножества, каждое из которых состоит из меньшего числа атомарныхмножеств. Далее атомарные множества всегда отбрасываются. И, наконец,число атомарных множеств является конечным.Пусть Q = Q1 È Q2 , где Q1 – объединение подмножеств отброшенных попервому правилу, Q2 – объединение подмножеств отброшенных при проверке по второму правилу.Если Q * Ç Q1 ¹ Æ , то рекорд, полученный алгоритмом, является оптимальным решением вне зависимости от того, как задана функция x (d ) .В противном случае, если Q * Ç Q1 = Æ , то Q* Í Q2 .
Следовательно, существует набор подмножеств {d i } таких, что Q* Ç d i ¹ Æ , d i Í Q2 для каждого i и Q* Í È d i .iРассмотрим два случая.Случай 1. Для любого множества d , если функция x (d ) определена, тоf ( x ( d )) = inf f ( x ) .xÎdИз определения множества Q2 следует, что функция x ( d i ) определенадля каждого i и является оптимальным решением задачи. Согласно алгоритму смена рекорда происходит только при реализации условия 2. Пусть d1 –первое подмножество, отброшенное по условию 2. Тогда из предыдущих рассуждений следует, что f ( x 0 ) £ f ( x ( d1 )) и, следовательно, x 0 – оптимальноерешение.Случай 2.
Допустим, что для любого множества d Í Q , для которого определена функция x (d ) , выполняется неравенство:f ( x (d )) £ (1 + e ) f ( x* ( d )) ,где x* ( d ) – наилучшее решение в подмножестве d , e > 0 .Рассуждаякаквпредыдущемпункте,получим,что0*f ( x ) £ f ( x ( d1 )) £ (1 + e ) f ( x ( d1 )) . Из определения множества d1 следует,что x 0 является e -оптимальным решением.Таким образом, при разработке алгоритма МВГ, исходя из специфики рассматриваемой задачи, необходимо конкретизировать и определить следующие составные элементы общей схемы:– атомарные множества решений;– способ задания подмножеств решений;– функцию ветвления;– способ вычисления нижней границы;– функцию выбора наилучшего решения;85– правила выбора перспективного элемента разбиения.В следующем параграфе будет показано, как данная схема может быть реализована для решения задачи нелинейного программирования.§ 5.
Метод ветвей и границ для решения задач нелинейного программированияРассмотрим задачу минимизации нелинейной функции f на параллелепипедеf ( x ) ® inf ,xÎQгде Q = {x = ( x1,K, xn ) ai £ xi £ bi , i = 1,K, n} .Считаем, что целевая функция f удовлетворяет условию Липшица с константой L = const > 0 :(18)f ( x) - f ( y) £ L x - y ¥ , x Î Q , y ÎQ .Из (18) следует, что f – непрерывная функция, следовательно, достигаетсвоего минимального значения f * на параллелепипеде.Выберем на отрезке [a j , b j ] оси j следующие точки:mx1j = a j + h / 2 , x 2j = x1j + h ,…, x ij+1 = x ij + h , x j j = min{ x1j + ( m j - 1)h,b j } ,где h = 2e / L – шаг сетки, m j – натуральное число, удовлетворяющее неравенствуm j -1xj<b j -h£ x1j + ( m j - 1)h .2iНа параллелепипеде Q введем сетку Qh = {x i1 Kin = ( x1i1 , x2i2 ,K, x jj ,K, xnin )} ,iгде j -ая координата x jj точки x i1Kin принимает одно из следующих значеmний: x1j , x 2j K x j j .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
