3-4 tajriba ishi

410-GURUH TALABASI BOLTABOYEV BAXROM

3-4 - tajriba ishi
Mavzu: Chiziqli dasturlash masalalarini simpleks usulida yechish
1.Har doimgidek 4-o’rindagi topshiriqni bajaraman

x1 + 2x2 <= 10

3x1 – 3x2 <=6

2x1 + 3x2 <=6

x1 >=0 , x2 >=0

f=x1+6x2 max


Grafik usul

1-ish. Dastlab berilgan masalani geometrik usulda yechamiz. Buning uchun

yuqoridagi tengsizlik shaklida berilgan cheklamalarni tenglama shaklida ifodalab

olamiz. U quyidagi ko’rinishda bo’ladi

x1 + 2x2 = 10

3x1 – 3x2 =6

2x1 + 3x2 =6

x1 >=0 , x2 >=0

Sistemadagi tenglamalarning birma-bir grafiklarini chizamiz.


x1 + 2x2 = 10 (1)

3x1 – 3x2 =6 (2)

2x1 + 3x2 =6 (3)

f1=x1+6x2 = 6

5.2-rasmdagi grafikdan ko„rinib turibtiki maqsad funksiyasining qiymati oxy o’qi bilan hosil bo’lgan uchburchak ichida yotibti. Maqsad funksiyasining maksimal qiymatini topishuchun tenglamaning grafigini o’ng tamonga parallel ravishda ko’chiramiz.2 va 3 tenglamalar kesishgani uchun ularni tanlab olamiz.

1 va 2 – tenglamarni sistemaga olib natijani hisoblimiz.

Natija:

X1=0 , x2= 2 , F= x1+6x2=12

Simpleks usuli


x1 + 2x2 = 10

3x1 – 3x2 =6

2x1 + 3x2 =6

1-qadam. Hosil qilingan tenglamalar sistemasini vektor shaklida yozamiz:

Bu yerda



1 2 10 0 0 10

P1= 3 P2= -3 P3= 6 P4= 1 P5= 0 P0= 6

2 3 6 0 1 6

Bazis vektorlar: P3, P4,P5 Таянч режа: X* = (0,0,10,6,6)
Ushbu ma‟lumotlar asosida simpleks jadvalini tuzib, va X* tayanch rejani

optimallikka tekshiramiz.

Dastlabki X* tayanch rejani optimallikka tekshirish

Iteratsiya 1

Tayanch reja optimal emasligi muqarrar, chunki 4-satrda manfiy elementlar

bor, shartga ko„ra ular barchasi nomanfiy bo„lishi kerak. Demak, yangi tayanch

rejani qidiramiz. Buning uchun avval mazkur jadvaldagi yo„naltiruvchi ustun va

yo„naltiruvchi satrni topamiz. Yo’naltiruvchi ustunni topish uchun 5.1-jadvalning 4 satrida joylashgan

qiymatlarning modulini olamiz, moduli eng katta bo„lgan qiymatni tanlaymiz va

shu son joylashgan yacheyka (katak) ni belgilaymiz, yacheyka joylashgan ustun

yo„naltiruvchi ustun hisoblanadi. Bizning misolimizda, -6 bo’ladi va

yo„naltiruvchi ustun P2 joylashgan 6-ustun bo„ladi.

Yo„naltiruvchi satrni topish uchun 5.1-jadvaldagi 4-ustunda joylashgan P0

ning qiymatlarini mos ravishda yo’naltiruvchi ustun P2 da joylashgan qiymatlarga

bo„lamiz, ular orasidan eng kichik bo„linmani tanlaymiz va shu bo„linma

joylashgan satr yo„naltiruvchi satr hisoblanadi.

Yangi iteratsiyaga o’tish

Bu qadamda ish jadvaldagi yo„naltiruvchi satrni to„ldirishdan boshlanadi.

Buning uchun yo„naltiruvchi ustun va satrning kesishish yacheykasida joylashgan

element ( 7 ) ga satr elementlari mos ravishda bo„lib yoziladi. 3-satrda joylashgan

P5 ning o„rniga P2 ni yozamiz. 6-ustunda joylashgan yo„naltiruvchi ustundagi P2 ni

qiymatlarining o„rniga 9-ustunda joylashgan P5 ning qiymatlari mos ravishda

qo„yiladi.

Shundan so’ng ushbu holat yuzaga keladi

Bu tayanch reja optimal, chunki 4-satrda manfiy elementlar yo„q.

Javob:

Optimal tayanch reja: (0,2)

Maksimal qiymat: 12

SimplexWin 3.1 dasturi orqali yechish