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

Обновлено: 02.07.2024

Инструкция . Укажите количество переменных и число ограничений. Полученное решение сохраняется в формате MS Word с проверкой решения в MS Excel . При этом ограничения типа x_i ≥ 0 не учитывайте.

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

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

Пример №2 .
5x₁ + 2x₂ ≤ 14
2x₁ + 5x₂ ≤ 16
x₁ , x₂ – целые числа
Z = 3x₁ + 5x₂ → max
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Оптимальное значение переменной x₁=1.81 оказалось нецелочисленным.
Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х₁ ≥ 2, а к задаче 12 — условие х₁ ≤ 1.
Эта процедура называется ветвлением по переменной х₁.
Решим графически задачу 11 как задачу ЛП.
5x₁+2x₂≤14 (1)
2x₁+5x₂≤16 (2)
x₁≥2 (3)
x₁≥0 (4)
x₂≥0 (5)

Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
5x₁+2x₂≤14
x₁≥2

Решив систему уравнений, получим: x₁ = 2, x₂ = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16

Решение задачи получилось целочисленным.
Новое значение текущего рекорда будет равно F(X) = 16.
Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом или просто рекордом, а оптимальное значение целочисленной задачи — текущим значением рекорда. Это значение является нижней границей оптимального значения исходной задачи Z*.

Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
2x₁+5x₂≤16
x₁≤1

Решив систему уравнений, получим: x₁ = 1, x₂ = 2.8
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2.8 = 17

Оптимальное значение переменной x₂=2.8 оказалось нецелочисленным.
Разбиваем задачу 12 на две подзадачи 121 и 122.
В первой из них к условиям задачи 121 добавляется условие х₂ ≥ 3, а к задаче 122 — условие х₂ ≤ 2.

Текущий рекорд Z=16≥13, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x₁=0.5 оказалось нецелочисленным.
Разбиваем задачу 121 на две подзадачи 1211 и 1212.
В первой из них к условиям задачи 1211 добавляется условие х₁ ≥ 1, а к задаче 1212 — условие х₁ = 0.

Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x₂=2.48 оказалось нецелочисленным. Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х₂ ≥ 3, а к задаче 12 — условие х₂ ≤ 2.
Эта процедура называется ветвлением по переменной х₂.

Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x₁=0.5 оказалось нецелочисленным. Разбиваем задачу 11 на две подзадачи 111 и 112. В первой из них к условиям задачи 111 добавляется условие х₁ ≥ 1, а к задаче 112 — условие х₁ = 0.

Решим графически задачу 111 как задачу ЛП.
5x₁+2x₂≤14 (1)
2x₁+5x₂≤16 (2)
x₂≥3 (3)
x₁≥1 (4)
x₁≥0 (5)
x₂≥0 (6) Задача не имеет допустимых решений. ОДР представляет собой пустое множество

Читайте также: