Identifikatsiyalash

Misol.


Yechilishi: qoʻshimcha oʻzgaruvchilarni kiritib bu masalani kanonik koʻrinishda yozamiz.


Chegaraviy shartlarning barcha koeffitsientlari butun sonlardir. Shu sababdan, va oʻzgaruvchilarning butunligi va oʻzgaruvchilarning butun boʻlishligiga olib keladi. Shu sababdan kanonik koʻrinishga keltirilgan masalani toʻla butun sonli chiziqli programmalash masalasi sifatida qarash mumkin. Gomori usulidan foydalanamiz. Uning faqat butun sonli programmalash masalalarini echish uchun muljallangan 1-algoritmi bilan tanishamiz. Bu usulning gʻoyasi quyidagidan iborat. Berilgan butun sonli programmalash masalasida noma’lumlarning butun boʻlishlik shartiga e’tibor bermasdan, ularni oddiy chiziqli programmalash masalasi sifatida simpleks usuldan foydalanib echamiz.

B			1	-20	0	0
	0	40	-1	10	1	0
	0	29	4	2	0	1
		0	-1	20	0	0
	-20	4	-1/10	1	1/10	0
	0	21	21/5	0	-1/5	1
		-80	2	0	-2	0
	-20	9/2	0	1	2/21	1/42
	1	5	1	0	-1/21	5/21
		-85	0	0	-41/21	-5/21

butun boʻlishlik shartini qanoatlantirmaydi. Shu sababdan oxirgi Simpleks jadvaliga qoʻshimcha satir kiritamiz.
; ,
Undan keyin algoritmda tasvirlangan qoida boʻyicha Simpleks jadvalni
oʻzgartiramiz.

B			1	-20	0	0	0
	-20	9/2	0	1	2/21	1/42	0
	1	5	1	0	-1/21	5/21	0
		-85	0	0	-41/21	-5/21	0
	0	-1/2	0	0	-2/21	-1/42	1
	-20	4	0	1	0	0	1
	1	0	1	0	-1	0	10
	0	21	0	0	4	1	-42
		-80	0	0	-1	0	-10

Oxirgi Simpleks jadval berilgan masalaning yechimi beradi.

Agar echim butun sonlardan iborat boʻlsa, u butun sonli programmalash masalasining ham echimi boʻladi. Aks holda noma’lumlarning butun boʻlishlik shartini e’tiborga oluvchi va «kesuvchi tenglama» deb ataluvchi qoʻshimcha tenglama tuziladi.
Kesuvchi tenglamalarni tuzish
Qayd qilib oʻtamizki, yuqorida keltirilgan misolimizda Simpleks jadvalga kiritilgan qoʻshimcha shartning kesuvchi tenglama koʻrinishini quyidagicha

boʻldi. Bu shartni , tenglamalar yordamida va oʻzgaruvchilarga oʻtkazib olamiz: . Bundan koʻrinib turibdiki, qoʻshimcha shart K toʻplamdan nuqtani oʻz ichiga oluvchi qismini kesib tashlaydi.

Eslatib oʻtamizki, shartlari tengsizlik



bilan berilgan toʻla butun sonli chiziqli programmalash masalasidan kanonik koʻrinishga oʻtishda, umuman olganda, toʻla butun sonli chiziqli programmalsh masalasi hosil boʻlmaydi, chunki qoʻshumcha oʻzgaruvchilar butun boʻlish shartiga boʻysunmaydi. Ammo yuqoridagi tengsizlikda barcha va lar butun sonlar boʻlgan holda butun boʻlishlik shartini larga ham tarqatish mumkin ekan.
Agar yuqoridagi tenglamadagi va lar ratsional sonlar boʻlganda ham kanonik koʻrinishga oʻtishda toʻla butun sonli chiziqli programmalash masalasini hosil qilamiz. Buning uchun tenglamani va lar maxrajlarining eng kichik umumiy karralisiga koʻpaytirib, faqat shundan soʻng ni qoʻshimcha oʻzgaruvchilarni kiritish kerak ekan.
1.Faraz qilaylik, masaladagi sonlarning butun boʻlishlik sharti tashlab yuborishdan hosil boʻladigan masala echilgan va uning optimal echimi mavjud boʻlsin. Agar barcha x lar butun sonlar boʻlsa, topilgan echim butun sonli programmalash masalaning echimi boʻladi.
2.Faraz qilaylik, ba’zi x lar kasr sonlardan iborat boʻlsin, ya’ni simpleks jadvaldagi ozod hadlar ustuni qiymatlari ichida kasr sonlar ham mavjud boʻlsin. Ularning butun qismlarini [x] bilan belgilaymiz. U holda bu sonlarning kasr qismlari q lar quyidagicha aniqlanadi:
Q_i=x_i-[x_i], q_ij=a_ij-[a_ij].
Faraz qilaylik, ba’zi q_i≠0 boʻlsin. U holda,
cimpleks jadvalning tenglikni qanoatlantiruvchi q katori uchun kesuvchi tenglama tuziladi. Buning uchun avval
q_k1x₁+ q_k2x₂+ …+ q_knx_n≥q_k
tengsizlik tuziladi, sungra uni (-1) ga koʻpaytirib, x_n+1 qoʻshimcha oʻzgaruvchi kiritamiz.
-q_k1x₁- q_k2x₂- …- q_knx_n + x_n+1=q_k
Bunday tuzilgan tenglama kesuvchi tenglama deyiladi.
3.Kesuvchi tenglamani simpleks jadvalning m+2 qatoriga joylashtiramiz vaa simpleks jadvalni almashtirishlarini bajaramiz.
Agar hosil boʻlgan yangi simpleks jadvalda barcha x_i lar butun sonli (ya’ni hamma q_i=x_i-[x_i]=0) boʻlsa, topilgan echim berilgan butun sonli programmalash masalasining echimi boʻladi. Aks holda yuqoridagi 2 va 3 punktlar yana takrorlanadi. Umuman bu jarayon masalaning butun sonli echimi topulguncha yoki masalaning butun sonli echimi mavjud emasligi aniqlanguncha takrorlanadi.
Misol. Quyidagi chiziqli programmalash masalasining butun sonli echimini toping.

