بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بررسی روش زوتندیک در مسایل برنامه ریزی خطی
چکیده
یکی از مهمترین مسایل علم ریاضی برنامه ریزی خطی و کاربردهای آن می باشد. برای حل این گونه مسایل الگوریتم های نقطه درونی از سال 1984 مورد استفاده قرار گرفته اند. در این مقاله سعی می شود ایدۀ زوتندیک در حالت خطی مورد تجزیه و تحلیل قرار گیرد. اساس کار این الگوریتم شروع از یک نقطه اکیداً درونی در ناحیه شدنی و حرکت در جهت گرادیان تابع هدف است. حسن این روش و به طور کلی روش های نقطه درونی عدم نیاز به جواب های شدنی پایه ای برای شروع می باشد.
کلمات کلیدی: الگوریتم های نقطه درونی، برنامه ریزی خطی، ایدۀ زوتندیک
1 مقدمه
اگر چه هنوز هم روش سیمپلکس یکی از کاراترین روش های حل مسایل برنامه ریزی خطی محسوب می شود، اما این روش نمی تواند مرتبه پیچیدگی چند جمله ای را برای یافتن جواب بهینه تضمین کند. به طور متوسط در یک مساله با m قید، تعداد تکرارهای لازم جهت رسیدن به جواب بهینه 1/5 m است.[3]
اما کلی و مینتی (1972) دسته مسایلی را ارایه دادند که تعداد تکرارهای لازم برای رسیدن به جواب بهینه در مورد آن ها بسیار بیشتر از عدد فوق بود.[6] در (1984) الگوریتم کارمارکار که دارای مرتبه پیچیدگی چند جمله ای بود، برای حل این گونه مسایل ارایه شد.[4] این الگوریتم سرآغاز دسته بزرگی از الگوریتم ها گردید که معمولاً به نام الگوریتم های نقطه درونی شناخته می شوند. شروع کار این الگوریتم ها عموماً از یک نقطه شدنی است که این نقطه در فاز اول این روش ها به دست می آید. حرکت در جهت بردار گرادیان تابع هدف یک ایدۀ کلی برای حل مسایل برنامه ریزی خطی و غیر خطی است که توسط زوتندیک مورد بررسی قرار گرفت. این ایده در مسایل برنامه ریزی خطی به حرکت در جهت بردار c منتهی می شود. بنابراین بردار c در پیدا کردن جهت حرکت نقش اساسی را خواهد داشت.
در اینجا گذری به مفاهیم پایه ای که در ادامه مورد استفاده قرار می گیرند، خواهیم داشت.
در این مقاله یک مساله برنامه ریزی خطی به صورت زیر در نظر گرفته می شود.
که در آن c برداری n بعدی و b برداری m بعدی و ماتریس A ، (m n) بعدی خواهد بود. در نظر داشته باشید که قیود نامنفی را می توان به فرم بالا در مجموعه محدودیت ها گنجاند.
قضیه 1 جهت گرادیان محدودیت به طرف خارج ناحیه شدنی است و گرادیان تابع هدف بهترین جهت بهبود دهنده برای یک مساله LP به فرم بالاست.[2]
تبصره اگر مساله دارای جواب بهینه متناهی باشد حرکت در جهت c تا رسیدن به نقطه بهینه ادامه می یابد و اگر ناحیه شدنی مساله بیکران باشد حرکت در این جهت می تواند به طور نامحدود ادامه یابد که در این حالت مقدار تابع هدف به صورت نامحدود افزایش می یابد.
قضیه 2 برادر em همواره یک نقطه شدنی برای مساله برنامه ریزی خطی زیر خواهد بود:
که در آن منظور از بردار em برداری m بعدی است که همه مولفه های آن یک می باشند.[7]
