Identifikatsiyalash

Simpleks-analitik usul algoritmi.

1. 
   Chiziqli programmalashtirish masalasi berilgan boʻlsin.(tenglama tengsizlik koʻrinishda). Tenglamani kanonik koʻrinishga oʻtkaziladi.
   
2. 
   Kanonik koʻrinishga qoʻshimcha -lar kiritiladi va ulardan bazis va ozod hadlar ajratiladi. Kiritilgan xad tenglamada boshqa takrorlanmaydi. Chunki ozod hadlar manfiy boʻlmasligi kerak, doim musbat boʻlish kerak.
   

3. Misol:


Tenglamaga larni kiritiladi. Maqsad funksiyasini (-1) koʻpaytirib, minimumga intiltiriladi, ya’ni , , -bazis oʻzgaruvchilar, - ozod hadlardir. Bundan larga tenglama tuziladi.


-larni 0 ga tenglab, tenglamalar sistemasiga qoʻyamiz. U holda Agar maqsad funksiyasida manfiy koeffitsientlar boʻlsa, modul boʻyicha eng kattasi olinadi. Optimal echimni topish uchun maqsad funksiyasi boʻyicha tekshiramiz. Agar maqsad funksiyasi ozod xad oldidagi koeffitstienti musbat boʻlsa optimal echimi bor, aksincha manfiy boʻlsa, tenglama qayta ishlanadi.


1.3.2. Simpleks jadval tuzish

Simpleks usuli chiziqli programmalash masalasini echishning asosiy usullaridan biri boʻlib, ketma-ket yaqinlashish usuli yordamida x₁,x₂, . . .x_n oʻzgaruvchilarning shunday optimal qiymatini topadiki, bu qiymatlar maqsad funksiyasigi maksimal (yoki minimal) qiymat beradi.

Quyidagi funksionalga maksimum qiymat beruvchi chiziqli programmalash masalasi berilgan boʻlsin.

Masalani echish uchun simpleks jadval quramiz va simpleks usuli gʻoyasini berish uchun berilgan masalani quyidagicha kanonik formada yozamiz.

Bu erda x_n+i - bazis oʻzgaruvchilar deyiladi. Ularni qulaylik, hamda boshqa oʻzgaruvchilardan farqlash uchun mos ravishda y₁,y₂, . . .y_m deb belgilaymiz va yana quyidagi belgilashlarni kiritamiz b_i0=b_i; b_i,j=a_i,j; b_0j=c_j. Bu belgilashlar asosida simpleks jadval tuzamiz.

BOʻ	1	-x1	-x2	. . .	-xs	. . .	-xn
y1	b10	b11	b12	. . .	b1s	. . .	b1n
y2	b20	b21	b22	. . .	b2s	. . .	b2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ys	br0	br1	br2	. . .