# ЛР-01: Линейное программирование для начинающих

## 1) Что это вообще такое

Линейное программирование (ЛП) это способ **найти лучшее решение** (максимум прибыли, минимум затрат и т.д.) при ограниченных ресурсах.

Есть три обязательные части:
- **переменные** (что выбираем)
- **целевая функция** (что хотим максимизировать или минимизировать)
- **ограничения** (чего нельзя нарушать)

Ключевое слово: **линейное**. Это значит, что все формулы состоят из сумм вида:

$$
a_1x_1 + a_2x_2 + \dots + a_nx_n
$$

без квадратов, произведений переменных и т.п.

---

## 2) Интуитивный пример

Вы производите 2 вида продукции:
- изделие A: прибыль 40
- изделие B: прибыль 30

Ресурсы:
- сырье: на A нужно 2, на B нужно 1, всего 100
- время: на A нужно 1, на B нужно 1, всего 80

Переменные:
- $x_1$ = сколько сделать A
- $x_2$ = сколько сделать B

Модель:

$$
\max z = 40x_1 + 30x_2
$$

при

$$
2x_1 + x_2 \le 100
$$

$$
x_1 + x_2 \le 80
$$

$$
x_1 \ge 0, \quad x_2 \ge 0
$$

Смысл:
- максимизируем прибыль
- не выходим за лимиты ресурсов
- отрицательное производство запрещено

---

## 3) Общая математическая постановка

### Векторная форма

$$
\max\; c^{T} x
$$

при

$$
Ax \le b,
$$

$$
x \ge 0.
$$

Где:
- $x \in \mathbb{R}^n$ — вектор переменных
- $c \in \mathbb{R}^n$ — коэффициенты целевой функции
- $A \in \mathbb{R}^{m \times n}$ — матрица ограничений
- $b \in \mathbb{R}^m$ — доступные ресурсы

Если по-человечески, то `A` — это большая таблица норм расхода, `b` — это запас ресурсов, а `c` — это ценность каждой переменной в целевой функции.

### Покомпонентно

$$
\max \sum_{j=1}^{n} c_j x_j
$$

при

$$
\sum_{j=1}^{n} a_{ij}x_j \le b_i, \quad i=1,\dots,m
$$

$$
x_j \ge 0, \quad j=1,\dots,n
$$

---

## 4) Какие бывают ограничения

1. $\le$ (ресурс не превысить)
2. $\ge$ (минимум обеспечить)
3. $=$ (точный баланс)

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

$$
x = x^+ - x^-, \quad x^+,x^- \ge 0
$$

---

## 5) Стандартная и каноническая формы

Часто для алгоритмов задачу переводят в специальный вид.

### Стандартная форма (частый вариант)

Для max-задачи:

$$
\max c^{T}x, \quad Ax \le b, \quad x \ge 0
$$

### Каноническая форма (для аккуратной записи ограничений)

Неравенства $\le$ превращают в равенства добавлением **добавочных переменных** (slack, то есть запаса ресурса):

$$
2x_1+x_2+s_1=100,
$$

$$
x_1+x_2+s_2=80,
$$

$$
s_1,s_2 \ge 0
$$

$s_1$ и $s_2$ показывают остаток ресурса.
Если ребёнку объяснить совсем просто, то это "сколько ресурса осталось в коробке после выполнения плана".

---

## 6) Геометрический смысл (очень важно)

- Каждое линейное ограничение задаёт полуплоскость (в 2D) или полупространство (в nD).
- Пересечение всех ограничений даёт **допустимую область**.
- Целевая функция это семейство параллельных гиперплоскостей.
- Оптимум достигается в одной из **вершин** допустимого многогранника.

Почему вершина? Это фундаментальный факт ЛП: если оптимум существует, то одна из вершин допустимой области оптимальна.

---

## 7) Что именно изучаем в этой ЛР

В этой лабораторной мы целенаправленно изучаем четыре вещи:
1. Геометрический метод для задачи с двумя переменными.
2. Формы математической записи ЛП (обычная, матричная, канонизированная через добавочные переменные).
3. Теоретическую связку через Лагранж/ККТ и двойственность.
4. Программное решение в Python через `linprog`.

