|
Chiziqli dasturlash masalalarida samaradorlik mezoni va cheklovlar tizimidagi funktsiyalar chiziqli bo'ladi
|
| bet | 4/8 | | Sana | 18.05.2024 | | Hajmi | 87,93 Kb. | | #241394 |
Bog'liq Chiziqli dasturlash modelining umumiy kox 3 \u003d x 3 + - x 3 - , qayerda x 3 + , x 3 - ≥ 0 .
1-misol. Chiziqli dasturlash muammosining kanonik shakliga qisqartirish:
min L \u003d 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x1 ≤ 0; x2 ≥ 0; x3 ≥ 0.
Cheklash tizimining har bir tenglamasiga tenglashtiruvchi o'zgaruvchilar kiritaylik x 4 , x 5 , x 6. Tizim tenglik ko'rinishida yoziladi va cheklovlar tizimining birinchi va uchinchi tenglamalarida o'zgaruvchilar x 4 , x 6 chap tomonda "+" belgisi bilan, ikkinchi tenglamada esa o'zgaruvchi kiritiladi x5“-” belgisi bilan kiritiladi.
2x 2 - x 3 + x 4 \u003d 5;
x 1 + x 2 - x 3 - x 5 \u003d -1;
2x 1 - x 2 + x 6 \u003d -3;
x4 ≥ 0; x5 ≥ 0; x6 ≥ 0.
Kanonik shakldagi erkin atamalar ijobiy bo'lishi kerak, buning uchun oxirgi ikkita tenglamani -1 ga ko'paytiramiz:
2x 2 - x 3 + x 4 \u003d 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x1 + x2 - x6 = 3.
Chiziqli dasturlash masalalarini yozishning kanonik shaklida cheklovlar tizimiga kiritilgan barcha o'zgaruvchilar manfiy bo'lishi kerak. Faraz qilaylik x 1 \u003d x 1 '- x 7 , qayerda x 1 ‘ ≥ 0, x 7 ≥ 0 .
Ushbu ifodani cheklovlar tizimiga va maqsad funktsiyasiga almashtirib, o'zgaruvchilarni indeksning o'sish tartibida yozsak, biz kanonik shaklda berilgan chiziqli dasturlash masalasini olamiz:
L min \u003d 2x 1 ' + x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 \u003d 5;
-x 1 ‘- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ‘ + x 2 - x 6 + 2x 7 = 3;
x 1 ‘ ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.
Kanonik LP muammosining asosiy dizayni uchun optimallik sharti. Simpleks usuli va uning konvergentsiyasi.
Simpleks usuli universal, chunki u yozilgan deyarli har qanday chiziqli dasturlash muammosini hal qilishga imkon beradi kanonik shakl.
Simpleks usuli g'oyasi rejani izchil takomillashtirish, ya'ni, ba'zi bir dastlabki mos yozuvlar yechimidan boshlab, ketma-ket yo'naltirilgan harakat muammoning optimal echimiga havola qilish orqali.
Maqsad funktsiyasining qiymati vazifalar uchun maksimal siljish bilan kamaymaydi.
Etakchi yechimlar soni chekli bo'lgani uchun, chekli qadamlardan so'ng optimal etalon yechimga erishamiz.
Asosiy manfiy bo'lmagan yechim qo'llab-quvvatlovchi yechim deb ataladi.
Simpleks usuli algoritmi
1. Masalaning matematik modeli bo'lishi kerak kanonik. Agar u kanonik bo'lmasa, uni kanonik shaklga keltirish kerak.
2. Biz dastlabki mos yozuvlar yechimini topamiz va uning optimalligini tekshiramiz.
Buning uchun 1-simpleks jadvalini to'ldiring.
1-bosqich jadvalining barcha qatorlari cheklovlar tizimi va maqsad funktsiyasi ma'lumotlariga muvofiq to'ldiriladi.
Muammolarni hal qilishda quyidagi holatlar mumkin maksimal:
1. Simpleks jadvalining oxirgi qatorining barcha koeffitsientlari bo'lsa Dj³ 0, keyin topildi
yechim optimal.
2 Agar kamida bitta koeffitsient bo'lsa DJ £ 0, lekin mos keladigan o'zgaruvchi bilan bitta ijobiy hisoblangan munosabat yo'q, keyin yechim vazifalarni to'xtatamiz, chunki F(X) ® ¥ , ya'ni maqsad funktsiyasi ruxsat etilgan echimlar sohasida cheklanmagan.
Agar oxirgi qatorning kamida bitta koeffitsienti salbiy bo'lsa va tegishli o'zgaruvchiga ega bo'lsa kamida bitta ijobiy baholash munosabati, keyin siz borishingiz kerak boshqa asosiy chiziqqa.
E agar oxirgi satrda bir nechta salbiy koeffitsientlar mavjud asosiy o'zgaruvchi ustuniga(BP) buni tanishtiring o'zgaruvchan ga mos keladi mutlaq qiymatdagi eng katta salbiy koeffitsient.
5. Agar kamida bitta koeffitsient Dk bo'lsa< 0 ,keyin k - th ustunni qabul qilish rahbar uchun.
6. uchun yetakchi chiziq mos keladiganini qabul qiling eng kam bepul a'zolar nisbati bi ijobiy koeffitsientlarga rahbar, k - bu ustun.
7. Etakchi qatorlar va ustunlar kesishmasidagi element deyiladi yetakchi element.
Simpleks jadvalini to'ldirish 2 :
· asosiy ustunni nol va bitta bilan to'ldiring
· yetakchi qatorni yetakchi elementga bo‘lish orqali qayta yozing
agar bosh qatorda nol bo'lsa, unda tegishli ustunlar keyingi simpleks jadvaliga o'tkazilishi mumkin
· qolgan koeffitsientlar "to'rtburchak" qoidasiga muvofiq topiladi
Biz tekshiradigan yangi mos yozuvlar yechimini olamiz optimallik uchun:
Agar oxirgi qatorning barcha koeffitsientlari bo'lsa Dj³ 0, keyin topilgan yechim maksimal.
Agar yo'q bo'lsa, biz 8-bosqichning simpleks jadvalini to'ldiramiz va hokazo.
Agar maqsad funksiyasi F(X) topishni talab qiladi minimal qiymat, keyin mezon muammoning optimalligi hisoblanadi koeffitsientlarning ijobiy emasligi D j hamma uchun j = 1,2,…n.
Simpleks usulining konvergentsiyasi. LP muammolarida degeneratsiya. Har qanday hisoblash algoritmining eng muhim xususiyati yaqinlashuv, ya'ni uni qo'llash jarayonida chekli qadamlar (iteratsiyalar)da kerakli natijalarni (ma'lum aniqlik bilan) olish imkoniyatidir.
Simpleks usulining konvergentsiyasi bilan bog'liq muammolar nisbatning bir xil minimal qiymatlari bo'lsa, r qiymatini (2" bo'lim) tanlash bosqichida yuzaga kelishi mumkinligini ko'rish oson.
bir vaqtning o'zida T (q) jadvalining bir necha qatoriga erishiladi. Keyin keyingi iteratsiyada b(b(q+1)) ustuni nol elementlarni o'z ichiga oladi.
⇐ Oldingi12345Keyingi ⇒
Nashr qilingan sana: 2015-11-01; O'qilgan: 4190 | Sahifa mualliflik huquqining buzilishi
Studopedia.org - Studopedia.Org - 2014-2018. (0,002 s) ...
Optimal yechim - muammo - chiziqli dasturlash
Chiziqli dasturlash masalasining optimal yechimiga hech bo'lmaganda k n - m o'zgaruvchilar nolga teng bo'lgan mos yozuvlar nuqtalaridan birida erishiladi.
Chiziqli dasturlash muammosining optimal yechimidan foydalanib, DS dagi ruxsat etilgan o'zgarishlarni topish mumkin, buning uchun L hali ham doimiy bo'lib qoladi.
Agar chiziqli dasturlash masalasining optimal yechimi mavjud bo'lsa, u holda asosiy optimal yechim mavjud.
Chiziqli dasturlash masalasining optimal yechimi n o‘lchamli fazoda ko‘pburchak bo‘lgan va chiziqli cheklovlar tizimi bilan aniqlangan boshqariladigan o‘zgaruvchilarning ruxsat etilgan qiymatlari mintaqasi chegarasida joylashganligi isbotlangan.
m cheklovli chiziqli dasturlash masalasining optimal yechimi z bo‘lgani uchun, bu yechim ko‘pi bilan m qat’iy musbat o‘zgaruvchilarni o‘z ichiga oladi.
Chiziqli dasturlash muammosining optimal yechimi chiziqli cheklovlar tizimi bilan aniqlangan / r o'lchovli fazodagi ko'pburchak bo'lgan boshqariladigan o'zgaruvchilarning ruxsat etilgan qiymatlari mintaqasi chegarasida joylashganligi isbotlangan. Har bir cho'qqining koordinatalari tenglamalar tizimini (cheklovlar) echish yo'li bilan aniqlanadi va n ta boshqariladigan o'zgaruvchilar va m cheklashlar mavjud bo'lganda, St p m tenglamalar tizimini echishi kerak. Spn n (m - n) kombinatsiyasi ortib borayotgan tur bilan juda tez o'sib boradi, shuning uchun yechim izlash juda ko'p sonli hisob-kitoblarni talab qiladi, hatto kompyuterga ham kirish mumkin emas.
Demak, D 1 holatida chiziqli dasturlash masalasining optimal yechimi avtomatik butun son bo‘lib chiqadi.
1-qismda ko'rsatilganidek, chiziqli dasturlash masalasining optimal yechimi mutlaqo butun son bo'lishi shart emas va shu bilan birga, tabiati yechim butun son bo'lishini talab qiladigan ko'plab muammolar mavjud. Ushbu muammolarning ba'zilari, birinchi qarashda, butun sonli dasturlash muammolari emas, lekin ularni shunday shakllantirish mumkin.
Shubhasiz, har bir asosiy yechim chiziqli dasturlash muammosining optimal yechimi emas. Biroq, degenerativ bo'lmagan masalaning optimal yechimi har doim tenglamalar tizimi (VIII, 42) uchun asos bo'lishi kerak va shuning uchun topish muammosi. optimal yechim tenglamalar sistemasining (VIII, 42) faqat asosiy yechimlarini sanashdan iborat bo‘lib, ular orasidan optimal yechim topiladi.
Shubhasiz, har bir asosiy yechim chiziqli dasturlash muammosining optimal yechimi emas. Biroq, degenerativ bo'lmagan masalaning optimal yechimi doimo tenglamalar tizimi (VIII42) uchun asos bo'lishi kerak va shuning uchun optimal echimni topish masalasi tenglamalar tizimining faqat asosiy echimlarini sanab o'tishdan iborat (VIII42). , ular orasida eng maqbuli topiladi.
3-bosqichda bir nechta iteratsiyalarni amalga oshirgandan so'ng, chiziqli dasturlash muammosining ko'plab alternativ optimal echimlari paydo bo'lishi mumkin.
Chiziqli dasturlash muammosi
Bunday velosiped ba'zan doimiy degeneratsiya deb ataladi. Afsuski, bu hodisa ko'pincha yuqori o'lchamli o'rta PI muammolarida sodir bo'ladi. Shuningdek, konvergentsiyaga erishish uchun minglab iteratsiyalarni talab qiladigan kichik o'lchamli masalalarga (10 dan ortiq o'zgaruvchi va tenglamalar) ko'plab misollar mavjud.
Bunday hollarda chiziqli dasturlash masalasining optimal yechimini aniqlashning iterativ (bosqichma-bosqich) protsedurasi bo'lgan simpleks usuli qo'llaniladi. Simpleks usuli bo'yicha hisob-kitoblar mumkin bo'lgan yechimni aniqlashdan boshlanadi, so'ngra boshqa mumkin bo'lgan echimlar topiladi va ularni takomillashtirish imkoniyatlari tekshiriladi. Bir yechimdan ikkinchisiga o'tish yangi yaxshilanishlar mumkin bo'lmaguncha davom etadi. Keng tarqalgan standart kompyuter dasturlari, ular chiziqli dasturlash masalalari sifatida ifodalanishi mumkin bo'lgan bunday boshqaruv muammolarini hal qilish uchun simpleks usulidan foydalanadilar.
Agar chiziqli cheklovlar tizimi maxsus tuzilishga ega bo'lsa, masalan, tarmoq modelini tashkil etsa, u holda 2-bosqichda chiziqli dasturlash masalasining optimal echimini topishda ushbu holatdan foydalanish mumkin.
Proportsional taqsimlash g'oyasi II Dikin tomonidan taklif qilingan ikki bosqichli hisoblash algoritmi shaklida amalga oshirildi, bunda ichki nuqtalar usulining xususiyati asosan optimal echimlar to'plamining nisbatan ichki nuqtasini ishlab chiqish uchun ishlatiladi. chiziqli dasturlash muammosi. Bu xususiyat (2.3.2) - (2.3.4) tengsizlik shartlariga muvofiq chegara qiymatlariga faqat boshqa har qanday optimal yechim uchun ushbu chegara qiymatlariga ega bo'lgan o'zgaruvchilar uchun erishilishini anglatadi.
Sahifalar: 1 2
Chiziqli dasturlash masalasini yechishning grafik usuli
Ikki o'zgaruvchining holati uchun ZLP ni standart shaklda ko'rib chiqing:
(10)
(10) tengsizliklar sistemasi mos kelsin (kamida bitta yechimga ega). Ushbu tizimning har qanday tengsizligi chegara chizig'i bilan yarim tekislikni geometrik tarzda belgilaydi Salbiy bo'lmagan shartlar mos keladigan chegara chiziqlari bilan yarim tekisliklarni belgilaydi Va.
Tizim izchil bo'lgani uchun, yarim tekisliklar, xuddi qavariq to'plamlar kabi, kesishib, umumiy qismni tashkil qiladi, bu qavariq to'plam bo'lib, har birining koordinatalari ushbu tizimning yechimi bo'lgan nuqtalar yig'indisidir. Bu barcha nuqtalarning yig'indisi deyiladi eritma ko'pburchagi. Bu nuqta, segment, nur, to'g'ri chiziq, yopiq ko'pburchak, cheksiz ko'pburchak maydoni bo'lishi mumkin.
LLP ning yechimi geometrik jihatdan yechim ko'pburchagining bunday nuqtasini qidirish bo'lib, uning koordinatalari maqsad funktsiyasiga eng katta (eng kichik) qiymat beradi. Bundan tashqari, ko'pburchakning barcha nuqtalari ruxsat etilgan echimlardir.
Deb nomlangan narsani ko'rib chiqing darajali chiziq maqsad funktsiyasi z, ya'ni bu funktsiya bir xil sobit qiymatni oladigan chiziq : yoki
|
| |
