Integer programming — برنامهریزی عددصحیح
برنامهریزی عددصحیح (بع؛ انگل. integer programming, IP) — شاخهای از بهینهسازی ریاضی است که در آن مسائلی بررسی میشوند که برخی یا همه متغیرها باید تنها مقادیر صحیح بپذیرند[1].
شناختهشدهترین حالت خاص آن، برنامهریزی خطی عددصحیح (بخع؛ انگل. integer linear programming, ILP) است که در آن تابع هدف و قیدها خطی هستند. برخلاف برنامهریزی خطی که متغیرها میتوانند هر مقدار حقیقی بپذیرند، الزام به صحیح بودن متغیرها، مسائل بع را به مراتب پیچیدهتر میکند[2].
برنامهریزی عددصحیح کاربرد گستردهای در اقتصاد، لجستیک، برنامهریزی تولید و سایر حوزههایی دارد که متغیرها ذاتاً گسستهاند (مانند تعداد واحدهای تولیدشده یا شمار کارکنان)[3].
تعریف و اصطلاحشناسی
مسئله کلی برنامهریزی خطی عددصحیح را میتوان به صورت زیر نوشت:
یافتن بردار که:
- را بیشینه (یا کمینه) کند
با قیدهای:
- (همه مؤلفههای بردار اعداد صحیح هستند)
در اینجا بردار متغیرها، و بردارها، و ماتریس ضرایب است[4].
بسته به الزامات مربوط به متغیرها، انواع مسائل زیر تمایز داده میشوند:
- برنامهریزی کاملاً عددصحیح: همه متغیرها باید صحیح باشند.
- برنامهریزی آمیخته-عددصحیح (انگل. mixed-integer programming, MIP): تنها بخشی از متغیرها باید صحیح باشند.
- برنامهریزی بولی (0-1): متغیرها تنها مقادیر 0 یا 1 میپذیرند که امکان مدلسازی تصمیمهای منطقی از نوع «بله/خیر» را فراهم میکند.
ویژگیهای کلیدی و پیچیدگی
پیچیدگی محاسباتی
مسئله برنامهریزی خطی عددصحیح در حالت کلی NP-سخت است[5]. این بدان معناست که هیچ الگوریتم شناختهشدهای وجود ندارد که بتواند جواب بهینه دقیق را برای یک مسئله دلخواه بع در زمان چندجملهای بیابد. این پیچیدگی ناشی از ماهیت ترکیباتی مسئله است، زیرا تعداد جوابهای صحیح ممکن میتواند با افزایش تعداد متغیرها به صورت نمایی رشد کند.
ارتباط با برنامهریزی خطی (آرامسازی بخ)
برای هر مسئله بع میتوان آرامسازی خطی آن را تدوین کرد — یعنی یک مسئله برنامهریزی خطی (بخ) که در آن الزام صحیح بودن متغیرها حذف شده است. جواب آرامسازی بخ دو ویژگی مهم دارد:
- میتوان آن را به مراتب سریعتر (در زمان چندجملهای) یافت.
- مقدار بهینه تابع هدف در آرامسازی بخ، یک کران (کران بالا برای مسئله بیشینهسازی و کران پایین برای کمینهسازی) برای مقدار بهینه مسئله عددصحیح اصلی فراهم میکند[2].
اما گرد کردن ساده جواب کسری آرامسازی بخ به نزدیکترین اعداد صحیح، به طور معمول به جواب بهینه یا حتی جواب شدنی مسئله عددصحیح منجر نمیشود[1].
ویژگی تکمدولاری کامل
دسته مهمی از مسائل بخع وجود دارد که به همان آسانی آرامسازیهای بخ آنها قابل حل هستند. این مسائل، مسائلی هستند که ماتریس قیدهای آنها کاملاً تکمدولار است (یعنی دترمینان هر زیرماتریس مربعی آن برابر 0، +1 یا −1 است). اگر ماتریس کاملاً تکمدولار و بردار صحیح باشد، تمام رأسهای چندوجهی جوابهای شدنی آرامسازی بخ به صورت خودکار صحیح خواهند بود. در نتیجه، جوابی که با روش سیمپلکس یافت میشود، صحیح خواهد بود[4]. مسئله حملونقل و مسئله انتساب نمونههایی از این دسته مسائل هستند.
روشهای حل
برای حل مسائل کلی بع که ویژگی تکمدولاری کامل را ندارند، روشهای دقیقی بر پایه ایده شمارش ضمنی توسعه یافتهاند.
- روش شاخه و کران (انگل. Branch and Bound) — روش دقیق اصلی که بر پایه تقسیمبندی سیستماتیک مجموعه جوابهای شدنی به زیرمجموعهها (شاخهزنی) و حذف زیرمجموعههایی است که به یقین جواب بهینه را در بر ندارند. برای ارزیابی امیدوارکنندگی زیرمجموعهها از آرامسازی بخ استفاده میشود[6].
- روش صفحات برشی (روش گومری؛ انگل. Cutting Plane Method) — رویکردی تکراری که به صورت متوالی قیدهای خطی جدیدی («برشها») به مسئله اضافه میکند. این برشها جوابهای کسری آرامسازی بخ را «میبرند» بدون اینکه هیچ جواب شدنی صحیحی را حذف کنند، و به تدریج ناحیه جوابهای شدنی آرامسازی بخ را به پوشش محدب جوابهای صحیح نزدیک میکنند[6].
حلکنندههای مدرن معمولاً از الگوریتمهای ترکیبی مانند روش شاخه و برش (انگل. Branch and Cut) استفاده میکنند که مزایای هر دو رویکرد را با هم ترکیب میکند.
نمونهها و حوزههای کاربرد
برنامهریزی عددصحیح امکان مدلسازی بسیاری از مسائل کلاسیک بهینهسازی ترکیباتی را فراهم میکند.
- مسئله کولهپشتی: مسئله کلاسیک برنامهریزی 0-1 که در آن باید مجموعهای از اقلام با بیشترین ارزش کلی انتخاب شود بدون اینکه محدودیت وزن کلی نقض گردد.
- مسئله فروشنده دورهگرد: مسئله یافتن کوتاهترین مسیری که از مجموعهای معین از شهرها میگذرد. میتوان آن را به عنوان مسئله برنامهریزی عددصحیح صورتبندی کرد که در آن متغیرها مسئول گنجاندن یالهای گراف در مسیر نهایی هستند.
با توجه به انعطافپذیری بالای خود، بع یکی از پرکاربردترین ابزارها در تحقیق در عملیات است و در حوزههایی مانند:
- لجستیک و مدیریت زنجیره تأمین: بهینهسازی مسیرهای حملونقل، مکانیابی انبارها، مدیریت موجودی.
- برنامهریزی تولید: تهیه برنامههای تولید، تخصیص منابع، بارگذاری تجهیزات.
- مالی و اقتصاد: تشکیل سبد سرمایهگذاری، بودجهبندی سرمایهگذاری.
- مخابرات و انرژی: طراحی شبکههای ارتباطی، برنامهریزی کار واحدهای نیرو.
کاربرد دارد.
همچنین ببینید
- برنامهریزی خطی
- روش شاخه و کران
یادداشتها
[1] [2] [3] [4] [5] [6] </references>
- ↑ 1.0 1.1 1.2 "Целочисленное программирование". Википедия. [۱]
- ↑ 2.0 2.1 2.2 Wolsey, Laurence A. (2020). Integer Programming (2nd ed.). John Wiley & Sons.
- ↑ 3.0 3.1 Писарук Н.Н. (2010). Модели и методы смешанного целочисленного программирования. Минск: БГУ.
- ↑ 4.0 4.1 4.2 Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). Integer Programming. Springer.
- ↑ 5.0 5.1 Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: Complexity of Computer Computations. Springer.
- ↑ 6.0 6.1 6.2 "Integer programming". Wikipedia. [۲]