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

Содержание

ЛР-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) Какие бывают ограничения#

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

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

\[ 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) Что именно изучаем в этой ЛР#

В этой лабораторной мы целенаправленно изучаем четыре вещи:

Геометрический метод для задачи с двумя переменными.
Формы математической записи ЛП (обычная, матричная, канонизированная через добавочные переменные).
Теоретическую связку через Лагранж/ККТ и двойственность.
Программное решение в Python через linprog.

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

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

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

Геометрический метод:

переменные \(x_1, x_2\);
ограничения как прямые/полуплоскости;
оптимум ищем по вершинам допустимой области.

Формы записи задачи:

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

Лагранж/ККТ:

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

Python (scipy.optimize.linprog):

используем c, A_ub, b_ub, bounds, результат res.x, res.fun.

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

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

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

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

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

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

Короткий ответ:

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

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

Показывает «узкие места» по ресурсам:

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

Даёт быстрые оценки «что будет, если увеличить лимит ресурса»:

при малых изменениях прирост оптимума примерно равен теневой цене.

Помогает экономически объяснять решение:

не просто «получилось \(x_1=...,x_2=...\)», а «вот ценность каждого ресурса для бизнеса».

Даёт проверку корректности:

в оптимуме значения прямой и двойственной задач совпадают (сильная двойственность).

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. \]

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

Каждому ограничению прямой задачи соответствует одна двойственная переменная:

если в прямой \(m\) ограничений, то в двойственной будет \(m\) переменных \(y_1,\dots,y_m\).

Каждой переменной прямой задачи соответствует одно ограничение двойственной:

если в прямой \(n\) переменных \(x_1,\dots,x_n\), то в двойственной будет \(n\) ограничений.

Коэффициенты целевой функции двойственной берутся из правых частей прямой:

в прямой были \(b_1,\dots,b_m\);
в двойственной цель: \(\min \sum_{i=1}^m b_i y_i\).

Правые части ограничений двойственной берутся из коэффициентов цели прямой:

в прямой цель: \(\max \sum_{j=1}^n c_j x_j\);
в двойственной в правых частях стоят \(c_1,\dots,c_n\).

Матрица коэффициентов «переворачивается» (транспонируется):

коэффициент \(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{split} \begin{cases} 2x_1 + x_2 \le 10,\\ x_1 + 2x_2 \le 8,\\ x_1, x_2 \ge 0. \end{cases} \end{split}\]

Здесь

\[\begin{split} 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}. \end{split}\]

Как строим двойственную:

из \(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{split} \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} \end{split}\]

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{split} \begin{cases} x_1 + x_2 \le 4,\\ 2x_1 + x_2 \le 5,\\ x_1, x_2 \ge 0. \end{cases} \end{split}\]

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

\[ \min \phi = 4y_1 + 5y_2 \]

\[\begin{split} \begin{cases} y_1 + 2y_2 \ge 3,\\ y_1 + y_2 \ge 2,\\ y_1, y_2 \ge 0. \end{cases} \end{split}\]

Короткая проверка:

для прямой задачи оптимум в точке \(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{split} \begin{cases} 2x_1 + x_2 \le 40,\\ x_1 + x_2 \le 30,\\ x_1, x_2 \ge 0. \end{cases} \end{split}\]

Интерпретация:

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

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

\[ \min \phi = 40y_1 + 30y_2 \]

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

Здесь:

\(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 единицу сырья по цене заметно выше \(3\), это сигнал риска переплаты;
если 1 единица времени/услуги стоит заметно выше \(3\), логика та же.

Проверка конкретной заявки на закупку:

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

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

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

Защита от нецелевого расхода:

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

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{свободны по знаку}. \]

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

Ограничение вида \(\le\):

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

Ограничение вида \(\ge\):

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

Ограничение-равенство:

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

Для максимизации:

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

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

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

Применение к нашей 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. Условия ККТ для ЛП#

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

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

\[ Ax \le b,\quad x \ge 0 \]

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

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

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

\[ \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 \]

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

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

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

\[ \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. \]

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

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

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

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

\[ \nu_1=\nu_2=0. \]

Условия стационарности по \(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. \]

Проверка экономического смысла:

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

Итог: мы связали три уровня одной и той же математики:

геометрический оптимум;
формальные условия ККТ;
управленческая интерпретация через цены ресурсов.

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

После нахождения оптимума обычно спрашивают:

что будет, если изменить прибыль \(c_j\)?
что будет, если увеличить ресурс \(b_i\)?

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

Практическая польза:

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

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

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

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

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

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 требуется отчёт, структура обычно такая:

постановка задачи словами
математическая модель
метод решения
вычислительный результат
экономическая/предметная интерпретация