Линейное программирование и симплекс-метод

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

Линейное программирование отвечает на вопрос «как распределить ограниченные ресурсы наилучшим образом». Это ядро курсовых по математическому моделированию, методам оптимизации и логистике.

Постановка задачи

Найти max (или min) целевой функции

  Z = c₁x₁ + c₂x₂ + … + cₙxₙ

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

  a₁₁x₁ + a₁₂x₂ + … ≤ b₁
  a₂₁x₁ + a₂₂x₂ + … ≤ b₂
  …
  xⱼ ≥ 0        (условие неотрицательности)

Все функции линейны — отсюда название.

Пример: цех выпускает изделия А и Б

  Прибыль:  30 руб. с А, 40 руб. с Б  →  Z = 30x₁ + 40x₂ → max

  Ограничения по ресурсам:
    металл:  2x₁ + 4x₂ ≤ 100 кг
    время:   3x₁ + 2x₂ ≤ 90 ч
    спрос:   x₂ ≤ 20 шт
    x₁, x₂ ≥ 0

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

1. Построить полуплоскости по каждому ограничению и найти область допустимых решений — выпуклый многоугольник.
2. Построить вектор-градиент целевой функции c = (c₁, c₂) — он указывает направление наибольшего роста Z.
3. Провести линию уровня Z = const перпендикулярно градиенту.
4. Двигать линию уровня по направлению градиента (для максимума) до последней точки касания области.
5. Найти координаты этой точки как решение системы двух ограничений, ставших равенствами.
6. Вычислить значение Z.

Канонический вид

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

  ≤ : добавляем дополнительную переменную   2x₁ + 4x₂ + x₃ = 100
  ≥ : вычитаем дополнительную и вводим искусственную
  = : вводим искусственную переменную

  min Z  →  max (−Z)

Дополнительные переменные имеют экономический смысл:
это неиспользованный остаток ресурса.

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

1. Привести задачу к каноническому виду и составить начальную симплекс-таблицу с базисом из дополнительных переменных.
2. Проверить строку целевой функции: если все оценки неотрицательны (для максимума), решение оптимально.
3. Выбрать разрешающий столбец — с наибольшей по модулю отрицательной оценкой.
4. Найти разрешающую строку: минимальное положительное отношение свободного члена к элементу разрешающего столбца.
5. Пересчитать таблицу методом Жордана-Гаусса, сделав разрешающий элемент единицей, а остальные в столбце нулями.
6. Повторять, пока не получится оптимальное решение.

Начальная таблица для примера (max Z = 30x₁ + 40x₂):

Базис │ x₁   x₂   x₃  x₄  x₅ │ b   │ b/x₂
──────┼───────────────────────┼─────┼──────
 x₃   │  2    4    1   0   0 │ 100 │  25
 x₄   │  3    2    0   1   0 │  90 │  45
 x₅   │  0    1    0   0   1 │  20 │  20 ← разрешающая
──────┼───────────────────────┼─────┼──────
  Z   │ −30  −40   0   0   0 │  0  │
                ↑ разрешающий столбец

После двух итераций: x₁ = 20, x₂ = 15, Z = 30·20 + 40·15 = 1200

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

Прямая:                    Двойственная:
  max Z = c·x                min W = b·y
  A·x ≤ b                    Aᵀ·y ≥ c
  x ≥ 0                      y ≥ 0

Теорема двойственности: оптимальные значения совпадают, Z* = W*

Переменные yᵢ — теневые цены ресурсов: показывают,
на сколько вырастет прибыль при увеличении i-го ресурса на единицу.

Теневые цены — самая содержательная часть анализа для курсовой: они показывают, какой ресурс расширять выгоднее всего. Нулевая теневая цена означает, что ресурс избыточен и добавлять его бессмысленно.

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

Даны m поставщиков с запасами aᵢ и n потребителей с потребностями bⱼ,
стоимость перевозки единицы cᵢⱼ. Минимизировать суммарные затраты.

  Условие закрытости: Σ aᵢ = Σ bⱼ
  Если не выполнено — вводят фиктивного поставщика или потребителя
  с нулевыми тарифами.

Число занятых клеток в базисном решении: m + n − 1

• Начальное решение строят методом северо-западного угла (просто, но грубо) или методом минимального элемента (ближе к оптимуму).
• Улучшают методом потенциалов: находят потенциалы поставщиков и потребителей, проверяют оценки свободных клеток.
• Если все оценки неотрицательны — решение оптимально.
• Иначе строят цикл пересчёта через клетку с самой отрицательной оценкой и перераспределяют поставки.

Решение на компьютере

from scipy.optimize import linprog

# scipy минимизирует, поэтому для максимума меняем знак коэффициентов
c = [-30, -40]
A = [[2, 4],
     [3, 2],
     [0, 1]]
b = [100, 90, 20]

res = linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], method='highs')

print('x =', res.x)              # [20. 15.]
print('Z =', -res.fun)           # 1200.0
print('теневые цены:', -res.ineqlin.marginals)

Типовые задачи для курсовой

Если переменные должны быть целыми — например, число станков — задача становится целочисленной и решается методом ветвей и границ или методом Гомори. Округление непрерывного решения в общем случае даёт неоптимальный, а иногда и недопустимый ответ.