Berilgan ChDMni simpleks usuli bilan yechish va optimal yechimini aniqlash. Zmax= X

15-Amaliy mashgulot

Berilgan ChDMni simpleks usuli bilan yechish va optimal yechimini aniqlash.

Z_max= x₁+2x₂+3x₃

x₁ + 2x₂ + 3x₃ £ 14,

2x₁ + 2x₂ + 5x₃ £ 21,

x₁ + x₂ - 3x₃ £ 10.

x₁³ 0, x₂³ 0, x₃³ 0

Vazifaning echilishi

I. Qo’shimcha no’malumlarni kiritamiz

ChDMdagi tengsizliklarni tenglikka aylantirish uchun y₁³ 0, y₂³ 0, y₃³ 0 qo’shimcha noma’lumlarni musbat ishora bilan qo’shamiz. Maqsad funkstiyasiga qo’shimcha noma’lumlar 0 koeffistient bilan kiritiladi. Natijada berilgan ChDM quyidagi ko’rinishni oladi:

Z_max= x₁+2x₂+3x₃+ 0y₁+ 0y₂+ 0y₃

x₁ + 2x₂+ 3x₃ + y₁ = 14,

2x₁ + 2x₂+ 5x₃ + y₂ = 21 ,

x₁ + x₂- 3x₃ + y₃ = 10.

x₁³ 0, x₂³ 0, x₃³ 0 , y₁³ 0, y₂³ 0, y₃³ 0 .
 Berilgan tenglamalar sistemasidan y₁³ 0, y₂³ 0, y₃³ 0 qo’shimcha noma’lumlarni bazis noma’lumlar sifatida qabul qilamiz va boshlanғich tayanch rejani topamiz.

Z_max= 0 - ( - x ₁-2x₂-3x₃ + 0y₁+ 0y₂+ 0y₃).

y₁ = 14 - (x₁ + 2x₂+ 3x₃),

y₂ = 21 - (2x ₁ + 2x₂+ 5x₃),

y₃ = 10 - (x₁ + x₂- 3x₃).

Bu erda

x₁= x₂= x ₃ = 0 deb olsak,

berilgan ChD masalasi boshlanғich tayanch reja ega bo’ladi:

y ₁ = 14, y₂ = 21, y ₃ = 10, Z_max= 0 .

II. Boshlaғich simpleks jadvalini tuzish

Boshlanғich simpleks jadvali

Bazis	Cj	Bi	x1	x2	x3	y1	y2	y3
			c1=1	c2=2	c3=3	c4=0	c5=0	c6=0
y1	c4=0	b1=14	1	2	3	1	0	0
y2	c5=0	b2=21	2	2	5	0	1	0
y3	c6=0	b3=10	1	1	-3	0	0	1
Zj -Cj		0	-1	-2	-3	0	0	0

III. Optimal rejani topish

 Endi ҳal qiluvchi ustun, ҳal qiluvchi satr va ҳal qiluvchi elementlarni aniqlashga o’tamiz.

Buning uchun:

 jadvaldagi indeks qatorida keltirilgan [-1, -2, -3] sonlardan absolyut qiymati bo’yicha eng kattasi 3 ga teng. Demak, [x₃] ustun ҳal qiluvchi ustun bo’ladi.

 ozod ҳadlar ustunida keltirilgan [14 va 21] sonlarni x₃ ҳal qiluvchi ustuning [3 va 5] mos musbat sonlariga bo’lib, minimal qiymatini aniqlaymiz, ya’ni:

min[b_i/a_ij]=min[14/3, 21/5]= 21/5 .

Demak, x₄ satr ҳal qiluvchi satr bo’ladi.

 jadvaldagi ҳal qiluvchi ustun va ҳal qiluvchi satrlarning kesishgan kattakda joylashgan a₃₂ = 5 son ҳal qiluvchi element bo’ladi. Bu sonni jadvalda to’ғri to’rtburchak ichiga olib qo’yamiz.

Endi ikkinchi simpleks jadvalini tuzishga o’tamiz.

Buning uchun y₂ qo’shimcha noma’lum (Bazis nomli ustundan) bazisdan chiqarilib o’rniga x₃ asosiy noma’lum bazisga kiritiladi. C_j ustunga esa y₂ qo’shimcha noma’lumning s₅=0 koeffistienti o’rniga x₃ asosiy noma’lumning koeffistienti s₃ = 3 ni yozamiz.

Birinchi simpleks jadvali

Bazis	Cj	Bi	x1	x2	x3▼	y1	y2	y3
			1	2	3	0	0	0
y1	0	14	1	2	3	1	0	0	14/3
y2►	0	21	2	2	[5]	0	1	0	21/5
y3	0	10	1	1	-3	0	0	1	inf
Zj -Cj		0	-1	-2	-3	0	0	0

Yangi tuziladigan ikkinchi simpleks jadvalini qolgan elementlarini ҳisoblash Jordan chiqarish usuli yordamida topiladi, ya’ni:

