Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

полнения различных работ, и условия невозможности выполне-

ния работы несколькими исполнителями. Целесообразно нахо-

дить распределение исполнителей, максимизирующее суммарное

качество выполнения всех работ.

Математическая модель назначений имеет вид:

∑

→ max

при ограничениях

∑

= 1, i = 1,…, n,

∑

= 1, j = 1,…, n,

∈ {0,1} , i = 1,…, n; j = 1,…, n.

К такой же модели могут быть сведены ситуации, когда ис-

полнителей больше, чем работ, или наоборот.

4. Модель оптимального планирования выпуска продукции

Пусть предприятие выпускает (n) наименований продукции,

в производстве которых используется (m) видов ресурсов.

Обозначим:

– объем затрат i-го вида ресурса на производство единицы j-

го вида продукции; i = 1,..., m; j = 1,..., n;

- полные объемы ресурсов, имеющихся на предприятии; i =

1,...,m;

- стоимость реализации j-го вида продукции на рынке това-

ров; j = 1,.. ..., n;

- целесообразный объем выпуска продукции j-го вида; j = 1,..

..., n.

Необходимо составить такой план выпуска продукции, ко-

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

отклонения от целесообразного объема выпуска.

В этом случае план выпуска продукции можно описать век-

тором x = ║x

║, где x

характеризует объем выпуска j-го вида про-

дукции. В качестве ограничений выступает требование выпуска

продукции в условиях имеющихся ресурсов. Здесь целесообраз-

но находить решение, минимизирующее суммарные отклонения

объемов выпуска продукции от заданных.

Математическая модель такой задачи имеет вид:

∑

)

→ min

∑

≤ b

, i=1,...,m;

≥ 0, j = 1,…,n.

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

такой задачи равно 0 (ресурсов достаточно для выпуска всех ви-

дов продукции), задачу планирования оптимального выпуска про-

дукции целесообразно ставить в виде:

∑

→ max

∑

≤ b

, i=1,...,m;

≤ x

≤ D

, j = 1,…,n.

Здесь D

– верхний предел целесообразного выпуска про-

дукции j-го вида.

5. Модель оптимального программного управления

линейным динамическим объектом

Задача нахождения оптимальной программы управления

линейным динамическим объектом может быть решена методами

оптимального управления динамическими системами (методы,

основанные на принципе максимума Л.С.Понтрягина или на прин-

ципе оптимальности Р.Беллмана). Однако в ряде случаев исход-

ную динамическую модель целесообразно свести к статистиче-

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

программирования, поскольку в этом случае многие сложные ог-

раничения, накладываемые как на переменные состояния, так и

на допустимые управления, которые крайне усложняют двухто-

чечную краевую задачу, легко учитываются алгоритмами матема-

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

Пусть изменение состояния линейного объекта управления

описывается системой дифференциальных уравнений

(t)x



= A(t)x + B(t)u ,

где x - n-мерный вектор состояния;

u - r-мерный вектор управления, под воздействием которого

изменяется состояние.

Необходимо найти программу управления u=u(t) на интер-

вале времени t∈(t

], позволяющую перевести линейный дина-

мический объект из состояния x(t

) в состояние x(t

), и достав-

ляющую максимум показателю качества J(x,u)

J(x,u) =

∫

F(t,x,u) dt → max

Возможные состояния и управления должны удовлетворять

ограничениям x(t)∈X, u(t)∈U, t∈(t

],, где X и U - соответствен-

но множества допустимых состояний и управлений.

Состояние линейного объекта управления в любой момент

времени определяется в соответствии с формулой Коши как

x(t) = Ф(t,t

) x(t

) + Ф(t,t

)

∫

-1

(τ,t

) B(τ) u(τ) dτ ,

где Ф(t,t

) - n×n-мерная фундаментальная матрица решений од-

нородной системы дифференциальных уравнений (переходная

матрица).

Проводя дискретизацию по времени, т.е. разбивая весь ин-

тервал (t

] на N подынтервалов, последнее выражение можно

переписать

x(k) = Ф(t

k-1

)x(k-1) + Ф(t

k-1

)

∫

1-k

-1

(τ,t

k-1

)B(τ)dτ u(k-1), k = 1,...,N

Тогда задача нахождения оптимального программного

управления будет иметь вид:

∑

F(x(k),u(k-1)) → max

x(k) = Ф(t

k-1

)x(k-1) + Ф(t

k-1

)

∫

1-k

-1

(τ,t

k-1

)B(τ)dτ u(k-1), k = 1,...,N

x(k) ∈ X, u(k-1) ∈ U, k = 1,…,N,

