ЛР-03: Двойственность и анализ чувствительности

ЛР-03: Двойственность и анализ чувствительности#

1) Зачем нужна именно эта лабораторная#

После ЛР-01 мы уже умеем:

  • собирать базовую задачу линейного программирования;

  • понимать смысл переменных, ограничений и целевой функции;

  • проверять решение через scipy.optimize.linprog;

  • на базовом уровне читать двойственные оценки и связь с ККТ.

После ЛР-02 мы умеем:

  • переводить логистическую ситуацию в специальную транспортную модель;

  • работать с балансом спроса и предложения;

  • строить A_eq для потоковой постановки.

ЛР-03 не повторяет эти шаги. Здесь главный вопрос другой:

какие ресурсы реально ограничивают оптимум и как изменится лучший результат, если немного изменить параметры модели?

Именно поэтому ЛР-03 сделана с фокусом на анализ чувствительности (sensitivity-first), а не как ещё один длинный пошаговый разбор ручного вывода двойственной (dual) задачи.

2) Прикладной контекст: публичный бюджет#

Предположим, что регион распределяет ресурсы между несколькими программами:

  1. мобильные медицинские бригады;

  2. школьное питание;

  3. цифровые образовательные наборы;

  4. зимние центры поддержки населения.

Каждая программа:

  • даёт некоторый общественный эффект;

  • потребляет бюджет;

  • требует трудозатрат персонала;

  • использует операционную ёмкость.

Нужно выбрать масштаб запуска программ так, чтобы суммарный общественный эффект был как можно выше.

3) Прямая задача#

Пусть:

  • \(x_j\) — доля запуска программы \(j\);

  • \(0 \le x_j \le 1\);

  • \(c_j\) — эффект от полной реализации программы \(j\);

  • \(a_{ij}\) — потребление ресурса \(i\) программой \(j\);

  • \(b_i\) — доступный запас ресурса \(i\).

Тогда модель имеет вид:

\[ \max E = \sum_{j=1}^{4} c_j x_j \]

при ограничениях:

\[ \sum_{j=1}^{4} a_{ij} x_j \le b_i, \quad i=1,2,3, \]
\[ 0 \le x_j \le 1, \quad j=1,2,3,4. \]

В этой лабораторной ресурсы такие:

  1. бюджет;

  2. трудозатраты персонала;

  3. операционная ёмкость.

Содержательно эта модель означает: мы можем запускать каждую программу полностью или частично, но не выше 100 процентов плана.

4) Что такое активное ограничение (binding) и запас ресурса (slack)#

Для ограничения вида

\[ a_i^T x \le b_i \]

величина

\[ \text{slack}_i = b_i - a_i^T x^* \]

показывает, сколько ресурса осталось в оптимуме.

По-человечески: мы сначала строим лучший план, а потом просто смотрим, сколько ресурса ещё лежит «на полке» и не было использовано.

Если запас ресурса (slack) равен 0#

Ограничение активно или binding.

Смысл: ресурс исчерпан, и именно он реально сдерживает дальнейший рост целевой функции.

Если запас ресурса (slack) больше 0#

Ограничение неактивно.

Смысл: часть ресурса остаётся в резерве, поэтому небольшое увеличение этого лимита в текущей точке ничего не меняет.

5) Краткая двойственная модель#

Так как у нас есть не только ресурсные ограничения, но и верхние границы

\[ x_j \le 1, \]

в полной двойственной (dual) модели появляются два типа двойственных переменных:

  • \(y_i \ge 0\) — теневая цена ресурса \(i\);

  • \(z_j \ge 0\) — теневая цена ограничения на максимальный масштаб программы \(j\).

Тогда двойственная задача к полной модели имеет вид:

\[ \min \Phi = \sum_{i=1}^{3} b_i y_i + \sum_{j=1}^{4} z_j \]

при условиях:

\[ A^T y + z \ge c, \]
\[ y \ge 0,\quad z \ge 0. \]

Как это читать по-человечески#

  • \(y_i\) показывает, насколько вырастет оптимальный общественный эффект при малом увеличении ресурса \(i\) на одну условную единицу;

  • \(z_j\) показывает, насколько ценным было бы ослабить верхний предел для программы \(j\).

В этой ЛР основное внимание уделяется именно ресурсным теневым ценам \(y_i\).

6) Сильная двойственность#

Если прямая и двойственная задачи корректно поставлены и имеют оптимум, то:

\[ E^* = \Phi^*. \]

Практический смысл:

  • можно решить прямую задачу;

  • отдельно решить двойственную (dual) модель;

  • убедиться, что оптимальные значения совпадают численно.

Это важная проверка того, что постановка собрана правильно.

7) Анализ чувствительности по правым частям#

Пусть ресурсный лимит \(b_i\) увеличили на маленькую величину \(\Delta b_i\).

Тогда при неизменной структуре оптимума:

\[ \Delta E^* \approx y_i \cdot \Delta b_i. \]

Это и есть главный операционный смысл теневой цены:

  • большая теневая цена означает дефицитный и дорогой ресурс;

  • нулевая теневая цена означает, что в текущем оптимуме ресурс не лимитирует результат.

В лабораторной мы не ограничиваемся формулой, а сравниваем:

  1. прогноз по теневой цене (shadow price);

  2. фактический результат после повторного решения задачи.

8) Анализ чувствительности по коэффициентам цели#

Если меняются коэффициенты \(c_j\), то меняется ценность самих программ.

Это важно в двух типичных ситуациях:

  1. новая оценка общественного эффекта программы;

  2. смена приоритетов заказчика или региона.

Здесь возможны два разных эффекта:

  • значение целевой функции меняется, а структура оптимального плана остаётся прежней;

  • при достаточно сильном изменении коэффициентов меняется сам состав оптимального плана.

Именно этот переход мы отдельно проверяем в основном ноутбуке.

9) Что должно быть в отчёте#

  1. Таблица программ, ресурсов и общественных эффектов.

  2. Прямая постановка задачи с пояснением переменных.

  3. Матрицы и векторы для linprog: c, A_ub, b_ub, bounds.

  4. Решение прямой задачи и итоговый план масштабов программ.

  5. Разделение ограничений на активные (binding) и с запасом ресурса (slack).

  6. Краткая запись двойственной (dual) модели.

  7. Численная проверка сильной двойственности.

  8. Таблица ресурсных теневых цен.

  9. Эксперименты по изменениям правых частей b с прогнозом и фактом.

  10. Один-два эксперимента по изменениям коэффициентов цели c.

  11. Вывод о том, какой ресурс сейчас самый дефицитный и где дополнительная единица ресурса даёт наибольший эффект.

10) Типичные ошибки#

  1. Считать, что любое ограничение автоматически влияет на оптимум. Это не так: сначала нужно посмотреть на запас ресурса (slack).

  2. Путать dual-переменные ресурсов с dual-переменными верхних границ x_j \le 1.

  3. Делать вывод по теневой цене, не проверив знак и экономический смысл.

  4. Сравнивать разные сценарии по b и c, но забывать повторно решать модель.

  5. Повторять из ЛР-01 длинный ручной вывод dual-задачи вместо анализа чувствительности.

  6. Смешивать ЛР-03 с транспортной логикой поставщик-потребитель из ЛР-02.

11) Граница темы этой лабораторной#

ЛР-03 специально разведена с другими материалами курса:

  • не про геометрические вершины и канонизацию как основную тему;

  • не про транспортную матрицу и баланс потоков;

  • не про аудит госзакупок, fair-price ranking и pipeline проверки контрактов;

  • да про тени ресурсов, устойчивость оптимума и сценарные управленческие выводы.