Fizika-matematika fakulteti

Gomorining kasr algoritmining ko'rinishi:
1-misol:

Yechim:
Chiziqli dasturlash relaksatsiyasi optimal yechimi

Ushbu misolda manba qatorini tanlash eng katta kasrli qatorni tanlash orqali amalga oshiriladi. Ushbu IP muammosini hal qilish uchun uchta kesish kerak. Jadvalda chiquvchi o'zgaruvchini va kiruvchi o'zgaruvchini ko'rsatadi. Ikki marta chizilgan element aylanma elementni bildiradi.
1-jadval: Chiziqli dasturlash relaksatsiyasi uchun optimal jadval

2-jadval:

3-jadval:

asosga kirgandan so'ng jadvaldan va tegishli qatorni o'chirib tashlashimiz mumkin.
4-jadval:

Bu IP uchun optimal yechimni beradi, chunki uchun barcha o'zgaruvchilari butun sonlar, ya'ni va obyektiv funksiyasi qiymati 14 ga teng.
Grafik jihatdan biz ushbu misolni quyidagicha tasvirlashimiz mumkin:

Xulosa
Butun sonli dasturlash (IP) muammolari ularga qo'yilgan butun son cheklovlari tufayli ularni hal qilish qiyin. Ushbu muammolarni hal qilish usuli - bu kesish tekisligi usuli. Bu usulda chiziqli cheklovlar butun sonli optimal yechim topilmaguncha, tegishli chiziqli dasturlash (LP) masalasiga qo'shiladi. Ushbu cheklovlar LP yechim maydonining bir qismini kesib tashlaydi, lekin hech qanday mumkin bo'lgan butun son echimini yo'q qilmaydi. Ushbu hisobotda Gomori va Dantzig tufayli IP-ni hal qilish algoritmlari keltirilgan. Yana ikkita kesish tekisligi yondashuvi va Gomori algoritmining ikkita kengaytmasi ham muhokama qilinadi. Ushbu usullar matematik jihatdan oqlangan bo'lsa-da, ular sekin konvergensiyaga va portlovchi saqlash talabiga ega ekanligi ma'lum. Natijada, kesish tekisliklari odatda hisoblashda muvaffaqiyatli emas.
Ushbu mustaqil ishda umumiy IPni hal qilish uchun Gomori algoritmi keltirilgan va muhokama qilindi.
Yuqoridagi sharhda eslatib o'tilgan kesish tekisligi yondashuvlari odatda hisoblashda muvaffaqiyatsiz deb topildi. Buning sabablaridan ba'zilari:

• 
  Oldindan qayta ko'rib chiqilgan simpleks kodlari ma'lumotlar tuzilmalariga ega edi, ular matritsa ma'lumotlarini ustunlar tartibida ko'rsatishni talab qiladi. Ushbu formatda kesish tekisligi cheklovlarini qo'shish qiyin edi.
  
• 
  Ko'rib chiqilayotgan kesish tekisliklari nolga teng bo'lmagan koeffitsiyentlarning yuqori zichligiga ega ekanligi ma'lum va shuning uchun portlovchi saqlash talabiga olib keladi va real hayotda keng ko'lamli LP va IP muammolarida keng tarqalgan siyraklikni yo'q qiladi. Qayta ko'rib chiqilgan simpleks usuli bu siyraklikdan foydalanadi va bu katta muammoni hal qilishga imkon beradi.
  
• 
  Kesish tekisligi usullari odatda sekin konvergensiyaga ega ekanligi aniqlangan. Shunday qilib, odatda ko'plab kesishlarni qo'shish talab qilinadi, bu nafaqat hal qilish vaqti, balki muammoning hajmi bilan bog'liq muammolarni ham keltirib chiqaradi.
  

Gomorining kasr algoritmini amalga oshirishdagi asosiy hisoblash qiyinligi iteratsiyalar sonidan emas, balki kompyuter arifmetikasidagi raqamli xatolardan kelib chiqqan. Simpleks arifmetika davom etar ekan, hisoblangan qiymatlarning eng kam ahamiyatli qismlari, ya'ni simpleks jadvalidagi koeffitsiyentlarning kasr qismlari, tabiiyki, xatolarni o'z ichiga olishi mumkin. Boshqacha qilib aytganda, algoritm yaxlitlash xatolaridan aziyat chekadi. Buni bartaraf etish uchun butun sonli algoritmlar taklif qilindi. Biroq, ma'lumki, barcha butun son algoritmlari (ushbu yondashuvga kiritilgan barcha butun son cheklovlari tufayli) Gomorining kasrli kesish algoritmiga qaraganda kuchsizroqdir. Hisoblash sinovlari cheklangan bo'lsa-da, umuman olganda, qanoatlantirmadi.