Вырожденность плана

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

Математическая формулировка

Рассмотрим задачу линейного программирования в канонической форме:

\[ \begin{aligned} & \text{минимизировать} \quad \mathbf{c}^T \mathbf{x} \\ & \text{при условиях} \quad A \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \ge \mathbf{0}, \end{aligned} \]

где \(A\) — матрица размера \(m \times n\) (\(m\) — число ограничений, \(n\) — число переменных), \(\mathbf{b} \ge \mathbf{0}\), \(\mathbf{x} \in \mathbb{R}^n\).

Пусть \(\mathbf{x}_B\) — базисное решение, соответствующее базису \(B\) (множеству индексов базисных переменных). Решение \(\mathbf{x}_B\) является вырожденным, если хотя бы одна компонента \(\mathbf{x}_B\) равна нулю. Иными словами, число строго положительных базисных переменных меньше \(m\). В противном случае решение называется невырожденным.

Причины возникновения

Вырожденность плана возникает, когда в системе ограничений \(A \mathbf{x} = \mathbf{b}\) имеется избыточность (линейная зависимость) или когда точка пересечения гиперплоскостей, задающих ограничения, совпадает с пересечением более чем \(m\) гиперплоскостей. Типичные причины:

• Линейная зависимость ограничений: если строки матрицы \(A\) линейно зависимы, то в любой базис входит не более \(m-1\) независимых ограничений, и часть базисных переменных обязательно будет нулевой.
• Избыточные ограничения: некоторые ограничения могут быть следствием других, что приводит к тому, что точка оптимума лежит на пересечении большего числа гиперплоскостей, чем необходимо.
• Специфика задачи: в транспортных задачах, задачах о назначениях и других задачах с целочисленными данными вырожденность встречается часто из-за структуры матрицы ограничений.

Последствия для симплекс-метода

В симплекс-методе вырожденность может вызывать следующие проблемы:

1. Зацикливание: при вырожденном решении симплекс-метод может бесконечно перебирать базисы, не улучшая значение целевой функции. Это происходит, когда при переходе к новому базису значение целевой функции не меняется, и алгоритм возвращается к ранее посещённому базису. Классический пример — задача Бела (Beale, 1955), где зацикливание возникает при отсутствии антициклических правил.

1. Неоднозначность выбора разрешающего элемента: при вырожденности отношение \(\theta = \min_{i: a_{is} > 0} \frac{x_{Bi}}{a_{is}}\) может быть равно нулю для нескольких строк, что приводит к множеству возможных разрешающих элементов.

1. Снижение скорости сходимости: даже если зацикливания нет, вырожденность может приводить к «пробуксовке» — многократным переходам между вырожденными базисами без улучшения целевой функции.

Методы борьбы с вырожденностью

Для предотвращения зацикливания и обеспечения сходимости симплекс-метода разработаны специальные правила:

Правило Бленда (Bland's rule)

Правило Бленда (или правило минимального индекса) предписывает:

• Выбирать в качестве вводимой в базис переменную с наименьшим индексом среди тех, для которых \(c_j - z_j < 0\) (в задаче минимизации).
• Если есть несколько кандидатов на вывод из базиса, выбирать переменную с наименьшим индексом.

Это правило гарантирует, что симплекс-метод не зациклится, но может замедлить сходимость.

Правило лексикографического выбора

При выборе разрешающего элемента используется лексикографическое сравнение строк симплекс-таблицы. Это позволяет однозначно определить, какую переменную выводить, и предотвращает зацикливание.

Метод возмущений (perturbation method)

Искусственно изменяются правые части ограничений \(\mathbf{b}\) на малые случайные величины, что делает решение невырожденным. После решения задачи возмущение убирается. Этот метод теоретически обоснован, но на практике может быть вычислительно затратным.

Элиминация избыточных ограничений

Перед решением задачи проводится предварительный анализ на линейную зависимость строк матрицы \(A\). Избыточные ограничения удаляются, что снижает вероятность вырожденности.

Примеры

Пример 1: Простая вырожденная задача

Рассмотрим задачу:

\[ \begin{aligned} & \text{максимизировать} \quad x_1 + x_2 \\ & \text{при условиях} \quad x_1 + x_2 \le 1, \quad x_1 \le 1, \quad x_2 \le 1, \quad x_1, x_2 \ge 0. \end{aligned} \]

В точке \((1,0)\) активны ограничения \(x_1 + x_2 \le 1\) и \(x_1 \le 1\), а также \(x_2 \ge 0\). Базисное решение будет вырожденным, так как \(x_2 = 0\) является базисной переменной.

Пример 2: Зацикливание (задача Бела)

Задача Бела (Beale, 1955) демонстрирует зацикливание симплекс-метода без антициклических правил:

\[ \begin{aligned} & \text{минимизировать} \quad -\frac{3}{4}x_1 + 150x_2 - \frac{1}{50}x_3 + 6x_4 \\ & \text{при условиях} \quad \frac{1}{4}x_1 - 60x_2 - \frac{1}{25}x_3 + 9x_4 \le 0, \\ & \quad \frac{1}{2}x_1 - 90x_2 - \frac{1}{50}x_3 + 3x_4 \le 0, \\ & \quad x_3 \le 1, \quad x_1, x_2, x_3, x_4 \ge 0. \end{aligned} \]

При стандартном симплекс-методе возникает цикл из 6 итераций, после которого алгоритм возвращается к исходному базису.

Вырожденность в других методах

Помимо симплекс-метода, вырожденность плана проявляется в:

• Методах внутренней точки: вырожденность может приводить к плохой обусловленности матриц и замедлению сходимости.
• Целочисленном программировании: вырожденные решения часто возникают при отсечениях Гомори.
• Транспортной задаче: вырожденность здесь — распространённое явление, для её устранения применяют введение фиктивных перевозок с нулевой стоимостью.

Историческая справка

Проблема вырожденности была осознана вскоре после появления симплекс-метода (Дж. Данциг, 1947). Первый пример зацикливания был опубликован А. Хоффманом (A. Hoffman, 1953), а затем более известный пример — Э. Белом (E. Beale, 1955). Правило Бленда было предложено в 1977 году. Теоретическое обоснование сходимости симплекс-метода при вырожденности долгое время оставалось открытой проблемой, пока в 1970-х годах не были разработаны антициклические правила.

Источники

• Данциг Дж. Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
• Бленд Р. (Bland R. G.) New finite pivoting rules for the simplex method // Mathematics of Operations Research. — 1977. — Vol. 2, No. 2. — P. 103–107.
• Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. — М.: Мир, 1982.
• Лунгу К. Н. Линейное программирование. — М.: Физматлит, 2009.
• Beale E. M. L. Cycling in the dual simplex algorithm // Naval Research Logistics Quarterly. — 1955. — Vol. 2, No. 4. — P. 269–275.