“Basic feasible solution”的意思、由来-开放百科全书

词条

Basic feasible solution

释义

Definition
Properties
Examples
Geometric interpretation
Application in the Simplex algorithm
References

In the theory of linear programming, a basic feasible solution (BFS) is, intuitively, a solution with a minimal number of non-zero variables. Geometrically, each BFS corresponds to a corner of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the simplex algorithm, which essentially travels from some BFS to another until an optimal one is found.^[1]

Definition

To define a BFS, we first present the linear program in the so-called equational form:

maximize

subject to and

where:

and are vectors of size n (the number of variables);
is a vector of size m (the number of constraints);
is an m-by-n matrix;
means that all variables are non-negative.

Any linear program can be converted into an equational form by adding slack variables.

As a preliminary clean-up step, we verify that:

The system has at least one solution (otherwise the whole LP has no solution and there is nothing more to do);
All m rows of the matrix are linearly independent, i.e., its rank is m (otherwise we can just delete redundant rows without changing the LP).

Typically m < n, so the system has many solutions; each such solution is called a feasible solution of the LP.

Let B be a subset of m indices from {1,...,n}. Denote by the square m-by-m matrix made of the m columns of indexed by B. If is nonsingular, the columns indexed by B are a basis of the column space of . In this case, we call B a basis of the LP.

Since the rank of is m, it has at least one basis;

since has n columns, it has at most bases.

Given a basis B, we say that a feasible solution is a basic feasible solution with basis B if all its non-zero variables are indexed by B, i.e., for all .

Properties

1. A BFS is determined only by the constraints of the LP (the matrix and the vector ); it does not depend on the optimization objective.

2. By definition, a BFS has at most m non-zero variables and at least n-m zero variables. A BFS can have less than m non-zero variables; in that case, it can have many different bases, all of which contain the indices of its non-zero variables.

3. A feasible solution is basic if-and-only-if the columns of the matrix are linearly independent, where K is the set of indices of the non-zero elements of . ^[1]{{rp|45}}

4. A BFS is uniquely determined by the basis B: for each basis B of m indices, there is at most one BFS with basis B. This is because must satisfy the constraint , and by definition of basis the matrix is non-singular, so the constraint has a unique solution. The opposite is not true: each BFS can come from many different bases.

If the unique solution of satisfies the non-negativity constraints, then the basis is called a feasible basis.

5. If a linear program has an optimal solution (i.e., it has a feasible solution, and the set of feasible solutions is bounded), then it has an optimal BFS. This is a consequence of the Bauer maximum principle: the objective of a linear program is convex; the set of feasible solutions is convex (it is an intersection of hyperspaces); therefore the objective attains its maximum in an extreme point of the set of feasible solutions.

Since the number of BFS-s is finite and bounded by , an optimal solution to any LP can be found in finite time by just evaluating the objective function in all BFS-s. This is not the most efficient way to solve an LP; the simplex algorithm examines the BFS-s in a much more efficient way.

Examples

Consider a linear program with the following constraints:

The matrix A is:

Here, m=2 and there are 10 subsets of 2 indices, however, not all of them are bases: the set {3,5} is not a basis since columns 3 and 5 are linearly dependent.

The set B={2,4} is a basis, since the matrix is non-singular.

The unique BFS corresponding to this basis is .

Geometric interpretation

The set of all feasible solutions is an intersection of hyperspaces. Therefore, it is a convex polyhedron. If it is bounded, then it is a convex polytope.

Each BFS corresponds to a vertex of this polytope. ^[1]{{rp|53-56}}

Application in the Simplex algorithm

The simplex algorithm keeps, at each point of its execution, a "current basis" B (a subset of m out of n variables), a "current BFS", and a "current tableau". The tableau is a representation of the linear program where the basic variables are expressed in terms of the non-basic ones: ^[1]{{rp|65}}

where is the vector of m basic variables, is the vector of n non-basic variables, and is the maximization objective. Since non-basic variables equal 0, the current BFS is , and the current maximization objective is .

If all coefficients in are negative, then is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies .

If some coefficients in are positive, then it may be possible to increase the maximization target. For example, if is non-basic and its coefficient in is positive, then increasing it above 0 may make larger. If it is possible to do so without violating other constraints, then the increased variable becomes basic (it "enters the base"), while another non-basic variable is decreased to 0 to keep the equality constraints and thus becomes non-basic (it "exits the base").

If this process is done carefully, then it is possible to guarantee that increases until it reachces the optimal BFS.

References

1. ^¹²³{{Cite Gartner Matousek 2006}}{{rp|44-48}}

1 : linear programming

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。