Mavzu: Chiziqli programmalashtirish masalalari Reja: Asosiy tushunchalar. Chiziqli programmalashtirish masalasining qo’yilishi

2. Chiziqli programmalashtirish masalasining yechimi.
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
1 1 2 2 0 ... Px P x P x P     n n , X  0
chegaraviy shartlarda topilsin.
1-ta’rif. (2.1.9)-chegaraviy shartlarni qanoatlantiruvchi n o`lchovli 1 2 ( , ,..., ) X x x x  n vektor berilgan chiziqli programmalashtirish masalasining mumkin bo`lgan yechimi deyiladi.
2-ta’rif. (2.1.11)-maqsad funksiyaga min(max) qiymat beruvchi * * * * 1 2 ( , ,..., ) X x x x  n – mumkin bo`lgan yechimni masalaning optimal yechimi deyiladi.
f- maqsad funksiyaning * * * * 1 2 ( , ,..., ) X x x x  n mumkin bo`lgan yechimdagi qiymati * f X( ) bo`lsin. Agar har qanday X uchun   * * f X f X f X f X ( ) ( ) ( ) ( )   tengsizlik bajarilsa, * * * * 1 2 ( , ,..., ) X x x x  n - mumkin bo`lgan yechimga masalaning maqsad funksiyasiga min (max) optimal qiymat beruvchi optimal yechim deyiladi.
3-ta’rif. (2.1.9) tenglamada musbat i x koeffitsientlar bilan qatnashuvchi Pi ( i  1, m ) vektorlar o`zaro chiziqli bog`liqsiz bo`lsa, mumkin bo`lgan * * * * 1 2 ( , ,..., ) X x x x  n yechimni masalaning tayanch yechimi deyiladi. Har bir Pi vektor m o`lchovli bo`lgani uchun musbat koordinatalar soni m dan ortmaydi.
4-ta’rif. Musbat koordinatalari soni m ga teng bo`lgan 1 2 ( , ,..., ) X x x x  n tayanch yechim - xosmas tayanch yechim, aks holda esa xos tayanch yechim deyiladi. 24
5-ta’rif. Chiziqli programmalashtirish masalasining (2.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:
1 2 3 1 3 1 2 3 1 2 3 3 2 max; 2 1, 3 4 2 6 2 2 0, 1, 2,3. j x x x x x x x x x x x x j               Chiziqli sistemaning birinchi tengsizligiga 4 x va ikkinchi tengsizligiga 5 x qo`shimcha o`zgaruvchilarni kiritamiz. Natijada quyidagi kononik ko’rinishdagi ChPM hosil qilinadi:
3 2 max; 2 1, 3 4 2 6, 2 2, 0, 1, 2,3. j x x x x x x x x x x x x x x j           