Линейное программирование: задача, у которой ответ в углу

Если ты умеешь записать задачу в стандартной форме, знаешь, почему оптимум достигается в вершине, и понимаешь разницу между линейным и целочисленным программированием, листай до «Теперь сам».

Как думаешь, где искать максимум

Цех делает два изделия. На первое уходит 2 часа станка и 3 часа сборки, на второе - 4 часа станка и 1 час сборки. Станок доступен 12 часов, сборка - 10. Прибыль: 5 за первое изделие, 4 за второе. Сколько чего делать?

Соблазн - перебрать целые количества. Но сначала ответь на другой вопрос: где вообще может стоять ответ? Внутри области или на границе? И если на границе, то в любой её точке или в особенной?

На что это похоже

Наклонная плоскость над многоугольной площадкой. Цель 5x + 4y - это высота: чем дальше в направлении «роста», тем выше. Поставь шарик в любую точку площадки и отпусти - он покатится в сторону роста и остановится, упёршись в край. Покатится вдоль края - и остановится в углу. Именно поэтому оптимум ищут в углах: из любой внутренней точки всегда есть куда идти, а из угла - уже нет.

Механизм: стандартная форма и геометрия

стандартная форма:
    максимизировать   c₁x₁ + c₂x₂ + ... + cₙxₙ
    при условиях      a₁₁x₁ + ... + a₁ₙxₙ <= b₁
                      ...
                      aₘ₁x₁ + ... + aₘₙxₙ <= bₘ
                      x₁ >= 0, ..., xₙ >= 0

Каждое неравенство отсекает полуплоскость (в общем случае полупространство). Пересечение полупространств - выпуклый многогранник: у него плоские грани и нет вмятин. Цель cᵀx растёт в одном фиксированном направлении, поэтому её линии уровня - параллельные прямые (плоскости), и двигать их можно только до касания многогранника.

три исхода линейной задачи:
    допустимых точек нет вовсе          - задача НЕСОВМЕСТНА
    цель растёт неограниченно           - оптимум НЕ ОГРАНИЧЕН
    оптимум конечен                     - он достигается в вершине
                                          (иногда на целой грани, но вершина среди них есть)

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

Правило

Линейное программирование: максимизировать линейную цель при линейных ограничениях-неравенствах и неотрицательности переменных. Допустимая область - выпуклый многогранник. Если оптимум конечен, он достигается в ВЕРШИНЕ - точке пересечения n ограничений, обратившихся в равенства. Задача бывает несовместной или неограниченной, и оба случая надо различать в ответе. Целочисленное программирование - это то же самое плюс требование целых значений, и оно NP-трудно: вершины перестают помогать.

Разбор: считаем цех по вершинам

Запишем задачу из вступления: x - первых изделий, y - вторых.

максимизировать  5x + 4y
    2x + 3y <= 12        станок (2 часа и 3 часа)
    4x +  y <= 10        сборка (4 часа и 1 час)
    x >= 0,  y >= 0

Вершины - это пересечения пар ограничений, обратившихся в равенства. Перебираем:

(0, 0)                     цель 0
(0, 4)    из 2x + 3y = 12  цель 16
(2.5, 0)  из 4x +  y = 10  цель 12.5
(1.8, 2.8) пересечение обоих ограничений:
           2x + 3y = 12 и 4x + y = 10  →  x = 1.8, y = 2.8
           проверка: 3.6 + 8.4 = 12 <= 12 ✓,  7.2 + 2.8 = 10 <= 10 ✓
           цель 5·1.8 + 4·2.8 = 9 + 11.2 = 20.2

Максимум - 20.2 в дробной точке. Теперь сравни с перебором целых точек: лучшая целая - (2, 2) с целью 18. Разница не в точности вычислений, а в том, что ответ линейной задачи ПРИНЦИПИАЛЬНО может стоять между узлами сетки. Уменьшение шага не помогает - оно лишь делает перебор дороже.

Разбор: почему оптимум обязан быть в вершине

Возьми любую допустимую точку, которая не является вершиной. Тогда у неё есть направление, в котором можно сдвинуться в обе стороны, не выходя из области, - скажем, d и −d. Значение цели изменится на cᵀd и −cᵀd: одно из двух неотрицательно. Значит, сдвинувшись в подходящую сторону, цель не ухудшишь.

идём в сторону, где цель не падает, пока не упрёмся в ограничение
упёрлись - получили точку, у которой на одно активное ограничение больше
повторяем: активных ограничений становится всё больше
через конечное число шагов их n штук - это и есть вершина

Вывод: от любой точки можно дойти до вершины, не ухудшив цель. Поэтому среди вершин обязательно есть оптимальная, и перебирать внутренность бессмысленно. Тот же аргумент объясняет, почему оптимум иногда достигается на целом ребре: если цель перпендикулярна направлению ребра, то вдоль него она не меняется - но и тогда концы ребра (вершины) не хуже.

Сколько всего вершин? Каждая задаётся набором из n ограничений, обратившихся в равенства, значит их не больше C(m, n), где m - число ВСЕХ ограничений, включая x >= 0: они такие же прямые, и вершины на них лежат наравне с остальными. Для двух переменных и десяти ограничений (восемь содержательных плюс две неотрицательности) это C(10, 2) = 45 - перебрать легко. Для двадцати переменных и сотни ограничений - астрономическое число, и нужен алгоритм, который ходит по вершинам, а не перебирает их. Это симплекс, и он в следующем уроке.

Что ломается без этого

Первое: искать оптимум перебором целых точек. Ответ будет занижен, а работы - в разы больше. Второе: забыть ограничения неотрицательности. Без них область другая, и «оптимум» может уехать в минус. Третье: не различать несовместную и неограниченную задачу: первая означает «ограничения противоречат друг другу», вторая - «в модели что-то забыли, прибыль не может расти вечно». Четвёртое: считать, что раз ответ дробный, надо просто округлить его до ближайшего целого - округлённая точка может оказаться недопустимой, а честное целочисленное решение может лежать совсем в другом углу. Пятое: путать линейное программирование с целочисленным: первое решается за полиномиальное время, второе NP-трудно, и внешне задачи отличаются одной строчкой условия.

Зачем это в работе

Линейное программирование - редкий случай, когда «есть готовый решатель» - это правда. Задачу описывают, а решает её библиотека (scipy.optimize.linprog, PuLP, OR-Tools, коммерческие Gurobi и CPLEX), причём с десятками тысяч переменных. Выглядит описание так:

from scipy.optimize import linprog
# linprog МИНИМИЗИРУЕТ, поэтому цель 5x + 4y берётся со знаком минус
res = linprog(c=[-5, -4],
              A_ub=[[2, 3], [4, 1]], b_ub=[12, 10],   # ограничения-неравенства
              bounds=[(0, None), (0, None)])          # x >= 0, y >= 0
print(-res.fun, res.x)        # 20.2  [1.8 2.8]

20.2 [1.8 2.8]

Вся работа - в трёх списках: коэффициенты цели, матрица ограничений и правые части. Практическая работа сводится к тому, чтобы ПРАВИЛЬНО ЗАПИСАТЬ задачу: что за переменные, какая цель, какие ограничения. Типовые сюжеты: раскрой материала с минимумом отходов, составление рациона или смеси заданного состава, загрузка производства, распределение рекламного бюджета, планирование смен, логистика перевозок. А ещё линейная форма нужна как ЯЗЫК: многие задачи проще сперва записать как ЛП, а потом заметить, что у них есть специальная быстрая структура - например, что это поток.

Теперь сам

Запиши задачу и найди максимум: столяр делает табуретки и полки. Табуретка требует 3 доски и 2 часа, полка - 1 доску и 4 часа. Досок 24, часов 32. Прибыль: 6 за табуретку, 5 за полку.

максимизировать  6x + 5y
    3x + y  <= 24      доски
    2x + 4y <= 32      часы
    x >= 0,  y >= 0

(0, 0)                          цель 0
(0, 8)    из 2x + 4y = 32       цель 40
(8, 0)    из 3x + y = 24        цель 48
пересечение 3x + y = 24 и 2x + 4y = 32:
    из первого y = 24 − 3x, подставляем: 2x + 96 − 12x = 32 → −10x = −64 → x = 6.4, y = 4.8
    проверка: 19.2 + 4.8 = 24 ✓,  12.8 + 19.2 = 32 ✓
    цель 6·6.4 + 5·4.8 = 38.4 + 24 = 62.4