Симплекс-метод онлайн
Решение задач линейного программирования симплекс-методом с пошаговым выводом. Канонический вид, симплекс-таблицы, искусственный базис, двойственная задача.
Симплекс-метод: алгоритм пошагово
Симплекс-метод — фундаментальный алгоритм решения задач линейного программирования (ЗЛП). Разработан американским математиком Джорджем Данцигом в 1947 году в рамках военных исследований ВВС США. До сих пор остаётся стандартом для большинства практических задач оптимизации.
Постановка задачи ЗЛП
Стандартная форма задачи линейного программирования:
при ограничениях:
a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
...
x₁, x₂, ..., xₙ ≥ 0
Алгоритм симплекс-метода
- Приведение к каноническому виду. Все ограничения преобразуются в равенства добавлением балансных переменных. Например, x₁ + x₂ ≤ 10 становится x₁ + x₂ + s₁ = 10, где s₁ ≥ 0.
- Построение начальной симплекс-таблицы. В качестве начального базиса берутся балансные переменные. Записываются коэффициенты целевой функции, ограничений, правые части.
- Поиск разрешающего столбца. Это столбец с наибольшей по модулю отрицательной оценкой в строке целевой функции (для задачи на максимум).
- Поиск разрешающей строки. Минимум симплекс-отношений b_i/a_ik по положительным элементам разрешающего столбца.
- Преобразование Жордана-Гаусса. Разрешающий элемент делает равным 1, всё в столбце — нулями.
- Проверка оптимальности. Если все оценки в строке целевой функции ≥ 0 — найден оптимум. Иначе — переход к шагу 3.
Метод искусственного базиса (M-метод)
Если в задаче есть ограничения «≥» или «=», стандартный симплекс не имеет очевидного начального базиса. Решение — ввести искусственные переменные с очень большим штрафом M (десятки тысяч). Алгоритм автоматически выводит их из базиса, оставляя реальное решение.
Типичные задачи
- Задача о ресурсах — максимизация прибыли при ограниченных ресурсах (сырьё, время).
- Транспортная задача — минимизация затрат на перевозку (специальный алгоритм быстрее).
- Задача о смесях — минимизация стоимости смеси при заданных требованиях по составу (диета, корм).
- Задача о раскрое — минимизация отходов при раскрое материалов.
- Задача о назначениях — оптимальное распределение сотрудников по задачам.
Применение в задачах ЕГЭ и вузов
Симплекс-метод изучается в курсах «Исследование операций», «Математические методы в экономике», «Линейное программирование». Входит в программу подготовки экономистов, математиков, IT-специалистов. Современные SaaS-системы (1С, SAP, Oracle) используют симплекс для автоматического планирования.
Связанные инструменты
Был ли этот калькулятор полезен?
Инструмент справочный — не заменяет эксперта
Только для информационных целей. Все расчёты, результаты и данные, предоставляемые инструментом, носят исключительно ознакомительный и справочный характер. Они не являются профессиональной консультацией — медицинской, юридической, финансовой, инженерной или иной.
Точность результатов. Калькулятор основан на общепринятых формулах и методиках, однако фактические результаты могут отличаться в зависимости от индивидуальных условий, исходных данных и применяемых стандартов. Мы не гарантируем полноту, точность или актуальность приведённых расчётов.
Профессиональные решения — медицинские, финансовые, инженерные — должны приниматься только после консультации с квалифицированным специалистом. Не используйте автоматический расчёт как единственное основание для важных решений.
Ограничение ответственности. Авторы и разработчики сервиса не несут ответственности за прямой или косвенный ущерб, возникший из-за использования данных расчётов. Пользователь принимает на себя всю ответственность за интерпретацию результатов.