Zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universtiteti


Download 232.03 Kb.
bet2/6
Sana11.05.2023
Hajmi232.03 Kb.
#1449986
1   2   3   4   5   6
Bog'liq
J

n
j1

aijxj



bi,

(i



,1m)

xj



0

(

j



,1n)

F



n
j1

cixi



max
















(4.1)

Berilgan masalani simpleks usuli yordamida yechish g’oyasini berish uchun berilgan masalani quyidagicha kanonik formada yozib olamiz:







































































a11x1a12x2...a1nxnxn1b1
 a21x1a22x2...a2nxnxn2b2

 .......................................................
 am1x1am2x2...amnxnxnmbm

xj



0

(i



,1m)

(

j



,1n)

F



c1x1



c

2x2



...

c

nxn



0

*

x

n1



0

*

x

n2



...

0

*

x

nm



max

(4.2)


Ushbu masalani vektor ko„rinishida qayta yozib olamiz

x1P1



x2P2



...

xnPn



xn1Pn

1



xn2Pn

2



...

xnmPn

m



P0

(4.3)

shartlar bajarilganda



F



c1x1



c2x2



...cnxn



0

*xn1



0*xn2



...0*xnm



max

(4.4)

funksiyaning maksimumi topilsin, bu yerda P1,P2,...,Pn va P lar m-o„lchovli 0
ustun-vektorlar bo„lib, ular berilgan masaladagi noma‟lum va ozod hadlardan tuzilgan:

P0



b1


...
b2

bm





;


P1



a11

...
a21
am1





;



P2



a12


...
a22
am2



;...;

Pn



a1n


...
a2n
amn





;



Pn1



1


 ...
0


;
 0

Pn2



 0



1
...



;...;
 0

Pnm



 0

 ...
0  
1 



Ta‟rif.

X

(

x1,x2,...,nx) reja tayanch reja deb ataladi, agarda barcha

jx



0




o„zgaruvchilarning koeffitsiyentlari chiziqli bog„liqsiz

jP vektorlarda musbat

sonlardan iborat
bo„lsa.

(

x1,x2,...,nx) nuqta ko‘pyoqli yechimning uchi bo‘lsa, u


Teorema. Agar

X

holda (4.3) yoyilmadagi har bir

x

j x

j



0) larga mos

P vektorlar o‘zaro chiziqli j

bog‘liqsiz bo‘ladi.
Bu yerda:

Bazis vektorlar:

Tayanch reja:



Tayanch reja uchun (4.2) shartlardagi noma’lumlar o‘rniga nol qiymat
qo‘yib ( ) bazis o‘zgaruvchi (xn+1=b1, xn+2=b2,…,xn+m=bm) lar
topiladi.

Yangi simpleks jadvalini to„ldirishni yo„naltiruvchi satrni to„ldirishdan boshlaymiz. Buning uchun, 2-satrning har bir elementlarini yechuvchi songa bo„lib chiqamiz. Jadvalning boshqa yacheykalarini shu yo„naltiruvchi satr yordamida to„ldirib chiqamiz. Navbatdagi bosqichda ohirgi simpleks jadvalining m+1 satri tahlil qilinadi. Agar bu satr elementlarining barcha musbat sonlarga o„zgargan bo„lsa, optimal yechimni izlash jarayoni to„xtatiladi. Agar bu satrda manfiy ishorali sonlar hali ham mavjud bo„lsa, yechimni izlash jarayoni yuqorida ko„rsatilgan ketma-ketlikda yana davom ettiriladi. Toki bu jarayon m+1 satrida manfiy ishorali sonlar qolmagunga qadar davom ettiriladi. m+1 satridagi barcha sonlar musbat ishorali sonlarga aylanib bo„lgach, yechimni izlash jarayoni to„xtatiladi va optimal yechim sifatida noma‟lumlarga mos ravishda P0 ustundagi qiymatlar, maqsad funksiyasining maksimal qiymati 4.1-jadvaldagi F0 o„rnidagi son olinadi. Shu tariqa, berilgan chiziqli dasturlash masalasining simpleks usuli yordamida optimal yechimi va maqsad funksiyasining maksimal qiymati topiladi.Аmaliy muammolarni hal qilish uchun dasturiy ta'minot usullarining samaradorligi, ayniqsa,bir xil turdagi amallarni kop marotaba bagarishga duch kelganda namoyon bo'ladi. Oddiy va dasturiy usullarni solishtirish va tasavvur qilish uchun biz o`n qavatli binoga zinapoyada va liftda chiqish garajonlarini korib chiqailik. Ushbu ikki usulni boshdan kechirgan kishi tabiiy ravishda liftni tanlaydi. Shunga o'xshab, muammoni hal qilish uchun dasturiy ta'minot usullarini o'zlashtirganlar hamma joyda, muammoni hal qilishning aynan dasturiy ta'minot usulini qo'llashga intilishadi. Buning uchun algoritmlarni loyihalash, ularni algoritmik dasturlash tillarida taqdim etish va EXM da dasturlarni sozlash jarayonlarini o'zlashtirishi kerak bo`ladi. Ushbu cursni tuzilishi va mavzulari aynan shu maqsad asosida shakllanadi.


