Методы оптимальных решений

 

 

 

 

Задача 1

Информация по фирме о  нормах затрат ресурсов  на  единицу выпускаемой продукции, лимитах на эти ресурсы  и ценах реализации готовой продукции представлена в таблице.

Наименование  ресурсов	Норма затрат на		Объем ресурса
	Продукт А	Продукт Б
Сырье (кг)	2	1	295
Оборудование (ст.час.)	1	4	204
Трудоресурсы (чел. час.)	9	1	681
Цена реализации (руб.)	460	335

Требуется:

1. Составить  модель расчета оптимальной производственной  программы для  этой фирмы на основе задачи линейного программирования.

2. Используя  графический метод решения этой  модели, найти оптимальную программу  выпуска продукции, максимизирующую ожидаемый объем продаж.

3. Сформировать  задачу, двойственную к задаче  расчета оптимальной производственной программы и составить обе группы условий “дополняющей нежесткости”.

4. Подставив  в условия “дополняющей нежесткости”  оптимальную программу выпуска, найти предельную эффективность имеющихся у предприятия объемов ресурсов.

5. Выполнить  проверку оптимальных решений  прямой и двойственной задачи  подстановкой  их в ограничения и целевые функции.

 

Решение

1. Построение математической модели  оптимизации выпуска продукции

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

В нашей задаче необходимо определить месячные объемы выпуска продукции А и Б, поэтому обозначим их как переменные модели:

х1 – месячный объем выпуска продукции А,

х2 – месячный объем выпуска продукции Б.

Ограничения модели должны учитывать физические возможности использования ресурсов. Таким образом, ограничения модели имеют вид:

 

    Расход ресурсов для             Максимально возможный

   производства месячных   месячный размер используемых

    объемов продукции             ресурсов

 

Используя данные таблицы, получим:

расход сырья = 2х1+1х2,

затраты времени работы оборудования  =  1х1+4х2,

затраты рабочего времени = 9х1+1х2.

Так как ежемесячный расход ресурсов не может превышать их максимально возможный месячный размер, то имеем ограничения

2x1+1x2£295,

1x1+4x2£204,

9x1+1x2£681.

Еще одно неявное ограничение состоит в том, что переменные х1 и х2 должны быть неотрицательны, т.е. х1 ³ 0, х2 ³ 0.

Целевая функция в данной задаче выражает стремление фирмы получить  максимальную выручку от реализации продукции:

Z=460х1+335х2→max

Таким образом математическая модель данной задачи выглядит следующим образом:

Найти неизвестные значения переменных х1, х2, удовлетворяющих ограничениям

2х1+1х2≤295

1х1+4х2≤204

9х1+1х2≤681

х1≥0, х2≥0

и доставляющих максимальное значение целевой функции:

Z=460х1+335х2→max

 

2. Нахождение оптимальной производственной  программы выпуска продукции

Решим задачу графическим способом. Построим множество допустимых решений или область допустимых решений. Проводим перпендикулярные оси координат: горизонтальная - 0х1, вертикальная - 0х2 (рис. 1.1.). Условия неотрицательности переменных х1 ³ 0,  х2 ³ 0 показывают, что область допустимых решений будет лежать в первом квадранте системы координат. Для изображения на плоскости множества точек, координаты которых удовлетворяют оставшимся ограничениям модели, рассмотрим уравнения, получаемые из неравенств модели заменой знака “ £ ” на знак “ = ”. В результате такой замены получим три линейных уравнения, которые представляют собой уравнения прямых:

2х1+1х2=295 (1)

1х1+4х2=204 (2)

9х1+1х2=681 (3)

Постоим уравнения данных прямых на координатной плоскости, для этого определим точки пересечения прямых с осями координат:

2х1+1х2=295:

	х1	х2
х1	0	295
х2	147,5	0

 

1х1+4х2=204:

	х1	х2
х1	0	51
х2	204	0

 

9х1+1х2=681:

	х1	х2
х1	0	681
х2	75	0

 

Множество допустимых решений представляет собой четырехугольник ОАВС. Любая точка, лежащая внутри этого пятиугольника и на любом отрезке его границы, удовлетворяет всем ограничениям модели и является допустимым решением.

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

Z=460х1+335х2→max.

Постоим линию градиента целевой функции, grad Z= (460, 335) и линии уровня целевой функции перпендикулярные градиенту. Точка пресечения области допустимых решений и линии уровня, соответствующей максимально возможному значению целевой функции, и будет точкой максимума.

 

 

