Sun'iy bazis vektor usuli

Cuniy bazis vektor usuli Reja: Masalani normal formaga keltirish Simpleks jadval tuzish Bazis yechimini yozish. Tayanch yechim aniqlash yechim yuklik shartlarini tekshirish. Tayanch yechimni optimallikka tekshirish chiziqli programmalash masalasining boshlang'ich tayanch plani mavjud va boshlang'ich planni tuzish mumkin buladigan m-o'lchovli birlik matritsa masala shartida katnashadi deb faraz kildik. Bu birlik matritsa erdami bilan optimal planga utishga erdam beradigan planni tuzish mumkin. Agar chiziqli programmalash masalasining chegaraviy shartlari AXR0 ko'rinishda berilgan bulsa, qo'shimcha o'zgaruvchilar kiritish mumkin. Amalda uchraydigan ko'p chiziqli programmalash masalalari planga ega bo'lgan holda birlik matritsani o'z ichiga olmaydi. Bunday masalalarni yechish uchun «sun'iy bazis vektor» usul kullaniladi. Umumiy holda berilgan chiziqli programmalash masalasini kuramiz: a11x1+a12x2++ a1nxn=b1, a21x1+a22x2++ a2nxn=b2, am1x1+am2x2++ amnxn=bm x10, x20,, xn0 umin=c1x1+ c2x2++ cnxn masalaning shartiga birlik matritsani kiritish uchun sistemadagi xar bir tenglamaga sun'iy o'zgaruvchi deb ataluvchi xn+i 0 nomalumni mos ravishda kushamiz, hamda umin=c1x1+ c2x2++ cnxn+M(xn+1++ xn+m) funksiyani minimallashtirish bilan bog'liq bo'lgan quyidagi kengaytirilgan masalani hosil kilamiz: a11x1+a12x2++ a1nxn +xn+1=b1, a21x1+a22x2++ a2nxn+ xn+2=b2, am1x1+am2x2++ amnxn+ xn+m=bm x10, x20,, xn0, xn+10, xn+m0 umin=c1x1+ c2x2++ cnxn +M(xn+1++ xn+m) Berilgan masalaning optimal yechimini topish uchun quyidagi teoremadan foydalanamiz. Teorema. Agar kengaytirilgan masalaning X=(x1, x2,,xn,xn+1,,xn+m) optimal planida xn+i =0 () bulsa, X=(x1, x2,,xn) plan berilgan masalaning optimal plani bo'ladi. Kengaytirilgan masalaning optimal planini topish uchun yuqoridagi simpleks jadvaldan qo'shimcha m+2 katori bilan farq qiluvchi simpleks jadvaldan foydalaniladi. Jadvalning (m+1) va (m+2) -katorini tuldirish uchun yj-cj ayirmani yj-cj=j+jM ko'rinishda ifodalanadi. Bazisga (m+2)- katorning musbat elementlarining eng kattasi mos keluvchi vektor kiritiladi. Xamma sun'iy bazis vektorlar bazisdan chikarilguncha (m+2)- katordan sungra, optimal plan topilgunga qadar (m+1)- katordan foydalaniladi. Masalani simpleks usul kullab yechish jarayonida m+2 - katordagi koeffitsiyentlarning barchasi manfiy bulsa, masala optimal yechimga ega bulmaydi yoki max j ustunda birorta xam musbat element katnashmasa, berilgan chiziqli programmalash masalasining bazis yechimi mavjud bo'lishi mumkin, optimal yechimi mavjud bulmaydi. Simpleks usul algoritmi bu holda xam takrorlanadi. Buni misolda tushuntirish va sun'iy bazis usulini afzalliklarini ko'rsatish kerak. Bu talabalarga mustaqil ishlash uchun koldirildi. mustaqil yechishga doir masalalalar quyidagi chiziqli programmalash masalasi echilsin. 1. 2. 3. 4. Adabiyotlar: N.R.Beknazarova, X.N.Jumaev Matematik programmalashtirish va optimallashtirish O'quv predmeti bo'yicha O'quv-uslubiy majmua (Bakalavriat bosqichi talabalari uchun).Tashkent 2006. Safaeva K. va boshqalar. Matematik programmalashdan ma'ruza mantlari. T., TDMI, 2003y. V.V.Rozen. Matematicheskie modeli prinyatiya resheniy v ekonomike. M. 2002. Matematicheskoe programmirovanie v ekonomike. Pod red. Kremera, M., Finansi i statistika, 1996g. K.Safaeva, F.Shomansurova. Matematik programmalashtirishdan masalalar to'plami. T., Moliya instituti, 2003y. V.Sh.Kremer i dr. Issledovaniy operatsiy ...