Линейное программирование

План лекции

1. Введение в линейное программирование

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

3. Геометрическая интерпретация

4. Симплекс-метод

5. Транспортная задача и метод потенциалов

6. Двойственность в линейном программировании

7. Программные средства решения задач ЛП

1. Введение в линейное программирование

Линейное программирование (ЛП) — это метод нахождения экстремума (максимума или минимума) линейной функции нескольких переменных при линейных ограничениях.

Область применения:

• Планирование производства и распределение ресурсов
• Транспортные задачи и логистика
• Финансовое планирование и портфельный анализ
• Управление персоналом и календарное планирование

Пример

Завод выпускает два продукта $x_1$ и $x_2$. Нужно максимизировать прибыль при ограниченных ресурсах (сырьё, рабочее время).

         Прибыль
Продукт 1:  3 у.е./шт
Продукт 2:  5 у.е./шт

         Сырьё    Время
Продукт 1:  2 кг    1 ч
Продукт 2:  1 кг    2 ч

Ресурсы:   100 кг   80 ч

2. Математическая модель ЗЛП

Общая форма задачи линейного программирования:

Найти $\vec{x} = (x_1, x_2, \ldots, x_n)$, при котором

$$Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \to \max (\min)$$

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

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m \\ x_j \geq 0, \quad j = 1, \ldots, n \end{cases}$$

Компоненты модели

Математическая модель

$$Z = 3x_1 + 5x_2 \to \max$$

$$\begin{cases} 2x_1 + x_2 \leq 100 \quad \text{(сырьё)} \\ x_1 + 2x_2 \leq 80 \quad \text{(время)} \\ x_1 \geq 0, \; x_2 \geq 0 \end{cases}$$

Формы записи ЗЛП

Переход к канонической форме

Добавление балансовых (добавочных) переменных:

$$2x_1 + x_2 \leq 100 \quad \Rightarrow \quad 2x_1 + x_2 + x_3 = 100, \quad x_3 \geq 0$$

Замена переменных:

$$x_j \leq 0 \;\Rightarrow\; x_j = x_j^+ - x_j^-, \quad x_j^+ \geq 0, \; x_j^- \geq 0$$

Умножение на $-1$:

$$2x_1 + x_2 \geq 10 \quad \Rightarrow \quad -2x_1 - x_2 \leq -10$$

3. Геометрическая интерпретация

Для задачи с двумя переменными ($n = 2$):

• Каждое линейное ограничение — полуплоскость
• Область допустимых решений (ОДР) — пересечение полуплоскостей (выпуклый многоугольник)
• Целевая функция — семейство параллельных прямых (линий уровня)
• Оптимальное решение — в вершине ОДР (или на ребре)

Геометрическое решение примера

$$Z = 3x_1 + 5x_2 \to \max, \quad \begin{cases} 2x_1 + x_2 \leq 100 \\ x_1 + 2x_2 \leq 80 \\ x_1, x_2 \geq 0 \end{cases}$$

Вершины ОДР: $(0,0)$, $(50,0)$, $(0,40)$, $(40,20)$

Вычисление $Z$ в вершинах

Оптимальный план: $x_1^* = 40$, $x_2^* = 40$, $Z^* = 220$

Основные теоремы ЛП

Особые случаи

Ограничения геометрического метода

• Геометрический метод работает только для $n = 2$ (иногда $n = 3$)
• При $n > 2$ — невозможно визуализировать ОДР
• Необходим аналитический метод для произвольного числа переменных
• Такой метод — симплекс-метод (Джордж Данциг, 1947)

4. Симплекс-метод

Симплекс-метод — универсальный аналитический метод решения ЗЛП, основанный на последовательном улучшении опорного плана.

Идея:

1. Найти начальную вершину (опорный план) ОДР
2. Проверить, является ли она оптимальной
3. Если нет — перейти к соседней вершине с лучшим значением $Z$
4. Повторять до достижения оптимума

Базис и опорный план

Для системы $m$ линейных уравнений с $n$ переменными ($n > m$) в канонической форме:

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \end{cases}$$

Базис — это набор из $m$ линейно независимых векторов-столбцов коэффициентов матрицы $A$.

• Переменные, вошедшие в базис, называются базисными ($x_B$)
• Остальные $n - m$ переменных — свободные ($x_N$)

Опорный план

Опорный план (допустимое базисное решение) — решение, получаемое приравниванием свободных переменных к нулю и решением системы относительно базисных:

