مدل ریاضی انتخاب تکنولوژی
f هزینه نصب تکنولوژی هست
هر تصمیم گیری ITS در رفتار کاربران تاثیر می گذارد
Ci,j هزینه ای است که کاربر K پرداخت می کند تا از مبدا i به مقصد j پرداخت می کند
Xi.j مسیر بین i , j هست
برای پیدا کردن مسیر از لاگرانژ استفاده می کنم
قید ها به دو دسته تقسیم می شود ( آسان و سخت )
مثال : متغیرصفر و یک برای الگوریتم های درختی (این متغیر برای این الگوریتم متغیر آسان است)
ولی اگر الگوریتم اگر حرکت باشد متغیر صفر و یک بدرد نمی خورد و در اینجا قید سخت محسوب می شود
در این مسایل هم قید های سخت را باید حذف کنیم
باید کرانی برای جواب پیدا کنیم
لاگرانژ به جای اینکه جواب دقیق پیدا کند یک جواب تقریبی برای مساله پیدا می کند
در اینجا فقط با یک قید سخت Complicated Constrained کار می کنیم
Ci,j هزینه سفر از i به j هست
Xi,j صفر یا یک می گیریم
لاگرانژ کمک می کند تا قید سخت را در این مسایل حذف کنیم
آزاد سازی لاگرانژ
فرض کنیم که لاندا مقدار جریمه باشد
با اضافه کردن ضریب جریمه لاندا در تابع هدف قید سخت را حذف می کنیم
تابع هدف که مینیمم سازی هزینه می خواست بکند
حالا با جریمه لاندا این قید های سخت را هم حذف می کنیم
حالا جریمه چقدر باشد تا جواب معقول بدست بیاوریم ؟
آیا مکانیزمی داریم که بعد از حذف قید های زاید جواب بهینه را پیدا کنیم ؟
بله لاندا را باید ثابت فرض کنیم
یک عدد ثابت را در یک تابع مینیمم سازی اضافه یا کم کنیم در جواب مساله تاثیر حاصل نمی شود
اول منفی لاندا تی را در نظر نمی گیریم
چجوری میشه لاندا را کم و زیاد کرد
آیا مقادیر بهینه لاندا را پیدا کرد؟
برای پاسخ به این سوال تست عددی را محاسبه می کنیم
در ابتدا لاندا را صفر در نظر می گیریم ( بدون در نظر گرفتن ترافیک یا شلوغی مسیر)
C1,6 : که مسیر ۱ به ۲ به ۴ به ۶ کوتاه ترین مسیر هست که با ۳ مسیر به مقصد می رسیم
T1,6 : ولی زمان سفر ۱۰+۱+۷ می باشد
حالا جریمه لاندا را اضافه می کنیم که به ازای لاندا مساوی ۱ با توجه به مقادیر ثابت یالها هزینه رسیدن به مقصد را پیدا می کنیم
(Ci,j+(Lamba)(Ti,j
همین کار را گسترش می دهیم با لاندا مساوی ۲ که می بینیم بهبودی مشاهده نمی شود
همین کار را برای مقادیر دیگر لاندا هم انجام میدهیم
در این شکل به ازای مقادیر مختلف لاندا هزینه های مسیر مشاهده می شود
اگر می توانستیم به ازای تمام مقادیر جریمه های لاندا جواب بهینه را پیدا کنیم ، خیلی خوب بود
ولی نمی توانیم تمام مقادیر لاندا را پیدا کنیم
پس لاندا را باید به صورت رندوم یا به صورت غیر خطی پیدا کنیم
اگر متناسب با L لاندا که یک عدد ثابت حقیقی هست جوابی را پیدا کنیم P جواب مساله می شود
در مساله لاگرانژین درسته که هدف ما ماکزیمم سازی L میو هست
اگر یک جواب بهینه پیدا کردیم که مساوی L میو شد بهترین حالت رخ داده است
ولی اگر پیدا هم نشد به عنوان جواب تقریبی قبول می کنیم
به عنوان homework مساله را با T=13 پیدا کنید
