Студопедия  
Главная страница | Контакты | Случайная страница

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

РОЗДІЛ 4. Метод ветвей и границ – один из комбинаторных методов

Читайте также:
  1. IV. РОЗПОДІЛ НАВЧАЛЬНОГО ЧАСУ ЗА РОЗДІЛАМИ, ТЕМАМИ ТА ВИДАМИ НАВЧАЛЬНИХ ЗАНЯТЬ
  2. IV. РОЗПОДІЛ НАВЧАЛЬНОГО ЧАСУ ЗА РОЗДІЛАМИ, ТЕМАМИ ТА ВИДАМИ НАВЧАЛЬНИХ ЗАНЯТЬ.
  3. Б) коли складові частки чітко визначені і відомо, хто із співавторів створив ту чи іншу частину — роздільне співавторство.
  4. Бойові завдання і бойові порядок механізованих підрозділів у наступі.
  5. Взаємодія слідчого з оперативними підрозділами
  6. Взаємозв'язки структури (банку) з іншими організаційними підрозділами
  7. ВИРОБНИЧИЙ ПІДРОЗДІЛ З ВИРОБНИЦТВА ПРОДУКЦІЇ ТВАРИННЦТВА
  8. Висновки до 2 розділу
  9. Висновки до другого розділу
  10. Висновки до першого розділу

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

Суть метода, не прибегая к математическим выкладкам, можно представить следующим образом: множество допустимых решений (планов) Go некоторым образом разбивается на подмножества G1 и G2 (рис. 4.6), каждое из которых этим же или другим способом снова разбивается на подмножества G21 и G22 и так далее. Процесс продолжается до тех пор, пока каждое подмножество не будет представлять собой точку в многомерном пространстве.

Разбиение множества решений на подмножества позволяет в ряде случаев существенно уменьшить объем перебора вариантов и основан на определении нижней границы линейной функции (Ф0) и нижней и верхней границ нецелочисленной компоненты оптимального решения На каждом шаге нецелочисленный план, не способствующий достижению цели задачи (например, Ф(Х*) ≤ Ф0 в задаче максимизации), исключается из дальнейшего рассмотрения.

Пусть задача 1 (задача (4.41) - (4.43) максимизации линейной функции Ф без учета целочисленности) решена симплексным методом и известны нижняя и верхняя границы для каждой переменной xj: vj ≤ xj ≤ wj (j = 1, n), а также нижняя граница линейной функции Фо, то есть, при любом плане Х имеем Ф(Х) ≥ Фо. Предположим для определенности, что только первая компонента х1* оптимального плана Х* задачи 1 не удовлетворяет условию целочисленности. Тогда из области допустимых значений задачи 1исключается область: [x1*]< x1*<[x1*]+1, где [x1*] – целая часть числа x1*. В результате из задачи 1 формируют две задачи: 2 и 3, отличающиеся друг от друга тем, что в задаче 2 кроме ограничений (4.42) задачи 1 добавлено ограничение v1 ≤ x1*≤ [x1*], а в задаче 3 кроме тех же ограничений (4.43) добавлено ограничение [x1*]≤ x1*≤ w1. Получим список из двух задач: 2 и 3.

Решаем одну из них (в любом порядке). В зависимости от полученного решения список задач расширяется, либо сокращается.

Если в результате решения одной из задач (2 или 3) получен нецелочисленный план, для которого Ф(Х*) ≤ Фо, то данная задача исключается из списка. Если Ф(Х*) > Фо, то из данной задачи формируются две новые задачи.

Если полученное решение Х* удовлетворяет условию целочисленности и Ф(Х*) > Фо, то значение Фо корректируется и за величину нижней границы Фо принимается оптимум линейной функции полученного целочисленного плана.

Процесс продолжается до тех пор, пока список задач не будет исчерпан, то есть, все задачи не будут решены.

Процесс формирования процедуры перебора может быть представлен в виде схемы ветвления. Сечение исходной допустимой области Go гиперплоскостью на части G11 и G12 с последующим разделением на G21 и G22 представляет собой построение дерева ветвлений с соответствующими подмножествами, как это показано на рис. 4.4.

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

Выбор оценок при определении границ и схемы ветвления взаимосвязаны и трудно указать общие рекомендации по использованию на практике этого метода.

 

РОЗДІЛ 4


Дата добавления: 2014-12-20; просмотров: 8 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2020 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав