Agar siz muhandis yoki muhandislik talabasi bo'lsangiz, optimallashtirish nimani anglatishini bilishingiz mumkin.
Mumkin bo'lgan eng yaxshi natijaga erishish uchun narsalarni qilishning eng yaxshi usulini topish muhimdir.
Chiziqli dasturlashda siz eng yaxshi yechimni topish uchun asosiy yechimdan foydalanishingiz mumkin.
Lekin asosiy yechim nima va nega muhandislar ular haqida bilish juda muhim? Ushbu maqolada men asosiy echimlar nima ekanligi, nima uchun ular muhandislikda muhimligi va turli vaziyatlarda eng yaxshi natijalarni olish uchun ulardan qanday foydalanish mumkinligi haqida gapirib beraman.
Shunday qilib, bog'ingizni bog'lang va asosiy echimlar dunyosiga sho'ng'ishga tayyorlaning, u erda men sirlarni ochaman va sizga bu texnika qanchalik kuchli ekanligini ko'rsataman.
Chiziqli dasturlashning asosiy yechimlari
Rasmiy ta'rif:
n ta o‘zgaruvchidagi m tenglamadan iborat chiziqli dastur modeli yechimi m o‘zgaruvchini qolgan (nm) o‘zgaruvchilar bo‘yicha yechish va (nm) o‘zgaruvchilarni nolga tenglashtirish orqali olinadi.
Chiziqli dasturlashda asosiy yechim ma'lum texnik talablarga javob beradigan chiziqli dasturlash masalasini hal qilish usulidir.
Xususan, agar {ai : xi = 0} vektorlari chiziqli mustaqil boʻlsa, x vektori koʻp yuzli uchun asosiy yechim hisoblanadi.
Demak, A ning nolga teng bo'lmagan xi o'zgaruvchilari bo'lgan ustunlari chiziqli mustaqildir.
Manfiy bo'lmagan komponentlarga ega bo'lgan asosiy yechim asosiy mumkin bo'lgan yechim (BFS) (BFS) deb ataladi.
BFS ko'pburchakni belgilaydigan barcha qoidalarga javob beradi.
Har bir BFS geometrik nuqtai nazardan mumkin bo'lgan echimlar ko'p yuzli burchagidir.
Asosiy yechimni topish uchun siz asosiy bo'lmagan nm o'zgaruvchilarni nolga o'rnatishingiz va asosiy bo'lgan m o'zgaruvchilarni echishingiz kerak.
Turli asoslar bir xil asosiy yechimga olib kelishi mumkin, ya'ni bir muammoni hal qilishning bir nechta usullari bo'lishi mumkin.
Simpleks usuli iterativ jarayon bo'lib, u eng yaxshi BFS ni topguncha bir BFS dan keyingi BFS ga o'tadi.
BFS ni topish uchun simpleks usulidan foydalangandan so'ng, biz yaqin atrofdagi boshqa BFSlar maqsad funktsiyasi uchun yaxshiroq qiymat berganligini ko'rish orqali eng yaxshi yechim ekanligini aniqlashimiz mumkin.
Agar bunday BFS bo'lmasa, hozirgi BFS eng yaxshisidir.
Chiziqli dasturlash modeli
Chiziqli dasturlash modeli uchta asosiy komponentni o'z ichiga oladi: qaror o'zgaruvchilari, maqsad funktsiyasi va cheklovlar.
Maqsad funktsiyasi ham, cheklovlar ham chiziqli funktsiyalar bo'lishi kerak va qaror o'zgaruvchilari doimiy bo'lishi kerak.
Maqsad funktsiyasi foyda, tannarx, ishlab chiqarilgan mahsulot soni va hokazolarni ko'rsatadigan sonni oshirish yoki kamaytirish uchun ishlatiladi.
Cheklovlar - bu qaror o'zgaruvchilaridagi muvaffaqiyat darajasini belgilaydigan vazifalarni bajarish uchun zarur bo'lgan ma'lum bir resursning umumiy miqdoriga cheklovlar yoki cheklovlar.
Bundan tashqari, ba'zi chiziqli dasturlar barcha qaror o'zgaruvchilari salbiy bo'lmasligini talab qiladi.
Chiziqli dasturlash modellarida siz butun va ikkilik o'zgaruvchilardan ham foydalanishingiz mumkin.
Ikkilik o'zgaruvchilar faqat 0 yoki 1 qiymatiga ega bo'lishi mumkin, shuning uchun ular faqat 0 yoki 1 qiymatiga ega bo'lishi mumkin.
Simpleks usuli
Chiziqli dasturlash masalalarini hal qilishning eng ko'p qo'llaniladigan usullaridan biri Simpleks usulidir.
Simpleks usulida asosiy yechimlar muhim ahamiyatga ega, chunki ular amalga oshirilishi mumkin bo'lgan hududning burchak nuqtalariga to'g'ri keladi va simpleks usuli optimal yechim topilgunga qadar bir burchakdan ikkinchi burchakka o'tadi.
Simpleks usuli chiziqli dasturlash masalasiga asosiy yechimlar xossalaridan foydalangan holda eng yaxshi javobni topishning tezkor usulidir.
Eng yaxshi BFS ni topish uchun simpleks usulidan foydalanish uchun A cheklash matritsasi uchun B bazisni topishimiz va Ax = b sistemasini nolga o'rnatilgan bazisdan boshqa barcha o'zgaruvchilar bilan hal qilishimiz kerak.
Asosiy o'zgaruvchilar uchun olingan qiymatlar BFS ni tashkil qiladi.
Agar optimal yechim mavjud bo'lsa, unda optimal BFS mavjud.
Simpleks usuli pivot protseduralari yordamida optimal BFS ga yetguncha bitta BFS dan qo'shni BFS ga o'tadi.
Asosiy echimlar va mumkin bo'lgan echimlar o'rtasidagi taqqoslash
Asosiy yechim va mumkin bo'lgan yechim o'rtasidagi farq shundaki, asosiy yechim hech qanday shartlarga javob berishi shart emas.
Xususan, u chiziqli mustaqil va xi uchun nolga teng bo'lmagan qiymatlarga ega bo'lgan vektorlarga ega bo'lishi va x 0 dan kichik bo'lishi kerak.
Boshqa tomondan, mumkin bo'lgan yechim muammoning chegarasiga to'g'ri keladigan har qanday nuqtadir.
Ammo barcha mumkin bo'lgan echimlar asosiy mumkin bo'lgan echimlar emas.
Asosiy amalga oshirilishi mumkin bo'lgan echimlar (BFS) faqat mumkin bo'lgan echimlar ko'pburchak burchaklariga mos keladigan echimlardir.
Asoslarga qaytish: Muhandislikdagi asosiy yechimlarning kuchini ochish
Hali ham tushunish qiyinmi? Keling, nuqtai nazarni biroz o'zgartiraman:
Qiyin muammolarni hal qilish uchun murakkab usullar va algoritmlardan foydalanishdan charchadingizmi? Chiziqli dastur modeli muammolarini hal qilishning oddiyroq va to'g'ri yo'li bo'lishini xohlaysizmi?
Xavotir olmang, chunki javob shu yerda: qolgan (nm) o‘zgaruvchilar bo‘yicha m o‘zgaruvchini yeching va (nm) o‘zgaruvchilarni nolga qo‘ying.
Asoslarga qaytishingiz mumkin bo'lganingizda, chiroyli ko'rinadigan algoritmlar kimga kerak? Shunday qilib, kalkulyatorlaringizni qo'ying va oddiy echimlarni o'rganishni boshlaylik.
Mayli, bu shunchaki televizor reklamasiga o'xshatish uchun qilingan hazil edi.
Endi tushuntirishga qaytaylik.
Asosiy yechim chiziqli dasturlash
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: | Asosiy yechim resurslarni taqsimlash muammolarida qo'llanilishi mumkin, bunda maqsad cheklangan resurslarni raqobatdosh ehtiyojlar o'rtasida taqsimlashdir. Masalan, kompaniya o'z byudjetini turli bo'limlar yoki loyihalar o'rtasida taqsimlashi kerak bo'lishi mumkin. Asosiy echimlardan foydalangan holda, ular eng ko'p pul ishlash yoki iloji boricha kamroq sarflash uchun o'z resurslaridan foydalanishning eng yaxshi usulini aniqlashlari mumkin. |
| Ishlab chiqarishni rejalashtirish: | Ishlab chiqarishni rejalashtirishda asosiy yechim eng ko'p pul ishlash uchun mahsulotlarning eng yaxshi aralashmasini aniqlash uchun ishlatilishi mumkin. Kompaniyalar asosiy yechimdan foydalangan holda eng ko'p pul olib keladigan va eng kam xarajat qiladigan eng yaxshi ishlab chiqarish aralashmasini topishlari mumkin. |
| Rejalashtirish: | Asosiy yechim vazifalarni yoki ishlarni eng samarali tarzda bajarish uchun qanday rejalashtirishni aniqlash uchun ishlatilishi mumkin. Misol uchun, kompaniya o'z xodimlarining ish vaqtini rejalashtirishi kerak bo'lishi mumkin, ular ish bilan band bo'lganda etarli ishchilar borligiga ishonch hosil qilishlari mumkin. Asosiy yechimdan foydalangan holda, ular imkon qadar kamroq to'xtab qolish va imkon qadar ko'proq ish qilish uchun ishlarni rejalashtirishning eng yaxshi usulini aniqlashlari mumkin. |
| Ta'minot zanjirini boshqarish: | Ta'minot zanjirini boshqarishda maqsad tovarlar va xizmatlarning etkazib beruvchidan mijozga imkon qadar silliq o'tishiga ishonch hosil qilishdir. Misol uchun, biznes xarajatlarni minimallashtirish va tovarlarni o'z vaqtida etkazib berish uchun tovarlarni tashishning eng yaxshi yo'llarini aniqlashi kerak bo'lishi mumkin. Asosiy echimlardan foydalangan holda, ular xarajatlarni past ushlab turadigan va mijozlarni xursand qiladigan ta'minot zanjirini boshqarishning eng yaxshi rejasini topishlari mumkin. |
| Portfelni optimallashtirish: | Portfelni optimallashtirishda, maqsad eng kam tavakkal qilib, eng ko'p pul ishlash uchun investitsiyalarning eng yaxshi aralashmasini topish bo'lsa, asosiy echimlardan foydalanish mumkin. Misol uchun, investitsiya firmasi o'z mijozlariga investitsiya maqsadlariga erishishda yordam berish uchun aktsiyalar, obligatsiyalar va boshqa qimmatli qog'ozlarning eng yaxshi aralashmasini aniqlashi kerak bo'lishi mumkin. Oddiy yechimdan foydalanib, ular o'z portfellarini aralashtirishning eng yaxshi usulini topishlari mumkin, shunda ular eng kam tavakkalchilikni o'z zimmalariga olgan holda eng yaxshi daromad olishlari mumkin. |
Xulosa
Xulosa qilib aytadigan bo'lsak, asosiy yechim g'oyasi muhandislik sohasida juda muhim va uni turli xil usullarda qo'llash mumkin.
Asosiy yechim nima ekanligini va chiziqli dasturlashda nima qilishini bilish orqali biz yechimlarni yaxshilashimiz, xarajatlarni kamaytirishimiz va ularni yanada samaraliroq qilishimiz mumkin.
Lekin shuni yodda tutish kerakki, asosiy yechim kuchli vosita bo‘lsa ham, bir o‘lchamdagi yechim emas.
Eng yaxshi natijalarga erishish uchun har bir muammoni diqqat bilan ko'rib chiqish va o'ylash kerak.
Muhandislar sifatida biz asosiy yechimlar va boshqa optimallashtirish usullari qanday qilib taraqqiyotga erishishimiz va yangi g‘oyalarni ishlab chiqishimizga yordam berishi mumkinligini o‘rganishda davom etishimiz kerak.
Shunday qilib, keling, oddiy echimlarning kuchini tan olaylik va yangi texnika va strategiyalardan foydalangan holda mumkin bo'lgan narsalar chegarasini bosib o'taylik.
Havolalar va havolalar
Kitoblar:
- Vasek Chvatal tomonidan chiziqli dasturlash
- R bilan chiziqli dasturlashni modellashtirish va yechish Xose M. Sallan tomonidan
Ulashish…
