Оптимизация процессов деревообработки на моделях линейного и нелинейного программирования
Курсовой проект - Разное
Другие курсовые по предмету Разное
?9),
х6=60-(0,1х1+0,15х2+0,3х3+0х4+0х5+0х7+0х8+0х9), (3.5)
х7=-100-(-1х1-0х2-0х3 +0х4+0х5+0х6+0х8+0х9),
х8 =-150-(-0х1-1х2-0х3 +0х4+0х5+0х6+0х7+0х9),
х9=-75-(-0х1-0х2-1х3+0х4+0х5+0х6+0х7+0х8).
Целевую функцию (критерий эффективности) представим в виде
W=0-(-80 х1-150 х2-250 х3). (3.6)
Заполним первую симплексную таблицу 3.2.
Таблица 3.2
БПСЧПеременныеОценочное отношениех1х2х3х4х5х6х7х8х9х41500,30,350,5100000300х52000,40,50,8010000250х6600,10,150,3001000200х7-100-100000100?х8-1500-10000010?х9-7500-100000175W0-80-150-250000000max
Дальнейшее решение представим в таблицах 3.3 - 3.6.
Таблица 3.3 х9- х3
БПСЧПеременныеОценочное отношениех1х2х3х4х5х6х7х8х9х4112,50,30,350100000,5225х51400,40,50010000,8175х637,50,10,150001000,3125х7-100-100000100?х8-1500-10000010?х37500100000-1?W18750-80-150000000-250max
Таблица 3.4 х6- х9
БПСЧПеременныеОценочное отношениех1х2х3х4х5х6х7х8х9х4500,1010000500х5400,1001000400х91250,5000001250х7-100-100000100?х8-1500-10000010150х32000,5100000400W50000-25000000max
Таблица 3.5 х8- х2
БПСЧПеременныеОценочное отношениех1х2х3х4х5х6х7х8х9х435001000,10350х525100100,10250х950000000,51100х7-100-100000100?х21500100000-10?х3125010000,50250W5375000000-250max
Таблица 3.6 х9- х8
БПСЧПеременныеОценочное отношениех1х2х3х4х5х6х7х8х9х425001000-0,2375х515000100-0,2225х81000000012150х7-100-100000100100х225010000002375х3750010000-1?W5625020000010000050max
Полученное решение является оптимальным, т. к. все коэффициенты ЦФ положительные, но не является допустимым, поскольку х7=-100<0. Поэтому продолжим поиск оптимального допустимого решения и представим его в таблице 3.7.
Таблица 3.7 х7- х1
БПСЧПеременныеОценочное отношениех1х2х3х4х5х6х7х8х9х4000100-0,2х5000010-0,2х80000012х1100100000-100х2010000002х375001000-1W5425000000100020050max
Критерий оптимальности выполнен, значит Wmax=54250, оптимальный план производства составляет Х* =(100; 183; 75; ; ; 0; 0; 33; 0).
Действительно, подставляя полученные значения в (3.4), получаем
W= 80x1 + 150x2 + 250x3 = 80*100+183*150+75*250=54200.
Ресурсы времени на сборку использованы полностью, осталось ч на производство деталей и ч на сборку приёмников. Перевыполнен план по выпуску приёмников модели В на 33 шт.
Решение двойственной задачи. Используя три теоремы двойственности, значение двойственных оценок у1 у2,..., уm можно получить на основе решения исходной.
Сначала составляем ММ двойственной задачи путем транспонирования расширенной матрицы коэффициентов исходной задачи.
Основываясь на свойствах взаимно двойственных задач, запишем ограничения, ЦФ из условия неотрицательности двойственной задачи
,3у1+0,4у2+0,1у3-1у4+0у5+0у6?80,
,35у1+0,5у2+0,15 у3+0у4-1у5+0 у6?150, (3.7)
,5у1+0,8у2+0,3у3+0у4+0у5-1у6?250.
ЦФ принимает вид
Z=150 у1+200 у2+60 у3-100 у4-150 у5-75 у6>min. (3.8)
Для преобразования ММ в ОЗЛП требуется ввести три дополнительные неотрицательные переменные у7, у8, и у9.
,3у1+0,4у2+0,1у3-1у4+0у5+0у6 -1у7-0у8-0у9=80,
,35у1+0,5у2+0,15 у3+0у4-1у5+0 у6-0у7-1у8-0у9=150, (3.7)
,5у1+0,8у2+0,3у3+0у4+0у5-1у6-0у7-0у8-1у9=250.
Составляем таблицу 3.8 соответствия переменных ИсхЗ и ДвЗ.
Таблица 3.8 - Соответствие переменных ИсхЗ и ДвЗ
Исходная задача 1Основные переменныеДополнительные переменныеДополнительные переменныеОсновные переменныеДвойственная задача 2
Согласно второй теореме двойственности, компоненты оптимального решения ДвЗ равны абсолютным значениям коэффициентов при соответствующих переменных ЦФ ИсхЗ, выраженной через неосновные переменные её оптимального решения. Из таблицы 3.7 имеем
У*=(0; 0; 1000; 20; 0; 50; 0; 0; 0).
Вычисляем оптимальное значение ЦФ
Wmax=Zmin=150у1+200у2+60у3-100у4-150у5-75у6= =150*0+200*0+60*1000-100*20-150*0-75 *50=54250.
W(x*)=Z(у*)=54250.
Получено подтверждение первой теоремы двойственности. Положительным (ненулевым) компонентам оптимального решения одной из взаимно ДвЗ соответствуют нулевые компоненты оптимального решения другой задачи, т. е.
если х*j >0, то уm+j=0,
если х*n+I >0, то уi=0, (3.8)
если у*j >0, то хn+j=0,
если у*m+j >0, то хj=0.
Заполним таблицу 3.9 соответствия переменных элементами решения ИсхЗ и ДвЗ.
Таблица 3.9 - Соответствие переменных элементами решения ИсхЗ и ДвЗ
Исходная задача 1Число единиц продукцииОстатки ресурсовПеревыполнение плана х1=100 х2 =184 x3=75 ¦ ¦ ¦ у7=0 у8=0 у9=0х4 =18,6 х5=8,6 х6=0 ¦ ¦ ¦ у1=0 у2=0 у3=1000 х7=0 х8=34 х9=0 ¦ ¦ ¦ у4=20 у5=0 у6=50Превышение затрат на ресурсы над ценойУсловие цены=ОбОбОц ресурсовДвойственная задача 2
Смысл объективно-обусловленных оценок. Третья теорема двойственности. Компоненты оптимального решения ДвЗ называются оптимальными (двойственными) оценками ИсхЗ, или объективно-обусловленными оценками (ОбОбОц). Смысл этих оценок выясним по компонентам оптимального решения.
В таблице 3.8 дополнительные переменные ИсхЗ Х4, Х5 и Х6, представляющие разность между запасами ресурсов времени на соответствующие операции и их использованием на соответствующие модели приёмников, выражают остатки ресурсов времени, дополнительные переменные Х7, Х8 и Х9, представляющие разность между выпуском и планом выпуска соответствующих приёмников, выражают перевыполнение плана, а дополнительные переменные ДвЗ у7, у8, и у9, представляющие разность между затратами на ресурсы для производства из них единицы продукции и прибылью от реализации ресурсов времени выражают превышение затрат над прибылью.
Действительно, по формулам 3.5
х4= 150 - 0,3* 100 - 0,35*183 - 0,5*75 = 18,45,
х5= 200 - 0,4* 100 - 0,5*183 - 0,8*75 = 8,5,
х6= 60 - 0,1* 100 - 0,15*183 - 0,3*75 = 0,05,
х7=100-100=0,
х8=183-150=33,
х9=75-75=0.
Из формул 3.7 получаем
у7= 0,3*0+0,4*0+0,1*1000-1*20+0+0 -80=0,
у8= 0,35*0+0,5*0+0,15 *1000+0-1*0+0 *50-150=0,
у9= 0,5*0+0,8*0+0,3*1000+0+0-1*50-250=0.
Ресурсы времени на упаковку ?/p>