$$x_N = 0 \quad \Rightarrow \quad x_B = A_B^{-1} b$$

Опорный план называется допустимым, если $x_B \geq 0$.

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

• Каждый опорный план соответствует вершине ОДР
• Смена базиса = переход к соседней вершине
• Симплекс-метод перебирает вершины алгебраически, через базисы

Пример: начальный базис

$$2x_1 + x_2 + x_3 = 100$$

$$x_1 + 2x_2 + x_4 = 80$$

Матрица коэффициентов:

$$A = \begin{pmatrix} 2 & 1 & \mathbf{1} & 0 \\ 1 & 2 & 0 & \mathbf{1} \end{pmatrix}$$

Начальный базис: столбцы переменных $x_3$ и $x_4$ образуют единичную матрицу $I$.

$$x_N = (x_1, x_2) = (0, 0) \quad \Rightarrow \quad x_B = (x_3, x_4) = (100, 80) \geq 0$$

Это допустимый опорный план $\Rightarrow$ вершина ОДР $(0, 0, 100, 80)$.

Свойства базиса

Вырожденные и невырожденные опорные планы

Невырожденный опорный план: все базисные переменные $x_B > 0$ (строго положительны).

Вырожденный опорный план: хотя бы одна базисная переменная $x_B = 0$.

• Вырожденный план соответствует вершине ОДР, в которой сходится более $m$ гиперплоскостей
• При вырождении возможен зацикливание (возврат к ранее рассмотренному базису)
• На практике применяется правило Бланда: выбирать переменную с наименьшим индексом

Смена базиса в симплекс-методе

На каждой итерации симплекс-метод выполняет смену базиса:

1. Вводимая переменная: свободная переменная $x_j$ с отрицательной оценкой $\Delta_j < 0$ входит в базис (может улучшить $Z$)
2. Выводимая переменная: базисная переменная $x_i$, для которой $\theta_i = \min \dfrac{b_i}{a_{ij}}$ при $a_{ij} > 0$, выходит из базиса
3. Жорданово исключение: пересчёт таблицы относительно разрешающего элемента $a_{i^* j^*}$

$$\text{Новый базис} = (\text{старый базис} \setminus \{x_{i^*}\}) \cup \{x_{j^*}\}$$

Свойства симплекс-метода

• Конечность — алгоритм завершается за конечное число итераций (при отсутствии вырождения или с правилом Бланда)
• Монотонность — значение $Z$ не ухудшается на каждом шаге
• Универсальность — решает любую задачу ЛП
• Сложность: в худшем случае — экспоненциальная, на практике — полиномиальная

Алгоритм симплекс-метода

Шаг 1. Привести задачу к канонической форме

Шаг 2. Выбрать начальный базис (обычно — балансовые переменные) и составить опорный план

Шаг 3. Заполнить симплекс-таблицу

Шаг 4. Проверить оптимальность (все $\Delta_j \geq 0$ для $\max$)

Шаг 5. Если не оптимально — выполнить смену базиса (выбрать разрешающий элемент, жорданово исключение)

Шаг 6. Вернуться к шагу 4

Симплекс-таблица

Правила выбора разрешающего элемента

Разрешающий столбец (для $\max Z$):

• Выбираем $j^*$, где $\Delta_{j^*} = \min \Delta_j < 0$

Разрешающая строка:

• Вычисляем оценочные отношения: $\theta_i = \dfrac{b_i}{a_{i j^*}}$, при $a_{i j^*} > 0$
• Выбираем $i^*$, где $\theta_{i^*} = \min \theta_i$

Разрешающий элемент: $a_{i^* j^*}$

Пример: начальная симплекс-таблица

Каноническая форма:

$$Z - 3x_1 - 5x_2 = 0$$

$$2x_1 + x_2 + x_3 = 100$$

$$x_1 + 2x_2 + x_4 = 80$$

Разрешающий элемент: $a_{22} = 2$ (столбец $x_2$, строка $x_4$)

Пример: вторая симплекс-таблица

Разрешающий элемент: $a_{11} = 3/2$

Пример: оптимальная таблица

Все $\Delta_j \geq 0$ — оптимальный план найден!

$x_1^* = 40$, $x_2^* = 20$, $Z^* = 220$

Искусственный базис (M-метод)

Когда начальный опорный план не очевиден (ограничения вида $=$ или $\geq$):

• Вводятся искусственные переменные $w_i \geq 0$
• В целевую функцию добавляется штраф: $M \cdot w_i$, где $M$ — большое число
• Решается расширенная задача
• Если $w_i^* = 0$ — исходная задача имеет решение
• Если $w_i^* > 0$ — исходная задача несовместна

