1. Chiziqli dasturlash masalasini echishning simpleks usuli

(14.17) dagi C'_m+1,C'_m+2,..., C'_n sonlar orasida musbatlari bor. Masalan, S'_j>0 deylik , u vaqtda X_m+1= X_m+2=…=X_j-1=X_j+1=…= X_n=0, X_j0 deb olib, X_j ning qiymatini orttira borish hisobiga Z= C₀^’- C'_jX^’_j ni qiymatini kamaytirish mumkin. Bu xolda (14.16) dan kelib chiqadigan quyidagi

X₁=b'₁-a'_1iX_j

X₂=b'₂-a'_2iX_j (14.19)

- - - - - - - -

X_m=b'_m-a'_miX_j
tenglamalardagi X₁,X₂,…,X_m larning birortasi xam manfiy bo‘lmasligi kerak.
Bu erda xam ikki hol ro‘y beradi:
a) (14.19) da a^’_1j, a^’_2j,…, a^’_mj, sonlarning hammasi musbat emas. X_j  0 uchun -a^’_kj X_j  0 (k=1,2,...,m) bo‘lganidan X_k=b'_k – a'_kj Xjb_k'>0 dir.
Demak, Z=C'₀ – C'_jX_j da C'_j > 0 va X_j 0 bo‘lgani uchun X_j ni cheksiz orttira borish bilan min Z =-  ega bo‘lamiz. Bundan esa, maqsad funksiya Z minimumga erishmasligi kelib chiqadi.
b) (14.19) dagi a^’_1j, a^’_2j,…,a^’_mj sonlar orasida musbatlari bor. Masalan , a'_kj >0 bo‘lsin . U holda X_k= b''_k – a^’_kj X_j da X_j ga dan katta qiymat berish mumkin emas, aks holda X_R < 0 bo‘lib qoladi. Bunda 0 ekanligi ravshan. Bunday kasrlar orasida eng kichigi bo‘lib, a^’_ij son hal qiluvchi elementdir. £isqalik uchun = belgilash kiritamiz. (6) da X_j ni gacha orttira olamiz, aks holda X_i<0 bo‘lishini ko‘rdik. Ozod nam’lumlarga
X_m+1= X_m+2=…=X_j-1=X_j+1=…= X_n=0, X_j= (14.20)
qiymatlarni berib, bazis noma’lumlarni quyidagidan aniqlaymiz.
(14.21)
endi yangi B₂ bazisga o‘tamiz:
B₂ = {X₁,X₂,…,X_i,…,0,0,…0}.
Bu bazis echim (14.20) va (14.21) dan tuziladi va unga mos Z (B₂) ning qiymati quyidagiga teng bo‘ladi:
Z(B₂) = C'₀ – C'_j  Z (B₁), S'_j>0
Endi (14.16) sistema va maqsad funksiya (14.17) ni yangi bazis B₂ ga moslab yozamiz. Buning uchun (14.16) dagi
X_i = b'_i – (a’_im+1 X_m+1 +…+a’_ij X_j+…+a’_inX_n)
tenglamani X_j ga nisbatan echamiz.

va bu ifodani (14.16) ning qolgan tenglamalariga qo‘yamiz.

hosil bo‘lgan yangi sistemani qo‘yidagi ko‘rinishda yozamiz.

(14.22)
Bu bazisning ifodalarini (14.17) ga qo‘yib, uni quyidagi ko‘rinishga keltiramiz:

Z=C"₀-(C"_m+1 X_m+1 + C"_m+2 X_m+2+... (14.23)
+C"_i X_i +...+ C"_nX_n),
Shu bilan jarayonning birinchi bosqichi tugadi. Keyingi bosqich, yana shu birinchi bosqichni, ya’ni (14.23) va (14.22) ga nisbatan I va II xolni, undan keyin IIa va IIb ni takrorlashdan iborat bo‘ladi va x.k.
Shunday qilib, simpleks usul quyidagi jarayonni ifodalaydi:

1. Cheklanish tenglamalari sistemasi (14.15) ni (14.16) ko‘rinishga, maqsad funksiya (14.14) ni esa (14.17) ko‘rinishga keltiramiz.

   
   

2. Agar (4) da barcha C'_m+1,C'_m+2,…,C'_n koeffisientlar manfiy bo‘lsa, B₁ bazisning {b₁', b'₂,…,b_m',0,0,…,0}echimi optimal bo‘lib, bu echimda Z(B₁)=S'₀ minimumga erishadi

   
   

3. (4)da S'_m+1, C'_m+2 ,…,C'_n ,lar orasida musbatlari mavjud, masalan, C'_j >0 desak, X_m+1=X_m+2=…=X_j-1=X_j+1=…=X_n=0, X_j>0 qiymatlarda (14.16) sistema, (14.19) ko‘rinishni oladi. Agar (14.19 da barcha a'_1j,a'_2j,…,a'_mj koeffisientlar musbat bo‘lmasa, min Z=- kelib chiqadi, ya’ni Z funksiya minimumga erishmaydi.

   
   

4. (14.19) dagi a_kj, k=1,2,...,m koeffisientlarning musbatlari mavjud, ya’ni a'_k>0 desak, sonlar orasida eng kichigi bo‘lgan ni olamiz. (14.16) sistemaning X_i ga nisbatan yozilgan tenglamasidan X_j ni aniqlab (14.16) sistemani yangi B₂ = { X₁,X₂,…,X_i,…, X_m,0,0,…,0} bazis echimga nisbatan yozib (14.22) ni hosil qilamiz maqsad funksiya (14.17) ni esa (14.23) ko‘rinishda ifodalaymiz.

   
   

2.