Mavzu: Simpleks metodining algoritmi. Sun’iy basis metodi Reja. Chiziqli dasturlash masalasining qo’yilishi

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
   

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