Chiziqli bul dasturlash modellari

chiziqli bul dasturlash modellari Reja: 1. Bul o'zgaruvchili chiziqli diskret optimallashtirish modellari 2. Diskret o'zgaruvchili masalarni bul o'zgaruvchili masalalarga o'zgartirish. 3.chiziqli bul dasturlash masalasini nochiziqli bul masalasiga o'zgartirish. 1.Bul o'zgaruvchili chiziqli diskret optimallashtirish modellari ; Bul o'zgaruvchili chiziqli maqsad funksiyani va chiziqli chegarali optemallashtirish masalasi diskret dasturlash modellarni eng keng tarkalgan masalalaridan biridir. Bul o'zgaruvchili nol va bir qiymatlar kabul qiluvchi kombinatorika masalalari iqtisodiyotning turli amaliy muammolarini yechishda ,loyihalashda , boshqarishda va boshqa sohalarda ko'llaniladi.Bul o'zgaruvchili chiziqli maqsad funksiyali va chiziqli chegarali optemallashtiriish (minimallashtirish va maksimallashtirish) masalalari umumiy holda quyidagi chiziqli bul dasturlash modellari bilan yoziladi. I . A- modeli , minimallashtirish masalasi uchun (1) (2) 2. B -modeli , maksimallashtirish masalasi. (3) (4) yani bul o'zgaruvchili xj0,1 chiziqli maqsad funksiyasi chiziqli tengsizliklar sistemasi (2) yoki (4) bajarilganda minimallashtirish yoki maksimallashtirish talab etiladi. yuqoridagi masalalarni (1) , (2) yoki (3),(4) yechimini topish muammosini to'la sinash usuli yordamida yechish mumkin. Bu mohiyati shundan iboratki, berilgan uzunlikdagi bul vektorlarni to'la tekshirish , xar vektor uchun chiziqli chegaralarni bajarilishini tekshirish va bu mumkin bo'lgan vektorlarni ichidan maqsad funksiyasini minimumni yoki maksimumni taminlovchi vektorni topishdan iborat . Ammo to'la sinash usuli bilan yechimni topish katta xajmdagi hisoblashlarni talab etadi va katta o'lchamdagi masalalarni yechish katta unumdorlikka ega EXM larda amalga oshirish mumkin emas . Xar bir o'zgaruvchi fakat 2 ta qiymat (0 va 1) kabul kilganligi sababli bul vektorlarini umumiy soni (n uzunlikdagi) 2n ga teng. Bu kattalik to'la sinash usulini algoritmini murakkab ekanligini xarakterlaydi. Ko'pgina diskret optimallashtirish masalalarida to'la sinash usulini ko'llash samara bermaydi . Shuning uchun , turli yakkol bo'lmagan sinash usullaridan foydalaniladi. Bu usullar xamma bul vektorlarini to'la ko'rib chikmasdan aniq yechim topish imkonini beradi. Bunday usullardan misol sifatida kesish usulini , shoxlar va chegaralar usulini , dinamik dasturlash usullarini keltirish mumkin.Masalalarni o'lchamlarini n ortishi murakkab yechimli , yani amaliy nuqtai nazardan echib bo'lmaydigan masalaga kalayapti. Masalalarni (1),(2) yoki (3),(4) ko'pgina kombinatorli optimallashtirish masalalari singari murakkab yechimli yoki NP (no polynomial)-to'la masalalarga tegishli masaladir. Bunga sabab , masalani o'lchamiga polinomalar vaqt bo'yicha chegaralanish bilan yechish algoritmlari mavjud emas. Shu sababli , bul o'zgaruvchili chiziqli dasturlash masalalarini yani samarali usullarini ishlab chiqish bo'yicha tadqiqotlar dolzarbdir. 2.Diskret o'zgaruvchili masalalarni bul o'zgaruvchili masalalarga o'zgartirish. Faraz kilaylik , x diskret o'zgaruvchili bo'lib, fakat butun qiymatlar 0,1,2,,k kabul kilsin.Unda bu o'zgaruvchini bul o'zgaruvchilarini y0, y1,,yp chiziqli kombinatsiyasi (p+1) shaklid a ifodalash mumkin , yani , (1) bu yerda p- -esa kuydagi shartni kanoatlantiruvchi butun son Misol ...