[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki41\/basic-feasible-solution-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki41\/basic-feasible-solution-wikipedia\/","headline":"Basic feasible solution – Wikipedia","name":"Basic feasible solution – Wikipedia","description":"before-content-x4 In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set of","datePublished":"2022-10-24","dateModified":"2022-10-24","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki41\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki41\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/de7378018c528600ed390cda26c039e4a3e0ab95","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/de7378018c528600ed390cda26c039e4a3e0ab95","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki41\/basic-feasible-solution-wikipedia\/","about":["Wiki"],"wordCount":8903,"articleBody":" (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set 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] (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsDefinitions[edit]Preliminaries: equational form with linearly-independent rows[edit]Feasible solution[edit]Basis[edit]Basic feasible solution[edit]Properties[edit]Examples[edit]Geometric interpretation[edit]Basic feasible solutions for the dual problem[edit]Finding an optimal BFS[edit]Using the simplex algorithm[edit]Converting any optimal solution to an optimal BFS[edit]Finding a basis that is both primal-optimal and dual-optimal[edit]External links[edit]References[edit]Definitions[edit]Preliminaries: equational form with linearly-independent rows[edit]For the definitions below, we first present the linear program in the so-called equational form: (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4maximize cTx{textstyle mathbf {c^{T}} mathbf {x} }subject to Ax=b{displaystyle Amathbf {x} =mathbf {b} } and x\u22650{displaystyle mathbf {x} geq 0}where: (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Any linear program can be converted into an equational form by adding slack variables.As a preliminary clean-up step, we verify that:The system Ax=b{displaystyle Amathbf {x} =mathbf {b} } 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 A{displaystyle A} are linearly independent, i.e., its rank is m (otherwise we can just delete redundant rows without changing the LP).Feasible solution[edit]A feasible solution of the LP is any vector x\u22650{displaystyle mathbf {x} geq 0} such that Ax=b{displaystyle Amathbf {x} =mathbf {b} }. We assume that there is at least one feasible solution. If m = n, then there is only one feasible solution. Typically m < n, so the system Ax=b{displaystyle Amathbf {x} =mathbf {b} } has many solutions; each such solution is called a feasible solution of the LP.Basis[edit]A basis of the LP is a nonsingular submatrix of A, with all m rows and only mb{displaystyle mathbf {x_{B}} ={A_{B}}^{-1}cdot b} The opposite is not true: each BFS can come from many different bases. If the unique solution of xB=AB\u22121\u22c5b{displaystyle mathbf {x_{B}} ={A_{B}}^{-1}cdot b} satisfies the non-negativity constraints xB\u22650{displaystyle mathbf {x_{B}} geq 0}, then B 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 (nm){displaystyle {binom {n}{m}}}, an optimal solution to any LP can be found in finite time by just evaluating the objective function in all (nm){displaystyle {binom {n}{m}}}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[edit]Consider a linear program with the following constraints:x1+5x2+3x3+4x4+6x5=14x2+3x3+5x4+6x5=7\u2200i\u2208{1,\u2026,5}:xi\u22650{displaystyle {begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\forall iin {1,ldots ,5}:x_{i}&geq 0end{aligned}}}The matrix A is:A=(1534601356)\u00a0\u00a0\u00a0\u00a0\u00a0b=(14\u00a0\u00a07){displaystyle A={begin{pmatrix}1&5&3&4&6\\0&1&3&5&6end{pmatrix}}~~~~~mathbf {b} =(14~~7)}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 AB=(5415){displaystyle A_{B}={begin{pmatrix}5&4\\1&5end{pmatrix}}} is non-singular.The unique BFS corresponding to this basis is xB=(0\u00a0\u00a02\u00a0\u00a00\u00a0\u00a01\u00a0\u00a00){displaystyle x_{B}=(0~~2~~0~~1~~0)}.Geometric interpretation[edit] 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]:\u200a53\u201356\u200aBasic feasible solutions for the dual problem[edit]As mentioned above, every basis B defines a unique basic feasible solution xB=AB\u22121\u22c5b{displaystyle mathbf {x_{B}} ={A_{B}}^{-1}cdot b} . In a similar way, each basis defines a solution to the dual linear program:minimize bTy{textstyle mathbf {b^{T}} mathbf {y} }subject to ATy\u2265c{displaystyle A^{T}mathbf {y} geq mathbf {c} }.The solution is yB=ABT\u22121\u22c5c{displaystyle mathbf {y_{B}} ={A_{B}^{T}}^{-1}cdot c}.Finding an optimal BFS[edit]There are several methods for finding a BFS that is also optimal.Using the simplex algorithm[edit]In practice, the easiest way to find an optimal BFS is to use the simplex algorithm. It 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]:\u200a65\u200axB=p+QxNz=z0+rTxN{displaystyle {begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}end{aligned}}}where xB{displaystyle x_{B}} is the vector of m basic variables, xN{displaystyle x_{N}} is the vector of n non-basic variables, and z{displaystyle z} is the maximization objective. Since non-basic variables equal 0, the current BFS is p{displaystyle p}, and the current maximization objective is z0{displaystyle z_{0}}.If all coefficients in r{displaystyle r} are negative, then z0{displaystyle z_{0}} is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies z\u2264z0{displaystyle zleq z_{0}}.If some coefficients in r{displaystyle r} are positive, then it may be possible to increase the maximization target. For example, if x5{displaystyle x_{5}} is non-basic and its coefficient in r{displaystyle r} is positive, then increasing it above 0 may make z{displaystyle z} larger. If it is possible to do so without violating other constraints, then the increased variable becomes basic (it “enters the basis”), while some basic variable is decreased to 0 to keep the equality constraints and thus becomes non-basic (it “exits the basis”).If this process is done carefully, then it is possible to guarantee that z{displaystyle z} increases until it reaches an optimal BFS.Converting any optimal solution to an optimal BFS[edit]In the worst case, the simplex algorithm may require exponentially many steps to complete. There are algorithms for solving an LP in weakly-polynomial time, such as the ellipsoid method; however, they usually return optimal solutions that are not basic.However, Given any optimal solution to the LP, it is easy to find an optimal feasible solution that is also basic.[2]:\u200asee also “external links” below.\u200aFinding a basis that is both primal-optimal and dual-optimal[edit]A basis B of the LP is called dual-optimal if the solution yB=ABT\u22121\u22c5c{displaystyle mathbf {y_{B}} ={A_{B}^{T}}^{-1}cdot c} is an optimal solution to the dual linear program, that is, it minimizes bTy{textstyle mathbf {b^{T}} mathbf {y} }. In general, a primal-optimal basis is not necessarily dual-optimal, and a dual-optimal basis is not necessarily primal-optimal (in fact, the solution of a primal-optimal basis may even be unfeasible for the dual, and vice versa).If both xB=AB\u22121\u22c5b{displaystyle mathbf {x_{B}} ={A_{B}}^{-1}cdot b} is an optimal BFS of the primal LP, and yB=ABT\u22121\u22c5c{displaystyle mathbf {y_{B}} ={A_{B}^{T}}^{-1}cdot c} is an optimal BFS of the dual LP, then the basis B is called PD-optimal. Every LP with an optimal solution has a PD-optimal basis, and it is found by the Simplex algorithm. However, its run-time is exponential in the worst case. Nimrod Megiddo proved the following theorems:[2]There exists a strongly polynomial time algorithm that inputs an optimal solution to the primal LP and an optimal solution to the dual LP, and returns an optimal basis.If there exists a strongly polynomial time algorithm that inputs an optimal solution to only the primal LP (or only the dual LP) and returns an optimal basis, then there exists a strongly-polynomial time algorithm for solving any linear program (the latter is a famous open problem).Megiddo’s algorithms can be executed using a tableau, just like the simplex algorithm.External links[edit]References[edit] (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki41\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki41\/basic-feasible-solution-wikipedia\/#breadcrumbitem","name":"Basic feasible solution – Wikipedia"}}]}]