Fizika-matematika fakulteti

Gomorining kasr algoritmi
Sof butun sonli dasturlash (PIP-pure integer programming) muammolarini hal qilish uchun Gomori (1963a) tomonidan kiritilgan birinchi kesish tekisligi algoritmi Gomorining kasr kesimlari deb nomlanadi, chunki hosil qilingan kesimlarning nolga teng bo'lmagan barcha koeffitsiyentlari birdan kichikdir. U ba'zan butun son shakli usuli deb ataladi. Bu, shuningdek, chekli konvergent ekanligi isbotlangan birinchi kesish tekisligi algoritmidir.
Sof butun sonli dasturlash muammosini ko'rib chiqish:
(1)
bu yerda ma'lumotlar integral bo'lishi talab qilinadi (cheklovlar kasrlardan tozalanadi) obyektiv funksiya qiymati va passiv o'zgaruvchilar har qanday butun sonli yechim uchun integral bo'lishini ta'minlash.
Gomorining kasr kesimlarini quyidagicha olish mumkin. Faraz qilaylik, bizda to'liq bo'lmagan chiziqli dasturlash relaksatsiyasining optimal yechimi bor. Butun son bo'lmagan yechimning p-qatorini ko'rib chiqamiz. Buni quyidagicha ifodalash mumkin
(2)
Bu yerda J - asosiy bo'lmagan o'zgaruvchilar to'plami, uni quyidagicha yozish mumkin
(3)
Bu yerda va y dan kichik yoki teng bo'lgan eng kattasini bildiradi.
Buni qayta tartibga solish mumkin
(4)
va shuni hisobga olib,
(5)
Shunday qilib
(6)
Barcha o'zgaruvchilar butun son bo'lishi talab qilinganligi sababli, (4) tenglamaning chap tomoni butun son bo'ladi, shuning uchun o'ng tomoni ham butun son bo'lishi kerak. Shunday qilib, (6) ning chap tomoni butun son bo'lishi kerak va shuning uchun
(7)
va shaklda yozilishi mumkin
(8)
bu yerda manfiy bo'lmagan butun son passiv o'zgaruvchidir. Bu butun sonli dasturlash muammolarini hal qilish uchun Gomori tomonidan kesilgan. Tegishli chiziqli dasturlash muammosining optimal jadvaliga yangi cheklov (8) ni qo'shish dual simpleks usuli yordamida hal qilinishi mumkin bo'lgan birlamchi bajarib bo'lmaydigan muammoga olib keladi.
Gomorining kasrli kesimlari uchun asosiy algoritm quyidagicha: