Tmc institute in Tashkent

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

Misol. quyidagi chiziqli dasturlash masalasining butun sonli yechimini toping. Masalani normal holga keltiramiz:
Masalani simpleks usulda yechamiz.
1.

BO‘	1	-x4	-x2		BO‘	1	-x4	-x3
x3	3	-1	6		x2	0.5	-0.17	0.17
x1	1.5	0.5	-1.5		x1	2.25	0.25	0.25
Z	3.5	-1.5	5.5		Z	0.75	-0.58	-0.92

2.
Shunday qilib 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, x5 qo‘shimcha o‘zgaruvchini kiritamiz. Natijada quyidagiga ega bo‘lamiz: , ya'ni Bu oxirgi tenglamada barcha koeffitsientlarning butun qismlari nolga teng bo‘lgani sabab, ular o‘zgarishsiz qoladi. Uni jadvalning oxiriga joylashtiramiz.

BO‘	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.

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

Simpleks almashtirish qilib quyidagi jadvalga ega bo‘lamiz.
Endi simpleks jadvalning ikkinchi qatoriga nisbatan kesuvchi tenglamani tuzamiz. Bu tengsizlikda koeffitsientlar butun qismi noldan katta bo‘lgani sabab qi=xi-[xi], qij=aij-[aij] lardan foydalanib ularning kasr qismini ajratamiz, ya'ni q2=1.5-[1.5]=1.5-1=0.5, q24=1.5-[1.5]=1.5-1=0.5. Tengsizlikning ikki tomoniga (-1) ni ko‘paytirib, x6 qo‘shimcha o‘zgaruvchini kiritamiz. Natijada quyidagiga ega bo‘lamiz: , ya'ni Uni jadvalning oxiriga joylashtiramiz

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
x6	-0.5	-0.5	-0.5
Z	3.5	-1.5	-5.5

5.

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

Simpleks almashtirishlar qilib quyidagi jadvalga ega bo‘lamiz.
Hosil bo‘lgan simpleks jadvalda ozod hadlar ustuni elementlari butun sonlardan iborat. Demak, butun sonli dasturlash masalasi yechimi X=(1,0,4,1) bo‘ladi va Zmin=5.

E’tiboringiz uchun rahmat