Линейное программирование: постановка задачи и графический метод

Цех получил заказ: нужны столы и тумбы, сколько сможет сделать — столько заберут. Один стол приносит 2 тысячи прибыли, одна тумба — 3 тысячи. Ресурсов впритык: станок А отработает до конца месяца не больше 8 часов, причём стол требует час его работы, тумба — два; у станка Б остаётся 6 часов, и он тратит по часу на любое изделие. Запускать одни тумбы? Выходит 4 тумбы и 12 тысяч. Одни столы? 6 столов и те же 12 тысяч. А если смешать? Оказывается, 4 стола и 2 тумбы дадут 14 тысяч — больше любой крайности. Как получать такие ответы не перебором догадок, а алгоритмом, и есть вопрос линейного программирования.

Что такое ЗЛП: три обязательных ингредиента#

Задача линейного программирования (ЗЛП) — задача об оптимизации линейной функции на множестве, заданном линейными неравенствами и равенствами. В общем виде она записывается так:

На переменные наложены ограничения — по одному на каждый ресурс:

Наконец, третий ингредиент — неотрицательность: $x_j\ge 0$. Отрицательный выпуск не имеет смысла. Слово «линейное» в названии означает: ни одна переменная не возводится в степень, не умножается на другую, под неё не подставляется синус. Благодаря этому каждое ограничение вырезает из пространства полуплоскость, а целевая функция задаёт семейство параллельных прямых — на этом и построен графический метод.

• линейная целевая функция — то, что максимизируем или минимизируем;
• линейные ограничения — неравенства или равенства, задающие границы плана;
• неотрицательность переменных — её иногда снимают, тогда меняется техника, но не идея.

Жизненные постановки: план, рацион и раскрой#

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

Задача о рационе (диете) — зеркальная: не прибыль максимизировать, а затраты минимизировать при обязательных требованиях. Есть корма с ценами и содержанием питательных веществ; нужно смешать их так, чтобы животное получило норму белка, жиров и витаминов, а смесь стоила дешевле всех остальных допустимых смесей.

Задача о раскрое: на складе прутки по 6 метров, а нужны заготовки двух сортов — по 2 и по 3 метра. Каждый способ разрезания даёт свой набор заготовок и свои обрезки. Переменные — сколько прутков резать каждым способом, критерий — минимум отходов или минимум израсходованных прутков. Похожа на неё и транспортная постановка про склады и магазины — у неё отдельный урок.

Общий знаменатель один: ищем неотрицательные числа, которые при заданных ресурсах дают наилучший результат. Различаются только «легенды» и коэффициенты.

Стандартная и каноническая форма: зачем две#

Стандартной (или симметричной) формой называют запись, где все ограничения — неравенства «≤», целевая функция максимизируется, переменные неотрицательны. Наша задача про цех записана именно так.

Каноническая форма требует равенств: каждое неравенство дополняют балансовой переменной. Ограничение $x_1+2x_2\le 8$ превращается в $x_1+2x_2+x_3=8$, где $x_3$ — недогрузка станка А, простой в часах. Ограничение со знаком «≥» приводят умножением строки на $-1$, а переменную без ограничения знака заменяют разностью двух неотрицательных. Зачем возня? Каноническая форма — стартовая площадка симплекс-метода: в ней сразу читается начальный базис.

Как нарисовать задачу: полуплоскости и линия уровня#

Пока переменных две, задачу можно нарисовать. Каждое линейное неравенство на плоскости — полуплоскость: прямая-граница плюс одна из двух сторон. Пересечение всех полуплоскостей и условий неотрицательности называют областью допустимых решений (ОДР). Это выпуклый многоугольник — возможно, пустой или неограниченный, но всегда выпуклый, если не пуст.

Целевая функция $F=c_{1}x+c_{2}y$ рисуется линиями уровня — прямыми $c_{1}x+c_{2}y=v$ с разными значениями $v$. Все они параллельны, а направление роста задаёт вектор $(c_1,c_2)$ — градиент. Двигаем линию уровня по стрелке; последняя точка, где она ещё касается ОДР, — оптимум.

