Производственная задача графический способ

Вспомним производственную задачу линейного программирования, решенную в предыдущем параграфе симплекс-методом.
Задача:

Предприятие выпускает 4 вида изделий, имея 3 группы оборудования. Нормы времени на обработку каждого изделия на каждой группе оборудования заданы матрицей А, фонд времени работы каждой группы оборудования задан матрицей В. Требуется составить такой план производства, при котором прибыль предприятия будет наибольшей.

Прибыль на единицу изделия соответствующей группы задана матрицей:

Результаты, полученные в предыдущем параграфе
Вывод: для максимальной выручки в размере 2196 следует выпускать продукцию первого типа в объеме 32 шт, второго типа – 20 шт., при этот остатки ресурсов третьего типа составят 8 единиц.

В оптимальной производственной программе

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

1)Построим граничные прямые и выберем соответствующие полуплоскости, приняв переменную за ординату, а
— за абсциссу.

— граничные прямые

— полуплоскости.

2) Целевая функция :

Построим вектор градиент

3) Проведем и сдвинем линию, перпендикулярную вектор градиенты, в направлении вектор-градиента до тех пор, пока она не станет опорной к области допустимых решений.

Точка пересечения прямой и области допустимых значений — точка пересечения прямых

Вывод: Это доказывает, что задача решена симплекс методом верно.

Источник

Графический способ решения производственной задачи

Условие

Сначала запишем условие производственной задачи из предыдущей главы:

Ресурс	Изделие A	Изделие B	Сколько ресурса на складах
R1	1	3	15
R2	2	1	20
R3	3	2	35
Прибыль	5	10

У нас получилась система ограничений и целевая функция следующего вида:

Строим область допустимых решений

Чтобы решить данную задачу линейного программирования графическим методом, необходимо сначала превратить (мысленно) все неравенства в равенства, и на время забыть про целевую функцию. То есть, получить следующую систему:

Мы получили пять уравнений с двумя переменными, следовательно, мы можем построить их графики. Например, мы можем направить ось с переменной $x_A$ вправо (где обычно у нас ось абсцисс) и ось с переменной $x_B$ вверх (где обычно у нас ось ординат). Для построения графиков нужно лишь выразить из этих уравнений $x_B$. Сделаем это:

Прежде чем строить графики, разберемся с последними двумя уравнениями, $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. При этом мы получим прибыль

Во всех остальных точках многоугольника решений прибыль будет меньше.

Другой способ

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

Найдем координаты каждой из них. Координаты точки 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$. И тогда придется строить трехмерный график, в котором запросто можно запутаться. А если переменных больше трех, то график не построить вообще. Однако специально для этих случаев был разработан еще один метод решения задач линейного программирования, и, в частности, производственной задачи — симплекс-метод, который мы рассмотрим в следующей главе.

Источник

Производственная задача

Пример производственной задачи

Как уже говорилось в предыдущем разделе, производственная задача состоит в следующем: Существует некоторое предприятие, которое может выпускать некоторые изделия. На то, чтобы их выпустить необходимы различные ресурсы. Задано, сколько и каких ресурсов необходимо для каждого изделия, задано сколько ресурсов у нас имеется, и задано, сколько предприятие выручит за продажу произведенных изделий. Необходимо выбрать, какие изделия и в каком количестве выпускать, чтобы прибыль предприятия была максимальной.

Приведем один из примеров производственной задачи:

Предприятие выпускает два вида изделий — A и B. Для их производства необходимо три вида ресурсов — R1, R2, R3. Для производства изделия A необходима 1 единица ресурса R1, 2 единицы ресурса R2 и 3 единицы ресурса R3. Для производства изделия B необходимо 3 единицы ресурса R1, 1 единицу ресурса R2 и 2 единицы ресурса R3. У предприятия на складе есть 15 единиц ресурса R1, 20 единиц ресурса R2 и 35 единиц ресурса R3. Сколько и каких изделий нужно выпустить предприятию, чтобы его прибыль была максимальной, если от продажи изделия A предприятие получает прибыль 5 рублей, а от продажи изделия B — 10 рублей.

