optimal solution to the dual linear program, that is, it minimizes . 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 is an optimal BFS of the primal LP, and 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: 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 How to move from an optimal feasible solution to an optimal basic feasible solution. Paul Robin, Operations Research Stack Exchange. References Linear programming