Chiziqli dasturlashtirish masalalari

Keyingi jadvalga o’tish. Dastlabki tayanch rejaning optimalligi tekshiriladi. Agar (m+1) qatorda manfiy sonlarbo’lmasa,ya‘ni hamma j= lar uchun
z_j-c_j ≥ 0 (16)
shart bajarilsa, reja optimal hisoblanadi. Agar (m+1) qatorning hech bo’lmaganda bironta elementi manfiy bo’lib, unga mos keladigan ustunda xech bo’lmasa bitta musbat koeffitsient mavjud bo’lsa, maqsad funksiyaning qiymati kattaroq bo’lgan boshq a tayanch reja mavjud ekanligini bildiradi.
3. Agar (m+1) qatorda bir qancha manfiy sonlar mavjud bo’lsa, avvalo bu manfiy sonlardan bazisga kirgani ajratib olinadi.
Buning uchun (m+1) - qatordagi absolyut qiymat jixatidan eng katta manfiy son tanlab olinadi. Agar bunday sonlar bir nechta bo’lsa va ulardan kaysi biri maqsad funksiyasini eng katta qiymatga intiltirsa, shu manfiy son tanlab olinadi. Umuman olganda (m+1) - qatordagi manfiy sonlar qiymat jixatidan farqlanadi. Shuning uchun rejaga maqsad funksiyasini eng katta qiymatga erishtiradigan o’zgaruvchi kiritiladi. Bu esa dastlabki tayanch rejani optimal rejaga o’tkazish bosqichlarini kamaytiradi.
4. Faraz qilaylik, aij o’zgaruvchi bazisga kiritilsin. Buning uchun bazisdan qaysi o’zgaruvchi chiqib ketishini aniqlash kerak. Ushbu
(17)
nisbatlardan eng kichigi bazisdan chiqib ketadigan o’zgaruvchining qatorini ko’rsatadi. Faraz qilaylik bu qator i qator bo’lsin. Shuning uchun x_j o’zgaruvchi bazisdagi x_n+j o’zgaruvchini o’rnini oladi. aij koeffitsient bosh element bo’ladi.
5. x_j kiritilgan qator yordamida yangi simpleks jadval tuziladi. Hal qiluvchi i qator elementlari yordamida quyidagilar hisoblanadi:
(18)
6. Matritsaning qolgan barcha elementlari koeffitsientlari ham quyidagi formula yordamida aniqlanadi:
(19)
7. Agar hal qiluvchi qator (yoki ustun) da nolli elementlar bo’lsa, mos ravishda shu qator (ustun) yangi jadvalga o’zgarishsiz ko'chiriladi.
8. Yangi variant hisoblashlari tamom bo’lgandan sung yana (m+1)-qator analiz qilinadi va Yuqoridagi jarayon 2-ketma-ketlikdan boshlab takrorlanadi.