مروری بر مسائل بهینه‌سازی متغیر صحیح

Abstract

بسیاری از پدیده های عالم واقعی در صورت مدل‌سازی با مقادیر عدد صحیح بیان می‌شوند. تعداد سدهای ساخته شده روی رودخانه، تعداد نیروی انسانی نمی‌توانند با اعداد اعشاری بیان شوند. برنامه‌ریزی متغیر صحیح مدلی ریاضی است که برای مدل‌سازی مسائلی شبیه آنچه گفته شد، به کار گرفته می‌شود. به عبارتی چنانچه تنها تفاوت فرموله کردن مسئله با یک مسئله‌ی برنامه‌ریزی خطی، در نظر گرفتن محدودیت متغیر صحیح باشد، به آن برنامه‌ریزی متغیر صحیح می‌گویند. <br />یک زمینه کاربرد دیگر برنامه‌ریزی متغیر صحیح که حتی اهمیت بیشتری دارد, پرداختن به تصمیم‌هایی از نوع "بله یا نه" است. به عنوان نمونه آیا منطقه ‎ x ‎ مکان مناسبی برای ایجاد یک مرکز فروش یا خدمات پس از فروش است یا خیر؟ هر تصمیمی که فقط دو انتخاب در پیش داشته باشد را می‌توان بر حسب متغیرهایی بیان کرد که فقط دو مقدار، یعنی صفر و یک را انتخاب می‌کنند؛ به طوری که اگر تصمیم j‎ نه باشد،‎x_j=0 ‎ و اگر تصمیم بله باشد، ‎x_j=1‎ . به چنین متغیرهایی، متغیرهای صفر و یک یا متغیرهای دوتایی گویند. در نتیجه به مسایل برنامه‌ریزی متغیر صحیح که فقط شامل چنین متغیرهایی باشند، مسایل برنامه‌ریزی متغیر صحیح صفر و یک(‎‎ دوتایی ) گفته می‌شود.<br />در این تحقیق به معرفی انواع مسائل متغیر صحیح پرداخته و به توضیح مختصری از کاربردها و روش‌های موجود برای حل هر کدام می‌پردازیم.