Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon:

Basislösung

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Für ein lineares Programm

$\displaystyle c^{\operatorname t} x \longrightarrow \min \,, \quad Ax = b \,, \; x \geq 0, $

mit einer $ m \times n$ Matrix $ A$ maximalen Ranges bezeichnet man $ x$ als eine Basislösung, falls ein Index-Vektor $ I \subset \left\{1,\,\ldots ,\, n\right\}$ der Länge $ m$ existiert, so dass $ A_I=A(:,I)$ invertierbar ist und

$\displaystyle x_k =0 \,, \quad k \notin I \,. $

Die Basislösung ist zulässig, falls

$\displaystyle x_I=A_I^{-1}b \geq 0\,, $

wobei $ x_I=x(I)$.

Die Indexmenge $ I$ legt die Basislösung $ x$ eindeutig fest. Sind jedoch Einträge von $ x_I$ Null, so können verschiedene Indexmengen derselben Basislösung entsprechen.

Beispiel:

[Verweise]
  automatisch erstellt am 19.  8. 2013