# ЛР-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 проверки контрактов;
- **да** про тени ресурсов, устойчивость оптимума и сценарные управленческие выводы.