مدل‌سازی و روش‏های حل مسائل برنامه ‏ریزی عددصحیح

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


در این اثر، علاوه بر معرفی مدل‌های کلاسیک، روش‌های خطی‌سازی، تکنیک‌های افزایش کارایی مدل‌ها، الگوریتم‌های شاخه‌وکران، شاخه‌وبرش، شاخه‌وقیمت، برنامه‌ریزی پویا و برنامه‌ریزی محدودیتی به‌صورت جامع تشریح شده‌اند. همچنین مباحث پیچیدگی محاسباتی، الگوریتم‌های تقریب و کاربردهای عملی آن‌ها همراه با آموزش مدل‌سازی و پیاده‌سازی مسائل در نرم‌افزارهای GAMS، MATLAB، IBM ILOG CPLEX، LINGO، AIMMS  و Excel ارائه شده است.


وجود مثال‌های متعدد، تمرین‌های هدفمند و تأکید بر کاربردهای واقعی، این کتاب را به منبعی ارزشمند برای دانشجویان تحصیلات تکمیلی، پژوهشگران، استادان و مهندسان علاقه‌مند به بهینه‌سازی و تحقیق در عملیات تبدیل کرده است.

فصل اول: مروری بر مفاهیم پایه 1


1-1 مقدمه 1


1-2 تحقیق در عملیات.. 2


1-2-1 تاریخچه تحقیق در عملیات.. 2


1-2-2 انواع مسائل تحقیق در عملیات.. 3


1-2-3 برنامه‌‌ریزی ریاضی. 4


1-2-4 برنامه‌‌ریزی محدودیتی. 5


1-2-5 گامهای مدل‌سازی. 5


1-3 مروری بر مفاهیم ریاضی. 6


1-3-1 ماتریس و بردار 7


1-3-2 فضای اقلیدسی. 11


1-3-3 روش گاوس -جردن برای حل دستگاه معادلات خطی. 12


1-3-4 ترکیب‌‌های خطی و محدب.. 14


1-3-5 استقلال و وابستگی خطی. 15


1-3-6 رتبه ماتریس.. 16


1-3-7 تعیین استقلال یا وابستگی با روش گاوس-جردن. 18


1-3-8 دترمینان ماتریس.. 18


1-3-9 معکوس ماتریس.. 19


1-3-10 مشتق و گرادیان. 21


1-3-11 مفاهیم هندسی. 22


1-4 مقدمه‌‌ای بر برنامه‌‌ریزی عددصحیح. 27


1-5 نمادهای ریاضی به‌کاررفته 29


1-6 تمرینهای فصل اول. 29


فصل دوم: مدل‌های کلاسیک برنامه‌‌ریزی عددصحیح. 33


2-1 مقدمه 33


2-2 مسئله پوشش مجموعه‌‌ها 33


2-3 مسائل برش.. 35


2-3-1 مسئله برش یک‌بعدی. 37


2-3-2 مسئله برش دوبعدی. 38


2-4 مسئله فروشنده دوره‌‌گرد 39


2-4-1 اهمیت و جایگاه مسئله فروشنده دوره‌‌گرد 39


2-4-2 تبدیل مسائل به TSP. 40


2-4-2-1 کوتاه‌‌ترین مسیر همیلتونی. 41


2-4-2-2 TSP با امکان ملاقات مجدد شهر 43


2-4-2-3 مسئله TSP چندگانه 44


2-4-2-4 TSP خوشه‌‌بندی‌شده 46


2-4-3 مدل‌سازی مسئله TSP نامتقارن. 46


2-4-3-1 حذف زیرتور با محدودیت‌‌های DFJ 48


2-4-3-2 حذف زیرتور با محدودیت‌‌های MTZ. 49


2-4-2 فرمول‌‌بندی TSP متقارن. 50


2-5 مسئله مسیریابی وسیله نقلیه 53


2-6 مسائل انتخاب پروژه 56


2-6-1 مسئله کوله‌پشتی. 57


2-6-2 مسئله بودجه‌‌بندی سرمایه 59


2-7 مسائل برنامه‌‌ریزی تولید 59


2-7-1 اندازه انباشته نامحدود 60


2-7-2 اندازه انباشته محدود 61


2-8 مسائل زمان‌بندی نیروی کار تمام‌وقت و پاره‌وقت.. 64


2-8-1 زمان‌بندی نیروی کار تمام‌وقت.. 64


2-8-2 زمان‌بندی نیروی کار پاره‌وقت.. 66


2-9 مسائل زمان‌بندی تک‌ماشینه 67


2-10 کاربردهای مدل‌های برنامهریزی عددصحیح. 71


2-10-1 انواع مسائل توالی عملیات ماشین. 71


2-10-2 مسائل توالی عملیات در صنعت الکترونیک.. 73


2-10-3 مسئله مسیریابی وسیله نقلیه در تحویل و توزیع. 73


2-11 تمرینهای فصل دوم 74


فصل سوم: خطی‌‌سازی روابط غیرخطی. 81


3-1 مقدمه 81


3-2 تبدیل متغیرهای عدد صحیح به باینری. 81


3-3 تبدیل توابع خطی‌قطعه‌‌ای. 82


3-4 خطی‌‌سازی ضرب متغیرهای باینری. 87


3-5 خطی‌‌‌‌سازی ضرب متغیر باینری در پیوسته 87


3-6 سایر حالت‌‌های ضرب دو متغیر 87


3-7 مدل‌سازی محدودیت‌‌های غیرهمزمان. 89


3-7-1 محدودیت‌‌های «این یا آن». 90


3-7-2 برقراری p محدودیت از بین k محدودیت.. 90


3-8 خطی‌‌سازی تابع هدف کسری. 92


3-9 خطی‌‌سازی تابع قدرمطلق. 93


3-9-1 قدرمطلق در تابع هدف کمینه‌‌سازی. 94


3-9-2 قدرمطلق در تابع هدف بیشینه‌‌سازی. 94


3-9-3 قدرمطلق در سمت چپ محدودیت.. 94


3-9-4 قدرمطلق در سمت راست محدودیت.. 94


3-10 خطی‌‌سازی عملگر مجموع با کران متغیر 95


3-11 برنامه‌‌ریزی خطی متوالی. 96


3-12 خطیسازی ضرب دو متغیر به روش مک‌کورمیک.. 100


3-13 تمرین‌‌های فصل سوم 103


فصل چهارم: افزایش کارایی مدل‌های برنامهریزی عددصحیح. 107


4-1 مقدمه 107


4-2 در مدل‌های برنامهریزی خطی. 107


4-3 در مدل‌های عددصحیح. 108


4-3-1 تعداد متغیرها در یک مدل IP. 109


4-3-2 تعداد محدودیت‌‌ها در یک مدل IP. 111


4-4 پیش‌‌پردازش‌‌های مدل‌های ریاضی. 118


4-5 کاهش دامنۀ متغیرها 120


4-5-1 حدود در متغیرهای پیوسته 120


4-5-2 حدود در متغیرهای عمومی صحیح. 121


4-5-3 حدود در متغیرهای باینری. 123


4-5-4 تثبیت متغیرها، حذف محدودیت‌‌های زائد و تعیین امکان‌‌ناپذیری. 125


4-6 پیش‌‌پردازش‌‌های مخصوص مدل‌های باینری محض... 127


4-6-1 تثبیت متغیرهای باینری. 127


4-6-2 شناسایی محدودیت‌‌های زائد و امکان‌‌ناپذیر 129


4-6-3 کاهش دامنه محدودیت (یا کاهش ضرایب) 130


4-6-4 گرد کردن با تقسیم بر بزرگ‌ترین مقسومٌ‌علیه مشترک.. 132


4-7 تجزیه یک مسئله به مسائل مستقل. 132


4-8 مقیاس‌بندی ماتریس ضرایب.. 134


4-9 تمرینهای فصل چهارم 134


فصل پنجم: روش شاخه‌و‌کران. 137


5-1 مقدمه 137


5-2 روش شاخه‌و‌کران. 138


5-3 مراحل الگوریتم شاخه‌و‌کران. 140


5-4 مراحل الگوریتم 141


5-5 مثالهای روش شاخه‌و‌کران. 143


5-6 تمرینهای فصل پنجم 159


فصل ششم: روش صفحات برشی. 163


6-1 مقدمه 163


6-2 روش صفحه برش گموری. 163


6-2-1 ایجاد محدودیت برشی عدد صحیح محض (کسری) 165


6-2-2 ایجاد محدودیت برشی عددصحیح مختلط. 167


6-3 معرفی الگوریتم شمارش ضمنی (بالاس) 169


6-3-1 قواعد شاخه‌زنی. 170


6-3-2 گام‌های الگوریتم شمارش ضمنی. 171


6-4 تمرینهای فصل ششم 177


فصل هفتم: روش برنامهریزی پویا 181


7-1 مقدمه 181


7-2 معرفی مسئله کوتاه‌ترین مسیر (دلیجان) 182


7-3 مشخصه‌های مسئله برنامه‌ریزی پویا 183


7-4 به‌کارگیری برنامه‌ریزی پویا برای حل برنامه‌ریزی عددصحیح. 190


7-5 به‌کارگیری برنامه‌ریزی پویا برای حل مسائل برنامه‌ریزی خطی. 192


7-6 روش برنامه‌ریزی پویا برای مسئله زمان‌بندی تک‌ماشینه 195


7-7 تمرینهای فصل هفتم 200


فصل هشتم: روش شاخه و برش.. 205


8-1 مقدمه 205


8-2 مفاهیم پایه‌ای روش شاخه‌و‌برش.. 205


8-2-1 مراحل الگوریتم شاخه‌و‌برش.. 206


8-2-2 مراحل الگوریتم شاخه‌و‌برش.. 207


8-2-3 تولید برش‌های معتبر و پیش‌پردازش.. 208


8-3 نامعادلات معتبر 209


8-3-1 نامعادلات معتبر برای برنامه‌ریزی خطی. 209


8-3-2 نامعادلات معتبر برای برنامه‌ریزی عددصحیح. 209


8-3-3 انواع نامعادلات معتبر 211


8-4 روشهای تولید برش.. 212


8-4-1 روش گرد کردن. 212


8-4-2 روش تفکیک.. 213


8-4-3 روش برداشتن. 215


8-5 تولید برش از مجموعه‌های شامل متغیرهای عددصحیح محض... 215


8-5-1 برش کسری گموری. 215


8-5-2 برش گموری چواتال. 215


8-5-3 برش گردشده عددصحیح محض... 217


8-5-4 برش صحیح تابع هدف.. 218


8-6 تولید برش از مجموعه‌های شامل متغیرهای عددصحیح مختلط. 218


8-6-1 برش عددصحیح مختلط گموری. 218


8-6-2 برش گردشده عددصحیح مختلط. 222


8-7 تولید برش از مجموعه‌های کوله‌پشتی باینری. 223


8-7-1 پوشش کوله‌پشتی. 223


8-7-2 پوشش کوله‌پشتی برداشته‌شده 224


8-7-3 پوشش حد بالای عمومی (GUB) 227


8-8 تولید برش از مجموعه‌های شامل ضرایب و متغیرهای باینری. 228


8-9 تولید برش از مجموعه‌های با ساختارهای ویژه 231


8-9-1 پوشش جریانی از یک شبکه جریانی هزینه ثابت ساده 231


8-9-2 مکان‌یابی تسهیلات/کارخانه (حمل‌ونقل با هزینه ثابت) 232


8-10 تمرینهای فصل هشتم 234


فصل نهم: روش شاخه‌و‌قیمت (تولید ستون) 239


9-1 مقدمه 239


9-2 مفاهیم پایه‌ای تولید ستون. 240


9-3 روش تجزیه دانتزیگ-ولف.. 241


9-4 مسئله تخصیص تعمیم‌یافته 253


9-4-1 فرمول قراردادی. 253


9-4-2 به‌کارگیری روش تولید ستون. 254


9-5 الگوی شاخه‌زنی در GAP. 262


9-6 تأثیر عملیات کاهشی در تولید ستون. 264


9-7 رفتار ماشین‌های یکسان. 265


9-8 الگوریتم شاخه‌و‌قیمت.. 266


9-9 کاربردهای دیگر روش شاخه‌و‌قیمت.. 267


9-10 تمرینهای فصل نهم 268


