О разделе
Раздел «Математическое программирование» — про выбор лучшего плана при линейных правилах: сколько произвести, куда перевезти, как распределить бюджет. Слово «программирование» здесь — план действий в смысле исследования операций, а не обязательно написание кода (хотя статья 9 показывает scipy и OR-Tools).
Рекомендуемый порядок для новичка: 1 (обозначения и постановка) → 2 (картинка на плоскости) → 3–6 (симплекс и двойственность) → по необходимости 7–8. Код — когда понятна постановка на бумаге.
Введение и постановка
Что такое математическое программирование, линейное программирование, стандартные формы записи, примеры из планирования и IT.
Теория и графический метод
Теоретические основы линейного программирования, выпуклость, геометрия допустимой области и пошаговый графический метод на примере.
Метод Жордана–Гаусса
Приведение систем линейных уравнений к ступенчатому и приведённому виду, slack-переменные и связь с симплекс-таблицей.
Симплекс-метод
Общая схема симплекс-метода, построение и заполнение таблицы, сокращённая форма, контроль ошибок, разбор числового примера.
M-метод и искусственный базис
Двухфазный симплекс-метод, метод большого штрафа M, искусственные переменные и вывод из оптимальной таблицы.
Теория двойственности
Постановка двойственной задачи, принцип двойственности, экономический смысл и связь с симплекс-таблицей.
Транспортная задача
Опорный план, метод северо-западного угла, распределительный метод, потенциалы, блокирование клеток, проверка оптимальности.
Динамическое программирование
Общая схема ДП в исследовании операций, этапы, уравнение Беллмана, примеры и отличие от алгоритмического DP.
Решатели в коде
scipy.optimize.linprog, постановка ЗЛП в Python, OR-Tools и когда доверять солверу вместо ручного симплекса.
Итоги
Краткие итоги раздела «Математическое программирование» — ЗЛП, симплекс, транспортная задача, двойственность, ДП Беллмана.
Чек-лист самопроверки
Вопросы для самопроверки по математическому программированию — ЗЛП, симплекс, транспорт, двойственность, ДП.
Математическое программирование — о разделе
Раздел «Математическое программирование» — про выбор лучшего плана при линейных правилах: сколько произвести, куда перевезти, как распределить бюджет.