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)

see also:


[Examples]

  automatically generated 4/24/2007