Is there a method for the simplex algorithm that avoids cycling?

  • Thread starter Thread starter wanderlust.xx
  • Start date Start date
  • Tags Tags
    Algorithm Method
Click For Summary
SUMMARY

The discussion centers on the simplex algorithm and its potential to avoid cycling through specific strategies. It highlights the use of the largest coefficient rule for selecting the entering variable, which can lead to cycling. To prevent this, the conversation suggests exploring "lexicographic ordering" and "Bland's Rule" as alternative methods. These strategies are essential for ensuring that the simplex algorithm converges without revisiting previous solutions.

PREREQUISITES
  • Understanding of the simplex algorithm and its standard implementation.
  • Familiarity with linear programming concepts.
  • Knowledge of "Bland's Rule" and its application in optimization.
  • Basic comprehension of "lexicographic ordering" in mathematical contexts.
NEXT STEPS
  • Research the implementation of "Bland's Rule" in the simplex algorithm.
  • Study "lexicographic ordering" and its role in avoiding cycling.
  • Explore alternative pivot rules in linear programming.
  • Examine case studies where cycling occurs in the simplex algorithm.
USEFUL FOR

Mathematicians, operations researchers, and students studying linear programming who seek to enhance their understanding of the simplex algorithm and its optimization techniques.

wanderlust.xx
Messages
3
Reaction score
0

Homework Statement



"There exists an implementation of the simplex algorithm that avoids cycling. (If your
answer is `yes', describe the strategy; if your answer is `no' give an example and explain
briefly why every strategy must fail.)"

The Attempt at a Solution



We normally do the simplex algorithm using the largest coefficient rule for the entering variable.

I would assume that to avoid cycling, we simply change this to another procedure, although I have tried to research this in both a book I have here and on the internet to no avail... I'm not sure how to go about doing this question! :(
 
Physics news on Phys.org
Look up "lexicographic ordering" and "Bland's Rule".

RGV
 

Similar threads

Simplex algorithm - phase one - why do I need to use it here?
  • · Replies 3 ·
Replies
3
Views
4K
C data structures and algorithms - graph problem
  • · Replies 2 ·
Replies
2
Views
2K
Python Partial pivoting in getting the reduced row echelon form of a matrix
  • · Replies 2 ·
Replies
2
Views
2K
Average complexity -- worst case of an algorithm
  • · Replies 8 ·
Replies
8
Views
2K
Graduate Matrix Exponential to Approximate the Value of Matrizant
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad The algorithms involved in finding a solution with numerical methods
  • · Replies 14 ·
Replies
14
Views
3K
Implementing Shift and Add Algorithm for 3D Reconstruction of X-ray Images
  • · Replies 1 ·
Replies
1
Views
3K
Programs How good is this applied math program?
  • · Replies 13 ·
Replies
13
Views
4K
Is Alan Turing given too much credit when it comes to computers?
  • · Replies 29 ·
Replies
29
Views
6K
Graduate Methods for capturing a Fabry-Perot Interference Pattern
  • · Replies 2 ·
Replies
2
Views
2K