Методы оптимизации: Учебное пособие

3 М И Н И СТ Е РСТ В О О БРА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Н Н Ы Й У Н И В Е РСИ Т Е Т

Т .В . А за р но в а , И .Л . К а ш ир ина , Г .Д . Ч ер ны ш о в а

М Е ТОД Ы ОП ТИ М И З А Ц И И У чебноепособи е

В О РО Н Е Ж 2003

4

У тверждено научно-методи чески м советом факультетаП М М В ГУ .

Рец ензент: зав. кафи сследовани я операц и й Ростовского госуни верси тета, д.т.н., профЖ акС.В . А з арнова Т . В . , К аш и ри на И . Л . , Ч ерны ш ова Г . Д . опти ми зац и и : У чеб. пособи е. – В оронеж: И зд-во В ГУ , 2003.- 86 с.

М етоды

В пособи и рассматри вается ш и роки й круг задач математи ческого программи ровани я. И зложены анали ти чески е и чи сленны е методы реш ени я задач безусловной и условной опти ми зац и и . П ри менени е каждого метода и ллю стри руется реш ени ями ти повы х при меров. П ри ведены задачи для самостоятельного реш ени я. П особи еподготовлено накафедрематемати чески х методов и сследовани я операц и й факультетаП М М В оронежского государственного уни верси тета. Рекомендуется для студентов 3 курсад/о и 5 курсав/о, обучаю щ и хся по спец и альности “ При кладная математи каи и нформати ка”.

5

§ 1. П о ста но в ка за да чи ма тема тическо го пр о гр а ммир о в а ния П од задачей математи ческого программи ровани я пони мается задача нахождени я в векторном пространстве Rn такого вектора x * , которы й обеспечи вает опти мальное (ми ни мальное и ли макси мальное) значени е функц и и f (x) и при этом при надлежи тнекоторой области Ω ⊆ R n . Рассмотри м следую щ ую постановку задачи :

f ( x ) → min n ,

(1)

x∈Ω ⊆ R

где x = ( x1 ,.., x n ) − n -мерны й вектор, f (x) − функц и я, назы ваемая функц и ей ц ели , Ω ⊆ R n − допусти моемножество. Задача пои ска макси мума функц и и f (x) своди тся к задаче пои ска ми ни мумапутем умножени я ц елевой функц и и на-1:

max f ( x ) = − min n ( − f ( x ))

x∈Ω ⊆ R n

x∈Ω ⊆ R

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

f ( x) → extr

x∈Ω⊆ R n

Е сли Ω = R n , то и меетместо задачабезусловной опти ми зац и и . В проти вном случае, т.е. если Ω ⊂ R n – задачаусловной опти ми зац и и . О пред ел ение1. Т очка x* ∈ Ω назы вается точкой глобального ми ни мума функц и и f (x) намножествеΩ , если функц и я дости гаетв этой точкесвоего наи меньш его значени я, т.е. f ( x*) ≤ f ( x), ∀x ∈ Ω . П ри этом и спользуется обозначени е x* = arg min f ( x ) . x∈Ω

О пред ел ение2. Т очка x* ∈ Ω назы вается точкой локального ми ни мума функц и и f (x) намножествеΩ , если ∃ε > 0, такое что ∀x : ( x ∈ Ω) ∩ ( || x − x* ||< ε ), справедли во неравенство f ( x*) ≤ f ( x) . Замечани е 1. В качественормы векторав R n и спользуется евкли дова n

норма: || x ||= ∑ xi2 i =1

6

назы вается вы пуклы м, если оно О пред ел ение3. М ножество Ω ⊆ R содержи т отрезок, соеди няю щ и й лю бы едветочки и з множества Ω , т.е. если ∀x1 , x 2 ∈ Ω и ∀λ ∈ [0,1] справедли во: λx 1 + (1 − λ ) x 2 ∈ Ω . О пред ел ение4. Ф ункц и я f (x), определенная навы пуклом множестве Ω n

назы вается вы пуклой , если f (λx 1 + (1 − λ ) x 2 ) ≤ λf ( x 1 ) + (1 − λ ) f ( x 2 ), ∀x1 , x 2 ∈ Ω, ∀λ ∈ [0,1] . Замечани е 1. В дальнейш ем будем назы ватьтакую функц и ю вы пуклой вни з. Д ля вы пуклой вверх функц и и справедли во обратное неравенство: f (λx 1 + (1 − λ ) x 2 ) ≥ λf ( x 1 ) + (1 − λ ) f ( x 2 ), ∀x1 , x 2 ∈ Ω, ∀λ ∈ [0,1] . О пред ел ение5. Задача(1 ) назы вается задачей вы пуклого программи ровани я (ЗВ П ) , если f (x) − вы пуклая функц и я , а Ω - вы пуклоемножество. Д ля задачбезусловной опти ми зац и и необходи моеуслови еэкстремума сформули ровано в теореме Ф ерма. Т ео р ема 1 (Ф е рма). Е сли х * - точкалокального безусловного экстремума непреры вно ди фференц и руемой в т. х * функц и и f (x) , то всееечастны е прои зводны епервого порядкав этой точкеравны нулю . (В векторны х обозначени ях, ∇f ( x*) = 0 ). Замечани е 2.Т очки , удовлетворяю щ и етеоремеФ ерма, назы ваю тся стац и онарны ми . Т ео р ема 2 (Д ос т ат очное ус ловие эк с т ре мума). Е сли в стац и онарной точке х * ∈ R n функц и я f (x) дважды ди фференц и руемаи матри ц аеевторы х частны х прои зводны х H(x*) (матри ц аГессе) положи тельно определена(т.е. всеееглавны еми норы Hk >0, k = 1, n ) , то х * - точкалокального ми ни мума. П р имер 1. Реш и тьзадачу f ( x) = x12 + x 22 + x 32 − x1 − 2 x 3 − x 2 x 3 → min Р е ше ние . Запи ш ем си стему:  df = 2 x1 − 1 = 0,  dx 1   df 1 2 4 ⇒ x* =  , ,  = 2 x 2 − x3 = 0,  2 3 3  dx 2  df = 2 x3 − 2 − 2 x 2 = 0  dx  3 П ровери м, вы полняю тся ли в полученной стац и онарной точкедостаточны е услови я экстремума. М атри ц авторы х частны х прои зводны х в данной задаче 0 2 0   является постоянной: H =  0 2 − 1 . В ы чи сли м главны еми норы : 0 −1 2   

7

H 1 = 2 > 0, H 2 = 2 ⋅ 2 = 4 > 0, H 3 = 2 ⋅ (2 ⋅ 2 + 1) = 10 > 0 ⇒ матри ц а 19 положи тельно определена, т.е. x * − точками ни мума. f min = − . 12 Д ля задачсограни чени ями -равенствами f 0 ( x) → min, f i ( x) = bi , i = 1, m необходи моеуслови еэкстремумаформули руется в ви депри нц и паЛ агранжа. Т ео р ема 3 (принцип Лагранж а). П усть х * - точкалокального экстремума функц и и f 0 (x) , при чем f i ( x), i = 0, m непреры вно ди фференц и руемы в

окрестности точки х * и векторы ∇f i ( x*), i = 1, m - ли нейно незави си мы . Т огда сущ ествуеттакой векторy* ∈ R m , что для функц и и Л агранжа m

Φ ( x, y ) = f 0 ( x) + ∑ y i (bi − f i ( x )) i =1

вы полняю тся следую щ и еравенства: 1) ∇ x Φ ( x*, y*) = 0  2) ∇ y Φ( x*, y*) = 0

П ри проверкедостаточны х услови й экстремумав некоторы х задачах условной опти ми зац и и можно пользоваться кри тери ем В ейерш трасса. Т ео р ема 4 (к рит е рий Ве йе ршт рас с а). П усть f (x) - непреры вная функц и я, а множествоΩ представляетсобой компакт. Т огдасущ ествую тточки min ) = min n f ( x ) , x min , x max ∈ Ω , таки ечто f ( x x∈Ω ⊆ R

f ( x max ) = max f ( x) . x∈Ω⊆ R n

П р имер 2. Н айти условны й экстремум в задаче f 0 ( x) = x1 + x 2 → extr f 1 ( x ) = x12 + x 22 = 2 Р е ше ние . Ф ункц и и f 0 ( x), f 1 ( x) данной задачи являю тся непреры вно ди фференц и руемы ми . О грани чени е здесь еди нственно, поэтому ли нейная незави си мостьгради ентов ограни чени й можетбы тьнаруш енали ш ьв случае, когда ∇f 1 ( x ) = 0, т.е. ( 2 x1 ,2 x 2 ) = (0,0 ) ⇒ x1 = x 2 = 0 . Oднако точка (0,0) не является допусти мой в данной задаче и , следовательно, не является реш ени ем. В оспользуемся при нц и пом Л агранжа. Ф ункц и я Л агранжа и меет ви д Φ ( x, y ) = x 1 + x 2 + y 1 (2 − x12 − x 22 ) В ы пи ш ем необходи мы еуслови я экстремума

8

 ∂Φ( x, y ) = 1 − 2 y 1 x1 = 0, 1) ∂ x 1   ∂Φ( x, y ) = 1 − 2 y 1 x 2 = 0, ,  ∂ x 2   ∂Φ( x, y ) = 2 − x12 − x 22 = 0 2 ) ∂y1  В ы чи тая и з первого уравнени я второе, получаем 2 y 1 ( x 2 − x1 ) = 0. Равенство y 1 = 0 невозможно, так как в проти вном случае первы е два уравнени я си стемы несовместны . Значи т, x1 = x 2 . И спользовав это услови ев последнем уравнени и , находи м подозри тельны енаэкстремум точки : A: x1* = 1, x 2* = 1, y 1* = 1 / 2; B: x1* = −1, x 2* = −1, y 1* = 1 / 2 . Д опусти моемножество в и сходной задачепредставляетсобой окружность, а, следовательно, компакт. К ак следует и з кри тери я В ейерш трасса, среди подозри тельны х на экстремум точек данной задачи должны бы ть точка макси мума и точка ми ни мума. Т ак как f 0 (−1,−1) < f 0 (1,1) , то точка В является точкой ми ни мума и f 0min = −2 , а точка А - точкой макси мума и f 0max = 2 . П р имер 3. Н айти условны й экстремум в задаче f 0 ( x) = 3 x12 + 4 x1 x 2 + 12 x 22 → min f 1 ( x ) = x1 + x 2 = 4 Р е ше ние . Ф ункц и и f 0 ( x), f 1 ( x) данной задачи являю тся непреры вно ди фференц и руемы ми . О грани чени е здесь ли нейное, ∇f 1 ( x ) = (1,1) − ли нейно незави си мая си стема. 1. Запи ш ем функц и ю Л агранжа: Φ ( x, y ) = 3 x12 + 4 x1 x 2 + 12 x 22 + y1 ( 4 − x1 − x 2 ) 2. В ы пи ш ем необходи мы еуслови я экстремума  ∂Φ( x, y ) = 6 x1 + 4 x 2 − y1 = 0, 1) x ∂ 1  x1* = 12,   ∂Φ( x, y )  ⇒  x 2* = −8, = 4 x1 + x 2 − y1 = 0,  ∂x 2  *   y1 = 40  ∂Φ( x, y ) = 4 − x1 − x 2 = 0 2) ∂y1  Д опусти мое множество в и сходной задаче представляет собой прямую , т.е. неявляется компактом. 3. Посчи таем вторы е частны е прои зводны е по х для функц и и Л агранжа : d 2 Φ ( x, y ) d 2 Φ ( x, y ) d 2 Φ ( x, y ) = 6 , = 1 , = 4. dx12 dx 22 dx1 dx 2

9

4. Состави м второй ди фференц и ал d 2 Φ( x*, y*) = 6dx12 + 8dx1 dx2 + dx22 . П роди фференц и ровав уравнени есвязи x1 + x 2 = 4 , получи м dx1 = −dx 2 . П одстави м это вы ражени ев ди фференц и ал : d 2 Φ( x*, y*) = 6dx22 − 8dx22 + dx22 = −dx22 . Т аккак d 2 Φ( x*, y*) < 0 , то точкаx* является точкой макси мума. П ри реш ени и больш и нства задач проверка услови я ли нейной незави си мости векторов ∇f i ( x*), i = 1, m затруднена, так как точка х * заранее неи звестна. О днако это требовани е является сущ ественны м. П рои ллю стри руем это наследую щ ем при мере. П р имер 4. Н айти условны й экстремум в задаче f 0 ( x ) = x1 → min f 1 ( x ) = − x13 + x 22 = 0

Р е ше ние . 1. Запи ш ем функц и ю Л агранжа: Φ ( x, y ) = x 1 + y 1 ( x13 − x 22 ) 2. В ы пи ш ем необходи мы еуслови я экстремума  ∂Φ ( x , y ) = 1 + 3 y1 x12 = 0 ,  a ) ∂x 1   ∂Φ ( x , y ) = −2 y1 x2 = 0,  ∂ x 2   ∂Φ ( x , y ) = x13 − x22 = 0 b ) ∂y1  И з второго равенстваследует, что ли бо y 1 =0, ли бо x 2 = 0 . П ри y 1 =0 первое равенство невозможно (1=0), значи т x 2 = 0 . Н о и з третьего равенства получаем x 2 = 0 и первое равенство снова не вы полняется (1=0). В и тоге получаем, что си стема несовместна и точек, подозри тельны х наэкстремум, нет. О днако, проанали зи ровав и сходную постановку задачи , нетрудно убеди ться, что она разреш и ма. И з ограни чени я следует, что x1 ≥ 0 (так как x1 = (3 x 2 ) 2 ). П оэтому точка x*=(0,0) является реш ени ем данной задачи . П ри нц и п Л агранжа неработает, потому что в точке x* наруш ено требовани е ли нейной незави си мости гради ентов: ∇f 1 ( x*) = ( −3( x1* ) 2 ,2 x 2* ) = (0,0 ) . Ч тобы и збежатьпроверки ли нейной незави си мости гради ентов в рассмотрени евводи тся такназы ваемая расш и ренная функц и я Л агранжа: ~ ( x, y , y ) = y f ( x) + m y (b − f ( x)) Φ 0

0 0

∑

i =1

i

i

i

Т ео р ема 5 (рас шире нный принцип Лагранж а). П усть х * - точкалокального экстремума функц и и f 0 (x) , при чем f i ( x), i = 0, m непреры вно

10

ди фференц и руемы в окрестности точки х .Т огдасущ ествуеттакой * m +1 , y* = ( y1* ,..., y m* ) , что для расш и ренной ненулевой вектор( y 0 ,y*) ∈ R функц и и Л агранжа ~ ( x, y , y ) = y f ( x) + m y (b − f ( x)) Φ 0

∑

0 0

i =1

i

i

i

вы полняю тся следую щ и еравенства: 1) ∇ x Φ ( x*, y 0* , y*) = 0  * 2) ∇ y Φ ( x*, y 0 , y*) = 0 В результатеоты скани е подозри тельны х наэкстремум точекможет осущ ествляться по следую щ ему алгори тму: Ш аг1. Состави тьрасш и ренную функц и ю Л агранжа: ~ ( x, y , y ) = y f ( x) + m y (b − f ( x)) Φ 0

0 0

∑

i =1

i

i

i

Ш аг2. Запи сатьнеобходи мы еуслови я экстремума 1) ∇ x Φ ( x, y 0 , y ) = 0  0 2) ∇ y Φ ( x, y , y ) = 0 Ш аг3. Реш и тьси стему для двух случаев 1) y0=0; 2) y0=1 В результатенайти подозри тельны енаэкстремум точки x*. В озврати мся кпр имер у4. 1. Состави м расш и ренную функц и ю Л агранжа. Φ ( x, y 0 , y ) = y 0 x 1 + y 1 ( x 13 − x 22 ) 2. В ы пи ш ем необходи мы еуслови я экстремума  ∂Φ( x, y ) = y 0 + 3 y 1 x12 = 0, a ) ∂x1   ∂Φ( x, y ) = −2 y1 x 2 = 0,  ∂ x 2   ∂Φ( x, y ) = x13 − x 22 = 0 b) ∂y 1  0 3. Положи м y =0. Реш ая полученную си стему, находи м еди нственную точку (0,0). П ри y0=1, какмы ужевы ясни ли , си стеманесовместна. З а да чи для са мо сто ятельно го р еш ения 1. Д оказать, что всякая точкалокального ми ни мумав задачевы пуклого программи ровани я является точкой глобального ми ни мума. 2. Н айти точки безусловного экстремумафункц и й.

11

x12 − x1 x 2 + x 22 − 2 x1 + x 2 → extr

1)

2) x14 + x 24 − ( x1 + x 2 ) 2 → extr 3. Н айти условны й экстремум в задачах: x12 − x 22 → extr 4 x + 3 x 2 → extr x12 + x 22 → extr 1) 2) 3) 1 ( x1 − 1) 2 + x 22 = 4 x1 2 + x 22 = 1 x1 2 + x 22 = 1 4. Реш и тьзадачу спомощ ью расш и ренной функц и и Л агранжа x 2 → extr x12 → extr 1) 2) 3 3 2 x12 + 2 x 22 − x1 x 2 = 0 x1 + x 2 − 3 x1 x 2 = 0 5. Д оказ ать, что ограни чени еви да f i ( x) ≤ bi можно экви валентно перепи сатькакограни чени е-равенство спомощ ью введени я новой переменной u i : f i ( x) + u i2 = bi . 6. П олучи тьнеобходи мы е услови я экстремумадля задач f ( x ) → extr a) ; b) 3 x2 x≥0 f 0 ( x) → extr , 2 f 1 ( x) ≤ b (4,2) cведя и х кзадачам с ограни чени ями -равенствами . 1 7. (З адача Аполлония) П ровести и з X* данной точки кданному элли псу отрезокми ни мальной дли ны . 0 x1 8. (З адачаШ т е йне ра) Н айти 2 3 1 такую точку в плоскости , чтобы суммарасстояни й отнеедо трех Ри с.1 заданны х точекбы ла ми ни мальной. 9. Н айти расстояни еотточки в пространстве R n до заданной прямой.

.

.

§ 2. Гр а фическо е р еш ение за да ч нелинейно го пр о гр а ммир о в а ния. Е сли допусти мое множество Ω ⊂ R 2 , то задача опти ми зац и и , как прави ло, можетбы тьреш енаграфи чески . Опр еделение. К ри вы е, задаю щ и еся уравнени ями f ( x1 , x 2 ) = C , назы ваю тся ли ни ями уровня функц и и f ( x1 , x 2 ) . П р имер 1. Реш и тьграфи чески задачу нели нейного программи ровани я f ( x, y ) = ( x1 − 4 ) 2 + ( x 2 − 2) 2 → min, x1 + x 2 ≤ 3, (1) x 1 + 2 x 2 ≤ 4, (2)

12

x1 , x 2 ≥ 0 Р е ше ние : Д опусти моемножество задачи и зображено нари с.1 Л и ни ями уровня ц елевой функц и и являю тся конц ентри чески е окружности с ц ентром в точке (4,2). М и ни мальному значени ю ц елевой функц и и соответствует окружность ми ни мального ради уса, пересекаю щ ая допусти мую область. Т акая окружность будеткасаться грани ц ы области на прямой (1). Д альнейш ее уменьш ени е ради уса при води т к ли ни ям уровня, не и мею щ и м общ и х точексобластью . К оорди наты точки касани я можно найти , при равни вая значени я прои зводны х ( x 2 ) 'x1 и з уравнени й прямой и окружности . Д и фференц и руя уравнени е окружности ( x1 − 4 ) 2 + ( x 2 − 2) 2 = C , и рассматри вая x 2 как неявную функц и ю от x1 , получи м 2 ( x1 − 4 ) ( x 2 ) 'x1 = − . И з уравнени я прямой находи м ( x 2 ) 'x1 =-1. В и тоге 2 ( x 2 − 2) 2( x 1 − 4 ) , т.е. x 2 − 2 = x1 − 4 . Д обави в вы пи сы вается равенство: − 1 = − 2( x 2 − 2) уравнени е прямой, которой при надлежи т точка касани я, получи м си стему:  x1 + x 2 = 3, 5 1 . Е ереш ени ем является точка X * = ( , ) .  2 2  x 2 = x1 − 2 П р имер 2. f ( x1 , x 2 ) = 2( x1 − 2) 2 + ( x 2 − 4) 2 → extr , − x 1 + x 2 ≤ 4, (1) − 9 x12 + 25 x 2 ≥ 0, (2) x1 , x 2 ≥ 0 Р е ше ние : Д опусти мое множество задачи и зображено на ри с.2. Л и ни ями уровня ц елевой функц и и являю тся конц ентри чески е элли псы с ц ентром в точке (2,4) и задаю щ и еся уравнени ем 2( x1 − 2) 2 + ( x 2 − 4 ) 2 = C . П оскольку точка (2,4) при надлежи т x2 допусти мому множеству, то она и X max будет являться точкой ми ни мума задачи . И з графи ка ви дно, что макси мальному значени ю функц и и соответствует элли пс, пересекаю щ и й грани ц у области в точке X max . X min К оорди наты этой точки находятся и з услови я пересечени я прямой и − x 1 + x 2 = 4 x1 параболы :  , 2 − 9 x + 25 x = 0  1 2 Ри с 2. откуда x1 = 5, x 2 = 9.

.

.

13

О твет: X max = (5,9) X min = ( 2,4) П р имер 3. f ( x1 , x 2 ) = max{ x1 − 2 , x 2 } → extr 2 x1 − x 2 ≤ 2 Р е ше ние . Д опусти мое множество задачи и зображено на ри с.3. Л и ни ями ур овня ц елевой функц и и являю тся 1 конц ентри чески е квадраты с ц ентром в точке (2,0) и задаю щ и еся уравнени ем x1 1 max{ x1 − 2 , x 2 } = C . М и ни мальному значени ю ц елевой функц и и соответствует квадрат с ми ни мальной стороной, пересекаю щ и й допусти мую область. Рис. 3. И з графи ка ви дно, что такой квадрат будет касаться грани ц ы допусти мой области в двух точках. К оорди наты 2 | x1 | − | x 2 |= 2 . Д ля той точки , которая лежи т точек находятся и з услови й:  | x − 2 | = | x | 2  1 в первой четверти 0 ≤ x1 ≤ 2, 0 ≤ x 2 , поэтому си стема при ни мает ви д: 2 x 1 − x 2 = 2 4 2 , откуда x11 = , x 21 = . В торая точка си мметри чна данной  3 3 2 − x 1 = x 2 4 2 относи тельно оси Ох , поэтому ее коорди наты и мею т ви д x11 = , x 21 = − . 3 3 П ри неограни ченном увели чени и стороны квадрата, ли ни и уровня будут продолжатьпересекатьдопусти мую область, поэтому sup f ( x, y ) = +∞ .

x2

. .

Ω

4 2 4 2 1 2 О твет: X min = ( , ), X min = ( ,− ) , sup f ( x1 , x 2 ) = +∞ . 3 3 3 3 Ω П р имер 4. f ( x1 , x2 ) = ( x1 − 5) x2 → extr , x12 + x 22 ≤ 3 Р е ше ние : Д опусти мое множество задачи и зображено на ри с.4. Л и ни ями уровня ц елевой функц и и являю тся ги перболы с аси мптотами x1 =5, x2 =0 и задаю щ и еся уравнени ем ( x1 − 5) x 2 = C . М и ни мум функц и и будет дости гаться при С<0, макси мум – при С>0. О бе точки являю тся точками касани я окружности и ги перболы . К оорди наты точки касани я находи м,

Ри с4.

14

при равни вая значени я прои зводны х ( x 2 ) 'x1 и з уравнени й ги перболы и окружности . Д и фференц и руя уравне-ни е ги перболы ( x1 − 5) x 2 = C , x получи м ( x 2 ) 'x1 = − 2 . И з уравнени я окружности находи м x1 − 5 2x x2 x т.е. ( x 2 ) 'x1 = − 1 . В и тоге вы пи сы вается равенство: = 1, 2 x2 x1 − 5 x 2 x 22 = x12 − 5x1 .

Д обави в уравнени е окружности ,

получи м

си стему:

 x 22 = x12 − 5 x1 , . С учетом услови я x1 ≤ 0 , ее реш ени ем являю тся точки  2  x1 + x 22 = 3 1 11 1 11 X min = (− , ), X max = ( − ,− ). 2 2 2 2 З а да чи для са мо сто ятельно го р еш ения Реш и тьграфи чески задачи нели нейного программи ровани я: 1. 2.

| x1 − 5 | + x2 → extr

( x1 − 1) 2 + ( x2 − 1) 2 → extr

5 x1 + 3 x2 ≤ 24,

( x1 − 2)( x2 + 1) ≤ 16,

0 ≤ x1 ≤ 3, x2 ≥ 0

x1 ≥ 0, x2 ≥ 0 3.

4.

x1 + 3x2 → extr

x1x2 → extr

( x1 − 5) + ( x2 − 3) ≥ 9, 2

2

x2 − | x1 − 4 |≤ 3,

( x1 − 5) + ( x2 − 3) ≤ 36, 2

2

2 ≤ x1 ≤ 6,

x1 + x2 ≥ 8,

x2 ≥ 0

x1 ≥ 0, x2 ≥ 0 5.

6. ( x1 − 3) 2 + ( x 2 − 2) 2 → extr

( x1 − 3) 2 + 4( x2 − 6) 2 → extr 3 x1 + 5 x2 ≤ 24,

x12 + x22 ≤ 36,

