1. Chiziqli tenglamalar tizimini yechish Chiziqli dasturlash masalasini yechishning grafik usuli


O‘zaro ikki yoqlama simpleks usul



Yüklə 392,23 Kb.
səhifə7/8
tarix17.10.2023
ölçüsü392,23 Kb.
#156408
1   2   3   4   5   6   7   8
Chiziqli dasturlash masalalarini qo`yilishi

O‘zaro ikki yoqlama simpleks usul
Dastlabki masalaning yechimidan, unga nisbatan ikki yoqlama masalaning yoki yoqlama masalaning yechimidan dastlabki masalaning yechimini keltirib chiqarishga imkon beradigan simpleks usul o‘zaro ikki yoqlama simpleks usul deyiladi. O‘zaro ikki yoqlama simpleks usulning asosiy mazmuni quyidagidan iborat:
Quyidagi masala


va unga nisbatan ikki yoqlama


masala berilgan bo‘lsin. Bu dastlabki va unga nisbatan ikki yoqlama bo‘lgan masalaga simpleks usulni qo‘llash uchun cheklanish shartlari bazis noma'lumlarga nisbatan yechilgan, ya'ni




Ko‘rinishda bo‘lishi kerak. Bu yerda tenglamalar tizimi masaladagi ularga mos tengsizliklar tizimidan qo‘shimcha
xn+i≥0, i=1,2,…,m; ym+j≥0, j=1,2,…,n
noma’lumlarni kiritish natijasida kelib chiqadi. Bu yerda xn+I, xn+2,..,xn+m noma’lumlar berilgan masala uchun bazis, xI, x2,.., xn lar ozod noma'lumlardir.
ym+I,ym+2,..,ym+n noma'lumlar esa ikki yoqlama masala uchun bazis, yI, y2,.., ym lar esa ozod noma'lumlardir.
O‘zaro ikki yoqlama masalaning asosiy teoremasiga asosan minZ=maxF bo‘lgani uchun yuqoridagi masalalarning birortasining optimal yechimini topsak, ikkinchisining ham optimal yechimini topgan bo‘lamiz.
Buning uchun, berilgan masaladagi bazis noma'lumlar bilan ikki yoqlama masaladagi ozod noma'lumlar va berilgan masaladagi ozod noma'lumlar bilan ikki yoqlama masaladagi bazis noma'lumlar o‘rtasida o‘zaro bir qiymatli moslik o‘rnatish kifoyadir, ya'ni:
xn+I↔y1; xn+2↔y2; . . .; xn+m↔ym; xI↔ym+1; x2↔ym+2; . . .; xn↔ym+n.
Agar berilgan masalaning optimal yechimi {0,0,…,xn+1,xn+2,…,xn+m} bo‘lsa, unga ikki yoqlama bo‘lgan masalaning optimal yechimi {y1,y2,…,ym,0,0,…,0} bo‘lib, y1 xn+1 oldidagi koeffitsientga, ya'ni y1=cn+1 ga; y2 esa xn+2 oldidagi koeffitsientga, ya'ni y2=cn+2 ga; ym esa xn+m oldidagi koeffitsientga, ya'ni ym =cn+m ga tengdir.
Ikki yoqlama masalani yechish uchun ikki yoqlama simpleks usul algoritmi quyidagicha:
1.Z qatordan musbat son qidiriladi va bu son turgan ustun hal qiliuvchi qilib olinadi.
2.Bu ustundan musbat son izlanadi va u turgan satr hal qiluvchi qilib olinadi (agar ustunda musbat son bo‘lmasa, masala yechmga ega bo‘lmaydi).
3.Z qator elementlarining shu hal qiluvchi qator elementlariga nisbatini qaraymiz va ularning musbatlarining eng kichigini olamiz. Unga mos element hal qiliuvchi bo‘ladi. Simpleks almashtirish bajariladi. Agar Z qator barcha koeffitsientlari manfiy bo‘lsa, shu bilan birinchi bosqich tugaydi, aks holda yana bu jarayon takrorlanadi.
4.Ikkinchi bosqichda ozod hadlar manfiylarining eng kichigi tanlanadi. Bu satr hal qiluvchi satr bo‘ladi.
5.Hal qiluvchi ustun va element 3 punktdagidek aniqlanadi. Simpleks almashtirish bajariladi. Agar barcha ozod had koeffitsientlari musbat bo‘lsa, shu bilan ikkinchi bosqich ham tugaydi, aks holda yana bu jarayon takrorlanadi.
Oxirgi olingan plan optimal deb qabul qilinadi.
Bu algoritmning bajarilishini quyidagi misolda ko‘rib chiqamiz.

Misol.


x1 +x3=4

Yüklə 392,23 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin