Математическое программирование — итоги
Кратко — что стоит унести из раздела "Математическое программирование". Если пункт кажется туманным — откройте указанную главу или оглавление.
FAQ — Часто задаваемые вопросы
Типичные затыки при первых задачах ЗЛП, симплекса и транспортной модели. Здесь — как диагностировать ошибку и куда вернуться в главах; пункты для самопроверки — в чек-листе.
Вопрос. Говорят «математическое программирование», а я жду урок Python — это один предмет?
Ответ. Здесь "программирование" = план действий (исследование операций): сколько произвести, куда везти. Код — в главе 9, после постановки на бумаге. Подробнее здесь — о разделе.
Вопрос. Из текста "максимизировать прибыль при нехватке муки" не получается запись max Z = … — с чего начать?
Ответ. Выделите переменные решения, коэффициенты в цели (руб./шт.), затем каждое ограничение ресурса в виде ≤ или =. Подробнее здесь — постановка и формы.
Вопрос. На графике область пустая, хотя "по смыслу" пирожки можно печь.
Ответ. Проверьте знаки (≥ vs ≤), единицы (кг vs г) и несовместные пары ограничений. Подробнее здесь — графика и теория.
Вопрос. Линии ограничений нарисовал, а лучшая точка "уезжает" в бесконечность.
Ответ. Цель не ограничена сверху в допустимой области (часто при параллельных лучах). Нужна новая граница или пересмотр постановки. Подробнее здесь — графика — неограниченность.
Вопрос. Забыл перевести max в min перед scipy.optimize.linprog — ответ "оптимален", но цифры странные.
Ответ. linprog минимизирует; для max Z подставьте отрицательные коэффициенты цели или эквивалентную форму. Всегда проверяйте подстановкой. Подробнее здесь — код.
Вопрос. Ограничение "не больше 10" записал как ≥ 10 — симплекс сошёл, но ответ нелепый.
Ответ. Перепутаны направления неравенств — типичная ошибка новичка. Перепишите в каноническом виде и сверьте с графиком. Подробнее здесь — постановка.
Вопрос. В жордановой таблице строка [0,0,…|5] — что делать дальше?
Ответ. Система несовместна (0 = 5). Если RHS = 0 — зависимая строка, её удаляют. Подробнее здесь — Жордан–Гаусс.
Вопрос. Симплекс-таблица "поехала" — в базисе два slack вместо одного.
Ответ. Нарушен базис: после pivot должна быть ровно одна единица в столбце базисной переменной. Пересоберите таблицу с нуля на маленьком примере. Подробнее здесь — симплекс.
Вопрос. В строке Z все коэффициенты "плохие", но выбираю входящий столбец наугад — оптимум не находится.
Ответ. Следуйте правилу курса для входящего/выходящего и минимального θ; при равенстве θ возможна вырожденность. Подробнее здесь — симплекс.
Вопрос. θ получилось отрицательным — можно игнорировать?
Ответ. Отрицательный θ сигналит об ошибке в знаках или выборе выходящей строки. Остановитесь и сверьте с эталонным шагом. Подробнее здесь — симплекс.
Вопрос. Нет стартового допустимого плана — сразу запускать M-метод или двухфазный?
Ответ. Оба дают старт; в курсе важно понять зачем искусственные переменные и как их "выкинуть" из базиса. Подробнее здесь — M-метод, симплекс.
Вопрос. В конце M-метода искусственная переменная осталась в базисе с ненулевым значением.
Ответ. Исходная задача несовместна (или ошибка постановки). Перепроверьте равенства =. Подробнее здесь — M-метод.
Вопрос. Двойственные переменные получились отрицательными — это всегда ошибка?
Ответ. Знак зависит от соглашения записи двойственной задачи; важнее интерпретация "тени цены" при малых изменениях b. Подробнее здесь — двойственность.
Вопрос. linprog вернул success: False, status "infeasible", на графике точка есть.
Ответ. Часто расходятся матрицы A, b (лишнее ограничение, неверный slack) или знак неравенства в коде. Подставьте найденную графически точку в каждое ограничение в Python. Подробнее здесь — код.
Вопрос. После изменения спроса правую часть b уменьшили — как быстро пересчитать план?
Ответ. Когда строка Z уже оптимальна, а допустимость нарушена — двойственный симплекс. Подробнее здесь — двойственность.
Вопрос. Сумма запасов 55, сумма потребностей 50 — куда девать разницу?
Ответ. Введите фиктивного потребителя с недостающим объёмом и нулевым тарифом (остаток на складе). Подробнее здесь — транспортная задача.
Вопрос. Опорный план северо-западного угла дал огромную стоимость — это нормально?
Ответ. Северо-западный угол быстрый, но грубый; для лучшего старта возьмите минимальную стоимость или метод Фогеля. Подробнее здесь — транспортная.
Вопрос. В опорном плане занято меньше m+n−1 клеток — потенциалы не считаются.
Ответ. Вырождение — добавьте ε-перевозку или блокируйте клетку по правилу курса. Подробнее здесь — транспортная.
Вопрос. Все Δ для пустых клеток положительные, а в разборе говорят «ещё не оптимально».
Ответ. Проверьте знак критерия оптимальности и баланс потенциалов uᵢ, vⱼ после вырождения. Подробнее здесь — транспортная.
Вопрос. Нужно запретить маршрут (1,2) — поставил c₁₂ = 0, а план всё равно туда везёт.
Ответ. Ноль может быть легальным тарифом; для запрета используйте большой штраф M. Подробнее здесь — транспортная — запреты.
Вопрос. Задача "сколько серверов включить по часам" — это всё ещё ЗЛП?
Ответ. Если решения только 0/1 — нужна целочисленная (MIP) постановка; обычная ЗЛП может дробить ответ. Подробнее здесь — о разделе — границы, код OR-Tools.
Вопрос. Цель квадратичная (штраф за отклонение) — симплекс из курса подойдёт?
Ответ. Классический симплекс — для линейной цели; квадратичные задачи решают другими методами/солверами. Подробнее здесь — графика и теория.
Вопрос. Рюкзак 0/1 в таблице ДП заполнил, а как восстановить набор предметов?
Ответ. Идите обратным ходом по таблице F, сравнивая с предыдущим слоем. Подробнее здесь — Беллман.
Вопрос. ДП Беллмана в курсе и "мемоизация рюкзака" в алгоритмах — это одно и то же?
Ответ. Идея рекуррентная, но в ИО акцент на этапах, состоянии и уравнении Беллмана для управления ресурсами. Подробнее здесь — Беллман, алгоритмы.
Вопрос. На интерактивной демо площадки поменял c₁ — оптимум прыгнул с одной вершины в другую. Это баг?
Ответ. При линейной цели оптимум часто сидит в вершине; смена коэффициентов сдвигает линию уровня до следующей вершины. Подробнее здесь — о разделе — playground.
Вопрос. Решил задачу в Excel "подбором параметра" — зачем тогда симплекс?
Ответ. Подбор на 2–3 переменных не объясняет структуру и не масштабируется; симплекс и солверы дают гарантированную схему для больших n. Подробнее здесь — симплекс, код.
Вопрос. На собеседовании просят "сформулировать ЗЛП для распределения нагрузки API" — хватит знать только linprog?
Ответ. Нужны переменные, цель, ограничения SLA словами; код без модели не убедит. Подробнее здесь — постановка, практический минимум на этой странице.
Вопрос. После каникулы всё забыли — как повторить раздел за один вечер?
Ответ. Один пример графика 2×2, один шаг симплекса, одна итерация потенциалов, один рюкзак в таблице — по маршруту повторения ниже. Подробнее здесь — чек-лист самопроверки.
Вопрос. Что такое линейное программирование простыми словами?
Ответ. Выбор лучшего плана при линейной цели и линейных ограничениях (ресурсы, спрос, бюджет). Подробнее здесь — постановка и формы, о разделе.
Вопрос. Чем математическое программирование отличается от программирования на Python?
Ответ. Здесь "программирование" = план оптимизации в ИО; Python в главе 9 лишь вызывает солвер после модели.
Вопрос. Как решить задачу линейного программирования графически?
Ответ. При двух переменных строят полуплоскости ограничений, находят вершины многоугольника и сравнивают значение цели. Подробнее здесь — графика и теория.
Вопрос. Симплекс-метод — как работает кратко?
Ответ. Старт в вершине, затем шаги: входящий столбец → выходящая строка → pivot, пока строка Z не покажет оптимум. Подробнее здесь — симплекс.
Вопрос. Что такое slack-переменная в ЗЛП?
Ответ. Дополнительная переменная переводит ≤ в равенство и даёт стартовый базис для симплекса. Подробнее здесь — постановка.
Вопрос. Задача линейного программирования в Python — как решить через scipy?
Ответ. scipy.optimize.linprog с матрицами A, b, вектором c; цель в форме минимизации. Подробнее здесь — код — linprog.
Вопрос. Двойственная задача ЗЛП — зачем она нужна?
Ответ. Даёт оценки дефицита ресурсов (тени цен) и альтернативные алгоритмы (двойственный симплекс). Подробнее здесь — двойственность.
Вопрос. Транспортная задача — как решить методом потенциалов?
Ответ. Опорный план → потенциалы u, v → оценки пустых клеток → сдвиг по циклу, пока все Δ не станут неотрицательными. Подробнее здесь — транспортная.
Вопрос. Метод северо-западного угла — что это?
Ответ. Быстрый способ построить начальный опорный план перевозок; качество часто хуже, чем у метода минимальной стоимости или Фогеля. Подробнее здесь — транспортная.
Вопрос. Метод Фогеля в транспортной задаче — когда применять?
Ответ. Когда нужен хороший стартовый план с меньшим числом итераций потенциалов, чем у северо-западного угла. Подробнее здесь — транспортная.
Вопрос. Задача о рюкзаке 0/1 — это динамическое программирование?
Ответ. Да, классический пример таблицы F по весу и предметам с уравнением Беллмана. Подробнее здесь — Беллман.
Вопрос. Уравнение Беллмана — что записывают в задаче с этапами?
Ответ. Рекуррентную связь лучшей ценности состояния с предыдущими этапами и допустимыми переходами. Подробнее здесь — динамическое программирование.
Вопрос. Исследование операций (ИО) — что входит в базовый курс?
Ответ. ЗЛП, транспорт, сети, часто ДП и постановки под солверы; этот раздел даёт ядро ЗЛП и транспорта. Подробнее здесь — о разделе.
Вопрос. Оптимизация производства — пример задачи ЗЛП?
Ответ. Переменные — объёмы выпуска; цель — прибыль; ограничения — сырьё, мощности, спрос. Подробнее здесь — постановка, playground на intro.
Вопрос. Логистика — как свести перевозки к транспортной задаче?
Ответ. Запасы складов, потребности точек, матрица тарифов; при дисбалансе — фиктивный узел. Подробнее здесь — транспортная.
Вопрос. M-метод и двухфазный симплекс — в чём разница?
Ответ. Оба ищут допустимый старт через искусственные переменные; отличаются записью штрафа в цели и числом фаз таблицы. Подробнее здесь — M-метод, симплекс.
Вопрос. ЗЛП с целыми переменными (0/1) — решается симплексом?
Ответ. Симплекс даёт релаксацию; для целых решений нужен MIP (например OR-Tools). Подробнее здесь — код.
Вопрос. Нелинейная оптимизация — когда ЗЛП не подходит?
Ответ. При квадратичных штрафах, произведениях переменных, логистических кривых спроса. Подробнее здесь — графика и теория.
Вопрос. Почему оптимум ЗЛП лежит в вершине многоугольника?
Ответ. Линейная цель улучшается вдоль градиента до границы выпуклой области; максимум достигается в крайней точке (вершине). Подробнее здесь — графика.
Вопрос. Жордан–Гаусс в ЗЛП — зачем перед симплексом?
Ответ. Приводит систему к виду с единичным базисом и выявляет несовместность или зависимость строк. Подробнее здесь — глава 3.
Вопрос. OR-Tools для линейного программирования — когда вместо scipy?
Ответ. При больших моделях, целых переменных и сетевых структурах. Подробнее здесь — код.
Вопрос. Распределение нагрузки на серверы — можно оформить как ЗЛП?
Ответ. Да: переменные — доля трафика; цель — задержка или стоимость; ограничения — ёмкость и SLA. Подробнее здесь — постановка, код.
Вопрос. С чего учить линейное программирование в вузе самостоятельно?
Ответ. Порядок раздела: 1 → 2 → 4 → 6 → 7 → 8 → 9, с одним числовым примером на каждую главу. Подробнее здесь — маршрут на intro, чек-лист.
Терминология раздела
Сводный словарь по математическому программированию. Подробные разъяснения — в соответствующих главах.
Общие термины
| Термин | Значение |
|---|---|
| План | допустимое решение |
| Базис | набор переменных, через которые выражают остальные в текущей таблице |
| Опорный план | допустимое решение в вершине (для транспортной — заполненная таблица с m+n−1 клетками) |
| Двойственная задача | парная ЗЛП; двойственные переменные — «тени цен» ресурсов |
| Симплекс-таблица | компактная запись эквивалентной системы для итераций |
| Slack (добавочная) | недоиспользованный запас ресурса в неравенстве ≤ |
| Surplus (избыточная) | перевыполнение нормы в ограничении ≥ |
| RHS | правая часть ограничения — число b в … ≤ b |
Коэффициент цели cⱼ | на сколько изменится Z, если увеличить xⱼ на 1 при том же базисе |
Симплекс-таблица
| Термин | Объяснение |
|---|---|
| Базис | m переменных (по числу ограничений), выраженных через остальные; в столбцах базиса — единичная матрица |
| Небазисные | переменные, временно считаемые нулевыми в текущем плане |
| Опорный план | значения базисных переменных из RHS при нулевых небазисных |
| Входящая | небазисная переменная, которую увеличивают, чтобы улучшить Z |
| Выходящая | базисная, которую выводят по правилу θ, чтобы сохранить ≥ 0 |
| Приведённая стоимость | коэффициент в строке Z при небазисной переменной |
Как читать итоги, чтобы они реально работали
Эта страница собирает главы в компактную карту повторения. Её лучше использовать в трёх режимах — перед повтором (чтобы увидеть структуру), после прохождения (чтобы проверить, что осталось в голове), и перед практикой/собеседованием (чтобы быстро восстановить логику раздела).
Если какой-то пункт ниже читается как "знакомо, но не объясню", это точный индикатор, куда вернуться. Такой подход намного эффективнее, чем перечитывать всё подряд без приоритизации.
Что запомнить
Раздел "Математическое программирование" даёт базу исследования операций, которая стыкуется с инженерной практикой — планирование ресурсов, логистика, распределение нагрузки, постановка задач для солверов.
Главные идеи
Задача оптимизации — выбрать лучшее допустимое решение. В линейном случае цель и ограничения линейны; допустимая область выпукла, а оптимум (если он существует и ограничен) достигается в вершине многогранника.
Графический метод на двух переменных учит читать ограничения и проверять постановку. Жордан–Гаусс готовит систему к симплекс-таблице. Симплекс итеративно улучшает план; контроль таблицы (базис, θ, знаки в строке Z) критичен при ручном счёте.
Если нет стартового допустимого плана — двухфазный метод или M-метод с искусственными переменными. Двойственная задача парна прямой; оптимальные значения совпадают; двойственные переменные — "цены" ресурсов. Двойственный симплекс восстанавливает допустимость после изменения b, когда строка цели уже оптимальна.
Транспортная задача — опорный план (северо-западный угол, минимальная стоимость, метод Фогеля), балансировка фиктивным узлом, потенциалы, сдвиг λ по единственному циклу, блокирование; в продвинутых постановках — запреты маршрутов и лимиты ≤ d.
Жордан–Гаусс — диагностика 0-строк (зависимость vs несовместность). Искусственный базис и M-метод — два способа стартовать симплекс при равенствах и ≥.
Динамическое программирование Беллмана — поэтапная оптимизация через уравнение Беллмана, таблицу Fₜ(s) и обратный/прямой проход; целочисленный рюкзак — частный случай. Это другой угол, чем мемоизация в алгоритмах, хотя рекуррентная идея родственна.
В коде ту же ЗЛП решают через scipy.optimize.linprog и OR-Tools — после ручного разбора вы понимаете, что означают A, b, slack и сообщения солвера.
Углублённые материалы в разделе — полный цикл симплекса с чтением yᵢ* из таблицы; двухфазный старт и три исхода M-метода; транспортная 2×2 с потенциалами, циклом и θ; запреты маршрутов через тариф M; DAG с уравнением Беллмана; 0/1-рюкзак как ДП; пошаговое приведение смешанных ограничений к канонической форме.
Маршрут для повторения
- Введение и формы
- Графика и теория
- Симплекс + при необходимости M-метод
- Двойственность и транспортная
- Беллман · Код
Смежные материалы — линейная алгебра, алгоритмы.
Практический минимум "умею применять"
После прохождения раздела стоит уметь сделать без подсказок —
- Сформулировать ЗЛП из текстового описания задачи.
- Решить небольшой пример графически и симплексом.
- Выписать двойственную задачу и интерпретировать
y*. - Пройти одну транспортную задачу с потенциалами.
- Записать и решить простую рекурсию Беллмана.
- Проверить решение в
linprogи объяснить статус солвера.
Если все шесть пунктов выполняются уверенно, раздел усвоен на рабочем уровне.
Куда идти дальше
Полный маршрут — на странице о разделе.
Проверьте себя — Чек-лист самопроверки.