x1 ≥ 3, x2 ≥ 0

x1 ≥ 0, x2 ≥ 0

7.

8. 2( x1 − 5) 2 + ( x2 − 7) 2 → extr

9.

( x1 − 4) 2 + ( x2 − 8) 2 → extr

x1 + 2 x2 ≤ 12,

2 x1 + 5 x2 ≤ 30,

x1 + x2 ≤ 9,

2 x1 + x2 ≤ 14,

x1 ≥ 0, x2 ≥ 0

x1 ≥ 0, x2 ≥ 0

15

( x1 − 2 ) + ( x 2 − a ) → extr 2

2

x12 + x 2 ≤ a,

(здесьa и b –прои звольны ечи сла)

bx1 + x 2 ≥ 0

§ 3. Т ео р ема К уна -Т а ккер а Рассмотри м задачу опти ми зац и и следую щ его ви да: f 0 ( x ) → max, f i ( x ) ≤ bi , i = 1, m, Ω x≥0  Э тазадачадопускаетследую щ ую экви валентную перезапи сь: max min Φ( x, y ), ãäå x≥0

Φ ( x, y ) = { f 0 ( x) +

m

y ≥0

∑ y i ( bi i =1

(1)

− f i ( x ))} ,

x ≥ 0, y ≥ 0 −

(2)

функц и я Л агранжа задачи (1). О пред ел ение1. Д войственной задачей кзадаче(1) назы вается задачави да min max Φ ( x , y ) y ≥0

x ≥0

О пред ел ение 2. Т очка ( x , y ) ≥ 0, x 0 ∈ R n , y 0 ∈ R m , назы вается седловой точкой функц и и Л агранжа, если вы полняю тся неравенства Φ ( x, y 0 ) ≤ Φ ( x 0 , y 0 ) ≤ Φ ( x 0 , y ), ∀x, y ≥ 0 0

0

О пред ел ение 2'. Т очка ( x 0 , y 0 ) ≥ 0, x 0 ∈ R n , y 0 ∈ R m , назы вается седловой точкой функц и и Л агранжа, если в этой точке Φ(x 0 ,y 0 ) = max min Φ(x,y) = min max Φ(x,y) y≥0 x≥0 x≥0 y≥0 Замечани е 1. О пределени я 2 и 2' экви валентны . Т ео р ема 1. (Д ос т ат очное ус ловие эк ст ре мума). Е сли ( x 0 , y 0 ) ≥ 0, x 0 ∈ R n , y 0 ∈ R m - седловая точка функц и и Л агранжа для задачи (1), то x 0 − реш ени езадачи (1). О пред ел ение 3. М ножество Ω назы вается регулярны м (по Слейтеру) если сущ ествуетточка x$ ≥ 0, такая что f i ( x$) < bi , ∀i = 1, m О пред ел ение 3'. М ножество Ω назы вается регулярны м, если для лю бого i= 1, m сущ ествуетточка x$ i ≥ 0, такая что f i ( x$ i ) < bi . З амечани е 2. О пределени я 3 и 3' экви валентны . Н е обх одимое ус ловие эк с т ре мума для задач ви да (1) формули руется в теоремеК уна- Т аккера. Т ео р ема 2. ( т е оре маКуна-Так к е ра). П усть (1) является задачей вы пуклого программи ровани я, множество Ω регулярно по Слейтеру. Т огда если x 0 − реш ени е задачи (1), то

16

сущ ествует y ≥ 0, y ∈ R , что ( x 0 , y 0 ) - седловая точка функц и и Л агранжа. Т ео р ема 3. (диффе ре нциальный вариант т е оре мы Куна–Так к е ра) П усть (1) является задачей вы пуклого программи ровани я, а функц и и f i ( x ), i = 0, m являю тся непреры вно ди фференц и руемы ми . Д ля того, чтобы точка ( x 0 , y 0 ) ≥ 0, x 0 ∈ R n , y 0 ∈ R m бы ла седловой точкой функц и и Л агранжа, необходи мо и достаточно, чтобы в ней вы полняли сьуслови я:  ∂Φ( x 0 , y 0 ) ≤ 0, j = 1, n, a ) ∂ x j  a)∇ x Φ ( x 0 , y 0 ) ≤ 0,  0 0 Φ x y ∂ ( , ) b) x j = 0, j = 1, n,  b)∇ x Φ ( x 0 , y 0 )( x 0 ) T = 0,  ∂x j ,   0 0 0 0  ∂Φ( x , y ) c)∇ y Φ( x , y ) ≥ 0, ≥ 0,i = 1, m, c)  0 0 0 T y ∂ i d )∇ y Φ( x , y )( y ) = 0   ∂Φ( x 0 , y 0 ) y i = 0,i = 1, m d )  ∂y i Замечани е 3. И з теоремы 1 следует, что при вы полнени и услови й теоремы 3 точка x 0 , являю щ аяся реш ени ем си стемы a)-d) ,будетреш ени ем задачи (1). Замечани е 4. Е сли в задаче (1) и щ ется ми ни мум функц и и f 0 ( x ) , то знак неравенств а) меняется напроти воположны й. Замечани е 5. Знаки неравенств с ) связаны со знаками неравенств в ограни чени ях задачи (1) и по сути являю тся экви валентно перепи санны ми и сходны ми неравенствами . Замечани е 6. Н еравенства b) и d) назы ваю тся услови ями дополняю щ ей нежесткости . Замечани е 7. Е сли услови я вы пуклости в задаче наруш аю тся, то си стема a) – d) можетнеи метьреш ени я. Т ео р ема 4. П усть (1) является задачей вы пуклого программи ровани я, функц и и f i ( x ), i = 0, m являю тся непреры вно ди фференц и руемы ми . Е сли в 0

0

m

точке ( x 0 , y 0 ) ≥ 0 вы полняю тся услови я а)-d) теоремы 3, то справедли во разложени е ∇f 0 ( x 0 ) = ∑ y i0 ∇f i ( x 0 ) − ∑ v 0j e j , (3) i∈I ( x0 )

где v 0j = −

∂Φ ( x 0 , y 0 ) ∂x j

j∈J ( x 0 )

≥ 0 - неотри ц ательны екоэффи ц и енты , e j − j-ты й орт,

I ( x 0 ) -множество и ндексов ограни чени й, акти вны х в точке

x 0 , т.е

I ( x 0 ) = {i : f i ( x 0 ) = bi } , J ( x 0 ) = { j : x 0j = 0} . И наоборот, если в точке ( x 0 , y$ 0 ) , где x 0 ∈ Ω, yˆ0 = ( yi0 , i ∈ I ( x 0 )) , вы полняется равенство (3), то

17

сущ ествует y ≥ 0, y ∈ R , что ( x 0 , y 0 ) удовлетворяет услови ям а)d) теоремы 3. Т ео р ема 5 (У с ловия Ф . Д ж она) П усть (1) является задачей вы пуклого программи ровани я, множество Ω регулярно по Слейтеру, функц и и f i ( x ), i = 0, m являю тся непреры вно ди фференц и руемы ми . Д ля того, чтобы 0

0

m

точка x 0 бы ла реш ени ем задачи (1) необходи мо и достаточно, чтобы сущ ествовал вектор y 0 ≥ 0, y 0 ∈ R m , такой что в точке ( x 0 , y 0 ) вы полняется услови е(3). Замечани е 8. У слови е(3) означает, что гради ентц елевой функц и и является ли нейной комби нац и ей гради ентов акти вны х ограни чени й, вклю чая услови я неотри ц ательности . П ри этом гради енты , соответствую щ и е ограни чени ям, и мею т в разложени и неотри ц ательны е коэффи ц и енты , а гради енты , соответствую щ и е услови ям неотри ц ательности (т.е. еди ни чны е орты ) неположи тельны е. Т ак, напри мер, нари с. 5 в точкеx* дости гается макси мум функц и и f 0 (x) , ав точке xˆ- нет(т.к. вектор∇f 1 (xˆ) войдетв разложени е(3) с отри ц ательны м коэффи ц и ентом). ∇f 1 (x*)

∇f 1 (xˆ)

∇f 0 (xˆ)

xˆ

x*

∇f 0 (x*) ∇f 2 (x*)

Ω

∇f 3 (xˆ)

Ри с5. Замечани е 9. Е сли услови я неотри ц ательности в задаче(1) отсутствую т, то разложени е(3) перепи сы вается следую щ и м образом: (3') ∇f 0 ( x 0 ) = ∑ y i0 ∇f i ( x 0 ) i∈I ( x0 )

Связь между при веденны ми фактами прои ллю стри роватьв ви деследую щ ей табли ц ы x0 является реш ени ем задачи (1) x 0 ∈ Ω, (1) - ЗВ П

(1) - ЗВ П, f i (x) −

Ω - регулярно, (1) - ЗВ П

и

теоремами

можно

(x0,y0) - седловая точкафункц и и Л агранжа Φ ( x, y ) (1) - ЗВ П, f i (x) −

f i (x) − непрер.

f i (x) − непрер. ди ффер. (i = 0, m)

18

непрер.

непрер. ди фференц . (i = 0, m) , Ω - регул.

У слови я Ф . Д жона x0 ∈ Ω

ди ффер. ди ффер. (i = 0, m)

(i = 0, m)

В точке(x0,y0) ≥ 0 вы полняю тся услови я a)-d) теоремы 3.

Т ео р ема 6. (Те оре ма Куна-Так к е ра дляз адач с линейными ограниче ниями). П усть (1) является задачей вы пуклого программи ровани я, а функц и я f 0 (x) является непреры вно ди фференц и руемой. Д ля того, чтобы точка x 0 бы ла реш ени ем задачи (1) в случае, когда все ограни чени я ли нейны , необходи мо и достаточно, чтобы сущ ествовал вектор y 0 ≥ 0, y 0 ∈ R m , такой что точка ( x 0 , y 0 ) ≥ 0, x 0 ∈ R n , y 0 ∈ R m бы ласедловой точкой функц и и Л агранжа. П р имер 1. Н айти реш ени езадачи f 0 ( x) = − x12 − x 22 → max f 1 ( x ) = − x 1 − x 2 ≤ −2 , x1 , x 2 ≥ 0 Р е ше ние . Т ак как функц и я f 0 (x) в задаче является вы пуклой (вверх) и непреры вно ди фференц и руемой, воспользуемся теоремами 6 и 3. Запи ш ем функц и ю Л агранжаданной задачи

Φ ( x, y ) = − x12 − x 22 + y 1 ( −2 + x1 + x 2 ), x1 , x 2 , y 1 ≥ 0 В ы пи ш ем услови я экстремумаэтой задачи . ∂ Φ ( x, y ) ∂Φ ( x, y ) a) = −2 x1 + y1 ≤ 0, = −2 x 2 + y1 ≤ 0 ∂x1 ∂x 2 ∂Φ ( x , y ) x1 = (−2 x1 + y1 ) x1 = 0, ∂x1 ∂ Φ ( x, y ) c) = −2 + x1 + x 2 ≥ 0, ∂y1

b)

∂Φ ( x , y ) x1 = (−2 x 2 + y1 ) x 2 = 0, ∂x1

∂Φ ( x , y ) y1 = ( −2 + x1 + x 2 ) y1 = 0, ∂y1 Т акая си стемареш ается следую щ и м образом: реш ается си стемаравенств b) и d), а затем полученны е точки подставляю тся в неравенства а), с ) и услови я неотри ц ательности и проверяю тся. И так, реш и м си стему d)

19

(−2 x1 + y1 ) x1 = 0,  (−2 x 2 + y 1 ) x 2 = 0, (−2 + x + x ) y = 0, 1 2 1  И з последнего равенстваследует, что ли бо y 1 = 0 , ли бо x1 + x 2 = 2 . Е сли y 1 = 0 , то и з первы х двух равенств следует, что x 1 = x 2 = 0 . Подстави м полученную точку (0,0,0) в неравенства. У слови я неотри ц ательности , очеви дно, вы полнены , однако неравенство с ) наруш ено ( -2+0+0 ≥ 0 неверно). Значи т y 1 ≠ 0 , т.е. x1 + x 2 = 2 . В ы рази м x 2 = 2 − x1 и подстави м в первы е дваравенства. (−2 x1 + y 1 ) x1 = 0,  (−4 + 2 x1 + y 1 )(2 − x1 ) = 0, Рассмотри м случай x1 = 0 ⇒ x 2 = 2, y 1 = 4 . П одстави м в неравенстваточку (0,2,4). У слови я неотри ц ательности вы полнены , однако первоенеравенство в а) наруш ено (0+4 ≤ 0 -неверно). Р Рассмотри м случай x1 = 2 ⇒ x 2 = 0, y 1 = 4 . В данной точкенаруш ено второе неравенство в а) (0+4 ≤ 0 -неверно). − 2 x 1 + y 1 = 0 О стался случай  ⇒ 4 x1 = 4, x1 = 1 ⇒ x 2 = 1, y 1 = 2 − + + = 4 2 x y 0  1 1 В точке(1,1,2) всенеравенства(в т. ч. услови я неотри ц ательности ) вы полнены , следовательно, онаявляется седловой точкой, аточка x* = (1,1) точкой условного макси мума. П р имер 2. П ровери ть, является ли точкаx = (4,0) реш ени ем задачи 3 x12 + 4 x1 x 2 + 5 x 22 → min x1 + x 2 ≥ 4 x1 , x 2 ≥ 0 Р е ше ние . Д анная точкаявляется допусти мой. В оспользуемся ди фференц и альны м вари антом теоремы К уна- Т аккера, для чего перепи ш ем задачу следую щ и м образом: f 0 ( x) = −3x12 − 4 x1 x 2 − 5 x 22 → max f 1 ( x) = − x1 − x 2 ≤ −4 x1 , x 2 ≥ 0 В точке (4,0) акти вны ми являю тся ограни чени я − x1 − x 2 ≤ −4, x 2 ≥ 0 . П осчи таем гради енты ∇f 0 ( x) = ( −6 x1 − 4 x 2 ;−10 x 2 − 4 x1 ) ; ∇f 0 ( 4,0) = ( −24;−16) ; ∇f 1 ( x ) = ( −1;−1) . Разложени е (3) и меет ви д: (-24; 16)= y1 ( −1,−1) − v 2 (0,1) . О тсю да y1 = 24; v 2 = −8 . Т аккакв опти мальной точке должны вы полняться неравенства y1 ≥ 0, v 2 ≥ 0, данная точка x = (4,0) не

20

является реш ени ем задачи . П р имер 3. − ( x1 − 3) 2 − x 22 → max − (1 − x1 ) 3 + x 2 ≤ 0 x1 , x 2 ≥ 0 Р е ше ние . Н ари с. 6 и зображено допусти моемножество данной задачи .

1

1 Ри с6. М ножество неявляется вы пуклы м, но и з графи кави дно, что реш ени ем задачи является точка x * = (1, 0). Запи ш ем услови я К уна-Т аккераи провери м, вы полняю тся ли они в данной точке.

Φ ( x, y ) = −( x1 − 3) 2 − x 22 + y1 ((1 − x1 ) 3 − x 2 ), x1 , x 2 , y1 ≥ 0 a)

∂Φ ( x , y ) = −2 x1 + 6 − 3 y1 (1 − x1 ) 2 ≤ 0, ∂x1

∂ Φ ( x, y ) = −2 x 2 − y1 ≤ 0 ∂x 2

b)

∂Φ ( x , y ) ∂Φ ( x , y ) x1 = ( −2 x1 + 6 − 3 y1 (1 − x1 ) 2 ) x1 = 0, x1 = ( −2 x 2 − y1 ) x 2 = 0, ∂x1 ∂x1

c)

∂ Φ ( x, y ) = (1 − x1 ) 3 − x 2 ≥ 0, ∂y1

∂ Φ ( x, y ) y1 = ((1 − x1 ) 3 − x 2 ) y1 = 0 ∂y1 В точке(1,0) первоеуслови еуженаруш ается, т.к. –2+6 >0. Следовательно, точкаопти муманеудовлетворяетси стемеа) - d). Э то прои зош ло потому, что гради енты ограни чени й невы пуклой задачи оказали сьли нейно зави си мы в точке(1,0). ( А кти вны ми ограни чени ями являю тся f 1 и услови е f 2 = x 2 ≥ 0 . ∇f 1 (1,0) = (0,−1) , ∇f 1 + ∇f 2 = 0 ). d)

21

З а да чи для са мо сто ятельно го

р еш ения

1.Н айти условны й экстремум в задачах 2) x1 → max 1) x1 + x 2 → max x12 + x 22 ≤ 1

− (1 − x1 ) 3 + x 2 ≤ 0

x1 , x 2 ≥ 0

x2 ≥ 0

3) ( x1 − 3) 2 + ( x 2 − 5) 2 → max x12 + x 22 ≤ 10,

x12 + x 22 ≤ 16

− 2 x1 + x 2 ≤ 5

x1 − x 2 ≥ 4

5) ( x1 − λ ) 2 + x 22 → max x12 + x 22 ≤ 1

1 1 + → max x1 x 2

6) 1

x1 ≥ 0 при λ = 2, λ = 1, λ =

x12 − x 22 → max

4)

1 , λ = 0, λ = −1 2

7 ) x1 x 2 x 3 → max x1 + x 2 + x 3 ≤ 6 , x 1 x 2 + x1 x 3 + x 2 x 3 ≤ 8 9 ) x12 + x 22 + x 32 → min

x12

+

1 x 22

≤1

8) x1 − 2 x 2 + 2 x 3 → min x12 + x 22 + x 32 ≤ 9, x1 ≥ 0 10) 2 x12 + 2 x1 + 4 x 2 − 3 x 3 → min

2 x 1 − x 2 + x 3 ≤ 5,

8 x1 − 3 x 2 + 3 x 3 ≤ 40,

x1 + x 2 + x 3 ≤ 3,

2 x1 − x 2 + x 3 = 3,

x1 ≥ 0

x2 ≥ 0

11) − e x1 − x2 + x1 + x 2 → max

12) ( x1 − 5) 2 + ( x 2 − 4 ) 2 + 5e x3 → min

x1 + x 2 ≤ 1,

x1 + x 2 + x 3 ≤ 1,

x1 ≥ 0, x 2 ≥ 0

x 1 ≥ 0, x 2 ≥ 0 , x 3 ≥ 0

2. Д оказать, что определени я 2 и 2' экви валентны . 3. Д оказать, что определени я 3 и 3' экви валентны . 4. Д оказатьзамечани е2 ктеореме5. 5. Сформули роватьи доказатьтеоремы , соответствую щ и еди агональны м связям при веденной табли ц ы . 6. Реш и тьзадачу и з при мера3 си спользовани ем расш и ренной функц и и Л агранжа. 7. Провери ть, является ли точка x * реш ени ем данной задачи

22

1) x = (2.5; 1.5)

2) x * = (0.4; 1.8)

x12 + x 22 − 2 x1 → min

x12 + x 22 − 2 x1 − 8 x 2 → min

*

x12 + 4 x 22 − 4 x1 − 4 x 2 ≤ 0,

x1 + 2 x 22 ≤ 4,

x1 + x 2 ≥ 4,

3 x1 + x 2 ≥ 3,

x1 ≥ 0, x 2 ≥ 0

x 1 ≥ 0, x 2 ≥ 0

§ 4. М ето ды о дно мер но йминимиза ции В данном параграфе рассматри ваю тся задачи одномерной ми ни ми зац и и , т.е. задачи ви да f ( x) → min x∈R . П оведени е реальны х фи зи чески х и экономи чески х си стем редко опи сы ваю тся в ви де задачи одномерной ми ни ми зац и и , чащ е таки е задачи возни каю тнаэтапевы боравели чи ны ш агав проц ессеми ни ми зац и и функц и и многи х переменны х. Задачи одномерной ми ни ми зац и и могут бы ть реш ены с помощ ью необходи мы х и достаточны х услови й безусловного экстремума. О днако, df ( x) = 0 может оказаться весьма проблема получени я реш ени я уравнени я dx сложной. Более того, в практи чески х задачах функц и я f (x) может бы ть не задана в анали ти ческом ви де и ли не являться ди фференц и руемой. П оэтому актуальны ми являю тся методы получени я чи сленного реш ени я поставленной задачи , которы епозволяю тнайти реш ени езадачи снеобходи мой точностью . Д ля чи сленны х методов реш ени я задач одномерной ми ни ми зац и и ти пи чно задани е апри орной и нформац и и о положени и точки ми ни мума с помощ ью начального промежутка неопределенности L 0 = [ a 0 , b0 ] . П редполагается, что точками ни мума x * при надлежи тпромежутку L0 , но ее точноезначени енеи звестно. К ак прави ло, результатом работы чи сленны х алгори тмов одномерной ми ни ми зац и и является некоторы й заклю чи тельны й промежуток неопределенности L N ( N - чи сло прои зведенны х ти повы х вы чи слени й в проц ессе работы данного алгори тма). В качестве одной и з характери сти к чи сленны х методов вы ступает вели чи на относи тельного уменьш ени я LN начального промежутканеопределенности R ( N ) = . L0 Больш и нство и звестны х методов одномерной ми ни ми зац и и при меняется для классауни модальны х функц и й. О пред ел ение 1. Ф ункц и ю f (x) будем назы вать уни модальной на отрезке [ a 0 , b0 ] , если она определена во всех точках отрезка [ a 0 , b0 ] и сущ ествует

23

точка x ∈ [ a0 , b0 ] , в которой функц и я дости гает глобального ми ни мума на [ a 0 , b0 ] , при чем слева от этой точки функц и я не возрастает, а справанеубы вает. Замети м, что в данном определени и не предполагается ни гладкость, ни непреры вность функц и и . При ведем некоторы е графи чески е и ллю страц и и уни модальны х функц и й *

a0

b0

a0

b0

a0

b0

Ч и сленны е методы одномерной ми ни ми зац и и бази рую тся на вы чи слени и конечного чи сла значени й функц и и f (x) и ее прои зводны х в некоторы х точках отрезка L0 = [a 0 , b0 ] . М етоды , и спользую щ и е только значени я функц и и и не требую щ и е вы чи слени я ее прои зводны х, назы ваю тся методами ми ни ми зац и и нулевого порядка. М етоды , и спользую щ и е значени я прои зводны х делятся на методы первого, второго и т.д. порядков в зави си мости оттого, прои зводны екакого порядкаони и спользую т. Сущ ествую т две при нц и пи ально разли чны е стратеги и вы бора точек, в которы х осущ ествляю тся вы чи слени я. Е сли все точки задаю тся заранее, до начала вы чи слени й, - это пасси вная стратеги я. Е сли все точки вы би раю тся последовательно в проц ессе пои ска с учетом результатов преды дущ и х вы чи слени й, - это последовательная стратеги я. При мером реали зац и и пасси вной стратеги и является метод перебораи ли равномерного пои ска. М ето д пер ебо р а М етод перебора является простейш и м и з методов ми ни ми зац и и нулевого порядка. В начале задается начальны й промежуток неопределенности L0 = [a 0 , b0 ] и коли чество вы чи слени й функц и и N . В ы чи слени я прои зводятся в N равноотстоящ и х друг от друга точках, при этом промежуток сL0 = [a 0 , b0 ] дели тся на N + 1 равны х промежутков). П утем сравнени я вели чи н f ( xi ), i = 1, N находи тся точка x k , в которой значени е функц и и наи меньш ее. И скомая точка ми ни мума счи тается заклю ченной в промежутке [ x k −1 , x k +1 ] . А лго р итм

24

Ш аг 1. Задать начальны й промежу- ток неопределенности L0 = [a 0 , b0 ] , N - коли чество вы чи слени й функц и и . (b − a 0 ) Ш аг2. В ы чи сли тьточки x i = a 0 + i 0 , i = 1, N , равностоящ и едруг от N +1 друга. Ш аг 3. В ы чи сли ть значени я функц и и в N найденны х точках: f ( xi ), i = 1, N . Ш аг 4. Среди точек x i , i = 1, N найти такую , в которой функц и я при ни мает наи меньш еезначени е: f ( x k ) = min f ( xi ) . 1≤i ≤ N

Ш аг 5. Т очка ми ни мума x при надлежи т промежутку: x * ∈ [ x k −1 , x k +1 ] = L N , на котором в качестве при бли женного реш ени я может бы ть вы брана точка x * = xk . В результате при менени я алгори тма равномерного пои ска, после N вы чи слени й функц и и характери сти ка сужени я первоначального промежутка 2 неопределенности равна R ( N ) = . П оэтому если и значально задана N +1 требуемая вели чи на R (N ) , то требуемое для данного сокращ ени я промежутка неопределенности чи сло вы чи слени й функц и и определяется как 2 наи меньш еец елоечи сло, удовлетворяю щ ееуслови ю N ≥ − 1. R( N ) *

П р имер 1. Н айти ми ни мум функц и и f ( x) = 2 x 2 − 12 x методом перебора. Реш ени е. В оспользуемся алгори тмом перебора. 1. В качестве начального промежутка неопределенности возьмем промежуток L0 = [a 0 , b0 ] = [0,10] . Задади м N = 9 так, чтобы L0 содержал N + 1 = 10 равны х промежутков. (10 − 0) 2. О предели м точки вы чи слени я функц и и : xi = 0 + i = i, i = 1,9 . 10 3. В ы чи сли м значени я функц и и в полученны х точках: f (1) = −10 , f (2) = −16 , f (3) = −18 , f (4) = −16 , f (5) = −10 , f (6) = 0 , f (7) = 14 , f (8) = 32 , f (9) = 54 . 4. В точке x3 = 3 функц и я при ни маетнаи меньш еезначени е: f ( x 3 ) = −18 . 5. И скомая точка ми ни мума после девяти вы чи слени й при надлежи т промежутку: x * ∈ [2,4] , в котором вы би рается точка x * = x 3 = 3 . П ри этом характери сти каотноси тельного уменьш ени я начального промежутка 2 1 неопределенности R ( N ) = = . 9 +1 5

