Mavzu: Iqtisodiy masalalarni yechishda simpleks usuli

Muhammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti
513-21- guruh talabasi Mardonov Serobboyning “Algoritm va loyihalash”
fanidan 1-Mustaqil ishi

Talaba:Mardonov Serobboy

O’qituvchi: Hamdamov Muzaffar


Mavzu: Iqtisodiy masalalarni yechishda simpleks usuli
Tayanch iboralar: (Simpleks usul, simpleks jadval, vektor, boshlang‘ich reja, rejaning optimallik sharti, yechimga ega emaslik sharti, bazis reja.)


Reja:
1. Simpleks usulning asosiy g‘oyasi.
2. Simpleks jadval.
3. Simpleks usulning analitik berilishi.
4. Rejaning optimallik sharti.
5. Masalaning yechimga ega emaslik sharti.
6. Yechimni izlashni davom ettirish sharti
7. Simpleks jadvalni to‘ldirishda to‘g‘ri to‘rtburchak usuli.
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_l vektor chiqariladi.Agar R_k vektorga mos keluvchi barcha x_ikЈ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.

5. 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
6. 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

7. 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.
8. 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.