Как решить задачу линейного программирования: разбор

Дано. Цех выпускает два изделия. На одно изделие A уходит 2 кг сырья и 4 станко-часа, на изделие B - 3 кг сырья и 2 станко-часа. За смену доступно 18 кг сырья и 20 станко-часов. Прибыль составляет 3 тыс. руб. с изделия A и 4 тыс. руб. с изделия B.

Найти: план выпуска, при котором прибыль максимальна.

Переменных всего две, поэтому задачу можно решить дважды и сверить ответы: графическим методом на плоскости и симплекс-методом по таблицам. Ответ: выпускать 3 изделия A и 4 изделия B, прибыль 25 тыс. руб., причём оба ресурса расходуются полностью. Калькулятор сверху пересчитывает область, её вершины и путь симплекса под любые свои нормы расхода, запасы и цены.

Решение по шагам

Шаг 1. Математическая модель. Обозначаем через $x_1$ число изделий A, через $x_2$ - число изделий B. Прибыль складывается из вкладов обоих изделий, её и максимизируем:

$$F = 3x_1 + 4x_2 \to \max.$$

Каждый ресурс даёт по одному неравенству: расход не может превысить запас. Плюс переменные неотрицательны, отрицательный выпуск смысла не имеет.

$$\begin{cases} 2x_1 + 3x_2 \le 18, \\ 4x_1 + 2x_2 \le 20, \\ x_1 \ge 0, \quad x_2 \ge 0. \end{cases}$$

Шаг 2. Область допустимых решений. Каждое неравенство задаёт полуплоскость, граница которой - прямая. Прямую удобнее всего строить по точкам пересечения с осями: подставляем поочерёдно $x_1 = 0$ и $x_2 = 0$.

$$\begin{aligned} 2x_1 + 3x_2 = 18: \; & (9;\,0) \text{ и } (0;\,6), \\ 4x_1 + 2x_2 = 20: \; & (5;\,0) \text{ и } (0;\,10). \end{aligned}$$

Какую из двух полуплоскостей брать, показывает пробная точка. Подставляем начало координат: $0 \le 18$ и $0 \le 20$ - оба неравенства верны, значит нужные полуплоскости лежат со стороны нуля. Их пересечение с первой четвертью и есть область допустимых решений: на графике сверху это залитый четырёхугольник.

Шаг 3. Вершины области. Три вершины видны сразу: начало координат $O(0;\,0)$, точка $A(5;\,0)$ на оси $x_1$ и точка $C(0;\,6)$ на оси $x_2$. Обратите внимание, что на оси $x_1$ границей служит вторая прямая, а не первая: точка $(9;\,0)$ лежит на прямой сырья, но нарушает ограничение по станко-часам, ведь $4 \cdot 9 = 36 > 20$.

Четвёртая вершина $B$ - пересечение двух прямых. Решаем систему подстановкой: из второго уравнения $x_2 = 10 - 2x_1$, подставляем в первое.

$$2x_1 + 3(10 - 2x_1) = 18 \; \Rightarrow \; -4x_1 = -12 \; \Rightarrow \; x_1 = 3, \quad x_2 = 4.$$

Если прямых больше двух, такие системы удобно гонять единообразно - например, методом Гаусса, он не запутается в знаках при любом числе уравнений.

Шаг 4. Перебор вершин. Считаем значение целевой функции в каждой вершине и выбираем наибольшее.

Шаг 5. Проверка линией уровня. Уравнение $3x_1 + 4x_2 = \text{const}$ задаёт семейство параллельных прямых. Смещать их надо в направлении вектора $c = (3;\,4)$ - это градиент целевой функции, направление её самого быстрого роста. Последняя точка области, которой касается уходящая линия уровня, и есть оптимум: здесь это вершина $B$. Перебор вершин и линия уровня дали одно и то же, значит арифметика сошлась.

Ответ: $x_1 = 3$, $x_2 = 4$, $F_{\max} = 25$ тыс. руб. Расход сырья $2 \cdot 3 + 3 \cdot 4 = 18$ кг, расход станко-часов $4 \cdot 3 + 2 \cdot 4 = 20$ ч: оба ресурса выбраны под ноль.

Канонический вид и симплекс-таблица

Графика хватает только для двух переменных. Универсальный инструмент - симплекс-метод, и начинается он с перевода неравенств в равенства. К левой части каждого ограничения добавляют неотрицательную балансовую переменную, которая и есть неиспользованный остаток ресурса:

$$\begin{cases} 2x_1 + 3x_2 + x_3 = 18, \\ 4x_1 + 2x_2 + x_4 = 20, \end{cases} \qquad x_j \ge 0.$$

Переменные $x_3$ и $x_4$ дают готовый начальный базис: если ничего не выпускать, весь ресурс лежит в остатке. Заполняем таблицу. В столбце $C_{\text{б}}$ стоят коэффициенты целевой функции при базисных переменных, а нижняя строка - оценки $\Delta_j = \sum C_{\text{б}} a_{ij} - c_j$.

Критерий оптимальности для задачи на максимум: план оптимален, когда все оценки неотрицательны. Здесь есть отрицательные, значит план улучшаем. Разрешающий столбец - с самой отрицательной оценкой, это $x_2$. Разрешающую строку выбирают по минимальному отношению свободного члена к положительному элементу этого столбца: $\min(6;\,10) = 6$, уходит $x_3$. Разрешающий элемент равен 3, делим на него всю строку и обнуляем остальные элементы столбца.

План стал лучше: $F = 24$, но оценка $\Delta_1 = -1/3$ всё ещё отрицательна. Вводим $x_1$, минимальное отношение равно 3, выводим $x_4$, разрешающий элемент $8/3$.