Симплекс-таблицы, пивот-правила и пошаговый табличный алгоритм здесь **не** рассматриваются.

---

## 8) Как не перепутать обозначения (методически важно)

Чтобы не смешивать подходы, держите простое правило:

1. Геометрический метод:
- переменные $x_1, x_2$;
- ограничения как прямые/полуплоскости;
- оптимум ищем по вершинам допустимой области.

2. Формы записи задачи:
- векторно-матрично: $c, A, b$;
- после канонизации: добавочные переменные $s_1, s_2, \dots$.

3. Лагранж/ККТ:
- множители Лагранжа для ограничений обозначаем $y$ (и $s$ для $x \ge 0$ в выбранной записи);
- условия ККТ: допустимость + стационарность + комплементарная нежёсткость.

4. Python (`scipy.optimize.linprog`):
- используем `c`, `A_ub`, `b_ub`, `bounds`, результат `res.x`, `res.fun`.

Это полезно помнить так: теория говорит "что означает задача", а `linprog` помогает честно проверить наши вычисления на компьютере.

Обозначения симплекс-таблиц (например, «входящая/выходящая переменная», пивот и т.п.) в этой ЛР не используем.

---

## 9) Когда задача «плохая»

1. **Недопустима**: ограничений слишком много/жёсткие, нет ни одной точки.
2. **Неограничена**: цель можно улучшать бесконечно.
3. **Вырождение**: в вершине одновременно активны «лишние» ограничения, из-за чего анализ чувствителен к малым изменениям.
4. **Множественные оптимумы**: целая грань оптимальных решений.

---

## 10) Двойственная задача: зачем она нужна на практике

Очень частый вопрос: «Мы уже нашли оптимальный план выпуска. Зачем ещё одна (двойственная) задача?»

Короткий ответ:
- прямая задача отвечает на вопрос **«сколько производить?»**;
- двойственная задача отвечает на вопрос **«сколько стоит дополнительная единица каждого ресурса?»**.

### 10.1. Практическая польза двойственной задачи

1. Показывает «узкие места» по ресурсам:
- если теневая цена ресурса положительна, ресурс дефицитный и реально ограничивает прибыль;
- если теневая цена ноль, запас этого ресурса сейчас не ограничивает оптимум.

2. Даёт быстрые оценки «что будет, если увеличить лимит ресурса»:
- при малых изменениях прирост оптимума примерно равен теневой цене.

3. Помогает экономически объяснять решение:
- не просто «получилось $x_1=...,x_2=...$», а «вот ценность каждого ресурса для бизнеса».

4. Даёт проверку корректности:
- в оптимуме значения прямой и двойственной задач совпадают (сильная двойственность).

### 10.2. Формально

Прямая задача:

$$
\max c^{T} x, \quad Ax \le b,\; x \ge 0
$$

Двойственная задача:

$$
\min b^{T} y, \quad A^{T} y\ge c,\; y \ge 0
$$

Здесь $y_i$ — теневая цена ресурса $i$.

### 10.3. Как получить двойственную задачу пошагово (откуда берутся коэффициенты)

Ниже правило именно для формы, которую мы используем в ЛР:

$$
\max c^{T} x,\quad Ax \le b,\quad x \ge 0.
$$

Шаги преобразования:

1. Каждому ограничению прямой задачи соответствует одна двойственная переменная:
- если в прямой $m$ ограничений, то в двойственной будет $m$ переменных $y_1,\dots,y_m$.

2. Каждой переменной прямой задачи соответствует одно ограничение двойственной:
- если в прямой $n$ переменных $x_1,\dots,x_n$, то в двойственной будет $n$ ограничений.

3. Коэффициенты целевой функции двойственной берутся из правых частей прямой:
- в прямой были $b_1,\dots,b_m$;
- в двойственной цель: $\min \sum_{i=1}^m b_i y_i$.

4. Правые части ограничений двойственной берутся из коэффициентов цели прямой:
- в прямой цель: $\max \sum_{j=1}^n c_j x_j$;
- в двойственной в правых частях стоят $c_1,\dots,c_n$.