Yo„naltiruvchi satrni topish uchun 4.3-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. Bizning msolimizda
Hisoblash jarayonlarini shartli ravishda chiziqli va tarmoqlanadigan turlarga bo'lish mumkin. Chiziqli dasturlash jarayoni - bu hisoblash jarayonlari bo'lib, unda hisob-kitoblar istisnosiz qat'iy belgilangan ketma-ketlik bo'yicha amalga oshiriladi. Bunday jarayonlarga oldindan belgilangan takrorlanuvchi soni bilan davriy jarayonlar kiradi. Yangi simpleks jadvalini to„ldirishni yo„naltiruvchi satrni to„ldirishdan boshlaymiz. Buning uchun, 2-satrning har bir elementlarini yechuvchi songa bo„lib chiqamiz. Jadvalning boshqa yacheykalarini shu yo„naltiruvchi satr yordamida to„ldirib chiqamiz. Navbatdagi bosqichda ohirgi simpleks jadvalining m+1 satri tahlil qilinadi. Agar bu satr elementlarining barcha musbat sonlarga o„zgargan bo„lsa, optimal yechimni izlash jarayoni to„xtatiladi. Agar bu satrda manfiy ishorali sonlar hali ham mavjud bo„lsa, yechimni izlash jarayoni yuqorida ko„rsatilgan ketma-ketlikda yana davom ettiriladi. Toki bu jarayon m+1 satrida manfiy ishorali sonlar qolmagunga qadar davom ettiriladi. m+1 satridagi barcha sonlar musbat ishorali sonlarga aylanib bo„lgach, yechimni izlash jarayoni to„xtatiladi va optimal yechim sifatida noma‟lumlarga mos ravishda P0 ustundagi qiymatlar, maqsad funksiyasining maksimal qiymati 4.1-jadvaldagi F0 o„rnidagi son olinadi. Shu tariqa, berilgan chiziqli dasturlash masalasining simpleks usuli yordamida optimal yechimi va maqsad funksiyasining maksimal qiymati topiladi.
Masalani berilishidan ko'rinib turibdiki, ushbu yig'indini hisoblash jarayoni hech qanday murakkablikka ega emas, balki bir xil turdagi hisoblashlarni ko'p marta takrorlash bilan bog'liq. Hozirgi kunda dasturlash ko'nikmalarini yaxshi bilmagan odamga ham bu hisob-kitoblarni bajarishga ko'ndirish qiyin. Endi har bir ozmi-ko'pmi bilimli odam intuitiv ravishda bunday muammolarga darhol javob beradigan vositalar mavjudligini anglaydi. Lift bilan bog'liq yuqoridagi Yangi simpleks jadvalini to„ldirishni yo„naltiruvchi satrni to„ldirishdan boshlaymiz. Buning uchun, 2-satrning har bir elementlarini yechuvchi songa bo„lib chiqamiz. Jadvalning boshqa yacheykalarini shu yo„naltiruvchi satr yordamida to„ldirib chiqamiz. Navbatdagi bosqichda ohirgi simpleks jadvalining m+1 satri tahlil qilinadi. Agar bu satr elementlarining barcha musbat sonlarga o„zgargan bo„lsa, optimal yechimni izlash jarayoni to„xtatiladi. Agar bu satrda manfiy ishorali sonlar hali ham mavjud bo„lsa, yechimni izlash jarayoni yuqorida ko„rsatilgan ketma-ketlikda yana davom ettiriladi. Toki bu jarayon m+1 satrida manfiy ishorali sonlar qolmagunga qadar davom ettiriladi. m+1 satridagi barcha sonlar musbat ishorali sonlarga aylanib bo„lgach, yechimni izlash jarayoni to„xtatiladi va optimal yechim sifatida noma‟lumlarga mos ravishda P0 ustundagi qiymatlar, maqsad funksiyasining maksimal qiymati 4.1-jadvaldagi F0 o„rnidagi son olinadi. Shu tariqa, berilgan chiziqli dasturlash masalasining simpleks usuli yordamida optimal yechimi va maqsad funksiyasining maksimal qiymati topiladi.muammoda bo'lgani kabi: nega lift bo'lganida zinapoyadan o'ninchi qavatga ter to`kib chiqish kerak? Bu xolat har qanday joyda, ozmi-ko'pmi murakkab 2 muammolarga duch kelganda rivojlanishi kerak bo'lgan psixologiyaning turidir. U muammoning dasturiy yechimlarini izlashi va bunday dasturlarni tuzishga qodir bo'lishi kerak. Siklik hisoblashni dasturlash jarayonini tasvirlash uchun yuqoridagi yig'indini hisoblashning blok-sxemasini tasvirlaymiz.
Chiziqli dasturlashning asosiy masalasini geometrik usulda yechganda tenglamalar sistemasiga va maqsad funksiyasiga kiruvchi o„zgaruvchilar kiruvchi o„zgaruvchilar soni qancha kam bo„lsa, masalani yechish shuncha osonlashadi. Agar o„zgaruvchilar soni juda ko„p bo„lsa, masalan qavariq shakl uchlarining soni bir necha million bo„lsa, u holda madsad funksiyasining eng katta (eng kichik) qiymatlarini topish hozirgi zamon hisoblash mashinalariga ham o„g„irlik qiladi. Shu kabi, ko„p o„zgaruvchili chiziqli dasturlash masalalarini yechish uchun maxsus usullar ishlab chiqish lozimki, ko„pyoqning uchlarini tanlash tartibsiz emas, balki maqsadli ravishda amalga oshirilsin. Masalan, ko„pyoqning qirralari bo„ylab shunday harakat qilish lozimki, har bir qadamda maqsad funksiyasi F ning qiymati maksimum (minimum) qiymatga tomon tartibli ravishda intilsin. Chiziqli dasturlashning shu ko„rinishdagi masalalarini yechish uchun maxsus analitik usul – simpleks usuli yaratilgan. Simpleks usuli birinchi bo„lib amerikalik olim D. Dansig tomonidan 1949 yilda taklif etilgan bo„lib, keyinchalik 1956 yilda Dansig, Ford, Fulkeron va boshqalar tomonidan to„la rivojlantirildi. Lekin 1939 yilda rus matematigi L. V. Kantorovich va uning shogirtlari asos solgan “Yechuvchi ko„paytuvchilar usuli” simpleks usulidan ko„p farq qilmaydi. “Simpleks” so„zi n o„lchovli fazodagi n+1 ta uchga ega bo„lgan oddiy ko„pyoqni ifodalaydi.
Shunga o'xshash usullar barcha keng tarqalgan standart funktsiyalar qiymatlarini hisoblash uchun ishlatiladi. Tegishli dasturlar EXMning operatsion tizimiga joylashtirilgan va agar kerak bo'lsa, biz tanlangan dasturlash tilining yozuvlariga muvofiq funktsiya turini ixtiyoriy usulda yozishimiz mumkin. Shu bilan birga, har bir bunday funktsiya ortida qandaydir blok-sxema va hisoblash dasturi turishini unutmasligimiz kerak. Yana shuni ta`kidlashimiz joizki: har qanday yaqinlashuvchi funktsional qatorlarning yig'indisi ham qandaydir funktsiyalarni ifodalaydi. Shunday qilib, blok-sxema shaklida taqdim etilgan yig'indilarni hisoblash algoritmi ham umumiy va universaldir. Agar qo`shiluvchilar turini yoki qo`shiluvchilar sonini o'zgartirish zarur bo'lsa, bu o'zgarishlarni bloksxema va dasturga kiritish lozim. Shu bilan birga, umumiy tarkibi saqlanib qoladi.
Chiziqli dasturlashning asosiy masalasini geometrik usulda yechganda tenglamalar sistemasiga va maqsad funksiyasiga kiruvchi o„zgaruvchilar kiruvchi o„zgaruvchilar soni qancha kam bo„lsa, masalani yechish shuncha osonlashadi. Agar o„zgaruvchilar soni juda ko„p bo„lsa, masalan qavariq shakl uchlarining soni bir necha million bo„lsa, u holda madsad funksiyasining eng katta (eng kichik) qiymatlarini topish hozirgi zamon hisoblash mashinalariga ham o„g„irlik qiladi. Shu kabi, ko„p o„zgaruvchili chiziqli dasturlash masalalarini yechish uchun maxsus usullar ishlab chiqish lozimki, ko„pyoqning uchlarini tanlash tartibsiz emas, balki maqsadli ravishda amalga oshirilsin. Masalan, ko„pyoqning qirralari bo„ylab shunday harakat qilish lozimki, har bir qadamda maqsad funksiyasi F ning qiymati maksimum (minimum) qiymatga tomon tartibli ravishda intilsin. Chiziqli dasturlashning shu ko„rinishdagi masalalarini yechish uchun maxsus analitik usul – simpleks usuli yaratilgan. Simpleks usuli birinchi bo„lib amerikalik olim D. Dansig tomonidan 1949 yilda taklif etilgan bo„lib, keyinchalik 1956 yilda Dansig, Ford, Fulkeron va boshqalar tomonidan to„la rivojlantirildi. Lekin 1939 yilda rus matematigi L. V. Kantorovich va uning shogirtlari asos solgan “Yechuvchi ko„paytuvchilar usuli” simpleks usulidan ko„p farq qilmaydi. “Simpleks” so„zi n o„lchovli fazodagi n+1 ta uchga ega bo„lgan oddiy ko„pyoqni ifodalaydi. Yo„naltiruvchi satrni topish uchun 4.3-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. Bizning msolimizda


Download 232.03 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




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