Перейти к основному содержимому

О разделе

Play ITЗагрузка интерактивного демо…

Play ITЗагрузка интерактивного демо…

Длинные листинги (от ~12 строк) вынесены в каталог code.spirzen.ru и подгружаются в статьях через ExternalCodeEmbed — так HTML энциклопедии не раздувается, а код остаётся с подсветкой, вкладками и сериями "шаг 1…N". Короткие фрагменты (псевдокод, пара строк linprog, формулы) по-прежнему прямо в markdown. Диаграммы mermaid и интерактив — на месте или в play.spirzen.ru.

В РАЗРАБОТКЕ
Не обязательно для старта

Раздел для логистики, исследования операций и углублённой математики — не нужен для освоения SQL, HTML или аналитики на Excel/Python. Вернитесь сюда, если учебный план или работа требуют оптимизационных моделей.

Раздел "Математическое программирование" — про выбор лучшего плана при линейных правилах — сколько произвести, куда перевезти, как распределить бюджет. Слово "программирование" здесь означает план действий в смысле исследования операций; реализацию в коде показывает статья 9 (scipy, OR-Tools). Символьная алгебра (решить систему, упростить выражение) — отдельная ветка: SymPy — уравнения и производные; численная оптимизация — здесь и в SciPy.

Формулы в главах сопровождаются псевдокодом на русском — сначала "что выбираем и что ограничивает", потом запись max Z = … и симплекс.

// Мини-пример: пекарня (два вида пирожков)

переменные: x1 = штук с яблоком, x2 = штук с капустой

максимизировать прибыль Z = 3·x1 + 2·x2   // руб. с штуки

при ограничениях:
  мука:   2·x1 + 1·x2 ≤ 100   // грамм муки в запасе
  духовка: x1 + x2 ≤ 80       // штук за смену
  x1 ≥ 0, x2 ≥ 0              // нельзя "минус пирожков"

лучший_план := перебрать_допустимые (x1, x2), взять максимальный Z
// на практике это делает солвер, не ручной перебор

Перед стартом раздела​

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

Если вы когда-либо сталкивались с задачами вида "ресурсов мало, вариантов много, нужно выбрать лучший план", то это и есть тот самый класс задач, который закрывает математическое программирование. Производство, логистика, бюджетирование, нагрузка сервисов, SLA, приоритизация работ — всё это естественно укладывается в модели данного раздела.

Читать полезно в режиме "медленно, но с проверкой" — после каждого блока пробуйте переформулировать идею своими словами и проверять 1 мини-пример руками. Такой темп выглядит медленнее, но в реальности он резко ускоряет освоение следующих разделов, где уже используется готовый инструментарий оптимизации.

Рекомендуемый порядок для новичка — Математическое программирование — введение и постановка задач (обозначения и постановка) → Выпуклые множества, свойства ЗЛП и графический метод (картинка на плоскости) → Метод Жордана–Гаусса в задачах линейного программирования–Двойственность в линейном программировании (симплекс и двойственность) → по необходимости Транспортная задача–Динамическое программирование и уравнение Беллмана. Код — когда понятна постановка на бумаге.

Что вы получите после раздела​

  • Умение переводить прикладную задачу в формальную модель — переменные, цель, ограничения.
  • Понимание границ применимости линейной модели.
  • Знание случаев, когда нужны целочисленные или нелинейные подходы.
  • Навык проверять решение двумя способами — вручную (графика/симплекс) и в коде (солвер).
  • Базу для тем уровня middle — чувствительность, MIP, network flow, робастные модели.

Практический режим прохождения​

Чтобы материал действительно закрепился, полезно после каждой главы делать три шага —

  1. Выписать 5-10 терминов своими словами.
  2. Решить один мини-пример руками (даже если потом будет код).
  3. Проверить тот же пример в linprog или OR-Tools.

Такой цикл резко уменьшает разрыв между "понимаю теорию" и "могу применить в задаче проекта".

Интерактивный старт​

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

Как работать с демо —

  • сначала оставьте базовые значения и проверьте, что лучший план совпадает с логикой из примера;
  • затем измените прибыль c1/c2 и посмотрите, какой продукт начинает "тянуть" оптимум сильнее;
  • после этого уменьшите лимиты b1/b2, чтобы увидеть, как появляются узкие места.

Play ITЗагрузка интерактивного демо…

После упражнения важно вынести две мысли —

  1. Оптимум определяется целью и набором активных ограничений.
  2. Даже небольшое изменение коэффициентов может сдвинуть лучший план заметнее, чем ожидается "на глаз".

С этим контекстом переходите к карточкам раздела ниже — читайте формулы с рабочей интуицией.

Откуда вырос курс​

Линейное программирование оформилось в XX веке как язык планирования производства и перевозок. В введении к главе 1 разбирают постановки; здесь — короткая хронология для ориентира.

ПериодВклад
1930-еА.Н. Толстой — оптимальный план перевозок; Л.В. Канторович — методы линейного планирования в СССР
1931Б. Эгервари — задача назначения ("венгерский" метод)
1947Дж. Данциг — симплекс-метод
1950-еР. Беллман — динамическое программирование
1975Нобелевская премия по экономике Л.В. Канторовичу (совместно с Т. Купмансом)

Структура раздела следует классическому курсу ЗЛП — от постановки и симплекса до транспортной задачи и уравнения Беллмана. Практику в коде даёт глава 9.

Теги:
Последнее обновление
Содержание