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