Metody_optimizatsii

В

пособи и

рассматри вается

ш и роки й

круг

задач

математи ческого

программи ровани я.

И зложены анали ти чески е и

чи сленны е методы

реш ени я задач

безусловной и

условной опти ми зац и и .

При менени е каждого метода и ллю стри руется

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

Пособи еподготовлено накафедрематемати чески х методови сследовани я операц и й

факультетаПМ М

В оронежского государственного уни верси тета. Рекомендуется для

§

1.

П о ста но в ка

за да чи ма тема тическо го

пр о гр а ммир о в а ния

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

нахождени я

в векторном пространстве Rn

такого вектора x *,

которы й

обеспечи вает опти мальное

(ми ни мальное

и ли

макси мальное)

значени е

функц и и

f (x) и при этом при надлежи тнекоторой области Ω Rn .

Рассмотри м следую щ ую

постановку задачи :

→ min

,

) x(f

(1)

xΩ Rn

где =

1

n ) −( n -,мерны.., xx й xвектор, f (x) - функц и я, назы ваемая функц и ей

ц ели ,

Rn − допустиΩ моемножество.

f (x)

Задача пои ска макси мума функц и и

своди тся к задаче пои ска

ми ни мумапутем умножени я ц елевой функц и и на-1:

Ω

n

= −

n

−

)) x( f ( min

) x( f

max

Ω R

x

x R

Задачапои сками ни мумаи макси муманазы вается задачей пои ска

экстремума:

(

) → extr

f x

функц и и

f (x) намножествеΩ , если функц и я дости гаетвэтой точкесвоего

наи меньш его значени я, т.е. f (x*) £ f (x),

"x ÎW .

При этом и спользуется обозначени е =

).x(f min

arg x*

xΩ

О пред ел ение2. Т очка x*ÎW назы вается точкой локального ми ни мума

функц и и

f (x) намножествеΩ , если ε > 0, такое

что "x : (x ÎW) Ç (|| x − x* ||< ε ), справедли во неравенство f (x*) £ f (x) .

Замечани е1. В качественормы векторав R n и спользуется евкли дова

n

норма:

x ||= ||å xi2

i=1

О пред ел ение3. М ножество W Í Rn

6

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

содержи т отрезок, соеди няю щ и й лю бы едветочки и з множества Ω , т.е.

если x1 , x2 Ω и λ [0,1] справедли во: λ 1 (

λ)x2

Ω1.

+

−

О пред ел ение4. Ф ункц и я f (x),

определенная навы пуклом множествеΩ

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

− λ + x2f),

λ≤(λ1 )+

1−x(1λf ) ( x

1 2 Ω λ 1]0.,, [

, x x

Замечани е1. В дальнейш ем будем назы ватьтакую функц и ю

вы пуклой

вни з. Д ля вы пуклой вверх функц и и справедли во обратное неравенство:

2

1 2

1 1 λ 12]0Ω., [

, x λ,x −),x f+ λ(

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

(ЗВ П) , если

f (x) -вы пуклая функц и я , аΩ - вы пуклоемножество.

Д ля задачбезусловной опти ми зац и и необходи моеуслови еэкстремума

сформули ровановтеоремеФ ерма.

Т ео р ема 1 (Ф

ерма). Е сли

х* - точкалокального безусловного экстремума

непреры вно ди фференц и руемой в т. х*

функц и и f (x) , то всееечастны е

прои зводны епервого порядкавэтой точкеравны нулю . (В

векторны х

обозначени ях,Ñf (x*) = 0 ).

Замечани е2.Т очки , удовлетворяю щ и етеоремеФ ерма,

назы ваю тся

стац и онарны ми .

Т ео р ема 2 (Дост ат очное условие экст ремума).

Е сли встац и онарной

точке х* Î R n функц и я f (x) дважды ди фференц и руемаи матри ц аеевторы х

частны х прои зводны х H(x*) (матри ц аГессе) положи тельно определена(т.е.

всеееглавны еми норы Hk >0, k =

) ,

то х* - точкалокального ми ни мума.

1, n

П р имер 1. Реш и тьзадачу

x→ minx

−

+− x

−

2= x f+ x

2

2

2

x

x

1

2

3

3 1 2

3

Р ешение. Запи ш ем си стему:

ì df

x1

= = 2,-0

1

ï

dx

ï

1

ï df

æ 1

2

4

ö

í

x2

x == , 0- Þ x* = ç

,

,

÷

2

3

è 2

3

3 ø

ïdx2

ï df

x3

x2 = 0 = 2- 2 - 2

ï

îdx3

Провери м, вы полняю тся ли вполученной стац и онарной точкедостаточны е

услови я экстремума. М

атри ц авторы х частны х прои зводны х вданной задаче

æ

02ö

0

ç

÷

является постоянной: H = ç

- 1÷0. В ы2 чи сли м главны еми норы :

ç

- 02

÷

1

è

ø

7

= >

=

× =

>

H 3

=

H× 1

×

+

=H2 > 0 Þ матри10 )1ц а 2

2( 2

, 0

4 2

положи тельно определена, т.е. x * − точками ни мума.

fmin

= -

19

.

Д ля задачсограни чени ями -равенствами

12

f0

x

→ min,

(

)

= i

=

, i (b)f x

i

, m1

необходи моеуслови еэкстремумаформули руется вви депри нц и паЛ агранжа.

Т

ео р ема

3 (принципЛагранж а). Пусть х* - точкалокального экстремума

функц и и f0 (x) , при чем

=

0непреры( i),f x

вно ди фференц и руемы

в

i

, m

окрестности точки х* и векторы Ñ i

=

си мы . Т огда

, m1- ли(iнейнонезави*),f x

сущ ествуеттакой векторy* Î Rm , что для функц и и Л агранжа

m

−

x))f (+Φ b y (= x )f (x y )( ,

å

i

i=1

0

i i

вы полняю тся следую щ и еравенства:

*) =)10 *, Ñy( Fx

ì

x

í

*) =)20 *, Ñy( Fx

î

y

При проверкедостаточны х услови й экстремумав некоторы х задачах

условной опти ми зац и и можно пользоваться кри тери ем В ейерш трасса.

Т

ео р ема

4 (крит ерийВейершт расса).

Пусть f (x)

- непреры вная функц и я,

а множествоΩ представляетсобой компакт. Т огдасущ ествую тточки

max

min

min

max

x

, x

=

x),f (

min=(f

x )

x) f. (

max (f

Ω , таки ечто

ΩRn

x

x

ΩRn

П р имер 2. Н айти условны й экстремум в задаче

(

) =

+

2

® extr

x

x f

x

0

1

1 ( )

2

2

= 2

+ x

x f x

1

2

Р ешение.

Ф ункц и и

0

1 x) f( данной(x),

задачи

являю тся

непреры вно

ди фференц и руемы ми .

О грани чени е здесь еди нственно,

поэтому ли нейная

незави си мостьгради ентовограни чени й можетбы тьнаруш енали ш ьв случае,

когда Ñ

1

= 0,f

(тx.е).

=

,

) Þ(

()=

2

,= 0 . Oднакx оx точк0а0(0,0) xне2 2x

1

1

2

является

допусти мой

в

данной

задаче и ,

следовательно,

не является

реш ени ем. В оспользуемся при нц и пом Л агранжа. Ф ункц и я Л агранжаи меет

ви д

2

− x2 )− x

2+Φy +( x= x x y )( ,

2

1

2

1 1

11

1)

2

2

1

2 1

2 → extr+

− −

x + x 2

x

1

2

2)