Masalani normal holga keltiramiz:

1. Masalani simpleks usulda echamiz.

BOʻ	1	-x1	-x2
x3	6	2	3
x4	3	2	-3
Z	8	3	1

2.

BOʻ	1	-x4	-x2
x3	3	-1	6
x1	1.5	0.5	-1.5
Z	3.5	-1.5	5.5

3.

BOʻ	1	-x4	-x3
x2	0.5	-0.17	0.17
x1	2.25	0.25	0.25
Z	0.75	-0.58	-0.92

Shunday qilib, masalaning masalaning optimal plani topildi, lekin bu plan butun sonli emas. Birinchi tenglamaning kasr qismi eng katta boʻlgani uchun, shu birinchi qatorga nisbatan kesuvchi tenglama tuzamiz:

Bu tengsizlikning ikki tomoniga (-1) ni koʻpaytirib, x₅ qoʻshimcha oʻzgaruvchini kiritamiz.Natijada quyidagiga ega boʻlamiz:
, ya’ni

Bu oxirgi tenglamada barcha koeffitsientlarning butun qismlari nulga teng boʻlgani sabab ular oʻzlari oʻzgarishsiz qoladi. Uni jadvalning oxiriga joylashtiramiz.

BО‘	1	-x4	-x3
x2	0.5	-0.17	0.17
x1	2.25	0.25	0.25
x5	-0.5	0.17	-0.17
Z	0.75	-0.58	-0.92

4.

Simpleks almashtirish qilib quyidagi jadvalga ega boʻlamiz.

BOʻ	1	-x4	-x5
x2	0.0	0.0	1.0
x1	1.5	0.5	1.5
x3	3.0	-1.0	-6.0
Z	3.5	-1.5	-5.5

endi simpleks jadvalning ikkinchi qatoriga nisbatan kesuvchi tenglamani tuzamiz.

Bu tengsizlikda koeffitsientlar butun qismi nuldan katta boʻlgani sabab q_i=x_i-[x_i], q_ij=a_ij-[a_ij] foydalanib ularning kasr qismini ajratamiz, ya’ni q₂=1.5-[1.5]=1.5-1=0.5, q₂₄=1.5-[1.5]=1.5-1=0.5.
Tengsizlikning ikki tomoniga (-1) ni koʻpaytirib, x₆ qoʻshimcha oʻzgaruvchini kiritamiz. Natijada quyidagiga ega boʻlamiz:
, ya’ni
Uni jadvalning oxiriga joylashtiramiz.
5.

BО‘	1	-x4	-x5
x2	0.0	0.0	1.0
x1	1.5	0.5	1.5
x3	3.0	-1.0	-6.0
x6	-0.5	-0.5	-0.5
Z	3.5	-1.5	-5.5

Simpleks almashtirish qilib quyidagi jadvalga ega boʻlamiz.

BOʻ	1	-x6	-x5
x2	-1.0	-1.0	2.0
x1	0.0	-1.0	3.0
x3	9.0	5.0	-12.0
x4	1.0	1.0	-2.0
Z	9.0	4.0	-11.0

6.

BOʻ	1	-x6	-x5
x2	0.0	1.0	0.0
x1	1.0	1.0	1.0
x3	4.0	-5.0	-2.0
x4	1.0	1.0	-2.0
Z	5.0	-4.0	-3.0

Hosil boʻlgan simpleks jadvalda ozod hadlar ustuni elementlari butun sonlardan iborat. Demak, butun sonli programmalash masalasi echimi X=(1,0,5,1) boʻladi va Z_min=5.