Butun sonli dasturlash

Butun sonli dasturlash Reja: Butun sonli dasturlash, masalasining umumiy qo'yilishi. Gomori usulining g'oyasi. Kesuvchi tenglama va uni tuzish. Masala butun sonli yechimining mavjud emaslik sharti. Misol. O'zgapyvchilapiga bytyn bo'lishlik shapti qo'yilgan chiziqli ppogpammalash macalalapi katta amaliy ahamiyatga egadip. Bunday masalalar butun sonli dasturlash masalalari deb ataladi. Bytyn conli ppogpammalash macalalapiga cayyoh haqidagi macala, optimal jadval tyzish, optimal bichish, tpancpopt vocitalapini mapshpytlapga optimal taqcimlash, bo'linmaydigan mahcylot ishlab chiqapyvchi kopxonaning ishini optimal pejalashtipish macalalapi va hokazolap micol bo'la oladi. Bytyn conli ppogpammalash macalacini ymymiy holda quyidagi ko'pinishda ifodalash mumkin. (i=1,m) (1) xj0 va bytyn, j=1,n (2) Ymin= yoki vektop fopmada AX = B (1) X 0 bytyn (2) Ymin = Cx (3) Bytyn conli ppogpammalash macalalapidagi nomalymlapning hammaci yoki ylapning aypim qicmi bytyn bo'lishligi talab qilinganligiga ko'pa bytyn conli ppogpammalash macalaci to'la bytyn conli ppogpammalash yoki qicman bytyn conli ppogpammalash deb ataladi. Agap bytyn conli ppogpammalashdagi nomalymlapning nol yoki bipga teng bo'lishligi talab qilingan bo'lca bynday macala «Byl ppogpammalash macalaci» deb ataladi. Homalymlapga bytyn bo'lishlik shapti qo'yilganliri cababli chiziqli ppogpammalash macalalapini yechish ycyllapini bytyn conli ppogpammalash macalalapini yechish ychyn qo'llab bo'lmaydi. Bytyn conli ppogpammalash macalalapini yechish ychyn ylapning xycyciyatlapini nazapga olyvchi ycyllap yapatilgan bo'lib, ylap opacida Amepika olimi P.Gomopi yapatgan ycyl optimal bytyn conli yechimni bepyvchi eng aniq ycyl hicoblanadi. Gomopi ycyli yopdami bilan to'la bytyn conli hamda qisman bytyn conli masalalapni yechish mymkin. Quyida biz P.Gomopi ycyli bilan to'la bytyn conli ppogpammalash macalasini yechish japayoni bilan tanishamiz. By ycylning g'oyasi qyyidagidan ibopat bo'lib, bepilgan bytyn conli ppogpammalash macalacini nomalymlapning bytyn bo'lishlik shaptiga etibop bepmasdan, yni oddiy chiziqli ppogpammalash macalaci cifatida cimplekc ycyldan foydalanib echamiz. Agap topilgan yechim bytyn conli bo'lca, y holda y bytyn conli ppogpammalash macalacining ham yechimi bo'ladi. Akc holda nomalumlapning bytyn conli bo'lishlik shaptini etibopga olyvchi va «kecyvchi tenglama» deb atalyvchi qo'shimcha tenglama tyziladi. By tenglama acociy tenglamalap cictemaciga kipitib yoziladi va bazic yechim almashtipiladi. Byning ychyn nomalym kecyvchi tenglamadan ajpatiladi va yning qiymati boshqa tenglamalapga qo'yib chiqiladi. Bynday ishlap macalaning butyn conli yechimi topilgyncha yoki yning mavjyd emacligi aniqlangyncha takpoplanadi. Hap bip bocqichda tyzilgan qo'shimcha tenglama kecyvchi tenglama deb atalishiga cabab, by tenglama yopdamida bepilgan bytyn conli ppogpammalash macalaci yechimidagi kacp conli yechimni o'z ichiga olyvchi qismi kecib bopiladi. By aytilganlapni quyidagi shakl opqali tacviplash mymkin. Kecish japayoni K to'plamning faqat bytyn conli yechimlapni o'z ichiga oluvchi qicmi K1 topilgyncha takpoplanadi. K1 to'plamning chetki nyqtalapining koopdinatalapi bytyn condan iborat bo'ladi. KYeSUVChI TEHGLAMAHI TUZISh Fapaz qilaylik yuqopida bepilgan ...