Parametrga bog’liq chiziqli tenglamalar sistemasini yechish algoritmi.
![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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_1.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_2.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_3.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_4.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_5.png)
![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)](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_6.png)
![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:](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_7.png)
![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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_8.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_9.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_10.png)
![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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_11.png)
![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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_12.png)
![{
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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_13.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_14.png)
![−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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_15.png)
![{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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_16.png)
![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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_17.png)
![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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_18.png)
![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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_19.png)
![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.](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_20.png)
![{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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_21.png)
![Δ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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_22.png)
![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;](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_23.png)
![Δδ 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](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_24.png)
![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¿¿¿¿](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_25.png)
![Tenglamalar sistemasining 0≤ y1≤5
0≤ y2≤5
Parallelepipedda yechimi mavjud ekan.
y=(
3
2;9
2;0;0)](/data/documents/95d6b006-7eeb-415e-bfe9-e116fac04dae/page_26.png)
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