Strreplkirish I bob. Chiziqli programmalashtirish masalalari 1-§. Chiziqli programmalashtirish masalalaining amaliy masalalari

1.2. Chiziqli programmalashtirish masalasining yechimlari haqida
Endi chiziqli programmalashtirish masalasi yechimlarining ta’riflari ustida to`xtalamiz. Vektor formada berilgan quyidagi chiziqli programmalashtirish masalasini ko`raylik:
f (X) CX
maqsad funksiyaning min qiymati

X 0
chegaraviy shartlarda topilsin.
1-ta’rif. (1.1.9)-chegaraviy shartlarni qanoatlantiruvchi n o`lchovli vektor berilgan chiziqli programmalashtirish masalasining mumkin bo`lgan yechimi deyiladi.
2-ta’rif. (1.1.11)-maqsad funksiyaga min(max) qiymat beruvchi mumkin bo`lgan yechimni masalaning optimal yechimi deyiladi.
f- maqsad funksiyaning mumkin bo`lgan yechimdagi qiymati * f (X^* ) bo`lsin.
Agar har qanday X uchun tengsizlik bajarilsa, - mumkin bo`lgan yechimga masalaning maqsad funksiyasiga min (max) optimal qiymat beruvchi optimal yechim deyiladi.
3-ta’rif. (1.1.9) tenglamada musbat koeffitsientlar bilan qatnashuvchi vektorlar o`zaro chiziqli bog`liqsiz bo`lsa, mumkin bo`lgan yechimni masalaning tayanch yechimi deyiladi.
Har bir vektor m o`lchovli bo`lgani uchun musbat koordinatalar soni m dan ortmaydi.
4-ta’rif. Musbat koordinatalari soni m ga teng bo`lgan tayanch yechim - xosmas tayanch yechim, aks holda esa xos tayanch yechim deyiladi.
5-ta’rif. Chiziqli programmalashtirish masalasining (1.1.2) chiziqli sistemasi nomanfiy ( X 0 ) yechimga ega bo`lmasa (Sistema birgalashmagan bo`lsa), masalaning o`zi ham yechimga ega bo`lmaydi. Chiziqli programmalashtirish masalasini (ChPM) kononik ko’rinishga keltirishga doir misollar ko`raylik.
1-misol. Quyidagi ko`rinishda berilgan ChPM ni kononik ko`rinishga
keltiring:

Chiziqli sistemaning birinchi tengsizligiga va ikkinchi tengsizligiga qo`shimcha o`zgaruvchilarni kiritamiz. Natijada quyidagi kononik ko’rinishdagi ChPM hosil qilinadi:

2-misol. Quyidagi masalani kononik ko’rinishdagi ChPM ga keltiring:

Bu uerda barcha chegaraviy shartlar tenglamalardan iborat, lekin va o`zgaruvchilarga nomanfiylik sharti qo`yilmagani uchun,masalani kanonik ko’rinishdagi ChPM deyish mumkin emas. Masalani kononik ko’rinishga keltirish uchun va yangi o`zgaruvchilarning ayirmalari shaklida ifodalaymiz:






va o`zgaruvchilarning bu ifodalarini masala shartiga qo`ysak, kononik ko`rinishdagi quyidagi ChPM ga kelamiz: