Fizika-matematika fakulteti

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
FARG’ONA DAVLAT UNIVERSITETI
FIZIKA-MATEMATIKA FAKULTETI

“Amaliy matematika va informatika” yo’nalishi

18.06-guruh talabasi Otajonova Oyzoda Sodiqjon qizining
“O’yinlar nazariyasi va jarayonlar tadqiqoti” fanidan “Gomorining kesish tekisligi usuli” mavzusidagi


MUSTAQIL ISHI
Qabul qildi: Mamatova Zilola
FARG’ONA 2021-2022
Mavzu: Gomorining kesish tekisligi usuli
Reja:

1. 
   Kirish
   
2. 
   Kesish tekisligi usulining kelib chiqishi
   
3. 
   Gomorining kasr algoritmi
   

KIRISH
Chiziqli dasturlash (LP-linear programming) muammosiga chiziqli tengsizlik cheklovlarini (kesuvchi tekisliklarni) qo'shish konsepsiyasi sayohatchi sotuvchi muammosi bo'yicha ishlarida birinchi marta Dantzig, Fulkerson va Jonson (1954) tomonidan kiritilgan. Ushbu cheklovlar konveks mumkin bo'lgan mintaqaning barcha mumkin bo'lgan nuqtalari bo'lmagan qismlarini samarali ravishda kesib tashlaydi. Keyinchalik Markowitz va Manne (1957) shunga o'xshash yondashuvni taklif qilishdi.
1958 yilda Gomori (1963a) butun sonli dasturlash (IP-integer programming) muammolariga qo'llanilishi mumkin bo'lgan kesmalarni muntazam ravishda yaratadigan birinchi kesish tekisligi algoritmini taqdim etdi. 1960 yilda u IP muammolari uchun butun sonlar jadvalini saqlaydigan ikkinchi kesish tekisligi algoritmini yaratdi (Gomori 1963b). Keyin Gomori (1966) aralash butun sonli dasturlash (MIP-mixed integer programming) muammolarini hal qilish uchun birinchi kesish tekisligi algoritmini kengaytirdi. Bu sohadagi yana bir tadqiqotchi Dantzig (1959) konvergent algoritmga olib kelmaydigan kesimni taklif qilgan. Ushbu algoritmlarning barchasi ikkita kesish tekisligi algoritmlari deb tasniflanadi, chunki ular IP muammolarini LP-relaksatsiyasining optimal yechimiga qo'llanganda ikki tomonlama amalga oshadiganligini saqlab qoladilar.
Kesish tekisligi usulining asosiy g'oyasi juda oddiy. LP-relaksatsiyaning optimal yechimining qiymati (ya'ni, butun son cheklovlarisiz IP muammosi) IP maqsad funksiyasi qiymatining yuqori chegarasi hisoblanadi. Agar bu yechim butun sonni amalga oshirish mumkin bo'lsa, u IP uchun optimal echimdir. Agar LP-relaksatsiyaning optimal yechimi fraksiyonel bo'lsa, biz LP yechim bo'shlig'ining bir qismini, shu jumladan joriy optimal asosiy yechimni kesib tashlaydigan haqiqiy tengsizlikni hosil qilamiz, lekin hech qanday amalga oshirilishi mumkin bo'lgan butun son echimini kesmasdan. Ushbu protsedura butun sonli yechim olinmaguncha joriy LP ga kesmalar qo'shish orqali takrorlanadi.