5. Транспортная задача

Транспортная задача — задача ЛП о минимизации стоимости перевозки грузов от $m$ поставщиков к $n$ потребителям.

$$Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \to \min$$

$$\begin{cases} \sum\limits_{j=1}^{n} x_{ij} = a_i, \quad i = 1, \ldots, m \quad \text{(запасы)} \\ \sum\limits_{i=1}^{m} x_{ij} = b_j, \quad j = 1, \ldots, n \quad \text{(потребности)} \\ x_{ij} \geq 0 \end{cases}$$

Пример транспортной задачи

         Потребители
         B1  B2  B3  B4   Запасы
A1       3   5   7   6     30
A2       2   5   8   7     40
A3       3   6   9   6     30
Потребн. 20  30  25  25

$m = 3$ поставщика, $n = 4$ потребителя

Условие баланса: $\sum a_i = \sum b_j = 100$

Методы построения начального плана

Пример: метод северо-западного угла

          B1   B2   B3   B4   Запасы
   A1    [20] [10]       —     30
   A2     —   [20] [20]  —     40
   A3     —    —   [5]  [25]   30
Потребн.  20   30   25   25

Число занятых клеток: $6 = 3 + 4 - 1$ — опорный план

Стоимость: $20 \cdot 3 + 10 \cdot 5 + 20 \cdot 5 + 20 \cdot 8 + 5 \cdot 9 + 25 \cdot 6 = 60 + 50 + 100 + 160 + 45 + 150 = 565$

Пример: метод наименьшей стоимости

Тарифы:          B1  B2  B3  B4
            A1   3   5   7   6
            A2   2   5   8   7
            A3   3   6   9   6

Шаги:

1. $\min c_{ij} = 2$ → клетка $(2,1)$: $x_{21} = \min(40, 20) = 20$
2. $\min = 3$ → клетка $(1,1)$: $x_{11} = \min(30, 0) = 0$ (пропускаем, $B_1$ исчерпан)
3. $\min = 3$ → клетка $(3,1)$: пропускаем. $\min = 5$ → $(1,2)$: $x_{12} = \min(30, 30) = 30$
4. $\min = 6$ → $(3,4)$: $x_{34} = \min(30, 25) = 25$
5. $(3,2)$: $x_{32} = \min(5, 0) = 0$ (пропускаем). $(2,2)$: $x_{22} = \min(20, 0) = 0$
6. $(1,3)$: $x_{13} = \min(0, 25) = 0$. $(2,3)$: $x_{23} = \min(20, 25) = 20$
7. $(3,3)$: $x_{33} = \min(5, 5) = 5$

Пример: метод наименьшей стоимости (результат)

          B1   B2   B3   B4   Запасы
   A1     —   [30]       —     30
   A2    [20]      [20]  —     40
   A3     —    —   [5]  [25]   30
Потребн.  20   30   25   25

Занятые клетки: $(1,2), (2,1), (2,3), (3,3), (3,4)$ — 5 шт. ($= 3 + 4 - 1$)

Стоимость: $30 \cdot 5 + 20 \cdot 2 + 20 \cdot 8 + 5 \cdot 9 + 25 \cdot 6 = 150 + 40 + 160 + 45 + 150 = 545$

Сравнение:

• Северо-западный угол: $Z = 565$
• Наименьшая стоимость: $Z = 545$ (лучше на 20)

Метод потенциалов

Алгоритм:

1. Построить начальный опорный план ($m + n - 1$ заполненных клеток)
2. Найти потенциалы $u_i$ и $v_j$: $u_i + v_j = c_{ij}$ для занятых клеток
3. Вычислить оценки свободных клеток: $\Delta_{ij} = c_{ij} - u_i - v_j$
4. Если все $\Delta_{ij} \geq 0$ — план оптимален
5. Иначе — выбрать клетку с $\min \Delta_{ij} < 0$, построить цикл, перераспределить грузы
6. Вернуться к шагу 2

Пример: метод потенциалов — итерация 1

Начальный план (северо-западный угол), занятые клетки: $(1,1), (1,2), (2,2), (2,3), (3,3), (3,4)$.

Потенциалы из $u_i + v_j = c_{ij}$, $u_1 = 0$:

Пример: итерация 1 — цикл и новый план

$\min \Delta_{ij} < 0$: $\Delta_{13} = -1$ — клетка $(1,3)$.

Цикл: $(1,3)^{+} \to (2,3)^{-} \to (2,2)^{+} \to (1,2)^{-} \to (1,3)$

$\theta = \min(x_{23},\, x_{12}) = \min(20,\, 10) = 10$

          B1   B2   B3   B4   Запасы
   A1    [20]       [10]  —     30
   A2     —   [30]  [10]  —     40
   A3     —    —    [5]  [25]   30

$Z = 20 \cdot 3 + 10 \cdot 7 + 30 \cdot 5 + 10 \cdot 8 + 5 \cdot 9 + 25 \cdot 6 = 555$

Пример: метод потенциалов — итерация 2

Занятые клетки: $(1,1), (1,3), (2,2), (2,3), (3,3), (3,4)$.

Пример: итерация 2 — цикл и новый план

$\min \Delta_{ij} < 0$: $\Delta_{21} = -2$ — клетка $(2,1)$.

Цикл: $(2,1)^{+} \to (1,1)^{-} \to (1,3)^{+} \to (2,3)^{-} \to (2,1)$

$\theta = \min(x_{11},\, x_{23}) = \min(20,\, 10) = 10$

          B1   B2   B3   B4   Запасы
   A1    [10]       [20]  —     30
   A2    [10] [30]        —     40
   A3     —    —    [5]  [25]   30

$Z = 10 \cdot 3 + 20 \cdot 7 + 10 \cdot 2 + 30 \cdot 5 + 5 \cdot 9 + 25 \cdot 6 = 535$

Пример: метод потенциалов — итерация 3

Занятые клетки: $(1,1), (1,3), (2,1), (2,2), (3,3), (3,4)$.

Пример: итерация 3 — цикл и новый план

$\min \Delta_{ij} < 0$: $\Delta_{31} = -2$ — клетка $(3,1)$.

Цикл: $(3,1)^{+} \to (1,1)^{-} \to (1,3)^{+} \to (3,3)^{-} \to (3,1)$

$\theta = \min(x_{11},\, x_{33}) = \min(10,\, 5) = 5$

          B1   B2   B3   B4   Запасы
   A1    [5]        [25]  —     30
   A2    [10] [30]        —     40
   A3    [5]              [25]  30

$Z = 5 \cdot 3 + 25 \cdot 7 + 10 \cdot 2 + 30 \cdot 5 + 5 \cdot 3 + 25 \cdot 6 = 525$

Пример: метод потенциалов — итерация 4

Занятые клетки: $(1,1), (1,3), (2,1), (2,2), (3,1), (3,4)$.

Пример: итерация 4 — цикл и новый план

$\min \Delta_{ij} < 0$: $\Delta_{12} = -1$ — клетка $(1,2)$.

Цикл: $(1,2)^{+} \to (2,2)^{-} \to (2,1)^{+} \to (1,1)^{-} \to (1,2)$

$\theta = \min(x_{22},\, x_{11}) = \min(30,\, 5) = 5$

          B1   B2   B3   B4   Запасы
   A1         [5]  [25]  —     30
   A2    [15] [25]       —     40
   A3    [5]             [25]  30

$Z = 5 \cdot 5 + 25 \cdot 7 + 15 \cdot 2 + 25 \cdot 5 + 5 \cdot 3 + 25 \cdot 6 = 520$

Пример: проверка оптимальности

Занятые клетки: $(1,2), (1,3), (2,1), (2,2), (3,1), (3,4)$.

Потенциалы: $u_1 = 0, \; u_2 = 0, \; u_3 = 1, \; v_1 = 2, \; v_2 = 5, \; v_3 = 7, \; v_4 = 5$

$$\Delta_{11} = 3 - 0 - 2 = 1, \quad \Delta_{14} = 6 - 0 - 5 = 1$$

$$\Delta_{23} = 8 - 0 - 7 = 1, \quad \Delta_{24} = 7 - 0 - 5 = 2$$

$$\Delta_{32} = 6 - 1 - 5 = 0, \quad \Delta_{33} = 9 - 1 - 7 = 1$$

Все $\Delta_{ij} \geq 0$ — план оптимален!

$$\boxed{Z^* = 520}$$

Прогресс метода потенциалов: $565 \to 555 \to 535 \to 525 \to 520$

6. Двойственность в линейном программировании

Каждой задаче ЛП (прямая) соответствует двойственная задача.

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

$$Z = c^T x \to \max, \quad Ax \leq b, \quad x \geq 0$$

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

$$W = b^T y \to \min, \quad A^T y \geq c, \quad y \geq 0$$

Первая теорема двойственности

Если прямая задача имеет оптимальное решение $\vec{x}^*$, то двойственная также имеет оптимальное решение $\vec{y}^*$, причём:

$$Z^* = W^*$$

Экономическая интерпретация:

• $y_i^*$ — «теневая цена» (двойственная оценка) ресурса $i$
• Показывает, на сколько увеличится прибыль при увеличении запаса ресурса $i$ на единицу
• Помогает анализировать чувствительность решения

Вторая теорема двойственности (дополняющая нежёсткость)

Для оптимальных планов $\vec{x}^*$ и $\vec{y}^*$ выполняется:

$$y_i^* (a_{i1}x_1^* + \cdots + a_{in}x_n^* - b_i) = 0$$

$$(c_j - a_{1j}y_1^* - \cdots - a_{mj}y_m^*) x_j^* = 0$$

Смысл: если ресурс не полностью используется, его двойственная оценка равна нулю; если продукция не производится, её «стоимость» не превышает цену.

7. Программные средства решения задач ЛП

Класс инструментов:

Пример: SciPy (scipy.optimize.linprog)

from scipy.optimize import linprog

# Z = 3x1 + 5x2 -> max  =>  -Z = -3x1 - 5x2 -> min
c = [-3, -5]              # коэффициенты целевой функции

# Ax <= b
A_ub = [[2, 1], [1, 2]]  # матрица ограничений
b_ub = [100, 80]          # правые части

# x >= 0 (по умолчанию)

result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='highs')
print(result.x)   # [40. 20.]
print(-result.fun) # 220.0

Пример: PuLP

from pulp import *

prob = LpProblem("example", LpMaximize)

x1 = LpVariable('x1', lowBound=0)
x2 = LpVariable('x2', lowBound=0)

prob += 3*x1 + 5*x2
prob += 2*x1 + x2 <= 100
prob += x1 + 2*x2 <= 80

prob.solve()
print(f"x1 = {x1.varValue}, x2 = {x2.varValue}")
print(f"Z = {value(prob.objective)}")
# x1 = 40.0, x2 = 20.0, Z = 220.0

Пример: Excel Solver («Поиск решения»)

Настройка:

1. Ячейки $B1$ (переменная $x_1$) и $B2$ (переменная $x_2$) — изменяемые
2. Ячейка $C1$: =3*B1 + 5*B2 — целевая (максимизировать)
3. Ячейка $C2$: =2*B1 + B2 — ограничение $\leq 100$
4. Ячейка $C3$: =B1 + 2*B2 — ограничение $\leq 80$

Параметры Solver:

• Оптимизировать: $C1$ → Максимум
• Изменяя: $B1{:}B2$
• Ограничения: $C2 \leq 100$, $C3 \leq 80$, $B1{:}B2 \geq 0$
• Метод: Поиск решения линейных задач симплекс-методом

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

from scipy.optimize import linear_sum_assignment

# Матрица тарифов
cost = [[3, 5, 7, 6],
        [2, 5, 8, 7],
        [3, 6, 9, 6]]

# Для закрытой транспортной задачи — scipy.sparse
from scipy.sparse import csr_matrix
from scipy.optimize import milp, LinearConstraint, Bounds

# Или через PuLP (проще для транспортной задачи):
from pulp import *
prob = LpProblem("transport", LpMinimize)
x = [[LpVariable(f"x{i}{j}", lowBound=0)
      for j in range(4)] for i in range(3)]

prob += lpSum(cost[i][j]*x[i][j]
              for i in range(3) for j in range(4))

# ограничения по запасам и потребностям...
prob.solve()
print(f"Z* = {value(prob.objective)}")  # 520

Программные средства и лабораторные работы

Лабораторная работа «Линейное программирование» — инструменты:

Заключение

Ключевые выводы лекции

Вопросы для самоконтроля

1. Что такое задача линейного программирования? Назовите компоненты модели.
2. В чём разница между канонической и стандартной формами ЗЛП?
3. Сформулируйте теорему об оптимальности в крайней точке ОДР.
4. Опишите основные шаги симплекс-метода.
5. Как выбрать разрешающий элемент в симплекс-таблице?
6. В каком случае применяется искусственный базис (M-метод)?
7. Сформулируйте первую теорему двойственности и её экономический смысл.
8. Опишите алгоритм метода потенциалов для транспортной задачи.

Рекомендуемые ресурсы