2-Amaliy mashg`ulot: Chiziqli dasturlash masalasini Simpleks usuli bilan yechish. Ishning maqsadi

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 c₅=0 koeffitsienti o’rniga x₃ asosiy noma’lumning koeffitsienti c_{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.

Topshiriqlar

Quyidagi ChD masalalarini simpleks usuli bilan eching:

a) berilgan masaladagi tengsizliklar sistemasini tenglamalar sistemasiga keltiring;
b) qo’shimcha noma’lumlarni kiriting;
c) boshlang’ich tayanch echimni toping;
d) boshlang’ich simpleks jadvalini tuzing;
e) Simpleks jadvalida hal qiluvchi ustun (HQU)ni, hal qiluvchi satr (HQS)ni va hal qiluvchi elementi (HKE)ni aniqlang. ChDMda boshlang’ich simpleks jadvalidan yangi simpleks jadvaliga o’tishning asosiy qoidalarini yozing va bajarilgan hisoblashlarni keltiring.

 4.1.1	 4.1.2	 4.1.3	 4.1.4