Министерстве по развитию информационных технологий и коммуникаций республики узбекистан

МИНИСТЕРСТВЕ ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН
ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ АЛ-ХОРАЗМИ

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI





TELEKOMMUNIKATSIYALAR FAKULTETI
ALGORITMLARNI LOYIHALASH FANIDAN

MUSTAQIL ISH

Bajardi: 043-20 guruh talabasi

Nazarov M.M.
Toshkent - 2023
Mavzu: Simpleks usul yordamida topilgan yechim iqtisodiy tahlili. Xulosa va tavsiyalar.
Reja:

1. 
   Simplеks jаdvаl usuli haqida
   
2. 
   Ichki marshrutlash protokollarining turlari
   
3. 
   Adabiyotlar
   

Simplеks jаdvаl usuli haqida
Simpleks usuli har qanday chiziqli programmalashtirish masalasining optimal echimini topishga xizmat qiluvchi eng universal usullardan biridir.
1. Dastlab berilgan chiziqli programmalashtirish masalasining chegaraviy shartlarida m ta o`zaro chiziqli bog‘liq bo`lmagan birlik vektorlar mavjud deb faraz qilinadi. Umumiylikni buzmagan holda bu vektorlar birinchi m ta vektordan iborat bo`lsin. U holda masala quyidagi ko`rinishda bo`ladi:

1. 
   sistemani vektor formada yozamiz:
   

(4)
vektorlar n o`lchovli vektor fazodagi o`zaro chiziqli bog‘liq bo`lmagan birlik vektorlardan iborat bo`lib, bu fazoning bazisini tashkil qiladi. (1) da o`zgaruvchilarni bazis o`zgaruvchilar, o`zgaruvchilarni esa bazis bo`lmagan (ozod) o`zgaruvchilar deb qabul qilib, bazis bo`lmagan o`zgaruvchilarni nolga tenglaymiz. Natijada:
(5)
boshlang‘ich yechimni hosil kilamiz. (5) yechimga quyidagi
(6)
yoyilma mos keladi. Bu yoyilmadagi vektorlar o`zaro chiziqli bog‘liq bo`lmagan vektorlar bo`lganligi sababli, topilgan boshlang‘ich (5) yechim tayanch yechim bo`ladi. Berilgan boshlang‘ich rejadan boshlab tayanch rejalar ketma-ketligini hosil qilib borib, jarayonni optimal yechim topilguncha davom ettirish mumkin va bu tayanch yechimlar simpleks jadval va simpleks usul algoritmi asosida optimallikka tekshiriladi.
2. (1) - (4) masalaning berilganlari simpleks jadvalda quyidagi ko`rinishda bo`ladi:

Bazis vekt.	Cbaz	P0	c1	c2	…	cm	cm+1	…	ck	…	cn
			P1	P2	…	Pm	Pm+1	…	Pk	…	Pn
P1	c1	b1	1	0	…	0	a1m+1	…	a1k	…	a1n
P2	c2	b2	0	1	…	0	a2m+1	…	a2k	…	a2n
…	…	…	…	…	…	…	…	…	…	…	…
Pl	cl	bl	0	0	…	0	alm+1	…	alk	…	aln
…	…	…	…	…	…	…	…	…	…	…	…
Pm	cm	bm	0	0	…	1	amm+1	…	amk	…	amn
j=Zj-cj	…	m Y0=cibi+c0 ^i=0	1=0	2=0	…	m=0	m m+1 =aim+1ci-cm+1 ^i=0	…	m k =aikci-ck ^i=0	…	m n =ainci-cn ^i=0

Simpleks jadval ustida tartib bilan quyidagi ishlarni bajarish kerak:
1. Har bir j uchun y_j-c_j=D_j lar tekshiriladi. Agar barcha j lar uchun D_jЈ0 bo`lsa, topilgan yechim optimal yechim bo`ladi.
2. Agar birorta j uchun y_j-c_j>0 bo`lsa, bazisga kiritiladigan vektor tanlanadi. Bazisga shartni qanoatlantiruvchi R_k vektor kiritiladi.
3. Bazisdan chiqarilishi kerak bo`lgan vektor aniqlanadi. Bazisdan
ga mos keluvchi P<sub>l</sub> vektor chiqariladi.Agar R<sub>k</sub> vektorga mos keluvchi barcha x<sub>ikЈ</sub>0 bo`lsa, chiziqli funksiya quyidan chegaralanmagan bo`ladi;
4. Aniqlovchi element x_ik>0 tanlangandan so`ng simpleks jadval almashtiriladi.
Shunday yul bilan har bir iteratsiyada yangi tayanch yechim topiladi. Simpleks usul yoki optimal yechimni beradi, yoki masaladagi chiziqli funksiyaning chekli minimum ga ega emasligini aniqlaydi.

2-ma’ruza mashg‘uloti
Reja:
1. Rejaning optimallik sharti.
2. Masalaning yechimga ega emaslik sharti.
3. Yechimni izlashni davom ettirish sharti
4. Simpleks jadvalni to`ldirishda to`g‘ri to`rtburchak usuli.

1. Qaralayotgan masalada dastlabki bazis rejani kabi olaylik. U holda bo`ladi. Simpleks jadval nomini olgan jadvalni tuzaylik.

Birinchi ustunga bazis tashkil etuvchi vektorlarni, ikkinchi ustunga narx vektori C ning mos komponentlarini, uchinchi ustunga esa B vektorning qaralayotgan bazisdagi koordinatalarini, ya’ni larni joylashtiramiz. Chunki x-reja bo`lgani sababli yoyilma o`rinlidir. Birinchi satrga C vektorning barcha koordinatalarini joylashtirgach, to`rtinchi ustundan boshlab, barcha ustunlarni shart vektorlarining qaralayotgan bazisdagi koordinatalari bilan to`ldirib chiqamiz. Bunda, dastlabki m ta ustun oson to`ldiriladi, chunki ular birlik vektorlardan iborat bo`ladi. Qolgan m+1 dan n gacha bo`lgan ustunlarni vektorlarning
(1)

yoyilmasi koordinatalari lar bilan to`ldirib chiqamiz. Ta’kidlash lozimki, agar belgilash kiritsak, uni (1) dan topish mumkin:

. (2)
Shunday qilib, jadvalning barcha kataklari berilgan masalaga oid kattaliklar bilan to`ldiriladi. Biroq, asosiy maqsad optimallik kriteriyini tekshirishdan iborat bo`lgani sababli, jadvalga yordamchi Z va Z-C orqali belgilangan ikkita satr kiritamiz. Z belgili satrning kataklariga mos ravishda
(3)
miqdorlarni joylashtiramiz. Agar (2) ni inobatga olib, (3) ni boshqacha ifodalasak,
(4)
ga ega bo`lamiz. Nihoyat, so`nggi satrga Z satr elementlaridan, birinchi satr elementlarini mos ravishda ayirib yozamiz:
. (5)
Dastlabki (to`rtinchisidan boshlab) m ta ustun uchun


(6)
bo`lib, qolgan ustunlar uchun esa
(7)
bo`ladi. Bu esa optimallik kriteriyidagi vektorning koordinatalaridir. Ya’ni so`nggi satrdagi barcha elementlarning manfiy bo`lmasligi qaralayotgan bazis rejaning optimalligini anglatadi
2. Yechimning chegaralanmaganlik shartini ham, tekshirish mumkin. Dastlab yechimning chegaralanmaganlik shartini keltiraylik.
Deylik x bazis reja uchun yuqoridagidek qilib to`ldirilgan jadvalning so`nggi satrida manfiy mavjud bo`lib, unga mos ustundagi vektorning barcha koordinatalari musbat bo`lmasin, ya’ni bo`lsin. Bu holda maqsad funksiya rejalar to`plamida chegaralanmagan tarzda o`sadi.
Haqiqatan, (7) ga asosan.



yoki

bo`lib, bo`lganda ixtiyoriy uchun vektor reja bo`lib qoladi va

bo`lganligidan, da

3. Deylik, x bazis reja uchun to`ldirilgan dastlabki jadvalning so`nggi satridagi lar orasida manfiylari bor bo`lib, ularga mos ustunlarda joylashgan -vektorlarning musbat koordinatasi mavjud bo`lsin. U holda maqsad funksiya qiymatini oshirish imkoniyati paydo bo`ladi. Bu holda simpleks iteratsiyada, larning manfiylari ichidan eng kichigi tanlanar edi.
Jadvalda esa so`nggi satrdagi larning manfiylari orasidan eng kichigini tanlaymiz va mos ustunni hal qiluvchi ustun deb belgilaymiz, u -indeksli ustun bo`lsin. So`ngra ustundagi musbat larni tanlab, ular ichidan nisbatga eng kichik qiymat beruvchi indeksni aniqlaymiz va unga mos satrni hal qiluvchi satr deb ataymiz. Hal qiluvchi satr va ustun kesishmasida joylashgan elementga esa hal qiluvchi element deb ataladi. Bu elementni topish, bazis vektorlar ichidagi vektor o`rnini vektor egallashi lozimligini anglatadi va natijada yangi

bazisga ega bo`lamiz.
4. x bazis reja uchun to`ldirilgan dastlabki jadvalning so`nggi satridagi lar orasida manfiylari bor bo`lib, ularga mos ustunlarda joylashgan -vektorlarning musbat koordinatasi mavjud bo`lsin. U holda maqsad funksiya qiymatini oshirish imkoniyati paydo bo`ladi. Bu holda simpleks iteratsiyada, larning manfiylari ichidan eng kichigi tanlanar edi.
Jadvalda esa so`nggi satrdagi larning manfiylari orasidan eng kichigini tanlaymiz va mos ustunni hal qiluvchi ustun deb belgilaymiz, u -indeksli ustun bo`lsin. So`ngra ustundagi musbat larni tanlab, ular ichidan nisbatga eng kichik qiymat beruvchi indeksni aniqlaymiz va unga mos satrni hal qiluvchi satr deb ataymiz. hal qiluvchi satr va ustun kesishmasida joylashgan elementga esa hal qiluvchi element deb ataladi. Bu elementni topish, bazis vektorlar ichidagi vektor o`rnini vektor egallashi lozimligini anglatadi va natijada yangi

bazisga ega bo`lamiz. Barcha shart vektorlarining yangi bazisdagi koordinatalarini esa «to`g‘ri to`rtburchak qoidasi» deb ataluvchi usul yordamida topiladi. Haqiqatan, deylik, yangi jadvaldagi ni aniqlash talab etilayotgan bo`lsin. U holda dastlabki jadvalda, diagonalining bir uchi , bir uchi bo`lgan to`g‘ri to`rtburchak yasaymiz (1-chizma). To`rtburchakning faqat burchaklarida joylashgan elementlar ustida quyidagi amallarni ketma-ket bajaramiz:

1. 
   hal qiluvchi element bilan bir diagonalda yotmagan va larni o`zaro ko`paytiramiz;
   
2. 
   natijani hal qiluvchi elementga bo`lib, hosil bo`lgan sonni dan ayramiz.
   

. :
-
-

1-chizma
Yangi jadvalning dastlabki jadvaldagi satr va ustunga mos koordinatalari ham oson topiladi. Satr barcha elementlarni ga bo`lish orqali hosil qilinsa, -ustun birlik vektordan iborat bo`lib qoladi.
So`ngra Z va Z-C satrlar xuddi dastlabki jadvaldagidek, amallarni yangi jadval uchun amalga oshirish orqali to`ldiriladi va optimallik sharti tekshiriladi. Shunday qilib, jadvalda, simpleks usulning bitta iteratsiyasi amalga oshiriladi.





Iqtisodiy masalalarni simpleks usulida tahlil qilish
Yuqori texnologiyali mahsulotlar ishlab chiqaradigan zamonaviy korxonalarda, asosan, mahsulotlarni yig'ish va yig'ish uchun avtomatlashtirilgan liniyalardan foydalaniladi. Ushbu liniyalarning har biri bir nechta turli turdagi mahsulotlarni ishlab chiqarish uchun ishlatilishi mumkin. Ko'pgina hollarda, ba'zi bir avtomatlashtirilgan liniyada har bir turdagi ishlab chiqarish birligini to'liq vaqtli ishlab chiqarish juda aniq ma'lum. Chiziqlarning har birida ma'lum bir rejalashtirish davri uchun cheklangan ish vaqti fondi mavjud. Korxona esa o‘z navbatida har bir mahsulot turini bir xil muddatga chiqarishni rejalashtirgan. Buning uchun kompaniya matematik dasturlashning turli usullaridan foydalanadi, ulardan biri simpleks usulidir.

Ayni paytda mintaqalar yoki hatto mamlakat iqtisodiyoti faoliyatini prognoz qilish, menimcha, biz hozir jiddiy e'tibor qaratishimiz kerak, chunki bugungi kundagi o'z muammolari pardasi ortida negadir hamma mamlakatning iqtisodiyoti, o'z-o'zini boshqarish, o'zini o'zi boshqarishi mumkin bo'lgan iqtisodiy rivojlanish darajasini esdan chiqardi. iqtisodiyotni ham boshqarish kerak, shuning uchun uning rivojlanish ko'rsatkichlarini prognoz qilishni mustahkam ilmiy asosga qo'yish kerak.

Simpleks usuli chiziqli dasturlash masalasini yechish usuli bo'lib, bunda harakat optimal yechim topilgunga qadar asosiy rejalar bo'yicha yo'naltiriladi; Simpleks usuli bosqichma-bosqich rejani takomillashtirish usuli deb ham ataladi. Chiziqli dasturlash bo'yicha birinchi ish L.V. 1939 yilda Kantorovich, lekin faqat 1947 yilda J. Danzig tomonidan simpleks usuli (simpleks - lotincha Simplex - oddiy) kashf etilgandan so'ng, chiziqli dasturlash masalasini hal qilish ushbu sinf muammolariga qiziqish uyg'otdi.



Usulning g'oyasi quyidagicha:

• 
  eritma ko'pburchakning istalgan uchini toping;
  
• 
  funktsiya kamayadigan (ortadigan) qirralarning bo'ylab eritma ko'pburchakning boshqa cho'qqisiga o'ting;
  
• 
  funktsiyaning minimal (maksimal) cho'qqisiga tushganda topiladi, undan funktsiya barcha yo'nalishlarda oshadi (kamayadi).
  

Shunday qilib, biz xulosa qilishimiz mumkinki, ushbu ishda simpleks modelini qurishning ko'rsatilgan jarayoni bir nechta turdagi mahsulotlarni ishlab chiqarishi mumkin bo'lgan ishlab chiqarish liniyalari mavjud bo'lganda ishlab chiqarish jarayonini rejalashtirishda tahlil qilish va kerak bo'lganda tuzatish kiritish imkonini beradi. Bundan tashqari, taklif qilingan rejani bajarishning iloji yo'qligini aniqlash, shuningdek, ikki xil usuldan foydalangan holda ishlab chiqarish jarayonini o'zgartirish bo'yicha tavsiyalar olish nisbatan oson: liniyalarning ish vaqtini oshirish, ishlab chiqarish rejasi hajmini kamaytirish.