Zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universtiteti
Download 232.03 Kb.
|
J
- Bu sahifa navigatsiya:
- Teorema. Agar
- 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: 
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||