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

Nazorat uchun savollar

1. 
   Qaysi hollarda ko„p bosqichli diskret dasturlash masalalari yechiladi va buning sababi nimada?
   
2. 
   Chiziqli dasturlash masalasidan diskret dasturlash masalasining asosiy farqlari nimada?
   
3. 
   Diskret dasturlash masalalarining maqsad funksiyalari qanday ko„rinishda bo„ladi?
   
4. 
   Kommivoyajer masalasini tushuntirib bering?
   
5. 
   Kombinator masalalariga misol keltiring.
   

6. BOB

BUТUN SONLI DASТURLASHNING MAТEMAТIK MODELLARI

7.1. Sayyoh haqidagi masala

O„zgaruvchilarga butun sonli bo„lishlik sharti qo„yilgan chiziqli dasturlash masalalari katta amaliy ahamiyatga egadir. Bunday masalalar butun sonli dasturlash masalalari deb ataladi. Butun sonli dasturlash masalalariga sayyoh haqidagi masala, optimal jadval tuzish, ratsional bichish, transport vositalarini marshrutlarga optimal taqsimlash, bo„linmaydigan mahsulot ishlab chiqaruvchi korxonaning ishini optimal rejalashtirish masalalari kiradi.

1. 
   Sayyoh haqidagi masala. Faraz qilaylik, P_ shaharda yashovchi sayyoh n ta
   

P₁ , P₂ ,..., P_n
shaharlarda bir martadan bo„lib, minimal vaqt ichida P_ shaharga qaytib

kelishi kerak bo„lsin. Bu masalaning matematik modelini tuzish uchun sayyohning

P_i shahardan P_j shaharga borishi uchun sarf qilgan vaqtini t_ij ,(i  1,n; j  1,n)
bilan

hamda uning har bir P_i shahardan P_j shaharga borish variantining xarakteristikasini x_ij bilan belgilaymiz. Agar sayyoh P_i shahardan P_j ga borsa, x_ij =1, bormasa x_ij =0 bo„ladi. Bu masalaning matematik modeli quyidagi ko„rinishga ega bo„ladi:


n
x_ij  1, (i  1, n)
j1
(7.1)

x_ij  0



_ x_ij  1, ( j  1, n)
i1

ѐки
x_ij  1,

(7.2)

(7.3)

n n

^ymin ^{ t}ij ^xij
(7.4)

i1 j1

2) Optimal joylashtirish masalasi. Faraz qilaylik, m-ta А₁, А₂ ,..., А_m
puntklarda

bir xil mahsulot ishlab chiqaruvchi korxonalarni joylashtirish kerak bo„lsin. Har bir

korxananing ish quvvatini bildiruvchi x_i ,(i  1,m)

butun sonli qiymatlarni qabul

qiladi. Har bir А_i punktda mahsulot ishlab chiqarish uchun sarf qilingan xarajat

ishlab chiqarilgan mahsulot miqdoriga bog„liq bo„lib, f_i (x_i ) funksiya orqali ifodalanadi. Bu funksiyani chiziqli deb qabul qilamiz.