Ikkinchi simpleks jadvali

Bazis	Cj	Bi	x1	x2▼	x3	y1	y2	y3
			1	2	3	0	0	0
y1►	0	7/5	-1/5	[4/5]	0	1	-3/5	0	7/4
x3	c3=3	21/5	2/5	2/5	1	0	1/5	0	21/2
y3	0	113/5	11/5	11/5	0	0	3/5	1	113/11
Zj -Cj		63/5	1/5	-4/5	0	0	3/5	0

Z_j -C_j indeks qatorida bitta (-4/5) manfiy son mavjud. Demak, x₂ ustun ҳal qiluvchi ustun va y₁ satr ҳal qiluvchi satr bo’ladi.

Demak, y₁ bazis noma’lumlar ustunidan chiqariladi va o’rniga x₂ asosiy noma’lum kiritiladi. Ikkinchi simpleks jadvalida ҳal qiluvchi element bo’yicha simpleks ҳisoblashlarini bajaramiz va uchinchi simpleks jadvalini ҳosil qilamiz.

Uchinchi simpleks jadvali

Bazis	Cj	Bi	x1	x2	x3	y1	y2	y3
			1	2	3	0	0	0
x2	2	7/4	-1/4	1	0	5/4	-3/4	0
x3	3	7/2	½	0	1	-1/2	1/2	0
x6	0	75/4	11/4	0	0	-11/4	9/4	1
Zj -Cj		14	0	0	0	1	0	0

Oxirgi simpleks jadvalining indeks qatoridagi barcha sonlar musbat. Demak berilgan masala optimal echimga ega.

Simplex usul uchun variantlar

1. Zmax= 3x1+2x2+5x3 x1 + 2x2 + 3x3  12, 2x1 + 4x2 + x3  16. x1 0, x2 0, x3 0
2. Zmax= 4x1- 3x2 + 5x3 x1 + 2x2 + 4x3  18, 2x1 + 4x2 + 3x3  24. x1 0, x2 0, x3 0	3. Zmax= 2x1 + 3x2 + 4x3 2x1 + 3x2 - 4x3  28, x1 + 2x2 + 3x3  32. 6x1 + 0x2 + 5x3  36. x1 0, x2 0, x3 0.
4. Zmax= 4x1 + 3x2 + 2x3 2x1 + 3x2 + 4x3  40, x1 + 2x2 + 3x3  32. 6x1 + 0x2 + 5x3  30. x1 0, x2 0, x3 0.	5. Zmax= 4x1+3x2+6x3 2x1 + 3x2 + 4x3  44, x1 + 2x2 + 3x3  36. 6x1 + 0x2 + 5x3  60. x1 0, x2 0, x3 0
6. Zmax= 2x1+3x2+4x3 2x1 + 3x2 - 4x3  14, x1 + x2 + 0x3  24, 3x1 + 2x2 +5x3  36, 4x1 + 6x2 + 4x3  40. x1 0, x2 0, x3 0	7. Zmax = 5x1 +4x2+2x3 2x1 + 3x2 - 4x3  14 , x1 + x2 + 0x3  24, 3x1 + 2x2 + 5x3  36, 4x1 +6x2 + 4x3  40. x1 0, x2 0, x3 0
8. Zmax= 4x1+3x2+2x3 2x1+ 3x2 + x3  4 , x1 + 2x2 + 3x3  6 , 3x1+ 2x2+ 2x3  4 . x1 0, x2 0, x3 0.	9. Zmax = 2x1+4x2+3x3 2x1+3x2+ x3  4, x1+ 2x2+ 3x3  6, 3x1+ 2x2+ 2x3  4, x1 0, x2 0, x3 0.
10. Zmax= 3x1+ 4x2+ 2x3 2x1+ 3x2+ x3  4, x1+ 2x2+ 3x3  6, 3x1+ 2x2+ 2x3  12. x1 0, x2 0, x3 0.	11. Zmax= 3x1+ 4x2+2x3 x1 + 2x2 + 4x3  14, x1 + 2x2 - 2x3  6, 3x1+ 2x2+ 2x3  12 x1 0, x2 0, x3 0
12. Zmax= 4x1 + 4x2 + 3x3 x1 + 2x2 + 4x3  12, x1+ 2x2 - 2x3  6, 3x1 + 2x2+2x3  24. x1 0, x2 0, x3 0	13. Zmax=4x1+ x2+3x3 4x1+2x2-3x3  10, x1+ 2x2+2x3  6, 3x1+2x2+2x3  14. x1 0, x2 0, x3 0.
14. Zmax= 2x1+ 4x2 + 5x3 2x1+ 2x2 + 6x3  10, 4x1+ 5x2 + 2x3  24, 6x1+ 3x2 + 6x3  46. x1 0, x2 0, x3 0	15. Zmax= 6x1+7x2+6x3 6x1+ 2x2 + 3x3  12, 2x1+ 5x2 + 2x3  30, 5x1+ 3x2  46. x1 0, x2 0, x3 0