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
AI Thread Summary
The discussion centers on whether the simplex algorithm can be implemented to avoid cycling. It is noted that the standard approach uses the largest coefficient rule for selecting the entering variable, which can lead to cycling. Suggestions for alternative strategies include exploring "lexicographic ordering" and "Bland's Rule" as potential solutions. However, the original poster expresses difficulty in finding a definitive method to avoid cycling. The conversation highlights the need for further research on these strategies to understand their effectiveness in preventing cycling in the simplex algorithm.
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
 

Thread 'Family of lines that are at a distance of 5 from the origin'

I picked up this problem from the Schaum's series book titled "College Mathematics" by Ayres/Schmidt. It is a solved problem in the book. But what surprised me was that the solution to this problem was given in one line without any explanation. I could, therefore, not understand how the given one-line solution was reached. The one-line solution in the book says: The equation is ##x \cos{\omega} +y \sin{\omega} - 5 = 0##, ##\omega## being the parameter. From my side, the only thing I could...
View full post »

Thread 'Making the denominator of a certain fraction real'

Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top