Рефераты → Информатика, программирование → Гр → Графический метод решения задач линейного программирования

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

Министерство науки и образования Украины


Днепропетровский Национальный Университет


Факультет электроники, телекоммуникаций и компьютерных систем


Кафедра автоматизированных систем обработки информации


Расчётная работа №1


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


Выполнил: ст. гр. РС-05,


Паляруш А.Б.


Проверил:


Доцент кафедры АСОИ


Саликов В.А


Г. Днепропетровск


2007 г.


Постановка задачи


Для производства двух видов продукции А и В предприятие использует 4 группы оборудования (1, 2, 3, 4) на производство одной штуки продукции А требуется занять в течение рабочей смены 1, 0, 5 и 3 единиц соответственно 1, 2, 3, 4 оборудования, а на производство одной штуки продукции В требуется 1, 1, 0, 2 единиц оборудования 1, 2, 3, 4. Имеется оборудование по группам 1 – 18, 2 – 12, 3 – 24, 4 – 18 единиц. Предприятие получает с одной штуки продукции А 4 гривны чистого дохода и 6 гривен - с одной штуки продукции В.


Сколько штук продукции каждого вида должно производить предприятие, чтобы получить наибольшую прибыль?
























Группа оборудования, штук для производства единицы продукции Прибыль, грн
1 2 3 4
А 1 0 5 3 4
В 1 1 0 2 6

Построение математической модели

Для реализации графического метода решения задач линейного программирования необходимо определить целевую функцию:


Z=4*x1+6*x2, где Z→max – целевая функция,


x1 – количество изготовленной продукции вида А,


x2 – количество изготовленной продукции вида В.


Далее необходимо определить ограничения, задающие ОДР:


>

(1) x1+ x2 ≤ 18; вытекает из доступного количества оборудования первой группы


(2) x2 ≤ 12; вытекает из доступного количества оборудования второй группы


(3) 5*x1 ≤ 24; вытекает из доступного количества оборудования третей группы


(4) 2*x1+2*x2 ≤ 18;вытекает из доступного количества оборудования четвёртой группы


(5) x1 ≥ 0;условие неотрицательности;


(6) x2 ≥ 0 ; условие неотрицательности;


Построим все полученные ограничения и целевую функцию:




Теперь можно увидеть, что ОДР ограничена (4) x1+x2 ≤ 9, (3) x1 ≤ 4.8, x1 ≤ 0, x2≤ 0.


Наилучшее (оптимальное) решение отмечено красным крестиком. Максимальная прибыль достигается в точке (0, 9), А=0, В=9; при нахождении оптимального решения данной задачи следует помнить, что количество продукции (равно как и количество ресурса) целое число.


Z(0,9)=4*0+9*6=54 (грн).


Чувствительность модели

Благодаря исследованию чувствительности модели, мы получаем информацию о ценности ресурса.


Оборудование группы 1 (голубой цвет на графике) не является дефицитным и не влияет на оптимальную точку т.к. вышло далеко за ОДР, его очень много. Это оборудование станет дефицитным при уменьшении его количества на 9 единиц.


Оборудование группы 2 (зелёный цвет на графике) так же не является дефицитным, однако, при уменьшении его количества на 3 единицы оно начнёт влиять на результат.


Оборудование группы 3 (синий цвет на графике) не дефицитно. Изменяя его количество, при неизменном количестве других ресурсов, мы не повлияем на результат т.к. для производства продукции А (именно она должна производиться для максимальной прибыли) его расход равен 0.


Оборудование группы 4 (чёрный цвет на графике) является дефицитным, ценность данного ресурса можно определить, увеличив его количество на 2 единицы (т.к. именно столько необходимо для производства одной единицы продукции А):



Следовательно, при изменении количества ресурса 4 на единицу прибыль растёт на 3 гривны. Данный ресурс можно увеличивать до 24 единиц, потом он перестанет быть дефицитным, значит, не будет влиять на оптимальное решение.
Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Графический метод решения задач линейного программирования

Слов:532
Символов:4781
Размер:9.34 Кб.