Метод Жордана–Гаусса в задачах линейного программирования

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

В линейной алгебре упоминается метод Гаусса для Ax = b. В курсе ЗЛП обычно требуют метод Жордана–Гаусса: он доводит матрицу до приведённого ступенчатого вида (в каждом ведущем столбце единственная ненулевая 1). Именно так удобно выразить базисные переменные и стартовать симплекс-таблицу.

Зачем это в ЗЛП, если есть солвер

Симплекс на каждом шаге переписывает систему ограничений так, чтобы часть переменных (базис) выражалась через остальные — ровно жордановские преобразования строк. Если вы один раз вручную приведёте матрицу к виду «в столбце s₁ одна единица, в остальных строках нули», вы уже видите опорный план: s₁ = 8, s₂ = 8 при x₁=x₂=0.

Объект	Роль в таблице
Строка ограничения	одно правило (ресурс, баланс)
Столбец переменной	коэффициенты при этой переменной
Столбец RHS	«свободный член» — запас ресурса в текущем базисе
Ведущий элемент	коэффициент, на который делят строку при жордановском шаге

Чем Жордан отличается от «простого» Гаусса

	Гаусс (прямой ход)	Жордан–Гаусс
Цель	треугольная система, подстановка	диагональ / единичные столбцы базиса
Ведущий элемент	обнуляем ниже	обнуляем выше и ниже
Результат	Ux = c	почти Ix = d для базисных

Для симплекса нужен вид «одна 1 в столбце базисной переменной» — это ровно жордановский шаг.

Расширенная матрица

Систему

a₁₁x₁ + … + a₁ₙxₙ = b₁
…
aₘ₁x₁ + … + aₘₙxₙ = bₘ

записывают как [A | b]. Элементарные преобразования строк не меняют множество решений:

1. умножить строку на ненулевое число;
2. переставить две строки;
3. прибавить к строке другую, умноженную на число.

Пример преобразования 3. Пусть есть строки L1: x + y = 6 и L2: 2x + y = 10. Вычтем L1 из L2: (2x+y)−(x+y) = 10−6 → x = 4. Это и есть «прибавить к строке другую, умноженную на −1». Подставив x=4 в L1, получим y=2. В матрице те же операции делают механически по столбцам.

Жордановский шаг (схема)

Для выбранного ведущего элемента aᵢⱼ ≠ 0 в столбце j:

1. Разделить ведущую строку на aᵢⱼ (на месте ведущего — 1).
2. Во всех остальных строках обнулить столбец j (прибавить кратную ведущей строку).

Повторяют по столбцам, пока не получен нужный базис.

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

Мини-пример жордановского шага (один столбец)

Система (уже одна переменная в «базисе»):

| 1  2 | 6 |   ← хотим единицу в первом столбце
| 2  1 | 10|

1. Делим 2-ю строку на 2: [1, 1/2 | 5].
2. Вычитаем из 1-й: [0, 3/2 | 1] → x₂ = 2/3, обратная подстановка x₁ = 4.

В симплекс-таблице после шага в столбце x₁ будет одна 1 в строке базиса и нули в остальных — по этому столбцу сразу читают x₁ = число в RHS этой строки.

Пример — привести к базису для старта симплекса

Рассмотрим ограничения задачи из графического примера в канонической форме с добавочными переменными s₁, s₂ ≥ 0:

2x₁ +  x₂ + s₁     = 8
 x₁ + 2x₂     + s₂ = 8

Матрица [A | b] (столбцы x₁, x₂, s₁, s₂):

| 2  1  1  0 | 8 |
| 1  2  0  1 | 8 |

Базис {s₁, s₂} — уже единичные столбцы: это тривиальное начальное решение x₁=x₂=0, s₁=8, s₂=8. Жордан здесь не нужен.

Когда Жордан обязателен — полный пример

Задача (фрагмент):

x₁ +  x₂ + s₁ = 6
2x₁ + x₂ + s₂ = 10

Стартовый базис {s₁, s₂} уже единичный — как в задаче станков. А вот система без готового slack во второй строке:

x₁ + x₂ = 6
2x₁ + x₂ = 10

Добавим slack только там, где удобно, или искусственную переменную (статья 5). Для чистого Жордана приведём к виду «базис = часть переменных»:

Из 2x₁ + x₂ = 10 выразим x₁ = (10 − x₂)/2. Подстановка в x₁ + x₂ = 6:

(10 − x₂)/2 + x₂ = 6  →  10 − x₂ + 2x₂ = 12  →  x₂ = 2,  x₁ = 4

Жордан в матрице [x₁ | x₂ | RHS]:

Шаг	Действие	Матрица (смысл)
1	Ведущий в x₁ во 2-й строке (коэф. 2)	делим 2-ю строку на 2 → x₁ + ½x₂ = 5
2	Обнуляем x₁ в 1-й строке	x₂ = 1 после вычитания
3	Обнуляем x₂ в 2-й строке	x₁ = 4

Итог совпадает с подстановкой. В симплекс-таблице те же операции выполняются одновременно над всеми строками, включая −Z.

Slack, surplus и искусственные переменные

Тип ограничения	Что добавляем	Знак в строке таблицы
… ≤ b	slack s ≥ 0	+s, RHS b
… ≥ b	surplus u ≥ 0	−u (или умножить строку на −1)
… = b без готового базиса	искусственная a ≥ 0	см. статью 5

Приведение неравенства к равенству:

a₁x₁ + … + aₙxₙ ≤ b   →   a₁x₁ + … + aₙxₙ + s = b,   s ≥ 0
a₁x₁ + … + aₙxₙ ≥ b   →   a₁x₁ + … + aₙxₙ − u = b,   u ≥ 0

Контроль правильности преобразований

Перед симплексом проверьте:

1. RHS (b) неотрицательны для классического старта с slack (иначе нужна двухфазная или M-метод).
2. В столбцах базисных переменных — одна 1 в каждой строке, остальные 0 в этом столбце.
3. Базисных переменных ровно столько, сколько строк.
4. Числа в строке цели согласованы с выбранным знаком max / min (для min часто переходят к max(−Z)).

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

Связь с симплекс-итерацией

Одна итерация симплекса — это жордановский шаг по входящему столбцу (новая переменная в базис) с выходом выходящей строки (правило минимального отношения θ).

Поэтому освоение Жордана на бумаге = меньше путаницы в симплекс-таблице.

Численная устойчивость (для кода)

Вручную на экзамене работают с дробями. В numpy.linalg / солверах используют частичный выбор главного элемента (pivoting), чтобы не делить на почти ноль. Для ЗЛП промышленные пакеты (CPLEX, Gurobi, HiGHS) используют устойчивые реализации симплекса и внутренних точек — см. статью 9.

Краткий чек-лист жордановского приведения

1. Записать [A|b] с именами всех переменных над столбцами.
2. Выбрать базис (slack или после преобразований).
3. Для каждого базисного столбца выполнить полный жордановский шаг.
4. Прочитать значения базисных переменных из RHS.
5. Подставить в целевую функцию или перенести в строку Z симплекс-таблицы.

Дальше: симплекс-метод.

---