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

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

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

Предприятие выпускает два вида изделий — 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 получить? Непонятно.

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

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

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

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

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

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

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

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