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