دانلود pdf برنامه ریزی عدد صحیح کمیاب و عالی

در دنیای بهینه‌سازی، برنامه ریزی عدد صحیح یک شاخه حیاتی است که به حل مسائل تصمیم‌گیری می‌پردازد، جایی که برخی یا تمامی متغیرهای تصمیم باید مقادیر صحیح (و نه لزوماً پیوسته) را اختیار کنند. این رویکرد به ویژه در موقعیت‌هایی کاربرد دارد که انتخاب‌ها گسسته و غیرقابل تقسیم هستند، مانند تعداد کارخانه‌هایی که باید احداث شوند یا اینکه یک پروژه خاص انجام شود یا خیر.

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

یکی از کاربردهای کلاسیک برنامه‌ریزی عدد صحیح صفر و یک در بودجه‌بندی سرمایه‌ای است. در این زمینه، مدل برنامه‌ریزی بودجه‌بندی سرمایه‌ای به شرکت‌ها کمک می‌کند تا بهترین مجموعه پروژه‌ها را برای سرمایه‌گذاری انتخاب کنند، با توجه به محدودیت‌های بودجه‌ای و سایر منابع، و به گونه‌ای که بیشترین سود یا بازده را به ارمغان آورد.

یک مثال بودجه‌بندی سرمایه‌ای شامل انتخاب از میان چندین پروژه با بازدهی و هزینه‌های متفاوت است که باید از بودجه‌ای محدود تامین مالی شوند. فرموله‌سازی این مدل‌ها نیاز به دقت فراوان در تعریف فروض برنامه سرمایه‌گذاری دارد، از جمله فرض ۱: هم‌زمانی که بیان می‌کند پروژه‌ها می‌توانند همزمان اجرا شوند؛ فرض ۲: ناسازگاری که نشان می‌دهد انتخاب یک پروژه، مانع از انتخاب پروژه دیگر می‌شود؛ و فرضیات وابستگی مانند فرض ۳: اگر در پروژه ۱ سرمایه‌گذاری شود، در پروژه ۴ نیز باید سرمایه‌گذاری شود ، یا فرض ۴: سرمایه‌گذاری در پروژه ۳ منوط به سرمایه‌گذاری در پروژه ۱ است.

مسئله کوله‌پشتی نیز یک مسئله معروف در برنامه‌ریزی عدد صحیح است که در آن باید از میان مجموعه‌ای از آیتم‌ها با وزن‌ها و ارزش‌های مختلف، آیتم‌هایی را انتخاب کرد تا در یک کوله‌پشتی با ظرفیت محدود جای گیرند و بیشترین ارزش کل را به دست آورند. یک مثال مسئله کوله‌پشتی می‌تواند انتخاب تجهیزات برای یک سفر با کوله‌پشتی محدود یا انتخاب پروژه با محدودیت بودجه باشد. فرموله‌کردن این مسئله به سادگی متغیرهای صفر و یک را برای نشان دادن انتخاب هر آیتم به کار می‌گیرد.

مسئله فروشنده دوره‌گرد یکی دیگر از مسائل شاخص و چالش‌برانگیز در این حوزه است. هدف در مثال مسئله فروشنده دوره‌گرد ، یافتن کوتاه‌ترین مسیری است که یک فروشنده باید از آن عبور کند تا هر شهر را دقیقاً یک بار ملاقات کرده و به نقطه شروع بازگردد.

گام اول و دوم: تعریف متغیرهای تصمیم و تابع هدف در اینجا شامل متغیرهای صفر و یک برای نشان دادن حرکت بین شهرها و تابع هدف برای کمینه‌سازی مسافت کل است. گام سوم: تعریف محدودیت‌های مدل و ادامه محدودیت‌ها اطمینان حاصل می‌کند که هر شهر دقیقاً یک بار بازدید شود و زیر-تورها (مسیرهای بسته فرعی) تشکیل نشود. این عناصر در نهایت به مدل کامل مسئله فروشنده دوره‌گرد و مدل عمومی مسئله فروشنده دوره‌گرد می‌انجامد.

مسئله مکان‌یابی (مسئله آتش‌نشانی) مثالی دیگر از کاربردهای برنامه‌ریزی عدد صحیح است که در آن هدف تعیین بهینه مکان برای استقرار تسهیلاتی مانند ایستگاه‌های آتش‌نشانی، بیمارستان‌ها یا انبارها است.

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

کاربردهای دیگر از متغیرهای صفر و یک فراتر از مسائل بودجه‌بندی و مکان‌یابی است. این متغیرها می‌توانند برای مدل‌سازی محدودیت‌های «این یا آن» استفاده شوند، جایی که حداقل یکی از دو یا چند گزینه باید انتخاب شود. همچنین، برقراری k محدودیت از N محدودیت به معنای این است که باید حداقل k محدودیت از N محدودیت موجود برقرار باشد.

محدودیت «برقراری N محدودیت از k» نیز حالتی مشابه است که در آن باید به طور دقیق N محدودیت از k محدودیت برقرار گردد. سه حالت محدودیت «برقراری N محدودیت از k» نیز نشان‌دهنده انعطاف‌پذیری در مدل‌سازی انتخاب‌های مختلف است.

در مواردی، با محدودیت با r مقدار معین در سمت راست مواجه می‌شویم که به این معنی است که سمت راست یک محدودیت می‌تواند یکی از r مقدار از پیش تعیین شده را بپذیرد. مثال محدودیت با r مقدار معین در سمت راست می‌تواند نشان دهد که ظرفیت تولید یک کارخانه می‌تواند یکی از چند سطح گسسته باشد.