Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

ББК 22.161 | Понятие математической модели. Математическая модель в задачах линейного программирования (ЛП) | Примеры задач ЛП | Графический метод решения задач ЛП | Приведение задач ЛП к стандартной форме | Порядок выполнения работ | Определение начального допустимого решения | Определение оптимального решения на основе симплекс-таблиц | Решение задач линейного программирования средствами табличного процессора Ехсеl | Анализ оптимального решения на чувствительность |


Читайте также:
  1. I. ЗАДАНИЯ ДЛЯ АУДИТОРНОЙ РАБОТЫ
  2. I. Итоговая государственная аттестация включает защиту бакалаврской выпускной квалификационной работы
  3. I. Цель работы
  4. I. Цель работы
  5. I. Цель работы
  6. I. Цель работы.
  7. I.3.1. Определение номенклатуры и продолжительности выполнения видов (комплексов) работ

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

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

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

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

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

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

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

20х1+5х2 ≤ 200

 

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

 

10х1+5х2≤ 250

 

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

1+20х2≤ 500

 

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

х1≥ 0, х2≥ 0.

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

Е=100х1+300х2→max

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

 

20х1+5х2≤ 200

10х1+5х2≤ 250(2.1)

1+20х2≤ 500

х1≥ 0, х2≥ 0

 

Е=100х1+300х2→max

 

Примечание. В данной задаче на переменные х1 и х2 накладывается также ограничение целочисленности: они должны принимать только целые значения, так как обозначают количество изделий. Если в результате решения задачи эти переменные примут дробные значения, то для получения целочисленного решения потребуется использовать специальные методы, рассматриваемые в лабораторной работе № 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х1+5х23=200

10х1+5х24=250 (2.2)

1+20х25=500

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

 

E=100х1+300х2→max

 

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

 


Дата добавления: 2015-07-21; просмотров: 208 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Теоретическое введение| Принцип работы симплекс-метода

mybiblioteka.su - 2015-2024 год. (0.007 сек.)