A NEW METHOD FOR THE LINEAR ASSIGNMENT PROBLEM
محل انتشار: چهارمین کنفرانس ملی مهندسی صنایع
سال انتشار: 1384
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 2,259
فایل این مقاله در 11 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
IIEC04_098
تاریخ نمایه سازی: 7 مهر 1385
چکیده مقاله:
Suppose we are given a feasible solution for a linear assignment problem (AP). Is this solution an optimal solution for the given AP? In this paper we prove necessary and sufficient conditions of optimality for an AP solution. Then we present a new method for solving the AP. The method starts with a feasible solution and if possible improves it then tests its optimality. If optimality of the current solution cannot be confirmed it uses the Hungarian method to identify an optimal solution. The computational testing on those problems that we have solved without the need to use the Hungarian method in the form of operations counts instead of CPU time so that the results are largely independent of the computing environment supports (but does not prove) the hypothesis that the method runs in expected time 0(n**3) on the worst case problems. This is better than the Hungarian method that runs in O(n**4 ) time and is comparable with Lawler's implementation, a successive shortest path algorithm, of the Hungarian method with the complexity of O(n**3 ). One very important application of this method is in the traveling salesman
problem (TSP) tour improvements.
کلیدواژه ها:
AP necessary and sufficient conditions of optimality
نویسندگان
Mohammad Sabbagh
Department of Industrial Engineering and systems planning center Isfahan University of Technology
Batul Mahvash Mohammadi
Department of Industrial Engineering and systems planning center Isfahan University of Technology
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :