logo
Русский O'zbekcha
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Parametrga bog’liq chiziqli tenglamalar sistemasini yechish algoritmi.

Parametrga bog’liq chiziqli tenglamalar sistemasini yechish algoritmi.

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

4

Hajmi:

377.8 KB
Ko'chirib olish shartlari
Mavzu: Parametrga bog’liq chiziqli tenglamalar sistemasini yechish algoritmi. MUNDARIJA. 1.bob.Umumiy tushunchalar.Tenglamalar sistemasini yechish usullari. 1.1 - § . Chiziqli tenglamalar sistemasi. Kroneker-Kapelli teoremasi 1.2 - § . Chiziqli tenglamalar sistemasini yechishning Kramer usuli. 1.3 - § .Chiziqli tenglamalar sistemasini yechishning Gauss usuli. 1.4 - § . Chiziqli tenglamalar sistemasini Teskari matritsaviy usuli. II.Chiziqli tenglamalar sistemasining manfiymas va parallelepipeddagi yechimlarini aniqlash. 2. 1 - § .Chiziqli tenglamalar sistemasini manfiymas yechimlarini aniqlash. 2.2 - § .Chiziqli tenglamalar sistemasining manfiymas yechimlari mavjudligini simpleks usulda aniqlash. 2.3 - § . Chiziqli tenglamalar sistemasini parallelepipedda yechimi mavjudligini aniqlash. 2.4 - § . Misollar III. Parametrga bog’liq bo’lgan chiziqli tenglamalar sistemasi yechimlar to’plamining parametrning barcha qiymatlarida bo’sh yoki bo’sh emasligini aniqlash algoritmi. 3.1 - §. Kesmada berilgan parametrga bog’liq bo’lgan chiziqli tenglamalar sistemasining parametrning barcha qiymatlarida yechimini yoki mavjud emasligini aniqlash algoritmi. 3.2 - §. Parallelepipedda berilgan parametrga bog’liq bo’lgan chiziqli tenglamalar sistemasining parametrning barcha qiymatlarida yechimi mavjud yoki mavjud emasligini aniqlash algoritmi. 4.bob . Misollar. 1.Foydalanilgan adabiyotlar. 2. Xulosa. I-BOB 1.Chiziqli tenglamalar sistemasi. Bizga m ta tenglamadan iborat n ta noma’lumli chiziqli tenglamalar sistemasi berilgan bo‘lsin: {a 11 x 1 +a 12 x 2 +...+a 1n x n =b 1¿{a 21 x 1 +a 22 x 2 +...+a 2n x n =b 2¿{.........................................¿¿¿¿ (1) bu yerda, x1,x2,..,xn noma’lumlar. Tenglamalarni birinchi, ikkinchi, va hokazo m- tenglama deb nomerlab chiqilgan deb hisoblaymiz. aij koeffitsient i- tenglamadagi xj noma’lumning koeffitsientini, bi esa i-tenglamaning ozod hadi. Noma’lumlar oldidagi koeffitsientlarni m ta satr va n ta ustundan iborat matritsa ko‘rinishida yozish mumkin: A= ( a11 a12 ... a1n a21 a22 ... a2n ... ... ... ... am1 am2 ... amn ) ) ) ¿ ) (2) Ushbu matritsa chiziqli tenglamalar sistemasining asosiy matritsasi deyiladi. Quyidagi ¯A matritsa esa chiziqli tenglamalar sistemasining kengaytirilgan matritsasi deyiladi: A = ( ¿ ¿ a11 a12 ... a1n b1 a21 a22 ... a2n b2 ... ... ... ... ... am1 am2 ... amn bm ¿ ) ) ) ) ¿ )¿ (3) Agar (1) sistemaning barcha ozod hadlari 0 ga teng bo‘lsa, u holda (1) sistema bir jinsli tenglamalar sistemasi deb ataladi. Agar (1) sistemada m=n bo‘lsa, u holda ushbu sistema n - tartibli sistema deyiladi. Yechimga ega bo‘lgan chiziqli tenglamalar sistemasi birgalikda deyiladi. Masalan, ixtiyoriy bir jinsli tenglamalar sistemasi birgalikda bo‘ladi, chunki barcha noma’lumlarni 0 ga teng qilib olinsa, u bir jinsli tenglamalar sistemasining yechimi bo‘ladi. Yagona yechimga ega bo‘lgan sistema aniq sistema, bittadan ortiq yechimga ega bo‘lgan sistema aniqmas sistema deyiladi. 1.1 - § Bir jinsli tenglamalar sistemasi. Kroneker-Kapelli teoremasi. Ushbu mavzuda chiziqli tenglamalar sistemasini umumiy yechimini topish usulini beramiz. Dastlab, bir jinsli tenglamalar sistemasini qaraymiz. Bizga {a 11 x 1 +a 12 x 2 +...+a 1n x n =0¿{a 21 x 1 +a 22 x 2 +...+a 2n x n =0¿{........................................¿¿¿¿ (1.1.1) bir jinsli tenglamalar sistemasi berilgan bo‘lsin. Ma’lumki, ushbu sistemaning matritsasini A va matritsaning ustunlarini v1,v2,...,vn deb olsak, sistemani x1v1+x2v2+...+xnvn=0 yoki A ¿X=0 ko‘rinishlarda ham yozish mumkin, bu yerda X  noma’lumlardan iborat bo‘lgan ustun vektor. 1-tasdiq. Agar Z1,Z2,...,Zk ustunlar bir jinsli chiziqli tenglamalar sistemasining yechimi bo‘lsa, u holda ularning ixtiyoriy chiziqli kombinatsiyasi ham yechim bo‘ladi. Isbot. Haqiqatdan ham, A⋅Zi= 0 ekanligidan A⋅(c1Z1+c2Z2+...+ckZk=c1A⋅Z1+c2A⋅Z2+...+ckA⋅Zk=0 kelib chiqadi. 1.1.1-teorema. Bir jinsli chiziqli tenglamalar sistemasining ixtiyoriy yechimi n -r ta chiziqli erkli yechimlarning chiziqli kombinatsiyasidan iborat bo‘ladi, bu yerda n  noma’lumlar soni, r= rang(A). Isbot. Sistemani x1v1+x2v2+...+xnvn=0 ko‘rinishida yozib olaylik. r =rang(A) ekanligi uchun v1,v2,...,vn ustunlar jamlanmasida r ta ustun bazis bo‘ladi. Umimiylikka ziyon yetkazmagan holda, dastladki r ta v1,vr,...,vr ustunni bazis deb olish mumkin. Bu holda qolgan vr+1,vr+2,...vn ustunlar v1,v2,...vr ustunlarning chiziqli kombinatsiyasi orqali ifodalanadi, ya’ni vr+1=br+11v1 + br+12v2+… br+1rvr v r + 2 = b r + 21 v 1 + b r + 22 v 2 + … b r + 2 r v r ………………………………………… vn=bn1v1 + bn2v2+… bnrvr. u tengliklardan quyidagi n  r ta ustunning yechim ekanligini ko‘rish qiyin emas, Z r + 1 = ( b r + 11 … … … b r + 1 r − 1 0 … . 0 ) , Z r + 2 = ( b r + 21 … … … b r + 2 r 0 − 1 … … .. 0 ) ,………. Z n = ( b n 1 … … … b nr 0 0 … . 1 )  yechimlar chiziqli erkli ekanligi osongina kelib chiqadi, chunki bu ustunlarning oxirgi n  r ta komponentalaridan tuzilgan minorni qarasak, ushbu minor noldan farqli bo‘ladi. Endi ixtiyoriy yechim bu yechimlar orqali chiziqli ifodalanilishini ko‘rsatamiz. Aytaylik, X= ( x 1¿ , … . , x r¿ , x r + 1 ,¿ … … x n¿ ) ustun sistemaning boshqa bir yechimi bo‘lsin. U holda Y=X+ xr+1¿ Zr+1+...+xn¿Zn ustun ham sistemaning yechimi bo‘ladi. Ma’lumki, bu yechimda ( r  1)-komponentadan boshlab barcha komponentalar nolga teng, ya’ni Y= y 1¿ , … . , y r¿ , 0 … … 0 ) Ushbu ustun sistemaning yechimi bo‘lganligi uchun y 1¿ v 1 + y 2¿ v 2 +…….. + y r¿ v r =0 Ammo, v 1 , v 2 , … .. , v r ustunlar chiziqli erkli ekanligidan ¿y1 ¿ = y2¿ =…….. ¿yr¿ =0 kelib chiqadi. Demak, Y  0, ya’ni X=− xr+1¿ Zr+1−...− xn¿Zn Shunday qilib, Zr+1,Zr+2,… … Zn chiziqli erkli yechimlar bo‘lib, barcha yechimlar ularning chiziqli kombinatsiyasi orqali ifodalanadi. Teorema isbotida keltirilgan , Z r + 1 , Z r + 2 , … … Z n yechimlar jamlanmasi bazis yoki fundamental yechim deb ataladi. Sistemaning umumiy yechimi deb fundamental yechimning umuniy chiziqli kombinatsiyasiga aytiladi. Ularning biror aniq chiziqli kombinatsiyasi esa xususiy yechim bo’ladi.uniy chiziqli kombinatsiyasiga aytiladi. Ularning biror aniq chiziqli kombinatsiyasi esa xususiy yechim bo‘ladi. Bir jinsli bo‘lmagan chiziqli tenglamalar sistemasi yechimini ham bir jinsli sistema yechimi orqali berish mumkin. Aytaylik, bir jinsli bo‘lmagan (1.1.2) sistema berilgan bo‘lsin. Bu sistemaning asosiy va kengaytirilgan matritsalarini qaraymiz, ya’ni A= Quyidagi teorema bir jinsli bo‘lmagan chiziqli tenglamalar sistemasi yechimi mavjudligini uning matritsalari ranglari orqali beruvchi teorema hisoblanadi. 1.1. 2-teorema. (Kroneker–Kapelli teoremasi) Chiziqli tenglamalar sistemasi yechimga ega bo‘lishi uchun uning asosiy matritsasining rangi kengaytirilgan matritsasining rangiga teng (ya’ni, rang ( A )  rang ( A ) ) bo‘lishi zarur va yetarli. Isbot. Tenglamalar sistemasini quyidagicha yozib olamiz: bu yerda B ozod hadlardan tuzilgan ustun. Sistema yechimga ega bo‘lishi uchun B ustun ustunlarning chiziqli kombinatsiyasi orqali ifodalanishi zarur. Bundan esa, matritsalarning ranglari tengligi kelib chiqadi. Agar matritsalarning ranglari bir hil bo‘lsa, dagi , bazis B ustunlar uchun ham bazis bo‘la oladi. Bundan esa B ustun , ustunlarning chiziqli kombinatsiyasi orqali ifodalanishi kelib chiqadi. 1.1.3-teorema. Bir jinsli bo‘lmagan chiziqli tenglamalar sistemasining umumiy yechimi, uning biror xususiy yechimi va xuddi shu koeffitsientlardan tuzilgan bir jinsli tenglamalar sistemasining umumiy yechimi yig‘indisiga teng. Isbot. Aytaylik, ustun A  X  B bir jinsli bo‘lmagan chiziqli tenglamalar sistemasining biror yechimi bo‘lsin. U holda A  X  B va A   B ekanligidan, A  X  A   sistemaga ega bo‘lamiz. Demak, berilgan sistema A  ( X  )  0 bir jinsli sistemaga teng kuchli. Bir jinsli tenglamalar sistemasining umumiy yechimi  X   ekanligidan . Ya’ni berilgan tenglamaning umumiy yechimi biror xususiy yechim va bir jinsli tenglamalar sistemasining umumiy yechimini yig’indilaridan iborat. 1.2 - § Chiziqli tenglamalar sistemasini yechishning Kramer usuli. Chiziqli tenglamalar sistemasini yechishning Kramer usuli sistemadagi tenglamalar soni noma’lumlar soniga teng bo‘lgan hol uchun o‘rinli bo‘ladi. { a11x1+a12x2+...+a1nxn= b1 a21x1+a22x2+...+a2n=b2 … … … … … … … … … … … … … … an1x1+an2x2+...+annxn= bn (1.2.1) ko‘rinishdagi tenglamalar sistemalarini qaraymiz. Tenglamalar sistemasi koeffitsientlaridan tuzilgan matritsa determinantini d harfi bilan belgilaylik: d= | a11 … a1j a21 … a2j … … … … a1n … a2n … … an1 … anj … ann | (1.2.2) Berilgan determinantni satr yoki ustun bo‘yicha yoyish xossalaridan quyidagilarga ega bo‘lamiz: d= a 1 j A 1 j + a 2 j A 2 j +…….+ a1jAnj (1.2.3) Bundan tashqari a 1 i A 1 j + a2iA2j… … … + a 1 j A nj i  j . (1.2.4) Ya’ni, determinantning birorta ustunidagi hamma elementlarini boshqa ustunning algebraik to‘ldiruvchilariga ko‘paytmalari yig‘indisi nolga teng. Agar d=a1jA1j +a2jA2j +…….+ a1jAnj A yoyilmada j- ustunning elementlarini ixtiyoriy n ta sonlar sistemasi b1,b2,… ..,bn bilan almashtirsak, hosil bo‘ladigan b 1 A 1 j + b 2 A 2 j +…….+ b n A nj (1.2.5) ifoda d determinantning j -ustunini shu sonlar bilan almashtirish natijasida hosil bo‘ladigan ushbu dj = | a 11 … a 1 j a 21 … a 2 j … … … … a 1 n … a 2 n … … a n 1 … a nj … a nn | determinantning j -ustun bo‘yicha yoyilmasi bo‘ladi. 1.2.1-teorema. Agar (1.2.2) sistemaning determinanti d noldan farqli bo‘lsa, u holda bu sistema yagona yechimga ega bo‘lib, uning ko‘rinishi quyidagicha bo‘ladi: x1 = d 1 d , x1 = d 2 d ,…….., x1 = d n d (1.2.6) Isbot. Aytalylik, d  0 bo‘lsin.  { a 1,1 x 1 + a 1,2 x 2 + ... + a 1 , n x n = b 1 a 2,1 x 1 + a 2,2 x 2 + ... + a 2 , n x n = b 2 … … … … … … … … … … … … … … a n , 1 x 1 + a n , 2 x 2 + ... + a n , n x n = b n sistemadagi birinchi tenglamaning ikkala tomonini A1j ga, ya’ni a1j elementning algebraik to‘ldiruvchisiga ko‘paytiramiz. Ikkinchi tenglamaning ikkala tomonini A2j ga va hokazo, oxirgi tenglamani Anj ga ko‘paytiramiz. Bu tengliklarning chap va o‘ng tomonlarini alohida-alohida qo‘shib, quyidagi tenglikka kelamiz: ¿ ¿ + a21A2j +…….+ an1Anj¿x1 + … … ..+¿¿ + a2jA2j +…….+ anjAnj¿xj + …………+ ¿ ¿ + a2nA2j +…….+ annAnj¿xn = ¿¿ + b2A2j +…….+ bnAnj Yuqorida qayd qilingan (1.2.3), (1.2.4) va (1.2.5) munosabatlardan, ushbu tenglikda xj oldidagi koeffitsient d ga, qolgan koeffitsientlarning barchasi nolga teng ekanligini, ozod had esa dj determinantga teng bo‘lishini hosil qilamiz. Demak, yuqoridagi tenglik quyidagi ko‘rinishga keladi: dx j  dj , 1  j  n . d  0 bo‘lganligi uchun xj = d j d 1  j  n kelib chiqadi Endi α 1 = d j d , α 2 = d 2 d ,…… α n = d n d  sonlar haqiqatdan ham (1.2.1) tenglamalar sistemasini qanoatlantirishini ko‘rsatamiz. Buning uchun sistemaning i -tenglamasiga a , α 2 , α n , noma’lumlarning qiymatlarini qo‘yamiz. i -tenglamaning chap tomonini , ∑ j = 1n a ij x j , ko‘rinishda yozish mumkinligi va , d j  ∑j=1 n bkAij bo‘lganligi uchun: ∑ j = 1n a ij d j d = 1 d ∑ j = 1n a ij ( ∑ k = 1n b k A kj ) = 1 d ∑ j = 1n b k ( ∑ j = 1n a ij A kj ) Bu almashtirishlarga 1 d soni barcha qo‘shiluvchilarda umumiy ko‘paytuvchi bo‘lib kelganligi uchun uni yig‘indi tashqarisiga chiqarishimiz mumkin. Bundan tashqari, qo‘shish tartibi o‘zgartirilgandan so‘ng, bk ko‘paytuvchi ichki yig‘indi belgisi tashqarisiga chiqarildi, chunki u ichki yig‘indi indeksi j ga bog‘liq emas. Ma`lumki, ∑ j = 1n a i , j A k , j = a i , 1 A k , 1 + a i , 1 A k , j +…….+ a i , n A k , n ifoda k=i bo‘lganda d ga, qolgan barcha k larda esa 0 ga teng. Shunday qilib, k bo‘yicha tashqi yig‘indida faqat bitta qo‘shiluvchi qoladi va u bi d ga teng bo‘ladi, ya’ni ∑ j = 1n a i , j d j d = 1 d b i d = b i Bundan α 1 , α 2 , α n , sonlar haqiqatdan ham (1.2.1) tenglamalar sistemasi uchun yechim bo‘lishi kelib chiqadi. Chiziqli tenglamalar sistemasini yechishning ushbu usuliga Kramer usuli deyiladi. Demak, Kramer usuli determinanti noldan farqli bo‘lgan n ta noma’lumli n ta tenglamadan iborat chiziqli tenglamalar sistemasini yechimini topish imkonini beradi. Sistema determinanti nolga teng bo‘lgan hollarda Kramer usulini qo‘llash maqsadga muvofiq emas. Chunki bu holatda tenglamalar sistemasi yoki yechimga ega emas yoki cheksiz ko‘p yechimga ega bo‘ladi 1.3 - § Chiziqli tenglamalar sistemasini yechishning Gauss usuli. Bizga bir hil tartibli ikkita chiziqli tenglamalar sistemasi berilgan bo‘lsin ∑ k = 1n a i , k x k = b i , i = 1 , m (1.3.1) va ∑ k = 1n c i , k x k = d i , i = 1 , m (1.3.2) 1.3.1-t a’rif. Agar (1.3.1) sistemaning ixtiyoriy ikkita tenglamasini o‘rinlari almashtirish natijasida (1.3.2) sistema hosil qilinsa, (1.3.2) sistemani (1.3.1) dan I  tur elementar almashtirish natijasida hosil qilingan deyiladi. 1.3.2-t a’rif . Agar (1.3.1) sistemaning biror tenglamasini biror songa ko‘paytirib, boshqa biror tenglamasiga qo‘shish natijasida (1.3.2) sistema hosil qilinsa, (1.3.2) sistema (1.3.1) sistemadan II  tur elementar almashtirish natijasida hosil qilingan deyiladi. I - tur va II - tur elementar almashtirishlarni qisqacha elementar almashtirish deb yuritiladi. Har bir chiziqli tenglamalar sistemasiga uning kengaytirilgan matritsasini mos qo‘ysak, u holda chiziqli tenglamalar sistemasi ustidagi elementar almashtirishlarga uning kengaytirilgan matritsasi ustida mos elementar almashtirishlar bajarilgan deb qarash mumkin. Aksincha, kengaytirilgan matritsa ustidagi elementar almashtirishlarga (elementar almashtirishlar ta’rifini to‘g‘ridan-to‘g‘ri matritsalar uchun ham aytishimiz mumkin) tenglamalar sistemasi ustidagi elementar almashtirishlar mos keladi. 1.3.3-t a’rif. Agar (1.3.1) va (1.3.2) sistemalar bir vaqtning o‘zida birgalikda bo‘lmasa, yoki bir vaqtda birgalikda bo‘lib, bir xil yechimlarga ega bo‘lsa, (1.3.1) va (1.3.2) sistemalar teng kuchli sistemalar deyiladi va (1.3.1)⇔ (1.3.2) ko‘rinishda yoziladi. 1.3.1-teorema. Agar (13.9) sistemaga (13.8) sistemadan elementar almashtirishlar natijasida hosil bo‘lgan bo‘lsa, ular teng kuchlidir. 1.3.1 Isbot . I tur elementar almashtirishlar uchun teoremaning isboti to‘g‘ridan to‘g‘ri ko‘rinib turibdi. Endi (1.3.1) sistemaga II tur elementar almashtirishlarni qo‘llaymiz, ya’ni (1.3.1) sistemaning birorbir i -tenglamasini  ga ko‘paytirib, j -tenglamaga qo‘shsak, yangi sistemaning j satrida qolganlari o‘zgarmagan holda ∑ k = 1n ( a ¿ ¿ ik + λ a ik ) x k = b i ¿ +λ bi tenglama hosil bo‘ladi. Agar x r0 , x 2 ,0 … … xn,0 sonlar (1.3.1) sistemaning yechimlari bo‘lsa, u holda ∑ k = 1n ( a ¿ ¿ ik + λ a ik ) x k0 ¿ = ∑ k = 1n a ik x k0 +λ∑k=1 n aikxk0 = bi+λai tenglamaning ham yechimi bo‘ladi va aksincha. Elementar almashtirishlar natijasida hosil bo‘lgan (1.3.2) tenglamalar sistemasining yechimi (1.3.1) tenglamalar sistemasining ham yechimi bo‘ladi. Endi biz sistemani yechishning eng qulay va ko‘p qo‘llanadigan usullaridan biri bo‘lgan, noma’lumlarni ketma-ket yo‘qotish usulini ya’ni, Gauss usulini keltiramiz. 1) Faraz qilaylik, (1.3.1) sistemada a11  0 bo‘lsin. U holda sistemaning birinchi tenglamasini ,   − ai1 a11 ,  i=2,m ga ko’paytirib ravishda boshqa tenglamalarga qo‘shsak, hosil bo‘lgan sistemaning birinchi tenglamasidan boshqa tenglamalarida xi noma’lumi oldidagi koeffitsientlari nolga aylanadi. 2) Agar a11  0 bo‘lsa, xi ning a11 koeffisientlari orasida noldan farqli bo‘lgan tenglamasini izlaymiz va I tur elementar almashtirish yordamida sistemaning birinchi tenglamasi bilan o‘rnini almashtirib, birinchi holatga kelamiz. 3) Agar xi oldidagi hamma a i 1 koeffitsientlar nollardan iborat bo‘lsa, biz birinchi yoki ikkinchi holatlarni x2 noma’lum uchun qo‘llaymiz va hokazo, bu jarayonni davom ettirish natijasida biz (1.3.1) sistemaga teng kuchli bo‘lgan sistemaga kelamiz. Hosil bo‘lgan sistemaga qarab, quyidagi xulosalarni chiqazishimiz mumkin: 1. Agar sistemaning zinapoyali shaklida chap tomonida nol va o‘ng tomonida noldan farqli hadlar qatnashuvchi tenglamalar hosil bo‘lsa, bunday sistema birgalikda bo‘lmaydi. 2. Agar sistema uchburchaksimon { a 11' x 1 + a 12' x 2 + ... + a 1 n' x n = b 1' a 22' x 2 + ... + a 2 n' x n = b 2' … … … … … … … … … … … … … a n − 1 , n − 1' x n − 1 + a n − 1 , n' x n = b n − 1' a nn' x n = b n shaklga kelib a11 ¿,a22'ann'  bo‘lsa, sistema birgalikda bo‘lib, yechim quyidagi algoritm bo‘yicha topiladi. Hosil bo‘lgan sistemaning oxirgi ann'xn'  bn' tenglamasidan xn0= bn1 ann1 noma’lumni topib, topilgan noma’lumni bitta yuqoridagi tenglamaga qo‘yamiz. So‘ngra, x10 x20 … … … … xn0 tenglamaga qo‘yamiz. Bu jarayonni davom ettirish natijada barcha x10,x20,...,xn0 noma’lumlarni noma’lumni topib, uni yuqoridagi aniqlaymiz. 3. Sistema zinapoyali shaklga kelib, zinapoya uchlarida turuvchi noma’lumlar soni r ta 1  r  min( m , n ) bo‘lsin. U holda ularni tenglamalarning chap tomonida qoldirib, qolgan n  r ta noma’lumni tenglamalarning o‘ng tomoniga o‘tkaziladi va ularni ozod o‘zgaruvchilar sifatida qabul qilinadi. Natijada tenglamalar sistemasi r ta noma’lumli uchburchak shaklidagi sistemaga keladi. Endi tenglamalarni o‘ng tomoniga o‘tgan n  r ta noma’lumga qiymatlar berib, qolgan r ta noma’lumni topamiz. Demak, bu holatda sistema cheksiz ko‘p yechimga ega bo‘ladi. Ya’ni, bunday tenglamalar sistemasi birgalikda aniqmas sistema bo‘ladi. Bundan tashqari, qaralayotgan sistemada tenglamalar soni noma’lumlar sonidan kichik bo‘lsa, u holda sistemani uchburchak shakliga keltirish mumkin emas, chunki Gauss metodi bo‘yicha o‘zgartirish jarayonida tenglamalar soni kamayishi mumkin, ammo ortishi mumkin emas. Demak, bunday holatda sistema zinapoyasimon shaklga keltiriladi va u aniqmas sistema bo‘ladi. Misol .1.4.1. Ushbu tenglamalar sistemasini Gauss usuli bilan yeching: { x1+2x2− x3+3x4= 5 2x1+3x2− 4x3+x4= 2 x1+x2−3x3−2x4=3 Bu sistemaning kengaytirilgan matritsasini yozib, uni elementar almashtirishlar yordamida o‘zgartiramiz: ( 1 2 − 1 3 2 3 − 4 1 1 1 − 3 − 2 | 5 2 3 ) ( 1 2 − 1 3 0 − 1 − 2 − 5 0 − 1 − 2 − 5 | 5 − 8 − 2 ) ( 1 2 − 1 3 0 − 1 − 2 − 5 0 0 0 0 | 5 − 8 6 ) 0  6 tenglamaga ega bo‘lgan sistemaga keldik, demak, berilgan sistema yechimga ega emas. Misol .1.4.2. Ushbu tenglamalar sistemasini Gauss usuli bilan Yeching { x 1 − x 2 + 3 x 3 = 2 x 1 + 2 x 2 + 5 x 3 = − 9 2 x 1 − 5 x 2 − 4 x 3 = 23 Sistemaning kengaytirilgan matritsasi uchun elementar almashtirishlar qo’llab ( 1 − 1 3 1 2 5 2 − 5 − 4 | 2 − 9 23 ) ( 1 − 1 3 0 3 2 0 − 3 − 10 | 2 − 11 19 ) ( 1 − 1 3 0 3 2 0 0 − 8 | 2 − 11 8 ) sistemaning matritsasini uchburchak shaklga keltiramiz. Demak, bu sistema yagona yechimga ega va quyidagi tenglamalar sistemasiga teng kuchli bo‘ladi: { x1− x2+3x3= 2 3x2+52 =− 11 −8x3=8 Bu sistemada pastdan yuqoriga qarab harakat qilib, x3=−1,x2=− 3,x1= 2 yagona yechimni topamiz. Misol .1.4.3. Ushbu tenglamalar sistemasini Gauss usuli bilan yeching: { x 1 − 2 x 2 + 3 x 3 − 4 x 4 = − 2 2 x 1 − 4 x 2 + x 3 + 3 x 4 = 2 − x 1 + 2 x 2 + 2 x 3 − 7 x 4 = − 4 Sistemaning kengaytirilgan matritsasini qaraymiz: ( 1 − 2 3 − 4 2 − 4 1 3 − 1 2 2 − 7 | − 2 2 − 4 ) ( 1 − 2 3 − 4 0 0 − 5 11 0 0 5 11 | − 2 6 − 6 ) ( 1 − 2 3 − 4 0 0 − 5 11 0 0 0 0 | − 2 6 0 ) Sistemaning matritsasi zinapoyasimon shaklga kelganligi uchun birgalikda va cheksiz ko‘p yechimga ega. x1va x3 noma’lumlar oldidagi koeffitsientlar uchburchak shaklni berganligi uchun x1,x4 noma’lumlarini o‘ng tomonga o‘tkazib, ozod o‘zgaruvchilar sifatida qabul qilamiz. { x1+3x3=−2+2x2+4x4 −5x3=6−11 x4 Bu yerda x3= 6−11 x4 −5 hosil bo‘ladi. Bu ifodani yuqoridagi tenglamaga olib borib qo‘ysak, x 1 = 8 + 10 x 2 − 13 x 4 5 hosil bo‘ladi. Shunday qilib, x 1 = 8 + 10 x 2 − 13 x 4 5 x 3 = − 6 + 11 x 4 5 berilgan tenglamalar sistemasi yechimlarining umumiy ko‘rinishi bo‘ladi. Bu formulada 2 x va 4 x larga ixtiyoriy qiymatlar berib, x1,,x3 larni topish orqali xususiy yechimlarni hosil qilish mumkin. Masalan, x1  1, x4  1 qiymatlar bersak, x1  1, x4  1, x4  1 qiymatlar bersak, x1  1, x4  1, x 4  1 qiymatlar bersak, x 1  1, x4  1, topilib, (1, 1, 1, 1) xususiy yechimga ega bo‘lamiz. 1.4 - § . Chiziqli tenglamalar sistemasini yechishning teskari matritsa usuli. Chiziqli tenglamalar sistemasini yechishning teskari matritsa usuli ham tenglamalar soni noma’lumlar soniga teng bo‘lgan hol uchun o‘rinli bo‘ladi. { a11x1+a12x2+...+a1nxn= b1 a21x1+a22x2+...+a2nxn=b2 … … … … … … … … … … … … … … an1x1+an2x2+...+annxn= bn ko‘rinishdagi tenglamalar sistemasini qaraymiz. Quyidagi belgilashlarni kiritamiz A= ( a11 a12 … a1n a21 a22 … a2n … … … … an1 an2 … ann ) X= ( x1 x2 … xn ) ,B= ( b1 b2 … bn ) Natijada yuqoridagi tenglamalar sistemasi quyidagi matritsaviy tenglamaga teng kuchli bo‘ladi A  X  B . Kramer usulidan ma’lumki, agar det( A )  0 bo‘lsa, sistema yagona yechimga ega. Bundan tashqari, det( A )  0 ekanligi A matritsaning teskarilanuvchi bo‘lishini bildiradi. Yuqoridagi matritsaviy tenglamaning ikkala tomonini chapdan A−1 ga ko‘paytirsak, A−1⋅A⋅X = A−1⋅B⇒ E⋅X = A−1⋅B⇒ X = A−1⋅B ekanligi kelib chiqadi. Demak, tenglamalar sistemasining yechimi X= A−1⋅B ko‘rinishida bo‘ladi. Chiziqli tenglamalar sistemasini yechishning ushbu usuli teskari matritsa usuli deb ataladi. 2.bob Ch i zi q li t engla ma lar siste m asi n i n g manfiy m a s va parallelepipeddagi yechimlarini aniqlash. 2.1 - § . Chiziqli tenglmalar sistemasining manfiymas yechimlar Ushbu aj1x1+aj2x2+...+ajnxn= bj j=1,n (2.1.1) t e ng la m alar siste m asini m a n f i y b o ʻ l m agan, y a ’ ni x1≥0,x2≥0,...,xn≥0 (2.1.2) shartni q a noat an ti r u vchi y ec h i m la r i ni i z l as h b ilan shug ʻ ulla n a m iz. Ravshanki, (2.1) s i s t e m a n i n g h ar bir t e ng l a m asi n ing chap to m oni bj dan katta va kichik b o l ʻ m a s a, u ho l da u bj g a t e n g bo l ʻ a d i . D e m ak, (2.1) s i s t e m a n i n g y echi m ga ega b o li ʻ s hi u c hun aj1x1+aj2x2+...+ajnxn≥bj (j=1,n ) aj1x1+aj2x2+...+ajnxn≤bj (2.1.3) tengsiz l iklar siste m asining birg a li k da bo ʻ lish i ga bog ʻ liq. ( 2.1.3 ) S i ste m ani aj1x1+aj2x2+...+ajnxn≥ bj (2.1.4) −aj1x1−aj2x2−...−ajnxn≥−bj deb h am y o zish m u m ki n. Endi (2.1.1) sist e m aning m a n f i y b o ʻ l m agan y echi m lari m avjudl i gi t a l a b q ili n g a ni uc h un b u s ha r t aj1x1+aj2x2+...+ajnxn≥ bj −aj1x1−aj2x2−...−ajnxn≥−bj x1≥0,x2≥0,...,xn≥0 (2.1.5) s iste m an i n g bi r g a l ik da bo ʻ lishiga o lib kela d i. Shunday qili b , (2. 1.1 ) si s te m a manfiy bo’lmagan yechimlarga ega bo’lsa,(2.1.5) sistema birgalikda bo’ladi va aksincha (2.1.5) sistemaning birgalikda ekanligidan (2.1.1) sistemaning manfiy bo’lmagan yechimlari mavjudligi kelib chiqadi. 2.2 - § . Chiziqli tenglamalar sistemasining manfiymas yechimlari mavjudligini simpleks usulda aniqlash. Chiziqli tenglamalar sistemasining manfiymas yechimlari mavjudligini simpleks usulda aniqlash. “Simpleks” so’zi n o’lchovli fazodagi n+1 uchga ega bo’lgan oddiy qavariq ko’pyoqni ifodalaydi.Simpleks bu ∑ k=1 n x≤1 ko’rinishdagi tengsizliklarning yechimlari sohasidir. Bu usul yordamida chekli qadamlarda optimal yechimlarini toppish mumkin. Lemma {c ¿ x→max ¿{Ax=b¿¿¿¿ (2.2.6) masalaning planlar (rejalar) to’plami bo’sh bo’lmasligi uchun −e¿xu→ max, Ax +xn= b, x≥0, xu≥0 (2.2.7) masalaning optimal plani {x¿,xn¿} da xn¿ ning nol bo’lishi zarur va yetatlidir. Quyidagi misolning manfiymas yechimlarini simpleks usulda topamiz. Misol. 2.2.1 {¿{¿{¿{¿¿¿¿ x1+x2≥1 x1+ x3 3 ≤1 x1≥0 x2≥0 Masalaning simpleks usuldan foydalanib yechish uni kanonik ko’rinishga keltiramiz. {x1+x2−x3=1¿{ x1+ x2 3 +x4=1¿{xi≥0¿¿¿¿ − x5− x6→ max Koordinatalar sistemsida ushbu misolni tasvirlasak quyidagicha. Natijada chiziqli programmalash masalasining birinchi fazasi masalasi quyidagicha ko’rinishga ega bo’ladi. − x5− x6→ max {x1+x2−x3+x5=1¿¿¿¿ ¿ ¿ Bu masalaning boshlang’ich basis plani sifatida x=(0,0,0,0,1,1 ) olamiz. c=(0,0,0,0 ,−1,−1) bo’ladi. Boshlang’ich bazis sifatida matritsaning 5- va 6- ustularini olamiz. Simpleks usul qoidalaridan foydalanib quyidagi jadvalni tuzamiz. 0 0 0 0 -1 -1 C5=−1 a5 1 1 1 -1 0 1 0 1 C6=−1 a6 1 1 1/3 0 1 0 1 1 Δ -2 -4/3 1 -1 0 0 Bu jadvaldan ko’riniib turibdiki boshlang’ich basis plani optimallik emas ekan. Shu sababli basis indeksdan 5 ni chiqarib, o’rniga 1 ni kiritamiz. Natijada quyidagi jadvalga ega bo’lamiz. 0 0 0 0 -1 -1 C1=0 a1 1 1 -1/3 -1 0 1 0 1 C6=0 a6 1 0 -2/3 1 1 -1 1 Δ 0 0 -1 -1 2 0 Yangi bazis plan X=(1;0;0;0;0;1) . Bu jadvaldan ko’rinib turibdiki bu bazis plani optimal emas ekan. Shu sababli bazis indeksdan 6 ni chiqarib, o’rniga 3 ni kiritamiz. Natijada quyidagi jadvalga ega bo’lamiz. 0 0 0 0 -1 -1 C1=0 a1 1 1 1/3 0 1 0 1 C3=0 a3 1 0 -2/3 1 1 -1 1 Δ 0 0 0 0 1 1 Shunday qilib uchinchi simpleks jadvalga asosan x=(1,0,0,0,0,0 ) birinchi faza masalasining optimal plani ekanligi kelib chiqadi. Bu planning 5,6 koordinatalari qiymatlari nolga teng. Demak x=(1,0,0,0,0,0 ) qaralayotgan masalaning manfiymas yechimidir. 2.3- § . Chiziqli tenglamalar sistemasini parallelepipedda yechimi mavjudligini aniqlash. Bizga berilgan ushbu a11x1+a12x2+...+a1nxn=b1 a21x1+a22x2+...+a2nxn= b2 (2.3.1) … … … … … … … am1x1+am2x2+...+amn xn= bmn d¿1≤ x1≤d1 ¿,d¿2≤ x2≤d2 ¿,...,d¿n≤ xn≤dn ¿ sistemani qaraylik. Bu sistemani yechish uchun chiziqli programmalash masalasining yechishning adaptiv usulidan foydalanamiz. (2.3.1) ga qo’shimcha sifatida F(x)= c1x1+c2x2+...+cnxn maqsad funksiyani qaraymiz. Hosil bo’lgan masalaning vektor-matritsa shaklini olish uchun belgilashlar kiritamiz; J={1,2 ,...,n} masala o’zgaruvchilari x1,x2,...,xn larning indekslar to’plami I={1,2 ,...,n} b1,b2,...,bm parametrlar indekslar to’plami. x=(x1,x2,...,xn)=(xj,j∈J)=x(J) c=(c1,c2,...,cn)=(cj,j∈J)=c(J) b=(b1,b2,...,bn)=(bj,j∈J)=b(J) d¿= d¿(J),d¿= d¿(J),A= A(I,J)=(aij,i= I,j∈J). Amalda vektorlar ustunlar kabi qatnashadi deb hisoblanadi. Vektor satrni olish uchun transponirlash (shtrix) operatoridan foydalaniladi. Yangi belgilashlar (2.2.1) misolning kompakt shakli quyidagi ko’rinishni oladi. F (x)= c¿x→ max, Ax = b,d¿≤ x≤ d¿ (2.3.2) m,n m<n sonlar (2.2.1) misolning mxn o’lchovini xarakterlaydi. {c,A,b,d¿,d¿} to’plam uning parametrlar jamlanmasini tashkil etadi. (2.3.2) misolning iqtisodiy tavsifiga tayanib uning parametrlariga maxsus nomlar beriladi. c-qiymat vektori, b-resurslar vektori (cheklashlar vektori) , A- xarajatlar matritsasi (uning aj,j∈J ustunlari vektorlari) , d¿,d¿− quyi va yuqori to’g’ri cheklovlar vektorlari. Algoritmning asosiy qismini bayon etishda rangA=m deb hisoblanadi. Umumiy hol adaptiv usulning usulning birinchi fazasida tekshiriladi. X = {x∈Rn:Ax = b,d¿≤ x≤ d¿} to’plam elementi (2.3.2) chiziqli programmalash masalasining plani (rejasi) deb ataladi. Ta’rif-2.3.1 Maqsad funksiya F(x) maksimal qiymatga erishadigan x0 plan (2.3.2) masalaning yechimi yoki optimal plani deb ataladi. Ta’rif-2.3.2 Berilgan E≥0 da x ε plan E optimal (suboptimal) deyiladi, agar u F( x o ¿ − F ( x ε ) ≤ ε tengsizlikni qanoatlantirsa. 1.Tayanch.Tayanch plan. Adaptiv usul kabi to’g’ri va aniq hisoblanadi, ya’ni masalani barcha cheklovlarini aniq qanoatlantiradigan x vektorlar bilan ish ko’radi. x ( 2.3.2) misolning plani bo’lsin. 1) Berilgan planning optimalligini aniqlay olishi; 2) Berilgan planning suboptimalligini aniqlay olishi; 3) Agar berilgan plan x optimal (suboptimal) bo’lmasa undan yaxshiroq x (c¿x ¿c¿x) planga almashtirish vositalarga ega bo’lish lozim. Adaptiv usulda bunday vosita bo’lib tayanch hisoblanadi. Ta’rif-2.3.3 Jon⊂J m indekslar jamlanmasi tayanch deb ataladi, agar aj,j∈Jon vektorlardan tuzilgan P= A(I,Jon) matritsa maxsusmas bo’lsa (det (A(I,Jon)≠0. Shunday qilib Jon tayanch J dagi shunday indekslar minimal birlashmasidan iboratki b vektorning va qolgan komponentlar X= xj,j∈JH= J/Jon ning istalgan qiymatlarida x vektorning xon=(xj,j∈Jon) komponentlari jamlanmasini tanlash bilan asosiy cheklovlarini bajarilishini ta’minlash mumkin. Bu xon vektor xon=Q(b−AHxH),AH=(I,JH),Q=P−1 formula bilan hisoblanadi. Adaptiv usul bilan ishlash jarayonida uning samaradorligini belgilash uchun tayanch rejalar bilan birga o zgaradi. Shunga ko’ra bu usulda almashtrishning ʻ asosiy vosita bo’lib reja va tayanch juftligi hisoblanadi. Ta’rif-2.3.4 Plan va tayanchdan iborat {x,Jon} juftlik tayanch reja deb ataladi. Tayanch reja aynimagan deb ataladi, agar d¿j<xj<dj ¿,j∈Jon bo’lsa. Optimallik kriteriyasi. {x,Jon} tayanch plan bo’lsin. u'=Con'Q shu vektor potensiallik vektori deb ataladi. Uning yordamida planning xj,j∈J komponentalari baholari deb ataladigan Δj=u'aj−cj,j∈J sonlar hisoblanadi.Tuzulishiga ko’ra Δon= (Δj,j∈ Jon )= 0 . Baholar yordamida maqsad funksiyasining orttirmasi uchun quyidagi formulaga ega bo’lamiz. ΔF (x)=c'x−c'x=c'Δx =− ∑ j∈JH ΔjΔx j (2.3.2) Bu yerda x= x+Δx psevdoplan Ax=b Bundan baholarning fizik ma’nosi kelib chiqadi. Δk - agar kelgan tayanch bo lmagan kompanentalar oldingi qiymatlarini saqlagan, tayanchlari esa A ʻ x  b cheklov bajariladigan bo’lib o’zgaradigan bo’lsa, x planning k - tayanch kompanenti oshganda F(x) maqsad funksiyasi o zgarish tezligining teskari ishora ʻ bilan olinganiga teng bo’ladi. Optimallik kriteriysi. {x,Jon} tayanch plan, Δ=(Δj,j∈J) mos baholar vektori bo’lsin. x rejalarning optimal bo lishi uchun ʻ Δj≥0 da xj=d¿j; Δj≤0 da xj=dj ¿; Δj=0 da d ¿j< x j< d j ¿ j∈JH munosabatlarning bajarilishi yetarli. {x,Jon} -aynimagan tayanch plan bo’lsa, (2.3.4) munosabatlarning bajarilishi x planning optimal bo’lishi uchun zarur hamdir. Ta’rif-2.3.5. (2.3.4) munosabat bajariladigan {x0,Jon0} juftlik optimal tayanch reja deb ataladi. Suboptimallik kriteriysi. {x0,Jon0} - tayanch plan, Δ− unga mos baholar vektori bo’lsin. Tayanch plan bilan JH= J¿on to’plamning JH+,JH− to’plamlari berilgan deb hisoblaymiz. JH+= {j∈ JH:Δj≥ 0},JH−= {j∈JH:Δj≤ 0,JH+∩ JH−= Θ JH+∪ JH−= JH (2.3.5) Ta’rif-2.3.6. ℘ vektor Jon tayanchga mos keluvchi psevdoplan deb ataladi. Agar: ℘j=¿{d¿j,j∈JH + ;¿¿¿¿ (2.3.6) ℘on=Q(b−A(I,JH)℘H) O ’ rinli bo ’ ladi . 1- ta ’ rifga ko ’ ra psevdoplan tayanchmas kompanentlari opt i mallik kriteriysi ni qanoatlantiradi va unda maqsad orttirmasi maksimal qiymatga ega bo ladi. ʻ max, ΔF (x)= ∑ j∈JH Δ j(xj−℘ j)= Δ'H(xH−℘ H) d¿j≤ xj≤dj ¿ j∈JH . 2.4- § . Misollar. Quyidagi tenglamalar sistemasini qaraymiz. 1-misol {y1+y2=3−α¿¿¿¿ 0≤ y1≤ 6,0 ≤ y2≤ 6 parallelepipedda bu sistema yechimi mavjudligini aniqlaymiz. Bu yerda α− parametr. Sistemani y1 va y2 ga nisbatan Kramer usulidan foydalanib yechamiz. Determinantini hisoblab olamiz. Δ=|1 1 1 −1 |=−1−1=−2 , Δ≠0 Δy1= |3−x 1 3+2x −1 | =−3+x−3− 2x=−6− x Δy2=|1 3− x 1 3+2x |=3+2x−3+x=3x Δy1,Δy2 larni topib oldik endi y1 va y2 topamiz. y1= Δy1 Δ = − 6− x − 2 = 6+x 2 ; y2= Δy2 Δ = 3x −2 =−3x 2 Bu yerdan parametrlar chegarasini aniqlaymiz. { 0≤ 6+x 2 ≤6¿¿¿¿ {−6≤x≤6¿¿¿¿ Demak, berilgan sistema α parametrning [−4;0] kesmadagi qiymatlarida talab etilgan parallelepipedda yechimga ega bo’ladi. 2-misol. Quyidagi tenglamalar sistemasi berilgan bo’lib {y1+y2=6¿¿¿¿ 0≤ y1≤5 0≤ y2≤5 parallelepipedda yechimi mavjud yoki mavjud emasligini adaptiv usuldan foydalanib aniqlaymiz. Dastlab masalaning parametrlarida boshlang’ich vektorini olish uchun yordamchi masala (birinchi faza masalasi) ko’riladi. Ya’ni −∑ i=1 m xn+1→ max, A(i,J)x+αin+i=bi,i=1,m ; d¿≤ x≤d∗,0≤ xn+i≤|ωi|,i=1,m Bu yerda αin+i=¿{1,ω≥0¿¿¿¿ ushbu masalani shakllantiramiz. − y3− y4→ max y1+y2+y3=6 y1− y2− y4=−3 0≤ y1≤ 5,0 ≤ y2≤ 5,0 ≤ y3≤ 6,0 ≤ y4≤ 3. Bu masalaning boshlang’ich plani sifatida y'=(0;0;6;3) bozhlang’ich bazis sifatida Jon= {3,4 } ni olamiz. Aon=( 1 0 0 −1) , Aon −1= 1 det A AT=( 1 0 0 −1) . Baholar vektorini hisoblaymiz. Δn '=(−1;−1)( 1 0 0 −1)( 1 0 0 −1)−(0;0)=(0;−2). y'=(0;0;6;3) Planni optimallikka tekshiramiz. Δ1= 0,y1=0− bajariladi . Δ1=− 2,y2=0−bajarilmaydi . Psevdoplan va yangi planni quramiz; ℘ =( 1 0 0 − 1)[( 6 − 3)−( 1 1 1 − 1)( 0 5)]= ( 1 0 0 − 1)[( 6 − 3)− ( 5 − 5)]= ( 1 0 0 − 1)( 1 2)=( 1 − 2) ℘=(0;5;1;−2) l=℘−x=(0,5,1 ,−2)−(0,0,6,3 )=(0,5 ,−5,−5) θ 3 = 0−6 5 = −6 5 ; θ 4 = 0 − 3 − 5 = 3 5 θ 0 = min { 1 , θ 3 , θ 4 } = 3 5 j0={4} y=(0,0,6,3 )+3 5(0,5 ,−5,−5)=(0,3,3,0 ). Tayanchni o’zgartirish uchun tegishli hisoblashni amalga oshiramiz; Δδ on'=(Δδ 3,Δδ 4)=(0,1 ), Δδ n '=(0,1 )( 1 0 0 −1)=(0,1 ) Jn+={1} Jn −={2} δ1=0,δ2=−2 A'y=c,A'Δy =0 A'Δy n+AΔ 'Δy n= 0 Yangi tayanch Jon={2,3 }. bu tayanch yordamida baholar vektorini hisoblaymiz va yangi planni (0;3;3;0) optimallikka tekshiramiz. Jon={2,3 }. ( 1 1 −1 0),( 0 −1 1 1 ) Δn '=(0,1 )( 0 −1 1 1 )( 1 0 1 −1)−(0,1 )=(−1,−1)( 1 0 1 −1)−(0,−1)=(−2,−1)−(0,−1)=(−2,0 ) Δ1=− 2,y1=0−bajarilmaydi . Δ4=0,y4=0−bajariladi . Psevdoplan va yangi planni quramiz. ℘=(℘1,℘2,℘3,℘4)=(5,℘2,℘3,0) ( ℘ 2 ℘ 3)=( 0 −1 1 1 )[( 6 − 3)−( 1 0 1 − 1)( 0 5)]=( 0 − 1 1 1 )[( 6 − 3)− ( 5 5)]= ( 0 − 1 1 1 )( 1 − 8)=( 8 − 7) ℘=(5,8 ,−7,0 ) l=(5,8 ,−7,0 )−(0,3,3,0 )=(5,5 ,−10 ,0) θ2= 2 3 , θ3=0 Qadam nol bo’lganligi sababli plan o’zgarmaydi. Tayanchni o’zgartirish uchun tegishli hisoblashni amalga oshiramiz; Δδ on'=(Δδ 2,Δδ 3)=(0,1 ), Δδ n '=(Δδ 1,Δδ 4)= Δδ on 'Aon −1An=(0,1 )( 1 1 1 −1)=(1,−1) σ1=∞ , σ4=0 Yangi tayanch Jon= {2,4 }. Bu tayanch yordamida baholar vektorini hisoblaymiz va yangi planni optimallikka tekshiramiz. Psevdoplan va yangi planni quramiz. ℘=(℘1,℘2,℘3,℘4)=(0,6,0 ,−3) l=(0,3 ,−3,−3) θ 2 = 5 − 3 3 = 2 3 , θ4=0 Tayanchni o’zgartirish uchun tegishli hisoblashlarni amalga oshiramiz. (Δδ 2,Δδ 4)=(0;1) (Δδ 1,Δδ 3)=(−1;−1) σ1=2,σ4=2 Yangi tayanch Jon={1,2 }. Bu tayanch yordamida baholar vektorini hisoblaymiz va (0;3;3;0) planni optimallikka tekshiramiz. Δ3=1,y1=3−bajarilmaydi . Δ4=1,y4=0−bajariladi . Psevdoplan va yangi planni quramiz. ℘=(℘1,℘2,℘3,℘4)=(1,5 ;4,5 ;0;0) l=(1,5 ;4,5 ;−3;0) θ 1 = 10 3 , θ 2 = 4 3 θ =min {1;10 3 ;4 3}=1 y=(0;3;3;0)+( 3 2;3 2;−3;0)=( 3 2;9 2;0;0) Bu plan uchun optimallik kriteriysi bajariladi. Demak {y1+y2=6¿¿¿¿ Tenglamalar sistemasining 0≤ y1≤5 0≤ y2≤5 Parallelepipedda yechimi mavjud ekan. y=( 3 2;9 2;0;0)

Mavzu: Parametrga bog’liq chiziqli tenglamalar sistemasini yechish algoritmi. MUNDARIJA. 1.bob.Umumiy tushunchalar.Tenglamalar sistemasini yechish usullari. 1.1 - § . Chiziqli tenglamalar sistemasi. Kroneker-Kapelli teoremasi 1.2 - § . Chiziqli tenglamalar sistemasini yechishning Kramer usuli. 1.3 - § .Chiziqli tenglamalar sistemasini yechishning Gauss usuli. 1.4 - § . Chiziqli tenglamalar sistemasini Teskari matritsaviy usuli. II.Chiziqli tenglamalar sistemasining manfiymas va parallelepipeddagi yechimlarini aniqlash. 2. 1 - § .Chiziqli tenglamalar sistemasini manfiymas yechimlarini aniqlash. 2.2 - § .Chiziqli tenglamalar sistemasining manfiymas yechimlari mavjudligini simpleks usulda aniqlash. 2.3 - § . Chiziqli tenglamalar sistemasini parallelepipedda yechimi mavjudligini aniqlash. 2.4 - § . Misollar III. Parametrga bog’liq bo’lgan chiziqli tenglamalar sistemasi yechimlar to’plamining parametrning barcha qiymatlarida bo’sh yoki bo’sh emasligini aniqlash algoritmi. 3.1 - §. Kesmada berilgan parametrga bog’liq bo’lgan chiziqli tenglamalar sistemasining parametrning barcha qiymatlarida yechimini yoki mavjud emasligini aniqlash algoritmi. 3.2 - §. Parallelepipedda berilgan parametrga bog’liq bo’lgan chiziqli tenglamalar sistemasining parametrning barcha qiymatlarida yechimi mavjud yoki mavjud emasligini aniqlash algoritmi. 4.bob . Misollar. 1.Foydalanilgan adabiyotlar. 2. Xulosa.

I-BOB 1.Chiziqli tenglamalar sistemasi. Bizga m ta tenglamadan iborat n ta noma’lumli chiziqli tenglamalar sistemasi berilgan bo‘lsin: {a 11 x 1 +a 12 x 2 +...+a 1n x n =b 1¿{a 21 x 1 +a 22 x 2 +...+a 2n x n =b 2¿{.........................................¿¿¿¿ (1) bu yerda, x1,x2,..,xn noma’lumlar. Tenglamalarni birinchi, ikkinchi, va hokazo m- tenglama deb nomerlab chiqilgan deb hisoblaymiz. aij koeffitsient i- tenglamadagi xj noma’lumning koeffitsientini, bi esa i-tenglamaning ozod hadi. Noma’lumlar oldidagi koeffitsientlarni m ta satr va n ta ustundan iborat matritsa ko‘rinishida yozish mumkin: A= ( a11 a12 ... a1n a21 a22 ... a2n ... ... ... ... am1 am2 ... amn ) ) ) ¿ ) (2) Ushbu matritsa chiziqli tenglamalar sistemasining asosiy matritsasi deyiladi. Quyidagi ¯A matritsa esa chiziqli tenglamalar sistemasining kengaytirilgan matritsasi deyiladi: A = ( ¿ ¿ a11 a12 ... a1n b1 a21 a22 ... a2n b2 ... ... ... ... ... am1 am2 ... amn bm ¿ ) ) ) ) ¿ )¿ (3) Agar (1) sistemaning barcha ozod hadlari 0 ga teng bo‘lsa, u holda (1) sistema bir jinsli tenglamalar sistemasi deb ataladi. Agar (1) sistemada m=n bo‘lsa, u holda ushbu sistema n - tartibli sistema deyiladi. Yechimga ega bo‘lgan chiziqli tenglamalar sistemasi birgalikda deyiladi. Masalan, ixtiyoriy bir jinsli tenglamalar sistemasi birgalikda bo‘ladi, chunki barcha

noma’lumlarni 0 ga teng qilib olinsa, u bir jinsli tenglamalar sistemasining yechimi bo‘ladi. Yagona yechimga ega bo‘lgan sistema aniq sistema, bittadan ortiq yechimga ega bo‘lgan sistema aniqmas sistema deyiladi. 1.1 - § Bir jinsli tenglamalar sistemasi. Kroneker-Kapelli teoremasi. Ushbu mavzuda chiziqli tenglamalar sistemasini umumiy yechimini topish usulini beramiz. Dastlab, bir jinsli tenglamalar sistemasini qaraymiz. Bizga {a 11 x 1 +a 12 x 2 +...+a 1n x n =0¿{a 21 x 1 +a 22 x 2 +...+a 2n x n =0¿{........................................¿¿¿¿ (1.1.1) bir jinsli tenglamalar sistemasi berilgan bo‘lsin. Ma’lumki, ushbu sistemaning matritsasini A va matritsaning ustunlarini v1,v2,...,vn deb olsak, sistemani x1v1+x2v2+...+xnvn=0 yoki A ¿X=0 ko‘rinishlarda ham yozish mumkin, bu yerda X  noma’lumlardan iborat bo‘lgan ustun vektor. 1-tasdiq. Agar Z1,Z2,...,Zk ustunlar bir jinsli chiziqli tenglamalar sistemasining yechimi bo‘lsa, u holda ularning ixtiyoriy chiziqli kombinatsiyasi ham yechim bo‘ladi. Isbot. Haqiqatdan ham, A⋅Zi= 0 ekanligidan A⋅(c1Z1+c2Z2+...+ckZk=c1A⋅Z1+c2A⋅Z2+...+ckA⋅Zk=0 kelib chiqadi. 1.1.1-teorema. Bir jinsli chiziqli tenglamalar sistemasining ixtiyoriy yechimi n -r ta chiziqli erkli yechimlarning chiziqli kombinatsiyasidan iborat bo‘ladi, bu yerda n  noma’lumlar soni, r= rang(A). Isbot. Sistemani

x1v1+x2v2+...+xnvn=0 ko‘rinishida yozib olaylik. r =rang(A) ekanligi uchun v1,v2,...,vn ustunlar jamlanmasida r ta ustun bazis bo‘ladi. Umimiylikka ziyon yetkazmagan holda, dastladki r ta v1,vr,...,vr ustunni bazis deb olish mumkin. Bu holda qolgan vr+1,vr+2,...vn ustunlar v1,v2,...vr ustunlarning chiziqli kombinatsiyasi orqali ifodalanadi, ya’ni vr+1=br+11v1 + br+12v2+… br+1rvr v r + 2 = b r + 21 v 1 + b r + 22 v 2 + … b r + 2 r v r ………………………………………… vn=bn1v1 + bn2v2+… bnrvr. u tengliklardan quyidagi n  r ta ustunning yechim ekanligini ko‘rish qiyin emas, Z r + 1 = ( b r + 11 … … … b r + 1 r − 1 0 … . 0 ) , Z r + 2 = ( b r + 21 … … … b r + 2 r 0 − 1 … … .. 0 ) ,………. Z n = ( b n 1 … … … b nr 0 0 … . 1 )  yechimlar chiziqli erkli ekanligi osongina kelib chiqadi, chunki bu ustunlarning oxirgi n  r ta komponentalaridan tuzilgan minorni qarasak, ushbu minor noldan farqli bo‘ladi. Endi ixtiyoriy yechim bu yechimlar orqali chiziqli ifodalanilishini ko‘rsatamiz. Aytaylik, X= ( x 1¿ , … . , x r¿ , x r + 1 ,¿ … … x n¿ ) ustun sistemaning boshqa bir yechimi bo‘lsin. U holda Y=X+ xr+1¿ Zr+1+...+xn¿Zn ustun ham sistemaning yechimi bo‘ladi. Ma’lumki, bu yechimda ( r  1)-komponentadan boshlab barcha komponentalar nolga teng, ya’ni Y= y 1¿ , … . , y r¿ , 0 … … 0 ) Ushbu ustun sistemaning yechimi bo‘lganligi uchun y 1¿ v 1 + y 2¿ v 2 +…….. + y r¿ v r =0 Ammo, v 1 , v 2 , … .. , v r ustunlar chiziqli erkli ekanligidan ¿y1 ¿ = y2¿ =…….. ¿yr¿ =0 kelib chiqadi. Demak, Y  0, ya’ni X=− xr+1¿ Zr+1−...− xn¿Zn

Ko'chirib oling, shunda to'liq holda ko'ra olasiz

O'xshashlar

Chiziqli tenglamalar sistemasini yechish
Chiziqli tenglamalar sistemasini yechish usullari
Chiziqli differensial tenglamalar sistemasini matritsaviy usulda yechish
C++ da chiziqli tenglamalar sistemasini yechish dasturini ishlab chiqish
CHIZIQLI TENGLAMALAR SISTEMACINI YECHISH