فصل دهم: برنامهریزی محدودیتی. 271


10-1 مقدمه 271


10-2 کاربردهای برنامه‌ریزی محدودیتی. 273


10-3 تاریخچه برنامهریزی محدودیتی. 274


10-4 اصول کلی برنامه‌ریزی محدودیتی. 275


10-5 مدل‌سازی مسائل برنامهریزی محدودیتی. 276


10-5-1 محدودیت‌های برنامه‌ریزی محدودیتی. 277


10-5-2 انواع ساختمان داده‌ها 281


10-6 مسائل ارضای محدودیت و هم‌ارزی. 282


10-7 مثالهایی از مسائل ارضای محدودیت.. 285


10-7-1 مسئله رمز ریاضیات.. 286


10-7-2 مسئله n وزیر 288


10-7-3 معمای گورخر 289


10-7-4 مدار جمع‌کننده کامل. 292


10-8 ساختار حل مسائل برنامه‌ریزی محدودیتی. 293


10-8-1 رویه پیش‌پردازش.. 294


10-8-2 رویه خوشحال. 295


10-8-3 اتمیک.. 296


10-8-4 رویه تجزیه 296


10-8-5 رویه پیشروی بر اساس حالت‌ها 299


10-8-6 رویه انتشار محدودیت.. 302


10-8-6-1 الگوریتم‌های انتشار محدودیت.. 305


9-10مثالهایی از بهکارگیری رویهها در حل مسائل ارضای محدودیت.. 307


10-9-1 محدودیت‌های باینری. 307


10-9-2 محدودیت‌های چندجمله‌ای روی بازه‌های عددصحیح. 309


10-10 انواع سازگاریها و فیلترسازیها 315


10-10-1 سازگاری گره 316


10-10-2 سازگاری کمان. 317


10-10-3 سازگاری فوق کمان. 323


10-10-4 سازگاری کمان جهت‌دار 324


10-11 سازگاری مسیر 326


10-12 مقایسه برنامهریزی محدودیتی با تحقیق در عملیات.. 333


10-13 ترکیب برنامهریزی محدودیتی و برنامهریزی خطی. 334


10-14 مثالهایی از مسائل برنامهریزی محدودیتی با تابع هدف.. 336


10-14-1 مسئله حمل بار 337


10-14-2 مسئله فروشنده دورهگرد 341


10-14-3 مسئله بهینهسازی غیرخطی. 343


10-14-4 مسئله پیکربندی کامپیوتر 346


10-14-5 مسئله زمان‌بندی کارها روی ماشینهای موازی. 352


10-14-6 مسئله سکه‌ها 356


10-14-7 خط‌کش گلومب.. 357


10-15 تمرینهای فصل دهم 359


فصل یازدهم: پیچیدگی محاسباتی و الگوریتمهای تقریب.. 363


11-1 مقدمه 363


11-2 تحلیل الگوریتم‌ها 364


11-3 زمان چندجمله‌ای و شبه‌چندجمله‌ای. 365


11-4 نمایش پیچیدگی. 366


11-5 استفاده از حد برای تعیین پیچیدگی. 368


11-6 ترتیب.. 368


11-7 مسئله تصمیم و کنترل‌ناپذیری. 370


11-8 کلاسهای پیچیدگی. 370


11-9 مسائل بهینهسازی ترکیبیاتی. 375


11-10 تحلیل پیچیدگی مسئله زمان‌بندی Tmax|rj| . 376


11-11 تحلیل پیچیدگی مسئله . 379


11-12 تقریبپذیری و الگوریتمهای تقریب.. 382


11-13 تاریخچه الگوریتمهای تقریب.. 385


11-14روشهای تولید الگوریتمهای تقریب.. 386


11-14-1 ساختار دادن به ورودی. 388


11-14-2 ساختار دادن به خروجی. 389


11-14-3 ساختار دادن به اجرای الگوریتم 391


11-15 مسئله کولهپشتی. 394


11-15-1 الگوریتم برنامهریزی پویا 395


11-15-2 الگوریتم FPTAS. 396


11-16 مسئله دیرکرد وزندار روی تکماشین. 398


11-16-1 الگوریتم برنامهریزی پویا 399


