بهینه‌سازی به شما کمک می‌کند بهترین نتیجه را بیابید که سود می‌آورد، هزینه‌ها را کاهش می‌دهد یا پارامتری را تعیین می‌کند که باعث شکست فرآیند کسب‌وکار می‌شود.
به این فرآیند برنامه نویسی ریاضی نیز می گویند. مشکل تعیین توزیع منابع محدود لازم برای دستیابی به هدف تعیین شده توسط رئیس مسئله بهینه سازی را حل می کند. از بین همه گزینه های ممکن، مطلوب است که گزینه ای را پیدا کنید که پارامتر کنترل را به حداکثر می رساند (یا کاهش می دهد)، به عنوان مثال، سود یا هزینه. مدل‌های بهینه‌سازی تجویزی یا هنجاری نیز نامیده می‌شوند زیرا به دنبال یافتن یک استراتژی عملی برای تجارت هستند.
سابقه توسعه
برنامه‌نویسی خطی (LP) با دسته‌ای از مسائل بهینه‌سازی کار می‌کند که در آن همه محدودیت‌ها خطی هستند.
ارائه تاریخچه مختصری از توسعه LP:
- در سال 1762، لاگرانژ مسائل ساده بهینه‌سازی را با محدودیت‌های برابری حل کرد.
- در سال 1820، گاوس تصمیم گرفتسیستم معادلات خطی با استفاده از حذف.
- در سال 1866، ویلهلم جردن روش یافتن حداقل مربعات خطا را به عنوان یک معیار مناسب کامل کرد. اکنون این روش گاوس-اردن نامیده می شود.
- کامپیوتر دیجیتال در سال 1945 ظاهر شد.
- Danzig روش های سیمپلکس را در سال 1947 اختراع کرد.
- در سال 1968، فیاکو و مک کورمیک روش Inside Point را معرفی کردند.
- در سال 1984، کارمارکار از روش داخلی برای حل برنامه های خطی استفاده کرد و تجزیه و تحلیل ابتکاری خود را اضافه کرد.
LP ثابت کرده است که یک ابزار بسیار قدرتمند هم برای مدل‌سازی مسائل دنیای واقعی و هم به عنوان یک نظریه ریاضی گسترده است. با این حال، بسیاری از مسائل بهینه سازی جالب غیر خطی هستند.
در این مورد چه باید کرد؟ مطالعه چنین مسائلی شامل ترکیبی متنوع از جبر خطی، محاسبات چند متغیره، تحلیل عددی و روش‌های محاسباتی است. دانشمندان در حال توسعه الگوریتم‌های محاسباتی هستند، از جمله روش‌های نقطه داخلی برای برنامه‌ریزی خطی، هندسه، تجزیه و تحلیل مجموعه‌ها و توابع محدب، و مطالعه مسائل ساختاری خاص مانند برنامه‌نویسی درجه دوم.
بهینه سازی غیرخطی درک اساسی از تحلیل ریاضی را فراهم می کند و به طور گسترده در زمینه های مختلف مانند مهندسی، تحلیل رگرسیون، مدیریت منابع، اکتشاف ژئوفیزیک و اقتصاد استفاده می شود.
طبقه بندی مسائل بهینه سازی
گام مهمی درفرآیند بهینه‌سازی طبقه‌بندی مدل‌ها است، زیرا الگوریتم‌های راه‌حل آنها با نوع خاصی تطبیق داده می‌شوند.
1. مشکلات بهینه سازی گسسته و پیوسته. برخی از مدل‌ها تنها زمانی معنا پیدا می‌کنند که متغیرها مقادیری را از زیر مجموعه‌ای از اعداد صحیح بگیرند. برخی دیگر حاوی داده هایی هستند که می توانند هر ارزش واقعی را به خود بگیرند. حل آنها معمولا راحت تر است. بهبود الگوریتم‌ها، همراه با پیشرفت‌های فناوری رایانه، اندازه و پیچیدگی یک مسئله بهینه‌سازی برنامه‌نویسی خطی را به‌طور چشمگیری افزایش داده است.
2. بهینه سازی نامحدود و محدود. تفاوت مهم دیگر وظایفی است که در آن هیچ محدودیتی برای متغیرها وجود ندارد. این می تواند به طور گسترده ای از برآوردگرهای ساده تا سیستم های برابری و نابرابری که روابط پیچیده بین داده ها را مدل می کند، متغیر باشد. چنین مسائل بهینه‌سازی را می‌توان با توجه به ماهیت توابع (خطی و غیرخطی، محدب و صاف، قابل تمایز و غیرمتمایز) طبقه‌بندی کرد.
3. وظایف امکان سنجی هدف آنها یافتن مقادیر متغیری است که محدودیت های مدل را بدون هیچ هدف بهینه سازی خاصی برآورده می کند.
4. وظایف مکمل آنها به طور گسترده ای در فناوری و اقتصاد استفاده می شوند. هدف یافتن راه حلی است که شرایط مکمل را برآورده کند. در عمل، وظایف با چندین هدف، اغلب به اهداف واحد تبدیل می‌شوند.
5. بهینه سازی قطعی در مقابل تصادفی بهینه سازی قطعی فرض می کند که داده ها برایتکالیف کاملا دقیق هستند با این حال، در مورد بسیاری از موضوعات موضوعی به دلایل متعددی نمی توان آنها را شناخت.
اولی مربوط به یک خطای اندازه گیری ساده است. دلیل دوم اساسی تر است. این در این واقعیت نهفته است که برخی از داده ها اطلاعات مربوط به آینده را نشان می دهند، به عنوان مثال، تقاضا برای یک محصول یا قیمت برای یک دوره زمانی آینده. هنگام بهینه سازی تحت شرایط بهینه سازی تصادفی، عدم قطعیت در مدل گنجانده شده است.
اجزای اصلی
تابع هدف تابعی است که باید کمینه یا حداکثر شود. اکثر انواع مسائل بهینه سازی یک تابع هدف دارند. اگر نه، اغلب می‌توان آنها را دوباره فرمول‌بندی کرد تا کار کنند.
دو استثنا برای این قانون:
1. وظیفه جستجوی هدف در بیشتر برنامه‌های تجاری، مدیر می‌خواهد به یک هدف خاص دست یابد و در عین حال محدودیت‌های مدل را برآورده کند. کاربر بخصوص نمی خواهد چیزی را بهینه کند، بنابراین تعریف یک تابع هدف منطقی نیست. این نوع معمولاً به عنوان یک مشکل رضایت‌پذیری نامیده می‌شود.
2. بسیاری از ویژگی های عینی. اغلب، یک کاربر دوست دارد چندین هدف مختلف را به طور همزمان بهینه کند. آنها معمولاً ناسازگار هستند. متغیرهایی که برای یک هدف بهینه می‌شوند ممکن است برای دیگران بهترین نباشند.
انواع مؤلفه:
- ورودی کنترل شده مجموعه ای از متغیرهای تصمیم گیری است که بر مقدار یک تابع هدف تأثیر می گذارد. در یک کار تولید، متغیرها ممکن است شامل توزیع منابع مختلف موجود یا نیروی کار مورد نیاز باشدهر اقدام.
- محدودیت ها روابط بین متغیرهای تصمیم گیری و پارامترها هستند. برای یک مشکل تولید، صرف زمان زیادی برای هر فعالیتی منطقی نیست، بنابراین همه متغیرهای "موقت" را محدود کنید.
- راه حل های ممکن و بهینه. مقدار تصمیم برای متغیرهایی که تحت آن همه محدودیت ها برآورده می شوند، رضایت پذیر نامیده می شود. اکثر الگوریتم ها ابتدا آن را پیدا می کنند، سپس سعی می کنند آن را بهبود بخشند. در نهایت، آنها متغیرها را تغییر می دهند تا از یک راه حل عملی به راه حل دیگر حرکت کنند. این فرآیند تا زمانی که تابع هدف به حداکثر یا حداقل خود برسد تکرار می شود. این نتیجه راه حل بهینه نامیده می شود.
الگوریتم های مسائل بهینه سازی توسعه یافته برای برنامه های ریاضی زیر به طور گسترده استفاده می شود:
- محدب.
- قابل جدا شدن.
- مربع.
- هندسی.
Google Linear Solvers
بهینه سازی یا برنامه نویسی خطی نامی است که به فرآیند محاسباتی حل بهینه یک مسئله داده می شود. به عنوان مجموعه‌ای از روابط خطی که در بسیاری از رشته‌های علمی و مهندسی به وجود می‌آیند، مدل‌سازی می‌شود.
Google سه راه برای حل مسائل بهینه سازی خطی ارائه می دهد:
- کتابخانه منبع باز Glop.
- افزونه بهینه سازی خطی برای Google Sheets.
- سرویس بهینه سازی خطی در اسکریپت Google Apps.
Glop در Google تعبیه شده استحل کننده خطی به صورت متن باز موجود است. می‌توانید از طریق روکش حل‌کننده خطی OR-Tools، که پوششی برای Glop است، به Glop دسترسی پیدا کنید.
ماژول بهینه‌سازی خطی برای Google Sheets به شما امکان می‌دهد با وارد کردن داده‌ها در یک صفحه‌گسترده، یک بیانیه خطی از مسئله بهینه‌سازی را انجام دهید.
برنامه نویسی درجه دوم
پلتفرم Premium Solver از یک نسخه توسعه یافته LP/Quadratic از روش Simplex با محدودیت های پردازش مشکل LP و QP تا ۲۰۰۰ متغیر تصمیم استفاده می کند.
SQP حل کننده برای مسائل در مقیاس بزرگ از پیاده سازی مدرن روش مجموعه فعال با پراکندگی برای حل مسائل برنامه نویسی درجه دوم (QP) استفاده می کند. موتور حل‌کننده XPRESS از گسترش طبیعی روش «نقطه داخلی» یا نیوتن برای حل مشکلات QP استفاده می‌کند.
MOSEK Solver از روش‌های تعبیه‌شده «نقطه داخلی» و دوگانه خودکار استفاده می‌کند. این به ویژه برای مشکلات QP با جفت آزادانه مؤثر است. همچنین می تواند مشکلات مقیاس درجه دوم محدودیت (QCP) و برنامه نویسی مخروط مرتبه دوم (SOCP) را حل کند.
محاسبات چندعملیاتی
آنها با استفاده از ویژگی های مایکروسافت آفیس، به عنوان مثال، حل مسائل بهینه سازی در اکسل، کاملاً با موفقیت استفاده می شوند.
در جدول بالا، نمادها عبارتند از:
- K1 - K6 - مشتریانی که نیاز به ارائه کالا دارند.
- S1 - S6 سایت های تولیدی بالقوه ای هستند که می توانند برای این کار ساخته شوند. می توان ایجاد کرد1، 2، 3، 4، 5 یا همه 6 مکان.
هزینه های ثابتی برای هر تسهیلات ذکر شده در ستون I (اصلاح) وجود دارد.
اگر مکان چیزی را تغییر ندهد، حساب نخواهد شد. سپس هیچ هزینه ثابتی وجود نخواهد داشت.
مکان های بالقوه را برای دریافت کمترین هزینه شناسایی کنید.
در این شرایط مکان یا مشخص است یا خیر. این دو حالت عبارتند از: "درست - نادرست" یا "1 - 0". شش حالت برای شش مکان وجود دارد، به عنوان مثال، 000001 فقط روی ششم، 111111 روی همه تنظیم شده است.
در سیستم اعداد باینری، دقیقاً 63 گزینه مختلف از 000001 (1) تا 111111 (63) وجود دارد.
L2-L64 اکنون باید {=MULTIPLE OPERATION (K1)} را بخواند، اینها نتایج همه راه حل های جایگزین هستند. سپس مقدار حداقل=Min (L) و جایگزین مربوطه INDEX (K) است.
CPLEX برنامه نویسی عدد صحیح
گاهی اوقات یک رابطه خطی برای رسیدن به قلب یک مشکل تجاری کافی نیست. این امر به ویژه زمانی صادق است که تصمیم گیری ها شامل انتخاب های گسسته باشد، مانند باز کردن یا عدم افتتاح انبار در یک مکان خاص. در این مواقع باید از برنامه نویسی عدد صحیح استفاده کرد.
اگر مشکل شامل هر دو انتخاب گسسته و پیوسته باشد، یک برنامه عدد صحیح مختلط است. می‌تواند مشکلات درجه دوم خطی و محدب و محدودیت‌های مرتبه دوم مشابهی داشته باشد.
برنامه های عدد صحیح بسیار پیچیده تر از برنامه های خطی هستند، اما کاربردهای تجاری مهمی دارند. نرم افزارنرم افزار CPLEX از روش های پیچیده ریاضی برای حل مسائل اعداد صحیح استفاده می کند. روش‌های او شامل جستجوی سیستماتیک برای ترکیب‌های ممکن از متغیرهای گسسته با استفاده از نرم‌افزارهای خطی یا درجه دوم برای محاسبه مرزهای مقدار راه‌حل بهینه است.
آنها همچنین از LP و دیگر روش‌های حل مسئله بهینه‌سازی برای محاسبه محدودیت‌ها استفاده می‌کنند.
حل کننده استاندارد Microsoft Excel
این فناوری از پیاده سازی اولیه روش اصلی Simplex برای حل مسائل LP استفاده می کند. به 200 متغیر محدود شده است. "Premium Solver" از یک روش ساده اولیه بهبود یافته با کرانهای دو طرفه برای متغیرها استفاده می کند. پلت فرم Premium Solver از یک نسخه توسعه یافته از LP/Quadratic Simplex Solver برای حل یک مشکل بهینه سازی با حداکثر 2000 متغیر تصمیم استفاده می کند.
LP در مقیاس بزرگ برای پلتفرم Premium Solver یک پیاده سازی پیشرفته از روش ساده و دوگانه ساده را اعمال می کند که از پراکندگی در مدل LP برای صرفه جویی در زمان و حافظه، استراتژی های پیشرفته برای به روز رسانی و استفاده می کند. ماتریس های refactoring، قیمت گذاری و چرخش های چندگانه و جزئی، و برای غلبه بر انحطاط. این موتور در سه نسخه موجود است (قابلیت کنترل تا 8000، 32000 یا متغیرها و محدودیت های نامحدود).
حل‌کننده MOSEK شامل سیمپلکس اولیه و دوگانه است، روشی که از پراکندگی نیز استفاده می‌کند و از استراتژی‌های پیشرفته برای به‌روزرسانی ماتریس و «بازسازی» استفاده می‌کند. مشکلات اندازه نامحدود را حل می کندروی مسائل برنامه ریزی خطی با میلیون ها متغیر تصمیم آزمایش شد.
نمونه گام به گام در EXCEL
برای تعریف مدل مشکل بهینه سازی در اکسل، مراحل زیر را انجام دهید:
- داده های مشکل را در یک صفحه گسترده به شکل منطقی سازماندهی کنید.
- یک سلول برای ذخیره هر متغیر انتخاب کنید.
- فرمولی برای محاسبه مدل ریاضی هدف مسئله بهینه سازی در سلول ایجاد کنید.
- فرمولهایی برای محاسبه سمت چپ هر محدودیت ایجاد کنید.
- از دیالوگ ها در اکسل استفاده کنید تا به Solver در مورد متغیرهای تصمیم، اهداف، محدودیت ها و محدوده های مورد نظر در آن پارامترها بگویید.
- "Solver" را برای یافتن راه حل بهینه اجرا کنید.
- یک برگه Excel ایجاد کنید.
- داده های مسئله را در اکسل سازماندهی کنید که در آن فرمول تابع هدف و محدودیت محاسبه می شود.
در جدول بالا، سلول‌های B4، C4، D4، و E4 برای نمایش متغیرهای تصمیم X 1، X 2، X 3، و X 4 رزرو شده‌اند. مثال‌های تصمیم:
- مدل ترکیب محصول (450 دلار، 1150 دلار، 800 دلار و 400 دلار سود برای هر محصول) به ترتیب در سلول های B5، C5، D5 و E5 وارد شد. این اجازه می دهد تا هدف در F5=B5B4 + C5C4 + D5D4 + E5E4 یا F5 محاسبه شود:=SUMPRODUCT (B5: E5، B4: E4).
- در B8 مقدار منابع مورد نیاز برای تولید هر نوع محصول را وارد کنید.
- فرمول F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- این را کپی کنیدفرمول در F9 علائم دلار در $B$4:$E$4 نشان می دهد که این محدوده سلول ثابت می ماند.
- در G8 مقدار منابع موجود از هر نوع را مطابق با مقادیر محدودیت های سمت راست وارد کنید. این به شما امکان می دهد آنها را به این صورت بیان کنید: F11<=G8: G11.
- این معادل چهار حد است F8<=G8, F9 <=G9, F10 <=G10 و F11=0
زمینه های کاربرد عملی روش
بهینه سازی خطی کاربردهای عملی زیادی به عنوان مثالی از یک مسئله بهینه سازی دارد:
یک شرکت می تواند چندین محصول را با حاشیه مشارکت مشخص تولید کند. تولید یک واحد از هر کالا به مقدار مشخصی از منابع محدود نیاز دارد. وظیفه ایجاد یک برنامه تولید برای تعیین میزان تولید هر محصول است تا سود شرکت بدون نقض محدودیت‌های منابع به حداکثر برسد.
مشکلات اختلاط راه حلی برای مشکلات بهینه سازی مربوط به ترکیب مواد در محصول نهایی است. نمونه ای از این مسئله مسئله رژیم غذایی است که توسط جورج دانزیگ در سال 1947 مورد مطالعه قرار گرفت. تعدادی مواد اولیه مانند جو، گوشت خوک و روغن آفتابگردان به همراه محتوای غذایی آنها مانند پروتئین، چربی، ویتامین A و قیمت هر کیلوگرم آن ارائه می شود. چالش این است که یک یا چند محصول نهایی از مواد خام با کمترین هزینه ممکن ترکیب شود و در عین حال حداقل و حداکثر محدودیت برای ارزش غذایی آنها رعایت شود.
یک کاربرد کلاسیک مسئله بهینه سازی خطی، تعیین مسیریابی برای نیازها استترافیک در شبکه های مخابراتی یا حمل و نقل. در عین حال، جریان ها باید از طریق شبکه به گونه ای هدایت شوند که تمام الزامات ترافیک بدون نقض شرایط پهنای باند برآورده شوند.
در تئوری ریاضی، از بهینه سازی خطی می توان برای محاسبه استراتژی های بهینه در بازی های حاصل جمع صفر برای دو نفر استفاده کرد. در این حالت توزیع احتمال برای هر شرکت کننده محاسبه می شود که ضریب اختلاط تصادفی استراتژی های وی است.
هیچ فرآیند کسب و کار موفقی در جهان بدون بهینه سازی امکان پذیر نیست. الگوریتم های بهینه سازی زیادی وجود دارد. برخی از روش ها فقط برای انواع خاصی از مشکلات مناسب هستند. مهم است که بتوانید ویژگی های آنها را بشناسید و روش راه حل مناسب را انتخاب کنید.
