Maruza mashg’ulotlari

Tenglama
Boshlang’ich shart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

11-§.Chiziqli dasturlash masalalarining qoʻyilishi va unda qoʻllaniladigan modellar. Masalasini simpleks usulda yechish.

Optimallash nazariyasi va matematik dasturlashtirish hozirgi inson faoliyatining turli jabxalarida keng qo‘llanilayotgan fanlardan biridir. Bu sohadagi muhim muvaffaqiyatlarga katta texnik sistemalarni loyihalash va tahlil qilish natijasida erishilgandir. Nazariy bilimlarni injenerlik va boshqa sohalarga tezda tadbiq qilinishi hozirgi zamon hisoblash texnikasining takomillashtirilishi va keng tarqalishi bilan bevosita bog‘liqdir.

hozirgi vaqtda matematik usullar xalq xo‘jaligining rivojlantirishda, iqtisodiy masalalarni echishda muvaffaqiyat bilan qo‘llanilmoqda. Masalalarni echishda quyidagi muommalar bilan duch kelinadi: a) masala echimining mavjudligi; b) echimning yagonaligi; v) echimning turg‘unligi; g) o‘zgaruvchilarga nisbatan cheklanish; d) maqsadga muvofiq echimni aniqlash.

Boshqarish va rejalashtirish jarayonida iqtisodcha quyidagi xususiyatlarga ega bo‘lgan masalalarga duch keladi:

- izlanayotgan miqdorlarga juda ko‘p cheklanishlar qo‘yiladi;

- masala juda ko‘p echimga ega bo‘lib, ulardan qandaydir ma’noda eng maqbulini (optimalini) tanlab olish kerak bo‘ladi.

Yaqin vaqtlargacha bunday masalalarning ko‘pchiligi empirik yo‘l bilan echilar edi. Keyingi yillarda yaratilgan chiziqli dasturlash usullari quyilgan masalalarni birdan – bir to‘g‘ri hal qilish imkonini yaratib berdi.

Matematik dasturlash amalga oshirsa bo‘ladigan dasturni (rejani) aniqlashdan iborat bo‘lib, u ma’lum nuqtai nazardan qabul qilingan mezonga (kriteriyga) asosan optimal hisoblanadi. Zamonaviy kompyuterlarning yaratilishi va ularning dasturiy ta’minoti, matematik dasturlash usullarining tadbiqlari va imkoniyatlarini kengaytirib yubordi.

Berilgan iqtisodiy masalaning matematik modelini tuzish ikki bosqichdan iborat bo‘ladi:

1.Oldimizga qo‘yilgan maqsad, izlanayotgan miqdorlarning (noma’lumlarning) biror bog‘lanishi ko‘rinishida beriladi. Bu bog‘lanish maqsad funksiyasi yoki mazkur masalaning funksionali deyiladi.

2.Shundan so‘ng izlanayotgan miqdorlarga qo‘yiladigan cheklanishlar ifodalanadi. Bunday shartlar cheklanishlar sistemasi deyiladi.

Agar maqsad funksiyasi musbat iqtisodiy omillarni (masalan foydani) ifodalasa, u holda maqsad funksiyasining maksimum qiymati aniqlanadi, aks xolda – minimum qiymati aniqlanadi.

Cheklanishlar sistemasini qanoatlantiruvchi har qanday echim (reja) mumkin bo‘lgan echim (reja) deyiladi. Maqsad funksiyasiga maksimum (yoki minimum) qiymat beradigan mumkin bo‘lgan echim (reja) optimal echim (reja) deyiladi.

Shunday qilib, masalani echish – mumkin bo‘lgan barcha echimlardan optimalini topishdan iborat.

Agar maqsad funksiyasi va cheklanishlar sistemasi noma’lumlarga nisbatan chiziqli bo‘lsa, u holda masala chiziqli dasturlash masalasi deyiladi. Agar maqsad funksiyasi yoki cheklanishlar sistemasi chiziqsiz ifodalardan tashkil topsa, u holda masala chiziqsiz dasturlash masalasi deyiladi. Chiziqsiz dastrulash qavariq, diskret, kvadratik, stoxastik, dinamik va boshqa dasturlashlarga bo‘linadi.

