Amaliy matematika va informatika ta’lim yo’nalishi 2-oliy ta’lim 4-bosqish talabasi
§ 4. Chiziqli programmalash masalalari uchun bazis tanlash va masala shartlarini tanlangan bazisga moslashtirish
Yüklə 0,77 Mb.
|
|
§ 4. Chiziqli programmalash masalalari uchun bazis tanlash va masala shartlarini tanlangan bazisga moslashtirish. Kanonik ko'rinishda berilgan ChPMni qaraymiz.
n ∑aij x j =bi i =1,2, …, m (4.1) j=1 x j ≥ 0 j =1,2, …, n n L =∑C j x j → max (4.2) j=1 Bu yerda avval ta'kidlaganimizdek m n bo'ladi, ya'ni (4.1) sistemaning yechimlari cheksiz ko'p. Shu yechimlar orasidan (4.2) shartga mos keladigani, ya'ni maqsad funksiyasiga maksimal qiymat beradiganini ajratib olish kerak. Buning uchun (4.1) sistema yechimlarini ifodalash qoidasini va ular orasidan bazis o'zgaruchilarni ajratish usulini aniqlashimiz kerak. (4.1) sistema matritsasi tartibi m × n bo'lganligi va mn bo'lgani uchun RgA ≤ m bo'ladi. Qulaylik uchun RgA=m deb olamiz. Aksariyat hollarda bu shart bajariladi. A matritsadan o'zaro chiziqli erkli bo'lgan m ta ustunni ajratib olamiz. Bu ustunlarni Aj1, Aj2 , … , Ajm deb belgilaymiz. Ular chiziqli erkli bo'lishi uchun shu ustun elementlaridan tuzilgan C = ( Aj1, Aj2 , … , Ajm ) matritsa determinanti noldan farqli bo'lishi kerak, ya'ni detC ≠ 0 . Tanlangan bazisga mos tayanch yechimni topish uchun esa shu bazisga mos x j1, x j2 , … , x jm noma'lumlardan boshqa barcha x j larni nolga teng deb olamiz. Natijada (4.1) sistema soddalashib m ∑aijk x jk =bi i =1, 2, …, m (4.3) k=1 ko'rinishni oladi. Bu sistema m noma'lumli m ta chiziqli algebraik tenglamalar sistemasi bo'lib qoladi. detC ≠ 0 bo'lganligi uchun uning yagona yechimi bo'ladi. Agar bu yechim uchun barcha x jk ≥ 0 bo'lsa topilgan yechim tanlangan bazisdagi tayanch yechim deyiladi. Agar x jk lar orasida manfiylari ham chiqib qolsa, tanlangan bazisda tayanch yechim yo'q deyiladi va boshqa bazisga o'tiladi. Tayanch yechimi mavjud bo'lgan bazis tanlangach esa shu bazisdagi tayanch yechim optimallikka tekshiriladi. Bu esa avvalgi paragrafda ko'rilgan usulda amalga oshiriladi. Faqat buning uchun masala shartlari tanlangan bazisga moslashtirilishi kerak. Buning uchun tanlangan bazisga mos C matritsa uchun teskari matritsa topiladi va (4.2) sistema vektor ko'rinishida C-1 ga ko'paytiriladi. Bunda sistema C−1 AX =C −1b (4.4) ko'rinishini oladi. (4.4) sistema (4.2) maqsad funksiyasi bilan birgalikda dastlabki simpleks jadval uchun asos qilib olinadi. Simpleks jadvaldan tanlangan bazisdagi tayanch yechim optimal bo'lishi tekshirilishi mumkin. Keltirilgan mulohazalar va hisoblash jarayonini amaliy misolda tahlil qilamiz. Quyidagi ko'rinishdagi ChPM berilgan bo'lsin 3x1 + 2x2 + 3x3 + 2x4 = 7 4x1 + 3x2 + 3x3 + 4x4 = 9 xi ≥ 0 L = 20x1 +15x2 + 30x3 + 25x4 → max Bu yerda matritsa ustunlari 4ta bo'lib ularni A1 , A2 , A3 , A4 vektorlar deb belgilasak ular ikki o'lchovli fazo vektorlari (m=2) bo'lgani uchun bazis sifatida ulardan ikkitasini olish mumkin. Bunda variantlar soni C42 = 6ta bo'ladi. Ulardan ixtiyoriy bittasini, masalan A1 , A2 bazis bo'lgan holni olsak C =43 32 bo'lib detС =1 ≠ 0 ekanligini ko'ramiz. Bu bazisga mos yechimni topish uchun x3,x4 = 0 deb olinadi va sistema 3x1 + 2x2 = 7 4x1 + 3x2 = 9 ko'rinishini oladi. Bu sistemani yechib x3 = 3; x2 =−1ekanligini ko'ramiz. Bu yerda x2 0 bo'lganligi uchun bu bazisdagi yechim tayanch yechim bo'la olmaydi. Boshqa bazis tanlashga to'g'ri keladi. Masalan A2 , A3 bazisni olsak C =23 33 ; detC =−3 ≠ 0 Demak A2 , A3 bazis bo'la oladi. Bu bazisdagi yechimni topish uchun sistemada x1 = 0; x4 = 0 deb olinsa u quyidagi ko'rinishni oladi 2x2 + 3x3 = 7 3x2 + 3x3 = 9 Bu sistemani yechib x2 = 2; x3 =1ekanligini ko'ramiz. Bu yerda xi ≥ 0, demak bu bazisdagi x1 = 0;x2 = 2;x3 =1;x4 = 0yechim tayanch yechim bo'lar ekan. Bu yechimning optimal bo'lish bo'lmasligini tekshirish uchun masala shartini tanlangan bazisga moslashtiramiz. Teskari matritsani hisoblash qoidasiga ko'ra C−1 =− 13 −33 −23 ekanligini ko'ramiz. Masala shartini shu teskari matritsaga ko'paytiramiz x 1 1 3 − 33 2 3 2x2 1 3 − 37 − 3 − 3 2 4 3 3 4x3 =− 3− 3 2 9 x4 x1 − 13−−13 −03 03 −2 6xx23 =− 13−− 63 − x4 x1 + x2 + 2x4 = 2 13 x1 + x3 − 23 x4 =1 Shartlar bazisga moslashtirildi, ya'ni bazis vektorlar A2 , A3 ga mos ustunlar birlik vektor ko'rinishini oldi. Bu bazisga mos tayanch yechim x2 = 2; x3 =1optimalligini tekshirish uchun simpleks jadval tuzamiz
Yüklə 0,77 Mb. Dostları ilə paylaş:
|