7-mavzu. Chiziqsiz dasturlash masalalari 1-ma’ruza rejasi


Download 1.56 Mb.
bet15/16
Sana10.02.2023
Hajmi1.56 Mb.
#1184057
1   ...   8   9   10   11   12   13   14   15   16
Bog'liq
7-mavzu. Chiziqsiz dasturlash masalalari

2-usul. noma’lumning qiymati orttirib borilganda ifoda birinchi bo’lib nolga aylansin, ya’ni quyidagi munosabat o’rinli bo’lsin:
. (74)

U holda noma’lumni bazisga kiritish uchun yangi




(75)
o’zgaruvchi tanlaymiz hamda (75) dan ni ajratib, yangi sistemaning birinchi tenglamasini tuzamiz:


.
Topilgan noma’lumning qiymati masala shartlari (69) ga va maqsad funktsiyaga qo’yamiz va yangi sistema hosil qilamiz. Yangi sistemada o’zgaruvchilar ajratilgan (bog’liq) o’zgaruvchilar bo’lib, lar esa ozod o’zgaruvchilar bo’ladi. ozod o’zgaruvchilarni nolga tenglab, yangi

bazis yechimini hosil qilamiz.
k-qadamda masala xj va ui noma’lumlarni o’z ichiga olishi mumkin. xj ui dan shunisi bilan farq qiladiki, xj ning ishorasiga chegara qo’yiladi ga esa bunday chegara qo’yilmaydi. Demak, u musbat ham, manfiy ham bo’lishi mukin. Bunday o’zgaruvchilar uchun Kun-Takkerning optimallik sharti bo’ladi.
Masalaning bazis yechimida bo’lishi kerak. Agar bo’lsa, tegishli tenglama va o’zgaruvchi masala shartlaridan o’chirib tashlanadi.
Algoritmning k-qadamida qo’yidagi ishlar bajariladi:
1. k-1-qadamda topilgan bazis yechim uchun optimallik shar-ti tekshiriladi. Agar xj ozod o’zgaruvchilar uchun bo’lib, yangi kiritilgan barcha ui o’zgaruvchilar uchun bo’lsa topilgan yechim optimal yechim bo’ladi.
2. Agar optimallik sharti bajarilmasa, u holda shartni qanoatlantiruvchi kamida bitta ui aniqlanadi. Bu yerda qo’yidagi 3 hol ro’y berishi mumkin:
a) Bu holda ui ning qiymatini kamaytirish kerak. Natijada maqsad funktsiyaning qiymati ortadi.
b) Bu holda ui ning qiymatini orttirish natijasida maqsad funktsiyaning qiymati ortadi.
v) Bu holda tengsizlikni qanoatlantiruvchi xt noma’lum tanlanadi. Bu noma’lum yoki bazisga kiritiladi va uning qiymati

formula orqali topiladi, yoki bo’lmasa, masalaning maqsad funktsiyasi yuqoridan chegaralanmagan ekanligi (barcha j lar uchun) aniqlanadi. Agar k-qadamda yangi bazis yechim topilgan bo’lsa, k+1 qadamga o’tiladi. Maqsad funktsiyaning yuqoridan chegaralanmagan ekanligi aniqlingan bo’lsa, masalaning yechish jarayoni to’xtatiladi.
Taqqoslash uchun yuqorida Barankin-Dorfman usuli bilan yechilgan masalani ko’ramiz va uni Bill usuli bilan yechamiz.
5-misol. Quyidagi masala yechilsin:


Yechich. Masala shartidagi birinchi tenglamadan x3 ni, ikkinchisidan x4 ni ajratamiz va f(x) maqsad funktsiyani (71) ko’rinishda yozamiz. Natijada berilgan masalani qo’yidagi ko’rinishga keltiramiz:




(76)
(76) dan ko’rish mumkinki,

Ozod o’zgaruvchilar (x1,x2) ga nol qiymat berib, boshlang’ich bazis yechimini aniqlaymiz:

Endi

bo’lganligi sababli x1 noma’lumni bazisga kiritamiz. Buning uchun

sonni aniqlaymiz va
(77)
belgilash kiritamiz. (77) dan x1 ni ajratib, bazis o’zgaruvchilarni almashtiramiz:
(78)
Topilgan x1 ning qiymatini masalaning shartlari va maqsad funktsiyaga qo’yamiz hamda (78) ni (76) sistemaga qo’shib yozamiz. Natijada qo’yidagilarni hosil qilamiz:
(79)
(78)-(79) masaladagi ozod o’zgaruvchilarga nol qiymat berib, yangi bazis yechimni topamiz:

dan ko’rinadiki,

Demak, bazisga x2 noma’lumni kiritish kerak.

bo’lganligi sababli x2 ni bazisga kiritib, bazisdan x4 ni chiqarish kerak. Demak, tenglamadan x4 ni x2 ga almashtiramiz:
(80)
Hosil bo’lgan (80) tenglamani yangi sistemaning birinchi tenglamasi deb qaraymiz. So’ngra topilgan x2 ning qiymatini masalaning shartlari (78) ga va maqsad funktsiya (79) ga qo’yib, yangi sistemaning qolgan tenglamalari va maqsad funktsiyasini hosil qilamiz:
(81)
(82)
Yangi bazis yechim. u1= 0 da

Shuning uchun topilgan yechim bazis yechim bo’lmaydi. Demak, bazis yechimni optimallashtirish kerak. Buning uchun u1 ni bazisga kiritamiz.
bo’lganligi sababli
(83)
yangi noma’lumni kiritamiz. (83) dan u1 ni ajratib, yangi sistemaning birinchi tenglamasini tuzamiz:
(84)
(84)ni (81) va (82) ga qo’yib topamiz:
(85)
(86)

Yangi bazis yechim (u2 = 0 da):



(9.80)dan ko’rinadiki,

Demak, X(3) uchun Kun-Takker shartlari bajariladi. Shuning uchun bu yechim optimal yechim bo’ladi. Shunday qilib, masalaning optimal yechimi:

Bu yechimni Barankin-Dorfman usuli bo’yicha topilgan yechim bilan solishtirib, ularning bir xil ekanligiga ishonch hosil qilish mumkin.



Download 1.56 Mb.

Do'stlaringiz bilan baham:
1   ...   8   9   10   11   12   13   14   15   16




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling