SAS OR. Лекция 2. Оптимизация и исследование операций (Лекции 2014), страница 2
Описание файла
Файл "SAS OR. Лекция 2. Оптимизация и исследование операций" внутри архива находится в папке "Лекции 2014". PDF-файл из архива "Лекции 2014", который расположен в категории "". Всё это находится в предмете "(ппп соиад) (sas) пакеты прикладных программ для статистической обработки и анализа данных" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
All rig hts reserv ed.MINLP: MPSНеобходимо преобразовать mps файл для того, чтобы сделать корректными именапеременных, которые были элементами массивов:%macro mps(old,new);data &new(drop=i);set &old;array FC{*} _CHARACTER_;do i=1 to dim(FC);FC[i]=tranwrd(FC[i],",","_");FC[i]=compress(FC[i],"[]");end;run;%mend;...LLLLCOLUMNS%mps(mpsraw, mpsdata);prd[1,0]prd1_0...Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.......repair_con[7,4]repair_con[8,4]repair_con[9,4]repair_con[10,4]prd[1,0]prd[1,0]prd[1,0]prd[1,0]prd[1,0]prd[1,0]prd[1,0]prd[1,0]prd[1,0]prd[1,1]prd[1,1]prd[1,1]prd[1,1]prd[1,1]prd[1,1]prd[1,1]............profit_final-10,82852residue_con[1,0]1residue_con[1,12]-0,128residue_con[2,12]-0,128residue_con[3,12]-0,128residue_con[4,12]-0,128residue_con[5,12]-0,128residue_con[6,12]-0,128residue_con[7,12]-0,128residue_con[8,12]-0,128residue_con[9,12]-0,128residue_con[10,12]-0,128power_con[1,2]-1power_con[1,3]-1power_con[1,4]-1power_con[1,8]-1power_con[1,9]-1power_con[1,11]-1profit_final-1,10353residue_con[1,1]1residue_con[2,1]1residue_con[3,1]1residue_con[4,1]1residue_con[5,1]1residue_con[6,1]1residue_con[7,1]1residue_con[8,1]1residue_con[9,1]1residue_con[10,1]1power_con[1,12]-0,5power_con[1,13]-1power_con[1,14]-1............MINLP: MPSНеобходимо преобразовать mps файл для того, чтобы сделать корректными именапеременных, которые были элементами массивов:%macro mps(old,new);data &new(drop=i);set &old;array FC{*} _CHARACTER_;do i=1 to dim(FC);FC[i]=tranwrd(FC[i],",","_");FC[i]=compress(FC[i],"[]");end;run;%mend;...LLLLCOLUMNS%mps(mpsraw, mpsdata);prd[1,0]prd1_0...Cop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.......repair_con7_4repair_con8_4repair_con9_4repair_con10_4...prd1_0prd1_0prd1_0prd1_0prd1_0prd1_0prd1_0prd1_0prd1_0prd1_1prd1_1prd1_1prd1_1prd1_1prd1_1prd1_1...-10,82852residue_con1_01-0,128residue_con2_12-0,128-0,128residue_con4_12-0,128-0,128residue_con6_12-0,128-0,128residue_con8_12-0,128-0,128residue_con10_12-0,128-1power_con1_3-1-1power_con1_8-1-1power_con1_11-1-1,10353residue_con1_111residue_con3_111residue_con5_111residue_con7_111residue_con9_111power_con1_12-0,5-1power_con1_14-1.........profit_finalresidue_con1_12residue_con3_12residue_con5_12residue_con7_12residue_con9_12power_con1_2power_con1_4power_con1_9profit_finalresidue_con2_1residue_con4_1residue_con6_1residue_con8_1residue_con10_1power_con1_13.........MINLP: FCMPОпределим функции для нелинейных ограничений с помощью процедуры FCMPвнутри макро-цикла:%macro lso_func;proc fcmp outlib = myfuncs.mypkg;%do p=1 %to &PRDS;%do m=1 %to &MCHNS;function nl_&p._&m (power_avail_&p._&m, wear_cur_&p._&m, rel_cur_&p._&m);return (power_avail_&p._&m - wear_cur_&p._&m * rel_cur_&p._&m);endsub;%end;%end;run;%mend;%lso_func;Cop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.MINLP: FCMPСоздадим файл с информацией о нелинейных ограничениях с помощью макроса:%macro lso_data;data nl;length _id_ $ 8;%do p=1 %to &PRDS;%do m=1 %to &MCHNS;_id_="nl_&p._&m";_lb_=0;_ub_=0;output;%end;%end;run;%mend;%lso_data;Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed._id_nl_1_1nl_1_2nl_1_3nl_1_4nl_2_1nl_2_2nl_2_3nl_2_4nl_3_1..._ub_000000000..._lb_000000000...MINLP: OPTLSOНаконец, вызывем процедуру OPTLSO:options cmplib = myfuncs;proc optlsompsdata = mpsdatanlincon = nlprimalout = resultabsfconv = 0.1maxtime = 600;performance nthreads = CPUCOUNT;run;Ее параметры ― это имена входных и выходных файлов, максимальная допустимаяпогрешность, ограничение на время решения и количество потоков выполнения.Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.MINLP: ОТЧЕТЫPerformance InformationProblem SummaryProblem TypeMINLPMPS Data SetMPSDATANonlinear ConstraintsNLExecution ModeSingle-MachineNumber of Threads8Solution SummaryNumber of Variables820Solution StatusMaximum time reachedInteger Variables320Objective-20223520803Continuous Variables500Infeasibility1051063.9667Number of Constraints920Iterations189Linear Constraints880Evaluations217917Nonlinear Constraints40Cached Evaluations132489Global Searches1Objective Definition SourceMPSDATAPopulation Size320Objective SenseMaximizeSeed1Cop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.ПОДХОД К РЕШЕНИЮ: MILPMINLPMILPлинейныеусловиялинейныеусловиянелинейноеограничениеCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.OPTMODELMILP: АППРОКСИМАЦИЯАппроксимация нелинейного ограничения линейным (и более сильным)мощность = износ надежностьCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.мощность =(износ + надежность – 1)MILP: OPTMODELВместо объявления доступной мощности как параметраvar power_avail_ {p in PERIODS, m in MACHINES};введем соответствующую линеаризованную переменную:var pa_x {p in PERIODS, m in MACHINES, 0..2} >= 0;var pa_z {p in PERIODS, m in MACHINES, 0..2} binary;impvar power_avail_ {p in PERIODS, m in MACHINES} = pa_x[p,m,1];con pa_con_0 {p in PERIODS, m in MACHINES}: sum {j in 0..2} pa_x[p,m,j]= 2 + (wear_cur[p,m] + rel_cur[p,m]) - 2 * (sum {r in REPAIRS}(sum {jj in 0..rep_time[r]-1 INTER 0..p-1} rpr[p-jj,m,r]));con pa_con_1 {p in PERIODS, m in MACHINES, j in 0..2}:pa_x[p,m,j] <= (if j=0 then 2 else 1) * pa_z[p,m,j];con pa_con_2 {p in PERIODS, m in MACHINES, j in 0..1}:(if j=0 then 2 else 1) * pa_z[p,m,j+1] <= pa_x[p,m,j];Cop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.MILP: OPTMODELВместо сохранения задачи в формате mps и решения в процедуре OPTLSOsave mps mpsraw;%mps(mpsraw, mpsdata);%lso_func;%lso_data;options cmplib=myfuncs;proc optlsompsdata=mpsdata nlincon=nl primalout=result absfconv=0.1 maxtime=300;performance nthreads=CPUCOUNT;run;сразу решим ее в процедуре OPTMODEL (и создаем файлы с результатами)solve with milp;createcreatecreatecreatedatadatadatadataCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.enrc.res_prdenrc.res_slsenrc.res_rprenrc.res_auxfromfromfromfrom[per mat] prd;[per] sls;[per mach rep] rpr;[per mat seg] wear_x wear_z rel_x rel_z pa_x pa_z;MILP: OPTMODELДобавим многопоточность и ограничение на погрешность:performance nthreads = CPUCOUNT;solve with milp / relobjgap=1e-1 parallel=ON;Результаты вычислений для меньших объемов данных:МаксимальнаяпогрешностьПериоды20202121222223232424253030Cop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.0.00010.10.00010.10.00010.10.00010.10.00010.10.10.00010.1Целевая функция24 009 865 90122 450 199 80625 043 929 78824 307 490 90226 275 535 22125 531 704 33827 577 711 13125 579 850 54428 901 025 27427 297 180 25527 554 386 44234 223 462 98133 692 600 604Фактическаяпогрешность00.065000.029400.028300.072400.0555.00.0155РемонтыВремя080003010049030:02:350:01:040:00:470:01:280:01:450:01:350:17:160:01:381:42:001:43:003:34:000:15:000:15:00MILP: OPTMODELВоспользуемся методом декомпозиции:for {p in PERIODS, m in MACHINES} do;wear_con_0[p,m].block = m;for {j in 0..2} wear_con_1[p,m,j].block = m;for {j in 0..1} wear_con_2[p,m,j].block = m;rel_con_0[p,m].block = m;for {j in 0..2} rel_con_1[p,m,j].block = m;for {j in 0..1} rel_con_2[p,m,j].block = m;pa_con_0[p,m].block = m;for {j in 0..2} pa_con_1[p,m,j].block = m;for {j in 0..1} pa_con_2[p,m,j].block = m;repair_con[p,m].block = m;end;Добавим ограничение на количество узлов для подзадач:performance nthreads = CPUCOUNT;solve with milp / relobjgap=1e-1 parallel=ONdecomp=(master_ip_freq=1) subprob=(relobjgap=1e-1 maxnodes=100000);Cop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.MILP: ЛОГЛог содержит информацию о покрытии исходной задачи подзадачами:...NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:NOTE:...The MILP presolver value AUTOMATIC is applied.The MILP presolver removed 720 variables and 1442 constraints.The MILP presolver removed 2646 constraint coefficients.The MILP presolver modified 0 constraint coefficients.The presolved problem has 4860 variables, 4858 constraints, and 59650constraint coefficients.The MILP solver is called.The Decomposition algorithm is used.The Decomposition algorithm is executing in single-machine mode.The DECOMP method value USER is applied.The problem has a decomposable structure with 4 blocks.
The largest blockcovers 19.76% of the constraints in the problem.The decomposition subproblems cover 4080 (83.95%) variables and 3840(79.04%) constraints.The deterministic parallel mode is enabled.The Decomposition algorithm is using up to 8 threads.Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.MILP: ОТЧЕТSolution SummarySolverAlgorithmObjective FunctionCop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.MILPDecompositionprofit_finalSolution StatusOptimal with Relative GapObjective Value51829253430Relative Gap0.0994791135Absolute Gap5725495392.6Primal Infeasibility6.7579094E-8Best Bound57554748823Nodes1Iterations4Presolve Time1.07Solution Time315.66MILP: РЕЗУЛЬТАТЫДисконтированная прибыль:Производство угля (приостанавлено в 31–32 периодах):Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.Средняя надежностьединиц оборудования:MILPКак улучшить решение?performance nthreads = CPUCOUNT;solve with milp / relobjgap=1e-1 parallel=ONdecomp=(master_ip_freq=1) subprob=(relobjgap=1e-1 maxnodes=100000); Уменьшить возможную погрешность• Решение лучше• Время решения возрастает слишком быстро Увеличить количество узлов• Время решения возрастает• Решение может быть лучше или хужеCop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.MILP: ГРАФИКГрафик зависимости значенияцелевой функции и временирешения от значения maxnodes(лучшее решение соответствуетзначению maxnodes = 250 000)Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.MILP: ОТЧЕТSolution SummarySolverAlgorithmObjective FunctionCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.MILPDecompositionprofit_finalSolution StatusOptimal with Relative GapObjective Value54854823804Relative Gap0.0409073398Absolute Gap2339674790.5Primal Infeasibility3.5390258E-8Best Bound57194498595Nodes1Iterations4Presolve Time0.85Solution Time655.76MILP: РЕЗУЛЬТАТЫДисконтированная прибыль:Производство угля:Cop yrig ht © 2012, SAS Institute Inc.
All rig hts reserv ed.Средняя надежностьединиц оборудования:ОПТИМИЗАЦИЯ ПРОИЗВОДСТВА И ПРОДАЖИ УГЛЯКак повысить качество решения? Добавить бизнес-правила Улучшить линейное приближение Уменьшить погрешность Настроить параметрыCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.www.sas.com/en_us/software/analytics/sas-or.htmlCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.www.SAS.com.
