Algoritmlarni baholash. (Big-O)

n
Mahsulot birligidan olinadigan daromad
1	a11	a12	a13	...	a1n	C1
2	a21	a22	a23	...	a2n	C2
...	...	...	...	...	...	...
m	am1	am2	am3	...	amn	Cm
i/ch matrialning zahirasi	b1	b2	b3	...	bn

• 
  Jadvaldagi har bir b_j - j - ishlab chiqarish faktorining zahirasini; a_ij - i - mahsulotning bir birligini ishlab chiqarish uchun sarf qilinadigan j - faktorning me’yori; s_i - korxonaning i - mahsulot birligini realizatsiya qilishdan oladigan daromadini bildiradi.
  
• 
  Masalaning iqtisodiy ma’nosi: korxonaning ishlab chiqarish rejasini shunday tuzish kerakki: a) hamma mahsulotlarni ishlab chiqarish uchun sarf qilinadigan har bir ishlab chiqarish faktorining miqdori ularning zahirasidan oshmasin; b) mahsulotlarni realizatsiya qilishidan korxonananing oladigan daromadi maksimal bo’lsin.
  

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_i  0 (i=1, 2, ..., m) .

• 
  Masaladagi b) shart uning maqsadini aniqlaydi. Demak masalaning maqsadi mahsulotlarni realizatsiya qilishdan korxonaning oladigan umumiy daromadini maksimallashtirishdan iborat va uni
  
• 
  Y = c₁x₁ + c₂x₂ + ... + c_mx_m -> max,
  
• 
  ko’rinishdi ifodalash mumkin.
  

Chiziqli dasturlash masalasi

Fabrika ikki xil M₁ va M₂ tikuv mahsuloti ishlab chiqaradi. Bu mahsulotlarni ishlab chiqarishda uch xil N₁,N₂,N₃ turdagi materiallarni ishlatadi. N₁-materialdan 15 m., N₂-materialdan 16 m., N₃-materialdan 18 m. mavjud. 
M₁- mahsulotni ishlab chiqarish uchun N₁-dan 2m., N₂-dan 1m., N₃-dan 3m. ishlatadi.
M₂- mahsulotni ishlab chiqarish uchun N₁-dan 3m., N₂-dan 4m., N₃-dan 0m. ishlatadi.
M₁- mahsulotning bir birligidan keladigan foyda 10 so‘mni, M₂ - mahsulotdan keladigan foyda 5 so‘mni tashkil qiladi.
Ishlab chiqarishning shunday planini tuzish kerakki fabrika maksimal foyda olsin. Masalaning matematik modelini tuzamiz:
Bu yerda M₁ mahsulotni x₁ va M₂ mahsulotni x₂ o’zgaruvchi bilan almashtirib olamiz.
Bu yerda M₁ mahsulotni x₁ va M₂ mahsulotni x₂ o’zgaruvchi bilan almashtirib olamiz.

Bu yerda Z=10x₁+5x₂ -> max maqsad funksiyasi bo’lib, x₁ va x₂ larning shatrlarni bajarilgan qiymatlarida Z ning maksimumga erishishini ta’minlash masalasi qaraladi.

• 
  Misol .
  
• 
  Z = 2x + 3y maqsad funksiyasining maksimum qiymatini toping.
  
• 
  Chegaraviy shartlar quyidagicha berilgan:
  
• 
  x + y 30, y 3, 0 y 12, x - y 0, va 0 x 20.
  
• 
  
• 
  Yechish
  
• 
  Birinchi navbatda koordinatalar sistemasida x 0, y 0 ekanligini belgilab olamiz.
  
• 
  Koordinatalar sistemasida x + y 30, y 3, y 12, x y va x 20, chegaralarni belgilab, ABCDE shaklni aniqlaymiz.
  
• 
  Shakl uchlaridagi nuqtalar A(3, 3), B (20, 3), C(20, 10), D(18, 12) va E(12, 12) bo’ladi.
  
• 
  Shakl uchlaridagi Z ning qiymatlari Z(A) = 15, Z(B) = 49, Z(C)= 70, Z(D)=72, va Z(E) = 60
  
• 
  D nuqtada Z maksimum qiymatga erishadi. Z(D)=72. Bu nuqtada x va y ning qiymatlari x = 18, y = 12 ga teng.
  

2-masala.
Korxonada ikki tur buyum ishlab chiqarish uch xil xomashyo ishlataladi. Birinchi tur buyum ishlab chiqarish uchun birinchi xil xomashyodan 6 kg, ikkinchi xil xomashyodan 3 kg, uchinchi xil xomashyodan 4 kg ishlatiladi. Ikkinchi tur buyum ishlab chiqarish uchun birinchi xil xomashyodan 2 kg, ikkinchi xil xomashyodan 4 kg, uchinchi xil xomashyodan 3 kg ishlatiladi.Agar korxona birinchi xomashyodan 600 kg, ikkinchi xil xomashyodan 520 kg, uchinchi xil xomashyodan 600 kg ta’minlangan va birinchi xil buyumni sotganda har bir donasidan 6 so'm , ikkinchi xil buyumni sotganda esa 3 so'm foyda olganda, korxona ishlab chiqarishini shunday rejalashtirinki, olingan daromad maksimal bo'lsin.