Читайте также:
|
|
Ограничения от целочисленной задачи называются ослабленной задачей.
Метод Гомори
(1)
(
(2) (
Метод Гомори начинается с решения симплекс методом ослабленной задачи. После того, как будет найдено оптимальное решение ослабленной задачи, просматривают все компоненты вектора . Если в результате решения, ослабленной задачи, переменная принимает дробное значение, то к системе (2) добавляют новое неравенство.
В неравенстве (3) обозначено … последнее значение полученное в симплекс таблице, а - дробная часть
… Это добавление к исходной задачи называется отсечение Гомори или правильное отсечение – мы отсекаем от области допустимых решений некоторую часть, не отбрасывая при этом ни одного целочисленного решения.
Решается система (2)-(3) и опять проверяется значение на целочисленность. Если решений слишком много, то неравенство (3) определяется как наибольшая дробная часть
Метод ветвей и границ (branches and boundaries – B&B)
…
…
…
…
Мы разбиваем исходную задачу, на две задачи. Такой процесс называется дихотомией (ветвление). Оптимальное решение может находиться либо в ЛП1 или в ЛП2.
…
Задача ЛП1 удовлетворяет условиям целочисленности. Мы говорим, что задача ЛП1 прозондирована.
Задача ЛП2
Последовательность решения
Зададим нижнюю границу -
Последовательность
1. Зондирование или ослабление границ
Задача называется задачей ЛПi. Зондируем решаем и можем прийти к:
a. Оптимальное решение не может улучшить значение текущей границы.
b. ЛПi имеет решение лучше, чем исходная задача.
c. ЛПi не имеет решения.
a. …
b. Если задача ЛПi не прозондирована, то переходим к шагу 2.
2. Ветвление
Выбираем одну из переменных исключаем из простанства допустимых решений
…
17.10.12
Дата добавления: 2015-01-12; просмотров: 34 | Поможем написать вашу работу | Нарушение авторских прав |