- •1. Введение 4
- •1.1. Основные методологические принципы
- •1.2. Основные определения
- •1.3. Этапы моделирования
- •5. Модели с обратной связью, динамическое проектирование.
- •2. О принципах принятия решений
- •2.1. Принятие решений в условиях неопределенности критерия.
- •Самостоятельная работа №1.
- •2.2. Принятие решения в условиях неопределенности состояния окружающей среды
- •Самостоятельная работа №2
- •3. Задачи выпуклого векторного программирования1.
- •3.1. Некоторые сведения выпуклого анализа
- •3.2. Понятие оптимальности по Слейтеру и Парето
- •3.3. Возможные (допустимые) и подходящие направления.
- •3.4. Задача выпуклого векторного программирования с ограничениями типа неравенства. Поиск подходящих направлений.
- •Самостоятельная работа №3.
- •3.4. Теорема Куна–Таккера для задачи выпуклого векторного программирования
- •Самостоятельная работа № 4.
- •4. Некоторые задачи теория игр
- •4.1. Анализ матричных антагонистических игр двух игроков .
- •Самостоятельная работа № 5.
- •4.2. Анализ матричных игр двух игроков с нулевой суммой в смешанных стратегиях.
- •Самостоятельная работа №6
- •4.3. Биматричные неантагонистические игры.
- •Самостоятельная работа № 7.
- •4.4. Взаимосвязь равновесий по Нешу и Парето в играх.
- •Самостоятельная работа № 8.
- •4.5. Динамические игры с полной информацией
- •Самостоятельная работа № 9
- •5. Задачи дискретного программирования.
- •5.1. Методы отсечения для решения задач целочисленного линейного программирования.
- •Самостоятельная работа № 10.
- •5.2. Комбинаторные методы решения задач целочисленного линейного программирования.
- •5.3. Алгоритм Ленд–Дойг.
- •Самостоятельная работа № 11.
- •5.4. Метод ветвей и границ для решения задачи о коммивояжере.
- •Самостоятельная работа № 12.
- •6.Транспортные задачи линейного программирования
- •6.1. Транспортная задача в сетевой постановке
- •Самостоятельная работа 13.
- •6.2. Транспортная задача в матричной постановке.
- •Самостоятельная работа 14.
- •7. Динамическое программирование и потоки в сетях
- •7.1. Задача оптимизации многошаговых процессов, задача о ранце.
- •Самостоятельная работа 15.
- •7.2 .Задача отыскания кратчайшего расстояния в сети между парами вершин
- •Самостоятельная работа 16.
- •7.2. Задача о максимальном потоке в сети.
- •Самостоятельная работа 17.
- •Литература.
3.2. Понятие оптимальности по Слейтеру и Парето
Рассмотрим понятие оптимальности в смысле Парето и в смысле Слейтера. В случае однокритериальной задачи оба эти понятия совпадают с обычным понятием оптимальности. Введем эти понятия.
Рассмотрим задачу i(x) min, i M, при ограниченияхxX,X Rn,M –конечное множество.
Введем следующие понятия и определения.
На множестве Х зададим отношение предпочтенияСлейтера и предпочтения Парето.
Определение 2.9.Пустьx,y X, будем говорить, чтоxпредпочтительнееy
а) по Парето и записывать тогда и только тогда, когдаK(x)K(y) для всех KM, и существуютK, для которых эти неравенства строгие.
б) по Слейтеру и записывать тогда и только тогда, когдаK(x)K(y) для всехKM.
В зависимости от того, какое будет взято на Хпредпочтение, возникают различные определения оптимальных точек.
Определение 2.10.Точкух*будем называть точкой локального оптимума по Парето (Слейтеру), если существует такое0>0, что для всех(0,0) на множестве 0(x0)X не содержатся точки ().
Определение 2.11. Множество всех точек локального оптимума по Парето (Слейтеру) назовем локальным множеством Парето (Слейтера).
Определение 2.12.Точкух*будем называть точкой глобального оптимума по Парето (Слейтеру), если вХне существует точекхтаких, что ().
Множество всех таких точек будем называть множеством Парето (Слейтера).
Точки глобального оптимума будем называть просто точками оптимума. Множество Р– Парето содержится во множествеS– Слейтера. Действительно, еслих*ÎР, т.е. вХне существует такогох, что. Но тогда тем более не существует , т.е. х*ÎS.Обратное, вообще говоря, не верно.
В случае, когда функции i(x), iM, выпуклые, множествоXтакже выпуклое, множества локального и глобального оптимума совпадают. Можно показать, чтоРS.
3.3. Возможные (допустимые) и подходящие направления.
Определение 2.13.Направление (вектор)s0n называется возможным (допустимым) в точкехХ, если существует такое0 >0, что для всех [0, l0] выполняетсях+lsÎX.
На рис. 2.6 показаны примеры возможных направлений.
Множество возможных направлений образует конус, который мы будем обозначать через Кр (х).
Определение 2.14. Возможное направлениеsв точкехХ назовемподходящимпо Парето (Слейтеру), если существует0 >0 такое, что для всех[0, l0] справедливо.()
Множество подходящих по Парето и подходящих по Слейтеру направлений образуют конусы, которые обозначим соответственно Кpp(x) иKps(x)., причемKps(x) Кpp(x), обратное, вообще говоря, не справедливо.
Определение 2.15. Функцию 0(x) назовем постоянной в точкех по направлениюs, если существует0 >0 такое, что для всехÎ [0,l0) функция 0(x+ls)= (x).
Определение.2.16.Будем говорить, что функцииi(x), iM, удовлетворяют условиюрегулярности R1(M), если для любыхх Rn , sRnиiMi(x) не является постоянной.
Замечание.Если функцииi(x),iM, удовлетворяют условию регулярности R1(M), то предпочтения по Слейтеру и Парето можно не различать. Если |M| = 1, то понятие предпочтения по Слейтеру и Парето можно не различать и при нарушении условия. Это вытекает из определения этих предпочтений.
Теорема.2 14.ПустьХ– выпуклое множество. Для того, чтобых*Хбыло точкой локального оптимума Парето (Слейтера) необходимо, чтобыKpp(х*) = (Kps(х*) = ).
Теорема. 2.15.Еслиi(x), i M выпуклые функции,Х– выпуклое множество, тогда любая точка локального оптимума, как по Парето, так и по Слейтеру, будет точкой глобального оптимума.