x(0) = x(t

), x(N) = x(t

) .

Данная задача имеет N

= N×(m+r) переменных, соответст-

вующих различным значениям x(k), u(k-1), k = 1,...,N. Вводя новый

вектор неизвестных переменных y, размерности N

задачу опти-

мального программного управления линейным динамическим

объектом можно представить в форме задачи математического

программирования. Размерность такой задачи при большом N

может быть достаточно велика, тем не менее, в ней достаточно

просто учитываются сложные ограничения на возможные состоя-

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

Рассмотренные примеры задач математического програм-

мирования относятся

к задачам различных классов. Задачи 1, 2

являются задачами линейного программирования, задача 3 явля-

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

4, 5 представляют собой задачи нелинейного программирования.

2.3. Элементы выпуклого анализа задач оптимизации

Итак, рассматриваем задачу выбора решения в конечно-

мерных пространствах, поставленную в виде (2.1)

x* = arg max f(x), где ∆ = {x∈R

│ϕ

(x)≤ b

, i = 1,…., m }.

x∈∆

Рассмотрим ряд определений и утверждений, связанных с

заданием свойств ∆ и f(x), которые используются в выпуклом

анализе для исследования таких задач оптимизации.

Пусть задано множество D ⊂ R

♦ Точка x∈R

называется п р е д е л ь н о й точкой множест-

ва D, если в любой окрестности этой точки содержится бесконеч-

но много точек из D, отличных от x.

♦ Если точка x∈D не является предельной, то она называется

и з о л и р о в а н н о

й .

♦ Точка x∈D называется в н у т р е н н е й, если существует

такая ее ε-окрестность U(x,ε), что все точки этой ε-окрестности

принадлежат D; U(x,ε) ⊂ D.

♦ Точка x∈D называется г р а н и ч н о й, если в любой ε- ок-

рестности этой

точки содержатся как точки из D, так и точки, не

принадлежащие D. Множество, состоящее из всех граничных то-

чек называется г р а н и ц е й D.

♦ Множество D ⊂ R

называется з а м к н у т ы м, если оно со-

держит все свои предельные точки.

♦ Множество D ⊂ R

называется о г р а н и ч е н н ы м, если

∃C>0 │∀x∈D ║x║ < C.

♦ Множество D ⊂ R

называется в ы п у к л ы м, если для

∀x,y ∈ D оно содержит отрезок, соединяющий эти точки, т.е.

∀x,y∈D ∀α∈[0,1] (αx + (1-α)y) ∈ D

♦ Пересечение выпуклых множеств является выпуклым мно-

жеством.

♦ Ограниченное замкнутое множество называется к о м п а к -

т н ы м.

Отделимость выпуклых множеств

♦ Г и п е р п л о с к о с т ь ю Г в R

называется множество ви-

да

Г = { x∈R

│(c,x) = a }, где c ≠ 0 .

В пространстве R

гиперплоскость Г задает:

- два замкнутых полупространства: Г

(-)

= { x ∈ R

│(c,x) ≤ a}

(+)

= { x ∈ R

│(c,x) ≥ a}

- два открытых полупространства: G

(-)

= { x ∈ R

│(c,x) < a}

(+)

= { x ∈ R

│(c,x) > a}

♦ О п о р н о й гиперплоскостью Г выпуклого множества D в

некоторой его граничной точке (x) называется гиперплоскость,

проходящая через (x) и разбивающая R

на два полупространства

(+)

и Г

(-)

, в одном из которых полностью содержится D.

♦ Множества D и Q называются с т р о г о о т д е л и м ы -

м и друг от друга, если существует такая гиперплоскость Г, что

множества D и Q принадлежат различным открытым полупро-

странствам, определяемым Г.

♦ Множества D и Q называются с о

б с т в е н н о о т д е -

л и м ы м и, если они принадлежат различным закрытым полу-

пространствам.

♦ Любые два непересекающиеся, выпуклые множества строго

отделимы.

Таким образом, если D представляет собой объединение

непересекающихся, выпуклых множеств, то поиск оптимального

решения можно искать на каждом

множестве независимо от дру-

гих. Глобальный оптимум находится путем сравнения оптималь-

ных выборов на каждом множестве.

Представление выпуклых множеств

♦ Точка x называется л и н е й н о й к о м б и н а ц и е й

точек x

, x

,..., x

, если существуют такие числа α

, α

,…., α

∈ R

что

x =

∑

Если же ∀α

≥ 0 и

∑

= 1, то линейная комбинация точек назы-

вается в ы п у к л о й комбинацией.

♦ Точка (x) множества D называется к р а й н е й (угловой)

точкой, если не существует точек y,z ∈ D, таких, что

x = (αy + (1-α)z) при некотором α∈(0,1).

Т.е. не существует в D отрезка с концами y,z, для которого

(x) бы-

ла бы внутренней точкой.

Утверждение.

Любая точка (x) выпуклого, замкнутого и ограниченного мно-

жества D может выть представлена в виде выпуклой комбинации

конечного числа крайних точек этого множества.

♦ Количество крайних точек, необходимых для представления

точки (x) выпуклого, замкнутого и ограниченного множества D, не

превышает числа p = dim(D) + 1.

Таким образом, множество всех допустимых решений Δ в

задаче математического программирования можно представить

виде выпуклой комбинации крайних точек Δ.

Выпуклые функции. Дифференцируемость

♦ Функция f: D → R

, заданная на выпуклом множестве D ⊆ R

называется в ы п у к л о й (выпуклой вниз) на D, если

∀x,y ∈ D, ∀α∈(0,1) f(αx + (1-α)y) ≤ αf(x) + (1-α)f(y),

и называется с т р о г о в ы п у к л о й , если

∀x,y ∈ D, ∀α∈(0,1) f(αx + (1-α)y) < αf(x) + (1-α)f(y).

♦ Если f(x) - выпуклая функция, то h(x) = -f(x) -

вогнутая (вы-

пуклая вверх) функция. Действительно, тогда

∀x,y ∈ D, ∀α∈(0,1) h(αx + (1-α)y) ≥ αh(x) + (1-α)h(y).

Выпуклая функция

f(x) f(αx + (1-α)y)

αf(x) + (1-α)f(y)

f(y)

x y

αx + (1-α)y

♦ Л и н и я у р о в н я (с) функции f(x) - множество точек вида

{x∈D │f(x) = c}.

♦ Множество A = {x∈D │f(x) ≤ c}, ограниченное линией уровня

выпуклой функции f(x), заданной на выпуклом множестве D, вы-

пукло.

♦ Функция f(x) называется н

е п р е р ы в н о й на D в точке

, если для ∀δ>0 ∃ε>0, такое что для ∀x∈U(x,ε) ║f(x) – f(x

)║ ≤ δ.

♦ Выпуклая функция f(x), определенная на выпуклом множе-

стве (x∈D), является непрерывной в каждой внутренней точке D.

♦ Г р а д и е н т ∇f(x

) функции f(x) в точке x

∈D, представ-

ляет собой вектор

)f(x

,..., )f(x

),f(x

)f(x grad )f(x

⎟

⎠

⎞

⎜

⎝

⎛

==∇

Вектор градиента показывает направление возрастания значений

функции.

Геометрический смысл градиента.

линия уровня f(x

)

∇

(

)

∗

♦ Функция f(x), определенная в окрестности x

, называется

д и ф ф е р е н ц и р у е м о й в x

, если ∃∇f(x

), такой, что в ок-

рестности точки x

функция f(x) представима в виде

f(x) = f(x

) + ∇

f(x

)(x - x

) + o║x - x

║ (2.2)

♦ Функция f(x) дифференцируема в x

, если она имеет в ок-

рестности этой точки частные производные (δf/δx

), непрерывные

в точке x

♦ Функция f принадлежит классу С

, если она непрерывна.

♦ Функция f принадлежит классу С

, если она непрерывно

дифференцируема - имеет непрерывные частные производные

по каждому из своих аргументов. (Называется "С

- гладкая" или

просто "гладкая").

♦ Функция f принадлежит классу С

, если у нее непрерывны

все частные производные по каждому из своих аргументов вплоть

до к-го порядка.

Анализируя свойства выпуклости множества допустимых

решений и целевой функции, можно исследовать существование

и единственность решения задачи математического программи-

рования. В частности, существует утверждение, что, если f(x) во-

гнута (выпукла вниз) на выпуклом, замкнутом и

ограниченном

множестве Δ, то решение задачи математического программи-

рования (2.1) существует; такие задачи называются задачами

выпуклого математического программирования.

2.4. Необходимые и достаточные условия существования

оптимального решения. Теорема Куна-Таккера

В задаче математического программирования (2.1)

x* = arg max f(x), где ∆ = {x∈R

│ϕ

(x) ≤ b

, i = 1,…., m } , (2.3)

x∈∆

будем полагать, что f(x)-вогнутая (выпуклая вверх) функция, и все

функции ϕ

(x), i = 1,…., m выпуклы. Тогда множества ϕ

(x)≤ b

, i =

1,…, m, ограниченные линией уровня выпуклой функции, выпук-

лы, а, следовательно, и Δ - выпукло, т.к. как является пересече-

нием m выпуклых множеств.

Такая задача является задачей выпуклого программирова-

ния, и для нее можно сформулировать необходимые и достаточ-

ные условия оптимальности решения [13]. Такие условия задают-

ся теоремой Куна-Таккера, которая представляет собой обобще-

ние классического метода множителей Лагранжа для определе-

ния экстремума функции при наличии ограничений.

Для формулирования необходимых и достаточных условий

будем рассматривать функцию Лагранжа в виде

L(x, μ) = f(x) + μ

(b - ϕ(x)) = f(x) +

∑

- ϕ

(x)), (2.4)

