فهرست مقالات ‎ ‎Network simplex algorithm

• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  1 - A new network simplex algorithm to reduce consecutive‎ ‎degenerate pivots and prevent ‎stalling‎
  Z. ‎Aghababazadeh‎‎ M. ‎Rostamy-‎Malkhalifeh‎‎
  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&l چکیده کامل

  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^2$ 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.‎ پرونده مقاله