Online User مدلسازی مسئله برنامه ریزی عدد صحیح Integer Programming - مدیریت صنعتی Industrial Management

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

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

مدلسازی مسئله برنامه ریزی عدد صحیح Integer Programming
نویسنده : محسن رحیمی - ساعت ٩:۱۸ ‎ب.ظ روز ۱۳٩٠/٤/۳۱
 

برنامه ریزی عدد صحیح (IP) نام گروهی از مسائل برنامه ریزی خطی است که در آن کلیه یا تعدادی از متغیرها حتماً باید اعداد صحیح غیر منفی باشند. برای حالت عمومی برنامه ریزی خطی متغیرهای تصمیم بهینه می توانند هر مقدار غیر منفی صحیح یا غیر صحیح باشند. متاسفانه اعداد غیر صحیح (کسری) در بسیاری از مسائل نه عملی هستند و نه معنی دار. این مشکل در اکثر مسائل مربوط به تجارت، مسائل تولیدی و نظامی وجود دارد. برای نمونه اگر در مثال انتخاب تعداد مناسب وسائل نقلیه ها جواب به صورت کسری حاصل شود (مثلاً تعداد ماشین ماک 37.6 محاسبه شود) اصالتاً پاسخ معنی داری نیست. برای حل این معضل برنامه ریزی عدد صحیح که پاسخ های حاصل از آن اعداد صحیح هستند مورد استفاده قرار می گیرد. به طور کلی می توان گفت برنامه ریزی عدد صحیح همان برنامه ریزی خطی است که شرط بخش پذیری برای آن صادق نیست. سه نوع مدل برنامه ریزی عدد صحیح وجود دارد که عبارتند از:

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

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

مدل بالا را می توان یک مدل برنامه ریزی عدد صحیح نامید. همانطور که ملاحظه می شود تفاوت مدل اولیه با این مدل تنها در اضافه نمودن عبارت Integer در انتهای محدودیت غیر منفی بودن متغیرهاست. در نرم افزارهای مختلف حل مسائل برنامه ریزی خطی، راه های گوناگونی جهت تعیین عدد صحیح بودن متغیرها وجود دارد. در این بخش قصد پرداختن به چگونگی حل این مسائل را نداریم. تنها باید به یاد داشته باشیم که در مدلسازی حتماً باید نوع متغیرها مشخص باشد. در صورتی که در رابطه با متغیرها به جز محدودیت غیر منفی بودن قید دیگری ذکر نشده بود، متغیرها از نوع اعداد حقیقی غیر منفی هستند. برای تعیین صفر و یک بودن متغیرها نیز می توانید از عبارت are either 1 or 0 پس از محدودیت غیر منفی بودن استفاده نمایید.

پست مرتبط بعدی:مثالی برای مسئله بودجه بندی سرمایه ای

پست مرتبط قبلی: مدلسازی مسئله انتخاب ترکیب وسائل نقلیه