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


Download 1.82 Mb.
Sana03.11.2023
Hajmi1.82 Mb.
#1742951
Bog'liq
5-maruza


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.


C1i i=1..n shart o’rinli bo’lsa, u holda topilgan X0 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)=10x1+12x2+8x3→max
3x1+4x2+2x3≤1020
4x1+3x2+3x3≤940
5x1+3x2+5x3≤1010
x1, x2, x3≥0


G(x)=10x1+12x2+8x3+0x4+0x5+0x6
3x1+4x2+2x3+x4=1020 3x1+4x2+2x3+1x4+0x5+0x6=1020
4x1+3x2+3x3+x5=940 => 4x1+3x2+3x3+0x4+1x5+0x6=940
5x1+3x2+5x3+x6=1010 5x1+3x2+5x3+0x4+0x5+1x6=1010
x1, x2, x3, x4, x5,x6 ≥0 x1, x2, x3, x4, x5,x6 ≥0


X

x1

x2

x3

x4

x5

x6

Xn




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)=15x1+8x2+20x3→max
3x1+4x2+2x3≤850
4x1+3x2+6x3≤900
6x1+7x2+5x3≤1050



Mavzu yuzasidan savollar

  1. Chiziqli dasturlash masalasining qo’yilishi

  2. Simpleks usul algoritmi

Download 1.82 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling