Калькулятор целочисленного программирования (Метод ветвей и границ)

Решение задач линейного программирования с целочисленными ограничениями методом ветвей и границ с визуализацией дерева и отсечений.

Размерность задачи

Цель

Целевая функция — Максимизация Z

x1
+
x2

Ограничения

C1
x1
+
x2
C2
x1
+
x2
Дискретная оптимизация и целочисленное программирование

Целочисленное линейное программирование и метод ветвей и границ

Узнайте, как алгоритм ветвей и границ (Branch and Bound) исследует дерево релаксаций, отсекает неперспективные ветви и находит точный оптимум.

1. Какую задачу решает целочисленное программирование?

В стандартных задачах линейного программирования переменные считаются непрерывными. Однако в реальном управлении операциями многие объекты неделимы: число работников, рейсов, станков или бинарные решения 0-1. Задачи ЦЛП требуют xⱼ ∈ ℤ. Поскольку область допустимых решений представляет собой дискретную сетку точек, градиентные алгоритмы не применимы, что требует использования методов направленного перебора, таких как алгоритм ветвей и границ.

2. Алгоритм метода ветвей и границ (Branch & Bound)

Шаг 1: Непрерывная релаксация задачи ЛП

Условие целочисленности временно снимается (допуская xⱼ ∈ ℝ), задача решается симплекс-методом. Значение Z_LP задает теоретическую верхнюю оценку для максимизации.

Шаг 2: Проверка целочисленности и ветвление

Если решение непрерывной задачи целочисленно, оно оптимально. Если переменная xₖ дробная со значением v, задача делится на две ветви: левую (xₖ ≤ ⌊v⌋) и правую (xₖ ≥ ⌈v⌉).

Шаг 3: Вычисление оценок в узлах

Для каждого узла дерева решается непрерывная релаксация и фиксируется 'рекорд' — наилучшее найденное допустимое целочисленное решение Z*.

Шаг 4: Отсечение (зондирование) ветвей

Ветвь закрывается без дальнейшего ветвления, если: (1) Задача не имеет решений, (2) Оценка узла Z_node ≤ Z* (ветвь бесперспективна), (3) Получено целочисленное решение (обновляется Z* при превышении рекорда).

3. Разобранный пример: целочисленная задача с 2 переменными

Почему простое округление приводит к ошибкам и как полное дерево из 9 узлов сходится к Z* = 40.

Максимизировать Z = 5x₁ + 8x₂
Ограничение 1: x₁ + x₂ ≤ 6
Ограничение 2: 5x₁ + 9x₂ ≤ 45
Неотрицательность: x₁ ≥ 0, x₂ ≥ 0
Целочисленность: x₁, x₂ ∈ ℤ (обе переменные должны быть целыми числами)

Почему эвристическое округление приводит к ошибкам

Непрерывное решение дает x₁ = 2,25, x₂ = 3,75 при Z = 41,25. Округление до ближайших целых (2, 4) нарушает второе ограничение: 5(2) + 9(4) = 46 > 45 (недопустимо!). Округление вниз до (2, 3) дает Z = 34, что на 6 единиц хуже истинного оптимума. Метод ветвей и границ полностью исключает подобные погрешности.

Полное дерево поиска метода ветвей и границ (обход в глубину DFS)

Tree NodeBranch ConstraintLP Relaxation PointObjective ZBranch & Bound Action
Узел 1 (Корень)Непрерывная релаксация ЛП (без ограничений целочисленности)x₁ = 2,25; x₂ = 3,75Z = 41,25Дробная переменная x₁ = 2,25. Ветвление: x₁ ≤ 2 (Узел 2) и x₁ ≥ 3 (Узел 3).
Узел 2Добавлено ограничение: x₁ ≤ 2 (из корня)x₁ = 2,00; x₂ = 35/9 ≈ 3,89Z = 370/9 ≈ 41,11Дробная переменная x₂ ≈ 3,89. Ветвление: x₂ ≤ 3 (Узел 4) и x₂ ≥ 4 (Узел 5).
Узел 4Узел 2 + ограничение: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3)x₁ = 2; x₂ = 3Z = 34,00Целочисленное решение! Начальный рекорд: Z* = 34 в точке (2, 3).
Узел 5Узел 2 + ограничение: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4)x₁ = 1,80; x₂ = 4,00Z = 41,00Дробная переменная x₁ = 1,80 (Z = 41 > 34). Ветвление: x₁ ≤ 1 (Узел 6) и x₁ ≥ 2 (Узел 7).
Узел 6Узел 5 + ограничение: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4)x₁ = 1,00; x₂ = 40/9 ≈ 4,44Z = 365/9 ≈ 40,56Дробная переменная x₂ ≈ 4,44 (Z ≈ 40,56 > 34). Ветвление: x₂ ≤ 4 (Узел 8) и x₂ ≥ 5 (Узел 9).
Узел 8Узел 6 + ограничение: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4)x₁ = 1; x₂ = 4Z = 37,00Целочисленное решение! Так как 37 > 34, обновляем рекорд: Z* = 37 в (1, 4).
Узел 9Узел 6 + ограничение: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0)x₁ = 0; x₂ = 5Z = 40,00Целочисленное решение! Так как 40 > 37, обновляем рекорд: Z* = 40 в (0, 5) (ГЛОБАЛЬНЫЙ ОПТИМУМ).
Узел 7Узел 5 + ограничение: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4)Нет допустимых решений (5(2)+9(4) = 46 > 45)НедопустимоОтсечение по недопустимости.
Узел 3Добавлено ограничение: x₁ ≥ 3 (из корня)x₁ = 3; x₂ = 3Z = 39,00Целочисленное решение, но Z = 39 ≤ Z* (40). Отсечение по оценке.

Доказанный точный оптимум

Все 9 узлов дерева поиска исследованы или отсечены. Глобальный целочисленный оптимум: x₁* = 0, x₂* = 5 с максимумом Z* = 40. (Полностью соответствует калькулятору).

4. Типичные ошибки студентов

⚠

Предположение, что оптимум лежит рядом с непрерывной точкой

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

⚠

Игнорирование отсечения бесперспективных узлов

Продолжение ветвления в узле, где оценка Z меньше или равна текущему рекорду Z*, приводит к экспоненциальному росту лишних вычислений.

⚠

Некорректная запись ограничений ветвей

Ветвление должно строго разделять интервал: xₖ ≤ ⌊v⌋ и xₖ ≥ ⌈v⌉. Использование строгих неравенств (< или >) приводит к потере целых точек.