Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge

Mathematik-Online-Lexikon:

Hilfsproblem


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

Eine zulässige Basislösung für ein lineares Programm

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

mit $ \left( b_1,\, \ldots,\,b_m \right)\geq 0$ kann durch Lösen des Hilfsproblems

$\displaystyle y_1+\cdots + y_m \longrightarrow \min \,, \quad Ax+y=b \,,
\quad x,y \geq 0\,
$

bestimmt werden. Für dieses Problem ist

$\displaystyle \left( x^{\operatorname t} ,\, y^{\operatorname t} \right)=
\left( 0,\, b^{\operatorname t} \right)
$

eine zulässige Basislösung, die zum Start des Simplex-Algorithmus benutzt werden kann.

Eine Lösung $ \left(x,\, y \right)$ des Hilfsproblems entspricht einer zulässigen Basislösung für das Ausgangsproblem, falls $ y=0$ ist. Ist andererseits $ y \neq 0$, dann hat das Ausgangsproblem keine zulässigen Punkte.

Beispiel:


[Verweise]

  automatisch erstellt am 19.  8. 2013