Дәріс конспекті. Дәріс тақырыбы: Бейсызықты оптималдандыру есептері

Дәріс тақырыбы: Бейсызықты оптималдандыру есептері. Көп критерийлі оптималдандыру есептері.

Көптеген нақты оптималдандыру есептері бейсызықты болып табылады.

Бейсызықты мақсаттылық функцияның бір немесе бірнеше экстремумі бола алады. Көпэкстремальды мақсаттылық функция кезінде (4.3) айнымалылардың өзгеру диапазоны бірнеше кіші диапазондарға бөлінеді, мысалы

d_i < х_i < a_i, a_i < х_i < b_i, b_i < х_i < D_i, i = 0, 1, 2,... n, (4.13)

бұл кезде мақсаттылық функцияның әр диапазонының локальды экстремумі анықталады. Алынған локальды экстремумдерден глобалды экстремум таңдалады.

Шартсыз оптималдандыру есептері бейсызықты программалаудың ең қарапайым есептері болып табылады.

Бұл есептерде мақсаттылық функцияның абсолютті экстремумі шектеулерсіз және шектеу шарттарсыз анықталады.

Жоғарғы математика курсынан белгілі, бейсызықты функцияның экстремум нүктесінде (минимум, максимум) оның дербес туындылары нөлге тең болады. Демек, n айнымалысы бар бейсызықты функцияның экстремумін анықтау үшін барлық айнымалылары бойынша дербес туындыларын нөлге теңестіру қажет. n айнымалысы бар n теңдеуден құрылған жүйенің шешімі функцияның экстремумі алынатын айнымалылардың мәндерін береді.

Шартсыз минималдандыру есептері практикада сирек кездеседі, бірақ оларды шешу әдістері шартты оптималдандырудың практикалық есептерін шешудің негізі болып табылады.

Бұл есептерде мақсаттылық функцияның шартты экстремумі анықталады, яғни шектеулер мен шекті шарттарды ескере отырып функцияның экстремумі анықталады.

Шартты оптималдандыру есептерін шартсыз оптималдандыру есептеріне қарағанда шешу қиынырақ.

Сондықтан шартты оптималдандыру есебін (салыстырмалы экстремумін анықтау) қарапайым шартсыз оптималдандыру есебіне келтіруге тырысады (абсолютті экстремумді анықтау).

Мұндай процедура Лагранж әдісінде орындалады.

Лагранж әдісі.

Бейсызықты функцияның шартты экстремумін анықтау қажет

Z(x₁, x₂,... x_n) → extr (4.14)

m шектеулерінде n айнымалыларын анықтау қажет

f₁(x₁, x₂,... x_n) > b₁,

f₂(x₁, x₂,... x_n) = b₂, (4.15)

……………………..

Fm(x1, x2,... xn) < bm.

Шектеулер-теңсіздіктер теңдіктерге түрленеді, ал бос мүшелері шектеулердің сол жағына ауысады, яғни (4.15) жүйесі келесі түрге келтіріледі

f₁(x₁, x₂,... x_n, b₁) = 0,

f₂(x₁, x₂,... x_n, b₂) = 0, (4.16)

……………………….

f_m(x₁, x₂,... x_n, b_m) = 0.

Лагранж әдісіне сәйкес (4.16) шектеулерінде (4.14) функцияның салыстырмалы экстремумінің орнына Лагранж функциясының абсолютті экстремумі анықталады және ол келесі түрде жазылады:

L = Z(x₁, x₂,... x_n) + λ₁f₁(x₁, x₂,... x_n, b₁)+λ₂f₂(x₁, x₂,...

... x_nb₂) +... + λ_mf_m(x₁, x₂,... x_n, b_m) → extr, (4.17)

мұнда λ₁, λ₂,... λ_m – анықталмаған Лагранж көбейткіштері, x₁, x₂,... x_n айнымалылары сияқты ізделетін айнымалылар болып табылады.