Все оценки неотрицательны - критерий выполнен, дальше улучшать нечего. Из таблицы читаем базисный план: $x_1 = 3$, $x_2 = 4$, $F_{\max} = 25$. Тот же ответ, что и на графике. Переключатель в калькуляторе сверху рисует путь метода по вершинам: симплекс стартовал из $O(0;\,0)$, шагнул в $C(0;\,6)$ и закончил в $B(3;\,4)$, ни разу не заглянув внутрь области.

Числа $5/4$ и $1/8$ в оценках балансовых столбцов - не мусор, а двойственные оценки ресурсов: килограмм сырья сверх запаса добавил бы 1,25 тыс. руб. прибыли, лишний станко-час - 0,125 тыс. руб. Проверка сходится: $18 \cdot 5/4 + 20 \cdot 1/8 = 25$. Откуда берётся это равенство и что оно гарантирует, разобрано в статье про теорему двойственности.

Почему оптимум всегда в вершине

Целевая функция линейна, а область допустимых решений - выпуклый многогранник. Линии уровня линейной функции параллельны, и при сдвиге в сторону градиента последняя точка контакта с выпуклым множеством не может оказаться внутри области: изнутри всегда есть куда сдвинуться дальше. Значит максимум достигается на границе, а на границе - в вершине.

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

Отдельный случай - когда линия уровня параллельна одной из граничных прямых. Тогда оптимальна вся сторона многоугольника, и решений бесконечно много. Проверить легко: поставьте в калькуляторе прибыли 2 и 3 - вектор $c = (2;\,3)$ станет параллелен прямой сырья, и вершины $B$ и $C$ дадут одинаковое значение 18. В симплекс-таблице это видно по нулевой оценке у небазисной переменной.

Если задача поставлена иначе

Минимум вместо максимума. Задача $F \to \min$ равносильна $-F \to \max$, поэтому можно поменять знаки коэффициентов и работать по тому же алгоритму. Графически линию уровня двигают против градиента, в симплексе меняют критерий: план оптимален, когда все оценки неположительны.

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

Больше двух переменных. Плоскости уже не хватает, остаётся симплекс-таблица: трудоёмкость растёт по числу строк, но вручную метод остаётся рабочим.

Особая структура задачи. Если ограничения описывают перевозки от поставщиков к потребителям, симплекс избыточен: у такой задачи есть свой экономный алгоритм, разобранный в решении транспортной задачи.

Дробный ответ. Здесь план вышел целым по построению условия, но в общем случае симплекс выдаёт дроби. Округлять их нельзя: округлённая точка либо выходит за границу области, либо перестаёт быть оптимальной. Нужны целочисленные методы - ветвей и границ или отсечения Гомори.

Частые ошибки

• Ставка на «самое выгодное» изделие. Прибыль от B выше, но если гнать только B, сырья хватит на 6 штук и прибыль составит 24 тыс. руб. - меньше оптимальных 25. Смесь выгоднее чистой стратегии.
• Точка пересечения с осью принимается за вершину. Точка $(9;\,0)$ лежит на первой прямой, но нарушает второе ограничение и в область не входит. Каждую кандидатную вершину надо подставлять во все неравенства.
• Неравенства подставляют в симплекс без канонизации. Балансовые переменные добавляют до заполнения таблицы, причём с коэффициентом $+1$ и с нулевым коэффициентом в целевой функции.
• Отношение считают по всем элементам разрешающего столбца. В расчёт идут только строго положительные элементы; нули и отрицательные пропускают, иначе метод уведёт в недопустимый план.
• Расчёт останавливают на первой неотрицательной оценке. Проверять нужно всю строку $\Delta_j$ целиком: одна отрицательная оценка среди прочих неотрицательных означает, что итерация ещё нужна.
• Забытое условие неотрицательности. Без $x_j \ge 0$ область перестаёт быть многоугольником в первой четверти, и ответ уезжает в отрицательный выпуск.

FAQ

Когда графический метод работать не будет? Он применим строго при двух переменных, изредка при трёх с построением в пространстве. Как только переменных больше, область не нарисовать, и остаётся симплекс-метод. Число ограничений роли не играет.

Что означает пустая область допустимых решений? Ограничения противоречат друг другу, допустимых планов нет вообще. На чертеже полуплоскости не имеют общей части, в симплексе искусственные переменные остаются в базисе с ненулевым значением. Обычно виноват знак неравенства или опечатка в правой части.

Может ли задача не иметь максимума? Да, если область не ограничена в направлении роста целевой функции. Тогда линию уровня можно двигать бесконечно, а в симплекс-таблице появится разрешающий столбец без единого положительного элемента - это признак неограниченности.

Обязательно ли ответ будет целым? Нет. Симплекс работает с непрерывными переменными и спокойно выдаёт дробные объёмы выпуска. Целочисленность - отдельное требование, которое решается методом ветвей и границ, а не округлением дробного ответа.

Коротко

1. Записать модель: переменные, целевую функцию, ограничения по ресурсам и условие неотрицательности.
2. При двух переменных построить прямые по точкам пересечения с осями, выделить пробной точкой полуплоскости и получить область допустимых решений.
3. Найти координаты вершин, посчитать в них $F$ и выбрать наибольшее значение; направление сдвига проверить градиентом.
4. Для общего случая привести задачу к каноническому виду балансовыми переменными и вести симплекс-таблицы, пока все оценки $\Delta_j$ не станут неотрицательными.
5. Для условия смены: $x_1 = 3$, $x_2 = 4$, $F_{\max} = 25$ тыс. руб., оба ресурса израсходованы полностью, двойственные оценки равны $5/4$ и $1/8$.