Yakun va tavsiyalar. Tayanch iboralar



Download 118,22 Kb.
Sana25.04.2022
Hajmi118,22 Kb.
#581218
Bog'liq
2 5397880426205287427


MAVZU-6: SIMPLEKS USUL YORDAMIDA TOPILGAN YECHIMG IQTISODIY TAHLILI. YAKUN VA TAVSIYALAR.


Tayanch iboralar: Simpleks usul, simpleks jadval, vektor, boshlang‘ich reja, rejaning optimallik sharti, yechimga ega emaslik sharti, bazis reja.


1-ma’ruza mashg‘uloti
Reja:
1. Simpleks usulning asosiy g‘oyasi.
2. Simpleks jadval.
3. Simpleks usulning analitik berilishi.
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 yj-cj=Dj lar tekshiriladi. Agar barcha j lar uchun DjЈ0 bo‘lsa, topilgan yechim optimal yechim bo‘ladi.
2.Agar birorta j uchun yj-cj>0 bo‘lsa, bazisga kiritiladigan vektor tanlanadi. Bazisga shartni qanoatlantiruvchi Rk vektor kiritiladi.
3.Bazisdan chiqarilishi kerak bo‘lgan vektor aniqlanadi. Bazisdan
ga mos keluvchi Pl vektor chiqariladi.Agar Rk vektorga mos keluvchi barcha xikЈ0 bo‘lsa, chiziqli funksiya quyidan chegaralanmagan bo‘ladi;
4.Aniqlovchi element xik>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.


Nazorat uchun savollar:
1. Maqsad funksiya maksimumini topishdan minimumini topishga qanday o‘tiladi?.
2.Chegaraviy shartlari tengsizliklar sistemasidan iborat bo‘lgan masaladan chegaraviy shartlari tenglamalar sistemasidan iborat masalaga o‘tish qanday amalga oshiriladi?
3.Chiziqli programmalashtirish masalasi qanday yechimlarga ega bo‘lishi mumkin?
4.Qanday masalalar uchun simpleks jadval tuzish mumkin?
5.Simpleks usul algoritmi qanday?
6.Masalaning yechimi mavjud emaslik sharti qanday?
7.Bazis yechimni ortimallik sharti qanday?

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.


Nazorat uchun savollar:
1. Maqsad funksiya maksimumini topishdan minimumini topishga qanday o‘tiladi?.
2.Bazis rejaning optimallik sharti qanday?
3.Chiziqli programmalashtirish masalasi qanday yechimlarga ega bo‘lishi mumkin?
4.Qanday masalalar uchun simpleks jadval tuzish mumkin?
5.Masalaning yechimga ega emaslik sharti qanday?
6.Echimni izlashni davom ettirish sharti qanday?
7. Maqsad funksiya maksimumini topishdan minimumini topishga qanday o‘tiladi?.
8.Chegaraviy shartlari tengsizliklar sistemasidan iborat bo‘lgan masaladan chegaraviy shartlari tenglamalar sistemasidan iborat masalaga o‘tish qanday amalga oshiriladi?
Download 118,22 Kb.

Do'stlaringiz bilan baham:




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

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish