Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online lexicon:

Finding an Admissible 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
An admissible basic solution for a linear program

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

with $ \left( b_1,\, \ldots,\,b_m \right)\geq 0$ can be determined by solving the auxiliary linear program

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

For this problem,

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

is an admissible basic solution, which can be used to start the simplex algorithm.

A solution $ \left(x,\, y \right)$ of the auxiliary problem yields an admissible basic solution for the original problem if $ y=0$. If, on the other hand, $ y \neq 0$, the original problem has no admissible points.

(Authors: Höllig/Pfeil/Walter)

Example:

[Links]
  automatically generated 4/24/2007