Vazifani bajaring. Vazifa

Vazifani bajaring.

1. 
   Vazifa. Berilgan Chiziqli Dasturlash Masalasini simpleks usuli bilan eching va optimal echimini aniqlang.
   

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

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

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

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

х₁³ 0, х₂³ 0, х₃³ 0

 Vazifaning yechilishi

I. Qo’shimcha noma’lumlarni kiritamiz

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

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

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

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

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

х₁³ 0, х₂³ 0, х₃³ 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 boshlang’ich tayanch rejani topamiz.
Z_max= 0 - ( - х ₁-2х₂-3х₃ + 0y₁+ 0y₂+ 0y₃).

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

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

y₃ = 10 - (х₁ + х₂- 3х₃).
Bu yerda

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

berilgan ChD masalasi boshlang’ich tayanch reja ega bo’ladi:

y ₁ = 14, y₂ = 21, y ₃ = 10, Z_max= 0 .
II. Boshlag’ich simpleks jadvalini tuzish

Boshlang’ich simpleks jadvali

Базис	Cj	Bi	х1	х2	х3	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 hal qiluvchi ustun, hal qiluvchi satr va hal 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 hal qiluvchi ustun bo’ladi.

 ozod hadlar ustunida keltirilgan [14 va 21] sonlarni x₃ hal 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 hal qiluvchi satr bo’ladi.

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

Birinchi simpleks jadvali

Базис	Cj	Bi	х1	х2	х3▼	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

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 koeffitsienti o’rniga x₃ asosiy noma’lumning koeffitsienti s_{3 =}3 ni yozamiz.
Yangi tuziladigan ikkinchi simpleks jadvalini qolgan elementlarini hisoblash Jordan chiqarish usuli yordamida topiladi, ya’ni:

Ikkinchi simpleks jadvali

Базис	Cj	Bi	х1	х2▼	х3	y1	y2	y3
			1	2	3	0	0	0
y1►	0	7/5	-1/5	[4/5]	0	1	-3/5	0	7/4
х3	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 hal qiluvchi ustun va y₁ satr hal qiluvchi satr bo’ladi.

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

Uchinchi simpleks jadvali

Базис	Cj		Bi		х1		х2		х3		y1		y2		y3
					1		2		3		0		0		0
х2	2		7/4		-1/4		1		0		5/4		-3/4		0
х3	3		7/2		½		0		1		-1/2		1/2		0
х6	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.

Asosiy noma’lumlarning qiymatlari: х ₁ = 0, х ₂ = 7/4, х ₃ = 7/2.

 Qo’shimcha noma’lumlarning qiymatlari: y₁ = 0, y₂= 0, y₃ =75/4.

 Topilgan echimlarni umumiy holda quyidagicha yozish mumkin:

Х = (х ₁, х ₂, х ₃, y₁, y₂, y ₃) = (0, 7/4, 7/2, 0, 0 , 75/4).

Funktsionalning qiymati quyidagiga teng bo’ladi:

Z_max= 3х₁+ 4х₂ + 2х₃ = 14

 Xulosa. Berilgan chiziqli dasturlash masalasida:

 Noma’lumlar soni 3 ta. Tenglamalar soni 3 ta.

 Uchta qo’shimcha noma’lum kiritildi.

 Masala uchta simpleks jadvalida optimal echimga ega bo’ldi. 1-simpleks jadvalida [2-satr, 3-ustun] elementi hal qiluvchi element qilib olindi. 2-simpleks jadvalida [1-satr, 2-ustun] elementi hal qiluvchi element qilib olindi.

 Berilgan masala Х* = (х₁, х₂, х₃) = (0, 7/4, 7/2) qiymatlarda optimal echimga ega bo’ladi. Maqsad funktsiyasining optimal qiymati Z_max = 14.