ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ (СЛОЖНЫМИ СИСТЕМАМИ) Для магистрантов направления – Информационные системы и технологии С.А.Пиявский 2011 год

ЦЕЛЬ ДИСЦИПЛИНЫ «МПД» ЛР1. Классические методы оптимизации (разработка математической модели и получение решения) ЛР2. Оптимизация динамических систем (Принцип максимума ) ЛР3. Методы принятия автономных решений (Выбор места работы и вакансии) ЛР4. Парные игры с нулевой суммой ЛР5. Некооперативные игры n игроков. ЛР6. Иерархические игры Дать теоретические знания и практические умения оптимального управления, преимущественно в сложных системах ЛАБОРАТОРНЫЕ РАБОТЫ Постановка задачи и структура оптимального управления сложными системами. Классические методы оптимизации (обзор и повторение). Оптимизация динамических систем. Методы принятия автономных решений. Теория игр. Парные игры с нулевой суммой. Игры нескольких игроков. Иерархические игры. ЛЕКЦИИ

Структура курса

Основная литература 1.Бурков В.Н., Коргин Н.А., Новиков Д.А. Введение в теорию управления организационными системами / Под ред. чл.-корр. РАН Д.А. Новикова. – М.: Либроком, – 264 с. 2.Пиявский С.А. Методы оптимизации и принятия решений, Самара, СГАСУ, Ларичев О.И. Теория и методы принятия решений, М., Логос, с. 4.Ларичев О.И. Вербальный анализ решений, ИСИ РАН – Мю: Наука, 2006 – 181 с. 5.

Постановка задачи в теории оптимального управления сложными системами

Хронология развития теории оптимального управления сложными системами ТАС – теория активных систем ТИ – теория искусственного интеллекта MD – Mechanism Design

Процессуальная схема деятельности

Классификация видов управления ОС

Функции управленческой деятельности Регулирование Учет Анализ

Пример управления предприятием с использованием методов оптимизации

Области применения теории принятия решений

Процессуальная схема деятельности ПРИНЯТИЕ РЕШЕНИЯ

Цикл принятия решения Осознание цели принимаемого решения Формирование набора критериев оптимальности принимаемого решения Описание множества альтернативных вариантов принимаемого решения Разработка и валидизация математической модели объекта принятия решения (переменные, соотношения, ограничения, коэффицинты) Выбор конкретной технологии принятия решения Формирование текущей версии оптимального решения Осмысление текущей версии оптимального решения РЕШЕНИЕ !!!

Пример принятия решения об объеме выпуска продукции предприятием

Простые примеры 1.Груз веса G, лежащий на горизонтальной плоскости, должен быть сдвинут приложенной силой F. Под каким углом к горизонту приложить ее ( с учетом трения), чтобы ее величина была наименьшей? 2.От канала шириной a под прямым углом к нему отходит канал шириной b. Стенки каналов прямолинейны. Найти наибольшую длину бревна, которое можно сплавить по этим каналам из одного в другой. 3.Под каким углом к оси OX надо провести прямую через точку (a,b), a, b>0, чтобы треугольник, образованный ею и осями координат, имел наименьший периметр? 4.Под каким углом к оси OX надо провести прямую через точку (a,b), a, b>0, чтобы её отрезок между положительными полуосями имел наименьшую длину? 5.Найти наибольшую площадь прямоугольника, вписанного симметрично в сектор круга радиуса с центральным углом 2.

6.Сечение бетонного канала представляет собой равнобедренную трапецию площадью S и высотой h, которые заданы из гидрологических соображений. Каким должен быть угол между боковой стороной и основанием, чтобы сумма длин нижнего основания и боковых сторон, определяющая расход материала, была наименьшей? 7.На какой высоте нужно повесить высящую в стороне от стола лампочку, чтобы получить максимальную освещенность поверхности стола? 8.Как проложить шоссе при транспортировке грузов от железнодорожной станции А до отстоящего от железной дороги на заданное расстояние пункта С, если стоимость провоза по железной дороге равна λ, а по шоссе - β (на единицу пути)? (Исследовать при различных соотношениях λ и β). 9.Найти соотношение между углами d1и d2 при преломлении света на границе двух сред (по принципу Ферма свет вбирает при преломлении между двумя точками путь, время прохождения которого минимально возможно, а скорость света в разных средах различна). 10.Найти кратчайшее расстояние от заданной точки (1,0) до эллипса 4х2+9х2=36.

Принятие решений при управлении процессами Пример 1. Расширение выпуска продукции и развитие технологического уровня предприятия

(Абсолютная величина с учётом того, что Uy может идти и на уменьшение объёма выпуска)

Принцип максимума Л.С.Понтрягина (необходимое условие оптимальности) Условия трансверсальности

Принятие многокритериальных решений Вектор частных критериев f1f1 f2f2 Пространство критериев Множество допустимых решений Y y1 y3 y2 y3 y1 y2

Формирование множества Парето f 2 (y) f 1 (y)

АНР (Analytic Hierarchi Process)

Пример. Выбор площадки для аэропорта Цель строительства аэропорта: прием и отправка большого числа пассажиров Критерий С3. Количество людей, подвергающихся шумовым воздействием Критерий С1. Стоимость строительства Критерий С2. Время в пути от аэропорта до центра города

Метод ELECTRE ранжирования многокритериальных альтернатив

Классические принципы оптимальности

Требования к методам принятия решений, пригодным для практического применения в системах поддержки принятия решений

Сопоставление различных методов принятия решений

МЕТОД ПРИНН (Принятия Решений в условиях Неустранимой Неопределенности)

Метод ПРИНН на линейной свертке двух критериев Равнозначные критерии Первый критерий «важнее» второго. Доказано, что его «весовой коэффициент ровно в три раза больше

Метод ПРИНН на свертке Гермейера двух критериев Равнозначные критерииПервый критерий «важнее» второго

По методу АНР, весовой коэффициент у «лучшего» критерия ровно в два раза больше, чем у «худшего»

Дополнительные постулаты метода ПРИНН 1) заменить множество всех допустимых СУН конечным набором типовых СУН, наилучшим образом представляющим все это множество, 2) организовать выбор наиболее рационального решения как процедуру последовательного согласования оценок его эффективности при различных типовых СУН

Принятие решений в играх Антагонистические Неантагонистические Игры с Природой Кооперативные Многошаговые Иерархические

ПАРНЫЕ ИГРЫ С НУЛЕВОЙ СУММОЙ Цена игры = 7,15 Цена игры = 0,7

Теорема Неймана. Каждая конечная игра с нулевой суммой имеет решение в смешанных стратегиях. Если чистая стратегия входит в оптимальную смешанную стратегию с вероятностью, отличной от нуля, то она называется активной. Теорема об активных стратегиях. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

Для того чтобы число v было ценой игры, а U* и Z*- оптимальными стратегиями, необходимо и достаточно выполнения неравенств:

Игры с природой Классические принципы оптимальности

НЕКООПЕРАТИВНЫЕ ИГРЫ N ИГРОКОВ - доминантные стратегии, - гарантирующие (максиминные) стратегии, - ситуации равновесия Нэша, - точки Парето, Доминантная стратегия Стратегия будет доминантной стратегией, если какая бы обстановка не складывалась, выигрыш игрока будет максимальным при выборе именно этой стратегии: B1B1 B2B2 B3B3 B4B4 A 1 –доминантная A2A A3A A4A

Доминантная стратегия игрока С - С 2 B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A С1С1 С2С2 С3С3 С4С4

Гарантирующая стратегия игрока С - С 2 B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A С 1 (min=1) С 2 (min=5) С 3 (min=2)С 4 (min=2) Гарантирующая стратегия - когда игрок полагает, что остальные игроки, несмотря на свои собственные интересы, будут действовать против него, а уж выбором своего действия он будет максимизировать то, что зависит от него самого

Ситуация равновесия Нэша Равновесие Нэша – когда ни один из агентов, в одиночку меняя свою стратегию на другую, не может увеличить свой выигрыш при условии, что остальные своих стратегий не меняют. B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A Платежная матрица игрока АПлатежная матрица игрока В

Равновесие по Нэшу для 3-х игроков

Точки Парето B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A Платежная матрица игрока А B1B1 B2B2 B3B3 B4B4 A1A A2A A3A A4A Платежная матрица игрока В

ИЕРАРХИЧЕСКИЕ ИГРЫ ДВУХ ИГРОКОВ Центр Агент Игра Штакельберга (принцип оптимизма) Игра Г1 (принцип гарантированного результата) Игра Г2 ( Стратегия Центра – Решение Агента – Решение Центра) Игра Г3 (Стратегия Агента – Решение Центра – Решение Агента) Игры Гк, к=4,…(многоэтапный обмен стратегиями) Теорема Кукушкина Игра Россия – Страны-изгои – НАТО Игра Россия - Украина

Игра Штакельберга (принцип оптимизма) Центр принимает решение, считая, что агент примет решение, наилучшее для Центра, и сообщает его Агенту, после чего Агент принимает свое решение

Игра Г1 (принцип гарантированного результата) Центр принимает решение, считая, что агент примет решение, наихудшее для Центра, и сообщает его Агенту, после чего Агент принимает свое решение

Игра Г2 (Стратегия Центра – Решение Агента – Решение Центра) Центр сообщает Агенту, какое решение примет в ответ на решение Агента; Агент принимает решение и сообщает его Центру; Центр принимает окончательное решение и сообщает его Агенту Стратегия своего решения, которую Центр сообщает Агенту А1 – Ц2 А2 – Ц1 А3 – Ц3 Рассуждения Агента А1 – Ц2 = 8 А2 – Ц1 = 4 А3 – Ц3 = 4 Решение Агента - А1 Решение Центра - Ц2 Выигрыш Центра = 9 Выигрыш Агента = 8

Игра Г3 (Стратегия Агента – Решение Центра – Решение Агента) Агент сообщает Центру свою стратегию принятия решения Центр в ответ сообщает Агенту, какое решение принял Агент, в соответствии со своей стратегией, принимает свое решение. Стратегия своего решения, которую Агент сообщает Центру Ц1 – А3 Ц2 – А3 Ц3 – А2 Рассуждения Центра Ц1 – А3 =1 Ц2 – А3 = 2 Ц3 – А2 = 5 Решение Центра - Ц3 Решение Агента - А2 Выигрыш Центра = 5 Выигрыш Агента = 10

Теорема Кукушкина Итак, Центру выгоднее всего играть игру Г2, если нельзя – то Г3, если ничего другого нельзя - то Г1. Центру измышлять более многоходовые игры бесполезно.