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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций