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: