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

Lineares Programm

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
Ein lineares Programm ist ein Optimierungsproblem mit linearer Zielfunktion

$\displaystyle c^{\operatorname t} x\longrightarrow \min \,, $

linearen Gleichungsnebenbedingungen und nicht-negativen Unbekannten

$\displaystyle Ax=b \,, \quad x \geq 0 \,. $

Im Allgemeinen wird angenommen, dass die $ m \times n$-Matrix $ A$ vollen Rang $ m \leq n$ hat. Dies kann immer durch Entfernen redundanter Nebenbedingungen erreicht werden.

Allgemeine lineare Nebenbedingungen

$\displaystyle P y = q \,, \quad R y \leq s $

für Unbekannte $ y_i$ lassen sich durch Einführen zusätzlicher Variablen auf die obige Standardform bringen. Man schreibt $ y$ als Differenz zweier nicht-negativer Vektoren

$\displaystyle y=u-v \,, \quad u \geq 0 \,, \; v \geq 0 \,, $

und führt nicht-negative Schlupfvariablen $ w$ ein, um die Ungleichungsnebenbedingungen zu entfernen. Genauer wird $ Ry-s \leq 0$ durch

$\displaystyle Ry -s+w =0 \,, \quad w \geq 0 \,, $

ersetzt, wobei $ Ry = Ru - Rv$.

Beispiel:

[Verweise]
  automatisch erstellt am 19.  8. 2013