2018-02-13
586
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Им. Н.И. ЛОБАЧЕВСКОГО
В.А. Рябинин
Решение оптимизационной задачи линейного программирования
Лабораторная работа №1
Нижний Новгород
2005
1. Содержательное описание
В полиграфическую фирму во время предвыборной кампании поступил заказ на изготовление листовок и плакатов. Известно, что для печати 1-ой листовки требуется 1мл цветной краски, 1 мл черной и 1 лист формата А4. Для печати 1-ого плаката необходимо израсходовать 3 мл цветной краски, 1 мл черной и 1 лист формата А3. Запасы краски и бумаги на фирме ограничены: цветной краски 1800 мл, черной 1000 мл и лента бумаги на 1500 листов формата А4. За каждую листовку заказчик выплачивает 2 рубля, за каждый плакат 5 рублей. При этом минимальное число отпечатанного агитационного материала должно составить не менее 700 экземпляров. Найти оптимальные параметры печати для достижения максимальной прибыли.
2. Формализация.
Формализация - построение экономико-математической модели задачи.
|
|
|
Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта.
Обозначим оптимизируемые величины (количество листовок и плакатов) переменными x1 и x2 соответственно.
Тогда ограничения по краске ([мл]) запишутся следующей системой неравенств:
 |
x1[шт]*1[мл]+ x2[шт]*3[мл]≤1800[мл] (1)
x1[шт]*1[мл]+ x2[шт]*1[мл]≤1000[мл] (2)
Так как 1 лист формата A3 равен двум листам формата А4, то ограничение по бумаге (в листах формата А4 [лА4]):
x1[шт]*1[лА4]+ x2[шт]*2[лА4]≤1500[лА4] (3)
Последнее ограничение по количеству агитационного материала запишется так:
x1[шт]+ x2[шт]≥700[шт] (4)
Опустим размерности и запишем полученную систему неравенств:
 |
x1+ x2*3≤1800
x1+ x2≤1000 (5)
x1+ x2*2≤1500
x1+ x2≥700
Оптимизационным критерием F будет доход, который необходимо максимизировать:
F=2[руб]*x1[шт]+ 5[руб]*x2[шт]→max (6)
Тогда решением будет вектор x*(x1,x2), если на нем достигается максимальное значение критерия F.
3. Графическое решение
Для решения задачи построим графики уравнений системы неравенств (5) и найдем общую область, удовлетворяющую нашим условиям.
На рис. 1 она закрашена серым цветом.
Для нахождения оптимального решения нам необходимо нанести на график семейство линий уровня - линий, перпендикулярных градиенту критерия F. В нашем случае градиентом будет являться вектор с координатами (2;5), направленный вверх и вправо (исходя из условия максимизации критерия). Крайней точкой, находящейся внутри закрашенной области исходя из построения будет точка пересечения графиков функций:
|
|
|
x1+ x2*3=1800 и x1+ x2=1000. Линия семейства уровней, проходящая через эту точку называется опорной линией уровня.
Рис. 1. Графическое решение оптимизационной задачи
Для нахождения координат точки пересечения решим систему уравнений:
x1+ x2*3=1800 (7)
x1+ x2=1000
x1=600; x2=400
Найдем доход от печати листовок F=600[шт]*2[руб]+ 400[шт]*5[руб]=3200[руб]
Ответ: Для достижения максимальной прибыли необходимо выпустить 600 листовок и 400 плакатов.
