حل مساله برنامه‌ریزی خطی

روش ترسیمی

حل مسئله برنامه‌ریزی خطی با استفاده از روش ترسیمی یکی از ساده‌ترین و بصری‌ترین شیوه‌ها برای درک و تحلیل مسائل بهینه‌سازی است. این روش به ویژه برای مسائل با دو متغیر بسیار کاربردی است و به ما این امکان را می‌دهد که به راحتی محدودیت‌ها و تابع هدف را تجسم کنیم. در این روش، ابتدا محدودیت‌های مسئله به صورت معادلات خطی رسم می‌شوند و ناحیه قابل قبول که نشان‌دهنده مجموعه‌ای از نقاط ممکن برای حل مسئله است، مشخص می‌شود.

سپس، تابع هدف نیز به صورت یک خط رسم می‌شود و با حرکت در ناحیه قابل قبول، نقاط مختلف بررسی می‌شوند تا مشخص شود کدام نقطه حداکثر یا حداقل مقدار تابع هدف را فراهم می‌کند. این فرآیند نه تنها به ما کمک می‌کند تا جواب بهینه را پیدا کنیم، بلکه درک عمیق‌تری از رابطه بین متغیرها و تأثیر محدودیت‌ها بر روی تصمیم‌گیری‌ها ارائه می‌دهد.

مثال حل ترسیمی

مسئله زیر را به روش ترسیمی حل کنید

\[\begin{align} Maximize\ z = 2x_1 + 3x_2 \\ \\ 2x_1 + x_2 \leq 4 \\ x_1 + 2x_2 \leq 5 \\ \\ x_1,x_2 \geq 0 \end{align}\]

پاسخ

تمرین حل ترسیمی

• مساله کارخانه رنگ را به روش ترسیمی حل کنید

روش سیمپلکس

حل برنامه‌ریزی خطی یکی از مهم‌ترین و پرکاربردترین تکنیک‌ها در علم مدیریت و بهینه‌سازی است که به ما این امکان را می‌دهد تا منابع محدود را به بهترین شکل ممکن تخصیص دهیم. یکی از روش‌های متداول برای حل مسائل برنامه‌ریزی خطی، روش سیمپلکس است که توسط جورج دانزیگ در دهه 1940 معرفی شد. این روش به طور خاص برای مسائل با چندین متغیر و محدودیت‌های خطی طراحی شده است و می‌تواند به سرعت به جواب‌های بهینه دست یابد. اساس کار سیمپلکس بر مبنای حرکت در میان رئوس یک چندوجهی تعیین شده توسط محدودیت‌ها است، به گونه‌ای که در هر مرحله، مقدار تابع هدف را به حداکثر یا حداقل می‌رساند. این فرآیند ادامه می‌یابد تا زمانی که به نقطه‌ای برسیم که دیگر نمی‌توانیم بهبود بیشتری در تابع هدف ایجاد کنیم. روش سیمپلکس نه تنها در حوزه‌های اقتصادی و صنعتی بلکه در زمینه‌های مختلف علمی و تحقیقاتی نیز کاربرد دارد و توانسته است تحولی شگرف در نحوه تصمیم‌گیری و تخصیص منابع ایجاد کند. با توجه به پیچیدگی‌های موجود در مسائل واقعی، این روش با الگوریتم‌های پیشرفته‌تری نیز ترکیب شده است تا کارایی و دقت بیشتری را ارائه دهد.

شکل معادله‌ای

• تمام قیود بایستی از شکل نامعادله به معادله تبدیل شود
• در شکل معادله‌ای متغیرها در سمت چپ و مقادیر ثابت نامنفی در سمت راست قرار می‌گیرد
• همه متغیرها مثبت هستند
• برای تبدیل نامعادلات به معادلات از متغیرهای کمکی استفاده می‌شود

مثال: شکل معادله‌ای مساله کارخانه رنگ

\[\begin{align} Maximize\ z = 5x_1 + 4x_2 \\ \\ 6x_1 + 4x_2 \leq 24 \\ x_1 + 2x_2 \leq 6 \\ x_2 - x_1 \leq 1 \\ x_2 \leq 2 \\ \\ x_1, x_2 \geq 0 \\ \end{align}\]

پاسخ

\[\begin{align} z - 5x_1 - 4x_2 = 0 \\ 6x_1 + 4x_2 + S_1 = 24 \\ x_1 + 2x+2 + S_2 = 6 \\ -x_1 + x_2 + S_3 = 1 \\ x_2 + S_4 = 2 \end{align}\]

الگوریتم سیمپلکس

• شرط بهینگی: متغیر ورودی (ستون مفصل) مسئله بیشینه سازی (کمینه سازی) منفی‌ترین (مثبت‌ترین) ضریب متغیر غیر پایه در ردیف تابع هدف است.
• شرط خاتمه الگوریتم: همه ضرایب متغیرهای ردیف تابع هدف نامنفی (نامثبت) شوند.
• شرط جواب: برای هر دو مسئله بیشینه‌سازی و کمینه‌سازی متغیر خروجی (ردیف مفصل) کوچکترین نسبت ضرایب نامنفی (نسبت سمت راست به ضرایب ستون مفصل) می‌باشد. در صورت یکسان بودن نسبت‌ها انتخاب دلخواه است.
• عدد مفصل: تلاقی ستون مفصل و ردیف مفصل است.
• حذف گاوسی: تبدیل عدد مفصل به ۱ (تقسیم بر خودش) و تبدیل سایر ضرایب ستون مفصل به صفر.

مثال: حل مساله تولید رنگ به روش سیمپلکس

جدول سیمپلکس را برای مسئله کارخانه تولید رنگ تشکیل دهید و آن را حل کنید

پاسخ

تمرینات سیمپلکس (بیشینه سازی)

مساله زیر را به روش سیمپلکس حل کنید

\[\begin{align} Maximize\ z = 5x_1 + 4x_2 \\ \\ 6x_1 + 4x_2 \leq 24 \\ x_1 + 2x_2 \leq 6 \\ x_2 - x_1 \leq 1 \\ x_2 \leq 2 \\ \\ x_1, x_2 \geq 0 \\ \end{align}\]

مساله زیر را به روش سیمپلکس حل کنید

\[\begin{align} Maximize\ z = 3x_1 + 2x_2 \\ \\ -x_1 + 2x_2 \leq 4 \\ 3x_1 + 2x_2 \leq 4 \\ x_1 - x_2 \leq 3 \\ \\ x_1, x_2 \geq 0 \\ \end{align}\]

مساله زیر را به روش سیمپلکس حل کنید

\[\begin{align} Maximize\ z = 3x_1 + 2x_2 + 5x_3 \\ \\ 3x_1 + 2x_3 \leq 460 \\ x_1 + 2x_2 + x_3 \leq 430 \\ x_1 + 4x_2 \leq 420 \\ \\ x_1, x_2, x_3 \geq 0 \\ \end{align}\]

روش M بزرگ

روش \(M\) با مسئله برنامه‌ریزی خطی (LP) در فرم معادله‌ای شروع می‌شود. اگر محدودیت \(i\) دارای متغیر مصنوعی نباشد (یا متغیری که بتواند نقش متغیر مصنوعی را بازی کند)، یک متغیر مصنوعی به نام \(R_i\) به مسئله اضافه می‌شود تا یک راه‌حل اولیه مشابه با راه‌حل پایه‌ای تمام-مصنوعی ایجاد شود. با این حال، از آنجا که متغیرهای مصنوعی بخشی از مسئله اصلی نیستند، برای حذف آنها از راه‌حل نهایی، یک "ترفند مدلسازی" مورد نیاز است که آنها را در زمان رسیدن به تکرار بهینه به مقدار صفر برساند (با فرض اینکه مسئله دارای یک جواب شدنی باشد). این هدف از طریق اعمال یک جریمه به دست می‌آید که به صورت زیر تعریف می‌شود: ضرایب تابع هدف برای متغیرهای مصنوعی برابر است با \(-M\) در مسائل ماکزیمم و \(+M\) در مسائل مینیمم. در اینجا، \(M\) یک مقدار مثبت بسیار بزرگ است که به طور ریاضی به سمت بی‌نهایت میل می‌کند (\(M \to \infty\)).

مثال روش M بزرگ

\[\begin{align} Minimize\ z = 4x_1 + x_2 \\ \\ 3x_1 + x_2 = 3 \\ 4x_1 + 3x_2 \geq 6 \\ x_1 + 2x_2 \leq 4 \\ \\ x_1, x_2 \geq 0 \\ \end{align}\]

فرم معادله‌ای

\[\begin{align} z - 4x_1 - x_2 - MR_1 - MR_2 = 0 \\ 3x_1 + x_2 + R_1 = 3 \\ 4x_1 + 3x_2 - S_1 + R_2 = 6 \\ x_1 + 2x_2 +S_2 = 4 \\ \end{align}\]

جدول سیمپلکس

ترسیم

روش دوفازی

• فاز I: مسئله را به شکل معادله درآورید و متغیرهای مصنوعی لازم را به محدودیت‌ها اضافه کنید (دقیقا مانند روش M) تا یک جواب اولیه پایه را بدست آورید. سپس یک جواب پایه از معادلات حاصل پیدا کنید که همیشه مجموع متغیرهای مصنوعی را بدون در نظر گرفتن اینکه آیا LP ماکزیمم یا مینیمم است، به حداقل برساند. اگر مقدار حداقل مجموع مثبت باشد، مسئله LP هیچ جواب شدنی ندارد. در غیر این صورت، به فاز II بروید.

• فاز II: از جواب شدنی فاز I به عنوان یک جواب اولیه شدنی پایه برای مسئله اصلی استفاده کنید.

مثال روش دوفازی

مساله قبل را به روش دوفازی حل کنید

تابع هدف فاز اول

\[Minimize\ z' = R_1 + R_2\]

جدول سیمپلکس