12- mavzu: Chiziqli programmalashtirishda ikkilanish nazariyasi. Chiziqli programmalashtirish masalasi yechimini ikkilanish nazariyasi yordamida tahlil qilish. Ikkilangan masalalar haqida asosiy tushunchalar
Download 466.5 Kb.
|
- Navigate this page:
- Masala .3.
- Ikkilangan masalalarning geometrik talqini
- Masala 20.
- Masala 21. Ikkilangan
1. Indeks satridan F dan absolyut qiymat bo‘yicha eng katta manfiy sonni olamiz. Bu son yechuvchi ustunni ko‘rsatadi. Ozod hadlarni mos ravishda echuvchi ustundagi musbat sonlarga bo‘lib ularning eng kichigini tanlaymiz. Bu satrga yechuvchi satr deyiladi . Yechuvchi ustun va yechuvchi satr kesishgan katakdagi songa yechuvchi son deyiladi. Simpleks jaldvallarni to‘ldirish formulalardan foydalanib qolgan kataklarni to‘ldiramiz. Natijada 2 – chi jadval hosil bo‘ladi. Bu jadvalda x2 – ni asosiy o‘zgaruvchilar safiga o‘tkazamiz. –ni qo‘shimcha o‘zgaruvchilar safiga o‘tkazamiz. 2-chi jadval
F - indeks satrida manfiy son (-5) bo‘lgani uchun 3 – chi simpleks jadvalni tuzamiz. Natijada quyidagi jadval hosil bo‘ladi. 3- chi jadval
F- indeks satri hadlarining hammasi musbat bo‘lgani uchun quyidagi yechim: , Optimal yechim bo‘ladi. Unga maqsad funksiyasining quyidagi qiymati mos keladi. Masala.3. Quyidagi shartlarda - funksiyani minimum qiymatini toping. Simpleks usul qoidalaridan foydalanib berilganlarning asosiy jadvalini tuzamiz. Jadval 1.
Ozod hadlar ustunidan manfiy sonlar ichidan eng kichik manfiy sonni olamiz. Bu son turgan satr yechuvchi satrni ko‘rsatadi. F satr hadlarini mos ravishda yechuvchi satrdagi sonlarga bo‘lib eng kichigini olamiz min . Bu ustunga yechuvchi ustun deyiladi. Yechuvchi satr va yechuvchi ustun kesishgan katakdagi son yechuvchi son deyiladi. Qo‘shimcha o‘zgaruvchi u3 – ni, v2 asosiy o‘zgaruvchi sifatida bazisga kiritamiz. Simpleks jadvallarni tuzish formulalaridan foydalanib 2-chi simpleks jadvalni tuzamiz 2 – jadval
O‘zgarmaslar ustunida manfiy son (-5) bo‘lgani uchun bu jadvalni ham yuqoridagi kabi almashtiramiz. Natijada quyidagi jadval hosil bo‘ladi. 3-jadval
Erkin hadlar ustunida hamma hadlar musbat bo‘lgani uchun quyidagi yechim optimal bo‘ladi Shunday qilib ikkilangan simpleks usul orqali masala yechildi. Quyidagi masalalarni chiziqli dasturlashning ikkilangan masalasiga keltiring va ikkilangan simpleks usul bilan yeching 4. 5. 6. 7.
8. 9.
10. 11.
12. 13. 14. 15. 16. 17. 18. 19.
Ikkilangan masalalarning geometrik talqini Agar berilgan va unga ikkilangan masalalarda o‘zgaruvchilar soni ikkiga teng bo‘lsa, chiziqli dasturlash masalalarining geometrik tahlilini berish osonlashadi. Bu holda bir –birini istsino qiluvchi quyidagi uchta hol bo‘lishi mumkin: 1) ikkala masala ham optimal yechimga ega; 2) faqat bitta masala optimal yechimga ega; 3) ikkala masalaning optimal rejalari bo‘sh to‘plamni tashkil qiladi. Masala 20. Quyidagi shartlar bo‘yicha masalani ikkilangan masalaga keltiring va ikkala masalaning yechimlarini toping. Yechish. Bu masalaga ikkilangan masala: funksiyaning quyidagi shartlarda minimum qiymatini topishdan iborat bo‘ladi 2.1-chizma Berilgan va unga ikkilangan masalada ham noma’lumlar soni ikkita (x1 va x2), (u1 va u2) uning uchun geometrik usul bilan yechish mumkin. Dastlabki masalada maqsad funksiyasi V nuqtada maksimum qiymatga ega. Shuning uchun V(2; 6) nuqtada F (2; 6)=22+76=46 maqsad funksiyasi optimal rejaga (planga) ega (2.1-chizma). Ikkilangan masala esa Ye(1; 4) nuqtada minimum qiymatga (2.2-chizma) ega. Shuning uchun F*(1; 4) = 141+84=46 – maqsad funksiyasining minimal qiymatidir. Masala 21. Ikkilangan masalalar juftligining yechimlarini toping. Dastlabki masala Ikkilangan masala Yechish. Dastlabki masala va unga ikkilangan masala ham ikkitadan o‘zgaruvchiga ega. Shuning uchun ularni geometrik usul bilan yechamiz. Ikkala masala uchun ham shakllarni chizamiz. (chizmalar 2.3,2.4) 2.3-chizma 2.3 -chizmadan ko‘rinib turibdiki dastlabki masala yechimga ega emas. Chunki maqsad funksiyasi mumkin bo‘lgan yechimlar to‘plamida quyidan chegaralanmagan. Chizma2.4-dan ko‘rinib turibdiki ikkilangan masalaning ham optimal rejalari yo‘q, chunki yechimlar ko‘p burchagi bo‘sh to‘plamni tashkil qiladi. Shunday qilib dastlabki masala optimal rejaga ega bo‘lmasa (maqsad funksiyasi mumkin bo‘lgan yechimlar to‘plamida chegaralanmagan bo‘lgani uchun) unga ikkilangan masala ham optimal rejaga ega bo‘lmaydi. Download 466.5 Kb. Share with your friends:
|