Методические указания к практическим занятиям по дисциплине «Методы и алгоритмы принятия решений», страница 10

p - правило выбора (инструкция как из Х, используя s, выделить Y).

R - линейно упорядочено:  "x,yÎX: x < y Ú x = y Ú x > y,

< -отношение предпочтения.           

(Например, R - множество действительных чисел, < - больше, меньше, равно.)

С: A ® R; "xÎА $ qÎR: q=С(x); 

С - критерий качества, целевая функция, функция предпочтения, функция полезности.

С - функционал в общем случае (динамические ЗПР, зависят от t).

s: С: A ® R; " x₁,x₂ÎА: x₁ предпочтительнее x₂ Û^df С(x₁) > C(x₂).

p: x^*=arg max C(x), С(·) - поэлементная функция выбора.

xÎX

< s, p > - однокритериальный механизм.

4.2. Методы решения. A={X=(x₁, x₂, …, x_n)} – множество альтернатив.

Статические: методы оптимизации (математическое программирование).

·  Отыскание безусловного экстремума:

·  Отыскание условного экстремума с ограничениями типа равенств:

  

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

·  Задачи математического программирования:

  

 

·  Задачи линейного программирования:

  

 

b_j, c_j, a_ij – постоянные.

·  Задачи квадратичного программирования:

  

 

b_j, c_j, a_ij, d_jk – постоянные.

·  Задачи выпуклого программирования:

  

 

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

  

 

·  Задачи геометрического программирования:

  

 

·  Задачи дискретного программирования.

Это задачи математического программирования, в которой есть ограничение на Х, состоящее в том, чтобы все (полностью дискретные задачи) или некоторые (частично дискретные задачи) компоненты вектора Х принимали только неотрицательные значения, т.е.

  

 - некоторая положительная величина, в частности,

·  Динамическое программирование (методы решения многошаговых задач)

Движение системы S состоит из m шагов (этапов); на i-м шаге управление u_i переводит систему из состояния s_i-1, достигнутого в результате (i-1)-го шага, в новое состояние s_i. Этот процесс перехода осуществляет функция f_i(s,u), и новое состояние определяется значениями s_i-1, u_i:

Таким образом, u₁, u₂, …, u_m переводят систему из начального состояния s₀ в конечное состояние s_m. Начальное состояние задано. Необходимо найти управляющие воздействия u₁, u₂, …, u_m таким образом, чтобы система перешла в допустимое конечное состояние и при этом заданная целевая функция F(s₀, u₁, s₁, u₂, …, u_m, s_m) достигла максимального значения F^*, т.е.

Метод динамического программирования применим лишь для аддитивной целевой функции  Кроме того, в задаче должно отсутствовать последействие: решения принимаемые на шаге оказывают влияние на  состояние s_i системы в момент i. Другими словами, процессы, описываемые функциями вида

не рассматриваются.

В основе решения задачи лежит принцип оптимальности Р.Беллмана: предположим, что, осуществляя управление дискретной системой, уже выбрано управление u₁, u₂, …, u_k и тем самым траектория состояний s₀, s₁, …, s_k. Необходимо завершить процесс, т.е. выбрать u_k+1, u_k+2, …, u_m (а значит и s_k+1, s_k+2, …, s_m). Тогда если завершающая часть процесса будет оптимальной в смысле достижения максимума функции

то и весь процесс будет оптимальным.

Пользуясь принципом оптимальности легко получить основное функциональное соотношение. Определим последовательность функций переменной s:

  

Здесь максимум берется по всем управлениям, допустимым на шаге k. Соотношение, определяющее зависимость от , принято называть уравнением Беллмана. Смысл функций  нагляден: если система на шаге k-1 оказалась в состоянии s, то  есть максимально возможное значение функции F. Одновременно с построением функций  находятся условные оптимальные управления u_k(s) на каждом шаге (т.е. значения оптимального управления при всевозможных предположениях о состоянии s системы на шаге k-1).  Окончательно оптимальные управления находятся последовательным вычислением величин