Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag

Mathematics-Online lexicon:

Basic Solution


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 overview

For a linear program

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

with an $ m \times n$ matrix $ A$ of full rank, we call $ x$ a basic solution if there exists an index vector $ I \subset \left\{1,\,\ldots ,\, n\right\}$ of length $ m$, such that $ A_I=A(:,I)$ is invertible and

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

The basic solution is admissible if

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

($ x_I=x(I)$).

We note that the index set $ I$ determines the basic solution $ x$ uniquely. However, if not all entries of $ x_i$ are non-zero, different index sets can correspond to the same basic solution.

(Authors: Höllig/Pfeil/Walter)

Example:


[Links]

  automatically generated 4/24/2007