Методика выполнения работы. 2.2.2.1 Пример задачи линейного программирования: задача планирования производства

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

Одной из наиболее распространенных практических задач, решаемых методами линейного программирования, является задача планирования производства при ограниченных ресурсах. Основной метод решения задач линейного программирования – симплекс-метод – будет рассмотрен на примере решения такой задачи.

Пример 2.1. Один из цехов машиностроительного предприятия выпускает изделия из двух видов: корпуса и задвижки. Для производства этих изделий требуются три вида сырья: алюминий, сталь и пластмасса. На выпуск одного корпуса расходуется 20 кг алюминия, 10 кг стали и 5 кг пластмассы. На выпуск одной задвижки расходуется 5 кг алюминия, 5 кг стали и 20 кгпластмассы. Запасы ресурсов ограничены: за рабочую смену цех может израсходовать не более 200 кг алюминия, 250 кг стали и 500 кг пластмассы.

Выпуск одного корпуса приносит предприятию прибыль в размере 100 денежных единиц (ден. ед.), одной задвижки – 300 ден. ед.

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

Для построения математической модели задачи введем переменные. Обозначим через х₁ количество выпускаемых корпусов, через х₂ - количество выпускаемых задвижек.

Составим ограничение на расход алюминия. На выпуск одного корпуса расходуется 20 кг алюминия: значит, расход алюминия на выпуск всех корпусов составит 20х₁ кг. На выпуск задвижек будет израсходовано 5х₂ кг алюминия. Таким образом, общий расход алюминия составит 20х₁ + 5х₂ кг Эта величина не должна превышать 200 кг, так как цех не может израсходовать за смену свыше 200 кг алюминия. Поэтому можно записать следующее ограничение:

20х₁+5х₂ ≤ 200

Аналогично можно составить ограничение на расход стали:

10х₁+5х₂≤ 250

и на расход пластмассы:

5х₁+20х₂≤ 500

Кроме того, переменные х₁ и х₂ по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество изделий. Поэтому необходимо указать ограничения неотрицательности:

х₁≥ 0, х₂≥ 0.

В данной задаче требуется определить количество выпускаемых изделий, при котором прибыль от их производства будет максимальной. Прибыль от выпуска одного корпуса составляет 100 ден. ед.: значит, прибыль от выпуска корпусов составит 100х₁ ден. ед. Прибыль от выпуска задвижек составит 300х₂ ден. ед. Таким образом, общая прибыль от выпуска всех изделий составит 100х₁+300х₂ ден. ед. Требуется найти такие значения переменных х₁ и х₂ при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

Е=100х₁+300х₂→max

Приведем полную математическую модель рассматриваемой задачи:

20х₁+5х₂≤ 200

10х₁+5х₂≤ 250(2.1)

5х₁+20х₂≤ 500

х₁≥ 0, х₂≥ 0

Е=100х₁+300х₂→max

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

Эту задачу можно решить также графическим методом. Решение показано на рис. 2.1.

Рис. 2.1. Решение примера 2.1 графическим методом

Найдем значения целевой функции для угловых точек ОДР:

Е(О) = 100*0+300*0 = 0,

Е(А) = 100*0 +300*25 = 7500,

Е(В) = 100*4 +300*24 = 7600,

Е(С) = 100*10+300*0 = 1000.

Таким образом, оптимальное решение находится в точке В = (4;24). Это означает, что цех должен выпускать за смену 4 корпуса и 24 задвижки. Прибыль при этом составит 7600 ден. ед.

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

Для решения задачи симплекс-методом требуется привести ее к стандартной форме, как показано в подразделе 1.2.2.3. Все ограничения задачи имеют вид «меньше или равно». Их необходимо преобразовать в равенства. Для этого требуется добавить в каждое ограничение дополнительную (остаточную) переменную. Математическая модель задачи в стандартной форме будет иметь следующий вид:

20х₁+5х₂+х₃=200

10х₁+5х₂+х₄=250 (2.2)

5х₁+20х₂+х₅=500

х_j≥ 0, j=1,…,5.

E=100х₁+300х₂→max

Здесь х₃,х₄,х₅- остаточные переменные. Их физический смысл будет показан в п. 2.2.2.4.

Дата добавления: 2015-07-21