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

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