2-amaliy mashg`ulot Mavzu: Chiziqli dasturlash masalasini grafik usulida yechish

2-amaliy mashg`ulot

Mavzu: Chiziqli dasturlash masalasini grafik usulida yechish

CHDM ning umumiy ko`rinishi quyidagicha bo`ladi:

(1)
Agar (1) masalada o`zgaruvchilar soni ikkita bo`lsa, ushbu masalani grafik usulda yechish mumkin bo`ladi. Natijada masalaning umumiy ko`rinishi quyidagicha bo`ladi:
(2)
(2) masalasini grafik usulda yechish Quyidagi tartibda bajariladi:
1) Berilgan masalalardagi tengsizliklarga mos tenglamalarni tuzamiz:

tenglamalarni koordinatalar tekisligida ifodalaymiz.

1. 
   Тengsizliklarga mos yarim tekisliklarni ifodalaymiz.
   
2. 
   Yarim tekisliklarning kesishmasini qaraymiz. Agar kesishma bo`sh to`plam bo`lsa, masala yechimga ega bo`lmaydi. Agar kesishma chekli ko`pburchakdan iborat bo`lsa, masalaning yechimi chekli qiymatga ega bo`ladi. Ushbu ko`pburchak yechimlar ko`pburchagi deyiladi va uning ixtiyoriy nuqtasi berilgan tengsizliklar sistemasini qanoatlantiradi. Masalaning optimal yechimini topish uchun o`zgaruvchilarning shunday qimatlarini topish kerakki, ushbu qiymatlarda z maqsad funksiyasi eng katta yoki eng kichik qiymatga erishsin. Bunday qiymatlar yechimlar ko`pburchagining chegarasida bo`ladi. Agar optimal yechim ko`pburchakning bitta uchida bo`lsa, yechim yagona bo`ladia, aks holda masala cheksiz ko`p yechimga ega bo`lib, ular ko`pburchakning optimal yechim qabul qiladigan uchlarini birlashtiruvchi sohasida bo`ladi. Agar yarim tekisliklar kesishmasi cheksiz soha bo`lsa, masala yechimining qiymati yuqoridan chegaralanmagan bo`lishi mumkin. Agar kesishma bo`sh bo`lmasa, masala ikki xil usulda yechiladi.
   

Birinchi usul:

1. 
   Yechimlar ko`pburchagining uchlari koordinatalari aniqlanadi.
   
2. 
   Aniqlangan koordinatalar z funksiyasiga qo`yiladi.
   
3. 
   Hosil bo`lgan qiymatlarning eng katta yoki eng kichigi topiladi.
   

Ikkinchi usul:
1) normal vektor chiziladi.
Nomal vektorga perpendikular bo`lgan to`g`ri chiziq chiziladi.
2) Masala maksimumga qarayotgan bo`lsa, to`g`ri chiziq normal bo`ylab o`ziga nisbatan parallel holda suriladi., Masala minimumga qaralayotgan bo`lsa, normal vector yo`nalishiga qarama-qarshi tomonga suriladi.

3. 
   to`g`ri chiziq yechimlar ko`pburchagidan chiqib ketayotgandagi oxirgi urinuvchi nuqtada masala optimal yechimga ega bo`ladi.