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

14,400,000 ریالریال 18,000,000

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


در این اثر، علاوه بر معرفی مدل‌های کلاسیک، روش‌های خطی‌سازی، تکنیک‌های افزایش کارایی مدل‌ها، الگوریتم‌های شاخه‌وکران، شاخه‌وبرش، شاخه‌وقیمت، برنامه‌ریزی پویا و برنامه‌ریزی محدودیتی به‌صورت جامع تشریح شده‌اند. همچنین مباحث پیچیدگی محاسباتی، الگوریتم‌های تقریب و کاربردهای عملی آن‌ها همراه با آموزش مدل‌سازی و پیاده‌سازی مسائل در نرم‌افزارهای 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