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)

see also:

[Examples]
  automatically generated 4/24/2007