Algoritmlarni loyihalash fanidan

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
QARSHI FILIALI


TT va KT FAKULTETI
II BOSQICH AX 11-21 GURUH TALABASINING
ALGORITMLARNI LOYIHALASH FANIDAN
2 MUSTAQIL ISH

Bajardi: Usmonova M
Qabul qildi: Nosirov B

Mavzu: Chiziqli dasturlash masalalrining kanonik ko’rinishi. Simpleks usul
Reja:

1. 
   Chiziqli dasturlash masalalarining kanonik ko’rinishi. Simpleks usul
   
2. 
   Raqamli axborotlarni qayta ishlashda Fur’ye usuli, Spektral tahlil.
   
3. 
   Statistik axborotlarni qayta ishlashda ba prognoz masalalarida dinamik dasturlash usullari
   

Chiziqli dasturlash masalalarining kanonik ko’rinishi. Simpleks usul
Matematik programmalash matematikaning asosan ko’p variantli yechimga ega bo’lgan iqtisodiy masalalarning eng yaxshi maqsadga muvofiq ( optimal ) yechimini topishga yordam beruvchi bir tarmog’idir.
Chiziqli programmalash usullarini taraqqiy ettirish muamosi bilan ko’pgina olimlar shuullanganlar. Masalan, amerikalik olim Xichkok 1941 yilda transport masalasining matematik modelini tuzdi, Danstig 1949 yilda chiziqli programmalash masalasini yechish uchun universal usul—simpleks usulni kashf etdi. Chiziqli va chiziqli bo’lmagan programmalash usullari Ford, Falkerson, Kun, Lemke, Gass, Charnes, Bil va boshqa olimlarning ishlarida o’z rivojini topdi.
Hozirgi davrda chiziqli va chiziqli bo’lmagan programmalash usullarini konkret iqtisodiy masalalarni yechishga qo’llash hamda ularni EhM da yechish uchun eng qulay algoritmlar yaratish muammosi bo’yicha ish olib borilmoqda. Shu bilan bir qatorda ko’p olimlarning e’tibori chiziqli bo’lmagan programmalash usullarini taraqqiy ettirishga bag’ishlangan. Bu sohada birinchi marta Kun va Takker 1951 yilda isbotlagan teorema birinchi yutuq bo’lib, unda chiziqli bo’lmagan programmalash masalasining optimal yechimga ega bo’lishining zarur va etarlilik sharti keltirilgan. Ayrim chiziqli bo’lmagan programmalash masalalari uchun chiziqli approksimastiya topilib ularni chiziqli programmalash usullarini qo’llab yechish mumkin.
Har qanday iqtisodiy masalani matematik dasturlash usullarini qo’llab yechishdan avval, ularning matematik modelini tuzish kerak; boshqacha aytganda berilgan iqtisodiy masalaning chegaralovchi shartlarini va maqsadini matematik formulalar orqali ifodalab olish kerak. Har qanday masalaning matematik modelini tuzish uchun:
-masalaning iqtisodiy ma`nosini o’rganib, undagi asosiy shart va maqsadni aniqlash;
-masaladagi noma`lumlarni belgilash;
-masalaning shartlarini algebraik tenglamalar yoki tengsizliklar orqali ifodalash;
-masalaning maqsadini funksiya orqali ifodalash kerak.
Misol uchun bir nechta eng sodda iqtisodiy masalalarning matematik modelini tuzish jarayoni bilan tanishamiz.
Ishlab chiqarishni rejalashtirish masalasi.
Faraz qilaylik, korxonada m xil mahsulot ishlab chiqarilsin; ulardan ixtiyoriy birini i (i=1,…,m) bilan belgilaymiz. Bu mahsulotlarni ishlab chiqarish uchun n xil ishlab chiqarish faktorlari zarur bo’lsin. Ulardan ixtiyoriy birini j (j=1,…,n) bilan belgilaymiz.
Har bir ishlab chiqarish faktorining umumiy miqdori va bir birlik mahsulotni ishlab chiqarish uchun sarf qilinadigan normasi quyidagi jadvalda berilgan:
2.1.1-jadval

i/ch faktorlari i/ch mahsulot Turlari	1	2	3	…	n	Daro-mad
1	a11	a12	A13	…	a1n	C1
2	a21	a22	A23	…	a2n	C2
…	…	…	…	…	…	…
M	am1	am2	am3	…	amn	Cm
i/ch faktorining zahirasi	b1	B2	B3	…	bn

Jadvaldagi har bir b_j – j‑ishlab chiqarish faktorining umumiy miqdori (zahirasi)ni; a_ij – i‑mahsulotning bir birligini ishlab chiqarish uchun sarf qilinadigan j-faktorning miqdori; c_i–korxonaning i‑mahsulotning bir birligini realizatciya qilishdan oladigan daromadi.
Masalaning iqtisodiy ma`nosi: korxonaning ishini shunday rejalashtirish kerakki: a) hamma mahsulotlarni ishlab chiqarish uchun sarf qilinadigan har bir ishlab chiqarish faktorining miqdori ularning umumiy miqdoridan oshmasin; b) mahsulotlarni realizatciya qilishdan korxonaning oladigan daromadi maksimal bo’lsin.

(2.1.1)
Rejalashtirilgan davr ichida ishlab chiqariladigan i-mahsulotining miqdorini x_i bilan belgilaymiz. U holda masaladagi a) shart quyidagi tengsizliklar sistemasi orqali ifodalanadi:



Masalaning iqtisodiy ma`nosiga ko’ra hamma noma`lumlar manfiy bo’lmasligi kerak, ya`ni:
x<sub>i</sub> і0 (i=1,2,…m) (2.1.2)
Masaladagi b) shart uning maqsadini aniqlaydi. Demak masalaning maqsadi mahsulotlarni realizatciya qilishdan korxonaning oladigan umumiy daromadini maksimallashtirishdan iborat va uni
y = c<sub>1</sub>x<sub>1</sub> +c<sub>2</sub>x<sub>2</sub>+ … + c<sub>m</sub>x<sub>m</sub> (2.1.3)
chiziqli funksiya orqali ifodalash mumkin. Shartga ko’ra y®max. Bu shartni Y<sub>max</sub> ko’rinishda belgilaymiz.
Chiziqli dasturlash masalasi umumiy holda 2.1.1-1.1.3 kabi ifodalanadi.
2.1.1-1.1.2 shartlarni qanoatlantiruvchi noma`lumlarning shunday qiymatlarini topish kerakki, ular (2.1.3) chiziqli funksiyaga minimal (maksimal) qiymat bersin. Masalaning (2.1.1) va (2.1.2) shartlari uning chegaraviy shartlari deb, (2.1.3) chiziqli funksiya esa masalaning maqsadi yoki maqsad funksiyasi deb ataladi.
Masaladagi barcha chegaralovchi shartlar va maqsad funksiya chiziqli ekanligi ko’rinib turibdi. Shuning uchun ham (2.1.1)–(2.1.3) masala chiziqli dasturlash masalasi deb ataladi.
Konkret masalalarda (2.1.1) shart tenglamalar sistemasidan, «і» yoki «Ј» ko’rinishdagi tengsizliklar sistemasidan yoki aralash sistemadan iborat bo’lishi
mumkin. Lekin ko’rsatish mumkinki, (2.1.1)–(2.1.3) ko’rinishdagi masalani osonlik bilan quyidagi ko’rinishga keltirish mumkin: