4-ma’ruza. Butun sonli chiziqli dasturlash. Gomorining kesuvchi tekisliklar usullari Reja

4-ma’ruza. Butun sonli chiziqli dasturlash. Gomorining kesuvchi tekisliklar usullari


Reja:

1. 
   Iqtisodiy masalalar.
   
2. 
   Butun sonli dasturlash masalasining qo’yilishi, turlari va geometrik talqini.
   
3. 
   Butun sonli dasturlash masalasini yechishning Gomori usuli.
   

Tayanch so’z va iboralar: butun sonli dasturlash, to’la butun sonli dasturlash, qisman butun sonli dasturlash, Bul o’zgaruvchili dasturlash, kesuvchi tenglama, Gomori usuli.

O’zgaruvchilariga butun sonli bo’lishlik sharti qo’yilgan chiziqli dasturlash masalalari katta 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 mahsulotlar ishlab chiqaruvchi korxonaning ishini optimal rejalashtirish masalalari misol bo’la oladi. Bu masalalarning ba’zilari bilan tanishamiz.

1. Iqtisodiy masalalar

1. Sayyoh haqidagi masala. Faraz qilaylik, shaharda yashovchi sayyoh, ta ..., shaharlarda bir martadan bo’lib, minimal vaqt ichida shaharga qaytib kelishi kerak bo’lsin. Bu masalaning matematik modelini tuzish uchun savdogarning shahardan shaharga borishi uchun sarf qilgan vaqtini , bilan hamda uning har bir shahardan shaharga borish variantining harakteristikasini bilan belgilaymiz. Agar savdogar shahardan ga borsa, , bormasa bo’ladi (Soddalik uchun va shaharlar faqat bir marshrut yordami bilan bog’langan deb faraz qilamiz). Bu holda masalaning matematik modeli quyidagi ko’rinishda bo’ladi:
(1)
(2)
yoki (3)
(4)