بهینه سازی ترکیبیاتی یا بهینه سازی روی شبکه

یکی از شاخه های جذاب و بین رشته ای که در بهینه سازی مطرح است بهینه سازی ترکبیاتی یا 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

 

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

 

JAMES B. ORLINSloan School of Management
Massachusetts Institute of Technology

  

 

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

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 بر می گردد زمانی که بهینه سازی به عنوان شاخه تحقیقی مجزا توسعه پیدا کرد و با پیوستن به انقلاب کامپیوتری منجر به تشکیل ابزاری قدرتمند در حل محاسبات علمی و مدیریتی شد.

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

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

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

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

 

فروشنده دوره گرد

 راجع به مسئله فروشنده دوره گرد قبلا هم نوشته بودم این بار  می خواهم یکی از راه حل هایی که نه جواب اصلی(اپتیمال) بلکه جواب بهینه ای  را بدست میدهد مطرح کنم .

مسئله:
فروشنده دوره گردی می خواهد از شهر های متعددی دیدن کند و سپس به نقطه شروعش برگردد در صورتی که زمانهای مسافرت بین شهر ها(یا اینکه طول مسیرها) داده شده باشد، چطور او خط سیرش را طراحی کند که از هر شهر دقیقا یک بار عبور کند و کوتاه ترین زمان ممکن را برای مسافرت صرف کند ؟

بصورت نموداری هدف یافتن دور همیلتنی  با وزن مینیمم در یک گراف کامل  وزندار است . چنین دوری را یک دور اپتیمال می نامند.تا کنون الگوریتم  موثری برای یافتن جواب اصلی یافت نشده بنابراین مطلوب است روشی برای یافتن جواب خوب و معقولانه .

یک روش نسبی:
یک رهیافت ممکن آن است که اول دور همیلتنی C را بیابیم ، و سپس با اصلاحات  مناسب C یک دور همیلتنی دیگر با وزن کمتر جستجو کنیم.شاید ساده ترین اصلاح بصورت زیر باشد .
فرض کنیدC=V1,V2,….Vn  باشد در این صورت برای همه مقادیر i وj به طوری که n>j>i+1 >1 ، می توانیم دور همیلتنی جدید

Cij=V1,V2….Vi,Vj,Vj-1,….Vi+1,Vj+1,Vj+2….Vn,V1

را با حذف یالهای Vi,Vi+1 و Vj,Vj+1 و اضافه کردن یالهای Vi,Vj وVi+1,Vj+1 به صورتی که در شکل نشان داده شده به دست بیاوریم.

شکل (1)

اگر برای مقداری از i و j داشته باشیم( (w(Vi,Vj  منظور وزن یال Vi,Vj است):

W(Vi,Vj)+W(Vi+1,Vj+1) < W(Vi,Vi+1)+W(Vj,Vj+1)

دور Cij دور اصلاح شده ای از C خواهد بود.

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

مثلا گراف وزندار شکل 2 را در نظر بگیرید :

 

 

شکل (2)

با دورL  MC  NY  PA  PE  T  Lشروع می کنیم دنباله ای از 3 اصلاح را می توانیم به کار ببریم ، وبادورL  NY  MC  T   PE  PA  L  به وزن 192 کار را خاتمه می دهیم(شکل 3).

شکل (3)

دلیل درستی این روش را میتوان به زبان ساده چنین توضیح داد:
اگر راس V  را با دو یالی که از آن عبور می کند از دور اپتیمال حذف کنیم مسیری بدست می آید که 2 خصوصیت دارد 1. اینکه همبند و با حداقل یال است (درخت) 2. اینکه کمترین وزن را دارد.
حال اگر شرط مسیری بودن این درخت را هم حذف کنیم لا اقل این باقیمانده درختی با کمترین وزن است این درخت برای مثال زده شده در شکل4 نشان داده شده.

شکل (4)

وزن این درخت122است حال اگر با کمال خوش شانسی این درخت حالت مسیری هم داشته باشد ما برای اینکه به یک دور همیلتنی برسیم نیاز به اضافه کردن راس V با 2 یال که ازV  عبور می کنند به مسیر موجود هستیم اگر این یالها را هم از یالهای با کمترین وزن انتخاب کنیم به عدد 122+21+35=178 می رسیم . و چون وزن دوری که پیدا کرده بودیم لا اقل کران بالایی برای دور اپتیمال است پس داریم.

178 < W(C) < 192

و این اختلاف ناچیز بین دو کران خود گویای کار آمدی روش ماست.

روشی که در اینجا شرح دادیم بعدا به وسیله لین (1965) و هلد وکارپ(1970،1971) بسط یافت . بخصوص لین دریافت که شیوه اصلاح دور را می توان با قرار دادن 3 یال در یک زمان به جای دو یال موثر تر ساخت ، اما نکته شگفت آور اینکه بسط دادن بیشتر این ایده سودمند نیست.

مرجع :  باندی ، مورتی ، نظریه گراف و کاربردهای آن، ترجمه دارا معظمی