М ето ды со кр а щ ения пр о межутко в

Рассмотри м далее при меры последовательную стратеги ю . В

методов, которы е реали зую т основе данны х методов лежи т

25

последовательное сокращ ени е промежутка неопределенности . Сокращ ени е промежутка неопределенности прои зводи тся в больш и нстве методов на основе вы чи слени я функц и и в точках текущ его промежутка. Д анны е точки разби ваю т промежуток неопределенности на несколько частей. Свойство уни модальности функц и и позволяет наосновевы чи слени я функц и и в прои звольны х двух точках, при надлежащ и х промежутку, определи ть, каки м и з полученны х отрезков точками ни муманепри надлежи т. Д ействи тельно, поскольку уни модальная функц и я на промежутке [ a, x * ] не возрастает, а на промежутке [ x * , b] не убы вает, то если вы брать две точки y, z ∈ [a, b], y < z и для эти х точек f ( y ) ≥ f ( z ) , то это может бы ть ли бо си туац и я, и зображенная на ри сунке 9 и ли ри сунке 9, и в том и в другом случае x * ∈ [ y , b] . Случаю же f ( y ) ≤ f ( z ) может соответствовать только си туац и и , и зображенны е на ри сунках 8, 10, и поэтому в данном случае Рассмотренны е ни же несколько методов последовательной x * ∈ [ a, z ] . одномерной ми ни ми зац и и отли чаю тся способом вы бора точек y, z ∈ [a, b], y < z . При этом разли чны е способы вы бора точек при водят к разной скорости сокращ ени я промежутка неопределенности и к разли чному чи слу необходи мы х вы чи слени й функц и и .

f

f

a

y

x*

z

b

a y

x

Ри с. 7 f

x*

Ри с. 8 f

z

b

x

26

a

y

z

x*

b

x

x* y

a

Ри с.9

z

b

x

Ри с. 10

М ето дделения пр о межутка по по ла м М етод делени я промежутка пополам относи тся к последовательны м стратеги ям и позволяет и склю чи ть и з дальнейш его рассмотрени я на каждой и терац и и полови ну текущ его промежутка неопределенности . Работа алгори тма заканчи вается, когда дли на текущ его промежутка неопределенности оказы вается не болеенекоторой вели чи ны ε > 0 , которую назы ваю т требуемой точностью . М етод при надлежи т к методам нулевого порядка. Н а каждой и терац и и сравни ваю тся значени я функц и и в трех пробны х точках, равномерно распределенны х на текущ ем промежутке, т.е. делящ и х его начеты реравны ечасти . А лго р итм Ш аг1. Задатьначальны й промежутокнеопределенности L0 = [a 0 , b0 ] и ε > 0 - требуемую точность. Положи ть k = 0 . a + bk , L2 k = bk − a k , f x kc . Ш аг2. В ы чи сли ть: x kc = k 2 L2k L2k , z k = bk − , f ( yk ) , f (zk ) . Ш аг3. В ы чи сли ть: y k = a k + 4 4 Ш аг4. Сравни тьзначени я f ( y k ) и f ( x kc ) :

( )

а) если

( )

]

(

f ( y k ) < f x kc , и склю чи ть промежуток x kc , bk , положи в

bk +1 = x kc , a k +1 = a k . Средней точкой нового промежутка станови тся точка y k : x kc +1 = y k . П ерейти кш агу 6.

( )

б) если f ( y k ) ≥ f x kc , перейти кш агу 5. Ш аг5. Сравни ть f ( z k ) и f ( x kc ) : а)

если

( )

f ( z k ) < f x kc ,

и склю чи ть промежуток

[a

c k , xk

)

положи в

a k +1 = x kc , bk +1 = bk . Средней точкой нового промежутка станови тся точка z k : x kc +1 = z k . П ерейти кш агу 6.

( )

б) если f ( z k ) ≥ f x kc , и склю чи ть промежутки [a k , y k ), ( z k , bk ], положи в a k +1 = y k , bk +1 = z k . Средняя точка нового промежутка не и змени тся x kc +1 = x kc .

Ш аг 6. В ы чи сли ть L2( k +1) = bk +1 − a k +1 . Е сли

L2( k +1) ≤ ε , алгори тм

заверш ает свою работу, и делается вы вод, что x * ∈ L2( k +1) , а в качестве при бли женного реш ени я можно, напри мер, взять середи ну данного

27

Е сли же L2( k +1) > ε , то положи ть k = k + 1 и перейти к

промежутка.

ш агу 3. Следует замети ть, что для данного метода на каждой и терац и и , начи ная со второй, вы чи сляется значени ефункц и и только в двух точках, так как средняя точка нового промежутка всегда совпадает с одной и з точек рассматри ваемы х на преды дущ ей и терац и и . Т аки м образом, для данного 1 метода R ( N ) = N , где N - коли чество вы чи слени й функц и и . Н умерац и я 2 2 промежутков неопределенности подчерки вает тот факт, что на каждой и терац и и вы чи сляется двазначени я функц и и . П р имер 2. Н айти ми ни мум функц и и f ( x) = 2 x 2 − 12 x методом делени я промежуткапополам. Реш ени е. В качестве начального промежутка неопределенности рассмотри м промежуток L0 = [a 0 , b0 ] = [0,10] и положи м ε = 1. 1. П оложи м k = 0 . 0 + 10 2. В ы чи сли м: x 0c = = 5, L0 = 10, f x 0c = −10 . 2 10 10 3. В ы чи сли м y 0 = 0 + = 2,5, z 0 = 10 − = 7,5 , f ( y 0 ) = −17,5 , 4 4 f ( z 0 ) = 22,5 .

( )

( )

4. f ( y 0 ) < f x 0c , поэтому положи м a1 = a 0 = 0, b1 = x 0c = 5 , x1c = y 0 = 2,5 . 5. П олучи м L2 = [0,5], L2 = 5 > ε = 1. Положи м k = 1 и перейдем кш агу 3. 5 5 y1 = 0 + = 1,25, z1 = 5 − = 3,75 , 6. В ы чи сли м f ( y1 ) = −11,875 , 4 4 f ( z1 ) = −16,875 .

( ) f ( z ) > f (x ) ,

7. f ( y1 ) > f x1c , поэтому перейдем кш агу 5. 8.

1

c 1

поэтому

положи м

a 2 = y1 = 1,25 ,

b2 = z1 = 3,75 ,

x 2c = x1c = 2,5 . 9. П олучи м L 4 = [1,25;3,75], L4 = 2,5 > ε . П оложи м k = 2 и перейдем к ш агу 3. П осле третьего прохода алгори тма, получи м L8 = [ 2,81;3,43], L8 = 0,62 < ε = 1 . Д ости гнута требуемая точность, поэтому алгори тм заканчи вает свою работу с N = 8 . Х арактери сти ка относи тельного 1 сокращ ени я промежутка R ( N ) = . В качестве реш ени я можно взять 16 средню ю точку последнего промежутка x * = x 4c = 3,125 . М ето д зо ло то го сечения М етод золотого сечени я относи тся к последовательны м методам нулевого порядка. В методезолотого сечени я двевнутренни еточки , которы е и спользую тся для сокращ ени я промежутка неопределенности , вы би раю тся

28

таки м образом, чтобы одна и з ни х и спользовалась с той же ц елью и на следую щ ем уже сокращ енном промежутке. Т акое прави ло вы бора точек при води т к тому, что чи сло вы чи слени й функц и и сокращ ается вдвое и одна и терац и я требует расчета только одного нового значени я функц и и . Т аки ми свойствами обладаю тточки , назы ваемы еточками золотого сечени я. Говорят, что точка прои зводи т золотое сечени е промежутка, если отнош ени е дли ны всего промежутка к дли не больш ей части равно отнош ени ю дли н больш ей части кменьш ей. В методе золотого сечени я на промежутке [ a, b] си мметри чно относи тельно его конц ов вы би раю тся точки y и z , таки ечто b−a b− y b−a z−a = = = b− y y−a z−a b−z П ри этом точка y прои зводи тзолотоесечени е промежутка [ a, z ] , а точка z промежутка [ y, b] . А лго р итм Ш аг1. Задатьначальны й промежутокнеопределенности L0 = [a 0 , b0 ] и ε > 0 - требуемую точность. Положи ть k = 0 . 3− 5 Ш аг 2. В ы чи сли ть: y0 = a0 + (b0 − a 0 ), z 0 = a 0 + b0 − y 0 , 2 3− 5 = 0,38196 . 2 Ш аг3. В ы чи сли ть f ( y k ), f ( z k ) . Ш аг4. Сравни ть f ( y k ) и f ( z k ) : и а) если f ( yk ) ≤ f (zk ) , то положи ть a k +1 = a k , bk +1 = z k y k +1 = a k +1 + bk +1 − y k , z k +1 = y k . П ерейти кш агу 5. б) если f ( y k ) > f ( z k ) , то положи ть a k +1 = y k , bk +1 = bk и y k +1 = z k , z k +1 = a k +1 + bk +1 − y k . П ерейти кш агу 5. k + 1, k ≠ 0 и провери ть Ш аг 5. В ы чи сли ть L N = a k +1 − bk +1 , N =  k 2 , = 0  услови е окончани я. Е сли L N ≤ ε , то проц есс пои ска заверш ается и x * ∈ [ a k +1 , bk +1 ] . В качестве при бли женного реш ени я можно взять середи ну a + bk +1 последнего промежутка x * = k +1 . Е сли L N > ε , положи ть k = k + 1 и 2 перейти кш агу 3. Д ля метода золотого сечени я характери сти ка относи тельного уменьш ени я промежутканеопределенности равна R ( N ) = (0,618) N −1 , где N коли чество вы чи слени й функц и и . 127 2 61 П р имер 3. Н айти ми ни мум функц и и f ( x) = x − x + 2 методом 4 4 золотого сечени я.

29

Реш ени е. В качестве начального промежутка неопределенности возьмем промежуток L0 = [a 0 , b0 ] = [0;0,5] , положим ε = 0,15 . 1. П оложи м k = 0 . 2. В ы чи сли м y 0 = a 0 + 0,382(b0 − a 0 ) = 0,191 ; z 0 = a 0 + b0 − y 0 = 0,309 . 3. В ы чи сли м f ( y 0 ) = 0,245; f ( z 0 ) = 0,319 . 4. Т аккак f ( y 0 ) < f ( z 0 ) , то a1 = a 0 = 0; b1 = z 0 = 0,309 ; y1 = a1 + b1 − y 0 = 0,118; z1 = y 0 = 0,191 . 5. П олучи м L2 = [0;0,309]; L2 = 0,309 > ε = 0,15 . Положи м k = 1 и перейдем кш агу 3. 6. В ы чи сли м f ( y1 ) = 0,642; f ( z1 ) = 0,245 . 7. Т ак как f ( y1 ) > f ( z1 ) , то a 2 = y1 = 0,118; b2 = b1 = 0,309; y 2 = z1 = 0,191; z 2 = a 2 + b2 − z1 = 0, 236 . 8. П олучи м L2 = [0,118;0,309]; L3 = 0,191 > ε = 0,15 . П оложи м k = 2 и перейдем кш агу 3. 9. В ы чи сли м f ( y 2 ) = 0,245; f ( z 2 ) = 0,162 . 10. Т ак как f ( y2 ) > f (z2 ) , то a 3 = y 2 = 0,191; b3 = b2 = 0,309; y 3 = z 2 = 0,236; z 3 = a 3 + b3 − z 2 = 0,264 . 11. П олучи м L 2 = [0,191;0,309];

L 4 = 0,118 < ε = 0,15 ; x * ∈ L 4 , N = 4 . В 0,191 + 0,309 = 0,25 . качествереш ени я можно взять x * = 2 Д ля данного при мера характери сти ка относи тельного уменьш ени я начального промежутканеопределенности равна R( N ) = (0,618) 3 = 0,236 . М ето д хо р д (секущ их) М етод хорд относи тся к последовательны м методам первого порядка. В основе данного метода лежи т следую щ ее обосновани е. Н еобходи мы м и достаточны м услови ем глобального ми ни мума вы пуклой непреры вно ди фференц и руемой функц и и является равенство f ′( x) = 0 . Е сли на конц ах промежутка [ a, b] прои зводная f ′(x) и меетразны езнаки , т.е. f ′( a) f ′(b) < 0 , то на промежутке найдется точка, в которой f ′(x) обращ ается в нуль, и пои ск точки ми ни мума f (x) на промежутке [ a, b] экви валентен реш ени ю уравнени я f ′( x) = 0, x ∈ [a, b] . Д ля при бли женного реш ени я данного уравнени я можно и спользовать метод хорд. Э тотметод основан на сокращ ени и отрезков путем определени я точки y пересечени я сосью OX хорды графи кафункц и и f ′(x) . К оорди нататочки f ′(a) y определяется по формуле y = a − ( a − b) . f ′(a ) − f ′(b)

30

f '

a

y

x*

b x

О трезок дальнейш его пои ска [ a; y ] и ли [ y; b] вы би рается в зави си мости от знака f ′( y ) . Е сли f ′( y ) > 0 , то вы би рается [ a; y ] , если f ′( y ) < 0 - [ y; b] . Т аки м образом, метод и спользуется при нали чи и и нформац и и об отрезке[ a, b] таком, что f ′(a ) < 0 , а f ′(b) > 0 . У слови е дости жени я требуемой точности в данном алгори тме наклады вается не на дли ну промежутка неопределенности , а на вели чи ну f ′( y k ) . А лго р итм Ш аг1. Задатьначальны й промежутокнеопределенности L0 = [a 0 , b0 ] и ε > 0 - требуемую точность. Положи ть k = 0 . f ′( a k ) Ш аг2. В ы чи сли ть y k = a k − ( a k − bk ) . f ′( a k ) − f ′(bk ) Ш аг3. В ы чи сли ть f ′( y k ) . Ш аг4. Е сли f ′( y k ) ≤ ε , то положи ть x * = y k , f ( x * ) = f ( y k ) и пои ск заверш и ть, и начеперейти кш агу 5. Ш аг5. Е сли f ′( y k ) > 0 , то положи ть b = y k , f ′(b) = f ′( y k ) , и наче положи ть a = y k , f ′(a ) = f ′( y k ) . П оложи ть k = k + 1 и перейти кш агу 2. В данном методемы предполагали , что f ′( a) f ′(b) < 0 . При наруш ени и этого услови я точку x * можно указатьсразу. Т ак, если f ′( a) > 0 и f ′(b) > 0 , то f (x) возрастает на [ a, b] , следовательно, x * = a , если

f ′(a) < 0 и

f ′(b) < 0 , то f (x) убы вает на [ a, b] , следовательно, x * = b . В случае, если прои зводная равна 0 на одном и з конц ов отрезка [ a, b] , то этот конец и является реш ени ем задачи . П р имер 4. Н айти ми ни мум функц и и f ( x) = x 4 + e − x методом хорд. Реш ени е. В качестве начального промежутка неопределенности возьмем промежуток L0 = [a 0 , b0 ] = [0;1] , положи м ε = 0,05 .

31

У слови евы полнено. 1. П ровери м услови е f ′(0) f ′(1) < 0 . 2. П оложи м k = 0 . 3. В ы чи сли м точку y 0 = 0,216; f ′( y 0 ) = −0,766 . 4. Т аккак f ′( y 0 ) > ε = 0,05 , то переходи м кш агу 3. 5. П оскольку f ′( y 0 ) < 0 положи м a1 = y 0 , b1 = b0 , f ′( a1 ) = −0,766 . 6. П ри сваи ваем k = 1 и переходи м кш агу 2. 7. В ы чи сли м точку y1 = 0,352; f ′( y1 ) = −0,528 . 8. Т аккак f ′( y1 ) > ε = 0,05 , то переходи м кш агу 3. 9. П оскольку f ′( y1 ) < 0 положи м a 2 = y1 , b2 = b1 , f ′(a 2 ) = −0,528 . 10. П ри сваи ваем k = 2 и переходи м кш агу 2. Н а 6-й и терац и и получаем промежуток с конц ами a 5 = 0,504, b5 = 1. Н а данном промежутке метод генери рует точку y 5 = 0,516 , в которой f ′( y 5 ) = −0,046 . А лгори тм заверш ает работу, поскольку дости гнута требуемая точность f ′( y 5 ) < ε = 0,05 . М ето д Ньюто на М етод Н ью тонаявляется последовательны м методом второго порядка. П редполагается, что функц и я f (x) дважды ди фференц и руема, при чем f ′′( x) > 0 (это гаранти руетвы пуклостьфункц и и f (x) ). В этом случаекорень уравнени я f ′( x) = 0 можно при бли женно и скать методом касательны х. В отли чи е от преды дущ и х методов, метод Н ью тона не относи тся к методу сокращ ени я промежутков. Д ля начала работы метода вместо задани я начального промежутка неопределенности требуется задани е начальной точки x 0 , в которой вы чи сляется f ′( x 0 ) и f ′′( x 0 ) . В проц ессе работы методагенери руется последовательность x k , k = 1,2... В очередной точке x k строи тся ли нейная аппрокси мац и я функц и и f ′(x) (касательная к графи ку f ′(x) ). Т очка, в которой ли нейная аппрокси ми рую щ ая функц и я обращ ается в нуль, и спользуется в качествеследую щ его при бли жени я x k +1 . У равнени е касательной к графи ку f ′(x) в точке x k и меет ви д y = f ′( x k ) + f ′′( x k )( x − x k ) , поэтому точка x k +1 , найденная и з услови я y = 0 , f ′( x k ) определяется формулой x k +1 = x k − . f ′′( x k ) П роц едура нахождени я точек x k продолжается до тех пор, пока не будетдости гнутатребуемая точность, т.е. f ′( x k ) ≤ ε . А лго р итм Ш аг1. Задатьначальную точку x 0 , ε > 0 - требуемую точность. П оложи ть k = 0 . Ш аг2. В ы чи сли ть f ′( x k ) . Ш аг3. Е сли f ′( x k ) ≤ ε , то положи ть x * = x k , f ( x * ) = f ( x k ) и пои ск заверш и ть, и начеперейти кш агу 4.

32

Ш аг4. В ы чи сли ть

x k +1 = x k −

f ′( x k ) . f ′′( x k )

Ш аг5. П оложи ть k = k + 1. П ерейти кш агу 2. И сследовани я методаН ью тонапоказы ваю т, что при достаточно бли зком к точкеми ни мума x * вы бореначального при бли жени я x 0 , гаранти руется скоростьсходи мости последовательности x k , k = 0,1,... к x * ви да k

x k − x * ≤ Cq 2 , q ∈ (0;1), C > 0 ,

q и C зави сят от функц и и

f (x) и

вы бора точки x 0 . Е сли начальное при бли жени е x 0 вы брано не достаточно бли зко к точке x * , то последовательность x k , k = 0,1,... метода Н ью тона может расходи ться. В подобны х случаях необходи мо найти лучш ее начальное при бли жени е x 0 , напри мер, с помощ ью нескольки х и терац и й методазолотого сечени я. 1 П р имер 5. Н айти ми ни мум функц и и f ( x) = xarctgx − ln(1 + x 2 ) 2 методом Н ью тона. Реш ени е. Д анная функц и я дважды ди фференц и руема и 1 f ′′( x) = > 0 . В качестве начального при бли жени я возьмем точку 1 + x 02 x 0 = 1 , положи м ε = 10 −7 . 1. В ы чи сли м f ′( x 0 ) = 0,785 .

2. П оскольку f ′( x 0 ) > ε = 10 −7 , то перейдем кш агу 4. f ′( x 0 ) 3. В ы чи сли м x1 = x 0 − = −0,57 . f ′′( x 0 ) 4. П оложи м k = 1 . П ерейти кш агу 2. 5. В ы чи сли м f ′( x1 ) = −0,519 . 6. П оскольку f ′( x1 ) > ε = 10 −7 , то перейдем кш агу 4. f ′( x1 ) 7. В ы чи сли м x 2 = x1 − = 0,117 . f ′′( x1 ) 8. П оложи м k = 2 . П ерейти кш агу 2. 9. П оскольку f ′( x 2 ) > ε = 10 −7 , то перейдем кш агу 4. f ′( x 2 ) 10. В ы чи сли м x3 = x 2 − = −1,061 ⋅ 10 −3 . f ′′( x 2 ) 11. П оложи м k = 3 . П ерейти кш агу 2. 12. В ы чи сли м f ′( x 3 ) = −1,061 ⋅ 10 −3 . 13. П оскольку f ′( x3 ) > ε = 10 −7 , то перейдем кш агу 4. f ′( x3 ) 14. В ы чи сли м x 4 = x3 − = 9 ⋅ 10 −8 . f ′′( x3 )

15. П оложи м k = 4 . П ерейти кш агу 2. 16. В ы чи сли м f ′( x 4 ) = 9 ⋅ 10 −8 . 17. П оскольку

33

f ′( x3 ) < ε = 10 −7 , проц есс пои ска заканчи вается. В качестве

реш ени я задачи при ни мается точка x * = x 4 = 9 ⋅ 10 −8 ≈ 0 . Бы страя сходи мость метода Н ью тона для рассмотренного при мера объ ясняется хорош и м вы бором начального при бли жени я x 0 . Е сли , напри мер, для данной функц и и в качестве начального при бли жени я вы брать x 0 = 3 , то методом будетгенери роваться последовательностьточек x1 = −9,5; x 2 = 124; x 3 = −23905; x 4 = 8,97 ⋅ 10 8 ; x 5 = −1,27 ⋅ 1018 ;... , которая расходи тся. З а да чи для са мо сто ятельно го р еш ения

1. Разли чны ми чи сленны ми методами одномерной ми ни ми зац и и (метод перебора, метод делени я отрезка пополам, метод золотого сечени я, метод хорд, метод Н ью тона) найти реш ени еследую щ и х задач. 1) f ( x) = x 3 − 3 sin x → min, x ∈ [0,1], x * = 0,8241 ; 2) f ( x) = x 4 + x 2 + x + 1 → min, x ∈ [ −1,0], x * = −0,3855 ; 1 3) f ( x) = e x + → min, x ∈ [0,5;1,5], x * = 0,7035 ; x 2 4) f ( x) = x + e − x → min, x ∈ [0,1], x * = 0,3517 ; 5) f ( x) = x 2 + x + sin x → min,

x ∈ [ −1;0], x * = −0,8354 ;

6) f ( x) = x 2 − x + e − x → min, x ∈ [0;1], x * = 0,7388 . 2. М ожет ли при менени е методов и склю чени я отрезков при вести к неверному определени ю x * , если функц и я f (x) не является уни модальной? О тветпоясни тьри сунком. 3. Т ребуется найти точку ми ни мума уни модальной функц и и на отрезке дли ны 1 сточностью ε = 0,02 . И меется возможностьи змери тьнеболее10 значени й функц и и f (x) . К акой и з прямы х методов ми ни ми зац и и можно и спользоватьдля этого? 4. У казатьклассфункц и й, для которы х точноеопределени еточки ми ни мума гаранти ровано в результатевсего одной и терац и и методаН ью тона?

М ето ды безусло в но йминимиза ции в Rn Д ля чи сленного реш ени я задачбезусловной ми ни ми зац и и ви да f ( x) → min x∈R n

разработано много алгори тмов, и спользую щ и х и терац и онны епроц едуры x k +1 = x k + α k y k , где y k − направлени епои скаточки xk+1 и з точки xk, а чи сло α k - вели чи наш агав вы бранном направлени и . Работатаки х алгори тмов накаждой и терац и и прои сходи тпо следую щ ей схеме:

34

Ш аг1. П ровери тьуслови я остановаи , если они вы полнены , вы чи слени я прекрати тьи взятьточку x k в качествеи скомого реш ени я. Ш аг2. Зафи кси роватьненулевой вектор y k в качественаправлени я пои ска. Ш аг3. В ы братьчи сло α k − вели чи ну ш ага. Ш аг4. П оложи ть x k + 1 = x k + α k y k Д ля проверки услови й останованаш аге1 напракти кечасто и спользую тся следую щ и екри тери и : ||xk+1 - xk||< ε , |f(xk+1) - f(xk)|<ε , || ∇ f ( x k ) ||< ε , где ε - заданны й параметр точности . К роме того, при практи ческой реали зац и и эти алгори тмы полезно дополнять "дежурны м" кри тери ем останова k ≤ N max , где N max − задаваемое заранее макси мальное чи сло и терац и й. В качестве вектора y k на ш аге 2 могут вы би раться еди ни чны е орты (покоорди натны й спуск), анти гради ент в точке xk (гради ентны е методы ) и други е направлени я. В ели чи на ш ага α k , как прави ло, вы би рается так, чтобы вы полнялось услови е f ( x k +1 ) ≤ f ( x k ) . В частности , чтобы гаранти ровать вы полнени е этого неравенства, можно вы би рать k k α k = arg min f ( x + α y ) ( будем в дальнейш ем это назы вать прави лом α

наи скорейш его спуска). Д ля чи сленного оты скани я α k может бы ть и спользован оди н и з методов, опи санны х в преды дущ ем параграфе. Рассмотри м при меры алгори тмов, построенны х в соответстви и с предложенной схемой.

М ето дпо ко о р дина тно го спуска . Э тотметод заклю чается в последовательной ми ни ми зац и и ц елевой функц и и f(x) сначалапо направлени ю первого бази сного векторае 1 ,затем второго е 2 и т.д. Т аки м образом, здесь y k = e k , α k вы би рается в соответстви и справи лом наи скорейш его спуска. Послеокончани я ми ни ми зац и и по направлени ю последнего бази сного векторае n ц и кл может повторяться. М етод покоорди натного спускаможетбы тьметодом нулевого порядка, т.к. он можетнеи спользоватьв работепрои зводны х функц и и f(x). Т аки м образом, он можетпри меняться для опти ми зац и и неди фференц и руемы х функц и й. А лго р итм. Ш аг0. В ы братьначальноепри бли жени ех 0 в пространствеR n , задатьпараметрточности ε . Н айти f(x0),положи тьj=1. Ш аг1. Pеш и тьзадачу одномерной ми ни ми зац и и

35

Ф (α )=f(x0+ α

ej) → min , т.е. найти α *. α ∈R

П оложи тьх 1=х 0+ α *е j, вы чи сли тьf(x1). Ш аг2. Е сли j
в ви де f ( x1 ,.., x n ) = ∑ f i ( x i ) , то через n ш агов алгори тма находи тся i =1

опти мальноереш ени е. П р имер 1. Реш и тьзадачу f ( x) = 2 x12 + x22 → min методом покоорди натного спуска. Реш ени е. Д анная функц и я является сепарабельной. В ы берем x1 x0 прои звольную начальную точку, напри мер, x0=(3,3). В результате ми ни ми зац и и по направлени ю e1 , очеви дно, получается точка 1 x =(0,3), а ми ни ми зац и я по x* 3 направлени ю e2 при води т к опти мальному реш ени ю x*=(0,0).

П р имер 2. Реш и тьзадачу f ( x) = 2 x12 + x 22 + x1 x 2 → min методом покоорди натного спуска. Реш ени е. 0. Задади м x0=(0.5,1), f(x0)=2. В качествекри тери я остановавы берем кри тери й |f(x0)-f(x1)|<ε и задади м ε =0.1. 1. В качествепервого направлени я вы би раем e1. Реш и м задачу одномерной ми ни ми зац и и по α : Φ (α ) = 2 (0.5 + α ) 2 + (0.5 + α ) → min . α*=-0.75, х1=(-0.25,1), f(x1)=0.375. 0 1 1 x x 2. П олагаем х 0=х 1 . 3. В качествеследую щ его направлени я вы би раем е 2. Запи сы ваем задачу

36

одномерной ми ни ми зац и и : Φ (α ) = (1 + α ) 2 − 0.25(1 + α ) → min . α *=-0.875. 1 х =(-0.25,0.125), f(x1)=0.11. 0,5 4. П роверяем кри тери й останова: |0.375-0.11|=0.265>ε 5. В качестве направлени я снова вы би раем e1. Реш и м задачу одномерной ми ни ми зац и и по α : 2 Φ (α ) = 2 ( −0.25 + α ) + 0.125 (−0.25 + α ) → min . α * ≈ 0.22. х 1=(-0.03,0.125), f(x1) ≈ 0.021. 0 1 6. П олагаем х =х . 7. В качестве направлени я вы би раем е 2. Запи сы ваем задачу одномерной ми ни ми зац и и : Φ (α ) = (0.125 + α ) 2 − 0.03(0.125 + α ) → min . α *=-0.11. х 1=(-0.03,0.015), f(x1) ≈ 0.001. 4. Проверяем кри тери й останова: |0.021-0.001|=0.02<ε . Полагаем x*=(-0.03,0.015), f*=0.001. Замечани е. И з графи ческой и ллю страц и и ви дно, что опти мальны м реш ени ем является ц ентрконц ентри чески х элли псов - точка(0,0) .

М ето ды гр а диентно го по иска . П редставленны едалееметоды и спользую туслови еди фференц и руемости функц и и f(x) в Rn. В качествекри тери я остановатаки х методов, какправи ло, вы би рается услови е|| ∇ f ( x k ) ||< ε . В качественаправлени я дви жени я для оты скани я ми ни мумав методах гради ентного спусканакаждом ш аге вы би рается вектор- анти гради ент y k = −∇ f ( x k ) . К аки звестно, в малой окрестности точки xk анти гради ентобеспечи ваетнаи скорейш ееубы вани е функц и и . При ведем двавари антаметодов гради ентного спуска (отли чаю щ и еся способом оты скани я вели чи ны α ). А лго р итм мето да др о бления ш а га . Ш аг0. Задатьпараметрточности ε , начальны й ш аг α > 0 , вы брать х 0 ∈ R n ,вы чи сли тьf(x0). Ш аг1. Н айти ∇f ( x 0 ) и провери тькри тери й останова: || ∇f ( x 0 ) ||<ε . Е сли он вы полнен, то вы чи слени я заверш и ть, полагая x*=x0, f*=f(x0) . Ш аг2. П оложи тьх 1=х 0- α ∇f ( x 0 ) , вы чи сли тьf(x1). Е сли f(x1)
37

2. Задади м x0=(0.5,1), f(x0)=1.5. 3. ∇f ( x 0 ) =(2, 2), || ∇f ( x 0 ) ||>ε .

В ы берем ε =0.01, α = 1 .

4. П оложи м х 1=х 0- ∇f ( x 0 ) =(0.5 -2, 1-2)=(-1.5,-1), f(x 1)=5,5, f(x1)>f(x0). 5. П оложи м α = α =1/2 и перейдем кш агу 2. 2 1 0 1 6. П оложи м х =х - 2 ∇f ( x 0 ) =(0.5 -1, 1-1)=(-0.5,0), f(x1)=0.5. Т аккак f(x1)ε 8. П оложи м х 1=х 0-

1 2

∇f ( x 0 ) =(-0.5 +1, 0)=(0.5,0), f(x1)=0.5, f(x1)=f(x0).

9. П оложи м α = α =1/4 и перейдем кш агу 2. 2 1 0 1 10. П оложи м х =х - 4 ∇f ( x 0 ) =(-0.5 +0.5, 0)=(0,0), f(x1)=0, f(x1)0 0

П оложи тьх =х - α * ∇f ( x ) и перейти кш агу 1. П р имер 1. Реш и тьзадачу f ( x) = x12 + x 22 − 4 x1 − 2 x 2 → min методом наи скорейш его спуска. Реш ени е. ∇f ( x) = (2 x1 − 4,2 x 2 − 2) И т е рация1. 0 0.Задади м x =(4,5). В ы берем ε =0.01. 1. ∇f ( x 0 ) =(4, 8), || ∇f ( x 0 ) ||>ε . 2. Реш и м задачу одномерной ми ни ми зац и и по α : Φ (α ) = f(х 0 − α∇f ( x 0 )) = (4 − 4α ) 2 + (5 − 8α ) 2 − − 4(4 − 4α ) − 2(5 − 8α ) → min . 0

0

α *=0.5. х 0=х 0- α * ∇f ( x 0 ) =(4-4·0.5, 5-8·0.5)=(2,1). И т е рация2. 0 0 3. ∇f ( x ) =(0,0), || ∇f ( x ) ||=0<ε - останов, найдено точноереш ени е. Графи ческая и ллю страц и я реш ени я при ведена на ри сунке. В данном случае ли ни и уровня являю тся конц ентри чески ми окружностями . В ектор -гради ент,

38

x0

.

∇f (x0 )

x*

П р имер 2. Реш и тьзадачу f ( x) = 2 x12 + x 22 + x1 x 2 → min методом наи скорейш его спуска. Реш ени е. ∇f ( x ) = ( 4 x 1 + x 2 , 2 x 2 + x 1 ) И т е рация1 0 12. Задади м x =(0.5,1), ε =0.4. 13. ∇f ( x 0 ) =(3, 2.5), || ∇f ( x 0 ) ||=3.9>ε . 3. Реш и м задачу одномерной ми ни ми зац и и по α : x0

Φ (α ) = f(х 0 − α∇f ( x 0 )) = 2(0.5 − 3α ) 2 + + (1 − 2.5α ) 2 + (0.5 − 3α )(1 − 2.5α ) → min α *=0.24. х 0=х 0- α * ∇f ( x 0 ) =(0.5-3·0.24, 1-2.5·0.24)= =(-0.22,0.4).

0.5

И т е рация2. 4. ∇f ( x 0 ) =(-0.48, 0.58), || ∇f ( x 0 ) ||=0.752>ε . 5. Реш и м задачу одномерной ми ни ми зац и и .

Φ (α ) = f(х 0 − α∇f ( x 0 )) = 2( −0.22 + 0.48α ) 2 + (0.4 − 0.58α ) 2 + + (−0.22 + 0.48α )(0.4 − 0.58α ) → min

α *=0.546, х 0=х 0- α *, ∇f ( x 0 ) = ( −0.22 + 0.48α , 0.4 − 0.58α ) =(0.04, 0.08) И т е рация3. 14. ∇f ( x 0 ) =(-0.24, 0.2), || ∇f ( x 0 ) ||=0.312<ε ⇒ x* = x 0 = (0.04 , 0.08 ) . Заданная точностьдости гнута, однако опти мальноереш ени я x min = (0,0 ) за2 и терац и и найдено небы ло. И з графи ческой и ллю страц и и ви дно, что ли ни ями уровня в данной задачеявляю тся конц ентри чески еэлли псы и получаемы ев ходеалгори тманаправлени я непроходятчерез и х ц ентр.

39

Д ажедля квадрати чны х функц и й сходи мостьгради ентны х методов законечноечи сло и терац и й негаранти рована. О днако если квадрати чная функц и я n переменны х при веденакви ду суммы полны х квадратов, то ееопти мум можетбы тьнайден в результатереали зац и и n одномерны х пои сков по преобразованны м коорди натны м направлени ям. П роц едурапреобразовани я квадрати чной функц и и f ( x) = a + bx T + 12 xHx T к ви ду суммы полны х квадратов экви валентнанахождени ю такой матри ц ы преобразовани я Q, которая при води тматри ц у квадрати чной формы к ди агональному ви ду. Т аки м образом, заданная квадрати чная форма xHx T путем преобразовани я x=zQ при води тся кви ду xHx T = zQ T HQz T = zD z T , где D -ди агональная матри ц а. П усть q j − j - тая строкаматри ц ы Q. Т огда преобразовани еx= zQ позволяетзапи сатькажды й векторx в ви дели нейной комби нац и и векторов q j : x= zQ= z1q 1 + z 2 q 2 + .. + z n q n . Д руги ми словами , осущ ествляется переход кновой си стемекоорди нат, задаваемой векторами q j ( замети м, что это преобразовани енеявляется еди нственны м). Т аки м образом, спомощ ью преобразовани я переменны х квадрати чной функц и и о о р дина т , с о в п а да ю щ их с гла в ны м ио сям и

квадрати чной функц и и . Следовательно, одномерны й пои скточки ми ни мума в пространствепреобразованны х переменны х экви валентен пои ску вдоль каждой и з главны х осей квадрати чной функц и и . Д ля полученной си стемы векторов q j будутвы полняться равенства q i H ( q j ) T = 0, i ≠ j. О пред ел ение. Си стемали нейно незави си мы х векторов q j , для которой вы полняю тся равенства q i H ( q j ) T = 0, i ≠ j , назы вается си стемой Hсопряженны х направлени й. И так, если заданы лю бы еn H-сопряженны х направлени й q 1 , q 2 ..q n , то проц едура x k +1 = x k + α k q k , гдеα k = arg min f ( x k + α q k ) , k = 1,2...n , α

позволяетнайти ми ни мум квадрати чной функц и и . Т аккакдостаточно больш ой классц елевы х функц и й можетбы ть представлен в окрестности точки ми ни мумасвоей квадрати чной аппрокси мац и ей, опи санная и дея при меняется и для неквадрати чны х функц и й. П остроени е си стемы H- сопряженны х направлени й возможно разли чны ми способами . Рассмотри м некоторы еи з ни х. М ето д со пр яжё нны х на пр а в ленийП а уэ лла И терац и онны й проц есс в методе П ауэлла органи зуется без предвари тельного построени я H- сопряженны х векторов, которы е последовательно находятся в проц ессе ми ни ми зац и и с и спользовани ем свойствапараллельного подпространства.

40

У т верж д ение ( с войс т во парал- ле льного подпрос т ранс т ва). Е сли точка y 1 найденав результатепои скаи з точки x 1 вдолькаждого и з m (m
при последовательном дви жени и и з некоторой начальной точки x по (n+1) направлени ям q 0 , q 1 ,.., q n , при этом каждая получаемая точкаи спользуется в качестве и сходной для пои ска по следую щ ему направлени ю . По свойству параллельного подпространства, направлени е, проходящ ее через точки , полученны епри первом и последнем пои ске, будетH- сопряжено с q n . Д алее заменяется q1 на q 2 , q 2 на q 3 и т.д. В качественаправлени я q n вы би рается полученное сопряженное направлени е, после чего повторяется пои ск по (n+1) направлени ям (уже не содержащ и м старого направлени я q1 ). Д ля квадрати чны х функц и й последовательность n 2 одномерны х пои сков при води ткточкеми ни мума. А лго р итм мето да со пр яжё нны хна пр а в лений. Ш аг0. Задатьпараметрточности ε , вы братьх 0 ∈ R n , положи тьк =0, i=0 , q j = e j , j = 1, n, q 0 = e n , y 0 = x 0 . Ш аг1. Н айти yi+1=yi+ α i qi , где α i = arg min f ( y i + α q i ) α

Ш аг2. П ровери тьуслови еi=n . а) Е сли оно вы полняется, то вы ясни тьуспеш ностьпои скапо n последни м направлени ям. Е сли yn+1=y1, пои скзаверш и ть, полагая x*= yn+1. b) Е сли i
41

Реш и м задачу одномерной ми Φ (α ) = (1 + α ) 2 + 12 (1 + α ) → min

ни ми зац и и :

α 0 = − 45 ⇒ y 1 = ( 12 ,− 41 ) . 2. Т аккакi<2, положи м i=1 и перейдем кш агу 1. 3. y 2 = ( 12 ,− 41 ) + α 1 (1,0) = ( 12 + α 1 ,− 41 ) . Реш и м задачу одномерной ми ни ми зац и и : Φ (α ) = 2 ( 21 + α ) 2 − 41 ( 12 + α ) → min 7 α 1 = − 16 ⇒ y 2 = ( 161 ,− 41 ) . 4. Т аккакi<2, положи м i=2 и перейдем кш агу 1. 5. y 3 = ( 161 ,− 41 ) + α 2 (0,1) = ( 161 , α 2 − 41 ) . Реш и м задачу одномерной ми ни ми зац и и : Φ (α ) = ( − 41 + α ) 2 + 161 ( − 41 + α ) → min 7 1 α 2 = 32 ⇒ y 3 = ( 161 ,− 32 ). 1 ). 6. Т аккак i=2 и y3 ≠ y1 , положи м х 1= y 3 = ( 161 ,− 32 7 7 1 ), 7. Положи м q 1 = e 2 , q 0 = q 2 = y 3 − y 1 = (− 16 , 32 ) , y 0 = ( 161 ,− 32 i=0 , к =2 и перейдем кш агу 1. 7 7 1 8. y 1 = ( 161 ,− 32 ) + α 0 (− 16 , 32 ) = (

1 −7 α 0 −1 + 7 α 0 , 32 16

) .

Реш и м задачу одномерной ми ни ми зац и и : Φ (α ) = 2 ( α0 =

1 7

1 −7 α 0 2 ) 16 1

+(

−1 + 7 α 0 2 ) 32

+(

1 −7α 0 16

)(

−1 + 7 α 0 32

) → min

⇒ y = (0 ,0 ) .

9. Т аккакi<2, положи м i=1 и перейдем кш агу 1. 10. y 2 = (0,0 ) + α 1 (0,1) = (0,α 1 ) . Реш и м задачу одномерной ми ни ми зац и и : Φ (α ) = α 2 → min α 1 = 0 ⇒ y 2 = (0,0 ) . 11. Т аккакi<2, положи м i=2 и перейдем кш агу 1. 7 7 y 3 = (0,0 ) + α 2 (− 16 , 32 ) = ( −

7α 2 7α 2 , 32 ) . 16

Реш и м задачу одномерной ми ни ми зац и и : 7α 2 2 ) 16 3

Φ (α ) = 2( −

+(

7α 2 2 ) 32

−

7α 2 7α 2 16 32

→ min

α 2 = 0 ⇒ y = (0,0 ) . 12. Т аккак i=2 и y3 = y1 , положи м x*= y3 =(0,0). Графи ческая и ллю страц и я реш ени я при веденанари сунке x0

1

42

x*

x1

0.5

y1

y2

М ето д со пр яжё нны х гр а диенто в Д анны й метод позволяетполучать сопряженны енаправлени я p k для квадрати чной функц и и f(x) си спользовани ем еепрои зводны х. В качестве p 0 вы би рается вектор-анти гради ент, а остальны е направлени я вы чи сляю тся по βk pk, k = 0, n − 1 , где формуле pk+1= - ∇f ( x k +1 ) + β k = || ∇f ( x k +1 ) || 2 || ∇f ( x k ) || 2 . Ф ормула пересчета точки x k +1 и меет ви д х k+1=х k+ α k pk , при чем ш аг α k и щ ется по прави лу наи скорейш его спуска. П ри отсутстви и вы чи сли тельны х погреш ностей метод сопряжённы х гради ентов обеспечи вает оты скани е ми ни мума квадрати чны х функц и й не болеечем заn и терац и й. Д ля неквадрати чны х функц и й сходи мостьметодаза конечноечи сло и терац и й негаранти рована. А лго р итм мето да со пр яжё нны хгр а диенто в . Ш аг0. Задатьпараметрточности ε , вы братьх 0 ∈ R n ,вы чи сли тьf(x0). Ш аг1. Положи тьк =0, p0= - ∇f ( x 0 ) ; Ш аг2. Реш и тьзадачу одномерной ми ни ми зац и и Ф (α )=f(х 0+ α pk) → min , т.е. найти α k. α >0

k+1

k

Ш аг3. П оложи тьх =х + α k pk . П ровери тькри тери й останова: || ∇ f ( x k +1 ) ||< ε . Е сли он вы полнен, то вы чи слени я заверш и ть, полагая x*=xk+1, f*=f(xk+1) . Ш аг4. П ровери тьуслови ек +1=n . Е сли оно вы полняется, то положи ть x0=xk+1, f(x0)=f(xk+1) и перейти кш агу 1 (обновлени еметода). Ш аг5. В ы чи сли тькоэффи ц и ент β k = || ∇f ( x k +1 ) || 2 || ∇f ( x k ) || 2 и найти новоенаправлени епои скаpk+1= - ∇f ( x k +1 ) + β k pk . Положи тьк =к +1 и перейти кш агу 2. Замечани е 1. О пи санны й метод является методом первого порядка, поэтому для реш ени я задачи одномерной ми ни ми зац и и наш аге2 ц елесообразно и спользовать, напри мер, метод хорд, вы би рая в качествеи нтервалапои скаα отрезок[0,1].

43

Замечани е 2. О бновлени еметода, какправи ло, прои зводи тся и для квадрати чны х функц и й, таккакреш ени езадачодномерной ми ни ми зац и и зачастую сопровождается вы чи сли тельны ми погреш ностями . П р имер . Н айти методом сопряжённы х гради ентов точку ми ни мума функц и и f ( x) = 4 x12 + 3 x 22 − 4 x1 x 2 + x1 , начав пои сксточки x 0 = (0,0) . Р е ше ние . ∇f (x) =(8x1-4x2+1;6x2-4x1). И т е рация1. 0. Задади м ε =0,01, x0=(0,0), ∇f ( x 0 ) = (1,0), || ∇f ( x 0 ) ||=1. 1. П оложи м к =0, p0= - ∇f ( x 0 ) =(-1,0). 2. Реш и м задачу одномерной ми ни ми зац и и по α : Φ (−α ,0) = 4α 2 − α → min . α 0=1/8. 3. Н айдем х 1=х 0+ α 0 p0=(-1/8,0), ∇f ( x 1 ) = (0,1/2), || ∇f ( x 1 ) ||= 1/2 > ε . 4. k + 1 ≠ n 5. β 0 = || ∇f ( x 1 ) || 2 || ∇f ( x 0 ) || 2 =1/4. p1= - ∇f ( x 1 ) + β 0 p0=(-1/4,-1/2). И т е рация2. 2. Реш и м задачу одномерной ми ни ми зац и и по α : Φ(−1/8 − α 4 , − α 2 ) = 4(1/8 + α 4 ) + 3 (α 2 ) 2 − 4(1/8 + α 4 ) α 2 − − 1/8 − α 4 → min. α 1=1/4. 3. Н айдем х 2=х 1+ α 1 p1 = (-3/16,-1/8). ∇f ( x 2 ) = (0,0) - получено опти мальное реш ени е, x*=x2 Реш ени еполучено в результатедвух и терац и й, поскольку ц елевая функц и я квадрати чная и одномерны езадачи опти ми зац и и реш ены точно. М ето д Ньюто на Е сли в результатепреобразовани я x=zQ матри ц аквадрати чной формы при води тся к еди ни чной (т. е. QT HQ = E ), то метод наи скорейш его спуска z1=z0- α * ∇f ( z 0 ) , получаетреш ени езаоди н ш аг. В пространствепеременны х х данны й переход запи ш ется в ви де и ли х 1 =х 0- α * ∇f ( x 0 ) Q Q −1 . х 1 Q −1 =х 0 Q −1 - α * ∇f ( x 0 ) Q Т аккак Q Q −1 =H-1 , то х 1 =х 0- α * ∇f ( x 0 ) H-1. И терати вны й метод ви да х k+1 =х k- α k ∇f ( x k ) H-1 носи тназвани еметодаН ью тона. Д ля квадрати чной функц и и с положи тельно определенной матри ц ей Гессе при менени е метода Н ью тона с ш агом α = 1 обеспечи вает получени е точки глобального ми ни мумаровно заодну и терац и ю , незави си мо отвы бора начальной точки . Д ля вы пуклой неквадрати чной функц и и при менени е этого метода обеспечи вает, как прави ло, бы струю сходи мость. О днако если точка

44

х 0 вы брана недостаточно бли зко к опти мальному реш ени ю , то k последовательностьх можетрасходи ться (каки в одномерном случае). Сущ ественны м недостатком метода Н ью тона является необходи мость вы чи слени я и обращ ени я матри ц ы Гессенакаждой и терац и и . А лго р итм мето да Ньюто на . Ш аг0. Задатьпараметрточности ε , вы братьх 0 ∈ R n ,вы чи сли тьf(x0). Ш аг1. Н айти ∇f ( x 0 ) и провери тькри тери й останова: || ∇f ( x 0 ) ||<ε . Е сли он вы полнен, то вы чи слени я заверш и ть, полагая x*=x0, f*=f(x0) . Ш аг2. П оложи тьх 0=х 0- ∇f ( x 0 ) H-1, вы чи сли тьf(x0) и перейти кш агу 1. П р имер . Н айти методом Н ью тонаточку ми ни мумафункц и и f ( x) = 4 x12 + 3 x 22 − 4 x1 x 2 + x1 , начав пои сксточки x 0 = (0,0 ) . Р е ше ние . П осчи таем вектор-гради ентфункц и и ∇f (x) =(8x1-4x2+1;6x2-4x1) .  8 − 4  . М атри ц авторы х частны х прои зводны х и меетви д H=  − 4 6  1  6 4  . 32  4 8  0. В ы берем ε =0.001, x 0 = (0,0 ) , f(x0)=0. Н айдем обратную матри ц у H-1=

1. П осчи таем ∇f ( x 0 ) =(1,0), || ∇f ( x 0 ) ||=1>ε . 1 (6 ,4 ) = ( − 3 16 ,− 1 8 ) , f(x0)= − 3 32 2. П оложи м х 0=х 0- ∇f ( x 0 ) H-1= − 32

3. ∇f ( x 0 ) =(0,0) -найдено опти мальноереш ени е x*= ( − 3 16 ,− 1 8 ) . Ц елевая функц и я квадрати чная, поэтому реш ени езадачи получено заодну и терац и ю . З а да чи для са мо сто ятельно го р еш ения 1. Н айти разли чны ми методами точку ми ни мумаследую щ и х функц и й: 1) f ( x ) = x12 + 2 x 22 − 4 x1 + 2 x 2 , 2) f ( x ) = 2 x12 + x 22 − 12 x1 ,

x 0 = (5,3)

3) f ( x) = x12 + x 22 − 2 x1 − 4 x 2 , 4 ) f ( x ) = x12 + x22 − 4 x1 − 2 x2 ,

7 ) f ( x ) = x12 + 3 x 22 − 2 x1 x 2 ,

x 0 = (5,10 ) x 0 = ( 4 ,5 )

5) f ( x) = x12 + 4 x22 − 6 x1 − 32 x2 , 6 ) f ( x) = 2 x12 + x22 − x1 x2 ,

x 0 = (1,0 )

x 0 = (0,0 )

x 0 = (1,2) x 0 = (2,0 )

45

2. Показать, что для квадрати чной α* = 1.

функц и и в методеН ью тонаш аг