Как мы говорили ранее, для таких задач найти какое-то решение найти очень просто. Так и в этом случае — это решение не производить ничего. То есть, произвести ноль изделий A и ноль изделий B. Прибыль, однако, также будет равна нулю. Все ограничения при этом выполнены — ресурсов на все хватит — ведь они даже не будут использованы.

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

Можно попытаться улучшить данное решение вручную. Например чуть-чуть увеличить план — выпустить по одному изделию A и B. При этом ресурса типа R1 понадобится $1+3=4$ штуки, ресурса типа R2 — $2+1=3$ штуки, и ресурса типа R3 — $3+2=5$ штук. Каждого из ресурсов нам хватит, так как их понадобилось меньше, чем есть у нас на складе. И тогда мы получим прибыль $1\cdot5+1\cdot10=15$ рублей.

Это решение, очевидно, лучше предыдущего, так как значение прибыли (целевая функция) уже больше нуля — 15 рублей. Однако можно видеть, что на складах останется еще много ресурсов, а из них можно было бы сделать еще больше изделий, и заработать еще больше.

Можно перебирать вручную и дальше, но во-первых, количество перебираемых вариантов огромно, а во-вторых, мы так никогда и не узнаем — лучший наш вариант или нет. Вот, например, мы получили прибыль в 45 рублей — это хорошо? Или можно и 75 получить? Непонятно.

Табличная запись задачи

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

Ресурс	Изделие A	Изделие B	Сколько ресурса на складах
R1	1	3	15
R2	2	1	20
R3	3	2	35
Прибыль	5	10

Эта задача абсолютно совпадает с той, которая приведена в начале данного раздела. Например, на пересечении строки R3 и столбца «Изделие B» записано «2» — именно столько единиц ресурса R3 требуется на производство одной единицы изделия B. В последней строке пишется прибыль от продажи каждого изделия, а в последнем столбце — количество каждого ресурса на складах.

Формализация задачи

А теперь попробуем записать систему ограничений нашей задачи и целевую функцию в виде неравенств. Обозначим за $x_A, x_B$ количество производимых изделий A и B, соответственно.

• Сколько всего потребуется ресурса R1? Для изделия A необходима 1 единица данного ресурса, а для изделия B — 3 единицы. Всего, следовательно, необходимо $1\cdot+3\cdot$ единиц. Так как у нас 15 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 15: $1\cdot+3\cdot\leq15$
• Сколько всего потребуется ресурса R2? Для изделия A необходимы 2 единицы данного ресурса, а для изделия B — 1 единица. Всего, следовательно, необходимо $2\cdot+1\cdot$ единиц. Так как у нас 20 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 20: $2\cdot+1\cdot\leq20$
• Сколько всего потребуется ресурса R3? Для изделия A необходимы 3 единицы данного ресурса, а для изделия B — 2 единицы. Всего, следовательно, необходимо $3\cdot+2\cdot$ единиц. Так как у нас 35 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 35: $3\cdot+2\cdot\leq35$
• Мы не можем производить отрицательное количество изделий. Следовательно, $x_A,x_B\geq0$
• В итоге мы получаем 5 единиц прибыли за каждое изделие A и 10 единиц за каждое изделие B. Всего мы получаем прибыли $5\cdot+10\cdot$. Естественно, мы хотим максимизировать данную величину. Можно записать, что $F(x_A,x_B)=5\cdot+10\cdot\to$

Итак, у нас получилась система ограничений и целевая функция следующего вида:

Способы решения

Самым простым способом решить производственную задачу является графический способ (есть и другие, о которых поговорим в следующих главах). Данный способ, однако, имеет ограничение — им можно решить производственную задачу только для двух производимых изделий. Однако для нас это неважно, так как в нашем случае изделий как раз два — изделие A и изделие B.

Источник