lopt7 (Лекционный курс), страница 2
Описание файла
Файл "lopt7" внутри архива находится в папке "Лекционный курс". PDF-файл из архива "Лекционный курс", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
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.