Chiziqli dasturlash usullarini qo‘llab echiladigan iqtisodiy masalalarga quyidagi masalalarni keltiramiz.

Transport (yuk tashish) masalasi. M₁,M₂,M₃, ko‘mir konlarida xar oyda mos ravshida a₁, a₂, a₃, tonnadan ko‘mir qazib chiqariladi. KO‘mir R₁, R₂, R₃, punktlarga (omborlarga) etkazib berilishi kerak. Bu punktlarning ko‘mirga har oydagi talabi mos ravshida v₁,v₂,v₃, tonnani tashkil etadi. M_i konidan R_j punktga keltirilgan 1 tonna ko‘mirga S_ij sum sarflansin. Agar M_i konidan P_j punktga keltirilgan X_ij tonna desak, masala shunday qo‘yiladiki, barcha ko‘mirni punktlarga etkazib berish uchun qilingan sarf – xarajat eng kichik qiymatga (minimum) ega bo‘lish kerak. Masalani echish uchun eng kam narx usuli, shimoliy – g‘arb usuli, diagonal usuli, potensial usuli kabilar mavjud.

Ozuka rasioni masalasi. Xo‘jalikda n hil ozuqa bo‘lib, ularning xar qaysisi m turdagi to‘yimli moddalarga (yog‘, kraxmal, oqsil va hokazolarga) ega. Birinchi ozuqaning bir birligi a_1i birinchi to‘yimli moddaga, a_2i birlik ikkinchi to‘yimli moddaga va hokazo ega. Umumiy holda j nomerli bir birlik ozuqada a_ij birlik i chi modda bor. v_i (i=1,2,...,m) – har qaysi to‘yimli moddaning miqdori. Bu miqdor albatta rasionga kirishi kerak. j nomerli ozuqaning narxi C_j (j = 1,2,...,n). Shunday rasion x_j , ya’ni boqish rejasini topish kerakki, u barcha talablarga javob berib, narxi eng kichik qiymatga ega bo‘lsin.

Yuqoridagi masalardan tashqari qo‘yidagi masalalar ham chiziqli dasturlash masalariga misol bo‘ladi:

1.Xom ashyo resurslaridan foydalanish masalasi (Korxonaning eng ko‘p daromad olish masalasi.)

2.Parxez masalasi.

3.Andozalash masalasi.

4.Ishga tayinlash xaqidagi masala.

Endi ba’zi tarixiy ma’lumotlarga to‘xtalib o‘tamiz. Chiziqli algebra matematikaning mustaqil sohasi sifatida XVIII asrda nemis matematigi Leybnis va shveysariyalik matematik G.Kramer tomonidan n – tartibli determinantlar tushunchasi kiritilib, n–ta noma’lumli n – ta tenglamalar sistemasining echishning umumiy formulasi berilgandan keyin yuzaga keldi.

Yuk mashinasining optimal rejasini tuzish masalasi chiziqli dasturlash masalasi tariqasida birinchi marta A.N.Tolstov tomonidan 1930 yilda qo‘yilgan.

1931 yili venger matematigi B. Egervari chiziqli dasturlashning hususiy xollaridan birining matematik qo‘yilishini tekshirib, bu masala keyinchalik «Tanlash muammosi» nomi bilan yuritila boshlandi. Bu masalani amerikalik matematik G.U. Kun yangi usul bilan echdi va uni Venger usuli deb atadi.

Chiziqli dasturlash masalasini tekshirishning sistematik taraqqiyoti 1939 yili. L.V. Kantarovich va uning shogirdlari ishlari asosida boshlandi. U chiziqli dasturalash masalasini echishning umumiy usuli – hal qiluvchi ko‘paytuvchilar usulini yaratdi.

Simpleks usul 1941 yili Dj. Dansig tomonidan yaratildi. Chiziqli va chiziqsiz dasturlashning keyingi rivoji Ford, Kun kabi olimlarning ishlari va kompyuterlarning rivoji bilan bog‘liq.