11-16-2 الگوریتم FPTAS. 401


11-16-3 پیچیدگی و آزمون حد بدترین حالت الگوریتم 401


11-17 مسئله دیرکرد وزندار اریب روی تکماشین. 404


11-17-1 الگوریتم تقریب SPT. 406


11-17-2 الگوریتم برنامهریزی پویا 408


11-17-3 الگوریتم FPTAS. 411


11-17-3-1 آزمون حد بدترین حالت الگوریتم FPTAS3. 412


11-17-3-2 پیچیدگی الگوریتم FPTAS3. 414


11-18 تمرینهای فصل یازدهم 415


فصل دوازدهم: معرفی نرمافزارهای حل مسائل بهینهسازی. 419


12-1 مقدمه 419


12-2 نرمافزار GAMS. 420


12-2-1 معرفی نرم‌افزار گمز 420


12-2-2 معرفی دستورهای مدل‌سازی نرم‌افزار گمز 421


12-2-3 تنظیمات اصلی نرمافزار 425


12-2-4 مدل‌سازی مثال زمان‌بندی عملیات در محیط گمز 427


12-2-5 تنظیمات کاربردی نرم‌افزار گمز 431


12-3 نرم‌افزار MATLAB. 441


12-3-1 کدنویسی مسائل برنامه‌ریزی خطی و عددصحیح. 443


12-3-2 مدل‌سازی مثال زمان‌بندی عملیات در محیط متلب.. 447


12-4 نرمافزار EXCEL. 452


12-4-1 فعال‌سازی افزونه 452


12-4-2 محیط ابزار 454


12-4-3 مثال حل معادله درجه 2. 457


12-4-4 مدل‌سازی مثال زمان‌بندی تکماشینه در محیط اکسل. 459


12-4-5 سایر تنظیمات کاربردی نرم‌افزار اکسل. 464


12-5 نرمافزار IBM ILOG CPLEX. 468


12-5-1 مقدمه‌ای بر نرمافزار IBM ILOG CPLEX. 468


12-5-2 زبانهای قابل استفاده در CPLEX IDE. 469


12-5-2-1 زبان برنامه‌نویسی بهینه‌سازی OPL. 470


12-5-2-2 زبان اسکریپت‌نویسی. 470


12-5-2 کلیدواژهها و دستورهای پرکاربرد 470


12-5-3 آشنایی با محیط IDE CPLEX. 473


12-5-4 مدل‌سازی مثال زمان‌بندی عملیات در محیط ILOG. 473


12-5-5 مدل‌سازی مثال توالی عملیات در محیط IBM ILOG. 480


12-5-6 ارتباط IBM ILOG CPLEX با اکسل. 484


12-5-7 استفاده از Flow Control 486


8-5-12-1 فراخوانی و حل پروژه در Flow Control 487


8-5-12-2 حل تکرارشونده در Flow Control 487


12-5-8 تنظیمات کاربردی نرم‌افزار 489


12-6 نرمافزار LINGO. 497


12-6-1معرفی اولیه نرم‌افزار 497


12-6-2 صفحه اصلی نرم‌افزار 497


12-6-3 ساخت مدل جدید 498


12-6-4 عبارات ریاضی. 499


12-6-5 عبارات شرطی. 500


12-6-6 مجموعه‌ها 500


12-6-7 داده‌های ورودی به مدل. 502


12-6-8 توابع در نرم‌افزار لینگو 503


12-6-9 سایر ابزارهای نرم‌افزار Lingo. 504


12-6-10 مدل‌سازی مثال زمان‌بندی عملیات در محیط لینگو 509


12-6-11 تنظیمات کاربردی نرم‌افزار لینگو 512


12-7 نرمافزار AIMMS. 519


12-7-1 ساخت پروژه جدید 521


12-7-2 مدل‌سازی مثال توالی عملیات در محیط AIMMS. 532


12-7-3 تنظیمات کاربردی نرم‌افزار AIMMS. 537


12-8 تمرینهای فصل دوازدهم 540


سخن آخر..................................................................................................... 549


منابع.......................................................................................................... 553


واژه‌نامه فارسی به انگلیسی................................................................................ 557


واژه‌نامه انگلیسی به فارسی................................................................................ 563