Tmc institute in Tashkent

TMC Institute in Tashkent

guruh: 22-05

Bajardi: Bardibayev ulug’bek

Tekshirdi: xodjamurotova indira

Mavzu: Butun sonli dasturlash masalasining qo’yilishi. Reja: 1. Butun sonli dasturlash masalasining qo’yilishi.Shoxlar va chegaralar usuli.
2.Transport masalasi
3. Chiziqli dasturlashda optimallashtirish masalasi
Butun sonli dasturlash va uni yechish usuli O‘zgaruvchilarga butun sonli bo‘lishlik sharti qo‘yilgan chiziqli dasturlash masalalariga butun sonli dasturlash masalasi deyiladi. Butun sonli dasturlash masalalariga sayyoh haqidagi masala, optimal jadval tuzish, transport vositalarini marshrutlashni optimallash, optimal joylashtirish masalasi va hokazolarni misol qilish mumkin.
Butun sonli dasturlash masalasi chiziqli dasturlash masalasidan qo‘shimcha shartlar bilan farq qiladi. Bu shartlarning qatnashishi butun sonli dasturlash masalasini yechish jarayonini qiyinlashtiradi. Natijada chiziqli dasturlash masalalarini yechish uchun qo‘llaniladigan usullarni butun sonli dasturlash masalalariga qo‘llash mumkin bo‘lmay qoladi. Gomori usuli. Butun sonli dasturlash masalalarini yechish uchun uning xususiyatlarini e'tiborga oluvchi usullar yaratilgan bo‘lib, ulardan amerikalik olim R.Gomori yaratgan usul optimal yechimni beruvchi eng aniq usul hisoblanadi. Bu usulning g‘oyasi quyidagidan iborat. Berilgan butun sonli dasturlash masalasida noma'lumlarning butun bo‘lishlik shartiga e'tibor bermasdan, ularni oddiy chiziqli dasturlash masalasi sifatida simpleks usuldan foydalanib yechamiz.
Agar yechim butun sonlardan iborat bo‘lsa, u butun sonli dasturlash masalasining ham yechimi bo‘ladi. Aks holda noma'lumlarning butun bo‘lishlik shartini e'tiborga oluvchi va "kesuvchi tenglama" deb ataluvchi qo‘shimcha tenglama tuziladi
Kesuvchi tenglamani tuzish. 1.Aytaylik, masaladagi sonlarning butun bo‘lishlik sharti tashlab yuborishdan hosil bo‘ladigan masala yechilgan va uning optimal yechimi mavjud bo‘lsin. Agar barcha x lar butun sonlar bo‘lsa, topilgan yechim butun sonli dasturlash masalaning yechimi bo‘ladi. 2.Faraz qilaylik, ba'zi x lar kasr sonlardan iborat bo‘lsin, ya'ni simpleks jadvaldagi ozod hadlar ustuni qiymatlari ichida kasr sonlar ham mavjud bo‘lsin. Ularning butun kismlarini [x] bilan belgilaymiz. U holda bu sonlarning kasr qismlari q lar quyidagicha aniqlanadi
qi=xi-[xi], qij=aij-[aij]. Faraz qilaylik, ba'zi qi≠0 bo‘lsin. U holda, simpleks jadvalning tenglikni qanoatlantiruvchi k qatori uchun kesuvchi tenglama tuziladi. Buning uchun avval qk1x1+ qk2x2+ …+ qknxn≥qk tengsizlik tuziladi, so‘ngra uni (-1) ga ko‘paytirib, xn+1 qo‘shimcha o‘zgaruvchi kiritiladi. -qk1x1- qk2x2- …- qknxn + xn+1=qk . Bunday tuzilgan tenglama kesuvchi tenglama deyiladi. 3.Kesuvchi tenglamani simpleks jadvalning m+2 qatoriga joylashtiramiz va simpleks almashtirishlarni bajaramiz. Agar hosil bo‘lgan yangi simpleks jadvalda barcha xi lar butun sonli (ya'ni hamma qi=xi-[xi]=0) bo‘lsa, topilgan yechim berilgan butun sonli dasturlash masalasining yechimi bo‘ladi. Aks holda yuqoridagi 2 va 3 punktlar yana takrorlanadi. Umuman bu jarayon masalaning butun sonli yechimi topulguncha yoki masalaning butun sonli yechimi mavjud emasligi aniqlanguncha takrorlanadi.