6 Задачи линейного программирования (1013406), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Вычисляются значенияфункции f ( x) на оптимальных решениях обеих задач. Если ни одна из них не имеет целочисленного решения, то выбирается задача для приоритетного дальнейшего ветвленияпо установленному правилу: например приоритетному ветвлению подлежит та задача, вкоторой значение f ( x ) на оптимальном нецелочисленном решении максимально. Допус-   тим, что f x 1  f x 2 и задача ЗЛП-1 первой ветвится на ЗЛП-3 и ЗЛП-4, которые решаются симплекс-методом без учета требований на целочисленность с последующиманализом решений.

Если ни одна из задач ЗЛП-3 и ЗЛП-4 не имеет целочисленного решения, приступают к ветвлению задачи ЗЛП-2.Процесс ветвления продолжается до тех пор, пока не будет получено в одной изветвей целочисленное решение. Пусть задача ЗЛП-4 (рис. 2) имеет целочисленное решение. Обозначим f – значение функции на первом целочисленном решении: f  f x 4  . Соответствующее целочисленное решение включается в множество X  возможных оптимальных решений исходной задачи. После того как найдено первое целочисленное решение, вопрос о дальнейшем ветвлении других задач решается на основании сравнениязначений f (x k  ) на оптимальных нецелочисленных решениях в оставшихся ветвях созначением f . Если f x k   f для всех оставшихся k , то расчет закончен.

Решениями исходнойзадачи являются те целочисленные решения x k  , для которых f ( x k  )  f . Если62 f x k   f , то соответствующая этому номеру k задача ветвится далее. Так, на рис. 2  имеем f x 2   f и f x 3   f . Задача ЗЛП-2 подлежит ветвлению на ЗЛП-5 и ЗЛП-6, аЗЛП-3 не подлежит ветвлению. Задача ЗЛП-6 не имеет решения, так как множество допустимых решений пустое, и поэтому далее она не рассматривается. Задача ЗЛП-5 имеетнецелочисленное решение x 5 , f (x 5 ) .

Если f x 5   f , то решение задачи закончено и x   x 4 , f ( x  )  f . В противном случае задача ЗЛП-5 ветвится дальше.Если в одной из задач получено целочисленное решение, то ее ветвление далее непроизводится. Если соответствующее значение целевой функции не меньше f , решениесчитается принадлежащим множеству X  возможных оптимальных решений исходнойзадачи. Если значение целевой функции меньше f , целочисленное решение не включается в множество X  .Таким образом, ветвление какой-либо задачи заканчивается, если выполняется одно из условий, а именно: решение целочисленное; значение целевой функции данной задачи не больше f ; множество допустимых решений пустое.Если ветвление всех задач закончено, то в множестве X  выбирается решение(решения), которому соответствует наибольшее значение целевой функции.

Оно и является решением исходной задачи. Если множество X  пустое, то исходная задача не имеет решения.Алгоритм определяет правила ветвления задач и правила окончания ветвления (нахождения границ), что соответствует его названию.З а м е ч а н и е. Распространенным методом решения задач линейного целочисленного программирования, опирающимся на сведение исходной задачи к решению последовательности задач линейного программирования без учета требования целочисленности, является метод Гомори [1,2].63.

Характеристики

Список файлов лекций