Fizika-matematika fakulteti

Kesish tekisligi usulining kelib chiqishi
Tarixiy jihatdan, butun sonli dasturlash muammosini hal qilishning birinchi usuli kesish tekisligi usuli edi. Bu usul haqiqiy butun sonli dasturlash modeli uchun xizmat qiladi.
Jarayon, birinchi navbatda, butun son shartlariga e'tibor bermaslik va muammoni oddiy chiziqli dasturlash muammosi sifatida hal qilishdir.
Agar yechim butun son cheklovlarini qanoatlantirsa, u holda asl masala uchun optimal yechim topiladi. Aks holda, har bir iteratsiyada asl muammoga qo'shimcha cheklovlar qo'shiladi. Ushbu cheklashlar har bir ketma-ket iteratsiyada yechim maydonini qisqartirish yoki kesish uchun qo'shiladi, joriy kasrli yechimni istisno qiladi, shu bilan birga jarayonda butun sonli yechim istisno qilinmasligini ta'minlaydi. Butun qiymat olingandan keyin usul tugaydi. Ushbu usulda chekli miqdordagi iteratsiyalarda konvergensiya (yaqinlashish) kafolatlanadi.
Matematik optimallashtirishda kesish tekisligi usuli - bu kesimlar deb ataladigan chiziqli tengsizliklar yordamida amalga oshirilishi mumkin bo'lgan to'plam yoki obyektiv funksiyani takroriy aniqlaydigan har qanday optimallashtirish usullaridir. Bunday protseduralar odatda aralash butun sonli chiziqli dasturlash (MILP) muammolarining butun sonli yechimlarini topish uchun, shuningdek, umumiy, har doim ham farqlanmaydigan, qavariq optimallashtirish masalalarini hal qilish uchun ishlatiladi. MILP yechimi uchun kesish tekisliklaridan foydalanish Ralf E. Gomori tomonidan kiritilgan.
Butun sonli chiziqli dasturni, berilgan butun sonli dasturning chiziqli relaksatsiyasini yechish orqali MILP ishi uchun kesish tekisligi usullari. Chiziqli dasturlash nazariyasi shuni ko'rsatadiki, yengil taxminlar ostida (agar chiziqli dastur optimal yechimga ega bo'lsa va amalga oshirilishi mumkin bo'lgan mintaqada chiziq bo'lmasa) har doim optimal bo'lgan ekstremal nuqta yoki burchak nuqtasini topish mumkin. Olingan optimal butun sonli yechimekanligi tekshiriladi. Aks holda, haqiqiy amalga oshirilishi mumkin bo'lgan to'plamning optimalni qavariq korpusidan ajratib turadigan chiziqli tengsizlikning mavjudligi kafolatlanadi. Bunday tengsizlikni topish ajratish masalasi, bunday tengsizlik esa kesma hisoblanadi. Qulay chiziqli dasturga kesma qo'shilishi mumkin. Shunda joriy butun son bo'lmagan yechim endi yo'q. Bu jarayon optimal butun yechim topilguncha takrorlanadi.
Kesish tekisliklari 1950-yillarda Ralf Gomori tomonidan butun sonli dasturlash va aralash butun sonli dasturlash masalalarini yechish usuli sifatida taklif qilingan. Biroq ko'pchilik ekspertlar, shu jumladan Gomorining o'zi ham raqamli beqarorlik tufayli ularni amaliy emas, shuningdek samarasiz, chunki yechimga erishish uchun ko'plab qisqartirishlar kerak edi. 1990-yillarning oʻrtalarida Jerar Kornuyeyols va hamkasblari ularni tarmoq va bogʻlanish (tarmoq va kesish deb ataladi) hamda raqamli beqarorliklarni bartaraf etish usullari bilan birgalikda juda samarali ekanligini koʻrsatishganda, vaziyat oʻzgardi. Hozirgi kunda barcha tijoriy MILP hal qiluvchilar Gomori kesmalaridan u yoki bu tarzda foydalanadi. Gomori kesmalari simpleks jadvalidan juda samarali tarzda yaratiladi, boshqa ko'plab turdagi kesishlar esa qimmat yoki hatto NP-ni ajratish qiyin. MILP uchun boshqa umumiy qisqartirishlar orasida, ayniqsa, ko'tarilish va loyiha Gomori qisqartirishlarida ustunlik qiladi.

Birlik kubining kesish tekisligi bilan kesishishi. Uchta tugundagi sayohatchi sotuvchi muammosi konteksida bu (ancha zaif) tengsizlik har bir turning kamida ikkita chetiga ega bo'lishi kerakligini bildiradi.

Butun sonli dasturlash masalasi (kanonik shaklda) quyidagicha shakllantirilsin:

Usul birinchi navbatda ning butun son bo'lishi talabini bekor qilish va asosiy mumkin bo'lgan yechimni olish uchun tegishli chiziqli dasturlash muammosini hal qilish orqali davom etadi. Geometrik jihatdan, bu yechim barcha mumkin bo'lgan nuqtalardan tashkil topgan qavariq politopning cho'qqisi bo'ladi. Agar bu cho'qqi butun nuqta bo'lmasa, usul cho'qqisi bir tomonda, barcha mumkin bo'lgan butun nuqtalari boshqa tomonda joylashgan gipertekislikni topadi. Keyinchalik, bu topilgan cho'qqini chiqarib tashlash uchun qo'shimcha chiziqli cheklov sifatida qo'shiladi va o'zgartirilgan chiziqli dasturni yaratadi. Keyin yangi dastur yechiladi va jarayon butun sonli yechim topilguncha takrorlanadi.
Chiziqli dasturni yechish uchun simpleks usulidan foydalanib, shaklning tenglamalari to'plami hosil bo'ladi

Bu yerda - asosiy o'zgaruvchi va - asosiy bo'lmagan o'zgaruvchi. Ushbu tenglamani butun sonlar chap tomonda, kasr qismlari o'ng tomonda bo'lishi uchun qayta yoziladi:

Mumkin mintaqadagi har qanday butun nuqta uchun bu tenglamaning o'ng tomoni 1 dan kichik, chap tomoni esa butun son, shuning uchun umumiy qiymat 0 dan kichik yoki teng bo'lishi kerak. Demak, tengsizlik

mumkin bo'lgan mintaqadagi har qanday butun nuqta uchun tutilishi kerak. Bundan tashqari, har qanday asosiy yechimda asosiy bo'lmagan o'zgaruvchilar 0 ga teng va agar asosiy yechim uchun butun son bo'lmasa,

Shunday qilib, yuqoridagi tengsizlik asosiy mumkin bo'lgan yechimni istisno qiladi va shuning uchun kerakli xususiyatlarga ega bo'lgan kesimdir. Ushbu tengsizlik uchun yangi o'zgaruvchisini kiritib, chiziqli dasturga yangi cheklov qo'shiladi, ya'ni

Kesish tekisligi usullari chiziqli bo'lmagan dasturlashda ham qo'llaniladi. Asosiy prinsip – chiziqli bo'lmagan (qavariq) dasturning mumkin bo'lgan mintaqasini cheklangan yopiq yarim bo'shliqlar to'plamiga yaqinlashtirish va chiziqli dasturlarni yaqinlashish ketma-ketligini hal qilish.