Метод Жордана–Гаусса в задачах линейного программирования
Play ITЗагрузка интерактивного демо…
Для чего в разделе отдельная глава про Жордана-Гаусса
Эта глава связывает линейную алгебру с механикой симплекс-таблицы — вы преобразуете систему так, чтобы базис и опорный план читались явно.
Когда видны единичные столбцы базисных переменных и логика элементарных преобразований строк, симплекс читается как последовательность осмысленных шагов.
Хороший маркер освоения — после чтения вы можете вручную объяснить, как из ограничений получить форму, пригодную для старта симплекса, и почему это эквивалентно исходной системе.
В линейной алгебре упоминается метод Гаусса для 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]. Элементарные преобразования строк не меняют множество решений —
- умножить строку на ненулевое число;
- переставить две строки;
- прибавить к строке другую, умноженную на число.
Пример преобразования 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 —
- Разделить ведущую строку на
aᵢⱼ(на месте ведущего — 1). - Во всех остальных строках обнулить столбец
j(прибавить кратную ведущей строку).
Повторяют по столбцам, пока не получен нужный базис.
Вырожденность — если в столбце после обнуления нет ненулевого кандидата — столбец свободный (неограниченно много решений или нужен другой базис).
Замечания про 0-строки
При жордановских исключениях иногда появляется строка из нулей в коэффициентах —
| Свободный член (RHS) | Интерпретация | Действие |
|---|---|---|
| 0 | уравнение линейно зависимо от остальных | строку можно удалить (дублирует информацию) |
| ≠ 0 | противоречие 0 = b при b ≠ 0 | система несовместна — дальше симплекс бессмыслен |
В симплекс-таблице тот же сигнал — вырожденный pivot (θ = 0) или невозможность выбрать выходящую строку без нарушения знаков. При 0-строке с нулевым RHS явно напишите «зависимость, строку исключаем».
В сокращённых жордановых таблицах (см. симплекс) столбцы, перенесённые в верхнюю часть как базисные, в нижних строках должны обнуляться полностью.
Частичное обнуление — признак ошибки в шаге.
Мини-пример жордановского шага (один столбец)
Система (уже одна переменная в "базисе") —
| 1 2 | 6 | ← хотим единицу в первом столбце
| 2 1 | 10|
- Делим 2-ю строку на 2 —
[1, 1/2 | 5]. - Вычитаем из 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
Контроль правильности преобразований
Перед симплексом проверьте —
- RHS (
b) неотрицательны для классического старта с slack (иначе нужна двухфазная или M-метод). - В столбцах базисных переменных — одна 1 в каждой строке, остальные 0 в этом столбце.
- Базисных переменных ровно столько, сколько строк.
- Числа в строке цели согласованы с выбранным знаком
max/min(дляminчасто переходят кmax(−Z)).
Типичная ошибка — обнулили столбец только снизу, забыв сверху — в симплекс-таблице "единица" в столбце базиса дублируется в другой строке.
Связь с симплекс-итерацией
Одна итерация симплекса — это жордановский шаг по входящему столбцу (новая переменная в базис) с выходом выходящей строки (правило минимального отношения θ).
Поэтому освоение Жордана на бумаге = меньше путаницы в симплекс-таблице.
Численная устойчивость (для кода)
При ручном счёте работают с дробями. В numpy.linalg / солверах используют частичный выбор главного элемента (pivoting), чтобы не делить на почти ноль. Для ЗЛП промышленные пакеты (CPLEX, Gurobi, HiGHS) используют устойчивые реализации симплекса и внутренних точек — см. статью 9.
Краткий чек-лист жордановского приведения
- Записать
[A|b]с именами всех переменных над столбцами. - Выбрать базис (slack или после преобразований).
- Для каждого базисного столбца выполнить полный жордановский шаг.
- Прочитать значения базисных переменных из RHS.
- Подставить в целевую функцию или перенести в строку
Zсимплекс-таблицы.
Типичные вычислительные ловушки
| Ошибка | Почему возникает | Как предотвратить |
|---|---|---|
| Потеря знака при вычитании строк | спешка в арифметике дробей | выписывать промежуточно каждый столбец, особенно RHS |
| Деление не всей строки на pivot | механическая ошибка в одном столбце | после деления проверять: pivot = 1 и строка масштабирована целиком |
| Неполное обнуление pivot-столбца | забыли обработать строку Z или одну из ограничений | делать обнуление по фиксированному списку строк |
| Случайный выбор нулевого pivot | не проверен столбец заранее | выбирать pivot только из ненулевых кандидатов, при необходимости менять строку |
Те же ошибки в программной реализации дают "правдоподобные", но неверные таблицы. Поэтому тесты на маленьких примерах с известным ответом (2x2 и 3x3) обязательны перед запуском на реальных данных.
Дальше — симплекс-метод.
Приведение к канонической форме
Теорема о slack-переменной
При переходе от неравенства ≤ к равенству в канонической форме используют добавочную переменную s ≥ 0:
a₁x₁ + … + aₙxₙ ≤ b ⟺ a₁x₁ + … + aₙxₙ + s = b , s ≥ 0
Каждому допустимому решению (x₁,…,xₙ) исходного неравенства соответствует единственное решение (x₁,…,xₙ, s) расширенной системы с s = b − Σaⱼxⱼ ≥ 0, и наоборот. Поэтому поиск плана по неравенствам ≤ эквивалентен поиску по системе равенств с дополнительными неотрицательными переменными — именно в таком виде строят симплекс-таблицу.
Аналогично для ≥ вводят избыточную переменную (surplus) или умножают строку на −1, чтобы получить привычный вид ≤ с неотрицательным RHS.
Пошаговое приведение смешанной постановки
Исходная задача:
max Z = 5x₁ + 4x₂
x₁ + x₂ ≤ 10
2x₁ + x₂ ≥ 6
x₁, x₂ ≥ 0
| Шаг | Действие | Результат |
|---|---|---|
| 1 | Цель уже max | коэффициенты (5, 4) |
| 2 | ≤ 10 | добавить s₁ ≥ 0: x₁ + x₂ + s₁ = 10 |
| 3 | ≥ 6 | умножить на −1 или ввести surplus u₁: 2x₁ + x₂ − u₁ = 6, u₁ ≥ 0 |
| 4 | Проверить RHS | если RHS отрицательный — нужен M-метод / фаза 1 |
| 5 | Записать таблицу | столбцы x₁, x₂, s₁, u₁, базис из slack/искусственных |
Для солвера linprog (min) часто оставляют как есть — c = [-5,-4], A_ub для ≤, согласованные знаки для ≥ — см. главу 9.