Метод ветвей и границ

Назначение сервиса. Сервис предназначен для решения задач целочисленного линейного программирования в онлайн режиме методом ветвей и границ. Другое название метода - метод Ленд и Дойг. (см. пример решения). При двух переменных (x1, x2) применяется графическое решение, при большем количестве переменных - симплексный метод. В ходе решения формируется Дерево решения задачи.
Инструкция. Укажите количество переменных и число ограничений. Полученное решение сохраняется в формате MS Word с проверкой решения в MS Excel.
Выберите количество переменных
Выберите количество строк (количество ограничений)
При этом ограничения типа xi ≥ 0 не учитывайте.
Дерево решения задачи методом ветвей и границ
Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов. При использовании метода ветвей и границ область допустимых решений (ОДР) исходной задачи определенным способом разбивается на непересекающиеся подмножества, и решаются подзадачи, т.е. задачи на этих подмножествах с той же ЦФ и без учета условия целочисленности (как задачи ЛП). Если в результате получено оптимальное нецелочисленное решение, ОДР подзадачи снова разбивается на части и этот процесс продолжается до тех пор, пока не будет найдено оптимальное целочисленное решение исходной задачи.
Если в задаче на максимум при решении подзадач получаются оптимальные целочисленные решения, то запоминаются те из них, которым соответствуют возрастающие значения ЦФ. Если полученное «непрерывное» решение подзадачи оказывается не лучше сохраненного целочисленного решения, то такая подзадача исключается из списка задач. Название этого метода объясняется тем, что в процессе решения задача последовательно «ветвится», разбиваясь на более простые подзадачи.

Примечание: метод ветвей и границ используется также и в задаче коммивояжера.

Пример. В задаче методом Гомори (или методом ветвей и границ) найти оптимальные решения задач целочисленного линейного программирования. Дать геометрическую интерпретацию процесса решений задач.
Z=3x1 + 2x2 → max
при ограничениях:
x1 + x2 ≤ 13
x1 - x2 ≤ 6
-3x1 + x2 ≤ 9
x1≥0, x2 ≥0
x1, x2 – целые числа.

загрузка...