Реферат Курсовая Конспект
Решение задачи методом ветвей и границ - раздел История, Историческая справка Пусть ...
|
Пусть
- целые.
Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных.
Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.
Если среди компонент плана имеются дробные числа, то необходимо осуществить переход к новым планам, пока не будет найдено решение задачи.
Метод ветвей и границ основан на предположении, что наш оптимальный нецелочисленный план дает значение функции, большее, чем всякий последующий план перехода.
Пусть переменная в плане – дробное число. Тогда в оптимальном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу , либо больше или равно ближайшему большему целому числу .
Определяя эти числа, находим симплексным методом решение двух задач линейного программирования
- целые.
и
- целые.
Возможны четыре случая при решении этой пары задач:
1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции дают решение исходной задачи.
2. Одна из задач неразрешима, а другая имеет нецелочисленный оптимальный план. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу и строим две задачи, аналогичные предыдущим.
3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение.
4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. И строим две задачи.
Таким образом, при решении задачи получаем схему:
1. Находим решение задачи линейного программирования без учета целочисленности.
2. Составляет дополнительные ограничения на дробную компоненту плана.
3. Находим решение двух задач с ограничениями на компоненту.
4. Строим в случае необходимости дополнительные ограничения, согласно возможным четырем случаям получаем оптимальный целочисленный план либо устанавливаем неразрешимость задачи.
– Конец работы –
Эта тема принадлежит разделу:
Большой класс прикладных задач оптимизации сводится к задачам целочисленного программирования Для решения этих задач широко применяются... При решении многомерных задач оптимизации предлагается совместное применение... Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Решение задачи методом ветвей и границ
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов