Однокритериальная оптимизация операций и решений (1264202)

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

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

Однокритериальная оптимизация операций и решенийЗадачи, методы и алгоритмы IV-гоиерархического уровняОсновные функции управляющего органа:1) выбор состояния, в которое надо перевести систему;2) выбор режима, в котором должна функционировать система;3) принятие решений о выполнении нестандартной задачи;4) формирование алгоритма принятия решений в плохо структурированныхусловиях:a) когда формальных моделей нет;b) когда векторов показателей, обладающих полнотой отражениявербальной цели, нет;c) когда множество альтернатив точно не задано (альтернатива –множество, на котором мы принимаем решения);5) принятие решений во внештатных ситуацияхсредство реализации – элемент 4.1 :a) либо в виде автомата,b) либо в виде ЛПР, обеспеченного системами подготовки решений илигруппами поддержкиСреди типовых задач, решаемых на уровне 4.1 , выделяются задачиуправления ресурсами, например:1) распределение ресурсов2) целераспределениеОсновные ограничения при принятии решений:1) t p  Tд ,2) Т д = Т д ( y )Классическая задача принятия решенийЗаключается в выборе допустимого или оптимального решения надекартовом множестве альтернатив (Y,H,U,P(X),G,D)Y – множество входных неконтролируемых воздействий.U f  U – множество допустимых управлений в ЗОУ, ЗИСО, ПР.H – множество неопределенностей.X – множество выходов или множество моделей PМножество моделей: P : Y U  H → X – множество выходов (состояний)G – множество оценочных функций, гдеG : Y U f  H  X → I (или Е) – множество оценокD – множество допустимости (толерантности),где D : Y  H → I ( E ) , I – допустимые значения оценок (или другихограничений).Формулировка задачи принятия допустимых решенийПри заданном y*  Y существует допустимое решение, если можно найтиu д Uтакие, что h  H : G( y*, h, u д , xд )  D(u д , h) .x X«  » – если вектор I ( E ) в функции G – потери;д«  » – если вектор I ( E ) имеет смысл эффективности.Задача принятия оптимального решенияПри заданном y*  Y существуют оптимальные решения, если можно найтиu o Ux XoG( y д , h, u, x) (или supG , если I ( E ) –такие, что h  H : G( y*, h, u o , xo ) = infuUпоказатель эффективности)Пример задачи принятия решений.

(Задача выбора оптимального маршрутана основе нелинейного программирования)Введем функцию, подобную функции Беллмана k , определяющуюоптимальное значение критерия для маршрута из 0 в К.k = min[akp +  p ] ,{ p}где р – множество вершин; akp - вес дуги из любой вершины Р в вершину К.Р<К – номера всех вершин, инцидентных вершине К, {K=0..N}.Учитывая срецифику этого конкретного графа:a41 + 14 = min a40 + 0a42 + 2{1 = a10 ; 2 = a20 ; 3 = a30 ; 0 = 0}5 = min p = mina52 + 2a53 + 3a p 4 + 4a p 5 + 5и т.д.

(Идем по функциям, выбираем не единственный оптимальныймаршрут.)Методы решения задачи выбора (задачи назначения)В общем случае задача принятия решения – неформализованная задача, дляее решения необходимо применить такой метод, как экспертные подходы.В данном пункте мы будем рассматривать предварительно количественноеобоснование решений на основе одного из видов задач распределенияресурсов:• общая задача распределения ресурсов• задача размещения• задача назначенияНаиболее структуно простой является задача назначения:существует n – исполнителей и n – работnnE =  aij xij → mini =1 j =1 xij = 1, j = 1: n  i =1 n x = 1, i = 1: n  j =1 ijxij = {0;1}nМатрица A = {aij } , где aij может иметь смысл времени, стоимости работ,дальности (расстояния) и т.д.

или вероятности поражения ( Pij - i-ое средство,т.е. снаряд, направляется на j-ую цель, где aij = Pij - эффективностьпоражения).Задача выбора (назначения) с матрицей А особого видаA = {aij } , пусть элементы матрицы удовлетворяют следующим условиям:1) В любой строке приращение между элементами матрицыci = ai , j +1 − ai , j = const2) Строки расположены так, чтоc1  c2  ...

 cnВ этом случае оптимальное решение имеет следующий вид:nE o = Spur = SpA =  a iii =1( trace )ox = x = x = ... = xnn= 1.o11o22o33Пример54A=319 13 177 10 135 7 92 3 4c1 = 4; c2 = 3; c3 = 2; c4 = 1oo0E o = 5 + 7 + 7 + 4 = 23 . Совершенно ясно, что x11o = x22= x33= x44= 1.I.II.III.IV.V.VI.Точные методы решения задач выбораМетод линейного программированияВычислительная процедура динамического программированияВенгерский методМетод кратчайшего увеличивающегося пути (КУП)Задача выбора с матрицей особого вида\Метод МакаМетод линейного программированияПредварительно проводится переиндексация переменных и коэффициентовматрицы:a11 → a1a21 → an +1xij → x1...xn2n2a1n → anann → an2I ( E ) = E =  ai xi → mini =1Ограничения по строкам и столбцам:x1 + x2 + ...

+ xn = 1x1 + xn +1 + x2 n +1 + ... + xn2 − n +1 = 1.......................xn +1 + ... + x2 n = 1.......................xn + x2 n + ... + xn2 = 1dimA=100, n2 = 10000, n = 100 .Вычислительная процедура динамического программированияВведем функцию Беллмана k (i1 , i2 ,..., ik ) - функция оптимальногораспределения К –работ между К-исполнителями, когда они имеют номераi1 , i2 ,..., ik .Функциональное уравнение Беллмана имеет вид:ak ,i1 + k −1 (i2 , i3 ,...ik ) ak ,i2 + k −1 (i1 , i3 ,...ik ) k (i1...ik ) = min ............................... a +  (i , i ,...i ) k −1 1 2k −1  k ,ikМетод кратчайшего увеличивающегося пути (КУП)Предположим, что существует оптимальное решение для матрицы An−1 ,и его можно расположить по главной диагонали.E *( A( n−1) ) = SpA( n−1)Перейдем к An .

Нужно добавить элемент для того, чтобы получитьоптимальное решение.Проанализируем пары: (ai ,i + an,n ) и (ai ,n + an,i ) .Рассмотрим разность: (ai ,n + an,i ) - (ai ,i + an,n ) → min,i = 1: n − 1 - условие{i}включения элемента в решение.Если min соответствует i =  , следовательно, в решение включаемэлементы a ,n и an, .Если min обеспечивается для i = n , следовательно, в решение добавляемэлемент an,n .Если решение для матрицы An−1 будет оптимальным, то полученноерешение будет оптимальным для матрицы An .В методе КУП последовательно наращивается порядок матрицы от 2 до n, врешение вводятся элементы по приведенным выше правилам.Пример задачи выбора.Пусть A( n −1) =54321088915 1291220 16 158Дополним до матрицы An .i=1 (25+1)-(5+5)=16i=2 (20+2)-(8+5)=9i=3 (15+3)-(9+5)=4i=4 (10+4)-(8+5)=4i=5 5-5=0дает решение E* = SpA( n−1) = 30 .min=0  в решение попадает a55 = 5Порядок: от 2 до n.x11 = x22 = x33 = x44 = x55 = 1 .Приближенные методы решения задач выбора1) Метод поэтапного выбора2) Метод Фогеля3) Метод КУП4) Задача выбора и «жадный» алгоритм5) Метод приращений6) Метод min (max) элемента при минимизации (максимизации) (частныйслучай «жадного» алгоритма)и т.д.Метод поэтапного выбораПодсчитывается сумма элементов в каждой строке, строкирасположены в порядке убывания этих сумм.К-тый шаг: в К-той строке отыскивается минимальный элемент и вносится врешение.

Соответствующий этому элементу столбец исключаем из матрицы,K = 1, n .ПримерK =1 = 48K =2 = 38 = 28 = 18Эта матрица особого вида, следовательно, уже знаем решение.x11 = x22 = x33 = x44 = 1 - существует сигнал.E o = 6 + 8 + 8 + 6 = 28Метод Фогеля1-ая итерация1-ый шаг: в каждой строке определяется минимальный элемент иближайший к нему элемент и составляются n-разностей. i = int aij* − aij*aij* = min aijj2-ой шаг: в каждом столбце определяется минимальный и ближайшийк нему элемент и составляются n-разностей. j = int aˆij − aˆijaˆij = min aiji3-ий шаг: Из 2n элементов  j и  i выбирается максимальный.

Пустьсоответствующий элемент ( aˆij или aij* ) есть akl .2-ая итерацияЭлемент akl вносится в искомое решение.3-я итерацияСтрока k и столбец l удаляются из матрицы.К-ая итерацияАналогично, но матрица имеет порядок n-k.Замечания:1. Если среди элементов  i и  j одинаковые максимумы, тоанализируются соответствующие им минимальные элементы строки(столбца), из них выбирается минимум.2. Если и они одинаковые ( aij* и aˆij ), то выбирается 1-ый элемент впорядке просмотра.Пример (рассматривается специальная матрица, имеющая точное решение)1-ая итерация:два одинаковых максимальных элемента иодинаковые соответствующие им минимальные элементы (6).

Поэтомувыбирается 1-ый элемент в порядке просмотра a11 = 6 - в решение ( x11 = 1 ).2-ая итерация:i8 11 146 8 10456+3+2+1 j +2 +3 +4max( j и i ) = +4  a44 = 6 - вносим в решение ( x44 = 1 )3-я итерация:i811+368+2 j +2 a22 = 8 - в решение ( x22 = 1 )+34-ая итерация:8  x33 = 1E o = 6 + 6 + 8 + 8 = 28x11 = x44 = x22 = x33 = 1Объединенная задача выбора и «жадный» алгоритм ее решенияОбъединенная задача состоит из 3-х подзадач:1. Вычисление специальных коэффциентов матрицы А на основе aij .2. Проверка допустимости их использования (сравнение параметров).3.

Собственно задача выбора.Для точного решения: Tp = a1n2 + a2n2 + a3n3 .Для приблизительного решения: Tp = a1n2 + a2n2 + a3n2 ,где n – порядок матрицы, ai - коэффициенты пропорциональности, имеющиесмысл времени.Подготовительный этап алгоритмаОпределяется опорное решение и формируется на главной диагоналиматрицы.Пример3 4 5 64 6 8 10A=5 8 11 146 10 11 18E o = 38К-ая итерация состоит из следующих этапов.1) Определяется максимум и ближайший к нему элемент главнойдиагонали:max ai ,i = am,mint ai ,i = al ,l.2) Для элементов am,l и al ,m(am,l + al ,m )  am,m + al ,l - проверка допустимости.3) Если это условие выполняется, то строки m и l меняются местами(свойство «жадности»); переход к следующей итерации (собственнозадача выбора).4) Если это условие не выполняется, то k-ая итерация повторяется, новместо max ai ,i используется int ai ,i .Метод приращенийЭто приближенный, но достаточно быстрый меод реализации.1) Составление матрицы В, состоящей из приращений элементов в строкепри переходе от столбца к стобцу, т.е.B = bij = aij − ai , j +1 , i = 1,6, j = 1,5 .2) Находим минимальный элемент 1-го столбца матрицы В.3) Соотвествующий ему элемент исходной матрицы А заносится врешение с вычеркиванием его столбца и строки из матрицы А и т.д.Примерx21 = x32 = x53 = x64 = x45 = x16 = 1E o = 5 + 2 + 14 + 6 + 6 + 12 = 45Метод минимального элемента1) Находим минимальный элемент матрицы А.2) Вычеркиваем соответствующие строку и столбец.3) Соответствующий минимальный элемент заносится в решение.В новой матрице повторяется итерация и т.д.Задача выбора с вероятностным критериемaij = pij - вероятность выполнения i-ым исполнителем j-ой работы.nnE ( xij ) =  pij xij → max - эффективность выполнения всех работ;i =1j =1nnE ( xij ) =  pij xij → max - среднее число выполненных работ.i =1 j =1n xij = 1;i =1nxj =1ij= 1; xij = {0;1} .Замечание:Чтобы в первой задаче перейти от двойного произведения к двойнойсумме, необходимо:aij = ln pij → ln E = ...где ln p - монотонно возрастающая функция, следовательно, решениеисходной задачи E → max .Задача принятия решений с векторным критерием•••••••Многокритериальные задачиОни имеют место как в управлении, так и в ИСО, принятии решений.К общим требованиям относятся:Эффективность;Стабильность;Сложность;Эргатичность;Интеллектуальность;Робастность;Адаптивность..

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

Тип файла PDF

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

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

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