![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод ветвей и границ
Идея этого метода состоит в последовательном ветвлении исходного множества решений на дерево подмножеств с нахождением решений на всех подмножествах пока не получим искомое. Как и методе отсекающих плоскостей, процесс начинается с решения задачи отбрасывая условие целочисленности. Если полученное решение не удовлетворяет условию целочисленности, то значение целевой функции дает верхнюю оценку искомого решения и начальное множество Таким образом, исходное множество Находим решение и оценки на множествах. Если оба решения полученные на этих множествах оба целочисленны, то оптимальным будет то, у которого оценка больше. Если же, допустим на множестве Ветвление продолжается до тех пор пока не будет получено целочисленное решение с максимально большой оценкой.
ЛЕКЦИЯ 12.
|