![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод ветвей и границ
Метод можно применять как к полностью, так и частично целочисленным задачам. Метод заключается в построении дерева задач. Оценка V – это значение критерия, заведомо не хуже оптимального, а рекорд Z – достигнутое в процессе решения значение критерия исходной задачи. Задача будет порождающей только при условии, что ее оценка лучше рекорда. При этом уровень, на котором находится задача, не имеет значения. Рассмотрим метод применительно к линейной целочисленной задаче. Используется разбиение на две задачи, то есть строится бинарное дерево. При этом для целочисленных множеств выполняются соотношения Алгоритм: 1. Задается начальное значение рекорда и в список задач помещается исходная задача без требования целочисленности переменных. 2. Анализируется список задач: если он пуст, то переход на шаг 6. Иначе выбирается одна из задач с удалением ее из списка. 3. Выбранная задача решается одним из методов линейного программирования. Если задача неразрешима или оптимальное значение критерия L* £ Z, ветвь обрывается (задача прозондирована). Переход на шаг 2. 4. Полученное решение анализируется на целочисленность. Если решение целочисленное, оно фиксируется, рекорду присваивается оптимальное значение критерия решенной непрерывной задачи (Z: = L*), ветвь обрывается и осуществляется переход на шаг 2. 5. Выбирается одна из переменных, имеющих нецелочисленные значения. По ней производится ветвление: порождаются 2 задачи, одна образуется присоединением к решенной (родительской) задаче условия хj £ 6. Вывод результатов (если значение рекорда больше начального, получено оптимальное решение исходной задачи, иначе задача неразрешима). Число решаемых задач существенно зависит от выбора задачи из списка и переменной для ветвления. Из алгоритма, что ветвь обрывается по одной из трех причин: - неразрешимость задачи; - задача имеет целочисленное решение; - верхняя оценка не больше рекорда. Метода ветвей и границ имеет преимущества в сравнении с методом отсечений: накопление ошибок менее значительное, так как решение идет по разным ветвям; при принудительной остановке процесса решения высока вероятность получения целочисленного результата, но без установления его оптимальности; при решении непрерывных задач размеры симплекс-таблиц не увеличиваются. Недостатки метода ветвей и границ: - Нельзя оценить число задач, которые придется решать; Отсутствие признака оптимальности. Оптимальность устанавливается только по исчерпании списка задач; Размерность ограничена примерно 100.
|