Content deleted Content added
m →References: ce |
|||
Line 17:
The criss-cross algorithm is simpler than the simplex algorithm, because the criss-cross algorithm only has one-phase. Its pivoting rules are similar to the [[Bland's rule|least-index pivoting rule of Bland]].<ref name="Bland">
{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|number=2|month=May|year=1977|pages=103–107|url=http://www.jstor.org/stable/3689647|doi=10.1287/moor.2.2.103|jstor=3689647|MR=459599|ref=harv}}</ref> Bland's rule uses only [[sign function|sign]]s of coefficients rather than their [[real number#Axiomatic_approach|(real-number) order]] when deciding eligible pivots. Bland's rule selects an entering variables by comparing values of reduced costs, using the real-number ordering of the eligible pivots.<ref name="Bland"/><ref>Bland's rule is also related to an earlier least-index rule, which was proposed by Katta G. Murty for the [[linear complementarity problem]], according to {{harvtxt|Fukuda|Namiki|1994}}.</ref> Unlike Bland's rule, the criss-cross algorithm is "purely combinatorial", selecting an entering variable and a leaving variable by considering only the signs of coefficients rather than their real-number ordering.<ref name="FukudaTerlaky"/><ref name="TerlakyZhang"/>
==Description==
{{Expand section|date=April 2011}}
The criss-cross algorithm has been specified in many publications and implemented in many programming languages.
===Example===
Examples showing the criss-cross algorithm on a problem-instance have been published.
==Computational complexity: Worst and average cases==
| |||