Identifikatsiyalash

2-misol.
Berilgan chiziqli programmalash masalasining maqsad funksiyasiga min qiymat beruvchi echimni toping.
x₁+x₂£ 2
2x₁-x₂³ 2
a₁³0, x₂³0
Z=x₁-x₂®min
Chegaraviy sistemani kanonik koʻrinishda quyidagicha yozib olamiz:
x₁+x₂+x₃ =2
-2x₁+x₂+x₄ =-2
Simpleks jadval quramiz. Birinchi jadvalda ozod hadlar ichida manfiy element mavjud. SHuning uchun tayanch planni topamiz. Bu jadvaldan hal qiluvchi elementni topib, Simpleks almashtirish bajaramiz va ikkinchi jadvalga ega boʻlamiz. Ikkinchi jadvalda tayanch plan mavjud. Shu sabab undan optimal planni topishga oʻtamiz.

Soʻ Boʻ	1	-x2	-x2		Soʻ Boʻ	1	-y2	-x2
y1	2	1	1		y1	1	1/2	3/2
y2	-2	-2	1		x1	1	-1/2	-1/2
z	0	-1	1		z	1	-1/2	1/2

Optimal planni topish uchun Z- qator elementlarini manfay holga keltirish kerak. Buning uchun jadvaldan hal qiluvchi elementni topamiz. Hal qiluvchi element 3/2. Simpleks almashtirish qilib quyidagi jadvalga ega boʻlamiz.

Soʻ Boʻ	1	-y2	-y1
x2	2/3	1/3	2/3
x1	4/3	-5/6	-1/3
Z	2/3	-7/6	-1/3

Jadvaldan koʻrinib turibdiki maqsad funksiyasiga minimal qiymat beruchi nuqta mavjud, ya’ni:
x₁=4/3; x₂=2/3; z_min=2/3.

1.4. Chiziqli programmalash masalasini echishning sun’iy bazis usuli

Yuqorida biz chiziqli programmalash masalasining boshlangʻich tayanch plani mavjud va boshlangʻich planni tuzish mumkin boʻladigan m- oʻlchovli birlik matritsa masala shartida qatnashadi deb faraz qildik. Bu birlik matritsa yordami bilan optimal planga oʻtishga yordam beradigan planni tuzish mumkin. Agar chiziqli programmalash masalasining chegaraviy shartlari AX=V (B≥0) koʻrinishda berilgan boʻlsa, qoʻshimcha oʻzgaruvchilar kiritish yoʻli bilan birlik matritsani masala shartiga kiritish mumkin.

Amalda uchraydigan ayrim chiziqli programmalash masalalari planga ega boʻlgan holda birlik matritsani oʻz ichiga olmaydi va cheklanishlar sistemasida noma’lumlar soni cheklanishlar sonidan etarlicha katta boʻladi. Bunday masalalarni echishda “sun’iy bazis usuli” qoʻllaniladi.

Quyidagi chiziqli programmalash masalasini qaraymiz:

Bu erda b_i≥0, va sisiema birlik matritsani oʻz ichiga olmaydi. Masalaning shartiga birlik matritsani kiritish uchun sistemadagi har bir tenglamaga sun’iy oʻzgaruvchilar deb ataluvchi y₁, y₂, …, y_m noma’lumlarni mos ravishda qoʻshamiz va uni quyidagi koʻrinishda yozamiz:

Quyidagi, yordamchi maqsad funksiyasini tuzamiz F=y₁+y₂+…+y_m va uning yuqoridagi shartni qanoatlantiradigan minimumini topamiz. Agar min F>0 boʻlsa, qoʻyilgan masala y₁= y₂,= …= y_m =0 boʻlganda, x_i≥0 shartni qanoatlantiradigan echimga ega boʻlmaydi. Agar min F=0 boʻlsa, bazis echim masalaning optimal echimi boʻladi. Buning uchun yordamchi maqsad funksiyasini minimumga olib keluvchi masalani simpleks usulida echamiz.