Identifikatsiyalash

3.2. Butun sonli programmalash masalasini echish uchun Gomori usuli
Amaliyotda koʻpgina masalalarni yechishda oʻzgaruvchilarga butunlik sharti qoʻyiladi. Bu esa oʻz navbatida masalani yechishda murakkablik hosil qiladi. Bunday masalalarni yechishning turli usullari mavjud. Ularga Gomori usuli, shoxlar va chegaralar usuli kabilar kiradi. Butun sonli programmalash masalalarini echish uchun uning xususiyatlarini e’tiborga oluvchi usullar yaratilgan boʻlib, ulardan amerika olimi R.Gomori yaratgan usul optimal echimni beruvchi eng aniq usul hisoblanadi. R.Gomori toʻlik butun sonli va qisman butun sonli programmalash masalalarini echish usullarini yaratgan. Butun sonli programmalash masalasi chiziqli programmalash masalasidan qoʻshimcha shartlar bilan farq qiladi. Bu shartlarning qatnashishi butun sonli programmalash masalasini echish jarayonini qiyinlashtiradi. Natijada chiziqli programmalash masalalarini echish uchun qoʻllaniladigan usullarni butun sonli programmalash masalalariga qoʻllash mumkin boʻlmay qoladi. Gomori usulining mohiyatini koʻrib chiqamiz. Bunda dastlab butunlilik shartiga ahamiyat berilmasdan Simpleks usuli yordamida programmalashtirish masalasi yechiladi. Agar hech boʻlmaganda biron bir oʻzgaruvchining qiymati butun boʻlmasa, unga nisbatan qoʻshimcha kesuvchi tenglama tuziladi va yana Simpleks usuli qoʻllaniladi. Bu jarayon barcha oʻzgaruvchilarning qiymati butun boʻlgunga qadar davom etadi. Gomori usuli qoʻllanilganda sonlarning kongurentlik va kasr qismi tushunchasi ishlatiladi.
Kongurentlik “≡” belgisi bilan belgilanadi. a soni b soniga kongurent boʻladi, agarda ularning farqi (a-b) butun boʻlsa. Masalan, .
Sonning kasr qismi deb, eng kichik nomanfiy son bilan aniqlanuvchi songa aytiladi. Masalan,
, .
Kongurentlikning quyidagi xossalari mavjud.
1. Agar a≡b boʻlsa, ularning kasr qismlari ham kongurentdir.
{a}≡{b}.
2. Ikki son yigʻindisining kasr qismi har bir son kasr qismlarining yigʻindisiga teng.
{a+b}≡{a}+{b}.
3. Agar n butun son boʻlsa, uning kasr qismi quyidagicha boʻladi:
{n∙a}≡n{a}.
Gomori usulida masalani yechish algoritmini koʻrib chiqamiz. Masala Simpleks usuli yordamida yechiladi. Agar optimal yechim butun boʻlmasa, u holda eng katta kasr qismi oʻzgaruvchili tenglamadan bazis oʻzgaruvchisi tanlab olinadi va unga nisbatan kesuvchi tenglama tuziladi.
.
Butunlilik shartiga koʻra ushbu tenglamani quyidagicha yozish mumkin.
yoki .
- butun boʻlgani uchun
.
Bu tengsizlik qoʻshimcha ravishda jadvalga kiritiladi va Simpleks usuli qoʻllaniladi.