Usulda yechish. Ishning maqsadi


Download 58.35 Kb.
bet2/3
Sana27.01.2023
Hajmi58.35 Kb.
#1129999
1   2   3
Bog'liq
7 1 Amaliy mashg’ulot Chiziqli dasturlash masalasini simpleks

Zmax= х1+2х2+3х3+ 0y1+ 0y2+ 0y3
х1 + 2х2+ 3х3 + y1 = 14,
2х1 + 2х2+ 5х3 + y2 = 21 ,
х1 + х2- 3х3 + y3 = 10.
х1³ 0, х2³ 0, х3³ 0 , y1³ 0, y2³ 0, y3³ 0 .

 Berilgan tenglamalar sistemasidan y1³ 0, y2³ 0, y3³ 0 qo’shimcha noma’lumlarni bazis noma’lumlar sifatida qabul qilamiz va boshlang’ich tayanch rejani topamiz.


Zmax= 0 - ( - х 1-2х2-3х3 + 0y1+ 0y2+ 0y3).
y1 = 14 - (х1 + 2х2+ 3х3),
y2 = 21 - (2х 1 + 2х2+ 5х3),
y3 = 10 - (х1 + х2- 3х3).

Bu yerda


х1= х2= х 3 = 0 deb olsak,
berilgan ChD masalasi boshlang’ich tayanch reja ega bo’ladi:
y 1 = 14, y2 = 21, y 3 = 10, Zmax= 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, [x3] ustun hal qiluvchi ustun bo’ladi.
 ozod hadlar ustunida keltirilgan [14 va 21] sonlarni x3 hal qiluvchi ustuning [3 va 5] mos musbat sonlariga bo’lib, minimal qiymatini aniqlaymiz, ya’ni:
min[bi/aij]=min[14/3, 21/5]= 21/5 .

Demak, x4 satr hal qiluvchi satr bo’ladi.


 jadvaldagi hal qiluvchi ustun va hal qiluvchi satrlarning kesishgan kattakda joylashgan a32 =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 y2 qo’shimcha noma’lum (Bazis nomli ustundan) bazisdan chiqarilib o’rniga x3 asosiy noma’lum bazisga kiritiladi. Cj ustunga esa y2 qo’shimcha noma’lumning s5=0 koeffitsienti o’rniga x3 asosiy noma’lumning koeffitsienti s3 =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




Zj -Cj indeks qatorida bitta (-4/5) manfiy son mavjud. Demak, x2 ustun hal qiluvchi ustun va y1 satr hal qiluvchi satr bo’ladi.
Demak, y1 bazis noma’lumlar ustunidan chiqariladi va o’rniga x2 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: х 1 = 0, х 2 = 7/4, х 3 = 7/2.
 Qo’shimcha noma’lumlarning qiymatlari: y1 = 0, y2= 0, y3 =75/4.
 Topilgan echimlarni umumiy holda quyidagicha yozish mumkin:
Х = (х 1, х 2, х 3, y1, y2, y 3) = (0, 7/4, 7/2, 0, 0 , 75/4).
Funktsionalning qiymati quyidagiga teng bo’ladi:
Zmax= 3х1+ 4х2 + 2х3 = 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 Х* = (х1, х2, х3) = (0, 7/4, 7/2) qiymatlarda optimal echimga ega bo’ladi. Maqsad funktsiyasining optimal qiymati Zmax = 14.



Download 58.35 Kb.

Do'stlaringiz bilan baham:
1   2   3




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