§ 6. Ч исленны е мето ды по иска усло в но го экстр емума В §2 бы ли рассмотрены необходи мы еи достаточны еуслови я реш ени я задачнели нейной условной опти ми зац и и ви да f ( x) → min g j ( x ) ≤ 0, j = 1, m; g j ( x) = 0, j = m + 1, m + p . И спользовани е данны х услови й при води т к необходи мости реш ени я сложны х си стем равенств и неравенств. А нали ти чески реш и ть получаемы е си стемы возможно только для ограни ченного чи сла при меров. Д ля реш ени я больш и нства практи чески х задач и спользую тся чи сленны е методы . Ч и сленны еметоды можно условно раздели тьнатри группы . 1. М е т оды воз мож ных направле ний. Э то методы непосредственного реш ени я задачи условной опти ми зац и и , основанны е на дви жени и и з одной допусти мой x k точки к другой допусти мой точке x k +1 с"лучш и м" значени ем ц елевой функц и и . Д ви жени еосущ ествляется по прави лу x k +1 = x k + α k y k . В качестве вектораy k

вы би рается возможное и подходящ ее направлени е

пои ска в точке x k , а ш аг α k вы би рается, напри мер, путем опти ми зац и и ц елевой функц и и в данном направлени и по α k . К данны м методам, напри мер, относятся: ме т оды прое к ции градие нт а и ме т оды воз мож ных направле ний. 2. М е т оды лине ариз ации. Д анны е методы основаны на сведени и задач нели нейной условной опти ми зац и и к задачам ли нейной условной опти ми зац и и на уровне и сходной постановки с дальнейш и м анали зом полученны х результатов и корректи ровкой реш аемой ли нейной задачи . 3. М е т оды пос ледоват е льной бе з ус ловной минимиз ации. В основе данны х методов лежи т преобразовани е задачи условной опти ми зац и и в последовательность задач безусловной опти ми зац и и путем введени я в рассмотрени е вспомогательны х ц елевы х функц и й. И сходная задача аппрокси ми руется некоторой последовательностью вспомогательны х задач безусловной ми ни ми зац и и , для которы х разработаны эффекти вны е и надежны е методы реш ени я. П оследовательность вспомогательны х задач подби рается, как прави ло, таки м образом, чтобы реш ени е и сходной задачи оказы валось пределом последовательности получаемы х реш ени й вспомогательны х задач. Ч асто, для получени я реш ени я и сходной задачи с требуемой точностью достаточно бы вает реш и ть относи тельно небольш ое чи сло вспомогательны х задач. В спомогательны е задачи можно реш ать при бли женны ми методами и и нформац и ю , полученную в результате

46

реш ени я очередной вспомогательной задачи можно эффекти вно и спользовать для реш ени я следую щ ей. К данны м методам относятся: ме т од шт рафов, ме т од барье ров, ме т од множ ит е лей Лагранж а. М ето ды в о змо жны х на пр а в лений М етоды , входящ и е в эту группу методов, бази рую тся на построени и возможны х и подходящ и х направлени й, по которы м осущ ествляется дви жени и и з одной допусти мой x k точки к другой допусти мой точке x k +1 с "лучш и м" значени ем ц елевой функц и и . Д ви жени е осущ ествляется по прави лу x k +1 = x k + α k y k . О пред ел ение 1. П усть x допусти мая точка в задаче вы пуклого программи ровани я f ( x) → min (1) g j ( x) = 0, j = 1, m, m < n; g j ( x ) ≤ 0, j = m + 1, m + p , где f (x) - ди фференц и руемая функц и я. Н енулевой вектор y назы вается возможны м направлени ем в точке x , если сущ ествуеттакое δ > 0 , что точки x + αy являю тся допусти мы ми в задаче для всех α ∈ [0, δ ] . В ектор y назы вается подходящ и м направлени ем в точке x , если вы полняется T неравенство ∇f ( x ) y < 0 . З амечани е. Е сли некоторое направлени е y является возможны м и подходящ и м в точке x , то сущ ествует такое δ > 0 , что точки x + αy являю тся допусти мы ми в задаче и f ( x + αy ) < f ( x) для всех α ∈ [0, δ ] (Д оказать!). Т ео р ема 1. Д ля того, чтобы допусти мая точка x бы ла реш ени ем задачи вы пуклого программи ровани я необходи мо и достаточно, чтобы в этой точке несущ ествовало одновременно возможны х и подходящ и х направлени й. Рассмотри м вначале частны й случай задачи (1) - задачу с ли нейны ми ограни чени ями f ( x) → min Ax ≤ b Cx = d где A матри ц а размера (m × n) , C - матри ц а размера ( p × n) , b -вектор размера m , d - векторразмера p . Замети м, что, в частности , можетбы тьзадачатолько сограни чени ями равенствами и ли только ограни чени ями неравенствами . У тв ер ждение 1. П усть x допусти мая точка в задаче с ли нейны ми ограни чени ями и предположи м, что A1 - это подматри ц а матри ц ы A , отвечаю щ ая акти вны м ограни чени ям в точке x . Т огда ненулевой вектор y является возможны м направлени ем в точке x в том и только в том случае, если A1 y ≤ 0, Cy = 0 .

47

Замети м, что если в задаче отсутствую т ограни чени я-равенства и в рассматри ваемой точке x нет акти вны х ограни чени й (т.е. точка x является внутренней), то в качестве подходящ его направлени я можно взять y = −∇f (x) . В проти вном случае построени е подходящ и х направлени й можно осущ естви ть в ви де ми ни ми зац и и функц и и ∇f ( x) T y при услови ях A1 y ≤ 0, Cy = 0 . О днако если сущ ествует такой вектор y , такой, что ∇f ( x ) y T < 0 , A1 y ≤ 0, Cy = 0 , то ми ни мальное значени е функц и и ∇f ( x) y T

при такой ми ни ми зац и и не сущ ествует ( inf ∇f ( x ) y T → −∞ ), так как лю бой вектор λy , где λ - сколь угодно больш ое чи сло, также удовлетворяет услови ям A1 λy ≤ 0, Cλy = 0 . Т аки м образом, в задачу ми ни ми зац и и должно бы ть вклю чено услови е, которое ограни чи вало бы вектор y, напри мер, услови е y i ≤ 1, i = 1, n . И так, возможноеи подходящ еенаправлени еи щ ется в ви де реш ени я следую щ ей задачи ли нейного программи ровани я ∇f ( x) y T → min A1 y ≤ 0, Cy = 0 − 1 ≤ y i ≤ 1 , i = 1, n . А лго р итм Ш аг 1. Задать начальную точку x 0 , характери сти ку точности алгори тма ε > 0 . П оложи ть k = 0 . Ш аг 2. Н айти ∇f ( x k ) . Е сли ∇f ( x k ) ≤ ε , то вы чи слени я прекрати ть и положи ть x * = x k , и начеперейти кш агу 3. Ш аг 3. П одстави ть x k в неравенства и определи ть множество и ндексов акти вны х ограни чени й I ( x k ) . Ш аг4. Е сли I ( x k ) = ∅ и в задаченетограни чени й равенств, то положи ть y k = −∇f ( x k ) , и наче определи ть y k и з реш ени я задачи программи ровани я ∇f ( x k )( y k ) T → min

ли нейного

A1 y k ≤ 0, Cy k = 0 − 1 ≤ y ik ≤ 1 ,

i = 1, n .

Ш аг 5. Е сли ∇f ( x k )( y k ) T = 0 , то задачареш енаточно и x * = x k . И наче для найденного вектора y k определи ть αk =

arg min f ( x k + α y k ) . α: x k +α y k ∈Ω

Ш аг6. Н айти очередноепри бли жени е x k +1 = x k + α k y k . П р имер 1. Реш и тьрассмотренны м методом следую щ ую задачу f ( x, y ) = ( x1 − 4 ) 2 + ( x 2 − 2) 2 → min

48

x1 + x 2 ≤ 3, x 2 + 2 x 2 ≤ 4,

x1 , x 2 ≥ 0 .

Реш ени е.  1 17  1. В озьмем в качестве начальной точки x 0 =  ,  . Л егко провери ть, что  2 12  данная точка при надлежи т допусти мому множеству. П оложи м ε = 0,01 , k = 0 . И зобрази м графи чески допусти мое множество и ли ни и уровня ц елевой функц и и 3

x2

. .

.

1

x0

1

0

(4,2)

x

.

1

x2

.

2

3

x1

7  2. Н айдем ∇f ( x 0 ) =  − 7 ,−  . Т аккак ∇f ( x k ) > ε , то перейдем кш агу 3. 6  3. В се ограни чени я вы полняю тся в точке x 0 как строги е неравенства, т.е. x 0 - внутренняя точка допусти мого множества. Поэтому I ( x 0 ) = ∅ .  7 П олагаем y 0 = −∇f ( x 0 ) = 7 ,  .  6 4. О пределяя α 0 и з соотнош ени я 2

5.

2

7  7 7   α 0 = arg min  7α −  +  α −  получи м α 0 = 1 . 2 6 12  14 13   α ≤ Н айдем  98 α :  1 17  1  7   3  x 1 =  ,  + 7 ,  =  1,  . α ≤ 1  2 12  14  6   2   4 6 Н айдем ∇f ( x 1 ) = (− 6 ,−1) . Т ак как ∇f ( x k ) > ε , то

перейдем кш агу 3.

49 1

7. Т очка x при надлежи т грани ц е допусти мого множества, второе ограни чени е задачи является акти вны м для этой точки , поэтому I ( x 1 ) = {2} . 8. Состави м вспомогательную задачу для определени я вектора y 1 : − 6 y 11 − 1 y 21 → min y 11 + 2 y 21 ≤ 0 − 1 ≤ y 11 ≤ 1 − 1 ≤ y 21 ≤ 1 . Реш ая графи чески (си мплексны м методом) данную задачу  2 1 программи ровани я, найдем y 1 =  ,−  . 3 3 9. О пределяя α 1 и з соотнош ени я 2

ли нейного

2

1 2   1 α 1 = arg min  α − 3  +  − α −  , 2   3 3 3  α ≤  2 α : α ≤ 9  2 3 получи м α 1 = . 2  3 3  2 1 10. Н айдем x 2 =  1,  +  ,−  = (2,1) .  2 2 3 3 П родолжая данны й проц есс в качестве точки x 3 , получи м точку 5 1 x 3 =  ,  . В ектор y 3 = (0,0 ) , поэтому x * = x 3 . 2 2 М етод возможны х направлени й и спользуется также для реш ени я задач нели нейного программи ровани я более общ его ви да.

М ето дв о змо жны х на пр а в ленийЗ о йтендейка Рассмотри м задачу вы пуклого программи ровани я ви да f ( x) → min g j ( x ) ≤ 0, j = 1, m , где f ( x ) и g j ( x ) - вы пуклы еди фференц и руемы ефункц и и . В данном случае допусти мое множество вы пукло, поэтому в лю бой допусти мой точке сущ ествует возможное направлени е y . Д ля того, чтобы в данной задаче направлени е y бы ло возможны м и подходящ и м в точке x , достаточно, чтобы оно удовлетворяло си стеменеравенств (1) ∇f ( x ) y T < 0

50

∇g j ( x) y < 0 , T

j ∈ I (x) ,

где I (x) - множество акти вны х в точке x ограни чени й. В озможное и подходящ ее направлени е, удовлетворяю щ ее данной си стеме неравенств, определяется и з реш ени я задачи ли нейного программи ровани я z → min ∇f ( x ) y T ≤ z , ∇g j ( x) y T ≤ z, j ∈ I ( x ),

− 1 ≤ y i ≤ 1, i = 1, n . Замети м, что ( y, z ) = (0,0 ) удовлетворяет всем ограни чени ям задачи , следовательно, ожи даемы й результат z * ≤ 0 . Е сли z * < 0 , то си стема (1) и меет реш ени е y . В этом случае строи тся новая точка x + αy . П ри этом α вы би рается таки м образом, чтобы x + αy бы ла допусти мой точкой, напри мер, α k = min (β 0 , β 1 ,..., β m ) где β 0

вы би рается

из

услови я

f ( x k + β 0 y k ) = min f ( x k + βy k ) , β >0

а

β j , j = 1, m - макси мально возможное перемещ ени е и з точки

x вдоль направлени я y с учетом i -го ограни чени я, которое найдено и з услови я g j ( x + β i y) = 0 . Е сли z * = 0 , то си стема(1) несовместна, т.е. всевозможны ев точке x направлени я не являю тся подходящ и ми . Э то означает, что в точках h допусти мого множества, достаточно бли зки х к x , вы полняется неравенство f (h) ≥ f ( x) , т.е. x -точка локального ми ни мума f (x) на допусти мом множестве . Н о для вы пуклой функц и и f (x) на вы пуклом множестве этот ми ни мум является и глобальны м. Т аки м образом, точка x есть реш ени е задачи . А лго р итм Ш аг 1. Задать начальную точку x 0 , характери сти ку точности алгори тма ε > 0 . П оложи ть k = 0 . Ш аг 2. Н айти ∇f ( x k ) . Е сли ∇f ( x k ) ≤ ε , то вы чи слени я прекрати ть и положи ть x * = x k , и начеперейти кш агу 3. Ш аг 3. Подстави ть x k в неравенства и определи ть множество и ндексов акти вны х ограни чени й I ( x k ) . Ш аг 4. Е сли I ( x k ) = ∅ , то положи ть y k = −∇f ( x k ) , и наче определи ть y k и з реш ени я задачи

z k → min

51

∇f ( x )( y ) ≤ z k , k

k T

( )

∇g j ( x k )( y k ) T ≤ z k , j ∈ I x k , − 1 ≤ y ik ≤ 1, i = 1, n .

Ш аг 5. Е сли y k = 0 и ли z k ≤ ε , то положи ть x * = x k . И наче

для

найденного вектора y k определи ть α k = min (β 0 , β 1 ,..., β m ) , где β 0

вы би рается

из

услови я

f ( x k + β 0 y k ) = min f ( x k + βy k ) , β >0

а

β j , j = 1, m - макси мально возможное перемещ ени е и з точки

x вдоль направлени я y с учетом i -го ограни чени я, которое найдено и з услови я g j ( x + β i y) = 0 . Ш аг6. Н айти очередноепри бли жени е x k +1 = x k + α k y k . П р имер 2. Н айти ми ни мум в задаче ( x1 − 4 )2 + ( x 2 − 5 )2 → min x1 + x 2 − 1 ≤ 0 x 1 ≥ 0, x 2 ≥ 0 . Реш ени е. 1. В озьмем в качестве начальной точки x 0 = (0;0,95 ) . Л егко провери ть, что данная точка при надлежи т допусти мому множеству, при чем I ( x 0 ) = {2} . П оложи м ε = 0,03 , k = 0 .

2. Н айдем ∇f ( x 0 ) = (− 8;8,1) . Т ак как ∇f ( x k ) > ε , то продолжи м реш ени е задачи . Д ля нахождени я y 0 вы чи сли м ∇g 2 ( x 0 ) = (− 1;0 ) и состави м задачу ли нейного программи ровани я z 0 → min − 8 y 10 − 8,1 y 20 ≤ z 0 − y 10 ≤ z 0 − 1 ≤ y 10 ≤ 1 , − 1 ≤ y 20 ≤ 1 .

3. Реш ая полученную

задачу си мплексны м методом, получи м y 10 = 1 ,

y 20 = 1 , z 0 = 0 .

М ето д линеа р иза ции (Ф р а нка В улфа ) Рассмотри м задачу ми ни ми зац и и вы пуклой нели нейной функц и и на множестве, задаваемом ли нейны ми ограни чени ями : f ( x) → min Ax ≤ b  Ω x≥0 

52

М етод ли неари зац и и основан назаменев окрестности точки xk нели нейной функц и и f (x) ли нейной функц и ей c k x T . И з формулы Т ейлора следует, что f ( x) ≈ f ( x k ) + ∇f ( x k )( x − x k ) T . П оложи м c k x T = ∇f ( x k ) x T . Рассмотри м задачу ли нейного программи ровани я c k x T → min Ω

О бозначи м z − реш ени е к - той ЗЛ П . Т огданаправлени е l k = z k − x k в k

и сходной задачебудетподходящ и м. Ф ормулапересчетаи меетви д x k +1 = x k + α k l k , гдеш аг α k и щ ется по прави лу наи скорейш его спускас учетом услови я 0 ≤ α k ≤ 1 ( при таком вы бореα k точка x k +1 будетвы пуклой ли нейной комби нац и ей точек z k и x k , что обеспечи ваетеедопусти мость). В качествекри тери ев остановаалгори тмапри меняю тся стандартны е кри тери и : || ∇f ( x k +1 ) ||< ε , || x k +1 − x k ||< ε . А лго р итм Ш аг0. Зафи кси ровать x 0 ∈ Ω − начальноепри бли жени е. Положи тьк =0. Ш аг1. Реш и тьзадачу ли нейного программи ровани я c k x T = ∇f ( x k ) x T → min , Ω

k

найти z . Ш аг2. Зафи кси роватьвекторl k = z k − x k в качественаправлени я пои ска. Ш аг3. В ы чи сли тьα k = arg min f ( x k + α l k ) . 0≤α ≤1 k +1 Ш аг4. П оложи ть x = xk + α k l k Ш аг5. П ровери тьуслови я остановаи , если они вы полнены , вы чи слени я прекрати тьи взятьточку x k +1 в качествеи скомого реш ени я. И наче положи тьk=k+1 и перейти наш аг1. П риме р 1. Реш и тьметодом ли неари зац и и задачу нели нейного программи ровани я f ( x, y ) = ( x − 4) 2 + ( y − 2) 2 → min, x + y ≤ 3, (1) x + 2 y ≤ 4, (2) x, y ≥ 0 Р е ше ние . Д анная задачабы лаграфи чески реш енав §2: x*=(5/2,1/2). Д ля реш ени я задачи методом ли неари зац и и вы берем x0 ∈ Ω , напри мер, x0=(0,0). В ы чи сли м

∇f ( x) = ( 2 x − 8, 2 y − 4) Ω

.

.

x0

x*

.

x1

53

И т е рация1. ∇f ( x 0 ) = (−8, − 4 ) . Рассмотри м задачу ли нейного программи ровани я ∇f ( x 0 ) x T = −8 x1 − 4 x2 → min Реш и в ееграфи чески , получаем

Ω

0 x min = (3,0 ), l 0 = (3,0 ) , x 1 = (3α 0 , 0 ), гдеα 0 = arg min f (3α ,0) . 0≤α ≤1 Запи ш ем задачу одномерной опти ми зац и и (3α − 4) 2 → min

0 ≤α ≤1 0 Реш ени ем этой задачи будетα 0 = 1, тогда x 1 = x min = (3,0 ) И т е рация2 ∇f ( x 1 ) = ( −2, − 4 ) . Рассмотри м задачу ∇f ( x 1 ) x T = −2 x1 − 4 x 2 → min Ω

Реш ени ем этой ЗЛ П является отрезок, соеди няю щ и й точки (2,1) и (0,2). 1 В ы берем одну и з ни х, напри мер, x min = (2,1). Т огда l 0 = (2,1) − (3,0) = (−1,1) , x 2 = (3 − α 1 , α 1 ) . Запи ш ем задачу одномерной опти ми зац и и

( −α − 1) 2 + (α − 2) 2 → min 0 ≤α ≤1 Реш ени ем этой задачи будетα 0 = 1 / 2 , тогда x 2 = ( 5 / 2,1 / 2 ) И т е рация3. 2 ∇f ( x ) = ( −3, − 3) . Рассмотри м задачу ∇f ( x 2 ) x T = −3 x1 − 3 x 2 → min Ω

Реш ени ем этой ЗЛ П является отрезок, соеди няю щ и й точки (2,1) и (3,0). 2 В ы берем одну и з ни х, напри мер, x min = (3,0). Т огда l 2 = (3,0) − (5 / 2,1 / 2) = (1 / 2,−1 / 2) . α

α

x 2 = ( 52 + 22 , 12 − 22 ) . Запи ш ем задачу одномерной опти ми зац и и ( α2 − 32 ) 2 + ( α2 + 32 ) 2 → min 0 ≤α ≤1 Реш ени ем этой задачи будетα 2 = 0, тогда x 3 = x 2 = (5 / 2,1 / 2) . О станов. П олучено опти мальноереш ени ех*= (5 / 2,1 / 2) .

М ето д секущ их пло ско стей Д анны й метод при меняется для реш ени я программи ровани я сли нейной ц елевой функц и ей :

задач вы пуклого

54

cx → max T

(1)

Ω : f i ( x) ≤ bi , i = 1, m З амечани е 1 . Л ю бая задача вы пуклого программи ровани я может бы ть запи санав ви де(1). Д ействи тельно, если естьзадачаснели нейной ц елевой функц и ей ϕ ( x) → max f i ( x) ≤ bi , i = 1, m, то онаможетбы тьперепи санаследую щ и м образом µ → max µ − ϕ ( x) ≤ 0 f i ( x) ≤ bi , i = 1, m М етод секущ и х плоскостей основан на при бли жени и всех нели нейны х функц и й f i (x) ли нейны ми с и спользовани ем разложени я по формуле Т ейлора. f i ( x) ≈ f i ( x 0 ) + ∇f i ( x 0 )( x − x 0 ) T Рассмотри м задачу cx T → max (2) Ω1 : f i ( x 0 ) + ∇f i ( x 0 )( x − x 0 ) T ≤ bi , i = 1, m Е сли множество Ω1 ограни чено, то задача(2) всегдаразреш и ма(в проти вном случаеможетоказаться, что

sup

cx T = +∞ , дажеесли задача(1)

Ω1

разреш и ма) Т аккакфункц и и f i (x ) вы пуклы вни з, справедли во неравенство f i ( x) ≤ f i ( x 0 ) + ∇f i ( x 0 )( x − x 0 ) T ≤ bi . Следовательно Ω ⊆ Ω1 . П усть x 1 реш ени езадачи (2). 1 1) Е сли точка x допусти мав задаче(1), то онаявляется опти мальны м реш ени ем этой задачи (поскольку это экстремум той жец елевой функц и и наболееш и роком множестве). 2) Е сли x1 ∉ Ω , то в задаче(2) добавляю тся новы ели нейны еограни чени я: f i ( x 1 ) + ∇f i ( x 1 )( x − x 1 ) T ≤ bi , i : { f i ( x 1 ) > bi } .Э ти ограни чени я обладаю т следую щ и ми свойствами : a) точка x 1 неудовлетворяетэти м ограни чени ям; b) во всех точках множества Ω они вы полняю тся. Т аки м образом, получаем новоемножество Ω 2 , такоечто Ω ⊆ Ω 2 ⊆ Ω1 . Д алееи терац и онны й проц ессповторяется. Д оказано, что генери руемая таки м образом последовательность{ x k } реш ени й ЗЛ П сходи тся копти мальной точкеи сходной задачи . А лгори тм методаи меетследую щ и й ви д.

55

А лго р итм мето да секущ их пло с-

ко стей

Ш аг 1. Задать x 0 (не обязательно допусти мое), ε (точность попадани я в допусти мую область). Ш аг2.П оложи ть k = 1, Ω1 = {x : f i ( x 0 ) + ∇f i ( x 0 )( x − x 0 ) T ≤ bi , i = 1, m} Ш аг3. Н айти x k - реш ени езадачи ли нейного программи ровани я cx T → max x ∈Ωk Ш аг4. Е сли ∀i : f i ( x k ) − bi ≤ ε , то останов x* = x k Ш аг5. П оложи ть Ω k +1 = Ω k ∩ {x : f i ( x k ) + ∇f i ( x k )( x − x k ) T ≤ bi , i : f i ( x k ) > bi } ; k=k+1 . П ерейти кш агу 3. П р имер 1. Реш и тьметодом секущ и х плоскостей задачу ϕ ( x) = x1 + x2 → max f1 ( x) = −2 x1 + x22 ≤ −1 f 2 ( x) = 0.8 x12 + 2 x2 ≤ 9 x1 , x2 ≥ 0 Р е ше ние . В ы берем x 0 = (5,4) . В ы чи сли м ∇f 1 ( x) = (−2; 2 x 2 ) , ∇f 2 ( x) = (1.6 x1 ; 2) . Т огда f1 ( x ) ≈ 6 + (−2;8)( x1 − 5; x 2 − 4) T = −2 x1 + 8 x 2 − 16 f 2 ( x ) ≈ 28 + ( 8 ; 2 )( x 1 − 5 ; x 2 − 4 ) T = 8 x 1 + 2 x 2 − 20 Реш и м графи чески задачу ли нейного программи ровани я x1 + x2 → max

∇ϕ

• x2 • • x*

x1

− 2 x1 + 8 x2 ≤ 15  Ω1 8 x1 + 2 x2 ≤ 29  x1 , x2 ≥ 0 Е ереш ени ем является точка x 1 = ( 2.97;2.62) . О днако в этой точке наруш аю тся первоеи второе ограни чени е, при чем вели чи на невязокдостаточно вели ка, поэтому строи м отсекаю щ и еплоскости : 0.92 + ( −2; 5.24)( x1 − 2.97; x 2 − 2.62) T ≤ 15

12.3 + (4.75; 2)( x1 − 2.97; x 2 − 2.62) T ≤ 9 Д обавляем эти ограни чени я кзадачели нейного программи ровани я и находи м следую щ еереш ени е x 2 = ( 2.52; 2.05) , котороеужеявляется

56

хорош и м при бли жени ем копти мальной точке. Х отя в этой точкепопрежнему обаограни чени я наруш ены , вели чи наневязокнепревосходи т0.1, поэтому положи м x* = x 2 . П р имер 2. Реш и тьметодом секущ и х плоскостей задачу ϕ ( x) = x1 − x2 → max f1 ( x ) = x12 + x22 ≤ 9

