Butun sonli programmlashtirish masalasi

Butun sonli programmlashtirish masalasi Reja: Sayyox haqidagi masala. Optimal joylashtirish masalasi. Umumiy holda butun sonli programmalash masalasining matematik modeli. Gomori usuli. o'zgaruvchilarga butun sonli bo'lishlik sharti qo'yilgan chiziqli programmalash masalalari katta amaliy ahamiyatga egadir. Bunday masalalar butun sonli programmalash masalalari deb ataladi. Butun sonli programmalash masalalariga sayyox haqidagi masala, optimal jadval tuzish, ratsional bichish, transport vositalarini marshrutlarga optimal taksimlash, bulinmaydigan mahsulot ishlab chikaruvchi korxonaning ishini optimal planlashtirish masalalari kiradi. 1.Sayyox haqidagi masala. Faraz kilaylik, shaharda yashovchi sayyox n ta shaharlarda bir martadan bo'lib, minimal vaqt ichida shaharga kaytib kelishi kerak bulsin. Bu masalaning matematik modelini tuzish uchun savdogarning shahardan shaharga borishi uchun sarf kilgan vaqtini bilan hamda uning xar bir shahardan shaharga borish variantining xarakteristikasini bilan belgilaymiz. Agar savdogar shahardan ga borsa, =1, bormasa =0 bo'ladi. Bu masalaning matematik modeli quyidagi ko'rinishga ega bo'ladi: 2. Optimal joylashtirish masalasi. Faraz kilaylik, m-ta puntklarda bir xil mahsulot ishlab chikaruvchi korxonalarni joylashtirish kerak bulsin. Xar bir korxananing ish quvvatini bildiruvchi butun sonli qiymatlarni kabul qiladi. Xar bir punktda mahsulot ishlab chiqarish uchun sarf qilingan xarajat ishlab chikarilgan mahsulot miqdoriga bog'liq bo'lib, funksiya orqali ifodalanadi. Bu funksiyani chiziqli deb kabul kilamiz. = Bundan tashqari, n-ta punktda bu mahsulot istemol kilinadi. Xar bir istemol qiluvchi punktning mahsulotga bo'lgan talabi mos ravishda birliklarni tashkil qiladi deb faraz kilamiz. Xar bir ishlab chikaruvchi punkt bilan boglangan va transport xarajatlarining matritsasi dan iborat bulsin. punktdan j punktga yuboriladigan mahsulot miqdorini xij bilan belgilaymiz. U holda masalaning matematik modeli kuyidagicha ifodalanadi: chiziqli programmalash masalasining qo'shimcha shartlar bilan beriladigan masalalarni butun sonli programmalash masalasi deb ataymiz. Butun sonli programmalash masalasini umumiy holda quyidagi ko'rinishda ifodalash mumkin: yoki vektor formada AX=b (12) X0 va butun, (13) ymin=CX (14) Butun sonli programmalash masalalaridagi nomalumlarning xammasi uchun butun bo'lishlik sharti kuyilsa, bunday masalalar tulik butun sonli programmalash masalalari, agar ularning malum bir kismi uchungina bu shartlar kuyilsa, kisman butun sonli programmalash masalalari deb ataladi. Agar butun sonli programmalash masalalaridagi nomalumlarda (3) ko'rinishdagi shartlar qo'yilgan bulsa, bunday masala Bul programmalash masalasi deb ataladi. Butun sonli programmalash masalasi chiziqli programmalash masalasidan qo'shimcha (10) ko'rinishdagi shartlar bilan farq qiladi. Bu shartlarning katnashishi butun sonli programmalash masalasini yechish jaraenini qiyinlashtiradi. Natijada chiziqli programmalash masalalarini yechish uchun qo'llaniladigan usullarni butun sonli programmalash masalalariga qo'llash mumkin bulmay koladi. Butun sonli programmalash masalalarini yechish uchun uning xususiyatlarini etiborga oluvchi usullar yaratilgan bo'lib, ulardan amerika olimi R. Gomori yaratgan usul optimal yechimni beruvchi eng aniq usul hisoblanadi. Bu usulning g'oyasi kuyidagidan ...