Посмотрим простейшие действия с этими определениями

Задачи теории принятия решений

Задача может решаться в условиях не изменяющегося информационного состояния ЛПР. Это статическая задача ТПР. В таких задачах решение получается за один шаг и задача называется одношаговой.

Если же информационное состояние ЛПР меняется, то задача называется динамической и для решения используются многошаговые процедуры.

 

Операция – это и есть некоторое мероприятие, т.е. система действий, предназначенных для достижения конкретной цели. В ТПР рассматриваются только управляемые операции (Controlled Opetaions), т.е. всегда имеется возможность выбирать какие-то параметры, характеризующие варианты их проведения.

 

Результат решения будет обозначаться буквой "x", а целевая функция буквой "f".

 

Обычно речь идет о максимизации или минимизации некоторой целевой функции, т.е. решается одна из таких задач:

F max или f min

 

В этом случае задача называется Задачей математического программирования. К обычному программированию на ЭВМ этот термин не имеет отношения. Он был введен классиком Дж. Данцигом в 40-ых годах.

 

Под термином "программа" Данциг имел в виду просто некоторый план работы предприятия. Любое решение задачи при учете ограничений называют допустимой программой (решением / планом). Наилучшая – оптимальным решением. Его и нужно найти.

 

 

Задача многокритериальной оптимизации

 

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

 

Решение – это вектор

 

x = (x1 … xn)

 

x e Rn[1]

 

А ограничения задается системой линейных неравенств:

 

// формула 19:36

 

Соответствующее множество решений, если оно не пустое, называется Выпуклым многогранником.

 

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

 

Если же ограничения такие же или те же самые, а целевая функция квадратичная, то задача называется Задачей квадратичного программирования. – Это как раз задача Морковица об оптимальном портфеле акций:

 

формула 19:37

 

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

 

f1, f2, …,fm min

 

f1, f2, …,fm max

 

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

снижение себестоимости изделия,

повышение надежности,

снижение веса

и т.д.

Здесь мы имеем дело с задачами многокритериальной оптимизации.

 

На первый взгляд можно обозначить

 

f (x) = ( f₁(x) … f_n(x)) max (min)

 

Однако, задача многокритериальной оптимизации может вообще не иметь решения. Такие задачи называются "Некорректные".

 

x = (x₁ … x_n)

 

x_k является оптимальным решением задачи математического программирования для k-ой компоненты решения fk min

 

Но для векторной целевой функции должно быть одно x такое, что оно должно совпадать со всеми x_k, но оптимальное решение для fi компоненты функции м.б. совсем не оптимальной для fj.

 

 

Например, пусть у нас n = 2

 

n = 2

x = (x1, x2)

 

x1(x) = x1 min

x2(x) = x2 min

 

При условии, что множество допустимых решений таково:
G = {(x₁, x₂) (x₁ - 2)² + (x₂ - 2)² <= 1}

 

фото 19:49

 

Оказывается, что одно решение не совпадает с другим и это решение называется Некорректным.

 

Множество Парето

 

Если задача является некорректной, то можно попытаться найти некоторое компромиссное решение, но этот компромисс должен предложить ЛПР. Он должен сказать, в каком смысле выбранное компромиссное решение лучше остальных. Один из путей выбора компромисса заключается в том, что из набора скалярных целевых функций f₁ – f_n выбирается некоторая f_i , а все остальные переводятся в ограничения:

 

фото 19:57

 

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

непонятно, как выбирать основную целевую функцию,

непонятно, как выбирать ограничения

Поэтому на практике используется другой подход, связанный с понятием "Множество Парето".

 

Будем говорить, что допустимое решение x1 предпочтительнее допустимого решения x2, если выполняется следующее условие:

 

f_k (x₁) <= f_k (x₂) k = 1 … n

 

f = (f1 … fm)

Отношение строгой предпочтительности

Два решения называются эквивалентными, если там "..." равно.

Из того, что два решения эквивалентны, не вытекает, что x1 == x2

 

Посмотрим простейшие действия с этими определениями.

 

(x₁ > x₂) ^ (x2 > x3) => (x1 > x3)

 

(x1 ~ x2) ^ (x2 …

 

 

Пример с окружностью

Берем произвольную точку (напр. в центре).

Если нам нужно улучшить по координате x1, то нужно двигаться к x1.

 

Если мы находимся внутри круга, то существует такая точка, которая лучше по координате x2, но такая же по координате x1.

 

Если же мы выходим на границе некоторой точки C, то оказывается, что ситуации такова: как только мы движемся по границе, то улучшение по координате x2 приводит к ухудшению по координате x1 и наоборот.

 

Т.е. как бы мы не двигались, мы не можем одновременно улучшить решение. И таким образом попадаем во множество, где улучшение по одному критерию приводит обязательно к ухудшению по другому критерию. Это множество называется Множеством Парето. Обозначается буковой Омега .

 

Это множество может рассматриваться как обобщенное решение задачи многокритериальной оптимизации.

 

Наличие множества Парето характерно прежде всего для экономических задач. Для нашей задачи мы можем найти это множество аналитически.

 

(x1 - x2) …

фото 20:13

 

Множество Парето будет состоять из тех векторов…

 

Однако, множество Парето предполагает наличие множества решений. Для практики нужно одно решение. Для этого существуют специальные методы решения… (см. след. лекцию).

 

 

степень