Р е ше ние . В ы берем x 0 = (2,3) . В ы чи сли м ∇f1 ( x ) = ( 2 x1; 2 x2 ) . Т огда f1 ( x) ≈ 13 + (4;6)( x1 − 2; x2 − 3)T = 4 x1 + 6 x2 − 13

Реш и м графи чески задачу ли нейного программи ровани я x1 − x2 → max Ω1 : 4 x1 + 6 x2 ≤ 22 И з графи кави дно, что в направлени и вектора-гради ентац елевой функц и и допусти моемножество неограни чено, supϕ ( x) = +∞ , т.е. ЗЛ П реш ени я неи меет. Ω1

О днако и сходная задачаразреш и ма, 3 3 x* = ( ,− ) .Э тотпри мер 2 2 и ллю стри руетсущ ественностьтребовани я ограни ченности множества Ω1 .

М ето д гла дких ш тр а фо в Д анны й метод относи тся к методам последовательной безусловной ми ни ми зац и и . Рассмотри м задачу f ( x) → min g j ( x ) ≤ 0, j = 1, m; g j ( x) = 0, j = m + 1, m + p . Реш ени езадачи своди тся креш ени ю последовательности задачпои ска безусловного ми ни мумавспомогательной функц и и F ( x , r k ) = f ( x ) + P ( x , r k ) → min , где P ( x , r k ) - ш трафная функц и я, r k - параметр ш трафа, задаваемы й на каждой k -й и терац и и . Н а ш трафную функц и ю наклады ваю тся следую щ и е ограни чени я 0, 1) P ( x, r k ) =  > 0,

при выполне нии ограниче ний, при не выполне нии ограниче ний

57

2) при невы полнени и ограни чени й и

r k → ∞ , k → ∞ должно вы полняться

услови е P( x , r k ) → ∞ . В качествеш трафны х функц и й и спользую тся, напри мер, функц и и ви да m r k  m+ p  2 + P( x , r ) = g ( x ) g +j ( x ) 2  , ∑ ∑ j  2  j = m +1 j =1  + g j ( x ) = max 0, g j ( x ) . Д анная функц и я удовлетворяет k

где

{

}

всем

требовани ям, предъ являемы м к ш трафны м функц и ям, и является ди фференц и руемой. Ч то позволяет при безусловной опти ми зац и и и спользоватьгради ентны епроц едуры . А лго р итм Ш аг 1. Задать начальную точку x 0 , начальное значени е параметра ш трафа r 0 , чи сло C > 1 для увели чени я параметра, характери сти каточности алгори тма ε > 0 . Ш аг2. Положи ть k = 0 . Ш аг3. Состави тьвспомогательную функц и ю F ( x , r k ) . Ш аг 4. И спользуя заданны е на ш аге 1 параметры данного алгори тма, реш и ть задачу безусловной ми ни ми зац и и F ( x , r k ) → min одни м и з чи сленны х методов безусловной ми ни ми зац и и . Ш аг 5. В ы чи сли ть значени е функц и и P x * ( r k ), r k в полученной на

(

ш аге 4 точке ми ни мума x * ( r k ) . Ш аг 6. Е сли

(

)

)

P x * (r k ), r k ≤ ε , то проц есс пои ска закончи ть и

положи ть x * = x * ( r k ),

f ( x * ) = f ( x * ( r k )) . В проти вном случае положи ть

r k +1 = Cr k , x k +1 = x * ( r k ), k = k + 1 и перейти кш агу 3.

В данном методе, как прави ло, вы би раю т r 0 = 0; 0,01; 0,1; 1, а C ∈[ 4;10] . При этом не рекомендуется пы таться реш и ть одну вспомогательную задачу, беря сразу очень больш ое значени е параметра ш трафа r 0 , поскольку при больш ом значени и данного параметра вспомогательная функц и я при обретает явно вы раженную овражную структуру. П оследовательность x * ( r k ), k = 0,1,... , генери руемая данны м методом невсегдасходи тся к реш ени ю x * . Д ля частны х случаев, напри мер, когда x * - локальное еди нственное реш ени е и функц и и f ( x ) и g j ( x ) непреры вно ди фференц и руемы в окрестности точки x * , последовательность x * ( r k ), k = 0,1,... сходи тся к x * . С ростом параметра r k генери руемы е алгори тмом точки при бли жаю тся к x * и звне множества допусти мы х реш ени й. П ри реш ени и задачпроц едурарасчетов заверш ается при некотором

58

конечном значени и параметра ш трафа r k . П олученное при этом при бли женное реш ени е, как прави ло, не лежи т в множестве допусти мы х точек. П р имер 1. Н айти ми ни мум в задаче x 2 − 4 x → min x − 1≤ 0 Реш ени е. Запи ш ем в общ ем ви де (при прои звольном r k ) вспомогательную задачу для данной задачи сограни чени ями неравенствами rk [max{0, ( x − 1)}}]2 . F ( x, r k ) = x 2 − 4 x + 2 Н айдем в общ ем ви де ми ни мум функц и и F ( x, r k ) с помощ ью необходи мы х и достаточны х услови й:  dF ( x, r k ) = 2 x − 4 = 0, x −1≤ 0   dx .  k dF ( x , r )  = 2 x − 4 + r k ( x − 1) = 0, x − 1 > 0  dx 4 + rk * k О тсю да x (r ) = , при чем x * (r k ) − 1 > 0 при r k ≥ 0 . П олученная k 2+r точка удовлетворяет достаточному услови ю ми ни мума, так как 2 * k k d F x (r ), r = 2 + rk > 0. 2 dx П о полученной формуле проведем чи сленны е расчеты при k r = 1; 2; 10; 100; 1000; ∞

(

)

k 0 1 2 3 4 5

rk 1 2 10 100 1000 ∞ x* x * (2) x * (1) 1 2

x * (r k ) 5/3 3/2 7/6 52/51 502/501 1

(

F x * ( r k ), r k -3,66 -3,5 -3,166 -3,019 -3,002 -3

)

59

4 + rk = 1 = x* . Е сли бы в этой задаче положи ть П ри r → ∞ и меем lim k k r →∞ 2 + r ε = 0,01 , то алгори тм закончи т свою работу при r k = 1000 , так как k

(

)

P x * (r k ), r k ≤ ε . В качестве реш ени я будет при нята недопусти мая точка x * (1000 ) = 1,00199 . П р имер 2. Н айти ми ни мум в задаче x12 + x 22 → min − x1 + 1 = 0 x1 + x 2 − 2 ≤ 0 Реш ени е. В данной задаче одно ограни чени е равенство и одно ограни чени е неравенство, т.е. m = 1, p = 1 . Состави м вспомогательную функц и ю : rk [x1 − 1]2 + [max{0, ( x1 + x 2 − 2)}]2 . F ( x, r k ) = x12 + x 22 + 2 С помощ ью необходи мы х и достаточны х услови й найдем безусловны й ми ни мум F ( x, r k ) . В ы пи ш ем необходи мы е услови я безусловного экстремума: 2 x1 + r k ( x1 − 1) + r k ( x1 + x 2 − 2), x1 + x 2 − 2 > 0 ∂F ( x, r k ) =0 = , ∂x1 2 x1 + r k ( x1 − 1), x1 + x 2 − 2 ≤ 0 2 x 2 + r k ( x1 + x 2 − 2), ∂F ( x, r k ) x1 + x 2 − 2 > 0 =0 = . ∂x 2 2 x , x + x − 2 ≤ 0  2 1 2

[

]

П ри x1 + x 2 − 2 > 0 получи м x1* (r k

)=

(r k ) 2 + 6 r k (r k ) 2 + 6 r k + 4

О днако при всех r ≥ 0 и меем k

x 2* ( r k )

,

x1* (r k

)+

=

x 2* (r k

(r k ) 2 + 4r k (r k ) 2 + 6 r k + 4

)−2=

.

− 2r k − 8

(r k ) 2 + 6 r k + 4 проти воречи туслови ю x1 + x 2 − 2 > 0 для рассматри ваемого случая.

П ри x1 + x 2 − 2 ≤ 0 получи м x1* ( r k ) = по этом формулам чи сленны ерасчеты .

rk 2+r

k

< 0, что

, x 2* ( r k ) = 0 . Проведем

60

П ри

k

k

r

0 1 2 3 4 5

1 2 10 100 1000 ∞ r →∞ k

и меем

x1* (r k

0 0 0 0 0 0 x1* (r k

)=

(

x 2* ( r k )

F x * ( r k ), r k

5/9 3/4 35/36 2600/2601 251000/251001 1

-2/3 -1 -5/3 -100/51 -1000/501 -2

)

rk

)

= 1, x 2* (r k ) = 0 ,

т.е. 2+r последовательность точек, генери руемы х данны м алгори тмом, сходи тся к реш ени ю задачи . lim k

r →∞

k

З а да чи для са мо сто ятельно го р еш ения 1. М етодом секущ и х плоскостей реш и ть следую щ и езадачи : 1) x1 − x 2 → min x1 + x 2 ≤ 2 x12 + x 22 − 4 ≤ 0 2 ) x1 + x 2 → max x12 + x 22 ≤ 9 x1 , x 2 ≥ 0 2 . М етодом ш трафны х функц и й реш и ть следую щ и езадачи :

1) x1 − 2 x 22 + 4 x 2 → max − 3 x1 − 2 x 2 = 6 ;

3) ( x1 + 4 ) 2 + (x 2 − 4 ) 2 → extr 2 x1 − x 2 ≤ 2

2) − 4 x12 − 8 x1 + x 2 + 3 → max − x1 − x 2 = 2 ; 4) ln x1 − x 2 → min 1 − x1 ≤ 0

x 1 ≥ 0, x 2 ≥ 0 ; x12 + x 22 − 4 = 0 . 3.М етодами возможны х и подходящ и х направлени й реш и ть следую щ и е задачи : 1) 3 x12 + 4 x1 x 2 + 5 x 22 → min 2) ( x1 − 4 )2 + ( x 2 − 2 ) 2 → min x1 + x 2 ≥ 4 x1 + 2 x 2 ≤ 4 x 1 ≥ 0, x 2 ≥ 0 ; x1 + x 2 ≥ 3 x1 ≥ 0, x 2 ≥ 0 ; 3) − x1 − x 2 → min x12 + x 22 ≤ 25 . 4. Реш и тьметодом ли неари зац и и :

61

1)

x12

− 2 x1 + 3 x 2 → min

2) x1 + 2 x 2 + x 22 → min

4 x1 + 5 x 2 ≤ 80,

4 x1 + 5 x 2 + x3 = 80,

2 x1 + x 2 ≤ 34,

2 x1 + x 2 + x 4 = 34,

x1 , x 2 ≥ 0

xi ≥ 0, ∀i

§ 7. З а да ча кв а др а тично го пр о гр а ммир о в а ния Задачей квадрати чного программи ровани я назы вается задача вы пуклого программи ровани я ми ни ми зац и и квадрати чной функц и и на допусти мом множестве Ω , заданном ли нейны ми ограни чени ями x T Qx + bx T + c → min , x∈Ω, где Q = ( q ij ) - си мметри чная положи тельно определенная матри ц а размера n × n , b - фи кси рованны й векторразмера n , c - заданноечи сло. В данном параграфе рассмотри м задачу квадрати чного программи ровани я ви да n 1 n n f ( x ) = ∑ ∑ q ij x j + ∑ b j x j + c → min 2 i=1 j=1 j=1 n

g i ( x) = ∑ α ij x j − βi ≤ 0, i = 1, m j =1

Д ля данной задачи функц и ю Л агранжа ви да

− x j ≤ 0, j = 1, n . условной опти ми зац и и m

n

i =1

j =1

можно рассмотреть

L ( x , λ, µ ) = f ( x ) + ∑ λ i g i ( x ) + ∑ µ j ( − x j ) = n m 1 n n  n  n ∑ ∑ q ij x j + ∑ b j x j + c + ∑ λi  ∑ α ij x j − β i  + ∑ µ j ( − x j ) . 2 i =1 j =1 j =1 i =1  j =1  j =1 П ри этом услови я К уна - Т аккера запи ш утся в ви де следую щ ей си стемы равенств и неравенств: n n ∂L = ∑ q ij x i + b j + ∑ λ i α ij − µ j = 0, j = 1, n ∂x j i =1 i =1

=

n ∂L = ∑ α ij x j − β i ≤ 0, i = 1, m ∂λ i j =1 ∂L = − x j ≤ 0, j = 1, n ∂µ j

62

  λ i g i = λ i  ∑ α ij x j − βi  = 0, i = 1, m  j =1  − µ j x j = 0, n

j = 1, n

λ i ≥ 0, i = 1, m, µ j ≥ 0, j = 1, n . П о теореме К уна - Т аккера реш ени е этой си стемы является и скомой точкой ми ни мума функц и и f (x) на множестве Ω . В ведя дополни тельны е переменны е xn + i , i = 1, m , полученную си стему перепи ш ем в ви де си стемы равенств n

n

i =1

i =1

∑ q ij x j + ∑ λ i α ij − µ j = −b j ,

j = 1, n

n

∑ α ij x j + xn + i = βi , i = 1, m

j =1

x j ≥ 0,

j = 1, n + m

(1)

λ i xn + i = 0 i = 1, m, µ j x j = 0, j = 1, n λ i ≥ 0, i = 1, m , µ j ≥ 0, j = 1, n Реш ени е ( x1 , x2 ,..., xn + m , λ1 ,..., λ m , µ1 ,..., µ n ) данной си стемы n + m ли нейны х уравнени й содержи т, по крайней мере n + m нулевы х коорди нат. Задачу нахождени я реш ени я си стемы без услови й λ i xn + i = 0 i = 1, m, и µ j x j = 0, j = 1, n можно свести к нахождени ю допусти мой бази сной точки методом и скусственного бази са в спец и ально построенной задаче ли нейного программи ровани я z 1 + z 2 + ... + z n + z n +1 + ... + z n + m → min n

n

i =1

i =1

∑ q ij x j + ∑ λ i α ij − µ j + z j = − b j ,

j = 1, n

n

∑ α ij x j + x n + i + z n + i = β i , i = 1, m j=1

x j ≥ 0, z j ≥ 0

j = 1, n + m

λ i ≥ 0, i = 1, m, µ j ≥ 0, j = 1, n . П ри реали зац и и методаи скусственного бази саследуетучи ты ватьуслови я λ i xn + i = 0 i = 1, m, µ j x j = 0, j = 1, n ,

т.е. не вклю чать в бази сны е переменны е одновременно λ i и xn + i с одни м и тем женомером i и переменны е µ j и x j соди наковы м номером j . П р имер 1. Реш и тьзадачу квадрати чного программи ровани я: x12 − 2 x1 x 2 + 2 x 22 − 2 x1 − 6 x 2 → min

63

x1 + x 2 ≤ 2

− x1 + 2 x 2 ≤ 2 x1 ≥ 0, x 2 ≥ 0 . Реш ени е. Ц елевая функц и я данной задачи является квадрати чной с  1 − 1  . Т ак как определи тели главны х ми норов данной матри ц ей A =  −1 2  матри ц ы ∆ 1 = 1, ∆ 2 = 1 положи тельны , то данная матри ц а является положи тельно определенной, а ц елевая функц и я вы пуклой. Следовательно, данная задача является задачей вы пуклого программи ровани я и для ее реш ени я можно при мени ть опи санны й вы ш е метод реш ени я. Си стема равенств (1) запи ш ется для рассматри ваемой задачи в ви де 2 x1 − 2 x 2 + λ 1 − λ 2 − µ1 = 2 − 2 x1 + 4 x 2 + λ 1 + 2λ 2 − µ 2 = 6 x1 + x 2 + x 3 = 2 − x1 + 2 x 2 + x 4 = 2 x1 , x 2 , x 3 , x 4 , λ 1 , λ 2 , µ1 , µ 2 ≥ 0 µ1 x1 = µ 2 x 2 = λ 1 x3 = λ 2 x 4 = 0 . Н айдем допусти мое бази сное реш ени е этой си стемы , путем реш ени я вспомогательной задачи ли нейного программи ровани я с и скусственны ми переменны ми − x 5 − x 6 → max 2 x1 − 2 x 2 + λ 1 − λ 2 − µ1 + x 5 = 2 − 2 x1 + 4 x 2 + λ 1 + 2λ 2 − µ 2 + x 6 = 6

x1 + x 2 + x3 = 2 − x1 + 2 x 2 + x 4 = 2 x1 , x 2 , x3 , x 4 , λ 1 , λ 2 , µ1 , µ 2 ≥ 0 , взяв в качестве первоначального бази сного множества J = {5,6,3,4} . П ри ведем последовательностьси мплексны х табли ц . cB

J

xB

x1

x2

x3

x4

λ1

λ2

µ1

µ2

-1 -1 0 0

5 6 3 4

-1 -1 0 0

5 6 3 2

2 6 2 2 -8 4 2 1 1

2 -2 1 -1 0 1 0 3/2 -1/2

-2 4 1 2 -2 0 0 0 1

0 0 1 0 0 0 0 1 0

0 0 0 1 0 1 -2 -1/2 1/2

1 1 0 0 -2 1 1 0 0

-1 2 0 0 -1 -1 2 0 0

-1 0 0 0 1 -1 0 0 0

0 -1 0 0 1 0 1 0 0

64

-1 -1 0 0

5 6 1 2

-1 0 0 0

5 λ1 1 2

0 0 0 0

4 λ1 1 2

-6 10/3 2 2/3 4/3 -16/3 4/3 2 2/3 4/3 -4/3 4/10 28/10 4/5 6/5 0

-1 0 0 1 0 0 0 0 1 0 0

0 0 0 0 1 0 0 0 0 1 0

0 -2/3 0 2/3 1/3 2/3 -2/3 0 2/3 1/3 2/3

1 4/3 -2 -1/3 1/3 2/3 10/3 -2 -1/3 1/3 -10/3

-2 1 1 0 0 -2 0 1 0 0 0

-1 -1 2 0 0 -1 -3 2 0 0 3

1 -1 0 0 0 1 -1 0 0 0 1

1 0 -1 0 0 1 1 -1 0 0 -1

0

0

0

0

0

0

0

0

В последней си мплексной табли ц е мы получи ли допусти мое бази сное реш ени е ( x1 , x 2 , x3 , x 4 , λ1 , λ 2 , µ1 , µ 2 ) =  4 , 6 ,0, 2 , 14 ,0,0,0  . 5 5 5 5  П оэтому и скомое реш ени е задачи квадрати чного программи ровани я и меет 36 4 6 ви д x * =  ,  со значени ем ц елевой функц и и f * = f ( x * ) = . 5 5 5 З а да чи для са мо сто ятельно го р еш ения 1. Реш и тьзадачи квадрати чного программи ровани я: 2 2 x1 + x 2 ≤ 2 1) ( x1 − 4 ) + ( x 2 − 2 ) → min x1 ≥ 0, x 2 ≥ 0 x1 + x 2 ≤ 3 x1 + 2 x 2 ≤ 4 3) 20 x1 − x 22 → max x1 ≥ 0, x 2 ≥ 0 x1 − x 2 ≥ 0 − x1 + 2 x 2 ≤ 2 2) 2 x1 + 3x 2 − 2 x 22 → max x1 ≥ 0, x 2 ≥ 0 x1 + 4 x 2 ≤ 4

§ 8. К ла ссическо е в а р иа цио нно е исчисление П р о стейш а я за да ча в а р иа цио нно го исчисления 1

П усть C [t 0 , t 1 ] - пространство непреры вно ди фференц и руемы х на отрезке [t 0 , t 1 ] функц и й снормой

63

|| x (t ) ||1 = max max{| x (t ) |, | x& (t ) |} . t0 ≤t ≤t1

Раздел опти ми зац и и , связанны й с нахождени ем наи больш и х и наи меньш и х 1

значени й функц и оналов, определенны х на C [t 0 , t 1 ] , назы вается вари ац и онны м и счи слени ем. В отли чи е от рассмотренны х ранее экстремальны х задач, определенны х в конечномерном пространстве R n , задача вари ац и онного и счи слени я стави тся в бесконечномерном пространствефункц и й. О пред ел ение 1. П ростейш ей задачей класси ческого вари ац и онного 1 и счи слени я назы вается следую щ ая экстремальная задачав C [t 0 , t 1 ] : t1

J ( x(⋅)) = ∫ F (t , x (t ), x& (t ))dt → extr t0

(1)

x(t 0 ) = x0 , x(t 1 ) = x1 , где F(t ,x, x& ) - непреры вная функц и я трёх переменны х, ди фференц и руемая по двум свои м последни м аргументам. Э кстремум в задаче и щ ется среди 1 функц и й x(t ) ∈ C [t 0 , t 1 ] , удовлетворяю щ и х краевы м услови ям x(t 0 ) = x0 , x(t 1 ) = x1 . Т аки ефункц и и назы ваю тся допусти мы ми . О пред ел ение 2. Д опусти мая функц и я xˆ⋅ ( ) назы вается слабы м локальны м ми ни мумом (макси мумом) задачи (1), если сущ ествует δ > 0 такое, что для лю бой другой допусти мой функц и и x(⋅) , для которой || x(⋅) − xˆ(⋅) || 1 < δ , вы полняется неравенство J ( x(⋅)) ≥ J ( xˆ(⋅)) ( J ( x(⋅)) ≤ J ( xˆ(⋅)) ) . Замечани е 1. И наче говоря, простейш ая задачавари ац и онного и счи слени я состои тв оты скани и слабого экстремумафункц и оналави да(1) намножестве всех гладки х кри вы х, соеди няю щ и х двезаданны еточки . Н аряду со слабы м экстремумом в класси ческом вари ац и онном и счи слени и тради ц и онно рассматри вается си льны й экстремум. П ри этом расш и ряется класс функц и й, среди которы х и щ ется реш ени е задачи . В ведем в 1 рассмотрени е пространство кусочно-непреры вны х функц и й KC [t 0 , t 1 ] с нормой || x (t ) ||0 = max | x(t ) | . t0 ≤t ≤t1

1 О пред ел ение 3. Ф ункц и я xˆ⋅ ( ) ∈ KC [t 0 , t 1 ] , удовлетворяю щ ая краевы м услови ям x(t 0 ) = x0 , , x(t 1 ) = x1 , назы вается си льны м локальны м ми ни мумом (макси мумом) задачи (1), если сущ ествует δ > 0 такое, что для лю бой другой допусти мой функц и и x(⋅) , для которой || x(⋅) − xˆ(⋅) || 0 < δ , вы полняется неравенство J ( x(⋅)) ≥ J ( xˆ(⋅)) ( J ( x(⋅)) ≤ J ( xˆ(⋅)) ) . Замечани е 2. П оми мо поняти й си льного и слабого локального экстремума стандартны м образом вводи тся поняти е глобального экстремума задачи (1), то есть функц и и , доставляю щ ей ми ни мальное (и ли макси мальное) значени е функц и оналу J ( x(⋅)) среди всех допусти мы х функц и й.

64

Т ео р ема . (Н е обх одимое ус ловие эк с т ре мума). Е сли функц и я xˆ⋅ ( ) доставляетслабы й локальны й экстремум в задаче(1), то ∂F для этой функц и и ∈ C 1 [t 0 , t 1 ] и вы полнено уравнени еЭ йлера: ∂x& d ∂F ∂F (2) = dt ∂x& ∂x Замечани е 3. Е сли xˆ⋅ ( ) доставляет си льны й локальны й экстремум в задаче(1), то и з определени я следует, что онадоставляети слабы й. Поэтому необходи мое услови е слабого экстремума является также необходи мы м услови ем си льного экстремума. О пред ел ение 4. Реш ени я уравнени я Э йлера, являю щ и еся допусти мы ми функц и ями , назы ваю тся допусти мы ми экстремалями задачи (1). А лго р итм р еш ения пр о стейш ейза да чи в а р иа цио нно го исчисления 1. Запи сатьнеобходи моеуслови еэкстремума– уравнени еЭ йлера: d ∂F ∂F = dt ∂x& ∂x 2. Н айти общ еереш ени еуравнени я Э йлера x (t , C 1 , C 2 ) . 3. Н айти допусти мы е экстремали , т.е. реш ени я уравнени я Э йлера, удовлетворяю щ и езаданны м краевы м услови ям x(t 0 ) = x0 , x(t 1 ) = x1 . 4. Д оказать, что реш ени ем является однаи з допусти мы х экстремалей, и ли показать, что реш ени я нет. 1

J ( x& (⋅)) = ∫ x& 2 dt → inf; x (0 ) = 0, x (1) = 1.

П р имер 1.

0

d 2 x& = 0; и ли 2 &x& = 0. dt 2. О бщ ее реш ени е: x = C 1t + C 2 . 3. x (0 ) = C 2 = 0; x(1) = C 1 = 1. Т аки м образом, и меется еди нственная допусти мая экстремаль xˆ(t ) = t . 4. П окажем, что эта экстремаль доставляет глобальны й ми ни мум в данной задаче. Д ействи тельно, возьмем прои звольную допусти мую в этой задаче функц и ю x(t ) . В таком случае 1. У равнени еЭ йлера:

x(t ) ∈ C 1 [0,1], x(0 ) = 0, x(1) = 1. О бозначи м h(t ) = x(t ) − xˆ(t ). Т огда h(0) = h(1) = 0 . 1

1

1

1

0

0

0

0

