Dec 102013
 

خلاصه درس حمل و نقل هوشمند – دکتر قطعی – ۹۲/۰۹/۱۹

الگوریتم بهترین مسیر بین دو گره
تلاش های متفاوتی در این زمینه انجام شده
ولی زمان زیادی می برد
باید در زمان معقول بدست بیاید

بهترین مقدار w را پیدا می کنیم
میو = ۱٫۵ پیشنهاد شده
دوباره برای این مسیر Cp و Tp را محاسبه کردم
خط جدیدی بدست آمده
فضای w که کران پاین با رنگ آبی نمایش داده شده ایت
لاگرانژ برابر ۲ شده در ضریب لاگرانژین گذاشتیم
مقدار لاگرانژین بهینه همان ۲ بدست می آید
بنابر این با ۲ بار تکرار لاگرانژ مساوی دیگر الگوریتم را متوقف می کنیم

its-lagrange

[image lagrange ]

سوال : ایا لاگرانژین ربطی به LP هم دارد یا نه
یک تئوری :
فرض می کنیم یک تابع خطی داریم که می خواهیم شبیه سازی کنیم
یا این مساله جواب بهینه دارد یا ندارد
اگر جواب بهینه داشته باشد مثلا عدد ۱۰۰ یا ۲۰۰ باشد
این امکان هست که یک نقطه گوشه ای وجود دارد که جواب بهینه باشد

its-extremePoints-Optimization

[image extreme points and optimization]

در مسایل شبکه نقاط گوشه ای جایشان را می دهند به مسیر ها

بنابراین ما مسیر ها را مانند گوشه ها در نظر می گیریم
در شبکه ها هم جواب بهینه مانند نقاط گوشه ای پیدا می شود مانند LP

در مسایل ITS انتخاب هایی گسسته داریم
یا به صورت Integer
پس فضای شدنی و فضای جواب به صورت چند وجهی نیست بلکه مانند نقاط گسسته داخل فضا هست

در شکل خارجی ترین نقاط را به هم وصل می کنیم تا شکل چند وجهی محدب بست بیاید

این چند وجهی به ما کمک می کند که جواب بهینه تقریبی را بدست بیاوریم
پس یک ارتباط دو طرفه برقرار می شود

در تئوری می توان ثابت کرد x1 تا xn نقاط راسی ما باشند بقیه نقاط به صورت ترکیبی از نقاط قابل نوشتن هست

its-convex-hulls

Convex Hulls

در لاگرانژین مینیمم سازی cx

مساله لاگرانژ تبدیل به مساله لاگرانژ روی نقاط راسی تبدیل می شود

در این حالت یک کران بالا برای w ها پیدا می شود
بهترین مقدار w با این شرایط محاسبه می شود
مقدار بهینه *L پیدا می شود
مقدار بهینه لاندا ها پیدا می شود

ITS-constraint-Generation

البته مسایل لاگرانژین بخاطر کاربرد های متنوعی که در بهینه سازی دارد خیلی ها به دنبال راهکار هایی برای بهبود هستند که الگوریتم های لاگرانژین محکم و مستدل هستند

 

با کلیک روی آگهی زیر مبلغ 400 ریال به حساب من واریز می گردد

با کلیک روی آگهی زیر مبلغ 1000 ریال به حساب من واریز می گردد