Identifikatsiyalash

Sun’iy bizis usulini qoʻllashga misol
Ushbu Z=x₁+x₂+3x₃ funksiyaning cheklanish shartlari quyidagicha boʻlib:
x₁-x₃+x₄=3
2x₁ -x₂=2
3x₁ -2x₂-x₄=1
x_j³0, j=1,2,3,4
uni qanoatlantiradigan minimumi topilsin.
Echish. Cheklanish shartlari bazis noma’lumlarga nisbatan echilmagan boʻlganligi uchun simpleks usuldan foydalanib boʻlmaydi. Bu masalani simpleks jadval usuli bilan echish uchun sun’iy bazis usulidan foydalanamiz. y₁, y₂, y₃ sun’iy noma’lumlar yordamida bu masalaga mos chiziqli programmalash masalasini quyidagicha yozamiz:
y₁=3-(x₁--x₃+x₄),
y₂=3-(2x₁ -x₂),
y₃=1-( 3x₁ -2x₂-x₄)
Bu sistema uchun manfiy boʻlmagan x_j≥0 j=1, 2, 3, 4 larni va quyidagi
F= y₁+ y₂+ y₃
yordamchi maqsad funksiyaga minimum qiymat beruvchi y₁, y₂, y₃ larni topamiz.
Boshlangʻich jadvalda bazis noma’lumlar uchun y₁, y₂, y₃ larni olib, quyidagiga ega boʻlamiz.
y₁+x₁--x₃+x₄=3
y₂+2x₁ -x₂=3
y₃+3x₁ -2x₂-x₄=1
F+6 x₁-3 x₂-x₃+3x₄=7
Z- x₁- x₂-2x₃=0
Bu masalaga mos simpleks jadval quyidagicha boʻladi:

	1	-x1	-x2	-x3	-x4
y1	3	1	0	-1	4
y2	3	2	-1	0	0
y3	1	3	-2	0	-1
F	7	6	-3	-1	3
Z	0	-1	-1	-2	0

Simpleks jadvalning biridan ikkinchisiga ketma-ket oʻtib, quyidagi jadvallarni tuzamiz

	1	-y3	-x2	-x3	-x4
y1	8/3	-1/3	2/3	-1	13/3
y2	7/3	-2/3	1/3	0	2/3
x1	1/3	1/3	-2/3	0	-1/3
F	5	-2	1	-1	5
Z	1/3	1/3	-5/3	-2	-1/3

	1	-y3	-y1	-x3	-x4
x2	4	-1/2	3/2	-3/2	13/2
y2	1	-1/2	-1/2	1/2	-3/2
x1	3	0	1	-1	4
F	1	-3/2	-3/2	1/2	-3/2
Z	21/3	-1/2	-5/2	-9/2	21/2

	1	-y3	-y1	-y2	-x4
x2	7	-2	0	3	2
x3	2	-1	-1	2	-3
x1	5	-1	0	2	1
F	0	-1	-1	-1	-0
Z	16	-4	-2	9	-3

Oxirgi jadvalda F dan boshlanuvchi satrda musbat element mavjud emas. Demak, topilgan {5;7;2;0;0;0} echim optimal echim boʻladi, chunki bu echimda F=0. Demak, y₁= y₂= y₃=0 da Z_min=16 boʻlib, x₁=5; x₂=7; x₃=2; x₄=0 .

1.5. Chiziqli programmalash masalasining geometrik usuli

Usulning qoʻllanilish sharti. Chiziqli programmalash masalasini grafik usulda echish uni geometrik tasvirlashga asoslangan. Ikki oʻlchovli fazoda (tekislikda) berilgan chiziqli programmalash masalasini echish uchun grafik usulni qoʻllash mumkin. N>2 oʻlchovli fazoda berilgan masalani grafik usul bilan echish noqulay, chunki bu holda, echimlardan tashkil topgan qavariq koʻpburchakni yasash qiyinlashadi.
Chiziqli masalalarni echishning usullaridan biri geometrik usuldir. Bu usulning qoʻllanilishining asosiy sharti quyidagichadir: n – m = 2, bu yerda n – oʻzgaruvchilar soni, m – tenglamalar soni.
2 ta oʻzgaruvchini (x₁, x₂) ni erkin oʻzgaruvchi deb, qolgan oʻzgaruvchilarni ular orqali belgilab olamiz.

Toʻgʻri burchakli tenglamalar sistemasi olinadi.

Echim II chorakdan olinadi. Har bir toʻgʻri chiziqning grafigi quriladi. Toʻgʻri chiqqa shtrix oʻtkazish uchun bazis oʻzgaruvchiga orttirma beriladi. Toʻgʻri chiziqning siljishi yoʻnalishiga qarab shtrix oʻtkaziladi. Echimlar koʻpburchakning tugunlarida yotadi. Optimal echimni topish uchun maqsad funksiyasining grafigi quriladi.

Maqsad funksiyaning harakat yoʻnalishini aniqlash uchun L ga orttirma beriladi. Oqilona echim maqsad funksiya grafigining harakat yoʻnalishidagi mumkin boʻlgan echim ohirgi tugun hisoblanadi. Maqsad funksiyani ogʻish burchagi hamda harakat yoʻnalishini aniqlash uchun maqsad funksiyadagi C₁, C₂ koeffitsientlardan foydalanamiz.
1) boʻlsa,

2) boʻlsa,

3) boʻlsa,

4) boʻlsa,



1.5.1.Chiziqli programmalash masalasinining geomatematik interpritatsiyasi

Bizga maqsad funksiyaning cheklanish tengsizliklar sistemasini qanoatlantiradigan minimumini topishning chiziqli programmalash masalasi berilgan boʻlsin:

Tengsizliklar sistemasini qanoatlantiradigan ixtiyoriy x₁, x₂…,x_n sonlar toʻplami uning echimlari deyiladi.
Sistema hech boʻlmasa bitta echimga ega boʻlsa sistema birgalikda deyiladi. Aks holda esa, sistema birgalikda emas deyiladi. Bundan keyin biz tengsizliklar sistemasini birgalikda deb faraz qilamiz.
n=2 boʻlganda tengsizliklar sistemasidan quyidagi sistemani hosil qilamiz:

Bu tengsizliklarning har biri a_i1x₁+a_i2x₂₌b_i toʻgri chiziq bilan, echimlarning manfiy boʻlmaslik shartlari x_j0 j=1;2 esa x_j=0 toʻgʻri chiziq bilan chegaralangan yarim tekisliklar boʻladi. Tengsizliklar sistemasi birgalikda boʻlganligi uchun hech boʻlmaganda bitta echimga ega boʻladi, ya’ni chegaraviy toʻgʻri chiziqlar bir-biri bilan kesishib, mumkin boʻlgan (oʻrinli) echimlar toʻplamini hosil qiladi. Demak, n=2 boʻlganda mumkin boʻlgan echimlar toʻplami koʻpburchakning nuqtalaridan iborat boʻladi. Masalan, m=4 boʻlganda mumkin boʻlgan echimlar toʻplami 1.5.1-rasmda koʻrsatilgan koʻpburchakdan iborat boʻladi. Agar n=3 boʻlsa va bu tengsizliklarning har biriga geometrik nuqtai nazardan qaraganda ularning har biri a_i1x₁+ a_i2x₂+a_i3x₃ =b_i, (i=1,2,…m) tekisliklar bilan, echimlarning manfiy boʻlmaslik shartlari x_j0 lar esa, x_j=0 tekisliklar bilan chegaralangan uch oʻlchovli yarim fazolardan iborat boʻladi.
Ikkinchi tomondan, sistema birgalikda boʻlganligi uchun bu yarim fazolar kesishib, biror bir koʻpyoqli hosil qiladi. Koʻp yoqli esa mumkin boʻlgan echilar toʻplamini beradi, ya’ni uning ixtiyoriy nuqtasining koordinatalari sistemada n>3 boʻlsa, bu tengsizliklarning har biri
A_i1x₁+ a_i2x₂+ …+a_inx_n =b_i, (i=1,2,…m)
gipertekisliklar bilan echimlarning manfiy boʻlmaslik shartlari esa x_j=0 gipertekisliklar bilan chegaralangan yarim fazolardan iborat boʻladi. Bu yarim fazolar kesishib, mumkin boʻlgan echimlar toʻplami boʻlgan birorta koʻp yoqlini hosil qiladi.
Yuqoridagi mulohazalar chiziqli programmalash masalalarini geometrik nuqtai nazaridan quyidagicha talqin qilishga imkon beradi: mumkin boʻlgan echimlar toʻplami boʻlgan koʻpyoqlining shunday nuqtasining koordinatalarini topish kerakki, bu nuqtada maqsad funksiya oʻzining eng kichik qiymatiga erishsin.

1.5.1-rasm. Qavariq koʻpburchak 1.5.2-rasm.Koʻpburchakli qavariq soha

1.5.3- rasm. Yagona nuqtali 1.5.4- rasm. Boʻsh toʻplam
Mumkin boʻlgan echimlar sohasi (toʻplami) qavariq koʻpburchak (1.5.1-rasm), koʻpburchakli qavariq soha (1.5.2-rasm), yagona nuqta (1.5.3-rasm) va boʻsh toʻplam (1.5.4-rasm) boʻlishi mumkin.


1.5.2. Chiziqli programmalash masalasini echishning grafik usuli

Chiziqli programmalash masalasini echishning grafik usuli asosan oʻzgaruvchilar soni ikkita va masala simmetrik formada berilgan holda ishlatiladi. Chiziqli programmalash masalasini ikki oʻzgaruvchi uchun quyidagicha yozish mumkin.

Bu masalaning mumkin boʻlgan echimlari sohasi qavariq koʻpburchak yoki qavariq koʻpqirra, yoki yagona nuqta boʻlishi mumkin. Tengsizliklarning har biri chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. Chiziqli funksiya ham ma’lum bir oʻzgarmas qiymatda toʻgʻri chiziqni ifodalaydi c₁x₁+c₂x₂=const.
Faraz qilaylik, mumkin boʻlgan echimlar qavariq koʻpburchakdan tashkil topgan boʻlsin. Echimlardan tashkil topgan qavariq toʻplamni hosil qilish uchun toʻgʻri chiziqlar bilan chegaralangan koʻpburchakni yasaymiz. Bu koʻpburchak ABCDEF boʻlsin (1.5.5-rasm). Maqsad funksiyasi X₁OX₂ tekislikda parallel toʻgʻri chiziqlarni beradi. Chiziqli funksiyani ixtiyoriy oʻzgarmas c₀ songa teng deb olaylik. Unda c₁x₁+c₂x₂=const= c₀ toʻgʻri chiziq hosil boʻladi. Unga perpendikulyar boʻlgan N(c₁,c₂) vektor z-funksiyaning oʻsish yoʻnalishini belgilaydi (1.5.5--rasm).
Agar echimlardan tashkil topgan qavariq koʻpburchak chegaralanmagan boʻlsa ikki hol boʻlishi mumkin:
1-hol. c₁x₁+c₂x₂=const toʻgʻri chiziq N(c₁,c₂) vektor vektor boʻyicha yoki unga qarama-qarshi yoʻnalishda siljib borib har vaqt qavariq koʻpburchakni kesib oʻtadi. Ammo na minumum yoki maksimum qiymatga erishmaydi. Bu holda chiziqli funksiya quyidan va yuqoridan chegaralanmagan boʻladi (1.5.6-rasm).

1.5.5- rasm. Koʻpburchak 1.5.6-rasm. Quyidan va yuqoridan
chegaralanmagan chiziqli funksiya
2-hol. c₁x₁+c₂x₂=const toʻgʻri chiziq N(c₁,c₂) vektor boʻyicha siljib borib qavariq koʻpburchakning birorta chetki nuqtasida minumum yoki maksimum qiymatga erishadi. Bunday holda chiziqli funksiya yuqoridan chegaralangan, quyidan esa chegaralanmagan (1.5.7-rasm) yoki quyidan chegaralangan yuqoridan esa chegaralanmagan boʻlishi mumkin (1.5.8-rasm). Ba’zi chiziqli funksiya yuqoridan ham, quyidan ham esa chegaralangan boʻlishi mumkin (1.5.9-rasm).

1.5.7- rasm. Chiziqli funksiya 1.5.8-rasm. Quyidan
chegaralangan yuqoridan chegaralangan yuqoridan chegaralanmagan



1.5.9-rasm. Chiziqli funksiya yuqoridan ham, quyidan ham chegaralangan

Chiziqli programalash masalasini grafik usulda echish quyidagi ketma-ketlikda bajariladi:

1. 
   Tenglamalar yoki tengsizliklar sistemasining grafiklari quriladi .
   
2. 
   Har bir tengsizlikning tekislikdagi aniqlanish tomonlari (sohasi) belgilanadi.
   
3. 
   Mumkin boʻlgan echimlar sohasi ajratiladi .
   
4. 
   N=(c₁,c₂) vektori quriladi va unga (0,0) nuqtada perpendikulyar oʻtkaziladi.
   
5. 
   Koʻpburchakdan perpendikulyarga parallel chiziqni vektor yoʻnalishi boʻyicha paralel siljitilib ekstremal nuqta topiladi. Agar Z funksiyaning minimal qiymatiga mos nuqtani topish kerak boʻlsa, u holda bu nuqta p vektorga perpendikulyarning shu vektor yoʻnalishi boʻyicha siljitganda mumkin boʻlgan nuqtalar sohasining birinchi nuqtasiga mos keladi. Maksimum qiymat beruvchi nuqta esa eng oxirgi nuqta boʻladi. Agar vektor qiymati (manfiy ishora) -N boʻlsa yuqoridagi holning teskarisi boʻladi.
   
6. 
   Optimal nuqta kordinatasi topiladi va Z funksiya qiymati hisoblanadi.
   

Misol. Quyidagi chiziqli programmalash masalasini grafik usulda eching.


1.5.10-rasm. Echimlar soxasi.

Berilgan tengsizliklarning grafiklarini X₁OX₂ tekislikda quramiz va mumkin boʻlgan echimlar soxasini aniqlaymiz (1.5.10-rasm). Soha grafigida shtrixlangan joyni aniqlaydi. Chunki bu joy hamma tengsizliklarni qanoatlantiruvchi sohadir. Mumkin boʻlgan echimlar soxasidan optimal echimni aniqlaymiz. Aniqlash uchun (0,0) nuqtadan oʻtuvchi N=(2,-5) vektorini yasaymiz va uning yoʻnalishini aniqlaymiz. (0,0) nuqtada bu vektorga N perpindikulyarini oʻtkazamiz va uni vektor yoʻnalishi boʻyicha siljitamiz. Soha bilan perpindikulyarning oxirgi kesishish nuqtasi A nuqta boʻladi. Bu nuqta Z funksiyasiga maksimal qiymat beruvchi nuqtadir. Bu nuqta (3,0) boʻlib uning koordinatasi x₁=3, x₂=0 masalaning echimi boʻladi. Grafikdan koʻrinib turibdiki z funksiyaga minumum qiymat beruvchi nuqta esa (0,3).