1.8.5 Дөңес бағдарламалау есептері
Келесі сызықтық емес бағдарламалау есебі қарастырылсын:
F (х1 , х2 , . . ., хn) → max (9.8.)
g1( х1 , х2 , . . ., хn ) ≤ b1 , 1=1,m (9.9)
х1 ≥ 0, j = 1, n (9.10)
Мұндағы F, g1 – берілген функциялар.
Анықтама. Дөңес Х жиынында берілген F (х) функциясы дөңес деп аталады, егер кез келген х1 және х2 нүктелері мен кез келген 0 ≤ λ ≤ 1 саны үшін келесі шарт орындалса:
F [ х2 + ( 1 - λ )х1 ] ≤ λ F(х2) + ( 1 - λ) F(х1) (9.11)
Анықтама. Дөңес Х жиынында берілген F (х) функциясы ойыс деп аталады, егер кез келген х1 және х2 нүктелері мен кез келген 0 ≤ λ ≤ 1 саны үшін келесі шарт орындалса:
F [ х2 + ( 1 - λ )х1 ] ≥ λ F(х2) + ( 1 - λ) F(х1) (9.12)
Анықтама. Егер F (х) функциясы ойыс (дөңес), ал gi(х) функциялары дөнес болса, онда (9.8) – (9.10) есебі дөнес бағдарламалау есебі деп аталады.
Анықтама. Дөнес бағдарламалау есебінің (9.8) – (9.10) Лагранж функциясы деп келесі функцияны атайды:
Z(x,y) = F(x) +[ bi – gi(x) ] , (9.13)
мұндағы у1,у2,...,уm - Лагранж көбейтінділері.
Анықтама. Лагранж функциясының ер нүктесі деп (х0,у0) нүктесін
Z(x,y0) ≤ Z(x0,y0) ≤ Z(x0,y) (9.14)
Теорема (Кун – Таккер). Берілген (9.8) – (9.10) дөнес бағдарламалау есебінің х0 тиімді шешімі тек у0 ( уі0 ≥ 0 ) векторы болған жағдайда ғана болады; мұндағы (х0,у0) – Лагранж функциясының ер нүктесі болғанда:
≤ 0 ; = 0 ; хj0 ≥ 0, j =
(9.15)
≥ 0 ; = 0 ; ≥ 0, і =
Сонымен, осы анықтамалар мен Кун-Таккер теоремасын пайдаланып, дөнес бағдарламалау есебін шешу жолын көрсетейік:
Лагранж функциясы құрастырылады.
Лагранж функциясы үшін (9.15) түрінде ер нүктесінің болуының қажеттілігі мен жеткілікті шарттары жазылады.
Ер нүктесінің болмауын анықтайды немесе ол нүктенің координатын табады.
Берілген есептің тиімді шешімін жазып, мақсат функциясының мәнің табады.
Достарыңызбен бөлісу: |