Производственная задача
Пример производственной задачи
Как уже говорилось в предыдущем разделе, производственная задача состоит в следующем: Существует некоторое предприятие, которое может выпускать некоторые изделия. На то, чтобы их выпустить необходимы различные ресурсы. Задано, сколько и каких ресурсов необходимо для каждого изделия, задано сколько ресурсов у нас имеется, и задано, сколько предприятие выручит за продажу произведенных изделий. Необходимо выбрать, какие изделия и в каком количестве выпускать, чтобы прибыль предприятия была максимальной.
Приведем один из примеров производственной задачи:
Предприятие выпускает два вида изделий - 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{x_A}+3\cdot{x_B}$ единиц. Так как у нас 15 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 15: $1\cdot{x_A}+3\cdot{x_B}\leq15$
- Сколько всего потребуется ресурса R2? Для изделия A необходимы 2 единицы данного ресурса, а для изделия B - 1 единица. Всего, следовательно, необходимо $2\cdot{x_A}+1\cdot{x_B}$ единиц. Так как у нас 20 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 20: $2\cdot{x_A}+1\cdot{x_B}\leq20$
- Сколько всего потребуется ресурса R3? Для изделия A необходимы 3 единицы данного ресурса, а для изделия B - 2 единицы. Всего, следовательно, необходимо $3\cdot{x_A}+2\cdot{x_B}$ единиц. Так как у нас 35 единиц данного ресурса на складе, необходимо, чтобы это значение было не больше чем 35: $3\cdot{x_A}+2\cdot{x_B}\leq35$
- Мы не можем производить отрицательное количество изделий. Следовательно, $x_A,x_B\geq0$
- В итоге мы получаем 5 единиц прибыли за каждое изделие A и 10 единиц за каждое изделие B. Всего мы получаем прибыли $5\cdot{x_A}+10\cdot{x_B}$. Естественно, мы хотим максимизировать данную величину. Можно записать, что $F(x_A,x_B)=5\cdot{x_A}+10\cdot{x_B}\to{max}$
Итак, у нас получилась система ограничений и целевая функция следующего вида:
$$\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}$$Способы решения
Самым простым способом решить производственную задачу является графический способ (есть и другие, о которых поговорим в следующих главах). Данный способ, однако, имеет ограничение - им можно решить производственную задачу только для двух производимых изделий. Однако для нас это неважно, так как в нашем случае изделий как раз два - изделие A и изделие B.
