Њзбекистон республикаси олий ва њрта махсус

Optimal dasturlash usulining asosiy masalalari

Matematik modellashtirish kursi optimal dasturlash usullarini o„rgatadi.
Ularning ayrimlarini ko„rib chiqamiz.
Chiziqli dasturlash. 1-masala. Har bitta ishlab chiqarish jarayonini matematik formula bilan yozib chiqish mumkin. Masalan, bir nechta tarmoqlarda  j  1,2,..., n korxonalar bor i  1,2,..., m. Ularning har biri turli xildagi mahsulotlar ishlab

chiqaradilar
X _ij . Mahsulotdan oladigan daromadni
^Cij
bilan belgilaymiz. Bu holda

yalpi daromad
^Cij ^{ X} ij
ga teng bo„ladi. Yalpi daromad albatta iloji boricha ko„p

olinishi kerak. Ya‟ni, C_ij X_ij  max intilishi lozim.

Buning maqsad funksiyasi:


m n

^cij ^xij
 max

i1 j1

Bu maqsadga yetish uchun bir nechta shartlar bajarilish kerak. Ya‟ni:

1. 
   ishlatiladigan resurslar korxonadagi zaxiradan ko„p bo„lishi kerak emas.
   

m n

 ^aij ^xij
 b_{i ,}

i1 j1

bu yerda
me‟yorlari.
^aij
- har bitta mahsulotga i-korxonadan j-tarmoqda ketadigan xarajat

2. 
   O„zgaruvchilarning qiymati manfiy bo„lmaslik shart:
   

x_ij  0 .
Bularni hisobga olib, ushbu chiziqli dasturlash usulining umumiy masalasini yozib chiqamiz:



i1



j1
c_ij x_ij  min(max)

m n

 ^aij ^xij
 b_{i ,}

i1
j1


x_ij  0 .

2. 
   masala. Firma faoliyatini bozor sharoitida modellashtirish, tadbirkorni maksimal foyda olishga yo„naltirilgan xatti-harakatlarini tashkil etishga qaratilgan. Bunda tadbirkor bozor talablarini o„rgangan holda ishlab chiqarish imkoniyatlaridan to„liq foydalanib, o„z ishini tashkil etadi. Masalada maqsad mezoni bo„lib, umumiy daromadni yoki umumiy foydani maksimallash, ba‟zi hollarda esa umumiy xarajatlarni minimallashtirishni tanlashi mumkin.
   

Bu ekstremal masalaning matematik modelini quyidagicha yozish mumkin:
Z  ₁ x₁  ₂ x₂  ...  _n x_n  max


^{a11x1  a12x2  ...  a1n xn  A1}

a
^ 21^x1

 a₂₂ x₂
 ...  a_2n x_n
 A_{2 ,}

_.............................................
_^a_m1 x₁  a_m2 x₂  ...  a_mn x_n  A_m
bu yerda, j – firma ishlab chiqarayotgan mahsulot indeksi j  1, n;
n – firma ishlab chiqarayotgan mahsulotlarning umumiy soni;
 _j – j -mahsulotdan olinadigan foyda miqdori;
i – mahsulot ishlab chiqarish bilan bog„liq resurslar indeksi i  1, m;

^aij

• 
  j -turdagi bir birlik mahsulotni ishlab chiqarish uchun i -turdagi resurs
  

sarflari me‟yori;

A_i
x _j
miqdori.

• 
  firmada mavjud bo„lgan i -turdagi resurs hajmi;
  
• 
  firmaning maksimal foyda olishini ta‟minlovchi j -turdagi mahsulot
  

Chiziqli dasturlashning umumiy masalasi ikkita usul yordamida hal etilishi mumkin.
Bulardan birinchisi - simpleks usuli, yoki rejani ketma-ket yaxshilash usulidir.

Ikkinchi usul - bu taqsimlash usulidir. Chiziqli dasturlashning bu usuli bajaradigan asosiy vazifa - transport masalasini bo„lib hisoblanadi. Тaqsimlash usuli yuk tashishni samarali tashkil etishda qo„llanilgan, keyingi boblarda bu masalani, alohida transport masalasi sifatida ko„rib chiqamiz.
Agar noma‟lum o„zgaruvchilar soni m tengsizlik shartlari soni n ga teng bo„lsa, unda masalaning bitta optimal yechimi bo„ladi.

Ko„pincha
m  n
tenglamalar tizim ko„riladi. Unda masalaning bir nechta

yechimi mavjud bo„ladi. Asosiy vazifa - bir nechta yechimdan optimal yechimni topishdir.
Kasr-chiziqli dasturlash. Bu usul matematik dasturlashning bir bo„limi bo„lib, quyidagi ko„rinishdagi ekstremal masalalarni tekshiradi.

Shartlar bo„yicha
F(x)  max
g(x)  b ,
x  0 ,

bu yerda
F (x)
maqsad funksiyasini bildiradi. U kasr-chiziqli funksiya orqali

ifodalanadi;

• 
  g(x) shartlar funksiyasi;
  

• 
  b chegaralanish vektori
  

Bu masalaning maqsad funksiyasi chiziqli usulda yozilsa, shartlar tizimi kasr- chiziqli usulda yozilishi mumkin.
Butun sonli dasturlash. Butun sonli dasturlash chiziqli dasturlashning bir ko„rinishidir. Bunda masalaning bajarilishi mumkin bo„lgan shartlariga yana bitta, ya‟ni o„zgaruvchilar faqatgina butun sonli qiymatlarni qabul qilish sharti qo„shiladi. Chunki ayrim masalalarning mohiyatiga ko„ra o„zgaruvchilar faqatgina butun son bo„lgandagina ma‟noga ega bo„ladi. Masalan, avtomobillarning reyslari, korxonani joylashtirish.

3.