Выпуклое множество

- множество, которое вместе с двумя принадлежащими ему точками обязательно содержит отрезок, соединяющий эти точки.

Def 1

ф-я f(x1,…,xn), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек x1, x2 и любого l=(‾0,1‾)? выполняется соотношение:

f(lx2++(1-l)x1) clf(x2)+(1-l)f(x1) (14)

Def 2

ф-я f(x1,x2,…,xn) на выпуклом множестве X называется вогнутой,если для любых 2 точек x1, x2 и любого l выполняется соотношение:

f(lx2+(1-l)x1)³ lf(x2)+(1-l)f(x1) (15)

Def 3

Говоря, что множество доп. решений задачи (11)-(13) удовлетворяет условию регулярности, если сущ-ет по кр. мере xiÎОДР, такая ,что gi(xi)<bi, где x=‾1,n‾

Def 4

Задача (11)-(13) наз-ся задачей выпуклого программирования, если функция f(x1,…,xn) явл вогнутой (выпуклой), а функция gi(x), i=‾1,m‾ - выпуклой.

Теорема:

Любой локальный max (min) ЗВП является глобальным max (min).

Def 5

Функцией Лагранжа ЗВП (11)-(13) наз-ся функция

L(x₁,…,x_n,y₁,…,y_m)=f(x₁,…,x_n)+ (16),

где y₁,…,y_m - множители Лагранжа.

Def 6

Точка (x₀,y₀)=(x₁⁰,…,x_n⁰,y₁⁰,…,y_m⁰) называется седловой точкой функции Лагранжа, если

L(x₁,…,x_n,…,y₁⁰,…,y_m⁰) £ L(x₁⁰,…,x_n⁰,y₁⁰,…,y_m⁰), для всех x_j³0, j= ‾1,n‾, а y_i³0, i=‾1,m‾

Теорема 2

(Теорема Куна-Таккера) (о седловой точке)

Для ЗВП (11)-(13) множество допустимых решений, к-е обладает свойством регулярности

x_j³0, y_i³0, x₀=(x₁⁰,…,x_n⁰)

x₀ явл. оптимальным планом, когда существует такой вектор y₀=(y₁⁰,…,y_m⁰), y_i⁰ ³0, i=‾1,m‾ , что

(x0,y0) – седловая точка функции Лагранжа.

Для решения задач этого типа разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с понятием градиента целевой функции и основной идеей о том, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту. К ним относятся метод градиентного спуска, метод сопряженных градиентов и т.д. Но есть и методы, основанные на других идеях  метод штрафных функций, многочисленные варианты метода случайного поиска и т.д.

Динамическое программирование

Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

1. Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.

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

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

4. Выбор решения (управления) на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.

Задача о выборе траектории, задача последовательного принятия решения, задача об использовании рабочей силы, задача управления запасами — классические задачи динамического программирования.