Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 19

Consider a system of m linear equations Ax = b with n variables (m ≤ n).

DEFINITION 1.7.– A basic solution of the system of equations Ax = b is obtained by setting n − m variables to zero and solving the system for the remaining p variables. The solution of the system of p equations in m unknowns is assumed to be unique. The n − p variables set to zero are said to be non-basic variables, and the p remaining variables are said to be basic variables. An LP admits, at most, basic solutions. If the basic solution also satisfies the non-negativity constraints, it is said to be a basic feasible solution.

DEFINITION 1.8.– A basic solution is said to be degenerate if at least one basic variable is zero. This type of solution is obtained when the number of lines passing through an extreme point is greater than the number of decision variables. A basic feasible solution whose m basic variables are positive is said to be a non-degenerate basic feasible solution.

REMARK.– Each basic feasible solution corresponds to an extreme point. However, there can be more than one basic feasible solution for the same extreme point. This occurs when the basic feasible solution is degenerate.

REMARK.– The number of basic solutions quickly becomes very large, even in modestly sized models. For example, a model in standard form with 12 constraints and 25 variables can have up to basic solutions.