یکی از شاخه های جذاب و بین رشته ای که در بهینه سازی مطرح است بهینه سازی ترکبیاتی یا Combinatorial Optimization است. بسیاری از مسائل بهینه سازی را می توان با استفاده از این ابزار حل کرد حتی مسائلی را که ظاهر ترکبیاتی ندارد و شاید به شاخه های دیگر ریاضی نزدیک باشند.
در این پست  سعی در معرفی این شاخه دارم همچنین معرفی کتاب Network Flows، در بسیاری از کتاب های تحقیق در عملیات فصلی را به عنوان شبکه داریم ولی به جرعت می توان گفت کتاب حاضر یک از قدرتمند ترین کتاب های شبکه است که به طور خاص فقط به مبحث شبکه می پردازد و حاصل کار اساتید بزرگ دانشگاه دانشگاه MIT و دهلی است که به اختصار به کتاب AMO مشهور است.

Network Flows: Theory, Algorithms, and Applications


 

BA VINDRA K. AHUJADepartment of Industrial & Management Engineering
Indian Institute of Technology, Kanpur

Ravindra K. Ahuja, Department of industrial and systems engineering

 

THOMAS L. MAGNANTiSloan School of Management
Massachusetts Institute of Technology, Cambridge

Thomas L. Magnanti

 


JAMES B. ORLINSloan School of Management
Massachusetts Institute of Technology

  

James B. Orlin

 

لینک دانلود نسخه با قابلیت جستجوی لغات :

ifile.it

megaupload.com                        archive password: gigle.ws

fileserve.com                               archive password: ebooksclub.org

mediafire.com                             archive password: ebooksclub.org

لینک حل المسائل تمرین های فرد :

http://jorlin.scripts.mit.edu/Solution_Manual.html

این درس را در خدمت استاد (تمام) دکتر هاشمی تشکری بودیم که بزودی جواب تعدادی از تمرین های ضمن درس که از تمرین های زوج کتاب انتخاب شده قرار خواهم داد.

***

در زندگی امروزی به هر طرف که نگاه می کنیم شبکه های مختلف را مشاهده می کنیم.شبکه های نیرو و الکتریسیته که روشنایی و سرگرمی را به خانه های ما می آورند.شبکه تلفن که به ما اجازه برقراری ارتباط با یکدیگر می دهند حتی بدون کوچکترین تلاش ، ارتباط محلی و منطقه ای و حتی برون مرزی.سیستم های بزرگراهی شهری و بین المللی ، شبکه ریلی و شبکه های سرویس دهی هوایی وسایلی را فراهم نموده اند تا مسافت های طولانی را طی کنیم تا به کار و دیدن و عزیرانمان برسیم.بسط و توسعه شبکه های مختلف ما را قادر به دسترسی به لوازم مورد نیاز زندگی و کالا های مورد نیازمان می کند ، شبکه های کامپیوتری هم سهم بزرگی در ساخت و هدایت زندگی شخصی و کاری ما داشته اند.
در تمام مسائل شبکه ما مایل هستیم مقداری موجودی ( مثل الکتریسیته ، کالای مصرفی ، شخص یا وسیله نقلیه ، یک پیام ) را از نقطه ای به نقطه دیگر بکمک بستر شبکه موجود انتقال دهیم بطوری که این کار به کاراترین صورت ممکن انجام شود به این معنی که هم تامین خدمت مناسب برای کاربر شبکه و هم استفاده از تسهیلات بستر انتقالی شبکه ( که ممکن است پر هزینه هم باشد) به بهترین نحو انجام شود.
در بهینه سازی ترکبیاتی به دنبال مدل سازی تنظیمات شبکه واقعی به صورت موجودات ریاضیاتی شناخته شده در "مسائل جریان شبکه" هستیم تابتوانیم به کمک الگوریتم های مختلف مدل نتیجه شده فعلی را مورد مطالعه قرار دهیم و در نهایت بهترین تصمیم را در مورد تنظیمات شبکه بگیریم.
دامنه مسائل شبکه در راس چندین رشته مختلف تحقیقی شامل: ریاضی کاربردی ، علوم کامپیوتر ، مهندسی ، مدیریت و تحقیق در عملیات قرار دارد.
در تمام مسائل شبکه از "گراف" به عنوان ابزاری ریاضیاتی و کارا برای نشان دادن بسیاری از شبکه های فیزیکی استفاده می کنیم.
فعالیت های موجود در شبکه به سبک فعلی به دهه های 1940 و 1950 بر می گردد زمانی که بهینه سازی به عنوان شاخه تحقیقی مجزا توسعه پیدا کرد و با پیوستن به انقلاب کامپیوتری منجر به تشکیل ابزاری قدرتمند در حل محاسبات علمی و مدیریتی شد.


در سراسر این شاخه ما با سه دسته از مسائل روبرو هستیم:


مسئله کوتاهترین مسیر : بهترین مسیر برای رسیدن از نقطه ای از شبکه به نقطه دیگر چیست؟ ، طوریکه هزینه حرکت از هر مسیر در نظر گرفته شود.


مسئله بیشترین جریان : اگر هر مسیر ظرفیتی برای انتقال جریان داشته باشد بیشترین جریان ممکنی که می شود بین دو نقطه از شبکه انتقال داد چقدر است؟


مسئله جریان با کمترین هزینه : اگر همزمان هم هزینه و هم ظرفیت مسیر را لحاظ کنیم و نیاز داشته باشیم تا واحد هایی از کالا را از نقطه یا نقاطی از شبکه به نقطه یا نقاطی دیگر از شبکه انتقال دهیم چگونه می توانیم این کار را با کمترین هزینه انجام دهیم؟