Лагранж функциясына мақсаттылық функция және Лагранж көбейткішіне көбейтілген әр шектеу кіретіні байқауға болады.

(4.16) шектеулерімен (4.14) мақсаттылық функцияның салыстырмалы экстремумі (4.17) Лагранж функциясының абсолютті экстремумімен сәйкес келетіні дәлелденген.

(4.17) функцияның абсолютті экстремумі анықталуы белгілі әдістермен орындалады. Кейбір жағдайда Лагранж функциясының дербес туындылары анықталып, нөлге теңестіріледі:

∂L/∂x₁= ∂Z/∂x₁+ λ₁∂f₁/∂x₁+ λ₂∂f₂/∂x₁+...+λ_m∂f_m/∂x₁=0,

∂L/∂x₂= ∂Z/∂x₂+ λ₁∂f₁/∂x₂+ λ₂∂f₂/∂x₂+...+λ_m∂f_m/∂x₂=0,

……………………………………………………………..

∂L/∂x_n= ∂Z/∂x_n+λ₁∂f₁/∂x_n+ λ₂∂f₂/∂x_n+...+λ_m∂f_m/∂x_n=0, (4.18)

∂L/∂λ₁= f₁(x₁, x₂,... x_n, b₁)= 0,

∂L/∂λ₂= f₂(x₁, x₂,... x_n, b₂)= 0,

………………………………….

∂L/∂λ_m= f_m(x₁, x₂,... x_n, b_m)= 0.

Соңғы m теңдеулер оптималдандыру есебінің ( 4.16) шектеулерін көрсетеді.

(4.18) жүйесі (m+n) теңдеуден тұрады және белгісіздер саны да осындай болады. (4.18) жүйесінің шешімі (4.17) Лагранж функциясының абсолютті минимумының немесе (4.16) шектеулермен (4.14) мақсаттылық функцияның салыстырмалы минимумін координаталарын береді.

(4.18) жүйенің шешімі есептеу математикасының белгілі әдістерімен орындалады.

Егер (4.18) жүйесі бейсызықты болса, онда Гаусс әдісі қолданылады. Егер (4.18) жүйесі бейсызықты болса, онда Ньютон әдісі қолданылады.

Анықталмаған Лагранж көбейткіштерінің әдісін қолдану ерекшеліктері

1. Мақсаттылық функция дифференциалданатын болса, әдіс қолданылады. Егер мақсаттылық функция сызықты болса, әдісті қолдану мүмкін емес, себебі бірінші туынды константа болып табылады.

2. Егер мақсаттылық функция және шектеулер дискретті болса, әдісті қолдануға болмайды.

3. Туындыларды есептеу процестерін алгоритмдеуге болады, екі туындыны есептеу мүмкіндігі міндетті түрде қамтамасыз етілуі қажет.

4. Нақты есептердің шешімі үлкен өлшемділігімен байланысты, ал бұл жоғары реттік жүйелерді есептеуге үлкен қиындықтарды келтіреді.

5. Бұл есептің шешімі n – m > 0 шарты орындалған кезде болады, яғни айнымалылардың саны шарттар-шектеулер санынан көп болуы керек.

6. Егер n = m болса, онда оптималдандыру есебінің шешімі мүмкін емес. Бұл кезде есептің шешімі шектеулермен ғана есептеледі.

7. Егер n < m болса – есептелмейді, яғни берілген кеңістікте шарттар-шектеулер қанағаттандырылатындай нүктелердің біреуі де болмайды.

Көпкритерийлі оптималдандыру есептері

Жоғарыда қарастырылған оптималдандыру есептерінің шешімдері бір критерий бойынша (бір мақсаттылық функция бойынша) ғана орындалған. Практикада есепті бір критерийге келтіру әр уақытта мүмкін емес, себебі қажет мақсат бірнеше болуы мүмкін.

Оптималдандыру бірнеше критерий бойынша орындалатын есептер көпкритерийлі оптималдандыру есептері деп аталады. Мұндай оптималдандыру қабылданған критерийлер арасында келісімді орнатуға әрекет жасайды.

Мұндай келісімді табудың қажетті жағы әр критерийдің салмақ коэффициентінің мәні болып табылады. Нәтижесінде көпкритерийлі есепті шешу бір жалпы критерий бойынша оптималдандыруға келтіріледі, бұл критерийге барлық қабылданған критерийлердің шарттары өздерінің салмақтық коэффициенттерімен кіреді. Салмақтық коэффициенттерді анықтаудың көптеген әдістері бар. Осы әдістердің бірін, нақтысында эксперттік бағалау әдісін қарастырайық.

Бұл әдістің мәні келесіде:

Оптималдандыру есебін шешу үшін бірқатар критерий қабылданған (жалпы жағдайда s). Эксперт тобы жинақталады – берілген оптималдандыру есебі бойынша осы аумақтағы мамандар. Әр экспертке әр критерийді 0 -ден 1 -ге дейінгі баллда бағалауға ұсынылады. Бұл кезде барлық критерий бойынша әр эксперттің баллдарының қосындысы 1 -ге тең болатындай шарт беріледі.

і -ші критерийдің (i = 1, …, s) салмақтық коэффициенті ретінде осы критерий бойынша әр эксперттің бағасының орташа мәні қабылданады.

Көпкритерийлі есептің мүмкін шешімдерінің бірі жалпыланған мақсаттылық функция бойынша оптималдандыру болып табылады, оған қарастыруға алынған барлық критерийлер өздерінің салмақтық коэффициенттерімен кіреді.

Бұл жалпыланған функция келесі түрде жазылады:

→ max, (4.19)

мұнда Z_i – i -ші мақсаттылық функция, і -ші критерийді өрнектейді;

Z_{i норм} – і -ші мақсаттылық функцияның нормаланған мәні;

α_i – і -ші мақсаттылық функцияның салмақ коэффициенті;

s – мақсаттылық функцияның саны (қабылданған критерийлер саны).

Егер і -ші мақсаттылық функция максималдандырылатын болса, онда оның алдында қосынды белгісінің астында плюс қойылады. Егер і -ші мақсаттылық функция минималдандырылатын болса, онда оның алдында қосынды белгісінің астында минус қойылады.

Салмақтық коэффициенттерін эксперттік бағалау арқылы анықтауға болады.

і -ші мақсаттылық функцияның Z_{i норм} нормаланған мәні тек бір ғана і -ші критерий бойынша оптималдандыру есебін шешу нәтижелері бойынша қабылданады.

Жалпы жағдайда мақсаттылық функциялардың өлшем бірлігі әр түрлі болады. Сондықтан (4.19)өрнегінде әр мақсаттылық функцияның оның нормаланған мәніне бөлінуі енгізілген. Мұндай амал барлық мақсаттылық функцияларды бірдей өлшемділікке келтіреді (салыстырмалы бірліктерге, с.б.).

Көпкритерийлі есептер үшін шектеулер мен шектік шарттарды құрудың біркритерийлі есептерге қарағанда спецификалық ерекшеліктері болмайды.

Негізгі әдебиет 11[1-100],

Қосымша әдебиет 1 [430-440]

Бақылау сұрақтары:

1. Сызықты оптималдандыру есептерін шешудің негізгі әдістері және осы әдістердің негізгі этаптары.

2. Эксперттік бағалау әдісінің мәні.

3. Көпкритерийлі есептің жалпы мақсаттылық функциясын жаз.

4. «Мақсаттылық функцияның нормаланған мәні» ұғымын түсіндір.

5. Жалпыланған мақсаттылық функция бойынша оптималдандыру.

Не нашли, что искали? Воспользуйтесь поиском: