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

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 x_j va u_i noma’lumlarni o’z ichiga olishi mumkin. x_j u_i dan shunisi bilan farq qiladiki, x_j 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 x_j ozod o’zgaruvchilar uchun bo’lib, yangi kiritilgan barcha u_i o’zgaruvchilar uchun bo’lsa topilgan yechim optimal yechim bo’ladi.
2. Agar optimallik sharti bajarilmasa, u holda shartni qanoatlantiruvchi kamida bitta u_i aniqlanadi. Bu yerda qo’yidagi 3 hol ro’y berishi mumkin:
a) Bu holda u_i ning qiymatini kamaytirish kerak. Natijada maqsad funktsiyaning qiymati ortadi.
b) Bu holda u_i ning qiymatini orttirish natijasida maqsad funktsiyaning qiymati ortadi.
v) Bu holda tengsizlikni qanoatlantiruvchi x_t 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 x₃ ni, ikkinchisidan x₄ 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 (x₁,x₂) ga nol qiymat berib, boshlang’ich bazis yechimini aniqlaymiz:

Endi

bo’lganligi sababli x₁ noma’lumni bazisga kiritamiz. Buning uchun

sonni aniqlaymiz va

(77)
belgilash kiritamiz. (77) dan x₁ ni ajratib, bazis o’zgaruvchilarni almashtiramiz:
(78)
Topilgan x₁ 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 x₂ noma’lumni kiritish kerak.

bo’lganligi sababli x₂ ni bazisga kiritib, bazisdan x₄ ni chiqarish kerak. Demak, tenglamadan x₄ ni x₂ ga almashtiramiz:

(80)
Hosil bo’lgan (80) tenglamani yangi sistemaning birinchi tenglamasi deb qaraymiz. So’ngra topilgan x₂ 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. u₁= 0 da

Shuning uchun topilgan yechim bazis yechim bo’lmaydi. Demak, bazis yechimni optimallashtirish kerak. Buning uchun u₁ ni bazisga kiritamiz.

bo’lganligi sababli
(83)
yangi noma’lumni kiritamiz. (83) dan u₁ ni ajratib, yangi sistemaning birinchi tenglamasini tuzamiz:
(84)
(84)ni (81) va (82) ga qo’yib topamiz:
(85)
(86)
Yangi bazis yechim (u₂ = 0 da):

(9.80)dan ko’rinadiki,

Demak, X⁽³⁾ 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.