Контрольное задание по «Методы оптимальных решений»

Вогнутость функции ценности в области выигрышей влечет за собой несклонность к риску, а выпуклость функции ценности в области потерь - склонность к нему.

Склонность к риску - это устойчивый эффект, особенно когда вероятность потерь значительна.

 

59. Сформулируйте постановку задачи многокритериальной оптимизации.

 

Задача многокритериальной оптимизации формулируется следующим образом:

  (29)

Где это k ( ) целевых функций. Векторы решений   относятся к не пустой области определения S.

Задача многокритериальной оптимизации состоит в поиске вектора целевых переменных, удовлетворяющий наложенным ограничениям и оптимизирует векторную функцию, элементы которой соответствуют целевым функциям. Эти функции образуют математическое описание критерия удовлетворительности и, как правило, взаимно конфликтуют. Отсюда, «оптимизировать» означает найти такое решение, при котором значение целевых функций были бы приемлемыми для постановщика задачи.

 

60. Что такое множество достижимых критериальных векторов?

 

Числовое m-мерное пространство Em, координатами которого являются  yi=fi(X), называется критериальным пространством. Очевидно, что каждому Х можно поставить в соответствие точку в критериальном пространстве. Если же решение Х допустимо, то соответствующая точка в Em, определяемая вектором Y, является достижимой. Множество таких точек в критериальном пространстве называется множеством достижимости (достижимых векторов).

 

61. Дайте определение доминирования и оптимальности по Парето.

 

В случае доминирования при переходе от решения X2 к X1 ничего не будет проиграно ни по одному из частных критериев, но в отношении j – го частного критерия точно будет получен выигрыш. Говорят, что решение X1 лучше (предпочтительнее) решения X2.

Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.

Оптимальность по Парето — такое состояние системы, при котором значение каждого частного критерия, описывающего состояние системы, не может быть улучшено без ухудшения положения других элементов.

Эффективное решение называется решением, оптимальным по Парето, или Парето-оптимальным решением.

 

62. Что такое эффективные решения и паретова граница.

 

Допустимое решение называется эффективным, если не существует , такого что , т.е. для любого не выполняется, хотя бы одно из условий:

для всякого ;

существует такое что .

Допустимое решение называется слабо эффективным (или оптимальным по Слейтеру), если не существует , такого, что строго, т.е. для всякого существует число , такое, что

. (30)

Паретова граница – это множество критериальных векторов, оптимальных по Парето.

 

63. Назовите основные подходы к построению методов поиска решений в задачах многокритериальной оптимизации.

 

- Интерактивность

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

- Эволюционные методы

Упоминания о применении генетических алгоритмов для решения задачи многокритериальной оптимизации относятся к концу 1960-х.

 

64. Приведите примеры многошаговых систем в экономике.

 

Динамическое моделирование – многошаговый процесс, каждый шаг соответствует поведению экономической системы в определенный временной период.

 

65. В чем состоят особенности динамических задач оптимизации?

 

Особенностью этих задач является то, что процесс принятия решений в них распадается на ряд последовательных этапов. Естественно, что многоэтапность ассоциируется, прежде всего, с развитием процесса во времени. Поэтому динамическое программирование хорошо применимо к динамическим задачам, в которых должно быть принято не однократное оптимальное решение, а ряд последовательных во времени решений, обеспечивающих оптимальность всего развития в целом.

 

66. Приведите примеры динамической задачи оптимизации.

 

Маршрутизация запросов в распределенном хранилище информации представляет собой задачу динамической оптимизации.

 

67. Что такое многошаговые динамические модели?

 

Это модели, в которых текущие управляющие решения "проявляются" как в период, относящийся непосредственно к моменту принятия решения, так и в последующие периоды.

 

68. Что такое непрерывные динамические модели?

 

Более сложные линейные динамические системы могут быть описаны, если допустить, что не только сами значения уровня вынуждающей функции , но также скорость ее изменения и более высокие производные влияют на поведение системы.  Поэтому общая модель для описаний (непрерывных) динамических систем — это линейное дифференциальное уравнение:

                         (31)

Непрерывная модель может представляться как система дифференциальных уравнений 1-го порядка в явной форме Коши.

 

69. Что такое управление и переменная состояния в динамических моделях?

 

На каждом шаге необходимо определить два типа переменных - переменную состояния системы Sk, переменную управления xk. Переменная Sk определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состоянии  S на этом шаге можно применить некоторые управления, которые характеризуются переменной xk которые удовлетворяют определенным ограничениям и называются допустимыми.

 

70. Приведите примеры задания критерия в динамических задачах оптимизации.

 

В задачах, решаемых методом динамического программирования, значение целевой функции (оптимизируемого критерия) для всего процесса получают простым суммированием частных значений fi(x) того же критерия на отдельных шагах, то есть

                                                                              (32)

 

71. В чем состоит метод динамического программирования в многошаговых задачах оптимизации?

 

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

 

72. Сформулируйте принцип оптимальности и запишите уравнение Беллмана.

 

Метод динамического программирования состоит в том что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага.

Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Это основное правило динамического программирования, сформулированное Беллманом, называется принципом оптимальности.

Уравнение Беллмана:

                                (33)

 

73. Как задача оптимизации многошаговой системы сводится к задаче математического программирования?

 

Задача, которая состоит в выборе из заданного допустимого множества значений ряда переменных, называемых средствами («инструментами») таких значений, при которых достигается максимум заданной целевой функции называется задачей математического программирования.

Задачи, в которых время рассматривается не как непрерывная, а как дискретная величина называются многошаговыми задачами оптимизации.

Состояние системы в момент времени t задается вектором xt, а управление в момент t  задается вектором ut. Состояние в момент t+1 задается соотношением

, t= t0, t0+1, t0+2,…, t1,                          (34)

где  ft(…) – вектор составленный из непрерывно дифференцируемых функций текущего состояния и текущих значений управляющих параметров. Предполагается, что фиксировано начальное состояние x0

Возьмем в качестве параметров многошаговой задачи оптимизации начальный момент времени и начальное состояние. Тогда функция оптимального поведения равна оптимальному значению целевой функции в задаче с начальным состоянием х и начальным моментом времени t:

Оптимальное значение целевой функции рассматриваемой задачи равно

Согласно принципу оптимальности Беллмана,

Это означает, что оптимальное значение целевой функции в задаче с начальным состоянием х и начальным временем t равно оптимальному значению суммы двух слагаемых: функции в момент t и оптимального значения функции в момент t.

Используя уравнение (34), можно представить рекуррентное соотношение в виде

Граничное условие

показывает, что оптимальное значение целевой функции в задаче с начальным состоянием xi в момент t1 просто совпадает со значением функции конечных параметров, рассчитанным при х = x1, t = t1.

Таким образом, получена задача математического программирования.