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

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