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:
- Ta’rif.
- Masala 1 Quyidagi
|
12- Mavzu: Chiziqli programmalashtirishda ikkilanish nazariyasi. Chiziqli programmalashtirish masalasi yechimini ikkilanish nazariyasi yordamida tahlil qilish. Ikkilangan masalalar haqida asosiy tushunchalar Bizga chiziqli dasturlash masalasi berilgan bo‘lsin.a (1) maksad funksiyasi (2) ning maksimum qiymatini topish kerak bo‘lsin. Har qanday chiziqli dasturlash masalasini ikkilangan masala deb ataluvchi masala bilan uzviy bog‘liq ekanligini ko‘rsatish mumkin. Ta’rif. Quyidagi shartlar (3) qanoatlantirilganda (4) funksiyaning minimum qiymatini topishga (1), (2) chiziqli dasturlash masalasining ikkilangan masalasi deyiladi. Bu masalalarning optimal yechimlari o‘zaro quyidagi teorema asosida bog‘langan. Teorema. Agar berilgan masala yoki unga ikkilangan masalalardan birortasi optimal yechimga ega bo‘lsa, u holda ikkinchisi ham optimal yechimga ega bo‘ladi, hamda bu masalalardagi chiziqli funksiyaning optimal qiymatlari o‘zaro teng bo‘ladi, ya’ni . Agar yoki – chiziqli funksiyalardan birontasi chegaralanmagan bo‘lsa, u holda masala hech qanday yechimga ega bo‘lmaydi. Ikkilanganlik masalalari simmetrik va simmetrik bo‘lmagan masalalarga bo‘linadi. Yuqoridagi teorema simmetrik bo‘lmagan masalalarni yechishda qo‘llaniladi. Shuni ham aytish kerakki tengsizliklar sistemasini qo‘shimcha o‘zgaruvchilar yordamida tenglamalar sistemasi ko‘rinishiga keltirish mumkin. Demak, simmetrik ikkilanmalik masalalarni simmetrik bo‘lmagan ikkilanmalik masalaga keltirish mumkin. Shuning uchun simmetrik bo‘lmagan ikkilanish maslalarining optimal yechimlari haqidagi teorema simmetrik ikkilangan masalalar uchun ham o‘rinlidir. Masala 1 Quyidagi shartlar bilan berilgan masalani ikkilangan masalaga keltiring Masalani ikkilangan masalaga keltirish uchun oldin chegaralovchi shartlarni bir xil ko‘rinishdagi tengsizliklarga keltiramiz. Buning uchun birinchi tengsizlikni teskari ko‘rinishga keltiramiz Hosil bo‘lgan masalaga ikkilangan masala quyidagi ko‘rinishda bo‘ladi Ikkilangan masalani chiziqli dasturlashning asosiy masalasiga keltirib simpleks usul bilan yechish mumkin. Download 466.5 Kb. Share with your friends:
|