5. Матрица коэффициентов «переворачивается» (транспонируется):
- коэффициент $a_{ij}$ из ограничения $i$ при переменной $x_j$ в прямой
  становится коэффициентом при $y_i$ в ограничении $j$ двойственной.

Короткая шпаргалка знаков для нашей формы:
- $\max \rightarrow \min$;
- $\le \rightarrow \ge$;
- $x \ge 0 \rightarrow y \ge 0$.

#### Пример «по элементам» на числах

Пусть прямая задача:

$$
\max z = 5x_1 + 4x_2
$$

$$
\begin{cases}
2x_1 + x_2 \le 10,\\
x_1 + 2x_2 \le 8,\\
x_1, x_2 \ge 0.
\end{cases}
$$

Здесь

$$
A=\begin{pmatrix}2&1\\1&2\end{pmatrix},\quad
b=\begin{pmatrix}10\\8\end{pmatrix},\quad
c=\begin{pmatrix}5\\4\end{pmatrix}.
$$

Как строим двойственную:
- из $b=(10,8)$ получаем цель $\min \phi = 10y_1 + 8y_2$;
- 1-е ограничение двойственной строится из 1-го столбца $A$: $(2,1)$ и правой части $c_1=5$:
  $2y_1 + y_2 \ge 5$;
- 2-е ограничение двойственной строится из 2-го столбца $A$: $(1,2)$ и правой части $c_2=4$:
  $y_1 + 2y_2 \ge 4$;
- знаки: $y_1, y_2 \ge 0$.

Итоговая двойственная:

$$
\begin{cases}
\min \phi = 10y_1 + 8y_2,\\
2y_1 + y_2 \ge 5,\\
y_1 + 2y_2 \ge 4,\\
y_1, y_2 \ge 0.
\end{cases}
$$

### 10.4. Как «читать» двойственные ограничения

Ограничение вида

$$
\big(A^{T} y\big)_j \ge c_j
$$

означает: «оценённая стоимость ресурсов, нужных на 1 единицу продукта $j$, не должна быть меньше прибыли $c_j$ от этой единицы».

Это важный экономический фильтр согласованности цен ресурсов и ценности продукции.

### 10.5. Реалистичный мини-сюжет (управленческий взгляд)

Используем ту же пару прямой и двойственной задач из раздела 10.3.
Чтобы не дублировать одинаковые формулы, здесь фокусируемся только на интерпретации чисел.

Интерпретация:
- $y_1$ — «внутренняя цена» 1 единицы ресурса 1;
- $y_2$ — «внутренняя цена» 1 единицы ресурса 2;
- минимум $\phi$ — минимальная оценка стоимости всего запаса ресурсов при таких ценах.

Для этой же модели в оптимуме получается $y_1=2,\;y_2=1$, и

$$
\phi_{\min}=10\cdot2+8\cdot1=28.
$$

Это ровно совпадает с максимальной прибылью прямой задачи:

$$
z_{\max}=28.
$$

Управленческий смысл:
- если можно купить ещё 1 единицу ресурса 1 «дешевле чем 2», это выгодно;
- если 1 единица ресурса 2 стоит «дешевле чем 1», это тоже выгодно;
- если дороже, расширение ресурса обычно не даёт экономического смысла в текущей точке.

### 10.6. Ещё одна простая числовая пара: обычная (прямая) и двойственная

Обычная (прямая) задача:

$$
\max z = 3x_1 + 2x_2
$$

$$
\begin{cases}
x_1 + x_2 \le 4,\\
2x_1 + x_2 \le 5,\\
x_1, x_2 \ge 0.
\end{cases}
$$

Двойственная к ней:

$$
\min \phi = 4y_1 + 5y_2
$$

$$
\begin{cases}
y_1 + 2y_2 \ge 3,\\
y_1 + y_2 \ge 2,\\
y_1, y_2 \ge 0.
\end{cases}
$$

Короткая проверка:
- для прямой задачи оптимум в точке $x_1=1,\;x_2=3$, поэтому $z_{\max}=3\cdot1+2\cdot3=9$;
- для двойственной задачи оптимум в точке $y_1=1,\;y_2=1$, поэтому $\phi_{\min}=4\cdot1+5\cdot1=9$.

Получилось $z_{\max}=\phi_{\min}=9$, то есть сильная двойственность подтверждается на конкретных числах.

### 10.7. Производственный пример для контроля затрат и защиты от завышения цен

Сценарий: предприятие выпускает два изделия, а отдел закупок хочет контролировать,
чтобы деньги на ресурсы расходовались целево и без завышений.

Прямая (производственная) задача:

$$
\max z = 9x_1 + 6x_2
$$

$$
\begin{cases}
2x_1 + x_2 \le 40,\\
x_1 + x_2 \le 30,\\
x_1, x_2 \ge 0.
\end{cases}
$$

Интерпретация:
- $x_1, x_2$ — объёмы выпуска;
- 1-е ограничение — расход сырья (лимит 40 единиц);
- 2-е ограничение — загрузка времени/персонала (лимит 30 единиц).

Двойственная (контур внутреннего ценового контроля):

$$
\min \phi = 40y_1 + 30y_2
$$

$$
\begin{cases}
2y_1 + y_2 \ge 9,\\
y_1 + y_2 \ge 6,\\
y_1, y_2 \ge 0.
\end{cases}
$$

Здесь:
- $y_1$ — внутренняя предельная цена 1 единицы сырья;
- $y_2$ — внутренняя предельная цена 1 единицы времени/персонала.

Для этой пары задач оптимум:

$$
x_1^{*}=10,\quad x_2^{*}=20,\quad z_{\max}=210
$$

$$
y_1^{*}=3,\quad y_2^{*}=3,\quad \phi^{*}=210.
$$

Что это даёт для финансового контроля:

1. Защита от завышения цен на ресурс:
- если поставщик предлагает 1 единицу сырья по цене заметно выше $3$, это сигнал риска переплаты;
- если 1 единица времени/услуги стоит заметно выше $3$, логика та же.

2. Проверка конкретной заявки на закупку:
- пусть планируют докупить $\Delta r_1$ единиц сырья и $\Delta r_2$ единиц времени;
- экономически обоснованный верхний предел затрат:

$$
C_{\max}=y_1^{*}\,\Delta r_1 + y_2^{*}\,\Delta r_2.
$$

- если счёт $C_{\text{invoice}}$ существенно выше $C_{\max}$ (с учётом допустимого порога), заявку нужно эскалировать на пересмотр условий.

3. Защита от нецелевого расхода:
- если статья затрат не связана ни с одним ресурсом модели (не попадает в ограничения), у неё нет обоснованной теневой цены в этой задаче;
- такие расходы должны проходить отдельное согласование, а не закрываться «производственным» бюджетом ЛП-модели.

---

## 11) Сильная двойственность и комплементарная нежёсткость

### Сильная двойственность
Если у прямой и двойственной задач есть оптимум, то

$$
\max c^{T}x = \min b^{T}y
$$

### Комплементарная нежёсткость
Для оптимальных $x^{*}, y^{*}$:

$$
y_i^{*}\big(b_i-(Ax^{*})_i\big)=0,\quad i=1,\dots,m
$$

$$
x_j^{*}\big(\big(A^{T}y^{*}\big)_j-c_j\big)=0,\quad j=1,\dots,n
$$

Смысл:
- если ограничение «с запасом», его двойственная цена 0
- если переменная > 0, её reduced cost = 0

---

## 12) Метод функции Лагранжа и ККТ (когда применимо)

### 12.1. В чём идея метода Лагранжа

Метод Лагранжа добавляет ограничения в целевую функцию через множители.
Так мы ищем не просто «лучшее значение функции», а точку, где одновременно выполнены и цель, и ограничения.

Для задач только с равенствами используют классическую функцию Лагранжа.
Для задач с неравенствами (как в ЛП) обычно используют условия Каруша-Куна-Таккера (ККТ), это расширение метода Лагранжа.

### 12.2. Общие правила составления лагранжиана (и применение к нашей max-задаче)

#### Общий вид (для задачи минимизации)

Пусть задача записана так:

$$
\min f(x)
$$

$$
g_i(x) \le 0,\quad i=1,\dots,m,\qquad
h_k(x)=0,\quad k=1,\dots,p.
$$

Тогда лагранжиан:

$$
\mathcal{L}(x,\lambda,\mu)=f(x)+\sum_{i=1}^{m}\lambda_i g_i(x)+\sum_{k=1}^{p}\mu_k h_k(x)
$$

$$
\lambda_i \ge 0,\quad \mu_k\ \text{свободны по знаку}.
$$

#### Правило знаков (чтобы не перепутать)

1. Ограничение вида $\le$:
- в минимизации удобно писать как $g(x) \le 0$ и добавлять $+\lambda g(x)$, где $\lambda \ge 0$.

2. Ограничение вида $\ge$:
- можно либо умножить на $-1$ и свести к $\le$;
- либо оставить как есть и добавить с противоположным знаком (эквивалентно).

3. Ограничение-равенство:
- множитель добавляется линейно, без ограничения знака.

4. Для максимизации:
- либо перейти к эквивалентной минимизации $-f(x)$;
- либо использовать ту же логику напрямую, но строго согласовать знак множителя с формой ограничения.
- практично: если в задаче max ограничение записано как $q(x) \ge 0$, используйте $+\lambda q(x)$ при $\lambda \ge 0$;
  если как $q(x) \le 0$, используйте $-\lambda q(x)$ при $\lambda \ge 0$.

#### Чек-лист составления лагранжиана

1. Привести ограничения к единому удобному виду.
2. Назначить по одному множителю на каждое ограничение.
3. Проверить знаки множителей в соответствии с типом ограничения.
4. Записать сумму: «цель + множители * ограничения».
5. Проверить размерности и физический смысл каждого слагаемого.

#### Применение к нашей max-постановке ЛП

Прямая задача:

$$
\max c^{T} x, \quad Ax \le b,\quad x \ge 0
$$

Выбираем форму ограничений:
- для ресурса: $b-Ax \ge 0$;
- для неотрицательности: $x \ge 0$.

Для удобства возьмём обозначения:
- $\lambda$ — множители для ресурсных ограничений;
- $\nu$ — множители для ограничений неотрицательности переменных.

Тогда лагранжиан можно записать как:

$$
\mathcal{L}(x,\lambda,\nu)=c^{T} x + \lambda^{T}(b-Ax) + \nu^{T} x,
$$

$$
\lambda \ge 0,\quad \nu \ge 0.
$$

Здесь:
- $\lambda$ — множители для ограничений $Ax \le b$ (в форме $b-Ax \ge 0$);
- $\nu$ — множители для ограничений $x \ge 0$.

### 12.3. Условия ККТ для ЛП

В точке оптимума (при выполнении условий регулярности, а для ЛП это стандартный случай) выполняются:

1. Прямая допустимость:

$$
Ax \le b,\quad x \ge 0
$$

2. Двойственная допустимость:

$$
\lambda \ge 0,\quad \nu \ge 0,\quad A^{T} \lambda - \nu = c
$$

3. Комплементарная нежёсткость:

$$
\lambda_i\,(b_i-(Ax)_i)=0,\quad i=1,\dots,m
$$

$$
\nu_j\,x_j=0,\quad j=1,\dots,n
$$

Почему это важно методически:
- если ограничение по ресурсу не активно (есть запас), соответствующий множитель равен 0;
- если переменная положительна, её «штраф» $\nu_j$ равен 0.

### 12.4. Связь с двойственной задачей

Из условия

$$
A^{T} \lambda - \nu = c,\quad \nu \ge 0
$$

следует

$$
A^{T} \lambda \ge c.
$$

Это ровно ограничение двойственной задачи.
Поэтому метод Лагранжа/ККТ естественно приводит к двойственности в ЛП.

### 12.5. Связанный пример: геометрия -> ККТ -> экономический вывод

Возьмём ту же задачу из ЛР-01 (реальная интерпретация: два продукта и два ограниченных ресурса):

$$
\max z = 5x_1 + 4x_2
$$

