Калькулятор целочисленного программирования (Метод ветвей и границ)
Решение задач линейного программирования с целочисленными ограничениями методом ветвей и границ с визуализацией дерева и отсечений.
Размерность задачи
Цель
Целевая функция — Максимизация Z
Ограничения
Целочисленное линейное программирование и метод ветвей и границ
Узнайте, как алгоритм ветвей и границ (Branch and Bound) исследует дерево релаксаций, отсекает неперспективные ветви и находит точный оптимум.
1. Какую задачу решает целочисленное программирование?
В стандартных задачах линейного программирования переменные считаются непрерывными. Однако в реальном управлении операциями многие объекты неделимы: число работников, рейсов, станков или бинарные решения 0-1. Задачи ЦЛП требуют xⱼ ∈ ℤ. Поскольку область допустимых решений представляет собой дискретную сетку точек, градиентные алгоритмы не применимы, что требует использования методов направленного перебора, таких как алгоритм ветвей и границ.
2. Алгоритм метода ветвей и границ (Branch & Bound)
Условие целочисленности временно снимается (допуская xⱼ ∈ ℝ), задача решается симплекс-методом. Значение Z_LP задает теоретическую верхнюю оценку для максимизации.
Если решение непрерывной задачи целочисленно, оно оптимально. Если переменная xₖ дробная со значением v, задача делится на две ветви: левую (xₖ ≤ ⌊v⌋) и правую (xₖ ≥ ⌈v⌉).
Для каждого узла дерева решается непрерывная релаксация и фиксируется 'рекорд' — наилучшее найденное допустимое целочисленное решение Z*.
Ветвь закрывается без дальнейшего ветвления, если: (1) Задача не имеет решений, (2) Оценка узла Z_node ≤ Z* (ветвь бесперспективна), (3) Получено целочисленное решение (обновляется Z* при превышении рекорда).
3. Разобранный пример: целочисленная задача с 2 переменными
Почему простое округление приводит к ошибкам и как полное дерево из 9 узлов сходится к Z* = 40.
Почему эвристическое округление приводит к ошибкам
Непрерывное решение дает x₁ = 2,25, x₂ = 3,75 при Z = 41,25. Округление до ближайших целых (2, 4) нарушает второе ограничение: 5(2) + 9(4) = 46 > 45 (недопустимо!). Округление вниз до (2, 3) дает Z = 34, что на 6 единиц хуже истинного оптимума. Метод ветвей и границ полностью исключает подобные погрешности.
Полное дерево поиска метода ветвей и границ (обход в глубину DFS)
| Tree Node | Branch Constraint | LP Relaxation Point | Objective Z | Branch & Bound Action |
|---|---|---|---|---|
| Узел 1 (Корень) | Непрерывная релаксация ЛП (без ограничений целочисленности) | x₁ = 2,25; x₂ = 3,75 | Z = 41,25 | Дробная переменная x₁ = 2,25. Ветвление: x₁ ≤ 2 (Узел 2) и x₁ ≥ 3 (Узел 3). |
| Узел 2 | Добавлено ограничение: x₁ ≤ 2 (из корня) | x₁ = 2,00; x₂ = 35/9 ≈ 3,89 | Z = 370/9 ≈ 41,11 | Дробная переменная x₂ ≈ 3,89. Ветвление: x₂ ≤ 3 (Узел 4) и x₂ ≥ 4 (Узел 5). |
| Узел 4 | Узел 2 + ограничение: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3) | x₁ = 2; x₂ = 3 | Z = 34,00 | Целочисленное решение! Начальный рекорд: Z* = 34 в точке (2, 3). |
| Узел 5 | Узел 2 + ограничение: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4) | x₁ = 1,80; x₂ = 4,00 | Z = 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,44 | Z = 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₂ = 4 | Z = 37,00 | Целочисленное решение! Так как 37 > 34, обновляем рекорд: Z* = 37 в (1, 4). |
| Узел 9 | Узел 6 + ограничение: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0) | x₁ = 0; x₂ = 5 | Z = 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₂ = 3 | Z = 39,00 | Целочисленное решение, но Z = 39 ≤ Z* (40). Отсечение по оценке. |
Доказанный точный оптимум
Все 9 узлов дерева поиска исследованы или отсечены. Глобальный целочисленный оптимум: x₁* = 0, x₂* = 5 с максимумом Z* = 40. (Полностью соответствует калькулятору).
4. Типичные ошибки студентов
Предположение, что оптимум лежит рядом с непрерывной точкой
Истинное целочисленное решение может находиться далеко от непрерывного оптимума. Обязательно требуется систематическое ветвление.
Игнорирование отсечения бесперспективных узлов
Продолжение ветвления в узле, где оценка Z меньше или равна текущему рекорду Z*, приводит к экспоненциальному росту лишних вычислений.
Некорректная запись ограничений ветвей
Ветвление должно строго разделять интервал: xₖ ≤ ⌊v⌋ и xₖ ≥ ⌈v⌉. Использование строгих неравенств (< или >) приводит к потере целых точек.