Chiziqli programmalash masalasini yechishning Simpleks usuli

a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

. . . . . . . . . . . . .

am1x1+am2x2+…+amnxn≤bm,

x1, x2, . . . , xn≥0 shartlarni qanoatlantirgan holda F=c1x1+c2x2+…+cnxn (2) maqsad funktsiyaga maksimal qiymat beruvchi x1, x2, . . . , xn larni topish kerak.

Bu masalani matematik modeli chizikli model bo'lib u umumiy holda berilgan quyidagi chiziqli programmalash masalasini bo'ladi:

• 1-qadam. Berilgan (1) tengsizliklar sistemasida yangi xn+1, xn+2, . . . , xn+m, , musbat oʻzgaruvchilar kiritib barcha tengsizliklarni tengliklarga aylantirib olamiz. Bu yerda yangi kiritilgan oʻzgaruvchilarni iqtisodiy maʼnosi: shu oʻzgaruvchi qatnashgan tengsizlikga mos keluvchi xom ashyoni ortib qolgan miqdoridir.
• a11x1+a12x2+…+a1nxn+ xn+1 =b1
• a21x1+a22x2+…+a2nxn+ xn+2 =b2
• . . . . . . . . . . . . .
• am1x1+am2x2+…+amnxn+ xn+m =bm
• Demak n+m- oʻzgaruvchili m-ta chiziqli tenglamalar sistemasini xosil qildik va bu sistemada xn+1, xn+2, . . . , xn+m,– oʻzgaruvchilar faqat bittadan tenglamada bir koeffitsient bilan ishtirok etadi.
• 2-qadam. Xosil boʻlgan tenglamalar sistemada xn+1, xn+2, . . . , xn+m,– oʻzgaruvchilarni bazis oʻzgaruvchilar, x1, x2, . . . , xn –oʻzgaruvchilarni esa erkin oʻzgaruvchilar deb olamiz va bazis oʻzgaruvchilarni erkin oʻzgaruvchilar orqali ifodalaymiz:
• xn+1 = b1 -a11x1-a12x2-…-a1nxn
• xn+2 = b2 -a21x1-a22x2-…-a2nxn
• . . . . . . . . . . . . . (3)
• xn+m = bm-am1x1-am2x2-…-amnxn,
• bu yerda x1, x2, . . . , xn –oʻzgaruvchilarni barchasiga 0 qiymat bersak xn+1, xn+2, . . . , xn+m,– oʻzgaruvchilar mos ravishda b1, b2, ..., bm –qiymatlarni qabul qiladi va (0,0,...,0, b1, b2, ..., bm,) birinchi tayanch reja boʻladi.