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

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

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

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

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

Источник

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

Условие

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

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

Источник

Решение производственной задачи табличным симплекс-методом

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

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

Решение задачи табличным симплекс-методом

Решение задачи происходит в несколько последовательных этапов. Разберем их на небольшом примере производственной задачи.

1. Определение исходных данных

В нашем примере, по условиям задачи предприятие выпускает 4 вида изделий, обрабатывая их на 3 станках.

Исходные данные для производственной задачи запишем в формате матриц :

• Матрица A — нормы времени на обработку изделий;
• Матрица B — фонд времени работы станков;
• Матрица C — продажи производимых изделий.

Таким образом, нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:

Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:

Кроме того, обозначим через X_i планируемое количество изделий каждого вида. Тогда искомый план: X₁, X₂, X₃, X₄.

2. Запись ограничений плана в виде системы неравенств

Запишем ограничения плана в виде системы неравенств:

Коэффициенты при переменных в левой части системы неравенств берем из матрицы A, значения из правой части — из матрицы B.

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

Также добавляем условие, согласно которому переменные не могут быть меньше нуля, так как произвести отрицательное количество изделий невозможно.

3. Определение целевого показателя

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

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

Коэффициенты при переменных берем из матрицы C. То есть мы перемножаем прибыль от производства единицы изделия каждого вида на их планируемое количество, для получения значения суммарной прибыли (которая должна быть максимальной).

4. Приведение системы неравенств к системе линейных уравнений

Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X₅, X₆, X₇).

Эти переменные являются фиктивными изделиями, на которые мы списываем неиспользованные остатки фондов времени работы станков.

5. Формирование опорного плана

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

Здесь основным переменным (количеству изделий производимых в рамках плана) сопоставляем нулевые значения, а дополнительным (фиктивным) переменным — соответствующие величины фондов времени работы станков.

6. Составление симплекс-таблицы

Занесем исходные данные в специальную симплекс-таблицу.

В столбец Базис выписываем дополнительные переменные (X₅..X₇). В колонку H вносим величины фонда времени работы станков. В столбцы X₁..X₇ помещаем коэффициенты при этих переменных из составленной ранее системы уравнений (если переменных в уравнении нет, как например, X₆ и X₇ в первом равенстве, то коэффициенты будут равны 0). Кроме того, следует предусмотреть дополнительный столбец (b) для показателя, который мы будем рассчитывать на следующем этапе.

Количество строк в таблице соответствует числу дополнительных переменных (X₅..X₇). В последнюю строку (c) заносим коэффициенты при целевой функции с обратным знаком (коэффициенты при дополнительных переменных X₅..X₇ будут нулевыми).

7. Вычисление показателя b

Выбираем в последней строке наибольшее (по модулю!) отрицательное число.

В нашем примере это -48 (еще раз подчеркнем, что отрицательные числа сравниваем без учета знака).

Далее вычислим для столбца, которому соответствует выбранное число, специальный показатель b_i = Н_i / a_i, где a_i — значение ячейки выбранного столбца и соответствующей строки.

8. Нахождение разрешающего элемента

Среди вычисленных значений b выбираем наименьшее.

Пересечение выбранных столбца и строки даст нам разрешающий элемент (РЭ). Меняем базисную переменную (из первой колонки в выбранной строке) на переменную соответствующую разрешающему элементу (X₅ на X₁).

9. Перерасчет элементов симплекс-таблицы

Теперь необходимо пересчитать все элементы симплекс-таблицы, кроме столбца b (который очищается).

При перерасчете элементов симплекс-таблицы следует придерживаться следующих правил:

• Сам разрешающий элемент (РЭ) обращается в единицу;
• Для элементов разрешающей строки применяется формула: a_ij * = a_ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные);
• Для элементов разрешающего столбца — они просто обнуляются;
• Остальные элементы таблицы пересчитываем по правилу прямоугольника:

Формула здесь следующая: a_ij * = a_ij — ( A × B / РЭ )

Как видите, мы берем пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A × B) делим на разрешающий элемент (РЭ) и вычитаем из текущей пересчитываемой ячейки (a_ij) то, что получилось. В итоге имеем новое значение — a_ij * .

Полученные в результате перерасчета значения заносим в новую симплекс-таблицу:

10. Проверяем последнюю строку симплекс-таблицы на наличие отрицательных чисел: если их нет — оптимальный план найден (п. 11), если есть — план требует улучшения (п. 7)

Вновь проверяем последнюю строку (c) на наличие отрицательных чисел. Если их нет — оптимальный план найден, переходим к последнему этапу решения задачи (пункт 11). Если есть — план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.

Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию (повторение) вычислений с пункта 7.

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

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

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

11. Определение производственного плана и вычисление общей прибыли

В соответствии с найденным планом (смотрим какие переменные перешли в колонку «Базис») выпускать мы будем изделия X₁ и X₂ (X₇ не учитываем, т. к. это фиктивное изделие, не производимое на предприятии и введенное для приведения системы неравенств к системе уравнений).

Прибыль от производства каждой единицы продукции нам известна (матрица C). Остается перемножить ее с найденными объемами выпуска изделий X₁ и X₂ (значения X₃ и X₄ нулевые, т. к. эти изделия производить оказалось невыгодно), для получения общей (максимально возможной!) прибыли.

Ответ План производства: X₁ = 32 шт., X₂ = 20 шт., X₃ = 0 шт., X₄ = 0 шт., общая прибыль: P = 48 × 32 + 33 × 20 = 2 196 руб.

1. Галяутдинов Р. Р. Курс лекций по логистике
2. Симплекс-метод // Википедия. URL: http://ru.wikipedia.org/wiki/Симплекс-метод (дата обращения: 25.11.2013)

© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.

Источник