خلاصه درس حمل و نقل هوشمند – دکتر قطعی – ۹۲/۰۹/۱۹
الگوریتم بهترین مسیر بین دو گره
تلاش های متفاوتی در این زمینه انجام شده
ولی زمان زیادی می برد
باید در زمان معقول بدست بیاید
بهترین مقدار w را پیدا می کنیم
میو = ۱٫۵ پیشنهاد شده
دوباره برای این مسیر Cp و Tp را محاسبه کردم
خط جدیدی بدست آمده
فضای w که کران پاین با رنگ آبی نمایش داده شده ایت
لاگرانژ برابر ۲ شده در ضریب لاگرانژین گذاشتیم
مقدار لاگرانژین بهینه همان ۲ بدست می آید
بنابر این با ۲ بار تکرار لاگرانژ مساوی دیگر الگوریتم را متوقف می کنیم
[image lagrange ]
سوال : ایا لاگرانژین ربطی به LP هم دارد یا نه
یک تئوری :
فرض می کنیم یک تابع خطی داریم که می خواهیم شبیه سازی کنیم
یا این مساله جواب بهینه دارد یا ندارد
اگر جواب بهینه داشته باشد مثلا عدد ۱۰۰ یا ۲۰۰ باشد
این امکان هست که یک نقطه گوشه ای وجود دارد که جواب بهینه باشد
[image extreme points and optimization]
در مسایل شبکه نقاط گوشه ای جایشان را می دهند به مسیر ها
بنابراین ما مسیر ها را مانند گوشه ها در نظر می گیریم
در شبکه ها هم جواب بهینه مانند نقاط گوشه ای پیدا می شود مانند LP
در مسایل ITS انتخاب هایی گسسته داریم
یا به صورت Integer
پس فضای شدنی و فضای جواب به صورت چند وجهی نیست بلکه مانند نقاط گسسته داخل فضا هست
در شکل خارجی ترین نقاط را به هم وصل می کنیم تا شکل چند وجهی محدب بست بیاید
این چند وجهی به ما کمک می کند که جواب بهینه تقریبی را بدست بیاوریم
پس یک ارتباط دو طرفه برقرار می شود
در تئوری می توان ثابت کرد x1 تا xn نقاط راسی ما باشند بقیه نقاط به صورت ترکیبی از نقاط قابل نوشتن هست
Convex Hulls
در لاگرانژین مینیمم سازی cx
مساله لاگرانژ تبدیل به مساله لاگرانژ روی نقاط راسی تبدیل می شود
در این حالت یک کران بالا برای w ها پیدا می شود
بهترین مقدار w با این شرایط محاسبه می شود
مقدار بهینه *L پیدا می شود
مقدار بهینه لاندا ها پیدا می شود
البته مسایل لاگرانژین بخاطر کاربرد های متنوعی که در بهینه سازی دارد خیلی ها به دنبال راهکار هایی برای بهبود هستند که الگوریتم های لاگرانژین محکم و مستدل هستند