4

4

2

® extr ++

-)

x

x(x

x

1

2

1

2

3.

Н айти условны й экстремум в задачах:

12 +

22 ® extr

x

x

12 - 22 ® extr

x

x 1

+

2 → extr

x3

4x

1)

( 1

)

2

2

2)

2

+

2

=x1

x

3)

2

+

2

=x1

x

2

-= 4 + x x

11

2

1

2

4. Реш и тьзадачу спомощ ью

расш и ренной функц и и Л агранжа

x

® extr

x 2

® extr

1)

23

3

= 0 +

2)

1

2

2

=+0

x-x

x2

2x

1

2

1

2

x -x3x

x

2

1

2

1

5.

Д оказ ать,

что ограни чени еви да

i (

) ≤ bif можнx о экви валентно

перепи сатькакограни чени е-равенство спомощ ью

введени я новой

переменной u

i

:

i

(

) +

2

= b .

u f

x

i

i

6.

Получи тьнеобходи мы е услови я экстремумадля задач

3

x2

a)

(

) → extr ;

f x

b)

x ³ 0

0 (

) ® extr

f

x

2

(4,2)

1 (

) £ bf

x,

.

cведя и х кзадачам с

.X*

1

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

7. (З адача Аполлония) Провести и з

данной точки кданному элли псу

0

x1

отрезокми ни мальной дли ны .

1

2

3

8. (З адачаШ т ейнера) Н айти

такую

точку вплоскости , чтобы