جدول سیمپلکس به زبان خودمانی :دی

 * بهانه این پست رو بهزاد بهم داد، ازش تشکر میکنم ؛)

 * گیریم مساله برنامه‌ریزی خطی ما این باشه:

سعی می‌کنیم که به روش سیمپلکس، این برنامه‌ریزی خطی رو حل کنیم. برای دوستانی که با برنامه‌ریزی خطی آشنا نیستن بگم که این دستگاه بالا میتونه نشون از برنامه‌ریزی ِ پدر ِ خانواده باشه برای رفتن به مسافرت. پدر میخواد خانواده‌ش، بیشترین لذت ممکن رو از بودن در دو شهر x و y داشته باشن، فقط مشکل اینجاست که اگه خیلی بخوان خوش باشن پول‌شون تموم میشه ؛) خب پدر برنامه‌ریزی میکنه تا در هر شهر چقدر بمونه و بیشترین مقدار خوش‌گذشتن بهشون هم چند دکتر -که دکتر واحد خوش‌گذرونیه- میتونه باشه :)

 * بعد از استاندارد کردن مساله، ما اینطور چیزی داریم:

* برای مساله بالا اگه جدول سیمپلکس رو تشکیل بدیم، اینطور چیزی خواهیم داشت:

 * در جدول بالا، ما کدوم متغیر رو برای ورود به پایه انتخاب کنیم؟ اونی که کوچکترین ضریب ِ منفی رو در سطر ِ تابع هدف داشته باشه، یعنی در اینجا y، چون ضریبش منفی هفت ِ و کوچکترین، چرا این کار رو انجام میدیم؟ در جدول بالا، اگه معادله تابع هدف رو بر اساس سطر اول بنویسم، خواهیم داشت: z = 2x + 7y؛ در این معادله، اگر به مقدار y یک واحد اضافه کنید، مقدار تابع هدف -یعنی z- هفت واحد -یعنی ضریب y- افزایش پیدا میکنه، در حالیکه اگه به مقدار x یک واحد اضافه کنیم، مقدار تابع هدف ۲ واحد افزایش پیدا میکنه، چون متغیرهای s و h -متغیرهای کمکی- در تابع هدف ضریبشون صفر ِ، پس افزایش اونا تاثیری در مقدار تابع هدف نمیذاره. بنابراین متغیر y برای ورود به پایه انتخاب میشه.

 * خب حالا کی باید خارج بشه؟ جواب این سوال رابطه‌ی مستقیم داره با مقدار افزایش متغیر ورودی. یعنی ما در نمودار بالا، متغیر y رو تا جایی میتونیم افزایش بدیم که از اون ناحیه سبز رنگ که همون محدوده‌ی شدنی -Feasible area- هست خارج نشیم. این یعنی در صورت افزایش متغیر y هیچکدوم از محدودیت‌ها نباید از شرایط ارضاشده بیان بیرون و مقدار هیچکدوم از متغیرها هم نباید منفی بشه. خب برای فهمیدن اینکه ما چقدر میتونیم متغیر y رو افزایش بدیم، فرض می‌کنیم که همه‌ی متغیرهای غیرپایه‌ای موجود -در اینجا یعنی x- مقدار صفر رو داشته باشند -یعنی فرض می‌کنیم مقدار افزایش‌شون در این مرحله از جدول صفر واحد باشه- بنابراین در شکل استاندارد برنامه‌ریزی خطی که در بالا اومد، محدودیت‌ها اینطور چیزی میشن:

از این معادله، مقادیر معادل متغیر‌های پایه‌ای رو بدست میاریم:

خب گفتیم که هیچکدوم از متغیرها نباید منفی باشند، پس باید داشته باشیم: و ، از این دوتا و معادلات بالا نتیجه میشه که و . این یعنی اگر مقدار y از ۲.۸۵ (که همون هست) بیشتر بشه، h منفی میشه و اگر از ۴ بیشتر بشه s. ما برای اینکه هر دوتا متغیر نامنفی باقی بمونن، مقدار کمتر یعنی ۲.۸۵ رو انتخاب می‌کنیم. این یعنی اگر مقدار y به اندازه ۲.۸۵ افزایش پیدا کنه، مقدار تابع هدف بهتر میشه و همه شرایط هم ارضاشده باقی میمونن و همچنین اگه توجه کنی مقدار h هم در کنار این افزایش صفر میشه. این یعنی h دیگه تاثیری در بهینگی مقدار تابع هدف نداره و از پایه میاد بیرون.

 * خب همه‌ی این کارهایی رو که در بالا گفتیم، در جدول سیمپلکس اینطور انجام میدیم: ستون متغیر ورودی رو انتخاب می‌کنیم، همه‌ی مقادیر نامنفی سمت راست رو، بر مقادیر نامنفی این ستون تقسیم می‌کنیم، هر کدوم کوچکتر شد، میشه متغیر خروجی، یعنی اینطور چیزی:

 * خب الان در جدول ما، در این مرحله و پس از ورود و خروج متغیرها، متغیرهای پایه‌ای y و h هستند، حالا با توجه به محاسبات و داده‌های جدید که در بالا بود، این قانون از سیمپلکس که ظریب‌ هر متغیرپایه‌ای در محدودیت‌ها باید یک باشه و بالا و پایین اون ضریب صفر رو با یه عملیات سطری مقدماتی برقرار می‌کنیم، راستش رو بخوای یادم نیست چرا اینطور کاری رو میکردیم، به نظرم جز شرایط سیمپلکس بود اینطور چیزی اصن :دی- یعنی جدول اینطور چیزی میشه:

توجه کن که در جدول بالا ۱۳/۷ یعنی :دی

 * خب دوباره ما میخوایم در این جدول متغیر ورود به پایه انتخاب کنیم تا در صورت توان، جواب رو بهینه‌تر کنیم. گفتیم که در مسائل ماکزیمم‌سازی، متغیر ِ دارای ِ کوچکترین ضریب ِ منفی در سطر تابع هدف میشه متغیر ِ ورودی، اما ما در این جدول اینطور ضریبی نداریم و این یعنی جدولمون بهینه شد :) خودت میتونی شکل معادله‌ای تابع هدف رو بنویسی و ببینی که با افزایش هر واحد از متغیرهای پایه‌ای، مقدار تابع هدف کمتر خواهد شد ؛)

 * خیلی به محاسبات من اعتماد نکنید! هم دم افطار ِ و هم من در حالت عادی محاسباتم خیلی افتضاحه :))