محدودیت زائد: انواع و بعضی روشهای شناسایی در برنامه ریزی خطی – تحقیق در عملیات

فیلم آموزش بررسی انواع محدودیت زائد از فصل سیمپلکس و فصل روشهای حل و همگرایی کتاب بازارا و مورتی در تحقیق در عملیات ۱ در حدود ۲۵ دقیقه تهیه شده است.

منبع اصلی کتاب تحقیق در عملیات ۱ مهندس ایمن پور معروف به کتاب قرمز است. در ارتباط با فیم آموزشی فوق موارد زیر را در نظر داشته باشید:

۱) محدودیت زائد هندسی

در ابتدا زائد هندسی را مرور می کنیم، به شکل زیر دقت کنید.
تعریف زائد هندسی از کتاب بازارا (اصلی) آمده است.

برای مثالی دیگر محدودیت ۴ یک محدودیت زائد هندسی است.

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

حال می خواهیم روشهای پیدا کردن محدودیت زائد (در اینجا زائد هندسی) را بیاموزیم.
همانطور که در شکل زیر مشاهده می شود مساله مینیمم سازی روی متغیر کمکی هر محدودیت بصورت جداگانه لحاظ می کنیم.

در مثال فوق ۴ محدودیت داریم و در نتیجه ۴ مساله جداگانه باید تعریف شود که در ادامه آمده است.

نتیجه نهایی در مورد محدودیت زائد بصورت زیر شکل می گیرد یعنی اگر مقدار متغیر کمکی در بهینگی مثبت باشد نتیجه می گیریم که محدودیت زائد هندسی است.

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

در تمرین ۲۶ فصل ۴ کتاب بازارا نکته جالبی آمده است که در فیلم هم بطور کامل توضیح داده شده است.

این تمرین به عنوان یک نکته در صفحه ۲۵۴ کتاب قرمز تحقیق در عملیات ۱ مهندس امیر ایمن پور نیز آمده است.

برای مثال به جدول سیمپلکس زیر توجه کنید که نکته مورد نظر نمایش داده شده است.
دقت کنید متغیر کمکی سوم و چهارم شرایط نکته فوق را دارند و می توان نتیجه گرفت که محدودیت زائد هندسی است.

حال مهم است که بدانیم انتهای فاز اول روش دو فازی آیا محدودیت زائد هندسی قابل شناسایی است؟
پاسخ این سوال خیر است. در بخش بعدی این موضوع را بیشتر بررسی می کنیم.

۲) محدودیت زائد جبری

حال تعریف محدودیت زائد جبری را از کتاب برنامه ریزی خی مورتی میبینیم: (دو عکس بعد)

حال تعریف محدودیت زائد را در صفحه ۸۹ کتاب قرمز تحقیق در عملیات ۱ و در مبحث معادلات خطی وابسته مرور می کنیم:

فرض کنیم k معادله داریم که شرایط زیر را داشته باشند، آنگاه گفته می شود یک دور از معادلات خطی وابسته داریم:

برای مثال سه محدودیت زیر دارای شرایط فوق هستند و در شکل نیز می توان نتیجه آن را دید:

حال به نکات تکمیلی محدودیت زائد جبری در ادامه دقت کنید:

حال روش گوس جردن را کمی مرور کنیم. قصد داریم پیدا کردن زائد جبری را در آن بررسی کنیم.

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

روش دیگر شناسایی زائد جبری که در واقع استفاده از همان روش اول است، جدول انهتای فاز یک است.
بخشی از کتاب بازارا (اصلی) آورده شده است.

ترجمه آنچه گفته شده در کتاب قرمز تحقیق ۱ آمده است و در شکل زیر مشاهده می شود.

در شکل زیر می بینید که بازارا نیز این نوع زائد را زائد جبری می نامد.

مثال برای پیدا کردن زائد جبری

حال یک مثال را از کتاب بهینه سازی خطی برتسیماس که در کتاب قرمز تحقیق ۱ نیز آمده است را مرور می کنیم.

مساله فاز ۱ از روش دو فازی بصورت زیر است:

جداول بعدی در ادامه آمده است.

حال به جدول آخر فاز یک و توضیحات آن دقت کنید.

مثال دوم برای پیدا کردن زائد جبری

به مثال دیگری توجه کنید:

جداول فاز یک در ادامه آمده است.

حال به سوال قبل باز می گردیم، آیا زائد هندسی در انتهای فاز یک شناسایی می شود؟
پاسخ خیر است و برای مثال، تمرین ۷ فصل ۴ کتاب بازارا را ببینید.

ترجمه تمرین گفته شده در کتاب قرمز تحقیق در عملیات ۱ نیز آمده است.

نکته جالبی نیز صفحه ۲۵۵ کتاب قرمز آمده است و به آن توجه کنید.

در انتها پیشنهاد می کنیم بطور دقیق ۲۵ دقیقه فیلم فوق حتما مشاهده شود.

جهت پرسش و پاسخ می توانید در گروه تلگرام تحقیق در عملیات مهندس ایمن پور عضو باشید:
@OR12_QA

همچنین آرشیو پرسش و پاسخ با مهندس ایمن پور در ارتباط با سوالات کتابهای آبی (تست تحقیق ۱) و زرد (تست تحقیق۲) حتما پست اینجا را مطالعه کنید. منبع قابل توجهی از پرسش و پاسخ تحقیق در عملیات موجود است.

جهت ثبت نام در دوره های تحقیق در عملیات مهندس ایمن پور در موسسه پژوهش به منوی دوره های آموزشی در بالای صفحه مراجعه بفرمایید.