Метод нулевого базиса

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

История возникновения

Метод нулевого базиса был разработан в середине XX века в рамках развития теории линейного программирования. Его появление связано с необходимостью решения задач, в которых стандартные методы построения начального базиса, такие как метод искусственного базиса (М-метод), оказывались неэффективными из-за большого числа искусственных переменных. Конкретные авторы метода нулевого базиса в открытых источниках не указываются, однако он рассматривается как частный случай более общего подхода к построению начального решения в симплекс-методе. В советской и российской научной литературе метод нулевого базиса описывался в учебных пособиях по математическому программированию, например, в работах В. А. Емельянова, А. А. Корбута и других авторов.

Суть метода

Метод нулевого базиса применяется в задачах линейного программирования, записанных в канонической форме:

\[ \begin{cases} \mathbf{A}\mathbf{x} = \mathbf{b}, \\ \mathbf{x} \geq \mathbf{0}, \\ \mathbf{c}^T \mathbf{x} \to \min. \end{cases} \]

Здесь \(\mathbf{A}\) — матрица ограничений размера \(m \times n\), \(\mathbf{b}\) — вектор правых частей, \(\mathbf{c}\) — вектор коэффициентов целевой функции. Если в исходной задаче присутствуют неравенства типа «≥», они предварительно преобразуются в равенства введением дополнительных (остаточных) переменных.

Основная идея метода нулевого базиса заключается в том, что в качестве начального базиса выбирается набор из \(m\) переменных, среди которых часть может быть равна нулю. При этом не требуется вводить искусственные переменные, как в М-методе. Вместо этого начальное базисное решение строится следующим образом:

1. Выбирается подмножество из \(m\) переменных, которые будут базисными. Обычно это переменные, соответствующие столбцам матрицы \(\mathbf{A}\), образующим единичную подматрицу (если такая есть), или переменные, которые можно сделать базисными путём элементарных преобразований.
2. Значения базисных переменных вычисляются из системы уравнений \(\mathbf{A}\mathbf{x} = \mathbf{b}\). Если среди них оказываются отрицательные, то решение недопустимо, и требуется пересчёт.

Метод нулевого базиса особенно эффективен, когда в матрице \(\mathbf{A}\) имеются столбцы, соответствующие единичным векторам (например, после введения дополнительных переменных для неравенств типа «≤»). В таких случаях начальный базис формируется из этих переменных, и их значения равны соответствующим компонентам вектора \(\mathbf{b}\). Если же все компоненты \(\mathbf{b}\) неотрицательны, то начальное решение является допустимым.

Алгоритм применения

Алгоритм метода нулевого базиса включает следующие шаги:

1. Приведение задачи к канонической форме. Все ограничения-неравенства преобразуются в равенства введением дополнительных переменных. Целевая функция приводится к виду минимизации.
2. Формирование начальной симплекс-таблицы. В таблицу включаются все переменные, включая дополнительные. Если в матрице ограничений есть единичные столбцы, они используются как базисные.
3. Проверка допустимости. Вычисляются значения базисных переменных. Если все они неотрицательны, начальное решение считается допустимым. В противном случае применяются методы устранения отрицательности (например, двойственный симплекс-метод или переход к другому набору базисных переменных).
4. Итерации симплекс-метода. После получения допустимого базисного решения выполняется стандартная процедура симплекс-метода: выбор разрешающего столбца, разрешающей строки, пересчёт таблицы до достижения оптимальности.

Пример применения

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

\[ \begin{aligned} & x_1 + 2x_2 \geq 4, \\ & 3x_1 + x_2 \geq 6, \\ & x_1, x_2 \geq 0, \\ & F = 2x_1 + 3x_2 \to \min. \end{aligned} \]

Приведём к канонической форме, введя остаточные переменные \(x_3\) и \(x_4\) со знаком минус:

\[ \begin{cases} x_1 + 2x_2 - x_3 = 4, \\ 3x_1 + x_2 - x_4 = 6, \\ x_1, x_2, x_3, x_4 \geq 0. \end{cases} \]

Матрица ограничений не содержит единичных столбцов. Для применения метода нулевого базиса можно взять в качестве начальных базисных переменных \(x_3\) и \(x_4\), выразив их через остальные:

\[ x_3 = x_1 + 2x_2 - 4, \quad x_4 = 3x_1 + x_2 - 6. \]

При \(x_1 = x_2 = 0\) получаем \(x_3 = -4\), \(x_4 = -6\), что недопустимо. Однако метод нулевого базиса позволяет выбрать другой набор базисных переменных. Например, можно взять \(x_1\) и \(x_2\) в качестве базисных, решив систему:

\[ \begin{cases} x_1 + 2x_2 = 4 + x_3, \\ 3x_1 + x_2 = 6 + x_4. \end{cases} \]

При \(x_3 = x_4 = 0\) получаем \(x_1 = 1.6\), \(x_2 = 1.2\), что является допустимым базисным решением. Таким образом, метод нулевого базиса позволяет начать симплекс-процесс с этого решения, не вводя искусственных переменных.

Сравнение с другими методами

Метод нулевого базиса часто сравнивают с методом искусственного базиса (М-методом). Основные различия:

• М-метод вводит искусственные переменные в каждое ограничение, не содержащее базисной переменной, и добавляет их в целевую функцию с большим штрафным коэффициентом \(M\). Это увеличивает размерность задачи и может приводить к вычислительным погрешностям.
• Метод нулевого базиса не требует введения дополнительных переменных, что сокращает размерность симплекс-таблицы. Однако он применим не всегда: для его использования необходимо, чтобы в матрице ограничений можно было выделить \(m\) линейно независимых столбцов, образующих базис, и чтобы соответствующее базисное решение было неотрицательным (или могло быть сделано таковым путём преобразований).

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

Применение

Метод нулевого базиса используется в задачах линейного программирования, где:

• Исходные ограничения содержат равенства или неравенства типа «≥»;
• Матрица ограничений имеет разреженную структуру, позволяющую легко выделить базисные столбцы;
• Требуется минимизировать вычислительные затраты, связанные с введением искусственных переменных.

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

Критика и ограничения

Основные недостатки метода нулевого базиса:

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

В современной вычислительной практике метод нулевого базиса уступает место более универсальным алгоритмам, таким как метод внутренней точки или модифицированный симплекс-метод с автоматическим выбором начального базиса.

Источники

• Емельянов В. А., Корбут А. А. Математическое программирование. — М.: Наука, 1976.
• Таха Х. А. Введение в исследование операций. — М.: Вильямс, 2005.
• Лунгу К. Н. Линейное программирование. — М.: Физматлит, 2008.
• Карманов В. Г. Математическое программирование. — М.: Наука, 1986.