$$
2x_1+x_2 \le 10,\quad x_1+2x_2 \le 8,\quad x_1, x_2 \ge 0
$$

1. Из геометрического решения уже известно:

$$
x_1^{*}=4,\quad x_2^{*}=2,\quad z_{\max}=28.
$$

2. Запишем лагранжиан:

$$
\mathcal{L}=5x_1+4x_2+\lambda_1(10-2x_1-x_2)+\lambda_2(8-x_1-2x_2)+\nu_1x_1+\nu_2x_2.
$$

3. Проверим активность ограничений в оптимуме:

$$
10-(2\cdot4+2)=0,\quad 8-(4+2\cdot2)=0.
$$

Оба ресурсных ограничения активны (запаса нет).

4. Так как $x_1^{*}>0,\;x_2^{*}>0$, по комплементарной нежёсткости:

$$
\nu_1=\nu_2=0.
$$

5. Условия стационарности по $x_1, x_2$:

$$
5-2\lambda_1-\lambda_2=0,\quad 4-\lambda_1-2\lambda_2=0
$$

Отсюда:

$$
\lambda_1=2,\quad \lambda_2=1.
$$

6. Проверка экономического смысла:
- ресурс 1 ценнее ресурса 2 (2 против 1), значит именно первый ресурс чаще становится главным ограничителем роста прибыли;
- эти значения совпадают с интерпретацией двойственной задачи и с сильной двойственностью.
- если в разделе про двойственную задачу используется обозначение $y$, то здесь просто $y \equiv \lambda$.

Итог: мы связали три уровня одной и той же математики:
1. геометрический оптимум;
2. формальные условия ККТ;
3. управленческая интерпретация через цены ресурсов.

---

## 13) Чувствительность решения

После нахождения оптимума обычно спрашивают:
- что будет, если изменить прибыль $c_j$?
- что будет, если увеличить ресурс $b_i$?

Анализ чувствительности показывает диапазоны, где не меняется активный набор ограничений и структура оптимума.

Практическая польза:
- быстро оценивать «а если» без полного пересчёта
- понимать, какой ресурс самый ценный

---

## 14) Как решать ЛП на практике

1. Ввести переменные (понятный физический смысл).
2. Записать цель в линейной форме.
3. Записать все ограничения (единицы измерения проверять обязательно).
4. Добавить условия знака.
5. Проверить модель на здравый смысл (например, нулевое решение должно быть интерпретируемым).
6. Решить (геометрически для 2D, через Лагранж/ККТ для теоретического анализа, либо solver в Python).
7. Интерпретировать результат на языке предметной области.

---

## 15) Типичные ошибки начинающих

1. Перепутан $\max$ и $\min$.
2. Перепутаны знаки $\le$ и $\ge$.
3. Не добавлены ограничения неотрицательности.
4. Смешаны единицы измерения (часы, минуты, кг).
5. Нелинейная зависимость записана как линейная (или наоборот).
6. «Решили математику», но не проверили реалистичность решения.

---

## 16) Мини-шпаргалка формул

### Прямая (max)

$$
\max c^{T}x,\; Ax \le b,\; x \ge 0
$$

### Двойственная (min)

$$
\min b^{T}y,\; A^{T}y \ge c,\; y \ge 0
$$

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

$$
c^{T}x^{*} = b^{T}y^{*}
$$

### Комплементарная нежёсткость

$$
y_i^{*}(b_i-a_i^{T}x^{*})=0
$$

$$
x_j^{*}\big(\big(A^{T}y^{*}\big)_j-c_j\big)=0
$$

---

## 17) Что важно вынести для ЛР-01

- ЛП это не «сложная магия», а аккуратная запись реальной задачи в линейных формулах.
- Самый критичный этап это **правильно построить модель**, а не нажать кнопку «solve».
- Оптимум ищется среди вершин допустимой области.
- Двойственные переменные дают экономический смысл: ценность ресурсов.

Если в ЛР-01 требуется отчёт, структура обычно такая:
1. постановка задачи словами
2. математическая модель
3. метод решения
4. вычислительный результат
5. экономическая/предметная интерпретация