J ( x(⋅)) = J ( xˆ(⋅) + h(⋅)) = ∫ (1 + h&) 2 dt = ∫ dt + 2 ∫ h&dt + + ∫ h& 2 dt = 1

= J ( xˆ(⋅)) + ∫ h& 2 dt ≥ J ( xˆ(⋅)) Следовательно, функц и я xˆ(t ) = t 0

глобальны м ми ни мумом.

является

65

Замечани е 4. А налоги чны м образом можно сформули ровать алгори тм реш ени я простейш ей векторной задачи класси ческого вари ац и онного и счи слени я. П усть в задаче (1) x(⋅) = ( x1 (⋅),...x n (⋅)) , F = F (t , x1 ,.., x n , x& 1 ,.., x& n ) - функц и я 2n + 1 переменны х. Н еобходи мы е услови я в простейш ей векторной задаче состоят и з си стемы уравнени й d ∂F ∂F Э йлера = , i = 1, n . dt ∂x& i ∂xi Ч а стны е случа и ур а в нения Э йлер а Е сли функц и я F(t ,x, x& ) не зави си т явно от одной и з свои х переменны х, то уравнени еЭ йлерадопускаетпони жени епорядка, то естьсводи тся кболее простому уравнени ю . I. Е сли функц и я F(t ,x, x& ) незави си тявно отx, то уравнени еЭ йлерасводи тся к уравнени ю : ∂F = const (3) ∂x& 1

П р имер 2.

J ( x& (⋅)) = ∫ t 2 x& 2 dt → inf; x(0) = 0, x(1) = 1. 0

П оды нтегральная функц и я не зави си т явно от x, поэтому уравнени е Э йлера и меетви д: 2t 2 x& = C . C 1. О бщ ее реш ени е: x = 1 + C 2 . t 2. Э кстремали , удовлетворяю щ ей краевому услови ю x(0) = 0 , несущ ествует 3. Д анная задачанеи меетреш ени я. II. Е сли функц и я F(t ,x, x& ) не зави си т явно от t, то уравнени е Э йлера можно перепи сатьв ви де ∂F x& − F (t , x, x& ) = const (4) ∂x& П р имер 3.

J ( x& (⋅)) =

3π / 2

∫ ( x&

2

− x 2 ) dt → inf; x(0) = 0, x( 32π ) = 0.

0

1. П оды нтегральная функц и я не зави си т явно от t, поэтому уравнени е Э йлераможно запи сатьв ви де: x& ⋅ 2 x& − x& 2 + x 2 = C , и ли x& 2 = C − x 2 . 2. О бщ ее реш ени е: x = C 1 sin(t + C 2 ) . 3. Е ди нственная допусти мая экстремаль xˆ= 0 . 4. П окажем, что этаэкстремальнедоставляет ми ни мумав данной задаче. Рассмотри м последовательность функц и й x n (t ) = n1 sin 23t . О чеви дно, что x n − допусти мы ефункц и и и x n → xˆ≡ 0 в C 1 [0, 3π 2 ] , но при этом J ( x n (⋅)) =

1 3π n2 4

( 49 − 1) = −

5π 12 n 2

< 0 = J ( xˆ(⋅)) .

И з этого при мера ви дно, что уравнени е Э йлера – необходи мое, но не достаточноеуслови еэкстремума.

66

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

З а да ча Б о льца Задачей Больц а назы вается следую щ ая экстремальная

1 задачабез ограни чени й в C [t 0 , t 1 ]

t1

B( x(⋅)) = ∫ F (t , x(t ), x& (t )) dt + f ( x(t 0 ), x(t 1 ) ) → extr ,

(5)

t0

где f ( x(t0 ), x(t1 ) ) - функц и я, ди фференц и руемая по каждой и з двух свои х переменны х. 1 О пред ел ение 6. Ф ункц и я xˆ(⋅) ∈ C [t 0 , t 1 ] назы вается слабы м локальны м ми ни мумом (макси мумом) задачи (5), если сущ ествует δ > 0 такое, что для 1

лю бой другой функц и и x(⋅) ∈ C [t 0 , t 1 ] для которой || x(⋅) − xˆ(⋅) || 1 < δ , вы полняется неравенство B ( x(⋅)) ≥ B ( xˆ(⋅)) (B ( x(⋅)) ≤ B ( xˆ(⋅)) ) . Т ео р ема . (Н е обх одимые ус ловияэк с т ре мума). Е сли функц и я xˆ⋅ ( ) доставляетслабы й локальны й экстремум в задаче(5), то ∂F для этой функц и и ∈ C 1 [t 0 , t 1 ] и вы полнены : ∂x& d ∂F ∂F a) уравнени еЭ йлера: = ; dt ∂x& ∂x b) услови я трансверсальности : ∂f ∂f ∂F ∂F (6) (t 0 ) = ; (t 1 ) = − . ∂x& ∂x& ∂x(t 0 ) ∂x(t 1 ) О пред ел ение 7. Реш ени я уравнени я Э йлера, удовлетворяю щ и е услови ям трансверсальности , назы ваю тдопусти мы ми экстремалями задачи (5). А лго р итм р еш ения за да чи Б о льца 1. Запи сатьнеобходи мы е услови я экстремума: d ∂F ∂F a) уравнени еЭ йлера: = dt ∂x& ∂x ∂f ∂f ∂F ∂F b) услови я трансверсальности : (t 0 ) = ; (t 1 ) = − . ∂x& ∂x(t 0 ) ∂x& ∂x(t 1 ) 2. Н айти общ еереш ени еуравнени я Э йлера x(t , C 1 , C 2 ) . 3. Среди всех реш ени й уравнени я вы брать те, которы е удовлетворяю т услови ям трансверсальности . 4. Д оказать, что реш ени ем является однаи з допусти мы х экстремалей, и ли показать, что реш ени я нет. 1

П р имер 4.

1) B( x& (⋅)) = ∫ ( x& 2 − x)dt + x 2 (1) → extr . 0

67

1. П оды нтегральная функц и я не зави си т явно от t, поэтому уравнени е Э йлераможно запи сатьв ви де: x& ⋅ 2 x& − x& 2 + x = C , и ли x& 2 + x = C ; . У слови я трансверсальности в данной задачеи мею тви д: 8 x& (0) x 2 (0 ) = 4 x 3 (0)  8 x& (3) x 2 (3) = 8 t2 2. О бщ ее реш ени е: x = − + C 1t + C 2 . 4 3. Е ди нственная экстремаль, удовлетворяю щ ая услови ям 2 t 3 трансверсальности : xˆ(t ) = − + 4 4 4. П окажем, что эта экстремаль доставляет глобальны й ми ни мум в данной задаче. Д ействи тельно, возьмем прои звольную функц и ю h(t ) ∈ C 1 [0,1] и сравни м значени я B ( xˆ(⋅)) и B ( xˆ(⋅) + h(⋅)) 1

1

1

0

0

0

B ( xˆ(⋅) + h(⋅)) − B( xˆ(⋅)) = ∫ (−th&)dt + ∫ h& 2 dt − ∫ hdt + h(1) + h 2 (1) П ри мени в и нтегри ровани епо частям в первом и нтеграле, получаем: 1

1

1

0

0

0

1 B ( xˆ(⋅) + h(⋅)) − B ( xˆ(⋅)) = − th(t ) 0 + ∫ hdt + ∫ h& 2 dt − ∫ hdt + h(1) + h 2 (1) = 1

= ∫ h& 2 dt + h 2 (1) ≥ 0 0

Следовательно, функц и я xˆ(t ) = −

t2 3 является глобальны м ми ни мумом + 4 4

в данной задаче. З а да чи для са мо сто ятельно го р еш ения 1. Н айти допусти мы еэкстремали в простейш и х задачах вари ац и онного и счи слени я : 1

1)

J ( x& (⋅)) = ∫ ( x& 2 + tx) dt → extr ; x(0 ) = 0, x(1) = 0. 0 1

2) J ( x& (⋅)) = ∫ ( − x& 2 + t 2 x )dt → extr; x(0) = 0, x(1) = 0. 3)

J ( x& (⋅)) =

4 ) J ( x& (⋅)) =

0 3/2

∫ ( x&

0 π /4

3

∫ (4 x&

0

+ 2 x) dt → extr ; x (0 ) = 0, x( 32 ) = 1. 2

− x 2 )dt → extr; x(0) = 1, x( π4 ) = 0.

68

5) J ( x& (⋅)) =

π /2

∫ ( x&

2

− x 2 − tx )dt → extr; x(0 ) = 0, x( π2 ) = 0.

0 e

6 ) J ( x& (⋅)) = ∫ (−tx& 2 + x)dt → extr; x(1) = 1, x(e) = 2. 1 3

7)

J ( x& (⋅)) = ∫ x& 2 (t 2 − 1) dt → extr ; x (2) = 0, x (3) = 1. 2 e

8 ) J ( x& (⋅)) = ∫ (tx& 2 + 2 x )dt → extr; x(1) = 1, x(e) = 0. 1

2. Н айти допусти мы еэкстремали в задачах Больц а. 3

1) B ( x& (⋅)) = ∫ 4 x& 2 x 2 dt + x 4 (0) − 8 x(3) → extr. 0 1

2) B ( x& (⋅)) = ∫ x& 2 dt + 4 x 2 (0 ) − 5 x 2 (1) → extr . 0 1

3) B( x& (⋅)) = ∫ ( x& 2 + x 2 ) dt − 2 x(1) sh1 → extr . 0 1

4 ) B ( x& (⋅)) = ∫ ( x& 2 + x 2 )dt − 2 x 2 (1) → extr . 0 1

5) B ( x& (⋅)) = ∫ e t +1 ( x& 2 + 2 x 2 ) dt + 2 x(1)( x(0) + 1) → extr . 0 1

6 ) B( x& (⋅)) = ∫ ( x& 2 + x 2 )dt − 2 x 2 (1) → extr . 0 1

7 ) B ( x& (⋅)) = ∫ e x x& 2 dt + 4 e x (0 ) + 32e − x (1) → extr . 0

§ 9. Реш ение за да ч ма тема тическо го пр о гр а ммир о в а ния ср едств а ми EXCEL В данном параграфепри водятся алгори тмы реш ени я задачли нейного и нели нейного программи ровани я средствами EXCEL. Реш ение за да ч линейно го пр о гр а ммир о в а ния Реш ени е задачи ли нейного программи ровани я в среде EXCEL осущ ествляется в соответстви и со следую щ и м алгори тмом 1. Ввод ус ловийз адачи 1.1. Соз дание формы дляввода ус ловий з адачи. Ф орма для ввода услови й задачи c1 x 1 + c2 x 2 + ... + c n x n → max (min)

69

a11 x 1 + a12 x 2 + ... + a1n x n ≤ ( ≥, = ) b1 a21 x 1 + a22 x 2 + ... + a2 n x n ≤ ( ≥, = ) b2 …. a m1 x 1 + a m 2 x 2 + ... + a mn x n ≤ ( ≥, = ) bm l1 ≤ x 1 ≤ d1 , l 2 ≤ x 2 ≤ d 2 , … , l n ≤ x n ≤ d n и меетследую щ и й ви д им я зна че ние ниж н. гр в е р х . гр

ко эф.в Ц Ф

им я 1 им я 2 … l1 d1

с1

l2 d2

с2

… …

…

ПЕ Р Е М Е Н Н Ы Е им я n ln dn Ф ункция, р е а л изую щ а я cn це ле в ую функцию О ГР А Н И ЧЕ Н И Я

в ид на зв а ние о гр а ниче ния 1 a1 1 на зв а ние о гр а ниче ния 2 a2 1 … … на зв а ние о гр а ниче ния m a3 1

a1 2

…

a1n

a2 2 …

… …

a2n …

a3 2

…

a3n

на п р а в л е ние о п т им иза ции (m ax , m in )

ле в а я ча с т ь зна к Ф ункция,р е а л изую щ а я л е в ую ча с т ь 1-го о гр а ниче ния Ф ункция, р е а л изую щ а я л е в ую ч а с т ь 2-го о гр а ниче ния … … Ф ункция, р е а л изую щ а я л е в ую ч а с т ь m -го о гр а нич е ния

п р а в а я ча с т ь

b1

b2 … .

b3

Ввод ис х одных данных . Заполняю тся ячейки , содержащ и е: ни жни е и верхни е грани ц ы переменны х, коэффи ц и енты ц елевой функц и и , коэффи ц и енты ограни чени й, знаки ограни чени й, направлени е опти ми зац и и ц елевой функц и и . 2. Ввод з авис имос т е й из мат е мат иче с к ой моде ли. Заполняю тся ячейки содержащ и е: функц и ю , реали зую щ ую ц елевую функц и ю задачи , функц и и реали зую щ и елевы ечасти ограни чени й задачи . 2.1. Ввод з авис имос т и дляцеле вой функ ции. 2.1.1. П оме с т ит ь к урс ор в яче йк у, от ве де нную под з наче ние целе вой функ ции. 2.1.2. Выбрат ь к нопк у М аст ер ф у нкций. 2.1.3. Выбрат ь в ок не К ат егория к ат е горию мат емат ические 2.1.4. Выбрат ь функ цию СУ М М ПР О И ЗВ.

70

В

2.1.5. З аполнит ь диалоговое ок но функ ции СУ М М ПР О И ЗВ. масси в 1 нужно занести ди апазон ячеек, содержащ и х значени я

переменны х. В масси в 2 – ди апазон ячеек, содержащ и х коэффи ц и енты ц елевой функц и и . 3.2. Ввод з авис имос т е йдляле вых час т ейограниче ний. 3.2.1. П оме с т ит ь к урс ор в яче йк у, от ве денную под ле вую час т ь ограниче ния. 3.2.2. Выбрат ь к нопк у М ас т е р функ ций. 3.2.3. Выбрат ь в ок не К ат егория к ат е горию мат емат ические. 2.1.6. Выбрат ь функ цию СУ М М ПР О И ЗВ. 2.1.7. З аполнит ь диалоговое ок но для функ ции СУ М М ПР О И ЗВ. Занести в масси в 1 ди апазон ячеек, содержащ и х значени я переменны х (и спользовать при этом абсолю тны е ссы лки ), в масси в 2 – ди апазон ячеек, содержащ и х коэффи ц и енты данного ограни чени я. 2.1.8. Копироват ь с оде рж имое яче йк и в буфе р 2.1.9. Вс т авит ь соде рж имое буфера в яче йк и, от ве де нные под ле вые час т и ос т альных ограниче ний. 4. Ввод ос новных параме т ров моде ли в диалоговом ок не Поиск реш ения. 4.3. Войт и в ме ню Сервис и выбрат ь пунк т Поиск реш ения.

71

4.4. З аполнит ь парамет ры диалогового ок наПоиск реш ения. 4.4.1. В пунк т е У ст ановит ь цел еву ю ук аз ат ь яче йк у, от ве де нную под целе вую функ цию . 4.4.2. В с оот ве т с т вии с ре шае мой з адаче й выбрат ь направле ние целе войфунк ции. 4.4.3. Н аж ат ь к нопк у Добавит ь. П ояви тся ди алоговое окно для построени я ограни чени й задачи .В левой части указы вается ячейка (группа ячеек), в которой содержи тся левая часть ограни чени я, в ц ентре - знак ограни чени я, в правой части - ячейка (группа ячеек) с правой частью ограни чени я. П осле ввода каждого ограни чени я нужно нажи мать на кнопку Д о ба в ить. К огда все ограни чени я задачи построены , нужно нажать на кнопку О тмена и вернуться в ди алоговое окно П о искр еш ения. 4.4.4. Н аж ат ь к нопк у П араме т ры диалогового ок на Поиск реш ения. П ояви тся ди алоговоеокно П а р а метр ы по иска р еш ения.

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

72

назначени я времени в секундах, вы деляемого напои ск реш ени я задачи . В это поле можно ввести значени е, не превы ш аю щ ее 32767 с (более 9 часов). Значени е 100, и спользуемое по умолчани ю , подходи т для реш ени я больш и нства задач. К оманда П р едельно е число итер а ций служи тдля назначени я чи слаи терац и й… 4.4.5. У с т ановит ь флаж ок Линейная мод ел ь. Э то обеспечи т при менени еси мплекс– метода. 4.4.6. Н аж ат ь нак нопк у Выпол нит ь. Н ачнется реш ени есоставленной математи ческой модели задачи . Ч ерез какое-то время появи тся ди алоговоеокно Результа ты по иска р еш ения.

Н ужно вы брать и нтересую щ и е ви ды отчетов по реш ени ю задачи и проанали зи ровать полученное реш ени е. К ажды й и з вы бранны х ти пов отчета создается на отдельном ли сте. Отчет по р езульта та м состои т и з трех табли ц . Т а блица 1 при води тсведени я о ц елевой функц и и . В столбц е И схо дно при ведены значени я ц елевой функц и и до начала вы чи слени й. Т а блица 2 при води т значени я и скомы х переменны х, полученны е в результате реш ени я задачи . Т а блица 3 показы вает результаты опти мального реш ени я для ограни чени й и для грани чны х услови й. Отчет по усто йчив о сти состои ти з двух табли ц . В Т а блице 1 при водятся следую щ и е значени я переменны х: результат реш ени я задачи ; редуц и рованная стои мость, т.е. дополни тельны е двойственны е переменны е, которы е показы ваю т, насколько и змени тся ц елевая функц и я при при нуди тельном вклю чени и еди ни ц ы этой продукц и и в опти мальное реш ени е; коэффи ц и енты ц елевой функц и и ; предельны е значени я при ращ ени я каждого коэффи ц и ента ц елевой функц и и , при которы х сохраняется набор бази сны х переменны х в опти мальном реш ени и . В Т а блице 2 при водятся аналоги чны е значени я для ограни чени й: вели чи на и спользованны х ресурсов; теневая ц ена, т.е. двойственны е оц енки , которы е показы ваю т, как и змени тся ц елевая функц и я при и зменени и ресурсов на еди ни ц у; значени я при ращ ени я каждого ресурса, при которы х сохраняется опти мальны й набор переменны х, входящ и х в опти мальное реш ени е. Отчет по пр едела м показы вает, в каки х пределах может и зменяться вы пуск продукц и и , вош едш ей в опти мальное реш ени е, при сохранени и структуры опти мального реш ени я.

73

В качестве при мера рассмотри м реш ени е следую щ ей задачи прои зводственного плани ровани я П р имер 1. Предпри яти евы пускаеттри ви дапродукц и и : П род1, Прод2, П род3, Прод4. Т ребуется определи ть, в каком коли чественадо вы пускатьэти продукты , чтобы получи ть макси мальную при бы ль. И звестно, что для и зготовлени я данны х продуктов требую тся ресурсы трех ви дов: трудовы е, сы рьевы е, фи нансы . Н ормы расхода (коли чество ресурса каждого ви да, необходи мое для вы пуска еди ни ц ы продукц и и каждого ти па), а также при бы ль, получаемая от реали зац и и еди ни ц ы каждого ти па продукц и и , при ведены в следую щ ей табли ц е. р есур с П р о д1 П р о д2 П р о д3 П р о д4 Т рудовы е 60 70 120 130 Сы рье 1 1 1 1 Ф и нансы 6 5 4 3 П ри бы ль 4 6 10 13 М атемати ческая модельданной задачи и меетви д 60x 1 + 70x 2 + 120x 3 + 130 x 4 → max x1 + x 2 + x 3 + x 4 ≤ 16 6x 1 + 5 x 2 + 4 x 3 + 3x 4 ≤ 110 4 x1 + 6x 2 + 10x 3 + 13x 4 ≤ 100 x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0 1. Сос т авим форму дляданной з адачи лине йного программирования 2. Вве де м з авис имос т и из мат е мат иче с к оймоде ли ПЕР ЕМ ЕННЫ Е им я п р о д1 п р о д2 п р о д3 п р о д4 зна че ние 0 0 0 0 ниж н. гр в е р х. гр ко эф.в Ц Ф 60 70 120 130 =С У М М ПР ОИЗ В (B4:E4;B7:E7) ОГР А НИЧЕНИЯ в ид тр удо в ы е с ы р ье фина нс ы

1 6 4

1 5 6

1 4 10

1 3 13

ле в а =С У М =С У М =С У М

я М М М

м а кс

ча с ть зна к ПР ОИЗ В ($B$4:$E$4;B10:E10) <= ПР ОИЗ В ($B$4:$E$4;B11:E11) <= ПР ОИЗ В ($B$4:$E$4;B12:E12) <=

пра в а я ча с ть 16 110 100

3. Выз ове м диалоговое ок но П оис к ре ше ния. В нем устанавли вается ц елевая ячейка(F7), и зменяемы еячейки (B3:E3), указы вается направлени епои ска (макси ми зац и я) . Д алее вы би рается команда Д о ба в ить и в появи вш емся ди алоговом окне Д о ба в ление о гр а ничения вводятся ограни чени я: F10<=H10, F11<=H11, F12<=H12.

74

У слови я неотри ц ательности переменны х можно ввести в ди алоговом окне П а р а метр ы по иска р еш ения. В окне П а р а метр ы по иска р еш ения устанавли вается такжефлажокЛ инейна я мо дель. 4. З апус т им программу на выполне ние из ок на поис к ре ше ния. Н а экране появи тся ди алоговое окно Результа ты по иска р еш ения. В данном ди алоговом окнесделан вы вод о том, что найдено опти мальноереш ени е.

Результат реш ени я задачи при веден в табли ц е ПЕР ЕМ ЕННЫ Е им я зна че ние ниж н. гр в е р х. гр ко эф.в Ц Ф

п р о д1 п р о д2 п р о д3 п р о д4 10 0 6 0

60

70

120

130

1320 м а кс

ОГР А НИЧЕНИЯ в ид

ле в а я ча с ть

зна к

пра в а я ча с ть

тр удо в ы е с ы р ье

1 6

1 5

1 4

1 3

16 <= 84 <=

16 110

фина нс ы

4

6

10

13

100 <=

100

Д анная табли ц а показы вает, что макси мальная при бы ль (F7=1320) будет дости гнута предпри яти ем при следую щ ем вы пуске продукц и и : прод1=B4=10, прод2=C4=0, прод3=D4=6, прод2=E4=0. В спец и ально

75

отведенны х ячейках табли ц ы отражается коли чество и спользованны х ресурсов: трудовы х=F10=16, сы рья=F11=84, фи нансов=F12=100. оптим альн ы й вы пуск продукции 12 10 8 6 4 2 0

п р о д1

п р о д2

п р о д3

п р о д4

5. П ре дс т авим ре з ульт ат ы ре ше нияз адачи графиче с к и. П рове де м анализ получе нного ре ше ния. А нали з реш ени я осущ ествляется на основани и трех ви дов отчетов, представленны х в окнеРезульта ты по иска р еш ения: результаты , устойчи вость, пределы . Н ачнем сОтчета по р езульта та м. Д анны й отчетнаходи тся наотдельном ли сте. О тчетсостои ти з трех табли ц . Т абли ц а1 при води тсведени я о ц елевой функц и и . В столбц е И схо дно при ведены значени я ц елевой функц и и до началавы чи слени й – 0,ав столбц еРезульта т – значени ец елевой функц и и в опти мальном реш ени и 1320. Т абли ц а2 при води тзначени я и скомы х переменны х, полученны ев результатереш ени я задачи . Т абли ц а3 показы ваетрезультаты опти мального реш ени я для ограни чени й задачи : трудовы е, сы рье, фи нансы . В столбц е Ф о р мула при ведены ограни чени я в том ви де, в котором они бы ли введены в ди алоговом окнеП о искр еш ения, в столбц еЗ на чение при ведены вели чи ны и спользованного ресурса. Microsoft Excel 8.0a Отче т по ре зультатам Р абочий лист: [Лист в F: metod exel_lab1.doc]Лист1 Отче т создан : 03.08.00 15:20:32 Ц е ле в а я яче й ка (М а кс им ум ) Яче йка Имя И сходн о Р е зультат $F$7 ко эф.в Ц Ф B5 0 1320 Изм е няе м ы е яче й ки Яче йка Имя И сходн о Р е зультат $B$4 зна че ние п р о д1 0 10 $C$4 зна че ние п р о д2 0 0 $D$4 зна че ние п р о д3 0 6 $E$4 зна че ние п р о д4 0 0 Огр а ниче ния Яче йка Имя З н аче н ие ф орм ула Статус Р азн ица $F$10 тр удо в ы е B5 16 $F$10<=$H$10 с в яза нно е 0 $F$11 с ы р ье B5 84 $F$11<=$H$11 не с в яза н. 26 $F$12 фина нс ы B5 100 $F$12<=$H$12 с в яза нно е 0

76

