3 М И Н И СТ Е РСТ В О О БРА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Н Н Ы Й...
9 downloads
191 Views
948KB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
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.