5-ma’ruza Mavzu: Simpleks metodining algoritmi. Sun’iy basis metodi Reja

5-ma’ruza
Mavzu: Simpleks metodining algoritmi. Sun’iy basis metodi
Reja.

1. 
   Chiziqli dasturlash masalasining qo’yilishi
   
2. 
   Simpleks usulining algoritmi
   
3. 
   Ch. D. M. Simpleks usulida yechish namunasi
   

Kalit so’zlar: Simpleks usul, Sun’iy basis metodi, chiziqli dasturlash masalasi, maqsad funksiyasi, Simpleks usul algoritmi
Bizga chiziqli dasturlash masalasi berilgan bo’lsin.



Chiziqli dasturlash masalasi(CH.D.M)ning optimal yechimi uning bazis yechimlaridan birortasi bo’lib, unda maqsad funksiya minimal qiymatga erishadi.
(CH.D.M) ni yechishning simpleks usulini ko’rib chiqamiz.
Topilgan bazis yechimning optimal yechim bo’lishini tekshirish hamda, agar bu bazis yechim optimal yechim bo’lmasa, boshqa bazis yechimga o’tish qoidasi bilan tanishish uchun sistemani quyidagi ko’rinishga joylashtiramiz.

Bazis o’zgaruvchilar	B	Erkli o’zgaruvchilar
		Xm+1	Xm+2	..	Xn
X1	b1	a11	a12	…	a1n
X2	b2	a11	a12	…	a1n
…	….	…	…	..	..
Xm	b3	a11	a12	…	a1n
F	c0	C1	C2	…	Cn

Bunday jadval simpleks jadval deb ataladi.

C_1i i=1..n shart o’rinli bo’lsa, u holda topilgan X₀ bazis reja optimal reja deyiladi
Simpleks usuli algoritmi quyidagi bosqichlarni o'z ichiga oladi.

1. 
   Birinchi boshlang’ich bazis rejani tuzish . manfiy bo'lmagan qo'shimcha parametrlarini kiritish orqali chiziqli dasturlash masalasining kanonik shakliga o'tish.
   
2. 
   Rejani optimoptimallikka tekshirish . Agar kamida noldan kichik bo'lgan bitta ko'rsatkich qatori koeffitsienti bo'lsa, unda reja maqbul emas va uni takomillashtirish kerak.
   
3. 
   Asosiy ustun va qatorni aniqlang . Indeks qatorining manfiy koeffitsientlaridan mutlaq qiymat bo'yicha eng kattasi tanlangan. Keyin soddalashtirilgan jadvalning ustun elementlari yetakchi ustunning bir xil belgisining elementlariga bo'linadi.
   
4. 
   Yangi basis reja tuzish. Yangi rejaga o'tish Gauss usuli bo'yicha soddalashtirilgan jadvalni qayta hisoblash natijasida amalga oshiriladi .
   

Misol 1

L(x)=10x₁+12x₂+8x₃→max
3x₁+4x₂+2x₃≤1020
4x₁+3x₂+3x₃≤940
5x₁+3x₂+5x₃≤1010
x₁, x₂, x₃≥0


G(x)=10x₁+12x₂+8x₃+0x₄+0x₅+0x₆
3x₁+4x₂+2x₃+x₄=1020 3x₁+4x₂+2x₃+1x₄+0x₅+0x₆=1020
4x₁+3x₂+3x₃+x₅=940 => 4x₁+3x₂+3x₃+0x₄+1x₅+0x₆=940
5x₁+3x₂+5x₃+x₆=1010 5x₁+3x₂+5x₃+0x₄+0x₅+1x₆=1010
x₁, x₂, x₃, x₄, x₅,x₆ ≥0 x₁, x₂, x₃, x₄, x₅,x₆ ≥0

X	x1	x2	x3	x4	x5	x6	X^n
	1	4	2	1	0	0	1020
	4	3	3	0	1	0	940
	5	3	5	0	0	1	1010
L	-10	-12	-8	0	0	0	0

1024/4=255-min

940/3 313,33
1010/3 336,67


Mustaqil yechish uchun topshiriqlar
Quyidagi dasturlash masalalarni simpleks usul bilan yeching

L(x)=15x₁+8x₂+20x₃→max
3x₁+4x₂+2x₃≤850
4x₁+3x₂+6x₃≤900
6x₁+7x₂+5x₃≤1050



Mavzu yuzasidan savollar

1. 
   Chiziqli dasturlash masalasining qo’yilishi
   
2. 
   Simpleks usul algoritmi