Т рудовы е ресурсы и спользованы в коли честве 16, сы рье – 84, фи нансы – 100. В графе Ра зница показано коли чество неи спользованного ресурса. Т рудовы е ресурсы и спользованы полностью , остаток сы рья составляет 26, фи нансы и спользованы полностью . Е сли ресурс и спользуется полностью , то в столбц е С о сто яние указы вается св яза нно е; при неполном и спользовани и ресурсав этом столбц еуказы вается несв яза нно е. В торой ти п отчета– Отчет по усто йчив о сти. Д анны й отчетнаходи тся наотдельном ли стеи состои ти з двух табли ц . В столбц е Результир ующ ее зна чение табли ц ы 1 при води тся опи санны й ранее результат реш ени я задачи . Столбец Но р мир о в а нна я сто имо сть показы вает, что при при нуди тельном вклю чени и еди ни ц ы прод1 в опти мальноереш ени ец елевая функц и я неи змени тся, прод2 – уменьш и тся на 10, прод3 – не и змени тся, прод4 – уменьш и тся на 20. Столбц ы Д о пустимо е ув еличение и Д о пустимо е уменьш ение показы ваю т, что если при бы ль от реали зац и и прод1 будет и зменяться в пределах от 60-40 до 60+12 , то опти мальноереш ени езадачи неи змени тся, аналоги чно для прод2 – от70-10 до 70+(1Е +30), прод3 – от 120-30 до 120+13,33333333, прод4 – 130-20 до 130+(1Е +30). В столбц е Результир ующ ее зна чение табли ц ы 2 при водятся вели чи ны и спользованны х ресурсов. Столбец Т енев а я цена показы вает, что при увели чени и трудовы х ресурсов на еди ни ц у опти мальное значени е ц елевой функц и и увели чи тся на 20, при увели чени и сы рья на еди ни ц у ц елевая функц и я не и змени тся, при увели чени и на еди ни ц у фи нансов опти мальное значени ец елевой функц и и возрастетна10. Microsoft Excel 8.0a Отче т по устойчивости Рабочий лист: [Лист в F: metod exel_lab1.doc]Лист1 Отче т создан : 03.08.00 15:20:33 Изм е няе м ы е яче й ки Ре зульт. Норм ир. Ц е ле вой Д опустим ое Д опустим ое Яче йка Им я зн аче н ие стоим ость коэф ф ицие н т уве личе н ие ум е н ьш е н ие $B$4 зна че ние п р о д1 10 0 60 40 12 $C$4 зна че ние п р о д2 0 -10 70 10 1E+30 $D$4 зна че ние п р о д3 6 0 120 30 13,33333333 $E$4 зна че ние п р о д4 0 -20 130 20 1E+30 Огр а ниче ния Яче йка Им я $F$10 тр удо в ы е B5 $F$11 с ы р ье B5 $F$12 фина нс ы B5

Ре зульт. Те н е вая Огран иче н ие Д опустим ое Д опустим ое зн аче н ие це н а правая часть уве личе н ие ум е н ьш е н ие 16 20 16 3,545454545 6 84 0 110 1E+30 26 100 10 100 60 36

Т еневая ц ена позволяет определи ть макси мальную ц ену, по которой стои т покупать дополни тельны е еди ни ц ы ресурсов. Столбц ы Д о пустимо е ув еличение и Д о пустимо е уменьш ение показы ваю т, что и зменени е трудовы х ресурсов в пределах от 16-3,545454 до 16+6 не при води т к и зменени ю опти мального набора вы пускаемы х продуктов, аналоги чно для сы рья – от110-(1Е +30) до 110+26, для фи нансов – от100-60 до 100+36.

77

Т рети й ти п отчета – Отчет по пр едела м. Д анны й отчет состои т и з одной табли ц ы . Це ле в о е Яче й ка Им я зна че ние $F$7 ко эф.в ЦФ 1320 Изм е няе м о е Нижний Це ле в о й В е р хний Це ле в о й Яче й ка Им я зна че ние п р е де л р е зульт а т п р е де л р е зульт а т $B$4 зна че ние 10 0 720 10 1320 п р о д1 $C$4 зна че ние 0 0 1320 0 1320 п р о д2 $D$4 зна че ние 6 0 600 6 1320 п р о д3 $E$4 зна че ние 0 0 1320 0 1320 п р о д4

В табли ц еуказаны ни жни еи верхни епределы , в которы х можети зменяться вы пускпродукц и и , вош едш ей в опти мальноереш ени е. Реш ение за да ч нелинейно го пр о гр а ммир о в а ния ср едств а ми Excel Задачи нели нейной опти ми зац и и могут реш аться разны ми методами . Д ля задачбезусловной опти ми зац и и f ( x ) → extrn x∈R

в Excel реали зовано 2 метода: метод Н ью тона и метод сопряженны х гради ентов Ф летчера-Ри вса. В ы бор метода осущ ествляется в окне П араметры пои ска реш ени я. В качестве кри тери я останова в Excel k +1 f ( x ) − f ( xk ) и спользуется услови е ∆f k = ≤ ε . Значени е ε вводи тся в f ( xk ) окнеП а р а метр ы по иска р еш ения в строкеОтно сительна я по гр еш но сть.

78

Д ля реш ени я задачусловной опти ми зац и и f ( x) → extr g i ( x) ≤ bi , i = 1, m; x j ≥ 0, j = 1, n, в Excel и спользуется метод множи телей Л агранжа, позволяю щ и й реш ени е задачи условной опти ми зац и и свести креш ени ю задачи безусловной опти ми зац и и . Работареали зованного в Excel методамножи телей Л агранжа прои сходи тпо следую щ ей схеме. 1. В сеограни чени я –неравенствапреобразую тся в ограни чени я- равенства. Т аки м образом, задачапри ни маетви д f ( x ) → extr v i ( x ) = 0 , i = 1, m ; 2. Полученная задачаперепи сы вается спомощ ью функц и и Л агранжа m

L( x, y ) = f ( x) + ∑ y i vi ( x) → max min , i =1

x

y

где y i - двойственны епеременны е(множи тели Л агранжа). 3. Рассматри вается си стемауравнени й, ли нейная относи тельно y i : ∂L( x, y ) = 0, j = 1, n ∂x j Н аходи тся реш ени е этой си стемы - вектор y 0 , где коорди наты вы ражены через x j :

y i0

yi0 = yi0 ( x) .

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

79 m

f ( x) + ∑ y i0 ( x)v i ( x) → max x

i =1

5. Е ереш ени е x * берется в качествереш ени я и сходной задачи . Реш ени е задачи нели нейного программи ровани я рассмотри м на следую щ ем при мере. П усть требуется определи ть размеры бака a,b,h, стои мость которого не должна превы ш ать Cзад так, чтобы его объ ем V бы л макси мальны м.

h

b a О бъ ем бака V=abh П олная поверхность S=2(ab)+2(a+b)h=2(ab+(a+b)h) П ри ни маем, что стои мостьматери ала C=kS, гдеk-стои мостьеди ни ц ы площ ади матери ала. В результатеполучи м C=2k(ab+(a+b)h) П осле введени я рассмотренны х вели чи н сформули руем задачу опти ми зац и и следую щ и м образом: V = abh → max 2k (ab + (a + b)h ) ≤ C зад a , b, h ≥ 0 Д ля реш ени я задачи при ни маем следую щ и езначени я: k= 10 руб/м2, Сзад=100 руб. Т огдаматемати ческая модельпри метви д: V = abh → max 20(ab + (a + b) h ) ≤ 100 a , b, h ≥ 0 Реш и м данную задачу си спользовани ем средств EXCEL. Реш ени е задачи нели нейного программи ровани я отли чается от реш ени я задачи ли нейного программи ровани я следую щ и м: • назначаю тся начальны езначени я и скомы х переменны х xj0 • в окне П а р а метр ы по иска р еш ения не надо вводи ть Л инейна я мо дель. Н ачальны езначени я xj0 желательно назначать бли зки ми к ожи даемы м опти мальны м значени ям, что ускори т реш ени е задачи . О бязательны м является требовани е к ц елевой функц и и , которая в начальной точке должна бы тьнеравнанулю (и начевозможно делени енанольпри вы чи слени и ∆fk ). Н еобходи мо сделатьформу для вводауслови й задачи , в которую далее вводятся

80

• зави си мости для объ емаи стои мости (ячейки С8, С9); • начальны е значени я xj0 (ячейки В 3, С3, D3). В данном случае в качественачальны х значени й вы би раю тся еди ни чны е; • значени еправой части ограни чени я (ячейкаE9). В ячейках, в которы х будет представлен результат (B3:D3), перед реш ени ем задачи надо назначи ть чи сло знаков после запятой. В наш ем при мереназначаем в ячейках 2 знакапослезапятой. П Е Р Е М Е ННЫ Е b

a зна че ния ниж н. гр

1

h 1

З А В И СИ М О СТ И о бо зна че ние в е личина зна к о бъ е м = B 3^C3^D3 м а кс V с т о им о с т ь C = 20^(B 3^C3+ (B 3+ C3)^D3) < =

1

п р а в а я ча с т ь 100

Д алее вы зы вается программа П о иск р еш ения и в появи вш емся ди алоговом окне вводи тся ячейка для ц елевой функц и и (С8), направлени е пои ска(макси ми зац и я), и зменяемы еячейки (B3:D3). Затем вы би рается пункт Д о ба в ить и в появи вш емся окне Д о ба в ление о гр а ничений вводятся ограни чени я B3>=B4; C3>=C4; D3>=D4, C9<=E9. После ввода всех ограни чени й в окне пои ска реш ени я вы би рается команда П а р а метр ы и осущ ествляется переход в ди алоговое окно П а р а метр ы по иска р еш ения. В нем назначаю тся параметры пои ска реш ени я. В ы берем в качестве метода реш ени я безусловны х задач метод сопряженны х гради ентов, параметры точности можно остави тьбез и зменени я . П осле ввода всех и сходны х данны х и параметров прои зводи тся реш ени е задачи . Результаты

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

81

аналоги чны таки м жеотчетам для задачли нейного программи ровани я. О тчет Изм е няе м ы е яче й ки Р е зультат Яче йка И м я зн аче н ие $B$4 зна че ния а 1.29 $C$4 зна че ния b 1.29 $D$4 зна че ния h 1.29 Огр а ниче ния Р е зульт. Яче йка И м я зн аче н ие $C$10 С в е личина 100.00

Норм ир. градие н т 0.00 0.00 0.00 Лагран ж а М н ож ите ль 0.03

по устойчи вости состои ти з двух табли ц . В первой табли ц епри водятся значени я для переменны х: • результатреш ени я задачи • норми рованны й гради ент - вели чи на, при води мая при вы боре некоторы х методов в ди алоговом окнеП араметры пои скареш ени я. В о второй табли ц епри водятся значени я для ограни чени й: • вели чи настои мости • множи тельЛ агранжа, показы ваю щ и й, каки змени тся ц елевая функц и я при и зменени и правой части в ограни чени и наеди ни ц у. Д ля задач ли нейного программи ровани я можно прои звести также параметри чески й анали з, реш ая и х при разли чны х значени ях параметров. А лгори тм вы полнени я параметри чески х расчетов аналоги чен схеме, рассмотренной при реш ени и задачли нейного программи ровани я, поэтому в данном разделе разби раться не будет. В табли ц е при веден и тоговы й сц енари й, построенны й в результате реш ени я рассматри ваемой задачи нели нейного программи ровани я при разли чны х значени ях стои мости : 100, 200, 300, 400, 500. ИТОГОВ Ы Й СЦ Е НА РИЙ Те кущ ие зна че ния с =100 с =200 с =300 с =400 Изме н яе мы е яче йки $B$4 2.89 1.29 1.83 2.24 2.58 $C$4 2.89 1.29 1.83 2.24 2.58 $D$4 2.89 1.29 1.83 2.24 2.58 Яче йки ре зультата $C$9 24.06 2.15 6.09 11.18 17.21 $C$10 500.00 100.00 200.00 300.00 400.00 Пр име ча ние : в с то лбце Те кущ ие зна че ния п р ив е де ны да нные в изме няе мых яче й ка х на мо ме нт с о зда ния о тче та Ито го в ый с це на р ий .

с =500 2.89 2.89 2.89 24.06 500.00

ЗА Д А Н И Я Д Л Я Л А БО РА Т О РН О ГО П РА К Т И К У М А Л абораторны й практи кум ори енти рован на форми ровани е практи чески х навы ков построени я математи чески х моделей для разли чны х

82

классов задачопти мального вы бора и реш ени я и х с и спользовани ем средств EXCEL. Н и же при водятся задачи , для которы х необходи мо состави ть математи ческую модель, реш и ть средствами EXCEL и проанали зи ровать полученны ерезультаты . 1. И з пункта А в пункт В ежедневно отправляю тся пассажи рски е и скоры е поезда. В следую щ ей табли ц е указаны нали чны й парк вагонов разны х ти пов, и з которы х ежедневно можно комплектоватьданны епоезда, и коли чество пассажи ров, вмещ аю щ и хся в каждом и з вагонов: П о езда Скоры й П ассажи рски й Ч и сло пассажи ров П арквагонов

В а го ны Багажн. 1 1 12

П очт. 1 8

Ж .плац к. 5 8 58 81

К упе 6 4 40 70

М ягк. 3 1 32 26

О предели ть опти мальное коли чество скоры х и пассажи рски х поездов, при котором чи сло перевози мы х пассажи ров дости гает макси мума. Реш и ть задачу в предположени и , что пропускная способность дороги не позволяетв день пройти болеечем ш ести пассажи рски м поездам. 2. Д ля и зготовлени я двух ви дов и здели й А и В фабри ка расходует в качестве сы рья сталь и ц ветны е металлы , и мею щ и еся в ограни ченном коли честве. Н а и зготовлени и указанны х двух и здели й заняты токарны е и фрезерны естанки . В следую щ ей табли ц епри ведены и сходны еданны езадачи : В иды р есур со в Объем Но р ма р а схо да на о дно изделие Ресур со в А В Сталь(кг) 570 10 70 Ц ветны еметаллы (кг) 420 20 50 Т окарны ест. (стан.ч.) 5600 300 400 Ф резерны ест.(стан.ч.) 3400 200 100 О предели ть план вы пуска продукц и и , при котором будет дости гнута макси мальная при бы ль. 3. П рои зводи тель вы пускает два продукта: продукт Р, продаваемы й по 2000 дол. за 1 т., и продукт Q, продаваемы й по 1000 дол. за 1 т. П родукты могут прои зводи ться и з двух ти пов сы рья: А по 600 дол. за 1 т. и В по 900 дол. за1 т. И з кажды х 100 тонн сы рья А прои зводят30 тонн Р и 50 тонн Q, а и з 100 тонн сы рья В прои зводят60 тонн Р и 10 тонн Q. Е сли прои зводи тель обрабаты вает х тонн А и у тонн В , покажи те, что его при бы ль состави т (500х+400у). Ф абри ка способна обработать не более 10000 тонн сы рья ежегодно. П оставщ и ки сы рья могутобеспечи тьнеболее6000 тонн сы рья А и

83

неболее8000 тонн сы рья В в год. П рои зводи тельможетпродаватьежегодно по 5000 тонн продуктаР и до 3200 тонн продуктаQ. • О предели те, сколько сы рья А и В должно бы ть заказано для макси ми зац и и его при бы ли ? П оставщ и ки сы рья А угрожаю тповы си тьц ену. • Н асколько можно поднятьц ену, чтобы прои зводи телю при ш лось и змени тьзаказ? 4. И мею тся три технологи чески х проц есса (I,II и III), связанны х с прои зводством некоторого продуктаи потреблени ем при этом четы рех ви дов сы рья. П р о дукты Ра схо д сы р ья по типа м с 1 2 3 4 I II III b

5 4 6 50

8 3 7 50

3 9 4 20

6 5 2 60

10 15 8

П усть сi означает ц ену продукта, полученного в результате при менени я 1-го проц есса с еди ни чной и нтенси вностью , bk – ресурсы k-го ви да сы рья и аki – расход k-го ви да сы рья при i-м проц ессе с еди ни чной и нтенси вностью . О предели те и нтенси вности и спользовани я каждого проц есса и з услови я обеспечени я макси муматоварной продукц и и . 5. П редпри яти е может вы пускать продукц и ю по трем технологи чески отработанны м способам прои зводства. П ри этом за1 часпо первому способу прои зводстваоно вы пускает20 еди ни ц продукц и и , по 2-му – 25 еди ни ц и по третьему – 30 еди ни ц продукц и и . К оли чество прои зводственны х факторов, расходуемы х за час при разли чны х способах прои зводства, и и мею щ и еся ресурсы эти х факторов представлены в следую щ ей табли ц е: Способ пр-ва

Ф а кто р ы Сы рье

Станочн ы й парк 3 4 2

Рабочая си ла 7 3 4

Э нерги я

Т ранспорт 1 0 1

П рочи е расходы 4 2 1

1 2 2 2 1 1 3 3 3 И мею щ и еся ресурсы 60 80 70 50 40 50 факторов Сплани роватьработу предпри яти я и з услови я получени я макси мума продукц и и , если и звестно, что общ еевремя работы предпри яти я составляет 30 часов.

84

6. Ф и рмапрои зводи ттри ви дапродукц и и (А ,В ,С), для вы пускакаждого и з которы х требуется определенноевремя обработки навсех четы рех устройствах I, II, III, IV. В ид В ремя обработки , ч П ри бы ль, дол продукц и и I II III IV A 1 3 1 2 3 B 6 1 3 3 6 C 3 3 2 4 4 П усть время работы на устройствах – соответственно 84, 42, 21, 42 ч. О предели те, какую продукц и ю и в каки х коли чествах следует прои зводи ть. (М ожете предположи ть, что ры нок сбы та для каждого и з продуктов неограни чен; временем, требуемы м для переклю чени я устройства в зави си мости от ви да продукц и и , можно пренебречь; рассмотри те только задачу макси ми зац и и при бы ли .) 7.Ф и рма реклами рует свою продукц и ю с и спользовани ем четы рех средств: телеви дени я, ради о, газет и афи ш . И з разли чны х рекламны х экспери ментов, которы е проводи ли сь в прош лом, и звестно, что эти средства при водят к увели чени ю при бы ли соответственно на 10, 3, 7 и 4 доллара в расчетена1 доллар, затраченны й нарекламу. Распределени ерекламного бю джетапо разли чны м средствам подчи нено следую щ и м ограни чени ям: полны й бю джетнедолжен превосходи ть500000 долларов; Следует расходовать не более 40% бю джета на телеви дени е и не более 20% бю джетанаафи ш и ; вследстви е при влекательности для подростков ради о на него следует расходовать по крайней мере полови ну того, что плани руется на телеви дени е. Сформули руйтезадачу распределени я средств по разли чны м и сточни кам как задачу ли нейного программи ровани я и и спользуйте си мплекс-метод для ее реш ени я. 8.Н ефтяная компани я закупает необработанную нефть и з нескольки х и сточни ков W, X, Y, Z и зани мается ее очи сткой, вы рабаты вая разли чны е ви ды А , В , С смазочны х масел, готовы х к продаже. И мею тся также ограни чени я при продаженаколи чество каждого ви дасмазочны х масел. М асло Состав, % В озможное коли чество для продажи , галлоны А Н еменьш е10 (W) 90000 Н ебольш е25 (Z) В Н еменьш е15 (W) 100000 С Н еменьш е20 (X) 120000 Н ебольш е50 (Y)

85

Ц ены (в условны х еди ни ц ах) 1 галлонасы рья и смазочны х масел при ведены ни же. Сы рье М асло X 72

Z W A B C Y 60 67 75 90 87 84 П редполагая, что необработанная нефть доступна в неограни ченном коли честве, сформули руйте задачу макси ми зац и и при бы ли как задачу ли нейного программи ровани я, найди теопти мальноереш ени е. 9.Предпри яти е располагает ресурсами сы рья, рабочей си лой и оборудовани ем, необходи мого для прои зводства лю бого и з четы рех ви дов прои зводи мы х товаров. Затраты ресурсов на и зготовлени е еди ни ц ы данного ви да товара, при бы ль, получаемая предпри яти ем, а также запасы ресурсов указаны в следую щ ей табли ц е: В ид ресурса

В и д товара 1 2

Сы рье, кг 3 Рабочая си ла, ч 22 О борудовани е, ст-ч. 10

5 14 14

3

4

2 18 18

4 30 16

О бъ ем ресурсов 60 400 128

П ри бы льнаеди ни ц у товарав рублях соответственно составляет30, 25, 56, 48. П о и сходны м данны м реш и тьследую щ и езадачи : • О предели ть ассорти мент товара, обеспечи ваю щ и й макси мальную при бы ль. • О предели тьопти мальны й ассорти ментпри дополни тельном услови и : 1-го товара вы пусти ть не более 5 ед., 2-го – не менее 8 ед., а 3-го и 4-го – в соотнош ени и 1:2. • Д ополни тельно к первой задаче заданы прои зводственны е и здержки в рублях на еди ни ц у каждого и здели я: 6, 9, 12, 3. Н айти опти мальны й ассорти мент, ми ни ми зи рую щ и й при бы ль, при услови и , что суммарны е прои зводственны еи здержки недолжны превы ш ать96 р. 10. Н ефтеперерабаты ваю щ и й завод получает4 полуфабри ката: 400 ты с. л. алки лата, 250 ты с. л. креки нг-бензи на, 350 ты с. л. бензи на прямой перегонки и 100 ты с. л. и зопетона. В результате смеш и вани я эти х четы рех компонентов в разны х пропорц и ях образуется три сорта ави ац и онного бензи на: бензи н А – 2:3:5:2, бензи н В – 3:1:2:1, бензи н С – 2:2:1:3. Стои мость 1 ты с. л. указанны х сортов бензи на характери зуется чи слами : 120 р., 100 р., 150 р. • О предели ть план смеш ени я компонентов, при котором будет дости гнута макси мальная стои мостьвсей продукц и и . • О предели ть опти мальны й план смеш ени я и з услови я макси мального и спользовани я компонентов.

86

11. Д ля и зготовлени я определенного сплава и з сви нц а, ц и нка и олова и спользуется сы рье в ви де следую щ и х пяти сплавов и з тех же металлов, отли чаю щ и хся составом и стои мостью 1 кг. Сплав

Содержани ев % III

I II IV V К омпонен ты Сви нец 10 10 40 60 30 Ц и нк 10 30 50 30 20 О лово 80 60 10 10 50 Стои мость 4 4,5 5,8 6,0 7,5 • О предели ть, сколько нужно взять сплава каждого ви да, чтобы и зготови ть с ми ни мальной себестои мостью сплав, содержащ и й 20% сви нц а, 30% ц и нкаи 50% олова. • Реш и ть ту же задачу, если для нового сплава задаю тся следую щ и е ограни чени я: оловаот40 до 60% и ц и нкаот20 до 30%. • Реш и ть ту же задачу при следую щ и х ограни чени ях на состав сплава: олованеболее405 и ц и нка– неменее20%. 12. И з четы рех ви дов основны х матери алов (медь, ц и нк, сви нец , ни кель) составляю т три ви да сплава латуни : обы чны й, спец и альны й и для художественны х и здели й. Ц ены еди ни ц ы веса меди , ц и нка, сви нц а, ни келя составляю т 0.8 р., 0.6 р., 0.4 р., 1 р., а еди ни ц ы веса сплава соответственно: 2 р., 3 р., 4 р. Сплав для художественны х и здели й должен содержать не менее 6% ни келя, не менее 50% меди и не более 30% сви нц а; спец и альны й – не менее 4% ни келя, неменее 70% меди , не менее 10% ц и нка и неболее20% сви нц а. В обы чны й сплав компоненты могутвходи тьбез ограни чени й. П рои зводственная мощ ность предпри яти я позволяет вы пускать (за определенны й срок) неболее400 еди ни ц весаобы чного сплава, неболее700 еди ни ц веса спец и ального сплава и не более 100 еди ни ц веса декорати вного сплава. Н айти прои зводственны й план, обеспечи ваю щ и й макси маль-ную при бы ль. 12. Д ля и зготовлени я брусьев трех размеров: 0.6 м., 1.5 м., 2.5 м. В соотнош ени и 2:1:3 нараспи лпоступаю тбревнадли ной в 3 м. О предели ть план распи ла, обеспечи ваю щ и й макси мальноечи сло комплектов.

Л И Т Е РА Т У РА О сновная: 1. А ттетков А . В . М етоды опти ми зац и и / А . В . А ттетков, С.В . Галки н, В .С. Заруби н.- М .: И зд-во М ГТ У и м. Баумана, 2001.- 480 с. 2. Галлеев Э .М . К урслекц и й по вари ац и онному и счи слени ю и опти мальному управлени ю .-М .: И зд-во М ГУ , 1996.-160 с.

87

3. К ури ц ки й Б.Я . П ои скопти мальны х реш ени й средствами EXCEL 7.0. – СП б.: BHV-Санкт-П етербург,1997.- 280 с. 4. Л етоваТ .А . М етоды опти ми зац и и в при мерах и задачах/ Т .А .Л етова, А .В . Пантелеев.-M.: В ы сш ая ш кола, 2002.- 544 с. 5. Л еси н В .В О сновы методов опти ми зац и и : У чеб. пособи е/ В .В . Л еси н, Ю .П . Л и совец . - М .: И зд-во М А И , 1998. - 344 с. Допол нит ел ьная: 1. А ш манов С.А . Т еори я опти ми зац и и в задачах и упражнени ях/ С.А . А ш манов, А .В . Т и мохов. - М .: Н аука, 1991.- 448 с. 2. БазараМ . Н ели нейноепрограмми ровани е. Т еори я и алгори тмы ./ М . Базара, К . Ш етти - М .: М и р, 1982. -583 с. 3. Бати щ ев Д .И О пти ми зац и я в СА П Р/ Д .И . Бати щ ев, Я .Е . Л ьвови ч, В .Н .. Ф ролов.- В оронеж: И зд-во В ГТ У , 1997 - 541 c. 4. Ги лл Ф . П ракти ческая опти ми зац и я/ Ф .Ги лл, У . М ю ррей, М . Райт.- М .: М и р, 1985.-509 с. 5. Реклейти сГ. О пти ми зац и я в техни ке. / Г. Реклейти с, А . Рейви ндран, К .Рагcдел: В 2 т. - М .: М и р, 1986.