Базисные переменные

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

Определение и основные понятия

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

Формально: пусть дана система \(Ax = b\), где \(A\) — матрица размером \(m \times n\), \(x \in \mathbb{R}^n\), \(b \in \mathbb{R}^m\). Если ранг матрицы \(A\) равен \(m\), то существует подмножество из \(m\) переменных, образующих базис. Эти переменные называются базисными, а соответствующие им столбцы матрицы \(A\) образуют базисную матрицу \(B\). Остальные \(n-m\) переменных — свободные.

Свойства базисных переменных

• Невырожденность: базисная матрица \(B\) должна быть невырожденной (det \(B \neq 0\)), иначе система не имеет единственного базисного решения.
• Единственность в точке: для данного базиса базисные переменные однозначно определяются из системы \(B x_B = b\), где \(x_B\) — вектор базисных переменных.
• Нулевые значения свободных: в базисном решении все свободные переменные полагаются равными нулю.
• Число базисных переменных: равно количеству линейно независимых уравнений (рангу системы).

Роль в симплекс-методе

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

Итерация симплекс-метода

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

Пример

Рассмотрим задачу: \[ \begin{cases} x_1 + 2x_2 + x_3 = 4 \\ 2x_1 + x_2 + x_4 = 5 \\ x_1, x_2, x_3, x_4 \geq 0 \end{cases} \] Здесь \(m=2\), \(n=4\). Если выбрать базисные переменные \(x_3\) и \(x_4\), то базисная матрица \(B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\), и базисное решение: \(x_3 = 4\), \(x_4 = 5\), \(x_1 = x_2 = 0\). Это допустимое базисное решение. При переходе к другому базису, например, \(x_1\) и \(x_4\), базисные переменные изменятся.

Классификация базисных переменных

В зависимости от контекста и метода решения выделяют несколько типов базисных переменных:

По типу задачи

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

По допустимости

• Допустимые базисные решения: все базисные переменные неотрицательны (для задач с ограничениями \(x \geq 0\)).
• Недопустимые базисные решения: хотя бы одна базисная переменная отрицательна. Такие решения возникают на промежуточных этапах симплекс-метода при использовании двухфазного метода или метода больших штрафов.

По вырожденности

• Вырожденное базисное решение: хотя бы одна базисная переменная равна нулю. Это может привести к зацикливанию алгоритма.
• Невырожденное: все базисные переменные строго положительны.

Применение в экономике и оптимизации

Базисные переменные широко применяются в экономико-математическом моделировании, в частности:

• Планирование производства: базисные переменные соответствуют объёмам выпуска продукции, которые активно используются в текущем плане.
• Транспортная задача: базисные переменные — это объёмы перевозок по маршрутам, входящим в опорный план.
• Финансовое моделирование: базисные переменные могут представлять доли инвестиций в различные активы в портфеле.

Пример из экономики

Предприятие выпускает два вида продукции \(P_1\) и \(P_2\), используя ресурсы \(R_1\) и \(R_2\). Ограничения: \[ \begin{cases} 2x_1 + 3x_2 \leq 12 \\ 4x_1 + x_2 \leq 8 \\ x_1, x_2 \geq 0 \end{cases} \] После введения слабых переменных \(x_3\) и \(x_4\) получаем систему: \[ \begin{cases} 2x_1 + 3x_2 + x_3 = 12 \\ 4x_1 + x_2 + x_4 = 8 \end{cases} \] Базисное решение с \(x_3\) и \(x_4\) в базисе означает, что ресурсы не используются полностью (слабые переменные положительны). При оптимальном решении базисными становятся \(x_1\) и \(x_2\), а \(x_3 = x_4 = 0\) — ресурсы используются полностью.

Вычислительные аспекты

На практике вычисление базисных переменных требует решения систем линейных уравнений с базисной матрицей. Для этого используются:

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

Проблема вырожденности

Вырожденные базисные решения (когда базисная переменная равна нулю) могут вызвать зацикливание симплекс-метода. Для борьбы с этим применяются:

• Правило Бленда: выбор вводимой и выводимой переменных по минимальному индексу.
• Антициклические правила: например, правило лексикографического выбора.

Связь с другими понятиями

• Свободные переменные: противоположность базисным; в базисном решении равны нулю.
• Базис: совокупность столбцов матрицы, соответствующих базисным переменным.
• Опорный план: допустимое базисное решение в задаче линейного программирования.
• Двойственные переменные: в двойственной задаче базисные переменные соответствуют оценкам ресурсов (теневым ценам).

Примеры в российской науке и образовании

В российских учебных заведениях (МГУ, МФТИ, ВШЭ) понятие базисных переменных изучается в курсах «Линейное программирование», «Методы оптимизации» и «Исследование операций». В учебниках И. Л. Акулича, В. Г. Карманова, Ю. Г. Евтушенко подробно разбираются алгоритмы нахождения базисных решений и их роль в симплекс-методе.

Источники

• Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
• Карманов В. Г. Математическое программирование. — М.: Физматлит, 2004.
• Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982.
• Данциг Дж. Линейное программирование: его применения и обобщения. — М.: Прогресс, 1966.
• Лотов А. В. Введение в экономико-математическое моделирование. — М.: Наука, 1984.