A Bound for the Number of Different Basic Solutions Generated by the Simplex Method

Mathematics – Optimization and Control

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Keywords: Simplex method, Linear programming, Iteration bound, Strong polynomiality, Basic feasible solutions

Scientific paper

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the primal problem is nondegenerate, it becomes a bound for the number of iterations. We show some basic results when it is applied to special linear programming problems. The results include strongly polynomiality of the simplex method for Markov Decision Problem by Ye and utilize its analysis.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

A Bound for the Number of Different Basic Solutions Generated by the Simplex Method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Bound for the Number of Different Basic Solutions Generated by the Simplex Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Bound for the Number of Different Basic Solutions Generated by the Simplex Method will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-333076

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.