فهرست مطالب

فصل 1. مدل‌سازی مسائل با IP 1
1 - 1 مقدمه 1
1 - 2 دسته‌بندی انواع مسائل IP 2
1 - 3 مدل‌سازی مسائل با IP/MIP 5
1 - 4 انواع متغیرهای تصمیم‌گیری در یک مسئلۀ برنامه‌ریزی عدد صحیح 7
1 - 5 استفاده از انواع متغیرها در مدل‌سازی مسائل IP 8
1 - 6 انواع محدودیت‌های خاص در مدل‌سازی IP 16
1 - 7 محدودیت‌های فصلی 30
1 - 8 مدل‌سازی نواحی غیرمحدب 30
1 - 9 برنامه‌ریزی محدودیت 32
خودآزمایی 42

فصل 2. مدل‌های معروف در MIP/IP 47
2 - 1 مقدمه 47
2 - 2 مسئلۀ فروشندۀ دوره‌گرد (TSP) 47
2 - 3 مسئله مسیریابی خودرو (VRP) 53
2 - 4 مسئلۀ مکان‌یابی تجهیزات 56
2 - 5 مسئلۀ طراحی سیستم توزیع چندکالایی 59
2 - 6 مسائل مرتبط با عناصر یک مجموعه 61
2 - 7 مسائل شبکه 68
خودآزمایی 73

فصل 3. روش‌های آزادسازی خطی، شاخه و کران 79
3 - 1 مقدمه 79
3 - 2 حل مسائل IP با آزادسازی خطی 79
3 - 3 روش شاخه و کران برای حل مسائل IP/MIP 84
3 - 4 روش B&B برای مسائل با ابعاد بزرگ 91
خودآزمایی 98
فصل 4. روش‌های حل مسائل صفر و یک 103
4 - 1 مقدمه 103
4 - 2 الگوریتم بالاش برای حل مسائل صفر و یک 103
4 - 3 مسئلۀ کوله‌پشتی 108
4 - 4 حل مسئلۀ صفر و یک با ابعاد بزرگ با روش PCJ 115
خودآزمایی 126

فصل 5. روش صفحات برش 131
5 - 1 مقدمه 131
5 - 2 برش کسری گموری 133
5 - 3 نکات موجود در نامعادلۀ برش سادۀ گموری 137
5 - 4 برش گموری برای مسئلۀ برنامه‌ریزی عدد صحیح مخلوط 141
5 - 5 کاربرد نظریۀ گروه‌ها در تولید برش مسئلۀ برنامه‌ریزی عدد صحیح 143
5 - 6 روش برش تمام‌صحیح/ برش دوگان 151
خودآزمایی 164

فصل 6. آزادسازی لاگرانژ در حل مسائل IP 169
6 - 1 مقدمه 169
6 - 2 آزادسازی لاگرانژ در مسائل LP 169
6 - 3 آزادسازی لاگرانژ در مسائل IP 171
خودآزمایی 188

فصل 7. روش‌های بندرز، تولید ستون، شاخه و برش، شاخه و قیمت 193
7 - 1 مقدمه 193
7 - 2 روش تجزیۀ بندرز برای حل مسائل MIP 194
7 - 3 روش تولید ستون برای حل مسائل بزرگ LP 204
7 - 4 روش شاخه و برش برای حل مسائل بزرگ IP 212
7 - 5 روش شاخه و قیمت برای حل مسائل بزرگ IP 218
7 - 6 روش شاخه و قیمت برای مسئلۀ تخصیص تعمیم‌یافته 219
خودآزمایی 225

پیوست 231
مراجع 237
واژه‌نامه 241
فهرست راهنما 243



پیشگفتار
برنامه‌ریزی عدد صحیح یکی از شاخه‌های تخصصی برنامه‌ریزی ریاضی است که از اوایل دهۀ شصت میلادی موردتوجه ویژه قرار گرفته است و امروزه در بسیاری از جنبه‌های نظری و کاربردی سایر شاخه‌های مهندسی و علوم و فنون نیز استفاده می‌شود. اگرچه در ایران نيز برنامه‌ریزی خطی قدمتی بیش از نیم قرن دارد، تنها در حدود یک دهۀ اخیر، برنامه‌ریزی عدد صحیح به‌عنوان یک حوزۀ پژوهشی اهمیت یافته است. هنگامی‌که حدود بیست سال پیش برای نخستین بار درس برنامه‌ریزی عدد صحیح را به‌عنوان درسی مستقل و مجزا از تئوری شبکه در دانشکده مهندسی صنایع دانشگاه صنعتی شریف تدریس کردم، درخلال تدریس این درس خلاء وجود یک کتاب درسی به زبان فارسی به شدت احساس می‌شد. به این منظور کتاب حاضر که حاصل بیش از دو دهه پژوهش و تدریس این درس در مقاطع کارشناسی ارشد و دکتری است، تألیف شد. این کتاب شامل هفت فصل اصلی است؛ در فصل اول، مدل‌سازی مسائل در قالب برنامه‌ریزی عدد صحیح توضیح داده شده است. فصل دوم به بررسی برخی مدل‌های معروف در برنامه‌ریزی عدد صحیح و کاربردهای آن می‌پردازد. در فصل سوم، روش‌های آزادسازی خطی، شاخه و کران برای حل مسائل برنامه‌ریزی عدد صحیح بحث می‌شود. چون مسائل برنامه‌ریزی ریاضی با متغیرهای صفر و یک از اهمیت خاصی برخوردارند، فصل چهارم به این دسته از مسائل و روش‌های حل آن اختصاص یافته است. در فصل پنجم به ‌تفصیل دربارۀ یکی دیگر از روش‌های مهم حل مسائل برنامه‌ریزی عدد صحیح به‌نام روش صفحات برش توضیح داده می‌شود. آزاد‌سازی لاگرانژ یکی از روش‌های متداول برای حل برخی از مسائل این حوزه است که در فصل ششم مورد بررسی قرار می‌گیرد. در فصل هفتم روش‌های تجزیۀ بندرز، تولید ستون‌، شاخه و برش و شاخه و قیمت که همگی از روش‌های معروف حل هستند، بحث و بررسی می‌شوند. کتاب علاوه بر تشریح مدل‌های متعدد، شامل‌ تعداد بسیاری مثال حل‌شده و همچنین تمرین‌هایی است که در پایان هر فصل برای استفادۀ هرچه بیشتر خوانندگان کتاب فراهم شده است. در پیوست کتاب نیز نرم‌افزار سیپلکس که قوی‌ترین نرم‌افزار موجود برای حل مسائل برنامه‌ریزی عدد صحیح در ابعاد بزرگ است توضیح داده شده است. بدیهی است ﻫﻴﺞ اﺛﺮ ﻋﻠﻤﻲ ﺑﺪون ﺗﻼش و ﻛﻮﺷﺶ ﺟﻤﻌﻲ اﻣﻜﺎن‌ﭘﺬﻳﺮ ﻧﻴﺴﺖ. در اﻳﻦ راه وﻇﻴﻔﺔ ﺧﻮد ﻣﻲ‌داﻧﻢ از همۀ دانشجویان کلاس درس برنامه‌ریزی عدد صحیح دانشکدۀ مهندسی صنایع دانشگاه صنعتی شریف که با نکات خود سعی در بهبود این اثر داشته‌اند، قدردانی کنم. همچنین از زحمات سرکار خانم مهندس زهراسادات حسن‌پور جسری که در آماده‌سازی پیوست کتاب همکاری کرده‌اند تشکر می‌شود. در پایان برخود لازم می‌دانم از آقای دکتر علی پورجوادی مدیرعامل محترم مؤسسه انتشارات علمی دانشگاه صنعتی شریف و سرکار خانم‌ مریم طاهریان مدیر محترم تولید و همچنین سرکار خانم‌ها: اشرف سراج و حمیده رسولی که در انتشار این اثر اهتمام ورزیدند قدردانی کنم. از خوانندگان عزیز خواهشمندم پیشنهادهای ارزشمند خود را برای غنی‌تر کردن مطالب کتاب در چاپ‌های بعدی از طریق نشانی eshghi@sharif.edu در میان بگذارند.