Online User محدودیت‌های انتخاب K از N - مدیریت صنعتی Industrial Management

مدیریت صنعتی Industrial Management

مدیریت صنعتی - تحقیق در عملیات - مدیریت تولید - ...

محدودیت‌های انتخاب K از N
نویسنده : محسن رحیمی - ساعت ۱٠:٠٧ ‎ب.ظ روز ۱۳٩٠/٩/٢٦
 

مسئله‌ای را در نظر بگیرید که در مدل ریاضی آن، یک مجموعه Nتایی محدودیت وجود دارد ولی تنها Kمحدودیت از آن‌ها می‌توانند فعال باشند (K<N). در نتیجه مدل باید به صورتی نوشته شود که فرآیند بهینه سازی، ترکیبی از Kمحدودیت را به ترتیبی انتخاب کند که بهترین جواب بهینه ممکن برای مدل به دست آید. تعداد N-K محدودیتی که انتخاب نمی‌شوند، در ...

برای مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(450 کلمه)

مطلب مرتبط بعدی:محدودیت های تصمیم گیری بله - خیر

مطلب مرتبط قبلی: محدودیت های یا این یا آن


مسئله‌ای را در نظر بگیرید که در مدل ریاضی آن، یک مجموعه Nتایی محدودیت وجود دارد ولی تنها Kمحدودیت از آن‌ها می‌توانند فعال باشند (K<N). در نتیجه مدل باید به صورتی نوشته شود که فرآیند بهینه سازی، ترکیبی از Kمحدودیت را به ترتیبی انتخاب کند که بهترین جواب بهینه ممکن برای مدل به دست آید. تعداد N-K محدودیتی که انتخاب نمی‌شوند، در حقیقت از مدل حذف می‌شوند، اگر چه ممکن است تصادفاً برخی از آن‌ها در فضای موجه قرار داشته باشند. محدودیت‌های انتخاب K از N شکل عمومی‌تری از محدودیتهای «یا این یا آن» هستند که در آن K=1 و N=2 است.

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

مسئله زیر را در نظر بگیرید که در آن سه محدودیت ناسازگار وجود داشته باشد، یعنی تنها یکی از سه محدودیت می‌تواند صحیح باشد. به این ترتیب با یک مسئله K=1 از N=3 روبرو هستیم:

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

اگر محدودیت iام انتخاب شود

در غیر این صورت 

به وسیله این متغیر کمکی می‌توان مدل مسئله بالا را به یک مدل برنامه ریزی عدد صحیح معادل، تبدیل نمود.

در مدل بالا Mنمادی از یک عدد بسیار بزرگ است، به اندازه‌ای که بتواند دو محدودیت انتخاب نشده را تبدیل به محدودیت‌های زائد کند. محدودیتی که بیان می‌کند مجموع متغیرهای کمکی باید برابر با عدد یک شود، اطمینان می‌دهد که تنها یکی از محدودیت‌ها فعال می‌گردد. برای مثال اگر y1=1 آنگاه محدودیت اول فعال شده و محدودیت‌های دوم و سوم به محدودیت زائد تبدیل می‌شوند زیرا بر اساس محدودیت چهارم باید داشته باشیم: y2=y3=0

اگر متغیر کمکی مسئله را عکس تعریف بالا تعریف کنیم می‌توان مدل را به شکلی متفاوت نوشت. فرض کنید متغیر کمکی به صورت زیر تعریف شود:

اگر محدودیت iام انتخاب شود

در غیر این صورت 

مدل برنامه ریزی عدد صحیح جدیدی که بدست می‌آید به شرح زیر خواهد بود:

در اینجا نیز M باید به اندازه‌ای بزرگ باشد که مطمئن شویم دو محدودیتی که انتخاب نشده اند، تبدیل به محدودیت زائد می‌شوند. محدودیت چهارم که بیان می‌کند مجموع متغیرهای کمکی باید برابر با عدد 2 باشد، باعث می‌شود دو محدودیت از سه محدودیت تبدیل به محدودیت زائد می‌گردند. اگر y1=0 باشد آنگاه محدودیت اول فعال شده و محدودیت‌های دوم و سوم به محدودیت زائد تبدیل می‌شوند زیرا بر اساس محدودیت چهارم باید داشته باشیم: y2=y3=1

مطلب مرتبط بعدی:

مطلب مرتبط قبلی: محدودیت های یا این یا آن