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

Определение 1:

Функция f (х₁, х₂…х_n), заданная на выпуклом множестве Х, называется выпуклой вниз (выпуклой) функцией, если для любых двух точек х¹, х² из Х и любого λ (от 0 до 1) выполняется соотношение:

Геометрически это означает, что график такой функции лежит ниже отрезка, соединяющего любые две точки.

Определение 2:

Функция f (х₁, х₂…х_n), заданная на выпуклом множестве Х, называется выпуклой вверх (вогнутой) функцией, если для любых двух точек х¹, х² из Х и любого λ (от 0 до 1) выполняется соотношение:

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

Существуют функции не являющиеся невогнутыми и невыпуклыми.

Определение 3:

Говорят, что множество допустимых решений ЗНП (задач нелинейного программирования) удовлетворяет условию регулярности (условию Слейтера), если существует, по крайней мере одна точка х  Х такая, что .

Рассмотрим задачу нелинейного программирования (ЗНП):

Здесь: f, g – известные функции

b_i – числа

Универсального метода решения (1)-(3) нет.

Определение 4:

Задача (1)-(3) называется задачей выпуклого программирования, если функция (1) является вогнутой (выпуклой), а ОДР, определяемая (1) и (3) – только выпуклая.

Теорема:

Любой локальный экстремум ЗВП (задачи выпуклого программирования) является и глобальным экстремумом.

Для решения ЗВП рассматривается метод множителей Лагранжа.

Определение 5:

Функцией Лагранжа задачи выпуклого программирования (1)-(3) называется функция (4):

Здесь y_i – множители Лагранжа

Определение 6:

Точка (Х⁰; Y⁰) = называется седловой точкой функции Лагранжа, если выполняется

для всех и .

38. Теорема Куна-Таккера.

Для ЗВП (задачи выпуклого программирования) (1)-(3), множество допустимых решений которой обладает свойством регулярности, точка Х⁰ = является оптимальным решением тогда и только тогда, когда существует такой вектор Y⁰ = , что точка (Х⁰; Y⁰) является седловой точкой функции Лагранжа.

Если функции f и g_i непрерывно дифференцируемы, то теорема Куна-Таккера может быть дополнена необходимыми и достаточными условиями, чтобы точка (Х⁰; Y⁰) была седловой точкой функции Лагарнжа, то есть являлась решением ЗВП. Эти условия носят название условий Каруша-Куна-Таккера:

Здесь и – значения соответствующих частных производных функции Лагранжа, вычисленных в седловой точке.

39. Общая постановка задачи динамического программирования (здп). Геометрическая интерпретация задачи динамического программирования.

ДП – метод оптимизации, когда процесс принятия решения может быть разбит на этапы (шаги, многошаговые операции).

ДП даёт возможность принять ряд последовательных решений (многошаговый процесс), обеспечивающий оптимальность развития процесса в целом.

Общая постановка ЗДП (задачи динамического программирования):

Рассматривается управляемый процесс.

Например, распределение средств между предприятиями, замена оборудования, пополнение запасов.

В результате управляемая система переводится из начального состояния S₀ в состояние S_n.

Пусть управление можно разбить на n шагов, то есть решение принимается последовательно на каждом шаге, а управление, приводящее систему из начального состояния S₀ в конечное S_n, представляет собой совокупность n пошаговых управлений.

Обозначим:

x_k – управления на каждом шаге (шаговое упарвление);

Х = (х₁, х₂…х_n) – управление процесса в целом, переводящее систему из начального состояния S₀ в конечное S_n;

S_k – состояние системы после k-ого шага.

Показатель эффективности операции – ЦФ, зависящая от начального состояния и управления:

ЗДП: определить такое управление Х, переводящее систему из S₀ в S_n, при котором ЦФ принимает наибольшее (наименьшее) значение. Такое управление называется оптимальным и состоит из последовательности оптимальных шаговых управлений:

Особенности модели ДП:

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

2). ЦФ в целом равна сумме целевых функций каждого шага (аддитивность).

Показатель эффективности k-ого шага процесса управления, который зависит от состояния S_k-1 в начале этого шага и управления х_k, выбранного на этом шаге, обозначается через . В задаче пошаговой оптимизации целевая функция полагается аддитивной, то есть:

3). Выбор управления на каждом k-ом шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи).

4). Состояние S_k после k-ого шага зависит только от предшествующего состояния S_k-1 и управления х_k (отсутствие последействия).

– уравнение состояний.

5). На каждом шаге управление х_k зависит от конечного числа управляющих переменных, а состояние S_k – от конечного числа параметров.

40. Принцип оптимальности и уравнения Беллмана.

При решении ЗДП (задачи динамического программирования) используют уравнение Беллмана: вместо ЗДП с фиксируемым числом n и начальным состоянием S₀ рассматривается последовательность задач, полагая k = 1, 2… при различных состояниях S – одношаговую, двушаговую…, используя Принцип оптимальности Беллмана:

Управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на n-ом шаге.

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

При выборе шага управления необходимо учитывать:

1). На каждом шаге делаются условные предположения о возможных вариантах об окончании предыдущего шага и проводя для каждого варианта условную оптимизацию.

2). Сначала оптимизируется последний n-ный шаг. Делая предположение об окончании (n-1) шага для каждого из них проводят условную оптимизацию n шага и определяют условное оптимальное управление х_k. Аналогично поступают для х_-1 шага.

На первом шаге обычно нет условных предположений, то есть состояние системы перед первым шагом известно. [Обратный ход]

Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и последующем шагах. Это управление является безусловным оптимальным управлением на первом шаге, и, зная его, определяют безусловное оптимальное управление на всех шагах. [Прямой ход]

41. Математическая модель ЗДП.

Дополнительно введём следующие условные обозначения:

S – состояние процесса

S_i – множество возможных состояний процесса перед i-тым шагом

W_i – выигрыш с i-того шага до конца процесса

Этапы составления математической модели:

1). Разбиваем задачу на шаги.

2). Выбор переменных, характеризующих состояние S и ограничений.

3). Определение множества шаговых управлений х_i.

4). Определение выигрыша:

5). Определение состояния S':

6). Составляем уравнение, определяющее условный оптимальный выигрыш на последнем шаге для состояния S:

7). Составление основного функционального уравнения ДП, определяющего условный оптимальный выигрыш для данного состояния S с i-того шага и до конца через известный условный оптимальный выигрыш с (i+1) шага и до конца:

42. Алгоритм решения задачи ди­намического программирования.

Алгоритм:

1). Определение множества в одном состоянии S_n для последнего шага.

2). Проведение условной оптимизации для каждого состояния S на последнем n шаге по формуле (5) и определение условного оптимального уравнения x(S).

3). Определение множества возможных состояний S: для i-того шага (i = 2, n-1).

4). Проведение условной оптимизации i-того шага (i = 2, 3… n-1) для каждого состояния S по формуле (7) и определение условного оптимального управления x_i(S).

5). Определение начального состояния системы S₁, оптимального выигрыша W₁(S₁), оптимального управления х₁(S₁) по формуле (7) при i = 1. Это и есть оптимальный выигрыш для всей задачи. [Обратный ход]

6). [Прямой ход]:

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

На первом шаге находится оптимальное управление , подставляем в формулу (5); находим состояние системы:

Для этого состояния находим оптимальное управление , подставляем в формулу (5) и так далее.