convex polyhedron. If it is bounded, then it is a convex polytope. Each BFS corresponds to a vertex of this polytope. Basic feasible solutions for the dual problem As mentioned above, every basis B defines a unique basic feasible solution . In a similar way, each basis defines a solution to the dual linear program: minimize subject to . The solution is . Finding an optimal BFS There are several methods for finding a BFS that is also optimal. Using the simplex algorithm 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: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 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 increases until it reaches an optimal BFS. Converting any optimal solution to an optimal BFS 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. Finding a basis that is both primal-optimal and dual-optimal A basis B of the LP is called dual-optimal if the solution is an