SAS OR. Лекция 1. Оптимизация и исследование операций (Лекции 2014)

SAS/OR: оптимизация и исследование операцийЛЕКЦИЯ 1Валентина ВласоваValentina.Vlasova@sas.comCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.ОптимизацияCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.ОПТИМИЗАЦИЯОптимизация — поиск наилучшего решения среди возможных.Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.ОПТИМИЗАЦИЯЗадача оптимизацииТребуется найти такой вектор параметровфункция, для которого целеваяминимальна (максимальна)на допустимом множестве, заданном ограничениями:приУсловиеCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.ипри.называется критерием оптимальности.ОПТИМИЗАЦИЯВарианты решения Найти хотя бы одну точку глобального минимума (максимума)• Нужно убедиться, что максимум глобальный• Если точек несколько, можно ввести дополнительный критерий Показать, что допустимое множество пусто• Можно ослабить ограничения Показать, что целевая функция не является ограниченной снизу (сверху) надопустимом множестве• Можно ужесточить ограничения или выбрать другую целевую функциюCop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.ТИПЫ ЗАДАЧЗадачи линейного программирования:целевая функция и ограничения линейны,переменные непрерывны.Алгоритмы решения: прямой симплекс-метод, двойственный симплекс-метод, сетевой симплекс-метод, метод внутренней точки.Процедуры SAS: OPTLP, OPTMODEL.Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.LPТИПЫ ЗАДАЧЗадачи смешанно-целочисленноголинейного программирования:целевая функция и ограничениялинейны, переменные дискретны.Алгоритмы решения: метод ветвей и границ с секущимиплоскостями, эвристикой, поискомконфликтов.Процедуры SAS: OPTMILP, OPTMODEL.Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.MILPТИПЫ ЗАДАЧЗадачи нелинейного программирования:целевая функция и ограничения не вселинейны, переменные непрерывны.Алгоритмы решения: метод внутренней точки с довереннойобластью и линейным поиском; метод активного множества с довереннойобластью и линейным поиском; метод сопряженных градиентов; последовательно квадратичноепрограммирование.Процедуры SAS: NLP, OPTQP, OPTMODEL.Cop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.NLPOPTMODELCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.OPTMODELЯзык оптимизационного моделирования OPTMODEL:Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.построение модели,вызов подходящего алгоритма решения.OPTMODEL: ВЫРАЖЕНИЯПроцедура OPTMODELproc optmodel;quit;Построение модели:• константы,• параметры,• целевая функцияnum a = 42;var x {1..2} >= -1 <= 1;max f = a*x[1] - x[2]**2;Решениеsolve;Вывод результатовprint x;Комментарии/* a comment */Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.OPTMODEL: ЗАДАЧА РОЗЕНБРОКАФункция Розенброка для двух переменных:В точкеона имеет минимум, равный .Используется для оценкипроизводительности алгоритмов оптимизации.Поиск ее минимума — нетривиальная задача.Это стандартный пример тестовой функциидля локальных методов оптимизации.ПустьCop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed..OPTMODEL: ЗАДАЧА РОЗЕНБРОКА/* Процедура OPTMODEL */proc optmodel;/* Объявляем константу */num alpha = 100;/* Объявляем параметры */var x {1..2};/* Критерий оптимальности */min f = (1-x[1])**2 + alpha*(x[2]-x[1]**2)**2;/* Решаем */solve;/* Выводим результат */print x;quit;Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.OPTMODEL: ЗАДАЧА РОЗЕНБРОКАОтчеты о задаче и решенииProblem SummaryObjective SenseObjective FunctionObjective TypeSolution SummaryMinimizationfNonlinearSolverAlgorithmObjective FunctionfObjective Value8.204873E-239.704881E-11Bounded Above0Bounded Below0Optimality ErrorBounded Below and Above0InfeasibilityFree2Fixed0Cop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.Interior PointOptimal20NLPSolution StatusNumber of VariablesNumber of ConstraintsРешениеIterations014Presolve Time0.00Solution Time0.17[1]12x11OPTMODEL: ВЫРАЖЕНИЯПостроение модели:• множества,• инициализация,• типы переменных,• ограниченияВвод/вывод:• чтение из файла,• запись в файлОпции (выбор и настройкаалгоритма решения)Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.set DIGITS = 1..5;var number_of_digits integer;var missing {DIGITS} binary init 0;con positive {i in 0..10, j in 0..10}:z[i,j] >= 0;read data input into TOES=[_N_] name=toe len;create data output from [i] name=cat colour;solve with milp / maxtime = 600 loglevel = 2;OPTMODEL: ВЫРАЖЕНИЯФункции (sum, prod, max,min; inter, union, setof, in,within, symdiff, diff, cross,slice; card, sqrt)num distance {i in POINTS, j in POINTS} =sqrt(sum {k in 1..n} (x[i][k]-x[j][k])**2);Логические операции (and,or), ветвление: (if–then–else)num z =(if ((x ne 0) and (y ne 0)) then 1 else 0);set PLANETS init setof {p in FORMER_PLANETS}name[p] diff {"Pluto"};if u >= 1 then size = card(SET1 union SET2);else size = 0;Циклы (for, do, until, while)for {i in NUMBERS} next[i] = i + 1;do i=1 to N;s[i] = 10 + 2 * rand('poisson',p[i-1]);end;Cop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАЗадача коммивояжера: найти наиболее выгодныймаршрут, проходящий через все указанные городас возвращением в исходный город.Это (NP-)сложная задача.Алгоритмы решения: полный или случайный перебор; метод ближайшего соседа; метод эластичной сети; метод ветвей и границ . . .Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАВоспользуемся формулировкой, известной как MTZ*. В полном графе будем искатькратчайший связный ориентированный подграф, в котором каждая вершина имеетстепень 2.Пусть― полный граф; параметрыребра искомому маршруту,― индикаторы принадлежности;― длины ребер.Критерий оптимальности ― минимальность длины маршрута:* Miller, Tucker, Zemlin (1960)Cop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАОграничения, обеспечивающие каждой вершине степень 2 (одно ребро входит внее и одно ребро выходит из нее):Ограничения, обеспечивающие связность маршрута, то есть отсутствие подциклов:Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАВходные данные: таблица столиц штатов и их координатStateALARAZCACO...VTWAWIWVWYCop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.CityMontgomeryLittle RockPhoenixSacramentoDenver...MontpelierOlympiaMadisonCharlestonCheyenneLatitudeLongitude32,3615486,2791234,7360192,3311233,52837112,076338,55561121,468939,72629104,9655......44,2613572,5727647,04242122,893143,0746189,3947638,349581,6332941,14555104,802OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРА/* Процедура OPTMODEL */proc optmodel;/* Множество вершин */set VERTICES;/* Множество всех ребер */set EDGES = {i in VERTICES, j in VERTICES: i ne j};/* Координаты вершин */num xc {VERTICES};num yc {VERTICES};/* Чтение данных из файла */read data tspData into VERTICES=[_n_] xc=var2 yc=var3;/* Округленные расстояния */num c {<i,j> in EDGES}init floor(sqrt(((xc[i]-xc[j])**2+(yc[i]-yc[j])**2))+0.5);Cop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРА/* Параметры */var x {EDGES} binary;var u {i in 2..card(VERTICES)} >= 2 <= card(VERTICES);/* Ограничения на степень вершин маршрута */con assign_i {i in VERTICES}: sum {j in VERTICES: i ne j} x[i,j] = 1;con assign_j {j in VERTICES}: sum {i in VERTICES: i ne j} x[i,j] = 1;/* Критерий оптимальности */min obj = sum {<i,j> in EDGES} (if i > j then c[i,j] else c[j,i]) * x[i,j];/* Ограничение, гарантирующее отсутствие подциклов */con mtz {<i,j> in EDGES : (i ne 1) and (j ne 1)}:u[i] - u[j] + 1 <= (card(VERTICES) - 1) * (1 - x[i,j]);/* Решаем (не дольше 10 минут) */solve with milp / maxtime = 600;quit;Cop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАproc optmodel;set<str,str> CAPPAIRS;set<str> CAPITALS = union {<i,j> in CAPPAIRS} {i,j};num distance{i in CAPITALS, j in CAPITALS: i < j};read data CitiesDist into CAPPAIRS=[city1 city2] distance;set<str,str> TOUR;num order{CAPITALS};solve with NETWORK /loglevel = moderatelinks = (weight=distance)tspout = (order=order tour=TOUR);put (sum{<i,j> in TOUR} distance[i,j]);str CAPbyOrder{1..card(CAPITALS)};for {i in CAPITALS} CAPbyOrder[order[i]] = i;set TSPEDGES init setof{i in 2..card(CAPITALS)} <CAPbyOrder[i-1],CAPbyOrder[i]>union {<CAPbyOrder[card(CAPITALS)],CAPbyOrder[1]>};num distance2{<i,j> in TSPEDGES} = if i < j then distance[i,j] else distance[j,i];create data TSPTourNodes from [node] tsp_order=order;create data TSPTourLinks from [city1 city2]=TSPEDGES distance=distance2;quit;Cop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАproc optmodel;set<str,str> CAPPAIRS;set<str> CAPITALS = union {<i,j> in CAPPAIRS} {i,j};num distance{i in CAPITALS, j in CAPITALS: i < j};read data CitiesDist into CAPPAIRS=[city1 city2] distance;set<str,str> TOUR;num order{CAPITALS};solve with NETWORK /loglevel = moderatelinks = (weight=distance)tspout = (order=order tour=TOUR);put (sum{<i,j> in TOUR} distance[i,j]);str CAPbyOrder{1..card(CAPITALS)};for {i in CAPITALS} CAPbyOrder[order[i]] = i;set TSPEDGES init setof{i in 2..card(CAPITALS)} <CAPbyOrder[i-1],CAPbyOrder[i]>union {<CAPbyOrder[card(CAPITALS)],CAPbyOrder[1]>};num distance2{<i,j> in TSPEDGES} = if i < j then distance[i,j] else distance[j,i];create data TSPTourNodes from [node] tsp_order=order;create data TSPTourLinks from [city1 city2]=TSPEDGES distance=distance2;quit;Cop yrig ht © 2012, SAS Institute Inc.

All rig hts reserv ed.OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАОтчеты о задаче и решенииProblem SummaryNumber of Nodes49Number of Links1176Graph DirectionUndirectedProblem TypeTraveling Salesman ProblemSolution SummarySolverProblem TypeTraveling Salesman ProblemSolution StatusOptimalObjective Value10627.754318Solution TimeCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.Network0.17OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАВыходные данные: оптимальный маршрутCity 1MontgomeryTallahasseeColumbiaRaleighRichmond...SpringfieldIndianapolisFrankfortNashville-DavidsonAtlantaCop yrig ht © 2012, SAS Institute Inc. All rig hts reserv ed.City 2TallahasseeColumbiaRaleighRichmondWashington...IndianapolisFrankfortNashville-DavidsonAtlantaMontgomeryDistance177,1355311,2251182,9923135,584497,96186...186,4618129,8982175,5813212,605145,3927OPTMODEL: ЗАДАЧА КОММИВОЯЖЕРАОптимальный маршрут на картекартинкаCop yrig ht © 2012, SAS Institute Inc.