![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод ветвей и границ. Решение целочисленного линейного программирования.
Метод вариаций используется в задачах, где можно произвести полный анализ задач, т.е. полный перебор вариантов. Если такое невозможно, то используются методы неполного перебора, напр. Метод ветвей и границ: Нужно найти х0 Алгоритм: 11. Мн-во М разбиваем на не пересекаемые подмн-ва: 12. На каждом подмн-ве находим границу. Сn* – точная граница, если 13. Если есть точные границы у подмн-в, то находим самую наименьшую из них. Т.е. подмн-ва, у которых границы Ci > Cn исключаем из рассмотрения. 14. Если все подмн-ва исключены, то останавливаем алгоритм. 15. Если существует мн-во, у которого Сi*< Сn, то данное подмн-во снова разбиваем и переходим к п.2. Для реализации алгоритма используется схема: Целочисленное линейное программирование: Общий вид задачи: 1) Способ вычисления оценок: Для вычисления оценок уберем условия целочисленности переменных. Получим обычную задачу линейного прог-я. В этом случае число допустимых планов увеличивается. Оптимальное значение целевой функции будет оценкой сверху (задача на максимум). В этом случае решение х* будет иметь целочисленные координаты, а значит этот вектор и есть решение исходной задачи. 2) Способ ветвления: Пусть координата xj* не является целой. Все допустимые планы в этом случае можно разбить на 2 части по след. Признаку: 1) Xj< = C, C=[xj*] 2) Xj> = C+1, C=[xj*]
|