где μ

≥ 0, i=1,…, m - множители Лагранжа.

Множество Δ является р е г у л я р н ы м, если ∃x∈∆, та-

кое, что f(x) < b, т.е. в Δ существует внутренняя точка (условие

Слейтера).

Сформулируем следующую теорему.

Теорема (Куна-Таккера)

Для того, чтобы точка x* была решением задачи выпуклого

программирования (2.3) в условиях регулярности Δ необходимо и

достаточно существование такого вектора μ*≥0, чтобы для точки

(x*,μ*) выполнялись условия

L(x, μ*) ≤ L(x*, μ*) ≤ L(x*, μ) . (2.5)

Условия (2.5) являются условиями существования седло-

вой точки функции Лагранжа - функции двух векторных аргумен-

тов. Точка (x*, μ*) называется с

е д л о в о й точкой функции Ла-

гранжа L(x, μ), x ≥ 0, μ ≥ 0.

Поясним данную теорему, для этого подставим (2.4) в (2.5),

тогда

f(x) + μ*

(b - ϕ(x)) ≤ f(x*) + μ*

(b - ϕ(x*)) ≤ f(x*) + μ

(b - ϕ(x*)). (2.6)

Рассмотрим вторую группы неравенств в (2.6), откуда

можно заключить, что

μ*

(b - ϕ(x*)) ≤ μ

(b - ϕ(x*)).

Т.к. μ* = min μ, при ∀μ ≥ 0, то отсюда следует, что последнее

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

(b - ϕ(x*)) ≥ 0.

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

она д о п у с т и м а (x* ∈ Δ).

Далее, поскольку последнее неравенство должно выпол-

няться при

∀μ ≥ 0, и, как было показано, (b - ϕ(x*)) ≥ 0, то отсюда

непосредственно следует, что

μ*

(b - ϕ (x*)) = 0. (2.7)

Условия (2.7) называются условиями д о п о л н я ю щ е й

н е ж е с т к о с т и [13]. Данные условия устанавливают связь μ*

и x*. Смысл их в том, что

- если μ*

= 0, то b

- ϕ

(x*)) > 0 или, если b

- ϕ

(x*)) > 0, то μ*

= 0;

- если μ*

> 0, то b

- ϕ

(x*)) = 0 или, если b

- ϕ

(x*)) = 0, то μ*

> 0.

Рассмотрим первую группу неравенств в (2.6). С учетом

условий дополняющей нежесткости (2.7) их можно переписать как

f(x) + μ*

(b - ϕ(x)) ≤ f(x*),

т.к. μ*

(b - ϕ(x)) ≥ 0, x∈∆, то для ∀x∈∆ выполняется f(x) ≤ f(x*),

следовательно, точка x* - о п т и м а л ь н а на ∆.

Таким образом, если выполняются условия теоремы Куна-

Таккера, то решение x* допустимо и оптимально, т.е. является

решением задачи (2.3).

Приведем другую запись теоремы Куна-Таккера. Для этого

обозначим

L(x, μ*) = min L(x, μ) = Ф(x), тогда max Ф(x) = L(x*, μ*).

μ x

Cледовательно, L(x*, μ*) = max min L(x, μ)

x μ

С другой стороны введем обозначение

L(x*, μ) = max L(x, μ) = Ψ(μ), тогда min Ψ(μ) = L(x*, μ*).

x μ

Cледовательно, L(x*, μ*) = min max L(x, μ)

μ x

Тогда

max min L(x, μ) = L(x*, μ*) = min max L(x, μ)

x μ μ x

Таким образом, задачи поиска максимума по x и задачи

поиска минимума по μ функции Лагранжа L(x,μ) тесно связаны.

max min L(x, μ) = min max L(x, μ)

x μ μ x

Ф(x) Ψ(μ)

Задачи max Ф(x) и min Ψ(μ) называются д в о й с т в е н -

н ы м и (сопряженными) задачами и должны решаться совмест-

но. Это положение должно учитываться при построении алгорит-

мов поиска оптимальных решений.