Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






В. 65 Метод отсечений для задачи ЦЛП (идея и общая схема)





Задача целочисленного линейного программирования (ЦЛП).

Канонический вид

В задачу ЛП можно добавить условие:

хÎZn - целочисленное условие. Это означат, что х является n – мерным вектором. Или xjÎZ – целое. Т.е. если взять любую задачу канонического вида и это условие получим задачу ЦЛП.

Нельзя решать без условия целочисленности. Почему нельзя округлять нецелое решение, чтобы получить целое?

1 случай: нас устраивают решения лежащие в этих точках.

Предположим, что вектор градиента направлен вверх и вправо.

* если округлим эту точку, получим другую точку, неудовлетворяющую ограничению.

2 случай:

* решения нет в границе, поэтому, если возьмем точку выше, будет неправильно

Множество в данном примере не включает в себя целые числа.

Метод отсечений:

Убираем условие целочисленности и решаем задачу без него. Мы получим какую-то точку. Если случайно получим целое решение, то всё хорошо, если нет, то специальным образом выбирается дополнительное ограничение, которое отрезает это нецелое решение. Решаем задачу снова. Метод гарантирует, что за конечное число шагов будет найдено целое точное решение, если оно есть.

Отсечения выбираются таким образом, чтобы они были прямыми линиями, обязательно отсекали нецелое решение и не затрагивали бы ни одной целой точки.

 







Date: 2015-12-12; view: 498; Нарушение авторских прав



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию