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

نوع مقاله: مقاله علمی-ترویجی

نویسنده

دانشگاه اصفهان

چکیده

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

کلیدواژه‌ها


A‎. ‎Brooke‎, ‎D‎. ‎Meeraus‎, ‎A‎. ‎Meeraus ‎and‎ R‎. ‎Raman (1997) ‎GAMS Language Guide‎, ‎GAMS Development Corporation ‎Release 2.25‎ ‎Version 92
M‎. ‎A‎. ‎Duran ‎and‎ ‎I‎. ‎E‎. ‎Grossmann (1986) ‎An Outer approximation algorithm for a class of mixed integer nonlinear programs Math. Programming 36, 307-339
C‎. ‎A‎. ‎Floudas (1995) ‎Nonlinear and Mixed Integer Optimization ‎Department of Chemical Engineering‎, ‎Princeton University‎, ‎Princeton New Jersey
O‎. ‎Odele ‎and‎ ‎S‎. ‎Macchietto (1993) ‎Computer aided molecular design‎: ‎A novel method for optimal solvent selection Fluid Phase Equilibria 82, 47-62
N‎. V. ‎Sahinidis ‎and‎ ‎I‎. ‎E‎. ‎Grossmann (1991) ‎Reformulation of multiperiod MILP models for planning and scheduling of chemical processes Computers and Chemical Engineering 15, 255-272