توسعه يك الگوريتم نقطه مرزي براي حل مسائل برنامه‌ريزي خطي با جواب اوليه موجه

در اين تحقيق براي حل مسائل برنامه ريزي خطي، الگوريتم SALCHOW توسعه داده شده است كه در هرگام در جهت گراديان مقيد تابع هدف حركت مي‌كند به‌نوعي كه همواره روي مرز ناحيه موجه باقي مي‌ماند. اين نوع حركت بر روي مرز ناحيه موجه متفاوت با رفتار الگوريتم سيمپلكس است كه روي گوشه هاي فضاي موجه حركت ميكند. از سوي ديگر با رفتار الگوريتم هاي نقاط دروني هم كه از روي مرز فضاي موجه جدا شده و وارد آن مي شوند، نيز متفاوت است. در واقع SALCHOW با يافتن تدريجي ضرايب وزني براي مجموعه اي از قيدها و افزودن اين جمع وزن‌دار به گراديان تابع هدف، گراديان مقيد تابع هدف را بروزرساني مي‌كند؛ تا در نهايت ضرايب لاگرانژ قيود فعال در نقطه بهينه مسئله برنامه ريزي خطي را محاسبه كند. نتايج محاسباتي بر روي مجموعه اي از مسائل نمونه تصادفي توليد شده و چند مسئله استاندارد از پايگاه كتابخانه تحقيق در عمليات با اندازه كوچك نشان دهنده برتري زماني SALCHOW نسبت به سيمپلكس در اين مثالهاي محدود است. به اين معني كه متوسط زمان حل الگوريتم توسعه داده شده براي مسائل نمونه تابعي از تعداد متغيرهاي تصميم مسئله است. اين امر بر خلاف رفتار سيمپلكس است كه زمان اجراي آن در حالت متوسط، تابعي از تعداد قيدهاي مسئله است. وجود خطاي محاسباتي ناشي از گردكردن اعداد در محيط برنامه نويسي MATLAB امكان قضاوت در مورد برتري قاطع SALCHOW بر سيمپلكس را در حل مسائل كوچك سلب مي نمود.