بخشی از پاورپوینت
اسلاید 1 :
بنام خدا
برنامه ریزی خطی پیشرفته (21715(
Advanced Linear Programming
اسلاید 2 :
برنامه ریزی خطی پیشرفته (21715 (
روش یا الگوریتم های نقاط داخلی یکی از روش های متداول برای حل مساله های بهینه سازی
انجام تحقیقات بسیار در این زمینه تاکنون
عملکرد فوق العاده این روش ها برای حل مساله های برنامه ریزی خطی در دهه های گذشته
انجام تحقیقات برای یافتن کاربردهای این روش برای حل مساله های برنامه ریزی غیر خطی در حال حاضر
اسلاید 3 :
برنامه ریزی خطی پیشرفته (21715 (
جستجو برای پیدا کردن جواب بهینه در داخل منطقه موجه در این روش ها برخلاف الگوریتم سیمپلکس
نام گذاری این روش ها با عنوان non-simplex method
روش عمومی حل
آغاز حل مساله از یک نقطه از داخل منطقه موجه و حرکت به سمت گوشه بهینه برخلاف حرکت به روی مرزها در روش سیمپلکس
اسلاید 4 :
برنامه ریزی خطی پیشرفته (21715 (
روش اولیه- دوگان نوعی از روش نقاط داخلی
اولین تحقیق: کارمارکار در سال 1984
جذب علاقه دانشمندان تحقیق در عملیات به روش نقطه های داخلی به دلایل:
پیچیدگی روش بصورت چند جمله ای
نتایج فوق العاده در آزمایش های مقدماتی
اسلاید 5 :
برنامه ریزی خطی پیشرفته (21715 (
مشاهده مقاله های متعددی در این زمینه در ژورنال های معتبر
ابداع روش های متنوع با پیچیدگی از درجه چند جمله ای
مثال: پیچیدگی الگوریتم کارمارکار بصورت O(nL)
ارایه درجه پیچیدگی برابر برای بهترین الگوریتم ابداع شده برای حل مساله های برنامه ریزی خطی در این زمینه
اسلاید 6 :
برنامه ریزی خطی پیشرفته (21715 (
ارزیابی عملکرد الگوریتم ابداع شده بر اساس زمان حل آنها (تعداد عملیات) برای مساله های واقعی
عملکرد بهتر الگوریتم های primal-dual path following و primal and dual affine methods نسبت به سایر الگوریتم ها
نبود روش مناسب دیگر برای ارزیابی این الگوریتم ها
امکان وجود الگوریتم هایی با پیچیدگی محاسباتی غیر چند جمله ای با عملکرد بهتری نسبت به الگوریتم های چند جمله ای در حل مساله های واقعی
اسلاید 7 :
برنامه ریزی خطی پیشرفته (21715 (
مثال
ارایه الگوریتم Ellipsoid با درجه پیچیدگی چند جمله ای در سال 1979
عملکرد بسیار ضعیف محاسباتی الگوریتم
اسلاید 8 :
برنامه ریزی خطی پیشرفته (21715 (
تعاریف
ماتریس Diagonal: ماتریس مربعی است که تنها مقادیر قطر اصلی آن غیر صفر باشند.
اسلاید 9 :
برنامه ریزی خطی پیشرفته (21715 (
تقسیم بندی الگوریتم های موجود برای حل مساله های بهینه سازی به کمک الگوریتم های نقاط داخلی:
Affine scaling methods
Path following methods
Potential reduction method
Projective methods
مشاهده تقسیم بندی های دیگر در مرجع های مختلف
اسلاید 10 :
برنامه ریزی خطی پیشرفته (21715 (
Affine scaling methods
ساده ترین روش الگوریتم های نقطه های داخلی
انتقال مساله به روش “affine scaling”
توسعه مدل پس از روش کارمارکار به منظور ساده سازی آن
مشابهت روش به الگوریتم سیمپلکس
اسلاید 11 :
برنامه ریزی خطی پیشرفته (21715 (
Path following methods
جستجو برای جواب بهینه در نزدیکی مرزها
اساس روش: استفاده از barrier method
اسلاید 12 :
برنامه ریزی خطی پیشرفته (21715 (
Potential reduction method
در این روش ها سعی می شود تا کاهشی در بعضی از توابع و یا مکان های ممکن ایجاد شود.
اسلاید 13 :
برنامه ریزی خطی پیشرفته (21715 (
Projective methods
در این روش ها که الگوریتم کارمارکار متعلق به آن است به نوعی یک elaborate projective transformation انجام می شود.
اسلاید 14 :
برنامه ریزی خطی پیشرفته (21715 (
Affine scaling methods
یک مساله برنامه ریزی خطی و دوگان آن را در نظر بگیرید:
فرض ها:
P فضای موجه مساله اولیه
x یک نقطه موجه داخلی مربوط به این فضا
اسلاید 15 :
برنامه ریزی خطی پیشرفته (21715 (
Affine scaling methods
تجربه های قبلی: بهینه سازی مساله در یک چند وجهی بسته بسیار مشکل تر از بهینه سازی مساله در یک منطقه موجه بیضی شکل
توسعه یک روش حل برای مساله بر پایه این نکته با حل مجموعه ای از مساله های بهینه سازی با منطقه موجه بیضی شکل
آغاز حل مساله با یک نقطه موجه داخلی مساله X0 > 0 و ایجاد یک بیضی مانند S0 به مرکزیت X0 داخل منطقه موجه
اسلاید 16 :
برنامه ریزی خطی پیشرفته (21715 (
Affine scaling methods
بهینه سازی مساله در فضای S0 و پیدا کردن نقطه جدید مانند X1
انتخاب نقطه X1 به عنوان مرکز بیضی جدید و انجام مجدد فرایند قبلی
اسلاید 17 :
برنامه ریزی خطی پیشرفته (21715 (
Affine scaling methods
تعبیر دیگر
آغاز حل مساله از یک نقطه موجه داخلی
تبدیل مساله برنامه ریزی خطی به مساله معادلی که در آن نقطه جاری مساله در حالت اولیه به روش steepest descent method به صورتی انتقال داده می شود که در منطقه موجه مساله تبدیل یافته در نزدیکی مرکز منطقه موجه قرار بگیرد.
فرض کنید روی یک نقطه موجه داخلی مربوط به مساله اولیه هستیم.
اسلاید 18 :
برنامه ریزی خطی پیشرفته (21715 (
مساله های برنامه ریزی غیر خطی: استفاده از روش نیوتن برای تعیین جهت حرکت به سمت جواب بهینه
در مساله های برنامه ریزی خطی از آنجا که جهت گرادیان همواره ثابت است (برابر با ضرایب تابع هدف) مقادیر ماتریس هیشین برابر با صفر بوده و لذا جهت نیوتن قابل تعریف نیست.
در این حالت جهت –C جهتی است که دارای سریع ترین کاهش در مقدار تابع هدف است.
اسلاید 19 :
برنامه ریزی خطی پیشرفته (21715 (
به منظور حفظ موجه بودن، این جهت به روی فضای ماتریس A تصویر می شود.
اگر رتبه ماتریس A برابر با تعداد سطرها باشد، تصویر بردار گرادیان به روی منطقه موجه حاصل از ماتریس A از رابطه زیر بدست می آید:
P = I – AT(AAT)-1A
تصویر بردار گرادیان در منطقه موجه برابر است با:
Cp = -Pc
اسلاید 20 :
برنامه ریزی خطی پیشرفته (21715 (
این جهت جهت موجه ای است که دارای بیشترین نرخ کاهش در مقدار تابع هدف است.
اگر نقطه کنونی نزدیک به مرکز منطقه موجه باشد می توان انتظار بهبود قابل توجه ای در صورت حرکت در جهت تعیین شده داشت.
