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

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

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

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

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

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

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

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

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

Для производства двух видов продукции А и В предприятие использует 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 гривен - с одной штуки продукции В.

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

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

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

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 единиц, потом он перестанет быть дефицитным, значит, не будет влиять на оптимальное решение.