Redigerer Simplex-algoritmen (avsnitt)

== Revidert simplex-algoritme ==

=== Matriseversjon av simplex-algoritmen ===
I enhver iterasjon i simplex-algoritmen kan beskrives med formelen:
: <math>
  \begin{bmatrix}
    1 & \mathbf{c}_B \mathbf{B}^{-1}\mathbf{A}  -\mathbf{c} & \mathbf{c}_B \mathbf{B}^{-1} \\
    0 & \mathbf{B}^{-1}\mathbf{A} & \mathbf{B}^{-1}
  \end{bmatrix}
  \begin{bmatrix}
    Z \\ \mathbf{x} \\ \mathbf{x}_s
  \end{bmatrix} = 
  \begin{bmatrix}
    \mathbf{c}_B \mathbf{B}^{-1} \mathbf{b} \\ \mathbf{B}^{-1}\mathbf{b}
  \end{bmatrix}
</math>
der <math>\mathbf{c}_B</math> er koeffisienten av basisvariabene i '''c'''-matrisen; og '''B''' er <math>[\mathbf{A} \, \mathbf{I}]</math> som korresponderer med basisvariablene.

Det er viktig å merke seg at '''B''' og <math>\mathbf{c}_B</math> er de eneste variable i denne ligningen (unntatt ''Z'' og '''x'''). Alt annet er konstant gjennom algoritmen.

=== Algoritme ===
* Velg en startverdi for BF som vist over
: Dette betyr at '''B''' er identitetsmatrisen, og <math>\mathbf{c}_B</math> er en null-vektor.

* Gjenta til man har en optimal løsning:
** '''Finn retningen med størst [[gradient]]'''
*: Velg den variabelen som er assosiert med koeffisienten i <math>\mathbf{c}_B \mathbf{B}^{-1}\mathbf{A}  -\mathbf{c}</math> som har mest ''negativ''. Denne ikke-basisvariabelen, som vi kaller ''innbasis'', skal økes for å maksimalisere problemet.
** '''Velg maksimal skrittlengde'''
*: Bruk ligningen <math>\begin{bmatrix} \mathbf{B}^{-1}\mathbf{A} & \mathbf{B}^{-1} \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \mathbf{x}_s \end{bmatrix} =  \mathbf{B}^{-1}\mathbf{b}</math> for å bestemme hvilken basisvariabel som først går til null når ''innbasis'' økes. Denne variabelen som vi kaller ''utbasis'' blir ikke-basisvariabel. Denne operasjonen innebærer en divisjon for hver basisvariabel fordi de eksisterende basisvariablene er på diagonalen.
** '''Omskriv problemet'''
*: Modifiser '''B''' og <math>\mathbf{c}_B</math> for å ta hensyn til de nye basisvariablene. Dette vil sette de nye og gamle basisvariablene på diagonalen.
** '''Verifiser forbedring'''
*: Gjenta prosedyren til ingen ytterligere forbedring er mulig, slik at alle koeffisientene i <math>\mathbf{c}_B \mathbf{B}^{-1}\mathbf{A}  -\mathbf{c}</math> er positive. Prosedyren termineres også dersom alle koeffisientene er null eller dersom algoritmen har gått i sirkel og man har kommet til en tidligere tilstand.

<!-- Usynlig tekst start
{{uoversatt2|engelsk}}

== Description ==

[[Fil:Simplex description.png|thumb|240px|A series of linear inequalities defines a [[polytope]] as a feasible region. The simplex algorithm begins at a starting [[vertex]] and moves along the edges of the polytope until it reaches the vertex of the optimum solution.]]

A linear programming problem consists of a collection of [[linear]] inequalities on a number of [[real number|real]] [[variable]]s and a fixed linear functional which is to be maximized (or minimized). Some further details are given in the linear programming article.

In geometric terms we are considering a [[closed]] [[convex]] polytope P, defined by intersecting a number of half-spaces in ''n''-dimensional [[Euclidean space]], which lie to one side of a [[hyperplane]]. The objective is to maximise a linear functional L; if we consider the hyperplanes H(c) defined by L(x) = c as c increases, these form a parallel family. If the problem is well-posed, we want to find the largest value of c such that H(c) intersects P (if there is no such largest value of c, this isn't a reasonable question for optimization as it stands). In this case we can show that the optimum value of c is attained, on the boundary of P. Methods for finding this optimum point on P have a choice of improving a possible point by moving through the interior of P (so-called ''interior point methods''), or starting and remaining on the boundary.

The simplex algorithm falls into the latter class of method. The idea is to move along the facets of P in search of the optimum, from point to point. Note that the optimum cannot occur at a mid-point, for example in the middle of an edge lying as a line segment on the boundary of P, unless the whole relevant 'face' is parallel to H. Therefore it is possible to look solely at moves skirting the edge of a [[simplex]], ignoring the interior. The algorithm specifies how this is to be done.

We start at some vertex of the polytope, and at every iteration we choose an adjacent vertex such that the value of the objective function does not decrease. If no such vertex exists, we have found a solution to the problem. But usually, such an adjacent vertex is nonunique, and a ''pivot rule'' must be specified to determine which vertex to pick. Various pivot rules exist.

In [[1972]], Klee and Minty{{rf|1|Greenberg}} gave an example of a linear programming problem in which the [[polytope]] P is a distortion of an ''n''-dimensional cube. They showed that the simplex method as formulated by Dantzig visits all 2<sup>''n''</sup> vertices before arriving at the optimal vertex. This shows that the worst-case complexity of the algorithm is [[exponential time]]. Similar examples have been found for other pivot rules. It is an open question if there is a pivot rule with [[polynomial time]] worst-case complexity.

Nevertheless, the simplex method is remarkably efficient in practice. Attempts to explain this employ the notion of average complexity or (recently) smoothed complexity.

Other algorithms for solving linear programming problems are described in the [[linear programming#algorithms|linear programming]] article.

Usynlig tekst slutt -->