Identifikatsiyalash

brs	. . .
brn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ym	bm0	bm1	bm2	. . .	bms	. . .	bmn
Z	b00	b01	b02	. . .	b0s	. . .	b0n

Chiziqli programmalash masalasini simpleks usul yordamida echish uch bosqichdan iborat:

1. Boshlangʻich tayanch planni topish.
2. Tayanch planlar ichidan masalaning optimal planini topish.
3. Masalaning tayanch planini tuzish
Boshlangʻich tayanch planni topish quyidagi algoritm boʻyicha bajariladi:
1. Simpleks jadvaldan hal qiluvchi elementni topish:
1.1. Hal qiluvchi elementni topish oldin hal qiluvchi ustunni topishdan boshlanadi. Buning uchun ozod hadlar ustuniga qaraladi. Agar ozod xadlar ustunidagi elementlar hammasi musbat boʻlsa, bu boshlangʻich plan tayanch plan boʻladi va ikkinchi etapga oʻtiladi. Agar manfiy element mavjud boʻlsa ulardan modul boʻyicha eng kattasi tanlanadi (agar bitta boʻlsa shu element oʻzi olinadi). Misol uchun aytaylik bu element b_r0 boʻlsin. Shu b_r0 element turgan r satr qaraladi. Agar satr elementlaridan xammasi musbat boʻlsa, masalaning echimi mavjud boʻlmaydi (bu holda hisoblashlar shu joyda toʻxtatiladi). Agar satrda manfiy element mavjud boʻlsa, ulardan modul boʻyicha eng kattasi tanlanadi (agar bitta boʻlsa oʻzi olinadi). SHu element turgan ustun hal qiluvchi ustun deyiladi. Misol uchun bu s-chi ustun boʻlsin.
1.2. Hal qiluvchi satr topiladi. Ozod xadlarni hal qiluvchi ustun elementlarga boʻlib chiqiladi va ulardan musbatlarining eng kichigi tanlanadi, ya’ni
.
Aytaylik, bu nisbatlar ichida musbatlarning eng kichigi b_rs/b_r0 boʻlsin. U holda shu b_rs element turgan satr hal qiluvchi satr deyiladi, b_rs elementning oʻzi esa hal qiluvchi element boʻladi.
2. Hal qiluvchi ustun va satr oʻzgaruvchilari oʻrinlari almshtiriladi, (ya’ni x_s va y_s yangi jadvalda oʻrinlari almashadi).
3. Jadvalda simpleks almashtirish bajariladi.
3.1. Hal qiluvchi ustun elementlari hal qiluvchi elementga boʻlib chiqilib yangi jadvalga yoziladi, ya’ni .
3.2. Hal qiluvchi satr elementlari xal qiluvchi elementga boʻlib chiqilib yangi jadvalga yoziladi, ya’ni .
3.3. Hal qiluvchi element 1 ga tenglashtirilib oʻziga boʻlinadi, ya’ni .
3.4. Yangi simpleks jadvalning qolgan elementlari quyidagi formula orqali topiladi.
yoki
Yangi jadvalda b´_ij -elementni hisoblashda eski jadvaldan b_ij, b_is ,b_rj, b_rs -elementlarini topish quyidagicha boʻladi:
b_ij - b´_ij elementning eski jadvaldagi unga mos element;
b_is -b_ij element turgan satr bilan b_rs hal qiluvchi element ustuni kesishmasidagi element;
b_rj -b_ij element turgan ustun bilan b_rs hal qiluvchi element satri kesishmasidagi element;
b_rs - hal qiluvchi element.

BOʻ	1	-x1	-x2	. . .	-yr	. . .	-xn
y1	b’10	b’11	b’12	. . .	b’1s	. . .	b’1n
y2	b’20	b’21	b’22	. . .	b’2s	. . .	b’2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
xs	b’r0	b’r1	b’r2	. . .	b’rs	. . .	b’rn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ym	b’m0	b’m1	b’m2	. . .	b’ms	. . .	b’mn
Z	b’00	b’01	b’02	. . .	b’0s	. . .	b’0n

4. Yangi topilgan simpleks jadvalda tayanch plan mavjud boʻlsa ikkinchi bosqichga, ya’ni optimal planni topishga oʻtiladi, aks holda yuqoridagi protsess yangi jadval uchun toki tayanch plan topilguncha qayta takrorlanadi.

Masalaning optimal planni topish.
Agar 1 bosqichdan olingan tayanch planning simpleks jadvaldagi Z-satr elementlari (ozod hadi b´₀₀ dan tashqari) hammasi musbat boʻlsa, bu olingan boshlangʻich tayanch plan yagona va u masalaning optimal plani (echimi) boʻladi. Agar Z satrdagi hamma musbat elementlaridan kamida bittasi nulga teng boʻlsa, u holda masalaning cheksiz koʻp optimal plani mavjud boʻladi. Agar Z satrdagi elementlardan hech boʻlmaganda bittasi manfiy boʻlsa, optimal plan quyidagi algoritim boʻyicha topiladi:
1. Hal qiluvchi elementni topish.
1.1. Hal qiluvchi ustun topiladi. Z-qatordagi manfiy elementlarning modul boʻyicha eng kattasi (bitta boʻlsa oʻzi) tanlanadi. Shu element turgan ustun hal qiluvchi ustun boʻladi.
1.2. Hal qiluvchi satr topiladi. Ozod hadlar elementlari hal qiluvchi ustun elementlariga boʻlib chiqiladi va ulardan musbatlarining eng kichigi olinadi, ya’ni birinchi bosqichning 1.2 punktidagi kabi. Bu songa mos keluvchi ustundagi element hal qiluvchi element va shu element turgan satr esa hal qiluvchi satr boʻladi.
2. Hal qiluvchi satr va ustun oʻzgaruvchilari oʻz joylarini almashtiradi (agarda hali ular almashtirilmagan boʻlsa).
3. Jadvalda simpleks almashtirish bajariladi. Simpleks almashtirish 1- bosqichdagi 3.1, 3.2, 3.3, 3.4 punktlar kabi bajariladi.
4. Yangi topilgan jadvalning Z satri qaraladi. Agar Z qatordagi hamma elementlar musbat boʻlsa, olingan oxirgi plan masalaning optimal plani boʻladi. Aks holda yuqoridagi 1,2,3 punktlar yana takrorlanadi, toki optimal plan topilguncha.
Izoh: Chiziqli programmalash masalasida, agar maqsad funksiyasining minumimi izlansa yuqoridagi 1-chi bosqich toʻligʻicha oʻrinli boʻlib, 2-bosqichda esa faqat Z -qator elementlari manfiy holatga keltirilishi kerak, ya’ni teskari holat boʻladi
1-misol
z=5x₁-x₂+3x₃
Chiziqli funksiyaga maksimum qiymat beruvchi
x₁+x₂+x₃£2
4x₁+2x₂+x₃£3
x₁-x₂+2x₃£-1
-3x₁+2x₂-2x₃£5
x₁³0, x₂ ³0,x₃³0
chegaraviy sistemasining mumkin boʻlgan echimlari sohasida noma’lumlar topilsin. Chegaraviy sistemani kanonik koʻrinishda quyidagicha yozib olamiz:
x₁+x₂+x₃+x₄=2
4x₁+2x₂+x₃+x₅=3
x₁-x₂+2x₃+x₆=-1
-3x₁+2x₂-2x₃+x₇=5
x₁³0, x₂ ³0,x₃³0
Tenglamada bazis oʻzgaruvchilarni simpleks oʻzgaruvchilardan farqlash uchun x₄=u₁ , x₅=u₂ , x₆=u₃ , x₇=u₄ belgilashlarni kiritamiz va Simpleks jadval tuzamiz.

Soʻ Boʻ	1	-x1	-x2	- x3
u1	2	1	1	1
u2	3	4	2	1
u3	-1	1	-1	2
u4	5	-3	2	-2
Z	0	-5	1	-3

Oʻzgaruvchilarning manfiy boʻlmaslik sharti berilganligini hisobga olib, toʻgʻridan-toʻgʻri tayanch echimni topishga kirishamiz. Ozod hadlar ichida -1 manfiy ishorali koeffitsient bor. Shu qatordan ishorasi manfiy boʻlgan modul boʻyicha eng katta elementni topamiz. U x₂ ustunidagi -1 elementdir. Qoidaga binoan musbat nisbatlar ichidan eng kichigini topamiz:
+min2/1, 3/2, -1/-1, 5/2}=1/1
Demak, unga mos element x₂ ustunidagi -1 elemen. Bu element hal qiluvchi element boʻladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.

Soʻ Boʻ	1	-x1	-y3	- x3
u1	1	2	1	3
u2	1	6	2	5
x2	1	-1	-1	-2
u4	3	-1	2	2
z	-1	-4	1	-1

Bu jadvaldan koʻrinib turibdiki ozod hadlar musbat, shu sabab tayanch plan mavjud. Endi optimal echimini topish uchun Z qatoriga qaraymiz. Bu qatorda ikkita manfiy ishorali koeffitsient bor. Ulardan modul boʻyicha qiymati katta boʻlgan koeffitsientni tanlab olamiz, u -4 elementidir. Qoidaga binoan hal qiluvchi elementni aniqlab yangi jadval tuzamiz:

+ min 1/2, 1/6, 1/-1, 3/-1}=1/6
Unga mos element x₁ ustunidagi 6 element. Bu element hal qiluvchi element boʻladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.

Soʻ Boʻ	1	-y2	-y3	- x3
U1	2/3	-1/3	1/3	4/3
X1	1/6	1/6	1/3	5/6
X2	7/6	1/6	-2/3	-7/6
U4	19/6	1/6	7/3	17/6
Z	-1/3	2/3	7/3	7/3

Ozod hadlar va Z qatoridagi koeffitsientlar musbat. Demak, optimal echim topildi, ya’ni u₂=u₃=x₃=0 va x₁=1/6, x₂=7/6 boʻlganda Z ning maksimal qiymati -1/3 ga teng boʻladi, ya’ni z=-1/3.