Итоги
Кратко — что стоит унести из раздела «Математическое программирование». Если пункт кажется туманным — откройте указанную главу или оглавление.
Что запомнить
Раздел «Математическое программирование» даёт базу исследования операций, которая стыкуется с инженерной практикой: планирование ресурсов, логистика, распределение нагрузки, постановка задач для солверов.
Главные идеи
Задача оптимизации — выбрать лучшее допустимое решение. В линейном случае цель и ограничения линейны; допустимая область выпукла, а оптимум (если он существует и ограничен) достигается в вершине многогранника.
Графический метод на двух переменных учит читать ограничения и проверять постановку. Жордан–Гаусс готовит систему к симплекс-таблице. Симплекс итеративно улучшает план, переходя по вершинам; контроль таблицы (базис, θ, знаки в строке Z) критичен на экзамене.
Если нет стартового допустимого плана — двухфазный метод или M-метод с искусственными переменными. Двойственная задача парна прямой; оптимальные значения совпадают; двойственные переменные — «цены» ресурсов.
Транспортная задача использует таблицу перевозок: опорный план (северо-западный угол, минимальная стоимость), затем потенциалы и оценки Δ, пересчёт по циклу и блокирование вырожденных клеток.
Динамическое программирование Беллмана — поэтапная оптимизация через уравнение Беллмана и функцию Fₜ(s); это другой угол, чем мемоизация в алгоритмах, хотя рекуррентная идея родственна.
В коде ту же ЗЛП решают через scipy.optimize.linprog и OR-Tools — после ручного разбора вы понимаете, что означают A, b, slack и сообщения солвера.
Углублённые материалы в разделе: полный цикл симплекса с чтением yᵢ* из таблицы; двухфазный старт при равенствах; транспортная 2×2 с потенциалами, циклом и θ; DAG с уравнением Беллмана по слоям; пошаговое приведение смешанных ограничений к канонической форме.
Маршрут для повторения
- Введение и формы
- Графика и теория
- Симплекс + при необходимости M-метод
- Двойственность и транспортная
- Беллман · Код
Смежные материалы: линейная алгебра, алгоритмы.
Куда идти дальше
Полный маршрут — на странице о разделе.
Проверьте себя: Чек-лист самопроверки.
См. также
Другие статьи этого же раздела в боковом меню (как на странице «О разделе»). Что такое математическое программирование, линейное программирование, стандартные формы записи, примеры из планирования и IT. Теоретические основы линейного программирования, выпуклость, геометрия допустимой области и пошаговый графический метод на примере. Приведение систем линейных уравнений к ступенчатому и приведённому виду, slack-переменные и связь с симплекс-таблицей. Общая схема симплекс-метода, построение и заполнение таблицы, сокращённая форма, контроль ошибок, разбор числового примера. Двухфазный симплекс-метод, метод большого штрафа M, искусственные переменные и вывод из оптимальной таблицы. Постановка двойственной задачи, принцип двойственности, экономический смысл и связь с симплекс-таблицей. Опорный план, метод северо-западного угла, распределительный метод, потенциалы, блокирование клеток, проверка оптимальности. Общая схема ДП в исследовании операций, этапы, уравнение Беллмана, примеры и отличие от алгоритмического DP. scipy.optimize.linprog, постановка ЗЛП в Python, OR-Tools и когда доверять солверу вместо ручного симплекса. Вопросы для самопроверки по математическому программированию — ЗЛП, симплекс, транспорт, двойственность, ДП.Введение и постановка
Теория и графический метод
Метод Жордана–Гаусса
Симплекс-метод
M-метод и искусственный базис
Теория двойственности
Транспортная задача
Динамическое программирование
Решатели в коде
Чек-лист самопроверки