Графический способ решения производственной задачи
Условие
Сначала запишем условие производственной задачи из предыдущей главы:
| Ресурс | Изделие A | Изделие B | Сколько ресурса на складах |
| R1 | 1 | 3 | 15 |
| R2 | 2 | 1 | 20 |
| R3 | 3 | 2 | 35 |
| Прибыль | 5 | 10 |
У нас получилась система ограничений и целевая функция следующего вида:
$$\begin{array}{l} \left\{ {\begin{array}{*{20}{c}} {{x_A} + 3{x_B} \le 15}\\ {2{x_A} + {x_B} \le 20}\\ {3{x_A} + 2{x_B} \le 35} \end{array}} \right.\\ {x_A},{x_B} \ge 0\\ F({x_A},{x_B}) = 5{x_A} + 10{x_B} \to \max \end{array}$$Строим область допустимых решений
Чтобы решить данную задачу линейного программирования графическим методом, необходимо сначала превратить (мысленно) все неравенства в равенства, и на время забыть про целевую функцию. То есть, получить следующую систему:
$$\left\{ {\begin{array}{*{20}{c}} {{x_A} + 3{x_B} = 15}\\ {2{x_A} + {x_B} = 20}\\ {3{x_A} + 2{x_B} = 35}\\ {{x_A} = 0}\\ {{x_B} = 0} \end{array}} \right.$$Мы получили пять уравнений с двумя переменными, следовательно, мы можем построить их графики. Например, мы можем направить ось с переменной $x_A$ вправо (где обычно у нас ось абсцисс) и ось с переменной $x_B$ вверх (где обычно у нас ось ординат). Для построения графиков нужно лишь выразить из этих уравнений $x_B$. Сделаем это:
$$\left\{ {\begin{array}{*{20}{c}} {3{x_B} = 15 - {x_A}}\\ {{x_B} = 20 - 2{x_A}}\\ {2{x_B} = 35 - 3{x_A}}\\ {{x_A} = 0}\\ {{x_B} = 0} \end{array}} \right.$$ $$\left\{ {\begin{array}{*{20}{c}} {{x_B} = 5 - \frac{1}{3}{x_A}}\\ {{x_B} = 20 - 2{x_A}}\\ {{x_B} = 17,5 - 1,5{x_A}}\\ {{x_A} = 0}\\ {{x_B} = 0} \end{array}} \right.$$Прежде чем строить графики, разберемся с последними двумя уравнениями, $x_A=0$ и $x_B=0$. Эти уравнения выражают сами оси - абсцисс и ординат. А так как в исходных ограничениях были неравенства $x_A\geq0$ и $x_B\geq0$, то точка нашего решения должна быть правее и выше, чем эти оси - то есть, находиться в первой четверти. Поэтому эти две линии можно не строить, а просто учитывать, что решение в первой четверти.
Остальные линии мы построим на графике, и получим следующую картину (естественно, на нормальном графике не нужно рисовать такие стрелки, они лишь для наглядности, чтобы не перепутать линии друг с другом):
Каждая из этих линий разбивает область допустимых решений на две - одна находится правее и выше каждой из этих линий, вторая - левее и ниже. Какая из них нужна нам? Та, которая левее и ниже. Во-первых, в исходных неравенствах у нас был знак "меньше или равно", а левее и ниже как раз более маленькие значения переменных. А во-вторых, как мы говорили в предыдущем пункте, решение (0,0) вполне удовлетворяет условию задачи, хоть и не является оптимальным. А точка (0,0) - начало координат - расположена как раз левее и ниже каждой из прямых.
То есть, нам нужно найти область, расположенную левее и ниже, чем каждая из наших прямых. Отобразим ее:
Эта область, во-первых, расположена в первой четверти, как и должно быть, во-вторых, левее и ниже прямых $x_B=5-\frac{1}{3}x_A$ и $x_B=20-2x_A$. Прямая $x_B=17,5-1,5x_A$ оказалась не участвующей в решении, так иногда бывает, это не страшно.
Далее задачу можно решать двумя способами.
Основной способ
Рассмотрим первый из них. Для него нужно нарисовать линию нулевого дохода, то есть, линию, при которой целевая функция равна нулю: $5x_A+10x_B=0$. Если упростить данное выражение, получим $x_B=-0,5x_A$. Построим эту функцию красным цветом, и уберем подписи. Она будет расположена не в первой четверти, это нормально.
Эта линия состоит из точек, каждая из которых является решением, применяя которое, мы получим нулевой доход. Однако с тем условием, что $x_A,x_B\geq0$, такое решение мы получаем всего одно - в точке (0,0) - остальные точки лежат во второй и четвертой четверти.
Что будет, если эту линию поднимать выше (параллельным переносом)? Мы получим линии, которые будут давать больший, чем 0 доход. Получается, чем выше мы поднимем данную линию, тем лучше. Однако совсем до бесконечности поднимать ее не получится, ведь она должна хотя бы касаться разрешенной области, обозначенной серым цветом (сейчас она касается только в точке (0,0)). Попробуем провести (пока на глаз) линии, параллельные данной, через оставшиеся три точки многоугольника:
Мы нарисовали еще две линии, параллельные линии нулевого дохода, но расположенные выше. Средняя из них проходит через две точки нашего многоугольника с решениями, а самая высокая - через еще одну точку многоугольника. Кроме того, она вообще пересекает наш многоугольник в одной-единственной точке. И еще выше данную линию поднять нельзя - она вообще перестанет пересекать наш многоугольник. Следовательно, эта линия и есть "линия максимального дохода", а наше решение находится, как раз, в той точке, в которой эта линия пересекает нашу область допустимых решений - в точке пересечения линий $x_B=5-\frac{1}{3}x_A$ и $x_B=20-2x_A$. Найдем координаты данной точки. Для этого приравняем эти два значения для $x_B$:
$$5-\frac{1}{3}x_A=20-2x_A$$ $$-\frac{1}{3}x_A+2x_A=20-5$$ $$\frac{5}{3}x_A=15$$ $$5x_A=45$$ $$x_A=9$$ $$x_B=20-2\cdot9=20-18=2$$Итак, наше решение находится в точке (9,2). Это означает, что необходимо производить 9 единиц изделия A и 2 единицы изделия B. При этом мы получим прибыль
$$F(x_A,x_B)=5\cdot9+10\cdot2=45+20=65$$Во всех остальных точках многоугольника решений прибыль будет меньше.
Другой способ
Второй способ заключается в том, что нужно просто проверить значение целевой функции в каждой точке многоугольника. Всего их четыре. Обозначим их буквами:
Найдем координаты каждой из них. Координаты точки O мы знаем - (0,0). Координаты точки B мы нашли выше (по первому способу) - (9,2). Точка A - это точка на прямой $x_B=5-\frac{1}{3}x_A$, причем $x_A=0$. Следовательно $x_B=5$. То есть, ее координаты (0,5). Точка C - это точка на прямой $x_B=20-2x_A$, причем $x_B=0$. То есть, $20-2x_A=0$, $2x_A=20$, $x_A=10$. Следовательно, ее координаты (10,0).
Теперь найдем значение целевой функции в каждой из данных точек:
$$F(O)=F(0,0)=5\cdot0+10\cdot0=0+0=0$$ $$F(A)=F(0,5)=5\cdot0+10\cdot5=0+50=50$$ $$F(B)=F(9,2)=5\cdot9+10\cdot2=45+20=65$$ $$F(C)=F(10,0)=5\cdot10+10\cdot0=50+0=50$$Действительно, в точке B наша функция принимает максимальное значение, равное 65. Это и есть максимальная прибыль, которую можно получить в данном случае.
А если товаров больше?
Как говорилось в предыдущем разделе, графическим способом можно решать только задачу для двух производимых товаров. Это потому, что если товаров будет больше двух, то и переменных будет больше двух, например, три - $x_A, x_B, x_C$. И тогда придется строить трехмерный график, в котором запросто можно запутаться. А если переменных больше трех, то график не построить вообще. Однако специально для этих случаев был разработан еще один метод решения задач линейного программирования, и, в частности, производственной задачи - симплекс-метод, который мы рассмотрим в следующей главе.
Далее: 2.1.1. Симплексный способ решения
