Fizika-matematika fakulteti

1-qadam: Ishga tushirish
Chiziqli dasturlash relaksatsiyasini hal qiling. Agar buni amalga oshirish imkonsiz bo'lsa, IP muammosi - tugatish. Aks holda 2-bosqichga o'ting.
2-qadam: Optimallik testi
Agar chiziqli dasturlash relaksatsiyasining optimal yechimi butun son bo'lsa, IP-ni tugatish optimaldir. Aks holda 3-bosqichga o'ting.
3-qadam: Kesish va asosiy nuqta atrofida aylanish
bilan qatorni tanlang va simpleks jadvalining pastki qismiga kasr kesimi yoki cheklovni (8) qo'shing.
4-qadam: Qayta optimallashtirish
Dual simpleks usuli yordamida yangi chiziqli dasturlashni qayta optimallashtiring. Agar yangi chiziqli dasturlash muammosini hal qilish imkonsiz bo'lsa, butun sonli dasturlashda hech qanday yechim yo'q - tugatish. Agar yangi optimal butun sonni amalga oshirish mumkin bo'lsa, IP hal qilinadi - tugatish. Aks holda 2-bosqichga o'ting.
Har bir qo'shilgan tengsizlikni uning bo'sh o'zgaruvchisi asosiy o'zgaruvchilar to'plamiga qayta kirgandan so'ng darhol olib tashlash standart amaliyotdir. Ya'ni, yangi tengsizlik kiritilganda u aylanma qator sifatida ishlatiladi, shuning uchun uning bo'shligi asossiz bo'ladi. Ushbu bo'sh o'zgaruvchi asosiy to'plamga qaytsa, u va uning aniqlovchi qatori o'tkazib yuboriladi. Jadvalda har doim n ta asosiy bo'lmagan o'zgaruvchilar mavjud. Demak, agar bu qoidaga amal qilinsa, algoritmning istalgan bosqichida hech qachon n dan ortiq kesmalar bo'lmaydi.
Algoritmning chekli takrorlanishlar sonidan keyin optimal yechimga yaqinlashishi uchun obyektiv funksiyasining qiymati uchun qandaydir quyi chegara ma’lum bo‘lishini ta’minlash kerak, shuningdek, chekli algoritmni qo‘llab-quvvatlash uchun manba qatorini tanlash ham muhimdir. Manba qatorini tanlashda maqsad nisbati imkon qadar katta bo'lgan tengsizlikni hosil qilishdir, chunki nisbatning qiymati qanchalik katta bo'lsa, kesim kuchliroq bo'ladi. Geometrik jihatdan nisbati har bir o'qi bilan uning chegarasidagi (nol qiymatli passiv o'zgaruvchisi bilan) kesmaning (8) kesishish nuqtasi sifatida qaralishi mumkin. Salkin va Mathur (1989) tomonidan taklif qilingan klassik qoida eng katta kasr komponentli qatordan tengsizlikni hosil qilishdir.
Jenkins va Peters (1987) manba qatorini tanlashga ko'ra olingan turli Gomori kesmalarini sanab o'tdi. O'z hisobotlarida ular umumiy IP muammolarini hal qilish uchun Maksimal nisbat deb nomlanuvchi kesishni tavsiya qildilar. Bu Gomorining kasr kesimi bo'lib, manba qatori mavjud qator sifatida
(9)