درس بهینه سازی خطی (تحقیق در عملیات) به عنوان یکی از دروس تخصصی(اصلی) رشته ریاضیات و کاربردها معمولا در 4 واحد درسی ارائه می‌شود و گذراندن این درس نیز برای دانشجویان این رشته اجباری می‌باشد. پیش‌نیاز درس بهینه سازی خطی یا همان تحقیق در عملیات برای رشته ریاضیات و کاربردها طبق جدیدترین چارت اعلامی درس مبانی ماتریس‌ها و جبر خطی است.
هدف از ارائه درس بهینه سازی خطی یا تحقیق در عملیات به طور کلی این است که دانشجو توانایی مدل‌سازی مسائل مختلف بهینه سازی را بدست آورده و روش‌های حل مسائل برنامه ریزی خطی را بیاموزد. همچنین آشنایی با قضایا و مفاهیم ریاضی که این روش‌ها بر اساس آن‌ها بنا شده اند از اهداف این درس است. در انتهای این درس دانشجو باید بتواند یک مساله متوسط بهینه سازی را مدل‌سازی، تحلیل و با یک نرم افزار حل نماید.
همچنین مهم‌ترین مباحث و سرفصل‌هایی که در این درس بیان می‌شود را میتوان: آشنایی با زمینه های تحقیق در عملیات، مدل‌سازی مسائل بهینه سازی، مفاهیم پایه ای مرتبط با برنامه ریزی خطی شامل روش‌های ترسیمی، سیمپلکس اولیه و دوگان، دوفازی و M بزرگ، دوگانی، تحلیل حساسیت و قضایای مرتبط با آن‌ها در نظر گرفت. همچنین قضایا و روش‌های حل مسائل حمل ونقل ساده و مرکب، مدل سازی مساله تخصیص و روش حل آن، آشنایی با برنامه ریزی عدد صحیح و روش‌های شاخه و کران و صفحات برشی و معرفی یک نرم افزار یا زبان مدل سازی جهت حل مسائل بهینه سازی مانند CPLEX ، GAMS، LINGO نیز از دیگر مباحث مهم و کاربردی است که در درس بهینه سازی خطی بیان خواهد شد.
همچنین کاربران گرامی سایت آلفا مث و خوانندگان این مقاله می‌توانند اطلاعات بسیار کامل، جامع و به‌روزی را در ارتباط با رشته ریاضیات و کاربردها در مقاله اختصاصی منتشرشده در سایت ما با عنوان صفرتاصد رشته ریاضیات و کاربردها بررسی و مطالعه نمایند.
بررسی مهم‌ترین سرفصل‌ها و مباحث درس بهینه سازی خطی(تحقیق در عملیات)
اکنون با یکدیگر مهم‌ترین و چالشی ترین سرفصل‌ها و موضوعاتی که در درس بهینه سازی خطی بیان می‌شود را بررسی و توضیح کوتاهی درباره هر کدام خواهیم داد. همچنین در انتها و هر قسمتی که نیاز باشد مفیدترین و کامل‌ترین جزوات و فیلم‌های آموزشی را نیز برای کاربران گرامی سایت آلفا مث معرفی خواهیم کرد.
برنامه ریزی خطی و مدل‌سازی ریاضی
برنامه ریزی خطی در تعریف کلی یعنی ایجاد یک مدل ریاضی برای جستجو و انتخاب بهترین برنامه برای انجام کار یا یافتن موثرترین روش‌های اختصاص منابع که هدف تمامی این موضوعات حول یک هدف خاص مانند ماکزیمم کردن سود یا مینیمم کردن هزینه که وابسته به نوع مسئله و هدف آن می‌تواند متفاوت باشد، تعریف خواهد شد. از آنجایی که تمامی روابط ریاضی موجود در این نوع مدل‌ها یا مسائل از نوع درجه یک هستند، در نتیجه مدل را خطی می‌گوییم.
مهم‌ترین قسمت‌های تشکیل دهنده یک مدل برنامه ریزی خطی همراه با تعاریف
حالا به معرفی مهم‌ترین بخش‌هایی که یک مدل برنامه ریزی خطی از آن‌ها تشکیل شده خواهیم پرداخت و تعاریف مرتبط با هر کدام را نیز به طور خلاصه برای کاربران گرامی بیان می‌کنیم:
- تابع هدف (Objective Function): تابع ریاضی است که از متغیرهای تصمیم تشکیل شده و بیانگر هدف مسئله است. این تابع در واقع نشان دهنده خواسته‌های تصمیم گیرنده مانند حداکثر کردن سود یا حداقل کردن هزینه می‌باشد. تابع هدف در راس و بالاترین قسمت و سطح یک مدل و از نوع MAX یا MIN خواهد بود.
- محدودیت‌ها یا قیود (Constraint): عبارت است از یک دستگاه معادله یا نامعادله متشکل از متغیرهای تصمیم که محدودیت‌های تصمیم گیرنده را برای دستیابی به هدف مدل بیان می‌کند. به بیانگر دیگر قید و بندها و مقررات در دنیای واقعی و کارها مثل تعداد ساعات کار، تعداد نفرات و نیروی انسانی و محدودیت‌های استفاده از ابزارآلات و منابع و … همان محدودیت‌ها یا قیود یک مسئله خواهند بود.
- متغیرهای تصمیم(Decision Variables): متغیرهای مجهولی هستند که باید مقدار آن‌ها تعیین شود و از یکدیگر مستقل بوده و بهترین آن را برای حل یک مسئله برنامه ریزی خطی انتخاب می‌کنیم. این متغیرها معمولا سطح فعالیت یک شرکت یا محیط کاری را نشان داده و در انتهای مدل مشخص می‌شوند و می‌توانند منفی، مثبت و یا آزاد در علامت باشند.
- متغیرهای مستقل(Independent Variables): مقدار این متغیرها را تصمیم گیرنده بعد از حل تعیین می‌کند.
- متغیرهای وابسته(Dependent Variables): این متغیرها معمولا در تابع هدف بیانگر مفاهیم اقتصادی نظیر سود، هزینه، درآمد، تولید، فروش، مسافت و زمان و … است.
فرم کلی(شکل متعارفی) یک مسئله برنامه ریزی خطی
اکنون ابتدا فرم کلی(شکل متعارفی) یک مسئله برنامه ریزی خطی را و سپس گسترده این فرمول را می‌توانید به ترتیب در تصاویر زیر مشاهده و بررسی فرمایید:
و حالا شکل گسترده فرم کلی(شکل متعارفی) یک مسئله برنامه ریزی خطی:
همچنین در تصویر زیر نیز می‌توانید تا تفاوت‌های شکل استاندارد و شکل متعارفی یک مسئله برنامه ریزی خطی را مشاهده فرمایید:
مفروضات مدل‌های برنامه ریزی خطی:
حالا نوبت آن رسیده است تا مهم‌ترین مفروضات موجود برای یک مسئله یا مدل برنامه ریزی خطی را با یکدیگر بررسی و مشاهده نماییم:
اصل تناسب: فرض تناسب به این معناست که متغیرهای مدل در تابع هدف و محدودیت‌های مسئله از روابط غیرخطی پیروی نکنند و نسبت سهم هر متغیر متناسب با تغییر در میزان آن متغیر باشد. به عنوان مثال اگر تولید محصولات دو برابر شد آنگاه سود آن نیز باید دو برابر گردد. به مثال زیر دقت کنید:
اصل بخش‌پذیری: متغیرهای تصمیم توانایی انتخاب هر مقدار از اعداد حقیقی را داشته باشند. به طور مثال میزان پارچه تولیدی، راه ساخته شده بر حسب کیلومتر و مسافت طی شده نمونه‌هایی از مصادیق متغیرهای تصمیم پیوسته هستند در حالی که تصمیم گیری درباره تعداد سیلوهای مورد نیاز برای کار و خرید تعداد سهام یک شرکت متغیرهای عدد صحیح می‌باشند.
اصل جمع‌پذیری: روابط ریاضی بین متغیرها در تابع هدف و چه در محدودیت‌ها به صورت جمع جبری بایستی بیان شود. این اصل ضمانت می‌کند که هزینه کل(سود کل) برابر با مجموع تک‌تک هزینه‌ها(سودها) می‌باشد.
اصل معین(قطعی) بودن: اطلاعات و متغیرهای مدل معین و قطعی و غیراحتمالی باشند و به قولی تغییر نکرده و ثابت باشند.
معروف‌ترین مسائل برنامه ریزی خطی:
مشهورترین و معروف‌ترین مدل‌سازی هایی که برای مسائل برنامه ریزی خطی شده است عبارت است از: مسائل مربوط به حمل و نقل، مسائل مرتبط با کشاورزی و دامداری، مسائل مربوط به شرکت‌های بازرگانی یا ساختمانی، مسائل در حوزه صنعتی، مسائل ضایعات برش، مسئله کوله پشتی، مسائل زمان بندی، مسائل سرمایه گذاری، مسائل کنترل بهینه و مسائل امتزاج(ترکیب کردن چند نوع مواد برای تولید یک کالا).
حل مسائل برنامه ریزی خطی
مسائل برنامه ریزی خطی به طور کلی با دو روش هندسی یا ترسیمی و محاسباتی یا همان سیمپلکس حل می‌شوند که اکنون به طور دقیق هر کدام از روش‌های موجود را به طور جداگانه و با دقت بررسی خواهیم کرد:
روش هندسی یا ترسیمی
این روش به مدل‌هایی محدود می‌شود که حداکثر دارای سه متغیر متصمیم یک اندیسه هستند و البته کاربرد بیشتر آن برای حل مدل‌های خطی دو متغیره خواهد بود. روش ترسیمی به طور کلی از دو بخش تعیین منطقه موجه و پیدا کردن جواب بهینه تشکیل می‌شود.
مراحل حل یک مدل به روش ترسیمی:
1. تبدیل نامعادلات به معادلات: ابتدا مدل را بررسی کرده و آن دسته از محدودیت‌هایی که به صورت نامعادله هستند را به معادله تبدیل می‌کنیم.
2. رسم محدودیت‌ها: سپس برای هر کدام از معادلات دو نقطه دلخواه(بهتر است که یکبار X1 را صفر و بار دیگر X2 صفر فرض شود) را پیدا کرده و محدودیت را در نمودار رسم می‌نماییم.
3. تعیین فضای جواب: اکنون با توجه به کوچکترمساوی یا بزرگترمساوی بودن علامت نامعادلات طبق شکل زیر فضای جواب هر کدام را مشخص می‌کنیم. همچنین برای محدودیت‌هایی که از نوع مساوی هستند صرفا تمام آن خط در محدوده‌ی مجاز(به عنوان مثال اگر هم X1 و هم X2 بزرگتر مساوی صفر باشند پس محدوده مجاز ناحیه اول نمودار خواهد بود و تمامی بررسی‌ها باید در این محدوده انجام شود) به عنوان فضای جواب آن محدودیت در نظر گرفته خواهد شد.
4. تعیین فضای مشترک: بعد از تعیین فضای جواب برای هر کدام از محدودیت‌ها، فضای جواب مشترک میان تمامی محدودیت‌ها را به عنوان منطقه موجه یا فضای شدنی مسئله در نظر خواهیم گرفت. که ممکن است هر کدام از حالت‌های زیر اتفاق بیفتد:
5. بدست آوردن جواب بهینه در صورت وجود: در مرحله آخر و در صورت وجود جواب بهینه و برقراری شرایط برای جواب بهینه، بر اساس رفتار تابع هدف می‌توانیم از دو روش آزمون و خطا یا بررسی نقاط گوشه‌ای جواب بهینه را بدست آوریم.
الف) روش آزمون و خطا: در این روش می‌توانیم تابع هدف را به عنوان یک خط(یکبار X1 را صفر و بار دیگر X2 را صفر فرض می‌کنیم) رسم کرده و حالا اگر مسئله از نوع MAX سازی بود در جهت رشد فضای جواب(منطقه موجه) ولی اگر مسئله از نوع MIN سازی بود در جهت کاهش فضای جواب(منطقه موجه) خط تابع هدف را حرکت می‌دهیم و آخرین نقطه(یا آخرین نقاط به صورت تعدادی نقطه که یک خط را تشکیل می‌دهند) که خط تابع را قبل از خروج از فضای جواب لمس کند به عنوان جواب بهینه ما خواهد بود.
همچنین میتوان ضرایب تابع هدف را به عنوان یک نقطه نیز در نظر گرفت و سپس اگر مسئله از نوع MAX سازی بود در جهت نیمساز همان ربع و اگر مسئله از نوع MIN سازی بود در خلاف جهت نیمساز همان ربع حرکت کرده تا جواب بهینه بدست آید.
ب) روش بررسی نقاط گوشه‌ای: در این روش تمامی نقاط گوشه‌ای بدست آمده در فضای جواب یا ناحیه شدنی را یکی یکی در معادله تابع هدف قرار می‌دهیم و اگر مسئله از نوع MAX سازی بود، گوشه‌ای که بیشترین جواب را برای تابع هدف به ارمغان آورد جواب بهینه مسئله است اما اگر مسئله از نوع MIN سازی بود، نقطه گوشه‌ای با کمترین مقدار در تابع هدف جواب بهینه مسئله ما می‌باشد.
در شکل زیر اگر معادله تابع هدف به صورت 2X1 + 3X2 باشد، به صورت زیر نقاط گوشه‌ای را در تابع هدف جایگذاری می‌کنند:
بررسی حالت‌های خاص موجود در مسائل برنامه ریزی خطی
چهار حالت خاص ممکن است در مسائل برنامه ریزی خطی اتفاق بیفتد که اکنون به تفکیک هر کدام را بررسی خواهیم کرد:
1. حالت اول: ناحیه جواب بی‌کران
هرگاه فضای جواب یک مسئله برنامه ریزی خطی از یک سمت به محدودیت یا محدودیت‌های ختم نشود و به قولی تا بی‌نهایت ادامه داشته باشد، آنگاه ناحیه جواب بی‌کران خواهد بود. در این حالت ممکن است مسئله جواب داشته باشد یا جواب نداشته باشد که بستگی به تابع هدف دارد.
برای مثال در شکل زیر می‌توانید یک نمونه از فضای جواب به صورت بی‌کران را مشاهده نمایید. در این مثال تابع هدف از نوع MIN سازی بوده است، پس بنابراین در جهت کاهش مقدار فضای جواب حرکت کرده و همانطور که مشخص است نقطه A با مقدار Z برابر با عدد 24 جواب نهایی خواهد بود و میتوان گفت که مسئله با وجود داشتن ناحیه شدنی بی‌کران، جواب بهینه دارد.
در همین مثال اگر تابع هدف از نوع MAX سازی بود، در نتیجه این بار می‌بایست در جهت افزایش مقدار فضای جواب حرکت کرده و به دلیل اینکه فضای جواب برای افزایش مقادیر آن بی‌کران است، دیگر مسئله هیچ جوابی به دنبال نخواهد داشت.
2. حالت دوم: ناحیه شدنی فاقد جواب یا فاقد ناحیه موجه
این حالت در دنیای واقعی معمولا به دلیل اشتباه بودن مدل اتفاق می‌افتد. در روش حل ترسیمی یا هندسی هرگاه نتوانیم برای مسئله فضا یا ناحیه جواب مشترکی بین محدودیت‌ها پیدا کنیم آنگاه مسئله فاقد ناحیه موجه و در نتیجه فاقد جواب خواهد بود.
3. حالت سوم: جواب بهینه چندگانه
هرگاه در یک مدل برنامه ریزی خطی، معادله یکی از محدودیت‌ها با معادله تابع هدف موازی باشد، مسئله می‌تواند دارای جواب بهینه چندگانه باشد. همچنین به لحاظ هندسی نیز جواب بهینه مسئله اگر به صورت یک خط شامل مجموعه‌ای از نقاط با مقادیر نهایی یکسان در تابع هدف آنگاه حالت جواب بهینه چندگانه را برای مسئله خواهیم داشت.
در این شکل همانطور که مشخص است چون تابع هدف مسئله MAX سازی است بنابراین با حرکت در جهت افزایش مقدار فضای جواب به خط CD برمی‌خوریم. در این مثال مقدار هر نقطه از خط CD را که در تابع هدف قرار دهیم مقدار یکسانی حاصل خواهد شد و میتوان نتیجه گرفت که مسئله جواب بهینه چندگانه دارد.
4. حالت چهارم: جواب تبهگن
اگر در یک مسئله یک نقطه گوشه‌ای در فضای جواب از برخورد بیش از دو محدودیت به وجود آمده باشد(چه محدودیت موثر باشد و چه محدودیت زائد باشد) آنگاه مسئله دارای جواب بهینه تبهگن خواهد بود و به آن نقطه گوشه‌ای نقطه تباهیده می‌گویند.
انواع محدودیت‌ها در مدل‌های برنامه ریزی خطی
محدودیت‌ها در یک مسئله ممکن است به دو صورت موثر و زائد باشند. محدودیت موثر محدودیتی است که در تشکیل ناحیه و فضای جواب تاثیرگذار بوده و اضافه کردن محدودیت موثر جدید به مدل، موجب کاهش منطقه موجه و حذف یک محدودیت موثر موجب افزایش ناحیه موجه خواهد شد.
در حالی که محدودیت زائد مسئله تاثیری در ایجاد فضا یا ناحیه جواب ندارد و اضافه کردن یا حذف کردن آن نیز موجب تغییر در فضای شدنی نخواهد شد.
همچنین بیان این نکات نیز خالی از لطف نیست که اگر:
- یک محدودیت را برداریم و حذف کنیم: فضای جواب کوچکتر نخواهد شد و جواب مسئله نیز بزرگتر یا به قولی بهتر نمی‌شود.
- حالا اگر یک متغیر را اضافه کنیم: یک بعد به مسئله اضافه می‌شود و فضا بزرگتر خواهد شد و جواب بهینه نیز بدتر نخواهد شد.
روش سیمپلکس
در حل مسائل به روش سیمپلکس، از مبدا مختصات شروع کرده و از یک گوشه به گوشه‌ای بهتر حرکت می‌کنیم تا اینکه بهترین گوشه پیدا شود. این روش برای حل مسائل بهینه سازی خطی با متغیرهای یک اندیسه از یک نوع هستند قابل استفاده است و برای حل یک مسئله به این روش باید طبق مراحل زیر پیش برویم.
قبل از بررسی مراحل حل می‌توانید در تصویر زیر تابلو سیمپلکس را مشاهده نمایید:
مراحل حل مسائل به روش سیمپلکس
1. ابتدا باید مسئله را استاندارد سازی کنیم:
الف) تابع هدف مسئله بهتر است از نوع MAX سازی باشد، حالا اگر تابع هدف مسئله از نوع MIN سازی بود می‌توانیم با ضرب یک منفی در طرفین معادله تابع هدف، آن را از حالت MIN سازی به MAX سازی تبدیل کنیم.
البته می‌توانیم تا مسئله را با همان تابع هدف MIN سازی و بدون تبدیل نیز حل کنیم و فقط به جای وارد کردن منفی‌ترین مقدار به عنوان ورودی به تابلو سیمپلکس، می‌بایست مثبت‌ترین مقدار را به عنوان مقدار ورودی در نظر بگیریم.
ب)محدودیت‌های مدل را باید به فرم تساوی تبدیل نماییم:
برای این کار اگر محدودیت‌ها کوچکتر مساوی بودن باید به سمت چپ آن‌ها متغیر کمکی یا کمبود(S+) و اگر به فرم بزرگتر مساوی بودند باید متغیر کمکی یا مازاد(S-) را از سمت چپ همان محدودیت کم کنیم تا با این کارها محدودیت‌ها به فرم تساوی تبدیل شوند. این متغیرهای کمکی معمولا با نماد S نمایش داده می‌شوند و خودشان بزرگتر مساوی صفر هستند.
ج) مقادیر سمت راست تابع هدف را باید به سمت چپ منتقل کنیم و بعد از آن می‌توانیم تا جدول سیمپلکس را رسم کنیم که در تصاویر زیر می‌توانید تا نحوه جابه‌جایی مقادیر و اضافه کردن مقادیر کمکی را در مثال زیر مشاهده فرمایید:
همچنین در ابتدای حل مسئله دو شرط اساسی برای حل به روش سیمپلکس باید برقرار باشد:
اول آنکه ضریب متغیرهای اساسی(همان متغیرهای کمکی مثل S) در سطر تابع هدف می‌بایست صفر باشند.
دومین شرط نیز این است که متغیرهای اساسی در جدول سیمپلکس باید تشکیل یک ماتریس یکه دهند.
2. انتخاب متغیر ورودی:
متغیر ورودی برای یک مسئله با تابع هدف MAX سازی، منفی ترین مقدار بین ضرایب در سطر تابع هدف می‌باشد. که ستون مربوط به این متغیر را ستون لولا می‌نامند.
3. انتخاب متغیر خروجی:
متغیری که دارای حداقل(کمترین مقدار) حاصل تقسیم مقادیر سمت راست بر عناصر فقط مثبت(صفر و منفی را در نظر نمی‌گیریم) ستون لولا باشد. سطر مربوط به این متغیر را سطر لولا می‌گویند.
در تقاطع ستون لولا و سطر لولا در جدول سیمپلکس یک عدد مشاهده می‌شود که به آن عدد، عدد لولا گفته می‌شود.
تمامی اطلاعاتی که بررسی کردیم را می‌توانید اکنون در تصویر زیر که مربوط به مثال قبلی می‌باشد را مشاهده نمایید:
4. ایجاد کردن جداول مرحله بعد سیمپلکس:
پس از تعیین متغیرهای ورودی و خروجی، جداول بعدی سیمپلکس تا رسیدن به جدول بهینه نهایی طبق تصویر زیر مشخص خواهد شد. یک نمونه از جداول سیمپلکس را نیز می‌توانید در ارتباط با مثال قبلی مشاهده کنید:
5. رسیدن به جدول نهایی:
در سیمپلکس ما روند عبور از یک جدول به جدول بعدی را طبق مورد 4 تا جایی ادامه می‌دهیم به که به جدول نهایی که همان جدول بهینه ما باشد ادامه می‌دهیم. شرط بهینگی برای یک جدول در سیمپلکس(اگر تابع هدف MAX سازی بود) این است که در سطر تابع هدف، همه مقادیر در بازه متغیرها غیرمنفی باشد و عدد منفی برای آن‌ها در سطر تابع هدف مشاهده نشود و حالا جدول بهینه است. در تصویر زیر یک نمونه از جدول بهینه مربوط به مثال قبلی را نیز می‌توانید بررسی نمایید:
حالت‌های خاص در حل مسائل به روش سیمپلکس
همانطور که انواع حالت‌های خاص که در حل یک مدل برنامه ریزی خطی در روش روش ترسیمی ممکن بود اتفاق بیفتد را بررسی کردیم اکنون این حالت‌ها را نیز در جدول سیمپلکس بررسی می‌کنیم تا در صورت مشاهده آن‌ها اطلاعات کافی را در این زمینه دارا باشید.
1. جواب بهینه چندگانه:
هرگاه در تابلو یا جدول نهایی سیمپلکس ضریب متغیر غیراساسی(که در پایه در همان جدول حضور ندارد) در سطر صفرم(سطر تابع هدف) برابر صفر باشد یا تعداد صفرهای سطر تابع هدف از تعداد متغیرهای اساسی موجود در پایه بیشتر بود، آنگاه مسئله دارای جواب بهینه چندگانه است.
در شکل زیر و در سطر تابع هدف ضرایب متغیرهای غیراساسی X1 و X2 صفر هستند و هر کدام را که به عنوان ورودی انتخاب کنیم مقدار تابع هدف تغییری نخواهد کرد و طبق موارد بیان شده در این مثال جواب بهینه چندگانه اتفاق افتاده است.
2. فاقد ناحیه موجه یا فاقد جواب:
اگر در جدول نهایی حداقل یک متغیر کمکی(S یا R) در پایه باقی مانده بود که مقدار آن در ستون سمت راست(RHS) بزرگتر از صفر باشد، آنگاه مسئله فاقد جواب یا فاقد ناحیه موجه می‌باشد.
3. ناحیه جواب بی کران:
در مثال‌هایی که در تابلو آخر سیمپلکس(که الزاما بهینه هم نخواهند بود) امکان انتخاب متغیر ورود به پایه را داشته باشیم، اما هیچ متغیری نتواند از پایه خارج شود و متغیر خروجی بر اساس روشی که قبلا برای خروج یک متغیر از پایه بیان کردیم(یعنی ضرایب ستون لولا مثبت نیستند) نداشته باشیم؛ آنگاه مسئله دارای ناحیه جواب بی کران خواهد بود.
برای مثال در شکل زیر متغیر S1 شرایط ورود به پایه را دارد اما هیچ کدام از متغیرهای X1 و X2 شرایط خروج از پایه را ندارند و ناحیه جواب ما بی‌کران است.
4. جواب تبهگن:
اگر مقدار ستون سمت راست یکی از متغیرهای موجود در پایه برابر صفر باشد، آنگاه مسئله دارای جواب تبهگن است. همچنین باید توجه داشته باشیم که این تابلو الزاما تابلو نهایی جدول سیمپلکس ممکن است نباشد و در این صورت نقطه تبهگن موقت داریم، در حالی که اگر یک تابلو دیگر جلو برویم و به تابلو نهایی برسیم و همچنان نقطه تبهگن ایجاد شود آنگاه تبهگن دائم خواهیم داشت.
روش M بزرگ
برای حل کردن آن دسته از مدل‌هایی که دارای محدودیت‌های مساوی و یا بزرگتر مساوی هستند، روش M بزرگ را میتوان به کار برد.
از آن جایی که در این گونه مدل‌ها(مدل‌هایی که دارای محدودیت‌های مساوی و یا بزرگتر مساوی هستند) معمولا مبدا مختصات جز ناحیه موجه مدل قرار نمی‌گیرد، باید ناحیه موجه را بزرگ کنیم که این کار با استفاده از متغیر مصنوعی انجام می‌شود. در واقع این متفیر مصنوعی نه متغیر مازاد است و نه متغیر کمبود، بلکه متغیری است برای بزرگتر کردن ناحیه موجه برای قرار گرفتن مبدا مختصات در این ناحیه و این متغیر در اصل معنای فیزیکی و واقعی ندارد.
مراحل روش M بزرگ
حال به بررسی تک تک مراحل مورد نیاز در روش M بزرگ خواهیم پرداخت:
1. با استفاده از متغیرهای کمکی و مصنوعی S و R باید نامعادلات را به معادله تبدیل کنیم:
به این صورت که اگر محدودیت علامت کوچکترمساوی داشته باشد فقط کافی است متغیر S+ را به آن محدودیت اضافه کنیم.
اگر محدودیت بزرگترمساوی بود باید ابتدا متغیر S- از آن کم شده و سپس متغیر R+ اضافه گردد.
همچنین اگر محدودیت مساوی داشتیم فقط کافی است متغیر R+ به محدودیت اضافه شود.
2. جریمه کردن تابع هدف:
برای جلوگیری از قرار گرفتن جواب بهینه روی یکی از نقاط گوشه منطقه موجه ناشی از اضافه شدن متغیر مصنوعی باید جریمه ای معادل M واحد بزرگ(M یک عدد بسیار بزرگ و مثبت است) به متغیر مصنوعی R در تابع هدف تعلق می‌گیرد به این صورت که:
اگر تابع هدف از نوع MAX سازی بود باید به صورت MR- به تابع هدف اضافه شود ولی اگر تابع هدف از نوع MIN سازی بود باید MR+ به تابع هدف اضافه گردد. سپس ضرایب تابع هدف را همچون روش سیمپلکس باید به سمت چپ منتقل نماییم:
3. حل جدول‌های روش M بزرگ:
همچنین در اولین جدول متغیرهای کمکی مثبت(S+) و متغیرهای مصنوعی(R) در پایه هستند و اگر شرط یکه بودن برقرار نبود باید برقرار شود. سپس می‌بایست تا ابتدا ضرایب M موجود در تابع هدف با روش سطری مقدماتی صفر شود، و ادامه مدل با روش سیمپلکس معمولی حل شود. حالا اگر در جدول نهایی مقدار متغیر مصنوعی صفر شد و در پایه نبود مدل دارای جواب بهینه و نقطه موجه است اما اگر مقدار متغیر مصنوعی صفر نشد مدل فاقد جواب است.
روش دو فازی یا دو مرحله‌ای
این روش هم برای مدل‌هایی که دارای محدودیت‌های مساوی و یا بزرگتر مساوی هستند، استفاده می‌شود.
مراحل روش دوفازی یا دو مرحله‌ای:
حال مراحل این روش را با هم بررسی خواهیم کرد و نکات آن را بیان می‌نماییم:
1. ابتدا باید شبیه به مرحله اول روش M بزرگ، نامعادلات را با توجه به علامتی که دارند به معادله تبدیل کنیم.
2. سپس در مرحله بعدی جواب موجه ابتدایی برای مدل با استفاده از تشکیل تابع هدف مصنوعی پیدا می‌کنیم. به این صورت که مجموع متغیرهای مصنوعی را در حالت MIN به جای تابع هدف اصلی در مدل قرار داده و شروع به حل مدل خواهیم کرد(میتوان مدل را با همان تابع هدف MIN سازی نیز حل کرد اما به طور معمول تابع هدف مصنوعی MIN سازی را به MAX سازی تبدیل می‌نمایند).
سپس جدول اولیه سیمپلکس را با همین تابع هدف شکل داده و ابتدا ضرایب متغیرهای مصنوعی(شبیه صفر کردن ضرایب متغیر M در روش M بزرگ) را در سطر صفر یا همان سطر تابع هدف صفر می‌کنیم و جداول را تا انتها و رسیدن به جدول نهایی ادامه می‌دهیم.
3. حالا باید جدول نهایی را بررسی کنیم، اگر در جدول نهایی مقدار تابع هدف صفر شده باشد و هیچ متغیر مصنوعی(R) در پایه باقی نمانده باشد و یا اگر هم در پایه باقی مانده باشند مقدار صفر داشته باشد، آنگاه تابلو یا جدول نهایی بهینه است و می‌توانیم فاز یا مرحله دوم را شروع کنیم.
اما اگر مقدار تابع هدف صفر نمیشد یا متغیر مصنوعی با مقدار بزرگتر از صفر در پایه باقی مانده بود، مدل جواب بهینه ندارد و دیگر قادر به ادامه کار و رفتن به فاز یا مرحله دوم نیستیم.
4. در مرحله یا فاز دوم، باید سطر و ستون مربوط به متغیرهای مصنوعی(R) که صفر شده‌اند را از جدول حذف کنیم. و تابع هدف اولیه مدل را با تابع هدف مصنوعی در جدول نهایی فاز اول جایگزین کرده و دوباره مدل را به روش سیمپلکس حل می‌کنیم.
اکنون به مثال زیر که با روش دو فازی به طور خلاصه حل شده است توجه نمایید:
مسئله ثانویه یا دوگان
هر مسئله برنامه ریزی خطی یک مسئله ثانویه وابسته به خود دارد. خود مسئله اصلی را مسئله اولیه(P) و مسئله ثانویه را دوگان(D) یا Dual می‌نامند. این دو مسئله خواص بسیار نزدیکی به هم دارند به گونه‌ای که در واقع جواب بهینه یکی از این دو مسئله، همان جواب بهینه مسئله دیگر نیز خواهد بود.
در تصویر زیر می‌توانید تا فرم کلی یک مسئله ثانویه یا دوگان را مشاهده فرمایید:
قاعده کلی نوشتن دوگان برای مسئله اولیه
برای نوشتن مسئله ثانویه یا دوگان یک مسئله، می‌بایست یک سری اصول و مراحل را طی نمایید که اکنون به طور کامل به بررسی آن‌ها خواهیم پرداخت:
1. اگر تابع هدف مسئله اولیه از نوع MAX سازی باشد، تابع هدف مسئله ثانویه را باید به MIN سازی تبدیل کنیم و بالعکس یعنی اگر تابع هدف مسئله اولیه MIN سازی بود، باید تابع هدف مسئله دوگان آن را به صورت MAX سازی بنویسیم.
همچنین باید به این نکته نیز حتما توجه شود که قبل از شروع نوشتن مسئله ثانویه، در مسئله اولیه با تابع هدف MIN سازی تمامی محدودیت‌ها باید از نوع بزرگترمساوی و اگر تابع هدف مسئله اولیه از نوع MAX سازی بود، تمامی محدودیت‌ها باید به صورت کوچکترمساوی باشند و استاندارد سازی شوند( در صورتی که علامت محدودیت مغایر با موارد گفته شده باید برای تبدیل علامت کافی است تا کل آن محدودیت را در یک منفی ضرب کنیم تا علامت قرینه شود).
2. تعداد محدودیت‌های مسئله ثانویه یا دوگان برابر تعداد متغیرهای تصمیم مسئله اولیه می‌باشد. همچنین تعداد متغیرهای تصمیم مسئله ثانویه یا دوگان برابر با تعداد محدودیت‌های مسئله اولیه خواهد بود.
3. علامت متغیرهای مسئله ثانویه یا دوگان از روی علامت محدودیت‌ها یا قیود مسئله اولیه مطابق جدول زیر تعیین می‌گردد:
| علامت متغیر تصمیم در مسئله ثانویه | علامت محدودیت در مسئله اولیه | نوع تابع هدف مسئله اولیه |
|---|---|---|
| ≤ (بزرگتر مساوی) | ≥ (کوچکتر مساوی) | MAX سازی |
| ≥ (کوچکتر مساوی) | ≤ (بزرگتر مساوی) | MAX سازی |
| آزاد در علامت | = (مساوی) | MAX سازی |
| ≥ (کوچکتر مساوی) | ≥ (کوچکتر مساوی) | MIN سازی |
| ≤ (بزرگتر مساوی) | ≤ (بزرگتر مساوی) | MIN سازی |
| آزاد در علامت | = (مساوی) | MIN سازی |
4. همچنین علامت محدودیت‌های مسئله ثانویه یا دوگان از روی علامت متغیرهای تصمیم مسئله اولیه مطابق جدول زیر تعیین می‌گردد:
| علامت محدودیت در مسئله ثانویه | علامت متغیر تصمیم در مسئله اولیه | نوع تابع هدف مسئله اولیه |
|---|---|---|
| ≥ (کوچکتر مساوی) | ≥ (کوچکتر مساوی) | MAX سازی |
| ≤ (بزرگتر مساوی) | ≤ (بزرگتر مساوی) | MAX سازی |
| = (مساوی) | آزاد در علامت | MAX سازی |
| ≤ (بزرگتر مساوی) | ≥ (کوچکتر مساوی) | MIN سازی |
| ≥ (کوچکتر مساوی) | ≤ (بزرگتر مساوی) | MIN سازی |
| = (مساوی) | آزاد در علامت | MIN سازی |
5. ضرایب تابع هدف مسئله اولیه، مقادیر سمت راست مسئله دوگان را تشکیل می‌دهند.
6. بردار مقادیر سمت راست مسئله اولیه، ضرایب تابع هدف مسئله دوگان را تشکیل خواهند داد.
پس اگر بخواهیم یک جمع بندی کلی از تبدیلات مسئله اولیه به مسئله ثانویه داشته باشیم:
و حالا به چندین مثال حل شده از مسئله ثانویه یا دوگان توجه فرمایید:
قضایای مربوط مسئله ثانویه یا دوگان
حالا بعد از شناخت مسئله ثانویه یا دوگان، نوبت آن رسیده است که قضیه‌های مهم و معروف مربوط به این مسائل را با یکدگیر بررسی نماییم:
قضیه اول مسئله ثانویه یا دوگان
این قضیه بیان می‌کند که دوگان دوگان یک مسئله، همان مسئله اولیه ما خواهد بود. به عبارت دیگر اگر از مسئله اولیه، مسئله ثانویه را تشکیل دهیم و سپس دوباره برای مسئله ثانویه یک دوگان یا مسئله ثانویه تشکیل دهیم مجدد به مسئله اولیه و اصلی خواهیم رسید.
قضیه دوم مسئله ثانویه یا دوگان(قضیه ضعیف دوگانی)
اگر x1 تا xn به عنوان یک جواب موجه مسئله اولیه ما باشد و همچنین، y1 تا yn نیز جواب موجه مسئله ثانویه باشد؛ آنگاه همواره تابع هدف مسئله اولیه از تابع هدف مسئله ثانویه کوچکتر یا مساوی خواهد بود:
قضیه کمکی(لنگی) مکمل یا مکمل زائد
این قضیه بسیار مهم و پرکاربرد است و بیان می‌کند که هر جواب اساسی در مسئله اولیه، دارای یک جواب اساسی مکمل در مسئله ثانویه است و میان متغیرهای آن‌ها، یک رابطه لنگی مکمل وجود دارد و این قضیه برای فهمیدن رابطه میان مسئله اولیه و مسئله ثانویه کاربرد خواهد داشت. در تصویر زیر می‌تواند این رابطه را مشاهده نمایید:
قضیه قوی دوگانی
اگر مسئله اولیه شدنی و متناهی باشد، آنگاه جواب‌های بهینه مسئله ثانویه نیز حتما وجود دارد به طوری که:
بررسی ارتباط میان ناحیه جواب مسئله اولیه و ناحیه جواب مسئله ثانویه
اگر مسئله اولیه دارای ناحیه جواب محدود باشد آنگاه مسئله ثانویه دارای ناحیه جواب بی کران با گوشه بهینه می‌باشد.
اگر مسئله اولیه دارای ناحیه بی‌کران بدون گوشه بهینه باشد، مسئله ثانویه فاقد ناحیه جواب است.
اگر مسئله فاقد ناحیه جواب باشد، آنگاه مسئله ثانویه فاقد ناحیه جواب یا ناحیه جواب بی کران بدون گوشه بهینه دارد.
بدست آوردن جواب بهینه یک مسئله از روی جواب بهینه مسئله دیگر
برای این کار باید ابتدا یکی از دو مسئله اولیه یا ثانویه را برای حل انتخاب کنیم و جواب بهینه آن را محاسبه کنیم.
حالا جواب بهینه مسئله دیگر در سطر تابع هدف جدول سیمپلکس نهایی زیر ستون متغیرهایی هستند که در شروع حل سیمپلکس در پایه قرار داشتند.
به عنوان مثال در مسئله زیر در شروع متغیرهای S1 و S2 در پایه حضور داشتند و حالا در جدول یا تابلو نهایی می‌بینم که:
سیمپلکس ثانویه یا سیمپلکس دوگان
الگوریتم سیمپلکس ثانویه به منظور حذف متغیرهای مصنوعی در مدل‌های برنامه ریزی خطی استفاده می‌گردد. روش سیمپلکس معمولی در واقع با استفاده از دو شرط موجه بودن و بهینگی از جواب‌های غیر بهینه به سمت جواب‌های بهینه حرکت می‌کندو در حالی که سیمپلکس دوگان متسقیما با جواب‌های بهتر از بهینه سروکار دارد و با استفاده از موجه کردن این جواب‌ها به سمت جواب بهینه حرکت می‌کند.
به طور کلی میتوان گفت که شرط استفاده از الگوریتم سیمپلکس دوگان، وجود شرط بهینگی در مدل است.
این نکته نیز قابل ذکر است که اگر محدودیت مساوی در مسئله وجود داشته باشد، دیگر روش سیمپلکس ثانویه کارایی نخواهد داشت.
مراحل روش سیمپلکس دوگان یا ثانویه
1. در اولین مرحله می‌بایست تابع هدف مسئله را اگر MIN سازی بود به MAX سازی تبدیل کرده، همچنین تمامی محدودیت‌های مسئله باید از نوع کوچکتر مساوی باشند.
2. در سیمپلکس دوگان انتخاب متغیر خروجی بدین گونه است که باید به مقادیر سمت راست یا منابع را بررسی کنیم و منفی‌ترین مقدار موجود در بین اعداد سمت راست را به عنوان متغیر خروجی انتخاب می‌نماییم و سطر مربوط به این متغیر خروجی همان سطر لولا خواهد بود.
3. در قدم بعدی برای تعیین متغیر ورودی باید اعداد سطر تابع هدف را بر اعداد منفی سطر لولا تقسیم کرده و سپس با در نظر گرفتن قدرمطلق کوچکترین عدد را به عنوان متغیر ورودی در نظر بگیریم و حالا ستون مربوط به متغیر ورودی همان ستون لولا می‌باشد.
4. ادامه مراحل تا رسیدن به جدول نهایی نیز به همین شکل ادامه خواهد داشت و شرط پایان جداول سیمپلکس ثانویه این است که در بین مقادیر سمت راست هیچ مقدار منفی دیده نشود.
اکنون به مثال زیر که با الگوریتم سیمپلکس ثانویه حل شده است، توجه نمایید:
معرفی منابع درس بهینه سازی خطی
- کتاب برنامه ریزی خطی و جریان‌های شبکه‌ای؛ نوشته: مختار بازارا، جارویس و شرالی؛ ترجمه: دکتر اسماعیل خرم
- کتاب برنامه ریزی خطی؛ نوشته: لیبرمن، ترجمه محمد مدرس یزدی و اردوان آصف وزیر
- کتاب آشنایی با تحقیق در عملیات؛ نوشته: حمدی طه
- کتاب تحقیق در عملیات 1؛ نوشته: مازیار زاهدی سرشت؛ انتشارات نگاه دانش
- کتاب 2000 تست تحقیق در عملیات(3 جلد)؛ نوشته: مازیار زاهدی سرشت؛ انتشارات نگاه دانش
- کتاب بهینه سازی خطی؛ نوشته: مجید سیلمانی
- پژوهش عملیاتی دکتر محمدرضا مهرگان
- کتاب تحقیق در عملیات؛ نوشته: میربهادر قلی آریانژاد و سید جعفر سجادی
جزوات آموزشی درس بهینه سازی خطی
اکنون چندین مورد از جزوه‌های آموزشی مناسب و جامع درس بهینه سازی خطی(تحقیق در عملیات) را با ذکر نویسنده درون آن که در تهیه این مطلب از این جزوات کمک گرفته شده است، تقدیم مخاطبان گرامی سایت آلفا مث خواهد شد:
جزوه اسلایدی بهینه سازی خطی به همراه مثال
جزوه تحقیق در عملیات دکتر عادل آذر
جزوه تحقیق در عملیات، مدرس: اعظم باقری
معرفی فیلم‌های آموزشی درس بهینه سازی خطی
آموزش رایگان تحقیق در عملیات 1 (OR1)؛ مدرس: دکتر بهزاد اشجری؛ سایت مکتب خونه
مجموعه آموزش‌های صفرتاصد تحقیق در عمیات؛ مدرس: دکتر سعید بهشتی؛ آپارات
تحقیق در عملیات؛ مدرس: دکتر مسعود خلیلی؛ آپارات
آموزش بهینه سازی خطی؛ مدرس: علیرضا معینی؛ آپارات
همچنین کاربران گرامی می‌توانند تا شبیه به همین مقاله، تحلیل و بررسی صفرتاصد درس ریاضی عمومی 1 را نیز در مقاله اختصاصی منتشرشده در سایت آلفا مث را نیز در صورت تمایل مشاهده و بررسی فرمایند.
نتیجه گیری
درس بهینه‌سازی خطی(تحقیق در عملیات)، یکی از مهم‌ترین و کاربردی‌ترین دروس در رشته‌های مهندسی صنایع، مدیریت، ریاضی کاربردی، مهندسی کامپیوتر و سایر رشته‌های مرتبط با تحلیل داده و تصمیم‌گیری است. این درس پایه و مبنای بسیاری از مدل‌سازی‌های تصمیم‌گیری و بهینه‌سازی در دنیای واقعی است و مفاهیم کلیدی مانند مدل‌سازی خطی، روش سیمپلکس، روش دوگان، تحلیل حساسیت، و روش‌های حمل و نقل و تخصیص را شامل می‌شود.
برای موفقیت در این درس، بهره‌گیری از منابع جامع، آموزش‌های ویدیویی، و جزوات استادان معتبر به‌ویژه از دانشگاه‌های برتر ایران مانند دانشگاه صنعتی شریف، دانشگاه تهران، و دانشگاه علم و صنعت بسیار مهم است. علاوه بر این، تسلط بر نرم‌افزارهایی مانند Lingo، MATLAB، Excel Solver و GAMS نقش مؤثری در درک بهتر مباحث دارد.
به طور کلی، درس بهینه‌سازی خطی یک ابزار قدرتمند برای حل مسائل واقعی در صنعت، کسب‌وکار و علوم داده محسوب می‌شود و یادگیری عمیق آن می‌تواند در مسیر شغلی و تحصیلی دانشجویان و پژوهشگران تأثیر مثبتی داشته باشد و همچنین یکی از دروس مهم و اساسی در کنکور کارشناسی ارشد ریاضی است.
سوالات متداول
1. درس بهینه‌سازی خطی چه مباحثی را پوشش می‌دهد؟
درس شامل مباحثی مانند مدل‌سازی خطی، روش سیمپلکس، مسأله دوگان، تحلیل حساسیت، مسائل حمل و نقل و تخصیص، روش‌های بهینه‌سازی عددی و کاربردهای نرم‌افزاری است.
2. بهترین منابع برای یادگیری بهینه‌سازی خطی کدامند؟
کتاب‌هایی مانند «تحقیق در عملیات – هیلیر و لیبرمن»، «بهینه‌سازی خطی – همایون پور»، و دوره‌های آنلاین از مؤسساتی مانند مکتب‌خونه، فرادرس و یودمی جزو منابع پرکاربرد هستند.
3. چه نرم‌افزارهایی برای حل مسائل بهینه‌سازی خطی استفاده می‌شوند؟
نرم‌افزارهایی مانند Lingo، GAMS، MATLAB، Excel Solver و حتی زبان‌های برنامه‌نویسی مثل Python با کتابخانه‌هایی مانند PuLP و SciPy استفاده می‌شوند.
4. فرق بین بهینه‌سازی خطی و غیرخطی چیست؟
در بهینه‌سازی خطی، توابع هدف و محدودیت‌ها همگی خطی هستند، در حالی که در بهینه‌سازی غیرخطی ممکن است توابع شامل توان، لگاریتم، نمایی یا سایر عناصر غیرخطی باشند.
5. آیا یادگیری بهینه‌سازی خطی برای بازار کار مفید است؟
بله، به‌شدت! بهینه‌سازی خطی در صنایع لجستیک، تولید، امور مالی، تحلیل داده، مدیریت پروژه و بسیاری از حوزه‌های دیگر به‌صورت مستقیم استفاده می‌شود