МАТ-0129метод Данцига 1947пошаговое решениеревизия 2026-05-08

Симплекс-метод онлайн (лаборатория)

Пошаговое решение задач линейного программирования с симплекс-таблицами на каждой итерации. До 5 переменных и произвольного числа ограничений.

⏱ ~30 сек · max c·x при A·x ≤ b · 5 переменных

Решение · МАТ-0129|метод Данцига

calcal.ru / simpleks-metod-onlajn-laboratoriya

Целевая функция (max)

F = c₁·x₁ + c₂·x₂ + ...

Переменных:

F =·x1+·x2

Ограничения (3)

·x1+·x2≤

ОПТИМАЛЬНОЕ РЕШЕНИЕ

F_max = 36.00

x₁ = 2.00 · x₂ = 6.00 ·

Симплекс-таблицы (3 шагов)

Шаг 0 · Начальная таблица

1.00	0.00	1.00	0.00	0.00	4.00
0.00	2.00	0.00	1.00	0.00	12.00
3.00	2.00	0.00	0.00	1.00	18.00
-3.00	-5.00	0.00	0.00	0.00	0.00

Шаг 1 · Шаг 1: введена x2, выведена x2

1.00	0.00	1.00	0.00	0.00	4.00
0.00	1.00	0.00	0.50	0.00	6.00
3.00	0.00	0.00	-1.00	1.00	6.00
-3.00	0.00	0.00	2.50	0.00	30.00

Шаг 2 · Шаг 2: введена x1, выведена x1

0.00	0.00	1.00	0.33	-0.33	2.00
0.00	1.00	0.00	0.50	0.00	6.00
1.00	0.00	0.00	-0.33	0.33	2.00
0.00	0.00	0.00	1.50	1.00	36.00

Симплекс-метод Дж. Данцига (1947) — алгоритм решения задач линейного программирования. Принцип: переход от вершины к вершине допустимого многогранника по правилу максимального улучшения. Канонический вид: max c·x при Ax ≤ b, x ≥ 0. Через слабые переменные приводится к равенствам, затем итерации.

Загрузка…

max c·x

целевая функция

A·x ≤ b

линейные огранич.

x ≥ 0

неотрицательность

Данциг 1947

автор метода

Теория ЛП

Линейное программирование (LP) — оптимизация линейной функции при линейных ограничениях. Допустимое множество — выпуклый многогранник в n-мерном пространстве. Теорема: если оптимум существует, он достигается в одной из вершин многогранника. Симплекс-метод систематически перебирает вершины, переходя по рёбрам в направлении улучшения.

Алгоритм

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

Симплекс-метод — пожалуй, наиболее экономически значимый алгоритм всех времён. От военного снабжения 1940-х до глобальных цепочек поставок XXI века он остаётся основой решения миллионов задач оптимизации ежедневно.— George Dantzig, Linear Programming and Extensions, 1963

Где применяется

Транспортные задачи и логистика.
Производственное планирование.
Финансовая оптимизация (диверсификация портфеля).
Сети и распределение ресурсов.
Расписания и составление меню.

ИСТОЧНИКИ

Linear Programming and Extensions. Dantzig G.B.. Princeton University Press. 1963.
Introduction to Linear Optimization. Bertsimas D., Tsitsiklis J.. Athena Scientific. 1997.
Линейное программирование. Юдин Д.Б., Гольштейн Е.Г.. Наука. 1969 (классика).
CS 261 / Stanford Optimization. Stephen Boyd. web.stanford.edu. 2024.

Лаборатория для образовательных целей. Для производственных задач (тысячи переменных) — профессиональные солверы CPLEX, Gurobi, GLPK или коммерческие модули SAP Production Optimizer.

РАЗДЕЛ 04 · НЮАНСЫ

Что нужно понимать

01

Канонический вид

Любая ЗЛП приводится к: max c·x при A·x ≤ b, x ≥ 0. Слабые переменные превращают неравенства в равенства. Двойственная задача даётся для min.

02

Симплекс-таблица

Каждая строка — ограничение, каждый столбец — переменная (с слабыми). Последняя строка — целевая. Базисные переменные имеют единичные столбцы.

03

Правило Данцига

Вход в базис — переменная с самым отрицательным коэффициентом в целевой строке. Выход — переменная с минимальным положительным отношением b/a в выбранном столбце.

04

Сложность

В худшем случае O(2ⁿ), на практике — почти линейно от размерности. Для больших задач (тысячи переменных) — Internal Point Method (Karmarkar 1984), полиномиальный.

РАЗДЕЛ 05 · ПРАКТИКА

Три шага к решению

01ПОСТАНОВКА

Целевая и ограничения

Запишите функцию F = c₁x₁ + c₂x₂ + ... в стандартной форме. Все ограничения преобразуйте к ≤ (умножьте на −1 при необходимости). Условие x ≥ 0 обязательно.

02РЕШЕНИЕ

Итерации до стопа

Простой алгоритм останавливается, когда в целевой строке нет отрицательных коэффициентов. Это значит, что текущее базисное решение оптимально.

03ПРОВЕРКА

Графически 2D

При двух переменных решение можно проверить графически: построить ОДЗ как пересечение полуплоскостей, найти вершины, подставить в F, выбрать максимум.

ЧАСТЫЕ ВОПРОСЫ

Часто задаваемые вопросы

Симплекс-метод — алгоритм решения задач линейного программирования (ЗЛП), разработанный Джорджем Данцигом в 1947 году. Идея: оптимум линейной функции на многограннике (выпуклой области, ограниченной линейными неравенствами) всегда находится в одной из вершин. Алгоритм переходит от вершины к вершине, выбирая каждый раз направление максимального улучшения целевой функции, пока не достигнет оптимальной вершины. На практике сходится за O(2m+n) шагов в худшем случае, но на типовых задачах — почти линейно от числа переменных.

Стандартный вид, к которому приводится любая задача ЛП: maximize c·x subject to A·x ≤ b, x ≥ 0. Преобразования: 1) Цель min → max через смену знака. 2) Неравенство ≥ → ≤ через умножение на −1. 3) Равенство ≡ → пара ≤ и ≥. 4) Свободная переменная x → x⁺ − x⁻ (обе ≥ 0). 5) Введение слабых переменных для превращения ≤ в равенства: a·x + s = b, s ≥ 0. После этого таблица составляется из коэффициентов A, единичной матрицы при слабых, столбца b и строки −c в качестве целевой.

Каждая итерация — один обмен переменных в базисе. Выбираем входящую переменную: с самым отрицательным коэффициентом в целевой строке. Выбираем выходящую: с минимальным положительным отношением b/a в выбранном столбце (правило Блэнда против циклов). Делим выбранную строку на ведущий элемент (a_pivot = 1). Вычитаем кратные этой строки из других, чтобы в столбце все стали 0 кроме ведущей единицы. Повторяем, пока в целевой строке остаются отрицательные коэффициенты. На выходе — оптимум: значения базисных x в столбце b, F в правом нижнем углу.

Два случая. 1) Несовместные ограничения (нет точек в ОДЗ): обнаруживается в начальной фазе через искусственный базис, где остаётся ненулевая искусственная переменная. Решение: проверьте, что ограничения совместимы, нет противоречий типа x ≤ 5 и x ≥ 7. 2) Целевая функция неограничена сверху (для max): на итерации не находится конечного выходящего: все коэффициенты в выбранном столбце ≤ 0. Это значит, что значение можно увеличивать бесконечно. Решение: проверьте задачу — обычно недостаёт ограничения сверху на ресурс или производство.

Огромный спектр задач оптимизации с линейными ограничениями: 1) Транспортная задача — оптимальная развозка из M складов в N магазинов. 2) Задача о рационе — минимальная стоимость рациона с заданными питательными веществами (классика nutrition science). 3) Производственное планирование — какие продукты и сколько выпускать при ограниченных ресурсах. 4) Финансовая оптимизация — диверсификация портфеля Марковица в линейной упрощённой постановке. 5) Logistics — выбор маршрутов, складов. 6) Сети — распределение трафика, балансировка нагрузки. Все современные ERP-системы (SAP, 1С, Oracle) внутри используют LP-солверы для оптимизации цепи поставок.

Был ли этот калькулятор полезен?

ревизия · 8 мая 2026

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ

Инструмент справочный — не заменяет эксперта

Только для информационных целей. Все расчёты, результаты и данные, предоставляемые инструментом, носят исключительно ознакомительный и справочный характер. Они не являются профессиональной консультацией — медицинской, юридической, финансовой, инженерной или иной.

Точность результатов. Калькулятор основан на общепринятых формулах и методиках, однако фактические результаты могут отличаться в зависимости от индивидуальных условий, исходных данных и применяемых стандартов. Мы не гарантируем полноту, точность или актуальность приведённых расчётов.

Профессиональные решения — медицинские, финансовые, инженерные — должны приниматься только после консультации с квалифицированным специалистом. Не используйте автоматический расчёт как единственное основание для важных решений.

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

СМЕЖНЫЕ ИНСТРУМЕНТЫ

Симплекс-метод онлайн (лаборатория)

Теория ЛП

Алгоритм

Где применяется

Что нужно понимать

Три шага к решению

Целевая и ограничения

Итерации до стопа

Графически 2D

Часто задаваемые вопросы

Лиана Арифметова

Инструмент справочный — не заменяет эксперта

Похожие калькуляторы

Калькулятор оптимизации: симплекс, рюкзак, генетика

Калькулятор тригонометрии

Калькулятор дробей (смешанные и неправильные)

Калькулятор НОД и НОК

Калькулятор матриц

Калькулятор комбинаторики

Калькулятор комплексных чисел

Калькулятор производных и интегралов

Калькулятор чисел Фибоначчи

Калькулятор золотого сечения

Калькулятор сумм рядов

Калькулятор Монте-Карло симуляции: оценка рисков

Калькулятор процентов

Калькулятор научной нотации

Калькулятор интерполяции (Лагранж, сплайн)