Метод Жордана–Гаусса в задачах линейного программирования
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-строки
Жордановские исключения — это полный набор последовательных жордановых шагов, выполняемых для приведения системы линейных уравнений к диагональному виду относительно выбранного набора неизвестных, причём на каждом шаге исключается одна переменная из всех уравнений, кроме одного, где она остается с коэффициентом единица; в симплекс-методе жордановские исключения применяются не ко всей системе, а к текущей симплекс-таблице, и каждый такой цикл полностью пересчитывает все коэффициенты, сохраняя эквивалентность ограничений и целевой функции, но изменяя базис, причём весь процесс симплекс-алгоритма можно рассматривать как последовательность управляемых жордановских исключений, направляемых критерием оптимальности.
0-строки — это строки в симплекс-таблице, все коэффициенты которых, включая свободный член, равны нулю, что свидетельствует о линейной зависимости между ограничениями, причём такие строки могут возникать в процессе преобразований, если исходная система содержала избыточные или противоречивые уравнения; в контексте линейного программирования нулевые строки обычно удаляются как неинформативные, поскольку они не добавляют новых ограничений на переменные, однако если в такой строке в столбце правой части стоит ненулевое значение при нулевых коэффициентах при переменных, это указывает на несовместность системы и отсутствие допустимых решений, что требует немедленной остановки.
При жордановских исключениях иногда появляется строка из нулей в коэффициентах —
| Свободный член (RHS) | Интерпретация | Действие |
|---|---|---|
| 0 | уравнение линейно зависимо от остальных | строку можно удалить (дублирует информацию) |
| ≠ 0 | противоречие 0 = b при b ≠ 0 | система несовместна — дальше симплекс бессмыслен |
Свободный член и RHS — это столбец в симплекс-таблице, обозначаемый как правая часть (Right Hand Side), который содержит значения констант в уравнениях ограничений, причём после жордановых преобразований этот столбец непосредственно даёт текущие значения базисных переменных при условии, что все свободные переменные равны нулю; свободные члены играют ключевую роль в определении допустимости текущего решения, поскольку все они должны быть неотрицательными для допустимого базиса, и именно по минимальному отношению свободных членов к положительным элементам ведущего столбца выбирается ведущая строка, что гарантирует, что после шага все свободные члены останутся неотрицательными.
Линейная зависимость — это свойство набора векторов, которое означает, что хотя бы один из них может быть выражен в виде линейной комбинации остальных, то есть существует нетривиальная комбинация коэффициентов, обращающая сумму в ноль, причём в противном случае векторы называются линейно независимыми; в матричных системах линейная зависимость строк или столбцов указывает на избыточность ограничений или переменных, и ранг матрицы равен максимальному числу линейно независимых строк, причём в симплекс-методе требуется, чтобы матрица ограничений имела полный строчный ранг, иначе базисные решения не будут однозначно определены, а появление линейной зависимости в процессе преобразований часто проявляется в виде нулевых строк или вырожденности.
Pivot — это англоязычный термин, обозначающий ведущий элемент в симплекс-таблице или в методах исключения Гаусса, вокруг которого выполняется преобразование, причём выбор пивота определяет, какая переменная входит в базис, а какая покидает его, и вся процедура пересчёта таблицы часто называется пивотированием; в более общем смысле пивот — это опорный элемент, который должен быть ненулевым, а часто и положительным, чтобы преобразование было допустимым и численно устойчивым, причём стратегии выбора пивота, такие как выбор максимального по модулю элемента или использование частичного пивотирования с перестановкой строк, критически влияют на точность вычислений в методах решения систем линейных уравнений, особенно в плохо обусловленных задачах.
В симплекс-таблице тот же сигнал — вырожденный 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 и искусственные переменные
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.
Типичные вычислительные ловушки
| Ошибка | Почему возникает | Как предотвратить |
|---|---|---|
| Потеря знака при вычитании строк | спешка в арифметике дробей | выписывать промежуточно каждый столбец, особенно 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.