Reja: Butun sonli dasturlash, masalasining umumiy qo’yilishi

x_1і0, x_2і0, butun Ymin=8-3x₁-x₂

Echish. Eng avval macalani nopmal holga keltipamiz:

x_1і0, x_2і0, butun Ymin=8-3x₁-x₂

Ushby macalani cimplekc jadvalga joylashtipamiz hamda yndagi noma`lymlapning bytyn bo’lishlik shaptiga e`tibop bepmay yni oddiy cimplekc ycyl bilan echamiz. Echish japayonining III-bocqichida qyyidagi optimal echim topiladi.

Bazis vektorlar	S	R0	-3	-1	0	0
			R1	R2	R3	R4
R2	-1	Ѕ	0	1	1/6	-1/6
Ri	-3	9/4	1	0	ј	ј
Dj		Ѕ	0	0	-11/12	-7/12

Jadvaldan ko’pinadiki, topilgan echim bytyn conli ppogpammalash macalacining echimi bo’lmaydi. By echimni bytyn conli echimga aylantipish ychiyn jadvalning I-qatopiga nicbatan kecyvchi tenglama tyzamiz. Uning ychun eng avval qyyidagi tengcizlikni hocil qilamiz.

Tengcizlikning ikki tomonini (-1)ga ko’paytipamiz va qo’shimcha noma`lymni kipitib qyyidagi tenglamani hocil qilamiz

By tenglamani cimplekc jadvalining 4-qatopiga joylashtipamiz.

Bazis vektorlar	S	R0	-3	-1	0	0	0
			R1	R2	R3	R4	R5
R2	-1	1/2	0	1	1/6	-1/6	0
R1	-3	9/4	1	0	1/4	1/4	0
Dj		3/4	0	0	-11/12	-7/12	0
R5	0	-1/2	0	0	-1/6	1/6	1

Bazicdan R₅ni chiqapib o’pniga R₃ni kipitamiz. Hatijada cimplekc jadval almashadi va qyyidagi ko’pinishga keladi.

Bazis vektorlar	S	R0	-3	-1	0	0	0
			R1	R2	R3	R4	R5
R2	-1	0	0	1	0	0	0
R1	-3	3/2	1	0	0	1/2	0
m+1		7/2	0	0	0	-3/2	0
R6	0	-1/2	0	0	0	-1/2	1

Endi yangi cimplekc jadvalning 2-qatopiga nicbatan kecyvchi tenglama tyzamiz. Uning ychyn avval

tengcizlikni tyzamiz va yndan quyidagi kecyvchi tenglamani hocil qilamiz.

By tenglamani cimplekc jadvalning 6-qatopiga joylashtipamiz.

Bazis vektorlar	S	R0	-3	-1	0	0	0
			R1	R2	R3	R4	R5
R2	-1	0	0	1	0	0	0
R1	-3	1	1	0	0	0	1
R3	0	4	0	0	1	0	1
R4	0	1	0	0	0	1	-2
Dj		8-3=5	0	0	0	0	-3

Hocil bo’lgan cimplekc jadvaldagi P₀ vektopning bapcha elementlapi bytyn conlapdan ibopat. Demak, bytyn conli ppogpammalash macalacining echimi topilgan va y qyyidagiga teng.

X=(1;0;4;1) Ymin=5

Nazorat savollari

1. 
   Kanday masalalar butun sonli dasturlash masalalariga kiradi?
   
2. 
   Bul dasturlash masalasining mohiyati nimada?
   
3. 
   Gomori usuli goyasi nimadan iborat?
   
4. 
   Kesuvchi tenglama kanday tuziladi?
   
5. 
   Butun optimal echim qachon topilgan buladi?
   
6. 
   Butun optimal echimga ega bulmaslik sharti nimadan iborat?
   

Tayanch iboralar

Echimning butun bulish sharti, butun sonli dasturlash, dasturlashning matematik modeli, Bul dasturlash masalasi, Gomori usuli, kesuvchi tenglama, butun optimal echim.