Tayanch yechimning optimallik sharti. Chekli optimal yechimning mavjud bo'lmaslik sharti

Tayanch yechimning optimallik sharti chekli optimal yechimning mavjud bo'lmaslik sharti Reja: Simpleks usuli g'oyasi va uni yaratuvchilar. Eydelnant usuli. Jordan-Gauss usuli jadvallari. Optimal yechimni hosil qilish. Yangi tayanch yechimga o'tish qoidasi. Chiziqli dasturlash masalalarini yechish uchun ishlatiladigan eng universal usullardan biri simpleks usuldir. Bu usul yordamida iqtisodiy masalalarning yechimi topiladi yoki yechim mavjud emasligi aniqlanadi. Simpleks usulning g'oyasi quyidagidan iborat. Berilgan chiziqli dasturlash masalalarining yechimlar to'plamiga tegishli ixtiyoriy boshlang'ich (tayanch) yechimi topiladi, yani AX=B, x 0 shartlarni qanoatlantiruvchi ixtiyoriy yechim topiladi. Agar bu yechim optimallik shartini qanoatlantirsa, optimal yechim bo'ladi, aks holda boshlang'ich yechim optimal yechimga yaqin bo'lgan boshqa tayanch yechimga almashtiriladi. Tayanch yechimlarni almashtirish jarayoni optimal yechim topilguncha, yoki berilgan masalaning optimal yechimi mavjud emasligi aniqlanguncha takrorlanadi. Simpleks usulni 1949 yilda Amerika olimi Dantsig kashf qildi. Dantsig bilan parallel ravishda sobiq SSR olimi, akademik Kantorovich simpleks usulning bir turi bo'lgan «ikkilamchi baholar» usulini kashf qilib chiziqli dasturlash fanining taraqqiyotiga asos soldi. Simpleks usul keyinchalik turli olimlar tomonidan rivojlantirib borildi. Masalan, professor M.I. Eydelnant simpleks usulning eng sodda variantini kashf qilib uni chiziqli tenglamalar sistemasining nomanfiy yechimlari ichida berilgan chiziqli funksiyaga ekstremal qiymat beruvchi yechim algoritmi deb atadi. Eydelnant usuli quyidagidan iborat. Faraz qilaylik, kanonik formadagi chiziqli dasturlash masalasi berilgan bo'lsin x1 0, x2 0, …, xn 0, (2) Ymin = c0 + c1x1 + c2x2+ … + cnxn (3) Agar masala kanonik formada bo'lmasa, u bu ko'rinishga keltiriladi. Buning uchun (1) sistemada tengsizliklar qatnashsa, tengsizlikning kichik tomoniga qo'shimcha nomanfiy o'zgaruvchi qo'shish yordamida, u tenglamaga aylantiriladi. Agar chiziqli funksiya Ymax ko'rinishida bo'lsa, undagi ishoralarni almashtirib Ymin ga aylantiriladi, yani - Ymax = Ymin (1)-(3) masalani yechishdan avval, (1) sistemaning yechimi mavjud emaslik sharti hamda uning nomanfiy yechimi mavjud emaslik shartlarining bajarilishi tekshiriladi. a) Agar birorta tenglama 0x1+0x2+…+0xn = b (b0) qo'rinishda bo'lsa, u holda (1) sistema birgalashmagan bo'ladi va u umuman yechimga ega bo'lmaydi. b) Agar (1) sistemadagi biror tenglama a1x1+a2x2+…+anxn = b ko'rinishda bo'lib a1,a2,…,an koeffitsiyentlar bir xil ishorali va ularning ishorasi b ning ishorasiga teskari bo'lsa, sistema musbat yechimga ega bo'lmaydi. Agar a) va b) shartlardan birortasi bajarilsa masala yechimga ega bo'lmaydi. Agar bu shartlardan birortasi ham bajarilmasa masalaning berilganlari quyidagi ko'rinishdagi jadvalga joylashtiriladi. bu yerda Jadvaldagi m+1 qator nazorat tenglama deyiladi (N.T.). Bu tenglamadan ajratilishi kerak bo'lgan nomalum tanlanadi. Odatda max (aij) ga mos keluvchi ustun tanlanadi. Tanlangan nomalumni qaysi tenglamadan ajratish kerakligini aniqlash uchun aniqlovchi koeffitsiyent hisoblanadi. i-qatorga mos keluvchi (A.K.) i quyidagicha topiladi: Shartni qanoatlantiruvchi ...