Chiziqli dasturlash masalasining bazis rejasi

chiziqli programmalashtirish masalasining bazis rejasi Reja: 1. Bazis rejaning optimallik alomati 2. Simpleks usulning umumiy sxemasi 3. Simpleks-jadval. Chizi=li programmalashtirish masalasining bazis rejasi Chizi=li programmalashtirish masalasi kanonik kirinishda berilgan bilsin: (6.1) (6.2) (6.3) Chizi=li programmalashtirish masalasining yechimi yoki rejasi bazis yechim bilishi uchun biri-biriga teng bilmagan lar uchun =uyidagi ifoda irinli bilishi kerak: , bu yerda . Bazis yechim geometrik tasviri- kipburchak uchidir. Bu yerda - bazis yechim emas, - bazis yechim ta'rif: yechimning musbat komponentlariga tegishli shartlar vektorlar sistemasi chizi=li erkli bilsa, yechim (6.1)-(6.3) masalaning bazis yechimi, bazis rejasi deyiladi. Misol. +uyidagi cheklashlar sistemasi berilgan bilsin. bazis yechim biladimi, ani=laylik. Yu=oridagi ta'rifga kira, berilgan yechimda musbat komponentlar , ularga =uyidagi shartlar vektorlari mos keladi: . Agar shu vektorlar chizi=li erkli bilsa, yechim bazis yechim biladi. Bu vektorlar koordinatalaridan tuzilgan determinantni shisoblaylik. Demak, lar chizi=li erkli va bazis yechim biladi. Natija. (6.1)-(6.3) masalaning bazis yechimi musbat komponentlari soni sonidan oshmaydi (bu yerda - masalaning shartlari tenglamalar soni) - masalaning ixtiyoriy bazis yechimi bilsin. - uning musbat komponentlari soni ligini isbotlash mumkin. Faraz =ilaylik, , ani=lik uchun , u sholda yechimning musbat komponentlariga ilchovli vektordan tuzilgan sistema mos keladi, lekin bu sistema chizi=li boli=. Shunday =ilib, bazis yechimning musbat komponentlar soni cheklashlar sistemasi tenglamalari sonidan oshmaydi. Chizi=li programmalashtirish masalasining bazis yechimlarni 2 guruhga bilamiz: a) agar , bilsa xosmas bazis yechim (yoki xosmas bazis reja) deyiladi. b) agar , bilsa xos bazis yechim (yoki xos bazis reja) deyiladi. ta'rif. Chizi=li programmalashtirish masalasining bazis yechimining bazisi deb yechimlarning musbat komponentlariga tiri keluvchi barcha ta shartlar vektorlari (chizi=li erkli) sistemasiga aytiladi. Xosmas bazis yechim bazisiga yechimning musbat komponentlari mos keluvchi vektor kiradi. Xosmas bazis yechim yagona bazisga ega. Faraz =ilaylik, bilsin, - xos bazis yechim: Xos bazis yechimning bazisini =anday ani=laymiz? Buning uchun bazisning ta'rifidan kelib chi=amiz bazisga yechimning musbat komponentlariga mos keluvchi vektorlar kiradi. Bazis ta'rifiga kira, shartlar vektorlari sistemasi chizi=li boli=, shuning uchun =olgan shartlar vektorlar tarkibida shartlar vektorlari ( chizi=li kombinatsiyasi bilmagan) topiladi. shartlar vektorlarini tanlab, bazisni hosil =ilamiz. tanlash yagona emas. Xos bazis yechimining bazisi =uyidagilardan iborat: yechimning musbat komponentlariga mos barcha vektorlar; yechimning nol vektorlariga va birinchi vektorlarning chizi=li kombinatsiyasi bilmagan vektorlarga mos vektorlar. Shunday =ilib, xos bazis yechim bir necha bazislarga ega bilishi mumkin, xosmas bazis yechim esa yagona bazisga ega. Teorema. Chizi=li programmalashtirish masalalari chekli sondagi bazis yechimlarga ega. Isbot. Щar bir bazis yechimga bazis mos keladi. bazis yechimlar soni barcha bazislar sonidan oshib ketmaydi. Bazislar ...