На чертеже видна и главная теорема метода: если ОДР ограничена, линейная функция достигает максимума и минимума в вершинах многоугольника. Доказательство короткое: линия уровня либо касается многоугольника вершиной, либо сливается с целой стороной — но и тогда концы стороны, тоже вершины, дают то же значение. Практический вывод: вместо бесконечного множества точек достаточно посчитать $F$ в конечном числе вершин.

Полный пример: 2x + 3y → max с перебором вершин#

Вернёмся к цеху. Обозначим $x$ — столы, $y$ — тумбы. Прибыль и два ресурса дают систему:

1. 1
   Прямая $x+2y=8$ проходит через точки $(0,4)$ и $(8,0)$. Подстановка $(0,0)$ даёт $0\le 8$ — верно, значит, берём полуплоскость с началом координат.
2. 2
   Прямая $x+y=6$ проходит через $(0,6)$ и $(6,0)$; проверка нулём снова работает.
3. 3
   Условия $x\ge 0$, $y\ge 0$ оставляют первый квадрант.
4. 4
   ОДР — четырёхугольник с вершинами $(0,0)$, $(6,0)$, $(4,2)$, $(0,4)$; точка $(4,2)$ — пересечение прямых $x+2y=8$ и $x+y=6$: вычтем второе из первого, получим $y=2$, затем $x=4$.

Максимум равен 14 при $x=4$, $y=2$: четыре стола и две тумбы. Проверка честная: станок А загружен целиком — $4+2\cdot 2=8$ часов, станок Б тоже — $4+2=6$ часов. Оба ресурса прижаты к границе. Если бы какая-то полуплоскость «болталась» в стороне, стоило бы перепроверить арифметику.

Заметьте, как легли числа: чистые тумбы дают 12, чистые столы — тоже 12, а смесь выжимает 14. Интуиция «бери самое прибыльное» ошибается, потому что тумба съедает два дефицитных часа станка А. Редкий случай, когда «немножко всего» математически честнее, чем удар в одну точку.

Когда метод молчит: пустая ОДР и вечный рост#

Первый патологический случай — ОДР пуста: ограничения противоречивы. Например, $x+y\le 1$ и $x+y\ge 3$ не выполняются одновременно ни в какой точке. На чертеже полуплоскости не пересекаются, допустимых планов нет вовсе. В жизни это значит, что заказ невыполним физически, и чинить надо постановку — ресурсы или обещания, — а не алгоритм.

Второй случай — неограниченность. Возьмём $F=x_1+x_2\to \max$ при единственном ограничении $x_1-x_2\le 1$ и $x_1,x_2\ge 0$. План $(t+1,t)$ допустим при любом $t\ge 0$, а $F=2t+1$ растёт без предела. ОДР — бесконечный клин, линия уровня уезжает по нему вечно, максимума не существует. Симплекс-метод сообщает об этом отдельным сигналом — увидим его в уроке про симплекс-метод.

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

Что дальше#

При трёх переменных рисовать уже тесно, при десяти — невозможно. Но вывод «оптимум прячется в вершине» никуда не уходит: симплекс-метод перебирает вершины алгебраически, без единого чертежа. Систему ограничений удобно держать в матричной записи — об этом матрицы и операции, а решать систему руками научит СЛАУ и метод Гаусса; сам термин закреплён в статье про систему линейных уравнений. Корни всей линии — введение в теорию игр: исследование операций выросло из игр как их вырожденный случай с «природой» вместо противника.

Следующий шаг конкретный: возьмите задачу из урока и поменяйте прибыли местами — $F=3x+2y\to \max$ при тех же ограничениях. Пройдите графический метод от начала до конца и сверьтесь: оптимум должен переехать в вершину $(6,0)$ со значением 18. Сошлось — вы готовы к симплекс-методу.