Optimallashtirish foyda keltiradigan, xarajatlarni kamaytiradigan yoki biznes jarayonidagi nosozliklarni keltirib chiqaradigan parametrni oʻrnatadigan eng yaxshi natijani topishga yordam beradi.
Bu jarayon matematik dasturlash deb ham ataladi. Bu optimallashtirish muammosi rahbari tomonidan qo'yilgan maqsadga erishish uchun zarur bo'lgan cheklangan resurslarni taqsimlashni aniqlash muammosini hal qiladi. Barcha mumkin bo'lgan variantlardan nazorat parametrini, masalan, foyda yoki xarajatlarni maksimal darajada oshiradigan (yoki kamaytiradigan) variantni topish maqsadga muvofiqdir. Optimallashtirish modellari ko'rsatmalar yoki me'yoriy deb ham ataladi, chunki ular biznes uchun mumkin bo'lgan strategiyani topishga intiladi.
Rivojlanish tarixi
Chiziqli dasturlash (LP) barcha cheklovlar chiziqli boʻlgan optimallashtirish muammolari sinfi bilan ishlaydi.
LP rivojlanishining qisqacha tarixini taqdim etish:
- 1762 yilda Lagrange tenglik cheklovlari bilan oddiy optimallashtirish masalalarini hal qildi.
- 1820 yilda Gauss qaror qildieliminatsiya yordamida chiziqli tenglamalar tizimi.
- 1866 yilda Vilgelm Jordan mos mezon sifatida eng kichik kvadratlar xatolarini topish usulini takomillashtirdi. Bu endi Gauss-Jordan usuli deb ataladi.
- Raqamli kompyuter 1945-yilda paydo boʻlgan.
- Danzig 1947 yilda simpleks usullarini ixtiro qilgan.
- 1968 yilda Fiacco va McCormick Inside Point usulini joriy qilishdi.
- 1984-yilda Karmarkar oʻzining innovatsion tahlilini qoʻshib, chiziqli dasturlarni yechish uchun interyer usulini qoʻlladi.
LP real muammolarni modellashtirish uchun ham, keng qoʻllaniladigan matematik nazariya sifatida ham oʻta kuchli vosita ekanligini isbotladi. Biroq, ko'plab qiziqarli optimallashtirish muammolari chiziqli emas.
Bunday holatda nima qilish kerak? Bunday muammolarni o'rganish chiziqli algebra, ko'p o'lchovli hisoblash, raqamli tahlil va hisoblash usullarining turli xil aralashmasini o'z ichiga oladi. Olimlar hisoblash algoritmlarini, jumladan chiziqli dasturlash, geometriya, qavariq toʻplamlar va funksiyalar tahlili hamda kvadratik dasturlash kabi maxsus tuzilgan muammolarni oʻrganish uchun ichki nuqta usullarini ishlab chiqmoqdalar.
Nochiziqli optimallashtirish matematik tahlilning fundamental tushunchasini beradi va muhandislik, regressiya tahlili, resurslarni boshqarish, geofizikaviy qidiruv va iqtisodiyot kabi turli sohalarda keng qoʻllaniladi.
Optimallashtirish muammolari tasnifi
Muhim qadamOptimallashtirish jarayoni modellarni tasniflashdir, chunki ularni hal qilish algoritmlari muayyan turga moslashtirilgan.
1. Diskret va uzluksiz optimallashtirish bilan bog'liq muammolar. Ba'zi modellar o'zgaruvchilar diskret butun sonlar to'plamidan qiymatlarni olgan taqdirdagina mantiqiy bo'ladi. Boshqalar esa har qanday haqiqiy qiymatga ega bo'lishi mumkin bo'lgan ma'lumotlarni o'z ichiga oladi. Odatda ularni hal qilish osonroq. Algoritmlarning takomillashtirilishi kompyuter texnologiyalaridagi yutuqlar bilan birgalikda chiziqli dasturlashni optimallashtirish muammosining hajmi va murakkabligini keskin oshirdi.
2. Cheksiz va cheklangan optimallashtirish. Yana bir muhim farq - bu o'zgaruvchilarga hech qanday cheklovlar bo'lmagan vazifalar. U oddiy hisoblagichlardan tortib, ma'lumotlar o'rtasidagi murakkab munosabatlarni modellashtiruvchi tenglik va tengsizliklar tizimlarigacha keng bo'lishi mumkin. Bunday optimallashtirish masalalarini funksiyalarning tabiatiga ko‘ra (chiziqli va chiziqli bo‘lmagan, qavariq va silliq, differensiallanuvchi va ajratilmaydigan) yana tasniflash mumkin.
3. Texnik-iqtisodiy vazifalar. Ularning maqsadi hech qanday optimallashtirish maqsadisiz model cheklovlarini qondiradigan oʻzgaruvchan qiymatlarni topishdir.
4. To'ldiruvchi vazifalar. Ular texnologiya va iqtisodiyotda keng qo'llaniladi. Maqsad - bir-birini to'ldirish shartlarini qondiradigan yechim topish. Amalda, bir nechta maqsadlarga ega bo'lgan vazifalar ko'pincha bitta maqsadli vazifalarga aylantiriladi.
5. Deterministik va stokastik optimallashtirish. Deterministik optimallashtirish ma'lumotlar uchun nazarda tutaditopshiriqlar to'liq aniq. Biroq, ko'plab dolzarb mavzularda ular bir qator sabablarga ko'ra ma'lum bo'lmaydi.
Birinchisi oddiy oʻlchash xatosi bilan bogʻliq. Ikkinchi sabab esa asosiyroq. Bu shuni anglatadiki, ba'zi ma'lumotlar kelajak haqidagi ma'lumotlarni, masalan, mahsulotga bo'lgan talab yoki kelajakdagi vaqt narxini aks ettiradi. Stokastik optimallashtirish sharoitida optimallashtirishda noaniqlik modelga kiritiladi.
Asosiy komponentlar
Maqsad funksiyasi - bu kichraytirish yoki maksimallashtirish. Optimallashtirish masalalarining aksariyat turlari bitta maqsad funksiyasiga ega. Aks holda, ular tez-tez ishlash uchun qayta shakllantirilishi mumkin.
Ushbu qoidadan ikkita istisno:
1. Maqsadli qidiruv vazifasi. Ko'pgina biznes ilovalarida menejer model cheklovlarini qondirish bilan birga aniq maqsadga erishmoqchi. Foydalanuvchi biror narsani optimallashtirishni istamaydi, shuning uchun maqsad funktsiyasini belgilash mantiqiy emas. Bu tur odatda qoniqish muammosi deb ataladi.
2. Ko'p ob'ektiv xususiyatlar. Ko'pincha, foydalanuvchi bir vaqtning o'zida bir nechta turli maqsadlarni optimallashtirishni xohlaydi. Ular odatda mos kelmaydi. Bitta maqsad uchun optimallashtirilgan oʻzgaruvchilar boshqalar uchun eng yaxshisi boʻlmasligi mumkin.
Komponent turlari:
- Boshqariladigan kirish - bu maqsad funksiya qiymatiga ta'sir qiluvchi qaror o'zgaruvchilari to'plami. Ishlab chiqarish vazifasida o'zgaruvchilar turli xil mavjud resurslarni taqsimlashni yoki zarur bo'lgan mehnatni o'z ichiga olishi mumkinhar bir harakat.
- Cheklovlar qaror oʻzgaruvchilari va parametrlari oʻrtasidagi munosabatlardir. Ishlab chiqarish muammosi uchun har qanday faoliyatga ko‘p vaqt sarflash mantiqiy emas, shuning uchun barcha “vaqtinchalik” o‘zgaruvchilarni cheklang.
- Imumkin va maqbul echimlar. Barcha cheklovlar qondiriladigan o'zgaruvchilar bo'yicha qarorning qiymati qoniqarli deb ataladi. Aksariyat algoritmlar avval uni topadi, keyin uni yaxshilashga harakat qiladi. Nihoyat, ular bir mumkin bo'lgan yechimdan boshqasiga o'tish uchun o'zgaruvchilarni o'zgartiradilar. Bu jarayon maqsad funksiyasi maksimal yoki minimal darajaga yetguncha takrorlanadi. Bu natija optimal yechim deb ataladi.
Quyidagi matematik dasturlar uchun ishlab chiqilgan optimallashtirish masalalari algoritmlari keng qoʻllaniladi:
- Qavariq.
- Ajralishi mumkin.
- Kvadrat.
- Geometrik.
Google Lineer Solvers
Chiziqli optimallashtirish yoki dasturlash - muammoni optimal hal qilishning hisoblash jarayoniga berilgan nom. U koʻplab ilmiy va muhandislik fanlarida yuzaga keladigan chiziqli munosabatlar toʻplami sifatida modellashtirilgan.
Google chiziqli optimallashtirish muammolarini hal qilishning uchta usulini taklif qiladi:
- Glop ochiq manba kutubxonasi.
- Google Sheets uchun chiziqli optimallashtirish plagini.
- Google Apps skriptida chiziqli optimallashtirish xizmati.
Glop Google-ga oʻrnatilganchiziqli hal qiluvchi. U ochiq manbada mavjud. Siz Glopga OR-Tools chiziqli hal qiluvchi oʻrami orqali kirishingiz mumkin, bu Glop uchun oʻram hisoblanadi.
Google Sheets uchun chiziqli optimallashtirish moduli elektron jadvalga maʼlumotlarni kiritish orqali optimallashtirish muammosining chiziqli bayonini bajarish imkonini beradi.
Kadratik dasturlash
Premium Solver platformasi Simpleks usulining kengaytirilgan LP/Kvadratik versiyasidan LP va QP muammolarini qayta ishlash chegaralari 2000 tagacha qaror oʻzgaruvchisidan foydalanadi.
SQP Keng koʻlamli masalalarni hal qiluvchi kvadratik dasturlash (QP) masalalarini yechish uchun siyraklik bilan faol toʻplam usulini zamonaviy tatbiq etishdan foydalanadi. XPRESS Solver dvigateli QP muammolarini hal qilish uchun "Interior Point" yoki Nyuton to'sig'i usulining tabiiy kengaytmasidan foydalanadi.
MOSEK Solver o'rnatilgan "Inside Point" va avtomatik dual usullarni qo'llaydi. Bu, ayniqsa, bo'shashgan QP muammolari uchun samarali. Shuningdek, u o'lchovli kvadratik cheklov (QCP) va ikkinchi tartibli konusni dasturlash (SOCP) muammolarini hal qilishi mumkin.
Koʻp amalli hisoblar
Ular Microsoft Office xususiyatlaridan foydalanishda, masalan, Excelda optimallashtirish muammolarini hal qilishda juda muvaffaqiyatli foydalanilmoqda.
Yuqoridagi jadvalda belgilar:
- K1 - K6 - tovarlarni taqdim etishi kerak bo'lgan mijozlar.
- S1 - S6 - buning uchun qurilishi mumkin bo'lgan potentsial ishlab chiqarish joylari. Yaratish mumkin1, 2, 3, 4, 5 yoki barcha 6 ta joy.
I ustunda koʻrsatilgan har bir obʼyekt uchun qatʼiy xarajatlar mavjud (tuzatish).
Agar joylashuv hech narsani oʻzgartirmasa, hisobga olinmaydi. Shunda hech qanday doimiy xarajatlar bo‘lmaydi.
Eng past narxni olish uchun potentsial joylarni aniqlang.
Bunday sharoitlarda joylashuv belgilanadi yoki yoʻq. Bu ikki holat: "TRUE - FALSE" yoki "1 - 0". Oltita joy uchun oltita shtat mavjud, masalan, 000001 faqat oltinchiga, 111111 hammasiga oʻrnatilgan.
Iklik sanoq tizimida 000001 (1) dan 111111 (63) gacha boʻlgan aniq 63 xil variant mavjud.
L2-L64 endi {=MULTIPLE OPERATION (K1)} ni oʻqishi kerak, bu barcha muqobil yechimlarning natijalari. Keyin minimal qiymat=Min (L) va mos keladigan alternativ INDEX (K).
CPLEX butun sonli dasturlash
Ba'zida biznes muammosining mohiyatini tushunish uchun chiziqli munosabatlar etarli emas. Bu, ayniqsa, qarorlar muayyan joyda omborni ochish yoki ochmaslik kabi diskret tanlovlarni o'z ichiga olgan taqdirda to'g'ri keladi. Bunday holatlarda butun sonli dasturlashdan foydalanish kerak.
Agar muammo diskret va uzluksiz tanlovlarni oʻz ichiga olsa, bu aralash butun sonli dasturdir. Unda chiziqli, qavariq kvadratik masalalar va bir xil ikkinchi tartibli cheklovlar boʻlishi mumkin.
Integer dasturlari chiziqli dasturlarga qaraganda ancha murakkab, lekin ular muhim biznes ilovalariga ega. Dasturiy ta'minotCPLEX dasturi butun sonli masalalarni yechish uchun murakkab matematik usullardan foydalanadi. Uning usullari optimal yechim qiymati bo'yicha chegaralarni hisoblash uchun chiziqli yoki kvadratik dasturiy ta'minot relaksatsiyalari yordamida diskret o'zgaruvchilarning mumkin bo'lgan kombinatsiyalarini tizimli ravishda qidirishni o'z ichiga oladi.
Cheklovlarni hisoblash uchun ular LP va boshqa optimallashtirish muammolarini hal qilish usullaridan ham foydalanadilar.
Standart Microsoft Excel Solver
Ushbu texnologiya LP muammolarini hal qilish uchun asosiy Simpleks usulining asosiy amaliyotidan foydalanadi. U 200 ta o'zgaruvchi bilan cheklangan. "Premium Solver" o'zgaruvchilar uchun ikki tomonlama chegaralar bilan takomillashtirilgan asosiy simpleks usulidan foydalanadi. Premium Solver platformasi 2000 tagacha qaror oʻzgaruvchisi bilan optimallashtirish muammosini hal qilish uchun LP/Quadratic Simplex Solverning kengaytirilgan versiyasidan foydalanadi.
Premium Solver platformasi uchun keng miqyosli LP oddiy va qoʻshaloq simpleks usulining zamonaviy tatbiqini qoʻllaydi, bu esa vaqt va xotirani tejash uchun LP modelidagi siyraklikdan, yangilash va yangilash uchun ilgʻor strategiyalardan foydalanadi. matritsalarni qayta ishlash, ko'p va qisman narxlarni belgilash va aylanishlar va degeneratsiyani bartaraf etish uchun. Bu dvigatel uchta versiyada mavjud (8 000, 32 000 tagacha yoki cheksiz oʻzgaruvchilar va cheklovlar bilan ishlashga qodir).
MOSEK Solver birlamchi va dual simpleksni o'z ichiga oladi, bu usul ham siyraklikdan foydalanadi va matritsalarni yangilash va "refaktorizatsiya" uchun ilg'or strategiyalardan foydalanadi. Bu cheksiz hajmdagi muammolarni hal qiladi, edimillionlab qaror oʻzgaruvchilari bilan chiziqli dasturlash muammolari boʻyicha sinovdan oʻtkazildi.
EXCEL-da bosqichma-bosqich misol
Excelda optimallashtirish muammosi modelini aniqlash uchun quyidagi amallarni bajaring:
- Muammo uchun ma'lumotlarni mantiqiy shaklda elektron jadvalda tartiblang.
- Har bir oʻzgaruvchini saqlash uchun katakchani tanlang.
- Yacheykada optimallashtirish muammosining maqsadli matematik modelini hisoblash formulasini yarating.
- Har bir cheklovning chap tomonini hisoblash uchun formulalar yarating.
- Echuvchiga qaror oʻzgaruvchilari, maqsadlar, cheklovlar va ushbu parametrlar boʻyicha kerakli chegaralar haqida xabar berish uchun Excel dialog oynalaridan foydalaning.
- Optimal yechimni topish uchun “Yechuvchi”ni ishga tushiring.
- Excel varaqini yarating.
- Maqsad funksiyasi va cheklov formulasi hisoblangan Excelda muammo ma'lumotlarini tartibga soling.
Yuqoridagi jadvalda B4, C4, D4 va E4 katakchalari X 1, X 2, X 3 va X 4 qaror oʻzgaruvchilarini ifodalash uchun ajratilgan. Qarorga misollar:
- Mahsulot aralashmasi modeli (har bir mahsulot uchun $450, $1150, $800 va $400 foyda) mos ravishda B5, C5, D5 va E5 katakchalariga kiritilgan. Bu maqsadni F5=B5B4 + C5C4 + D5D4 + E5E4 yoki F5:=SUMPRODUCT (B5: E5, B4: E4) da hisoblash imkonini beradi.
- B8-ga har bir turdagi mahsulot ishlab chiqarish uchun zarur boʻlgan resurslar miqdorini kiriting.
- F8 formulasi:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Buni nusxalashF9 da formula. $B$4:$E$4dagi dollar belgilari bu katakcha diapazoni oʻzgarmasligini koʻrsatadi.
- G8-ga o'ngdagi cheklovlar qiymatlariga mos keladigan har bir turdagi resurslarning mavjud miqdorini kiriting. Bu ularni quyidagicha ifodalash imkonini beradi: F11<=G8: G11.
- Bu toʻrtta chegaraga ekvivalentdir F8<=G8, F9 <=G9, F10 <=G10 va F11=0
Usulni amaliy qoʻllash sohalari
Chiziqli optimallashtirishda optimallashtirish muammosiga misol sifatida koʻplab amaliy ilovalar mavjud:
Kompaniya ma'lum hissa marjasi bilan bir nechta mahsulotlarni ishlab chiqishi mumkin. Har bir buyumning bir birligini ishlab chiqarish ma'lum miqdordagi cheklangan resurslarni talab qiladi. Vazifa har bir mahsulotning qancha qismini ishlab chiqarish kerakligini aniqlash uchun ishlab chiqarish dasturini yaratishdan iborat bo‘lib, kompaniya foydasi resurslar cheklovlarini buzmasdan maksimal darajaga ko‘tariladi.
Aralash muammolari ingredientlarni yakuniy mahsulotga birlashtirish bilan bog'liq optimallashtirish muammolarining yechimidir. Bunga misol qilib, 1947 yilda Jorj Danzig tomonidan o'rganilgan parhez muammosini keltirish mumkin. Suli, cho'chqa go'shti va kungaboqar yog'i kabi bir qator xom ashyolar, oqsil, yog', A vitamini kabi ozuqaviy tarkibi va ularning kilogramm narxi bilan birga beriladi. Qiyinchilik xomashyodan bir yoki bir nechta yakuniy mahsulotlarni ozuqaviy qiymatining minimal va maksimal chegaralariga rioya qilgan holda iloji boricha arzon narxlarda aralashtirishdan iborat.
Chiziqli optimallashtirish muammosining klassik qoʻllanilishi ehtiyojlar uchun marshrutni aniqlashdirtelekommunikatsiya yoki transport tarmoqlaridagi trafik. Shu bilan birga, oqimlar tarmoq boʻylab shunday yoʻn altirilishi kerakki, barcha trafik talablari tarmoqli kengligi shartlarini buzmasdan bajariladi.
Matematik nazariyada chiziqli optimallashtirish ikki kishi uchun nol yigʻindili oʻyinlarda optimal strategiyalarni hisoblash uchun ishlatilishi mumkin. Bunda har bir ishtirokchi uchun ehtimollik taqsimoti hisoblanadi, bu uning strategiyalarini tasodifiy aralashtirish koeffitsienti hisoblanadi.
Dunyoda hech qanday muvaffaqiyatli biznes jarayoni optimallashtirishsiz mumkin emas. Ko'p optimallashtirish algoritmlari mavjud. Ba'zi usullar faqat muayyan turdagi muammolar uchun javob beradi. Ularning xususiyatlarini tan olish va tegishli yechim usulini tanlash muhim.