Рис. 1. Иллюстрация нахождения точки максимума целевой функции

 

Линия уровня целевой функции покидает последней точку В, а значит она и является оптимальным решением. Найдем координаты этой точки, лежащей на пересечении прямых (2) и (3):

1х1+4х2=204

9х1+1х2=681

Решая систему уравнений, находим х1* =72, х2* =33. При этих значениях целевая функция равна:

Z*=460х1*+335х2* =460∙72+335∙33=44175 руб.

Полученное решение означает, что предприятию необходимо производить 72 единиц продукции А и 33 единицы продукции Б, что позволит ему получать максимальную выручку, составляющую 44175 руб.

 

 

3. Построение двойственной задачи

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

2х1+1х2≤295

1х1+4х2≤204

9х1+1х2≤681

х1≥0, х2≥0

Z=460х1+335х2→max

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

1. Каждому ограничению прямой задачи (кроме ограничений х1 ³ 0, х2 ³ 0) соответствует неотрицательная переменная двойственной задачи. В нашем примере три ограничения. Следовательно, в двойственной задаче будет три переменных. Обозначим их через u1, u2, u3, где u1 соответствует первому ограничению, u2 - второму, u3 - третьему.
2. Каждой переменной прямой задачи соответствует ограничение двойственной. Следовательно, в нашем примере двойственная задача будет иметь два ограничения.
3. Коэффициенты при какой-либо переменной в ограничениях прямой задачи и коэффициент целевой функции при этой переменной становятся соответственно

• коэффициентами того ограничения двойственной задачи, которое соответствует этой переменной и

• правой частью формируемого ограничения двойственной задачи.

В нашем примере переменной х1 соответствует первое ограничение двойственной задачи; коэффициенты 2, 1, 9 при х1 являются коэффициентами первого ограничения двойственной задачи, а коэффициент целевой функции прямой задачи при х1, т.е. 126, становится правой частью первого ограничения, записываемого со знаком “ ³ ”. Таким образом, первое ограничение двойственной задачи примет вид

2u1+1u2+9u3³460

4. Правые части ограничений прямой задачи являются коэффициентами целевой функции двойственной задачи, которая минимизируется. Следовательно, в нашем примере целевая функция двойственной задачи примет вид

W = 295u1+204u2+681u3 ® min.

Применение сформулированных правил к задаче оптимизации производственной программы приводит к следующей двойственной задаче:

найти неизвестные значения переменных u1, u2, u3, удовлетворяющих ограничениям 

2u1+1u2+9u3³460

1u1+4u2+1u3³335,

u1³0, u2³0, u3³0,

и доставляющих минимальное значение целевой функции

W = 295u1+204u2+681u3 ® min.

 

4. Нахождение оптимального решения  двойственной задачи

Используя теоремы двойственности, сформулируем для данной задачи условия «дополняющей нежесткости»:

u1 (295-2х1-1х2)=0

u2 (204-1х1-4х2)=0

u3 (681-9х1-1х2)=0

х1(2u1+1u2+9u3-460)=0

х2(1u1+4u2+1u3-335)=0

 

Подставляя в них найденные значения х1* =72, х2* =33, получим:

так как х1* =72≠0, то 2u1+1u2+9u3-460=0,

так как х2* =33≠0, то 1u1+4u2+1u3-335=0,

так как 1295-2х1*-1х2* >0, то u1=0.

Таким образом, получаем систему уравнений:

2u1+1u2+9u3-460=0,

1u1+4u2+1u3-335=0,

u1=0.

Решая данную систему, находим оптимальные значения переменных двойственной задачи:

0,   73,  43.

Вычислим оптимальное значения целевой функции двойственной задачи: , т.е. 44175, что соответствует первой теореме двойственности.

 

5. Выполним проверку оптимальных решений прямой и двойственной задачи подстановкой  их в ограничения и целевые функции:

Подставляем х1* =72, х2* =33, получим:

2·72+1·33=177

1·72+4·33=204

9·72+1·33=681

х1 =72>0, х2=33>0

Z*=460х1*+335х2* =460∙72+335∙33=44175 руб.

Подставляем 0,  73,  43:

2·0+1·0+9·43=460

1·0+4·73+1·43=335,

u1=0, u2=73>0, u3=43>0,

204 681 295∙0+204∙73+681∙43=44175.