Agar siz muhandislik talabasi yoki muhandis bo'lsangiz, eng yaxshi natijaga erishish uchun tizimni optimallashtirish nimani anglatishini bilasiz.
Yechimni optimallashtirish ko'priklarni qurishdan tortib, dasturiy ta'minot ishlab chiqarishgacha bo'lgan hamma narsada muvaffaqiyat kalitidir.
Asosiy mumkin bo'lgan yechim g'oyasi shu nuqtada paydo bo'ladi.
Bu chiziqli dasturlashning asosiy g'oyasi bo'lib, sizga mumkin bo'lgan echimlar to'plamidan qaysi biri eng yaxshi ekanligini aniqlash imkonini beradi.
Lekin nima uchun bu juda muhim? Ushbu maqolada men asosiy mumkin bo'lgan echimlar va ulardan haqiqiy dunyoda muhandislik muammolarini hal qilish uchun qanday foydalanish mumkinligi haqida gapiraman.
Men ularni qanday topish mumkinligi, nimadan yasalganligi va nima uchun muhimligi haqida gapirib beraman.
Shunday qilib, siz tajribali muhandismisiz yoki endigina boshlayotgan talaba bo'lasizmi, biz bilan keling, men asosiy mumkin bo'lgan yechimlar olamiga sho'ng'ib, chiziqli dasturlash kuchidan qanday foydalanishni ko'rsataman.
Asosiy mumkin bo'lgan yechimni tushunish
Rasmiy ta'rif:
Barcha o'zgaruvchilar manfiy bo'lmagan chiziqli dastur modelining asosiy yechimi.
Asosiy amalga oshirilishi mumkin bo'lgan yechim (BFS) eng yaxshi echimlarni topishga yordam beradigan chiziqli dasturlashning asosiy g'oyasidir.
BFS - nolga teng bo'lmagan o'zgaruvchilarning mumkin bo'lgan eng kichik soniga ega yechim.
Bu mumkin bo'lgan echimlar ko'p yuzli burchagi.
Boshqacha qilib aytganda, BFS - bu salbiy bo'lmagan cheklovlarga javob beradigan va amalga oshirilishi mumkin bo'lgan mintaqa yoki muammoli hududda bo'lgan asosiy echim.
Optimal asosiy mumkin bo'lgan yechimni topish
Eng yaxshi BFSni topish uchun biz quyidagilarni bajarishimiz kerak:
- Chiziqli ketma-ketlik uchun dasturni standart shaklda yozing.
- Tengsizliklar tizimini kengaytirilgan matritsaga aylantiring.
- Qaysi o'zgaruvchilar asosiy va qaysi biri emasligini aniqlang.
- Boshqa o'zgaruvchilar nuqtai nazaridan asosiy o'zgaruvchilar nima ekanligini aniqlang.
- Faqat asosiy bo‘lmagan o‘zgaruvchilar funksiyasini olish uchun ushbu ifodalarni maqsad funksiyasiga qo‘ying.
- Hech qanday cheklovlarni buzmasdan oshirish mumkin bo'lgan va maqsad funktsiyasini yaxshilaydigan asosiy bo'lmagan o'zgaruvchini toping.
Bu o'zgaruvchi endi asosiy o'zgaruvchidir va boshqa asosiy o'zgaruvchilardan biri endi asosiy o'zgaruvchi emas.
Agar optimal yechim mavjud bo'lsa, u echimlar mumkin bo'lgan hududning uchlari yoki cho'qqilaridan birida bo'lishi kerak.
Shunday qilib, agar LP optimal echimga ega bo'lsa, u mumkin bo'lgan to'plamning ekstremal nuqtasida optimal echimga ega.
Bundan tashqari, agar optimal yechim mavjud bo'lsa, har doim optimal BFS mavjud.
Optimal BFSni topish uchun Simpleks usulidan foydalanish
Simpleks usuli chiziqli dasturlashdagi masalalarni yechish algoritmidir.
U pivot protsedurasi yordamida bitta BFS dan "qo'shni" BFS ga o'tadi.
Pivot protsedurasida asosiy o'zgaruvchiga aylanish uchun asosiy bo'lmagan o'zgaruvchi tanlanadi, so'ngra yangi asosiy o'zgaruvchilarni hal qilish uchun joriy BFS ishlatiladi.
Maqsad funksiyasini yaxshilash uchun hech qanday asosiy bo'lmagan o'zgaruvchini o'zgartirib bo'lmasa, algoritm bajariladi.
Nima uchun asosiy mumkin bo'lgan echimlar murakkab muhandislik muammolarini hal qilish uchun juda muhimdir
Hali ham tushunish qiyinmi? Keling, nuqtai nazarni biroz o'zgartiraman:
Oddiy va amaliy javoblar kimga kerak? Faqat hamma narsani bir joyga to'plang va eng yaxshisiga umid qiling.
Axir, tartibsizlik juda qiziqarli bo'lganda optimallashtirish kimga kerak? Salbiy bo'lmagan o'zgaruvchilar dunyosiga xush kelibsiz, bu erda hamma narsa faqat taklif va muvaffaqiyatsizlik deyarli aniq.
Yoki shundaymi?
Keling, nima uchun asosiy amalga oshirilishi mumkin bo'lgan echimlarning asosiy tushunchasi asosiy narsa emasligini va nima uchun ular hatto eng murakkab muhandislik muammolarini hal qilishda kalit bo'lishi mumkinligini bilib olaylik.
Mayli, bu shunchaki televizor reklamasiga o'xshatish uchun qilingan hazil edi.
Endi tushuntirishga qaytaylik.
Asosiy mumkin bo'lgan yechimni topish
Asosiy mumkin bo'lgan yechim (BFS) barcha cheklovlarga javob beradigan va nolga teng bo'lmagan o'zgaruvchilarning eng kam soniga ega bo'lgan chiziqli optimallashtirish muammosining echimidir.
Har bir BFS geometrik nuqtai nazardan mumkin bo'lgan echimlar ko'p yuzli burchagidir.
Agar eng yaxshi yechim bo'lsa, eng yaxshi birinchi qadam ham bo'lishi kerak.
Ushbu maqolada biz boshlang'ich asosiy mumkin bo'lgan yechimni qanday topish, barcha asosiy mumkin bo'lgan echimlarni qanday topish va bo'sh o'zgaruvchilarsiz asosiy mumkin bo'lgan yechimni qanday topish haqida gaplashamiz.
Dastlabki asosiy mumkin bo'lgan yechimni topish
Chiziqli optimallashtirish muammosi uchun ishlaydigan boshlang'ich asosiy yechimni topish uchun muammoning qanday o'rnatilishiga qarab turli usullardan foydalanishimiz mumkin.
Buning bir usuli - tengsizliklar bo'yicha cheklovlarga bo'sh o'zgaruvchilarni qo'shish va boshqa barcha o'zgaruvchilarni nolga o'rnatish.
Bo'sh o'zgaruvchilar asosiy o'zgaruvchilarga aylanadi, qolganlari esa asosiy bo'lmagan o'zgaruvchilardir.
Ikki fazali Simpleks usuli muammoni hal qilishning yana bir usuli hisoblanadi.
Bu usul qo'shimcha chiziqli dasturlash muammosini echishni o'z ichiga oladi, bu mumkin bo'lgan boshlang'ich asosiy yechimni topish.
Dastlabki asosiy mumkin bo'lgan yechim topilgandan so'ng, Simpleks usuli bitta asosiy mumkin bo'lgan yechimdan ikkinchisiga, keyin esa eng yaxshi yechimga o'tish uchun ishlatilishi mumkin.
Barcha asosiy mumkin bo'lgan echimlarni topish
Chiziqli dastur uchun ishlaydigan bir nechta asosiy echimlar bo'lishi mumkin.
Biz bo'sh o'zgaruvchilarni qo'shish orqali tizimni o'zgartirishimiz va keyin chiziqli dastur uchun barcha asosiy mumkin bo'lgan echimlarni topish uchun yangi tizimdan foydalanishimiz mumkin.
Keyinchalik, ushbu asosiy mumkin bo'lgan echimlar asl muammoning asosiy mumkin bo'lgan echimlarini topish uchun ishlatiladi.
Bo'sh o'zgaruvchilarsiz asosiy mumkin bo'lgan yechimni topish
Kamroq cheklovlardan xalos bo'lish uchun biz sust o'zgaruvchilardan foydalanishimiz kerak, shunda biz bo'sh o'zgaruvchilarsiz ishlaydigan asosiy echimni topishimiz mumkin.
Bo'shashtiruvchi o'zgaruvchi faqat cheklovning o'ng tomoni va chap tomoni o'rtasidagi farqdir.
Masalan, birinchi cheklov uchun biz x4 = 14 - 2x1 - x2 - x3 bo'sh o'zgaruvchini aniqlaymiz. Ushbu yangi o'zgaruvchi nuqtai nazaridan, birinchi cheklov oddiygina x4 ≥ 0 ga ekvivalent bo'lib, bu x4 uchun ijobiy cheklovdir.
Ushbu bo'sh o'zgaruvchilarni qo'shsak, biz asl dastur bilan bir xil bo'lgan chiziqli dasturga ega bo'lamiz, bundan mustasno, barcha cheklovlar tenglamalar yoki biror narsani ijobiy deb aytadigan cheklovlardir.
Asosiy yechimda noldan boshqa qiymatlarga ega bo'lgan asosiy o'zgaruvchilar to'plami bazis deb ataladi.
Asosiy yechimda nol qiymatiga ega bo'lgan o'zgaruvchilar asosiy o'zgaruvchilar emas.
Eng yaxshi yechimni topish uchun biz barcha qoidalarga javob beradigan va maqsad uchun eng katta yoki eng kichik qiymatni oladigan x vektorini topishimiz kerak.
Lekin eng yaxshi yechimni topish shunchaki ishlaydigan va hech qanday bo'sh o'zgaruvchilarga ega bo'lmagan yechimni topishdan ko'ra ko'proq qadamlarni talab qiladi.
Bo'shashmasdan o'zgaruvchilarsiz asosiy echimni topish har doim ham mumkin emas, ayniqsa cheklovlar kamroq bo'lgan muammolar uchun.
Asosiy mumkin bo'lgan yechimni topish uchun barcha cheklovlarga javob beradigan va eng kam noldan farqli o'zgaruvchilarga ega bo'lgan yechimni izlash uchun simpleks usuli yoki boshqa chiziqli dasturlash algoritmidan foydalanish kerak.
Asosiy mumkin bo'lgan yechimning xususiyatlari va ahamiyati
Asosiy mumkin bo'lgan yechimning xususiyatlari
Asosiy mumkin bo'lgan yechim nolga teng bo'lmagan ko'pi bilan m o'zgaruvchiga va kamida nm o'zgaruvchiga nolga teng bo'ladi, bu erda n - qaror qabul qiluvchi o'zgaruvchilar soni va m - cheklovlar soni.
BFS - bu mumkin bo'lgan echimlar ko'p yuzli burchagi va har bir BFS chiziqli mustaqil bo'lgan n ta faol cheklovlarga ega.
Agar eng yaxshi yechim bo'lsa, eng yaxshi birinchi qadam ham bo'lishi kerak.
Asosiy amalga oshirilishi mumkin bo'lgan yechimlarning eng muhimi shundaki, ular chiziqli dasturlash muammosi uchun qavariq echimlar to'plamining oxiri hisoblanadi.
Eng yaxshi javobni topish uchun simpleks algoritmi bir qator BFSlardan o'tadi.
Simpleks algoritmi eng yaxshisini topish uchun barcha asosiy mumkin bo'lgan echimlarni uyushgan tarzda qidiradi.
Asosiy mumkin bo'lgan yechimning ahamiyati
Mumkin bo'lgan asosiy yechimni topish muhim, chunki u chiziqli dasturlash muammolariga eng yaxshi javobni topishga yordam beradi.
Bundan tashqari, u murakkab algoritmlarga boshlash uchun joy beradi va chiziqli dasturning mumkin yoki yo'qligini aniqlash uchun ishlatilishi mumkin.
Chiziqli dastur uchun barcha asosiy mumkin bo'lgan echimlarni topish uchun siz bo'sh o'zgaruvchilarni qo'shish orqali tizimni o'zgartirishingiz mumkin va keyin barcha asosiy mumkin bo'lgan echimlarni topish uchun o'zgartirilgan tizimdan foydalanishingiz mumkin.
Keyinchalik, ushbu asosiy mumkin bo'lgan echimlar asl muammoning asosiy mumkin bo'lgan echimlarini topish uchun ishlatiladi.
Video: Asosiy mumkin bo'lgan echimlar
Maslahat: Agar kerak bo'lsa, taglavha tugmasini yoqing. Agar siz og'zaki tilni yaxshi bilmasangiz, sozlamalar tugmachasida "avtomatik tarjima" ni tanlang. Sevimli tilingiz tarjima uchun mavjud boʻlishidan avval videoning tilini bosishingiz kerak boʻlishi mumkin.
Foydalanish holatlari
| Ishlatilgan: | Tavsif: |
|---|---|
| Resurslarni taqsimlash: | BFS cheklangan resurslarni bir nechta loyihalar o'rtasida taqsimlash uchun ishlatilishi mumkin, shuning uchun eng kamini bajarish mumkin. Bu usul transport, dehqonchilik va moliya kabi turli sohalarda qo'llanilishi mumkin. |
| Tarmoqni optimallashtirish: | BFS aloqa, transport va logistika tarmoqlarini yaxshiroq ishlashi uchun ishlatilishi mumkin. BFS tovarlar va xizmatlar uchun eng yaxshi marshrutlarni topishga yordam beradi, transportga sarflangan vaqt va pulni qisqartiradi, yetkazib berishni tezlashtiradi va aniqroq qiladi. |
| Ishlab chiqarishni rejalashtirish: | BFS ishlab chiqarishni rejalashtirish uchun ishlatilishi mumkin, shuning uchun mehnat, xom ashyo va uskunalar kabi resurslar ulardan maksimal darajada foydalanish uchun eng yaxshi tarzda ishlatiladi. BFS ishlab chiqarish xarajatlarini kamaytirishga, chiqindilarni kamaytirishga va samaradorlikni oshirishga yordam beradi. |
| Moliyaviy rejalashtirish: | Moliyaviy rejalashtirishda BFS investitsiya portfellarini optimallashtirish, xavfni kamaytirish va eng ko'p pulni qaytarish uchun ishlatilishi mumkin. BFS aktivlarni taqsimlash, tranzaksiya xarajatlarini kamaytirish va ko'proq pul ishlashning eng yaxshi usulini topishga yordam beradi. |
| Ta'minot zanjirini boshqarish: | BFS ta'minot zanjirini boshqarishning bir qismi sifatida etkazib beruvchilardan mijozlarga tovarlar va xizmatlar oqimini yaxshilash uchun ishlatilishi mumkin. BFS qo'lda ushlab turish uchun eng yaxshi zaxira miqdorini aniqlashga, etkazib berish vaqtlarini qisqartirishga va mijozlarga xizmat ko'rsatishni yaxshilashga yordam beradi. |
Xulosa
Mumkin bo'lgan asosiy echimlarga qarash tugashi bilan, ular har qanday muhandis yoki muhandislik talabasi uchun muhim vosita ekanligi ayon bo'ladi.
Murakkab tizimni yaratishning eng yaxshi usulini aniqlashdan tortib mavjud resurslardan maksimal darajada foydalanishgacha bo'lgan asosiy mumkin bo'lgan echimlar eng yaxshi natijaga erishish uchun asos yaratadi.
Ammo ular foydali bo'lishdan ko'ra, matematikaning naqadar oqlangan va chiroyli ekanligini ko'rsatadi.
Ajablanarlisi shundaki, siz murakkab masalalarni oddiy tenglamalar to'plamiga aylantira olasiz va keyin haqiqiy dunyoda muammolarni hal qilish uchun bu tenglamalardan foydalanishingiz mumkin.
Bu muhandislik muammoni hal qilishdan iborat ekanligini va matematikaning kuchidan foydalanib, biz ilgari imkonsiz deb hisoblangan javoblarni topishimiz mumkinligini eslatib turadi.
Shunday qilib, muhandislik haqida ko'proq ma'lumotga ega bo'lganingizda, ishlaydigan oddiy echimlar haqida o'rganganlaringizni yodda tuting va ulardan dunyoni yaxshiroq va samaraliroq joyga aylantiring.
Havolalar va havolalar
Kitoblar:
- Chiziqli dasturlash: asoslar va kengaytmalar
- Chiziqli dasturlash: nazariya va ilovalar
Ulashish…
