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

Задача из жизни цеха. Продукция двух видов: изделия $A$ и $B$. На изделие $A$ уходит $2$ единицы древесины, на $B$ — одна; всего древесины $12$ единиц в смену. На станке: $A$ занимает $1$ час, $B$ — $2$ часа; всего $12$ часов. Прибыль: $40$ рублей с изделия $A$, $30$ — с $B$. Сколько выпускать каждого, чтобы заработать больше всего? Две переменные — и это подарок: задача решается карандашом на листе бумаги, без единой итерации симплекса. Графический метод — не игрушка, а способ увидеть устройство всей линейной оптимизации: ответ всегда сидит в вершине.

Стандартная форма задачи#

Обозначим план выпуска $x$ (изделия $A$) и $y$ (изделия $B$). Ограничения по ресурсам и неотрицательность выпуска дают систему неравенств, а цель — функцию прибыли:

Слово «линейное» здесь буквальное: ни в цели, ни в ограничениях нет ни квадратов, ни произведений переменных. Именно линейность делает задачу решаемой до конца — каждая граница на плоскости превращается в прямую, а нарисовать прямую вы умеете. Каждое неравенство вырезает из плоскости полуплоскость; пересечение всех четырёх полуплоскостей — область допустимых решений (ОДР):

Выпуклость не случайность, а теорема: пересечение полуплоскостей всегда выпуклое множество — вместе с любыми двумя своими точками оно содержит отрезок между ними. Вершины многоугольника — это решения систем уравнений из пар граничных прямых; пересечение $2x+y=12$ и $x+2y=12$ считается как обычная СЛАУ: удвоим первое, вычтем второе, получим $3x=12$, откуда $x=4$, $y=4$.

Линии уровня: куда двигать прибыль#

Зафиксируем прибыль: $40x+30y=F_0$. На плоскости это прямая, параллельная всем остальным линиям уровня — «карта высот» функции $F$. Прибыль растёт в направлении вектора $\vec{c}=(40,30)$, сокращённо $(4,3)$: это нормаль к линиям уровня, её направление связано со скалярным произведением — вдоль $\vec{c}$ функция растёт быстрее всего. Геометрический алгоритм решения:

1. Построить ОДР: по прямым-границам и полуплоскостям, с проверкой одной пробной точкой (обычно $(0,0)$).
2. Провести линию уровня $\vec{c}\cdot (x,y)=F_0$ для какого-нибудь $F_0$ — она перпендикулярна вектору $(4,3)$.
3. Сдвигать линию уровня параллельно себе в сторону $\vec{c}$ до последнего касания ОДР — у многоугольника это всегда вершина (или целое ребро).
4. Вычислить $F$ во всех кандидатных вершинах и выбрать максимум — проверка, которая защищает от ошибок рисунка.

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

Полное решение задачи о производстве#

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

Ошибки, которые меняют ответ#

• Вершина не из ОДР: посчитали пересечение прямых, но не проверили остальные неравенства. Точка $(0,12)$ — пересечение оси с первой прямой, но второе ограничение там нарушено; включить её в перебор — испортить ответ.
• Линия уровня сдвигается против нормали: получили максимум там, где прибыль минимальна. Всегда отмечайте $\vec{c}$ на чертеже стрелкой.
• Потерянная вершина: забыли осевые точки $(6,0)$ или $(0,6)$ — они тоже вершины ОДР, хотя на них не пересекаются две «наклонные» прямые.
• Арифметика пересечения: система из двух прямых решается в две строки, но знак минус при переносе — классическая потеря. Сверяйте пересечение подстановкой в оба уравнения.

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

Числовой прогон: цех делает столы и стулья, ресурс — 20 часов столярного времени и 18 часов покраски. Стол требует 2 и 3 часа, стул — 2 и 1 час; прибыль 6 и 5 тысяч. Ограничения: $2x+2y\le 20$, $3x+y\le 18$, целевая $6x+5y\to \max$. Вершины области: $(0,10)$, $(4,6)$, $(5,33;0)$, $(0,0)$. Значения целевой: 50, 54, 32 и 0 — оптимум в точке $(4,6)$: четыре стола и шесть стульев, прибыль 54 тысячи. Линия уровня $6x+5y=54$ в этой точке касается области последней — геометрия совпала с алгеброй.

Курс линейной алгебры на этом сайте пройден от первых операций с матрицами до оптимизации; возвращайтесь к любому уроку через хаб курса или тренируйте технику в тренажёре по матрицам. Если задача роста вам ближе по вероятностной части — переходите к цепям Маркова в курсе теории вероятностей.