تمرین شبیه سازی، درس طراحی شبکه با متلب

تمرین بخش بهینه سازی طراحی

هدف از این تمرین، استفاده از دانش بدست آمده در این بخش برای فرموله‌بندی چند مسئله طراحی بصورت مسئله بهینه‌سازی است. در این تمرین صرفا فرموله‌بندی مسئله مدنظر است. برای حل این مسایل می توان از ابزارهای نرم‌افزاری برای حل مسایل بهینه‌سازی استفاده کرد و برای این منظور باید زبان اسکریپت مربوط به آنها باید فراگرفته شود. محیط متلب نیز محیط مناسبی برای اینکار می‌باشد و Optimization Toolbox آن را می توان بکار برد. در فعالیت مجزایی با محیط متلب آشنا خواهید شد. لذا حل مسایل فرموله شده در این تمرین مدنظر نمی‌باشد. کتاب مربوط به Optimization Toolbox را می توانید از لینک زیر بدست آورید و در بخش مراجع آورده شده است:http://www.mathworks.com/help/pdf_doc/optim/optim_tb.pdf

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

مفروضات مسئله:

شبکه به صورت یک گراف G=(V,E) مدل می شود که E مجموعه یال ها و V مجموعه گره ها است. ظرفیت هر یال c_e است. D درخواست یا جریان ترافیکی وجود دارد. یک جریان دلخواه را با اندیس d نشان می دهیم که d برابر ۱ تا D است. هر جریان را با یک نرخ ترافیک موثر h_d تعریف می‌شود که برابر پهنای باند موثر موردنیاز آن جریان است. هر جریان تنها در صورتی پذیرفته می شود که شبکه کل پهنای باند موردنیاز آن را بتواند تامین کند. در غیر اینصورت جریان رد شده و پذیرفته نمی شود. پذیرش یک جریان سود یا درآمدی معادل b_d را برای شبکه به دنبال خواهد داشت. بنابراین هدف اصلی این است که بیشترین تعداد درخواست‌ها پذیرفته شود. به عبارتی هدف بیشینه‌سازی سود یا درآمد شبکه با توجه به محدودیت‌های موجود است. محدودیت‌ها نقش اصلی در نحوه فرموله‌سازی مسئله و خروجی حاصل از آن بازی می کنند. در زیر سه حالت مختلف از تعریف مسئله را بررسی می کنیم. در هر مورد پارامترهای بهینه‌سازی (خروجی های حاصله از حل مسئله) را بطور صریح مشخص کنید. بکاربردن این روش‌ها برای حل مسایل باز مطرح در شبکه‌سازی می‌تواند منجر به خروجی‌های پژوهشی و مقالات قابل ارائه در کنفرانس ها و مجلات گردد. برخی از مقالاتی که در این درس مطالعه کرده اید نمونه ای از خروجی‌های پژوهشی با استفاده از این روش ها می باشند.

الف) در ابتدا فرض می کنیم منابع شبکه (لینک ها و ظرفیت ها) ثابت هستند و قابل تغییر نیستند. بعلاوه بعنوان یک محدودیت اضافی فرض می کنیم کل یک جریان باید از یک مسیر ارسال شود و یک جریان قابل تقسیم و توزیع در مسیرهای مختلف نیست. مسئله پیدا کردن بیشترین سود را در این حالت به روش Node-Link مدل نمایید.

ب) در اینجا محدودیت قابل تقسیم نبودن جریان ها را تعدیل می کنیم. فرض می کنیم برای هر جریان d ، p_d مسیر کاندیدا وجود دارد و ترافیک آن جریان می‌تواند بین آن مسیرها توزیع شود. مسئله پیدا کردن بیشترین سود را در این حالت به روش Link-Path مدل نمایید.

ج) در اینجا محدودیت ثابت بودن منابع شبکه را حذف می کنیم. فرض می‌کنیم امکان افزایش ظرفیت برخی از لینک های موجود و حتی اضافه کردن لینک های جدید وجود دارد. به عبارت دیگر امکان بازطراحی و توسعه شبکه وجود دارد. مجموعه لینک‌هایی که امکان تغییر ظرفیت آنها وجود دارد را E1، مجموعه لینک‌هایی که قابل افزایش به همبندی شبکه می باشند را با E2 و مجموعه لینک‌هایی که امکان تغییر ظرفیت آنها وجود ندارد را با E3 نشان می دهیم. قاعدتا افزایش ظرفیت و افزودن لینک هزینه اضافی در بر دارد. هر لینک اضافی هزینه ثابت α برای نصب فیزیکی را در دارد. هزینه هر واحد ظرفیت اضافی در لینک های موجود یا جدید نیز برابر β است. هدف این است که در مجموع سودی که از پذیرش درخواست ها بدست می آید با در نظر گرفتن هزینه افزایش ظرفیت و نصب یال‌ها بیشینه شود. با استفاده از روش Link-Path مدلی برای مسئله ارائه نمایید.