Sun’iy bazis vektor usuli va chiziqli programmalash masalalarini sonli yechishga qo’llash.
![MAVZU: Sun’iy bazis vektor usuli va chiziqli programmalash
masalalarini sonli yechishga qo’llash.
MUNDARIJA
Kirish………………………………………………………………….………..3
I-BOB. CHIZIQLI PROGRAMMALASHTIRISH MASALASI……….………4
1.1. Asosiy tushunchalar . Chiziqli programmalashtirish
masalasining qo`yilishi ................................................................. 4
1.2. Chiziqli dasturlash masalalarining matematik modeli…9
II-BOB. Chiziqli programmalashtirish masalasining yechimlari haqida………12
2.1. Sun’iy bazis vektor usuli………………………………...14
2.2. Chiziqli modellarga misollar…………………………….17
2.3. Chiziqli programmalashtirish masalasining geometrik
talqini. Masalani grafik usulda yechish…………………19
XULOSA……………………………………………………………………………..22
FOYDALANILGAN ADABIYOTLAR RO’YXATI…………………………..…23](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_1.png)
![KIRISH
Fan va texnikaning jadal rivojlanishi, ishlab chiqarishni boshqarishning
murakkablashishi va uni rejalashtirishga qo`yiladigan talablarning ortishi bozor
iqtisodini rivojlanishlarini tavsiflovchi omillardan hisoblanadi. Bunday sharoitda
iqtisodni boshqarishga ilmiy yondoshish, matematik usullarni keng qo`llash, ayniqsa,
matematik programmalashtirishning aniq usullaridan foydalanish zaruratga aylandi.
Zamonaviy kompyuter texnologiyasidan keng foydalangan holda, matematik
programmalashtirish va optimallashtirish usullarini iqtisodiy izlanishlar va
rejalashtirishda qo`llash muhim bo`lib qoldi. M а t е m а tik pr о gr а mm а l а sh va
optimallashtirish usullari pr е dm е ti k о r хо n а , firm а , qurilish, qishloq xojaligi, b о z о r,
ishl а b chiq а rish birl а shm а si, ха lq х o’j а lik t а rm о ql а ri, umuman olganda, butun ха lq
х o’j а ligig а d о ir iqtis о diy j а r а yonl а rni t а svirl о vchi m а t е m а tik m о d е ll а rni tuzish va
ularga tegishli usullarni qo’llab yechishdan ib о r а t. M а t е m а tik m о d е ll а r ko’p
d а vrl а rd а n buyon iqtis о diyotd а ishl а tilm о qd а . M а s а l а n, iqtis о diyotd а qo’ll а nilg а n 1-
m о d е l – F.K е n е t о m о nid а n yar а tilg а n t а kr о r ishl а b chiq а rish m о d е lidir. «Iqtis о diy
m а s а l а ning m а t е m а tik m о d е li» d е g а nd а bu m а s а l а ning а s о siy sh а rtl а ri v а
m а qs а dining m а t е m а tik f о rmul а l а r yord а mid а ifodalanishiga а ytil а di.
Optimallashtirish usullari yordamida ekstremal iqtisodiy masalalarni yechishni to`rt
bosqichga bo`lish mumkin: masalani chuqur o`rganib, unga tatbiq qilish mumkin
bo`ladigan usullarni tanlash, masalada qo`yilgan shartlarga asoslanib matematik model
tuzish; - agar masalaning shartlari maqsadga muvofiq kelsa, tegishli matematik usulni
qo`llab, optimal yechimni topish; - yechimni iqtisodiy tahlil qilish va uni amaliyotga
«imkoni boricha» tatbiq etish; - amaliyotda matematik programmalashtirish va
optimallashtirishning taqribiy usullaridan foydalanish haqida tushunchalar berish.
Matematik programmalashtirish va optimallashtirish usullari masalalari chiziqli,
chiziqsiz hamda dinamik programmalashtirishga bo`linib, umumiy holda ekstremal
masalalarni yechishda qo`llaniladi. Ko`rsatilgan funksiyalardan hech bo`lmasa bittasi
chiziqli bo`lmagan funksiya bo`lsa, masala chiziqsiz programmalashtirish masalasidan
iboratdir.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_2.png)
![I-BOB. CHIZIQLI PROGRAMMALASHTIRISH MASALASI
1.1. Asosiy tushunchalar . Chiziqli programmalashtirish masalasining
qo`yilishi
Chiziqli dasturlash matematik dasturlashning bir bo’limi bo’lib, bunda
o’zgaruvchilariga chiziqli cheklashlar qo’yilgan chiziqli funksiyaning ekstremal
(maksimal yoki minimal) qiymatini topish masalalari va ularni yechish usullari
o’rganiladi. Chiziqli cheklashlar tengliklar yoki qa’tiy bo’lmagan tengsizliklar
ko’rinishida bo’lishi mumkin.
Chiziqli dasturlash masalalarini sistemalashtirish va ularni yechish uchun
umumiy, universal usul yaratish ustida L.V.Kantorovich 1939 yildan boshlab
shug’ullangan. Amerikalik olim J.Dansig tomonidan XX asrning 40- yillarida
simpleks-usul deb ataluvchi usul yaratildi va chiziqli programalashtirish nazariyasi
hamda uning qo’llanilishi tez suratlar bilan rivojlandi. «Chiziqli dasturlash»
iborasini birinchi bo’lib 1951 yilda J.Dansig va T.Kupmans kiritishgan.
Chiziqli dasturlash masalasining matematik modeli umumiy ko’rinishda
quyidagicha ifodalanadi:
, o’zgaruvchilarning shunday qiymatlari topilsinki,
, , va , shartlar bajarilsin
hamda funksiya maksimal (yoki minimal) qiymat qabul qilsin, bunda
.
Chiziqli dasturlash masalasining matematik modelidagi ,
shartlar (manfiymaslik shartlari), ba’zan, qisman yoki butunlay qatnashmasligi
mumkin.
Chiziqli programmalashtirish chiziqli funksiyaning eng katta va eng
kichik qiymatini o`zgaruvchilarga nisbatan chiziqli chegaraviy shartlar qo`yilgan
holda aniqlash bilan shug`ullanadi. Shuning uchun, chiziqli programmalashtirish
masalalari funksiyaning shartli ekstremum masalalari qatoriga kiradi. Lekin
chiziqli programmalashtirish masalalari ko`p o`zgaruvchili bo`lgani uchun
matematik analizdagi funksiya ekstremumini aniqlashning klassik usulini
to`g`ridan-to`g`ri qo`llash mumkin emas. Shuning uchun chiziqli
programmalashtirish masalalarini yechishning maxsus usullari ishlab chiqilgan.
Ular yordamida, ko`pgina masalalarni, ayniqsa, iqtisodiy masalalarni yechish
maqsadga muvofiq.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_3.png)
![1.2. Chiziqli dasturlash masalalarining matematik modeli. Ma’lumki,
ishlab chiqarish haqidagi masalaning matematik modeli quyidagi ko’rinishda
bo’ladi:
.
Bu model chiziqli dasturlash masalasi matematik modelining bir ko’rinishi
bo’lib, undagi , shartlar masalaning asosiy shartlari,
, shartlar esa, to’g’ri (bevosita) shartlari deb ataladi. Maksimal
qiymat qabul qilishi kerak bo’lgan chiziqli fuknsiya esa, masalaning
maqsad funksiyasi deb ataladi.
Ba’zi chiziqli dasturlash masalalarining asosiy shartlari tenglamalar
ko’rinishida yoki ulardagi tengsizliklar « » ko’rinishda bo’lishi mumkin, xullas,
asosiy shartlar tenglamalar va tengsizliklar sistemasini tashkil etadi.
Vektor-matrisa yozuvidan foydalanib chiziqli dasturlash masalasining
matematik modelini quyidagi ko’rinishida ham ifodalash mumkin:
,
bunda , , – vektorlar, matrisa,
(') belgi esa transponirlash amalini anglatadi.
Bu yerda matrisa va vektorlar ustida amallar amaldagi qoidalarga binoan
bajariladi. Yozuvlarda uchraydigan vektorlar vektor-ustun deb tushuniladi, vektor-
satrni hosil qilish uchun esa, transponirlash amali qo’llaniladi. Shuning uchun, c va
x vektorlarning skalyar ko’paytmasi ko’rinishda yoziladi. Biror x vektor uchun
yoki ko’rinishdagi yozuv uning har bir komponentasi ko’rsatilgan
shartga bo’ysunishini anglatadi. Shuni ham ta’kidlash kerakki, ba’zan, yozuvda
transponirlash belgisi (') tushirib qoldirilishi mumkin.
Chiziqli dasturlash masalasining yuqoridagi yozuvida qatnashgan
parametrlarga ishlab chiqarish haqidagi masalaning mohiyatidan kelib chiqqan
holda nomlar ham berilgan: x – rejalar vektori, s – baholar (narxlar) vektori, b –](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_4.png)
![shartlar vektori, A – shartlar yoki xarajatlar matrisasi. A matrisaning ustunlarini esa
shartlar vektorlari deb atashadi.
Agar chiziqli dasturlash masalasining matematik modeli yuqoridagi
ko’rinishga ega bo’lsa, u normal ( standart, tabiiy, simmetrik ) shaklda yozilgan
deb hisoblanadi.
Agar chiziqli dasturlash masalasining asosiy shartlari faqat tenglamalardan
iborat bo’lsa, ya’ni uning matematik modelil
,
ko’rinishda bo’lsa, u holda chiziqli dasturlash masalasi kanonik shaklda yozilgan
deyiladi.
Bulardan tashqari, chiziqli dasturlash masalasi matematik modelini yozish
uchun boshqa shakllar ham mavjud, masalan, umumiy shakl.
Isbotlash mumkinki, ixtiyoriy ko’rinishda yozilgan chiziqli dasturlash
masalasini, sodda matematik almashtirishlar yordamida, unga ekvivalent bo’lgan
boshqa ixtiyoriy ko’rinishdagi chiziqli dasturlash masalasiga keltirish mumkin.
Buning uchun, odatda, quyidagi almashtirishlar qo’llaniladi.
1. Tengsizlikning ishorasini teskarisiga almashtirish: « » ko’rinishdagi
tengsizlikning ikkala tomoni ishorasini teskarisiga almashtirib, “ ”
ko’rinishdagi tengsizlikka va, aksincha, “ ”ni “ ”ga keltirish mumkin.
2. Tengsizlikni tenglamaga «aylantirish» mumkin:
,
bunda – qo’shimcha o’zgaruvchi deb ataladi.
3. Agar biror o’zgaruvchiga to’g’ri shart qo’yilmagan bo’lsa, u holda bu
o’zgaruvchini ikkita manfiymas o’zgaruvchilar ayirmasi shaklida ifodalash
mumkin.
4. Maqsad funksiyasining ishorasini teskarisiga almashtirish yordamida
maqsadni ifodalovchi max ni min ga yoki, aksincha, min ni max ga
almashtirish mumkin.
Chiziqli dasturlash masalasining barcha (asosiy va to’g’ri) shartlarini
qanoatlantiruvchi vektor uning mumkin bo’lgan yechimi yoki
rejai deb ataladi. Barcha mumkin bo’lgan yechimlar birgalikda masalaning
mumkin bo’lgan yechimlari (rejalari) to’plami ni tashkil etadi.
Masalaning maqsad funksiyasiga maksimal qiymat beruvchi
reja (mumkin bo’lgan yechim) uning optimal rejai ( optimal
yechimi ) deb ataladi.
Misol. Quyidagi chiziqli dasturlash masalasi berilgan bo’lsin:](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_5.png)
![( m + M ) V 2
2,
V
,
mv 2
2 = ( m + M )V 2
2
.
Bu masala uchun va
g vektorlar rejalardir,
lekin
α vektor reja bo’la olmaydi, chunki va vektorlar
uchun berilgan masalaning barcha shartlari bajariladi,
V uchun esa asosiy shartlar
bajarilsada, to’g’ri shartlar qisman bajarilmaydi.
M
va M=m+mc rejalar uchun maqsad funksiyasining, ya’ni m
funksiyaning qiymatlarini hisoblaymiz:
m c
, M .
m = M − m c
bo’lgani uchun, reja masalaning optimal yechimi bo’la
olmaydi, chunki maqsad funksiyasiga reja
λ1>>L1 dan katta λ2 qiymat beradi. L2
rejaning optimal reja bo’lishi yoki bo’lmasligini maxsus tekshirib ko’rish kerak.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_6.png)
![2.2. Chiziqli modellarga misollar. Ishlab chiqarish haqidagi masala va
ozuqa qorishmasi haqidagi masala modellari chiziqli modellarga misol bo’la
oladilar.
Energiya sistemasining ish rejimini optimal boshqarish masalasi. Faraz
qilaylik, biror hududni elektr energiyasi bilan ta’minlaydigan bir nechta elektr
stansiyalar ishini boshqarish kerak bo’lsin. Belgilangan vaqt momentida mavjud
aktiv quvvatlarni elektr stansiyalararo taqsimlash masalasini qaraymiz. Bu yerda
taqsimlashni shunday bajarish kerakki, aktiv quvvatlarni generasiya qilishga zarur
yoqilg’i tufayli sarflanadigan umumiy xarajatlar minimal bo’lsin.
Bu masalaning matematik modelini tuzish uchun, avvalo, i - elektr stansiyada
generasiya qilinishi kerak bo’lgan aktiv quvvat miqdorini λ2<<L2 bilan belgilab, bu
miqdor texnik shartlarga ko’ra quyidan va yuqoridan chegaralanganligini
ta’kidlaymiz, ya’ni
t = 0 , M 1(0) . Bundan tashqari, quvvatlar miqdorlari
balansi sharti ham bajarilishi kerak. Quvvatlar miqdorlari balansi sharti deganda
generasiya qilinadigan umumiy quvvat miqdori
M 2(0) elektr quvvatini uzatishdagi
barcha yo’qotishlarni (
t>0 ni) e’tiborga olganda iste’mol qilinadigan quvvat
miqdoriga ( P ga) mos bo’lishi tushuniladi, ya’ni
M1(0)+M2(0)=M1(t)+M2(t) .
Har bir i - aktiv quvvatni generasiya qilishga zarur yoqilg’i tufayli
sarflanadigan xarajatlar
M1(t) ga, ya’ni generasiya qilinadigan aktiv quvvat miqdoriga
bog’liq ekanligi ravshan. Bu xarajatlar, umumiy holda,
M 2(t) funksiya ko’rinishda
ifodalanishi mumkin. Albatta, har bir i uchun
t funksiya turli xossalarga ega
bo’lishi mumkin.
Soddalik uchun,
M 1(t) , M 2( t) , funksiyalar chiziqli deb hisoblanishi
mumkin. Har bir i - aktiv quvvatning 1 birligini generasiya qilishga zarur yoqilg’i
tufayli sarflanadigan xarajatlar miqdorini ga teng deb faraz qilinsa, qo’yilgan
masalaning quyidagi matematik modeliga ega bo’lamiz:
t
Bu matematik model chiziqli dasturlash masalalari sinfiga oid bo ’ lib , u faqat
bitta asosiy shartga va ikki yoqlama to ’ g ’ ri shartlarga ega .](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_7.png)
![2.3. Chiziqli dasturlash masalalarining geometrik ma’nosi
Asosiy qism
1. Masalaning qo’yilishi va geometrik usulda yechish shartlari.
Sodda hollarda, ya’ni chiziqli dasturlash masalasining
o’zgaruvchilari soni uchdan oshmasa uni geometrik tasvirlash va
yechish mumkin. Albatta, hayotda o’zgaruvchilar soni uchdan
oshmagan chiziqli programalashtirish masalalari kam uchrasada,
ular chiziqli programalashtirish masalalarning ko’pchilik xossalari
hamda yechish usullarini tushunishni ancha osonlashtiradi. Chiziqli
dasturlash masalasining geometrik manosini quyidagi jadval uchun
ishlab chiqarish masalasini yechish misolida ko’rib chiqamiz: m=3,
n=2; 1- xom ashyo – ipak ip, 2- xom ashyo – paxta ip, 3- xom
ashyo – bo’yoq; ishlab chiqarilayotgan mahsulotlar – 1- xil О
2 4 6 8 10 12 14246810121416X
2
3x
1 +2x
2 =30x
1 +2x
2 =14 x
2 =5
А
2x
1 +3x
2 =0 BCD
X
12x
1 +3x
2 =25](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_8.png)
![gazlama va 2- xil gazlama.
Zarur xom ashyolar Gazlama xili Xom ashyolarning
umumiy miqdori
1 2
Ipak ip 1 2 14
Paxta ip 3 2 30
Bo’yoq 0 1 5
1 birlik mahsulotdan
olingan daromad 2 3
Bu masalaning geometrik ma’nosini anglash uchun oldin uning matematik
modelini tuzamiz:
2x
1 +3x
2 max, x
1 +2x
2 14, 3x
1 +2x
2 30, 0 x
2 5, x
1 0,
bunda x
1 – 1- xil gazlama va x
2 – 2- xil gazlama miqdori.
2. Mumkin bo’lgan yechimlar to’plamini aniqlash. Tengsizlikda Ox
1 x
2
dekart koordnatalar sistemasini qaraymiz va har bir ( x
1 , x
2 ) juftlikka bu
tengsizlikdan x
1 va x
2 koordinatali nuqtani mos qo’yamiz. Dastlab qaralayotgan
masalaning rejalar to’plamiga mos to’plamini aniqlaymiz. Buning uchun avval
asosiy shartlardan birinchisini tahlil qilamiz: x
1 + 2 x
2 14. Ma’lumki, ikki
o’zgaruvchili bitta tengsizlik tekislikda to’g’ri chiziq yordamida ajratilgan yarim
tengsizliklardan biriga mos keladi (to’g’ri chiziq ham shu yarim tekislikka
tegishli). Yarim tekisliklarning qaysi biri mos ekanligini aniqlash uchun chegarada
(ya’ni to’g’ri chiziqda) yotmagan ixtiyoriy nuqtaning koordinatalarini tengsizlikka
quyib tekshirish kerak. Agar tengsizlik qanoatlantirilsa, o’sha nuqta joylashgan
yarim tekislik shu tengsizlikka mos, aks holda yo’q. O ( 0;0 ) nuqta x
1 +2x
2
14
tengsizlikni qanoatlantiradi: 0+2*0=0<14 . Shuning uchun O nuqtani o’z ichiga
olgan va x
1 +2x
2 =14 to’g’ri chiziq bilan chegaralangan yarim tekislik x
1 +2x
2
14
tengsizlikka mos keladi. Xuddi, shuningdek, asosiy shartlarining boshqa
tengsizliklari bilan ish qilamiz.
To’g’ri shartlarga ham shu usulni qo’llash mumkin. Natijada qaralayotgan
masalalaning rejalar to’plamiga mos to’plam OABCD beshburchak ekanligini
topamiz (u shaklda shtirixlangan). Shuni takidlash keraki, rejair to’plami bo’sh,
bo’shmas va chegaralangan (bizning misolimizdagidek), bo’shmas va
chegaralanmagan bo’lishi mumkin. Agar rejalar to’plami bo’shmas va
chegaralangan bo’lsa, u umuman olganda, kandaydir ko’pyoqliga mos keladi,
ko’pyoqli chegaralangan yoki chegaralanmagan bo’lishi mumkin (agar rejalar
to’plami nuqta, kesma, to’g’ri chiziq, polosa (ya’ni ikki paralell to’g’ri chiziqlar
orasi) bo’lsa ham uni shartli ravishda ko’pyoqli deb qaraymiz). Albatta n=2
bo’lgan holda ko’pyoqli ko’pburchakka aylanadi.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_9.png)
![3. Maqsad chiziqlari. Endi misolni qarashda davom etib, optimal rejani
geometrik usul bilan topishga urinib ko’ramiz. Shartga binoan maqsad funksiyasi,
ya’ni (x
1 ,x
2 )=2x
1 +3x
2 funksiyaga eng katta qiymat beradigan x
1 va x
2 larni
topishimiz kerak. Bu funksiya 2x
1 +3x
2 =
to’g’ri chiziqning barcha nuqtalarida bir
xil (ya’ni
ga teng) qiymat qabul qiladi, bunda qandaydir haqqiy son ni
parametr deb hisoblasak = to’g’ri chiziqlar dastasini hosil qilamiz. Bu to’g’ri
chiziqlar dastasi qiymatlar chiziqlaridir. Biz shu to’g’ri chiziqlar dastasidan
shunday chiziqni ajratishmiz kerakki, u rejalar to’plami OABCD beshburchak bilan
umumiy nuqtalarga ega bo’lsin va
ga eng katta qiymat bersin.
Shakldan ko’rinib turibdiki, 2x
1 +3x
2 =
to’g’ri o’z-o’ziga paralel qilib
c=(c
1 ,c
2 )=(2; 3) normal bo’ylab siljitsak
o’sadi. Demak, bu to’g’ri chiziqni o’z-
o’ziga parallel qilib siljitishni OABCD besh burchak bilan kesishmay qolguncha
davom ettirish maqsadga muvofiqdir. U holda biz B nuqtaga kelib to’xtaymiz. Eni
V nuqtaning koordinatalarini topamiz. Buning uchun 3x
1 +2x
2 =30 va 2x
1 +3x
2 =30
tenglamalarni birgalikda yechamiz: x
1 =8, x
2 =3, B(8; 3).
Shunday qilib, korxona x
1 =8 birlik 1-xil gazlama va x
2 =3 birlik 2-xil
gazlama ishlab chiqarsa eng ko’p, ya’ni
(8; 3)=2*8+3*3=25 birlik daromad
oladi.
4. Asosiy teoremalar. Analitik geometriya kursidan ma’lumki, son o’qida
yotuvchi har qanday nuqta bitta haqqiy son orqali aniqlanadi. Shuning uchun
to’g’ri chiziqni bir o’lchovli chiziqli fazo deb atash mumkin. Tekislikda joylashgan
har qanday nuqta ikkita xaqqiy sonning tartiblangan jufti orqali aniqlanadi.
Shuning uchun tekislik ikki o’lchovli chiziqli fazo deb ataladi. Uch o’lchovli
chiziqli fazodagi har qanday nuqta 3 ta haqqiy sonnig tartiblangan uchligi bilan
aniqlanadi.
Ko’pchilik masalalarda, shu jumladan, iqtisodiy masalarda obyektlarni
xarakterlovchi faktorlar ( n>3 ) ta haqqiy son orqali ifodalanishi mumkin. Har
qanday n ta haqqiy sonning tartiblangan n ligini o’z ichiga olgan to’plamda
qo’shishi va skalyarga ko’paytirish operasiyalari bajarilsa bunday to’plam n
o’lchovli chiziqli fazo deyiladi. n o’lchovli fazoni R n
(ba’zan E n
) bilan belgilash
qabul qilingan.
Agar R n
fazodagi nuqtalar to’plamidan olingan ixtiyoriy ikkita nuqtani
tutashtiruvchi kesma shu to’plamga tegishli bo’lsa, unga qavriq deyiladi.
Isbotlash mumkinki, istalgan sondagi qavariq to’plamlar kesishmasi (bo’sh
bo’lmasa) qavariqdir.
Teorema. Chiziqli dasturlash masalasining rejalari to’plami (bo’sh
bo’lmasa) qavariqdir.
Isboti. Chiziqli dasturlash masalasida faqat ikki xil shartlar mavjud: chiziqli
tengsizliklar va chiziqli tenglamalar. Ma’lumki, chiziqli tenglama fazoda](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_10.png)
![gipertekislikni, tengsizlik esa yarim fazoni ifodalaydi. Har qanday gipertekislik va
har qanday yarim fazo qavariq to’plamlar bo’lgani uchun chiziqli dasturlash
masalsining rejalari to’plami (bo’sh bo’lmasa) qavariq to’plamlar kesishmasi
sifatida qavariqdir. Teorema isbot bo’ldi.
Chekli sondagi gipertekisliklar va yarim fazolar kesishmasi bo’sh bo’lmasa
uni qavrik ko’pyokli deyiladi.
Shunday qilib chiziqli dasturlash masalasining rejalari to’plami qavariq
ko’pyoklidir.
Chiziqli dasturlash masalasi maqsad funksiyaning chiziqli ekanligi va uning
rejalari to’plamining qavariq ekanligi asosida quyidagi teorema o’rinlidir.
Teorema. Agar chiziqli programmallash masalasining maqsad funksiyasi
maksimumga (minimumga) erishtirilayotgan va rejalar to’plamida yuqoridan
(quyidan) chegaralangan bo’lsa, bunday masala optimal yechimga ega.
Biz geometrik usul bilan chiziqli dasturlash masalasini hal qilganda topilgan
optimal yechim OABCD beshburchakning B uchida joylashganligini aniklagan
edik.
Isbotlash mumkinki, chiziqli dasturlash masalasining optimal yechimi uning
rejalari to’plamining chetki nuqtalari to’plamida bo’ladi.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_11.png)
![2 x 3 x 1
3 x 2
5 x x1 x2 max
x 3 x 1
3 x 2
9 x x 1
x 2
8
3 x 7 x 1
7 x 2
2 x 4 x 1
4 x 2
6
2 x 6 x 1
6 x 2
5 x 2 x 1
2 x 2
4
x 0 , x 1
0 , x 2
0 , x 0, x 1
0 , x 2
0
1 2 2 3 4 4
2.1. Sun’iy bazis vektor usuli
Biz yuqorida, chiziqli programmalashtirish masalasining
boshlang`ich tayanch yechimi mavjud va boshlang`ich yechimni tuzish
mumkin bo`ladigan m-o`lchovli birlik matritsa masala shartida
qatnashadi, deb faraz qildik. Bu birlik matritsa yordamida optimal
yechimga o`tishga yordam beradigan yechimni tuzish mumkin. Agar
chiziqli programmalashtirish masalasining chegaraviy shartlari AX B
ko`rinishda berilgan bo`lsa, qo`shimcha o`zgaruvchilar kiritib,
to`g`ridan-to`g`ri simpleks usul algoritmidan foydalanish mumkin.
Amalda uchraydigan ko`p chiziqli programmalashtirish masalalari
yechimga ega bo`lgan holda birlik matritsani o`z ichiga olmaydi.
Bunday masalalarni yechish uchun «sun’iy bazis vektor» usul
qo`llaniladi.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_12.png)
![FOYDALANILGAN ADABIYOTLAR RO’YXATI
1. Количественные методы в экономических
исследованиях: Учебник для вузов// Под ред. Ш.В.
Грачевой, М.Н. Фадеевой, Ю.Н. Черёмных - М.:
ЮНИТИ –ДИАНА, 2004.
2. Шапкин А.С, Мазаева Н.П, Математические
методы и модели ислледования операций. М. 2006г.
3. Красс М.С, Чупрынов Б.П, Математика для
экономического бакалавриата. –M.: Из-во «Дело», 2005.
4. Ермаков В.И. Общий курс высшей математики для
экономистов.
-М.: ИНФРА – М. 2006.
5. Волошин Г.Я. Методы оптимизации в
экономике. -М.: Дело и Сервис, 2004.
6. Шикин Е.В, Чхартшвиили А.Х.
Математические методы
7. и модели в управлении. –M.: Из-во «Дело» 2004.
8. Крамер Н.Ш. Исследование операций в экономике. -М.:
2005.
9. Jumaev X.N, Otaniyozov B, Yugay L.P, Jalilov A.
Matematik programmalashtirish, Darslik. Adabiyot
jamg`armasi nashriyoti – 2005.
10. Safaeva Q. Matematik dasturlash. Darslik,
“Iqtisod-Moliya” nashriyoti, -Т.: 2004.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_13.png)
![XULOSA
Ushbu kurs ishida men matematik programmalashtirish va optimallashtirish usullari
bo`yicha bilimlarimni yanada mustahkamladim.
Kurs ishi davomida matematik programmalashtirish va optimallashatirish usullarining
asosiy yo`nalishlari va metodlari haqida misollar bilan tanishib chiqdim.
Shuningdek, misollarning iqtisodiy talqini va tatbiqiy jihatlariga e’tibor qaratdim.
Mаtеmаtik prоgrаmmаlаsh va optimallashtirish usullari prеdmеti
kоrхоnа, firmа, qurilish, qishloq xojaligi, bоzоr, ishlаb chiqаrish
birlаshmаsi, хаlq хo’jаlik tаrmоqlаri, umuman olganda, butun хаlq
хo’jаligigа dоir iqtisоdiy jаrаyonlаrni tаsvirlоvchi mаtеmаtik
mоdеllаrni tuzish va ularga tegishli usullarni qo’llab yechishdan
ibоrаt. Mаtеmаtik mоdеllаr ko’p dаvrlаrdаn buyon iqtisоdiyotdа
ishlаtilmоqdа.](/data/documents/64895632-c7db-49c4-90d5-b4d58245c73a/page_14.png)
MAVZU: Sun’iy bazis vektor usuli va chiziqli programmalash masalalarini sonli yechishga qo’llash. MUNDARIJA Kirish………………………………………………………………….………..3 I-BOB. CHIZIQLI PROGRAMMALASHTIRISH MASALASI……….………4 1.1. Asosiy tushunchalar . Chiziqli programmalashtirish masalasining qo`yilishi ................................................................. 4 1.2. Chiziqli dasturlash masalalarining matematik modeli…9 II-BOB. Chiziqli programmalashtirish masalasining yechimlari haqida………12 2.1. Sun’iy bazis vektor usuli………………………………...14 2.2. Chiziqli modellarga misollar…………………………….17 2.3. Chiziqli programmalashtirish masalasining geometrik talqini. Masalani grafik usulda yechish…………………19 XULOSA……………………………………………………………………………..22 FOYDALANILGAN ADABIYOTLAR RO’YXATI…………………………..…23
KIRISH Fan va texnikaning jadal rivojlanishi, ishlab chiqarishni boshqarishning murakkablashishi va uni rejalashtirishga qo`yiladigan talablarning ortishi bozor iqtisodini rivojlanishlarini tavsiflovchi omillardan hisoblanadi. Bunday sharoitda iqtisodni boshqarishga ilmiy yondoshish, matematik usullarni keng qo`llash, ayniqsa, matematik programmalashtirishning aniq usullaridan foydalanish zaruratga aylandi. Zamonaviy kompyuter texnologiyasidan keng foydalangan holda, matematik programmalashtirish va optimallashtirish usullarini iqtisodiy izlanishlar va rejalashtirishda qo`llash muhim bo`lib qoldi. M а t е m а tik pr о gr а mm а l а sh va optimallashtirish usullari pr е dm е ti k о r хо n а , firm а , qurilish, qishloq xojaligi, b о z о r, ishl а b chiq а rish birl а shm а si, ха lq х o’j а lik t а rm о ql а ri, umuman olganda, butun ха lq х o’j а ligig а d о ir iqtis о diy j а r а yonl а rni t а svirl о vchi m а t е m а tik m о d е ll а rni tuzish va ularga tegishli usullarni qo’llab yechishdan ib о r а t. M а t е m а tik m о d е ll а r ko’p d а vrl а rd а n buyon iqtis о diyotd а ishl а tilm о qd а . M а s а l а n, iqtis о diyotd а qo’ll а nilg а n 1- m о d е l – F.K е n е t о m о nid а n yar а tilg а n t а kr о r ishl а b chiq а rish m о d е lidir. «Iqtis о diy m а s а l а ning m а t е m а tik m о d е li» d е g а nd а bu m а s а l а ning а s о siy sh а rtl а ri v а m а qs а dining m а t е m а tik f о rmul а l а r yord а mid а ifodalanishiga а ytil а di. Optimallashtirish usullari yordamida ekstremal iqtisodiy masalalarni yechishni to`rt bosqichga bo`lish mumkin: masalani chuqur o`rganib, unga tatbiq qilish mumkin bo`ladigan usullarni tanlash, masalada qo`yilgan shartlarga asoslanib matematik model tuzish; - agar masalaning shartlari maqsadga muvofiq kelsa, tegishli matematik usulni qo`llab, optimal yechimni topish; - yechimni iqtisodiy tahlil qilish va uni amaliyotga «imkoni boricha» tatbiq etish; - amaliyotda matematik programmalashtirish va optimallashtirishning taqribiy usullaridan foydalanish haqida tushunchalar berish. Matematik programmalashtirish va optimallashtirish usullari masalalari chiziqli, chiziqsiz hamda dinamik programmalashtirishga bo`linib, umumiy holda ekstremal masalalarni yechishda qo`llaniladi. Ko`rsatilgan funksiyalardan hech bo`lmasa bittasi chiziqli bo`lmagan funksiya bo`lsa, masala chiziqsiz programmalashtirish masalasidan iboratdir.
I-BOB. CHIZIQLI PROGRAMMALASHTIRISH MASALASI 1.1. Asosiy tushunchalar . Chiziqli programmalashtirish masalasining qo`yilishi Chiziqli dasturlash matematik dasturlashning bir bo’limi bo’lib, bunda o’zgaruvchilariga chiziqli cheklashlar qo’yilgan chiziqli funksiyaning ekstremal (maksimal yoki minimal) qiymatini topish masalalari va ularni yechish usullari o’rganiladi. Chiziqli cheklashlar tengliklar yoki qa’tiy bo’lmagan tengsizliklar ko’rinishida bo’lishi mumkin. Chiziqli dasturlash masalalarini sistemalashtirish va ularni yechish uchun umumiy, universal usul yaratish ustida L.V.Kantorovich 1939 yildan boshlab shug’ullangan. Amerikalik olim J.Dansig tomonidan XX asrning 40- yillarida simpleks-usul deb ataluvchi usul yaratildi va chiziqli programalashtirish nazariyasi hamda uning qo’llanilishi tez suratlar bilan rivojlandi. «Chiziqli dasturlash» iborasini birinchi bo’lib 1951 yilda J.Dansig va T.Kupmans kiritishgan. Chiziqli dasturlash masalasining matematik modeli umumiy ko’rinishda quyidagicha ifodalanadi: , o’zgaruvchilarning shunday qiymatlari topilsinki, , , va , shartlar bajarilsin hamda funksiya maksimal (yoki minimal) qiymat qabul qilsin, bunda . Chiziqli dasturlash masalasining matematik modelidagi , shartlar (manfiymaslik shartlari), ba’zan, qisman yoki butunlay qatnashmasligi mumkin. Chiziqli programmalashtirish chiziqli funksiyaning eng katta va eng kichik qiymatini o`zgaruvchilarga nisbatan chiziqli chegaraviy shartlar qo`yilgan holda aniqlash bilan shug`ullanadi. Shuning uchun, chiziqli programmalashtirish masalalari funksiyaning shartli ekstremum masalalari qatoriga kiradi. Lekin chiziqli programmalashtirish masalalari ko`p o`zgaruvchili bo`lgani uchun matematik analizdagi funksiya ekstremumini aniqlashning klassik usulini to`g`ridan-to`g`ri qo`llash mumkin emas. Shuning uchun chiziqli programmalashtirish masalalarini yechishning maxsus usullari ishlab chiqilgan. Ular yordamida, ko`pgina masalalarni, ayniqsa, iqtisodiy masalalarni yechish maqsadga muvofiq.
1.2. Chiziqli dasturlash masalalarining matematik modeli. Ma’lumki, ishlab chiqarish haqidagi masalaning matematik modeli quyidagi ko’rinishda bo’ladi: . Bu model chiziqli dasturlash masalasi matematik modelining bir ko’rinishi bo’lib, undagi , shartlar masalaning asosiy shartlari, , shartlar esa, to’g’ri (bevosita) shartlari deb ataladi. Maksimal qiymat qabul qilishi kerak bo’lgan chiziqli fuknsiya esa, masalaning maqsad funksiyasi deb ataladi. Ba’zi chiziqli dasturlash masalalarining asosiy shartlari tenglamalar ko’rinishida yoki ulardagi tengsizliklar « » ko’rinishda bo’lishi mumkin, xullas, asosiy shartlar tenglamalar va tengsizliklar sistemasini tashkil etadi. Vektor-matrisa yozuvidan foydalanib chiziqli dasturlash masalasining matematik modelini quyidagi ko’rinishida ham ifodalash mumkin: , bunda , , – vektorlar, matrisa, (') belgi esa transponirlash amalini anglatadi. Bu yerda matrisa va vektorlar ustida amallar amaldagi qoidalarga binoan bajariladi. Yozuvlarda uchraydigan vektorlar vektor-ustun deb tushuniladi, vektor- satrni hosil qilish uchun esa, transponirlash amali qo’llaniladi. Shuning uchun, c va x vektorlarning skalyar ko’paytmasi ko’rinishda yoziladi. Biror x vektor uchun yoki ko’rinishdagi yozuv uning har bir komponentasi ko’rsatilgan shartga bo’ysunishini anglatadi. Shuni ham ta’kidlash kerakki, ba’zan, yozuvda transponirlash belgisi (') tushirib qoldirilishi mumkin. Chiziqli dasturlash masalasining yuqoridagi yozuvida qatnashgan parametrlarga ishlab chiqarish haqidagi masalaning mohiyatidan kelib chiqqan holda nomlar ham berilgan: x – rejalar vektori, s – baholar (narxlar) vektori, b –
shartlar vektori, A – shartlar yoki xarajatlar matrisasi. A matrisaning ustunlarini esa shartlar vektorlari deb atashadi. Agar chiziqli dasturlash masalasining matematik modeli yuqoridagi ko’rinishga ega bo’lsa, u normal ( standart, tabiiy, simmetrik ) shaklda yozilgan deb hisoblanadi. Agar chiziqli dasturlash masalasining asosiy shartlari faqat tenglamalardan iborat bo’lsa, ya’ni uning matematik modelil , ko’rinishda bo’lsa, u holda chiziqli dasturlash masalasi kanonik shaklda yozilgan deyiladi. Bulardan tashqari, chiziqli dasturlash masalasi matematik modelini yozish uchun boshqa shakllar ham mavjud, masalan, umumiy shakl. Isbotlash mumkinki, ixtiyoriy ko’rinishda yozilgan chiziqli dasturlash masalasini, sodda matematik almashtirishlar yordamida, unga ekvivalent bo’lgan boshqa ixtiyoriy ko’rinishdagi chiziqli dasturlash masalasiga keltirish mumkin. Buning uchun, odatda, quyidagi almashtirishlar qo’llaniladi. 1. Tengsizlikning ishorasini teskarisiga almashtirish: « » ko’rinishdagi tengsizlikning ikkala tomoni ishorasini teskarisiga almashtirib, “ ” ko’rinishdagi tengsizlikka va, aksincha, “ ”ni “ ”ga keltirish mumkin. 2. Tengsizlikni tenglamaga «aylantirish» mumkin: , bunda – qo’shimcha o’zgaruvchi deb ataladi. 3. Agar biror o’zgaruvchiga to’g’ri shart qo’yilmagan bo’lsa, u holda bu o’zgaruvchini ikkita manfiymas o’zgaruvchilar ayirmasi shaklida ifodalash mumkin. 4. Maqsad funksiyasining ishorasini teskarisiga almashtirish yordamida maqsadni ifodalovchi max ni min ga yoki, aksincha, min ni max ga almashtirish mumkin. Chiziqli dasturlash masalasining barcha (asosiy va to’g’ri) shartlarini qanoatlantiruvchi vektor uning mumkin bo’lgan yechimi yoki rejai deb ataladi. Barcha mumkin bo’lgan yechimlar birgalikda masalaning mumkin bo’lgan yechimlari (rejalari) to’plami ni tashkil etadi. Masalaning maqsad funksiyasiga maksimal qiymat beruvchi reja (mumkin bo’lgan yechim) uning optimal rejai ( optimal yechimi ) deb ataladi. Misol. Quyidagi chiziqli dasturlash masalasi berilgan bo’lsin: