A new network simplex algorithm to reduce consecutive‎ ‎degenerate pivots and prevent ‎stalling‎

سال انتشار: 1395
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 65

فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_IJIM-8-3_006

تاریخ نمایه سازی: 27 دی 1402

چکیده مقاله:

It is well known that in operations research‎, ‎degeneracy can cause a cycle in a network‎ ‎simplex algorithm which can be prevented by maintaining strong‎ ‎feasible bases in each pivot‎. ‎Also‎, ‎in a network consists of n arcs‎ ‎and m nodes‎, ‎not considering any new conditions on the entering‎ ‎variable‎, ‎the upper bound of consecutive degenerate pivots is equal‎ \left( ‎\begin{array}{c}‎ ‎n-m+k \\‎ ‎k \\‎ ‎\end{array}‎ ‎\right)‎ ‎where k is the number of degenerate arcs in the basis‎. ‎As‎ ‎well as‎, ‎the network simplex algorithm may stall if it goes through‎ ‎some long consecutive degenerate pivot‎. ‎Through conditions such as‎ ‎(LRC) and (LRS) upon entering variable rules‎, ‎this upper bound can‎ ‎be reduced to mn and m^۲ respectively‎. ‎In this current paper we‎ first suggest a new algorithm for anti--stalling in which a new‎ ‎condition is provided to the entering variable and then show that‎ ‎through this algorithm there are at most k consecutive degenerate ‎pivots.‎

نویسندگان

Z. ‎Aghababazadeh‎‎

Department of Mathematics‎, ‎Science and‎ ‎Research Branch, ‎Islamic Azad University‎, ‎Tehran‎, ‎Iran‎.

M. ‎Rostamy-‎Malkhalifeh‎‎

Department of Mathematics‎, ‎Science and‎ ‎Research Branch, ‎Islamic Azad University‎, ‎Tehran‎, ‎Iran‎.