When using the simplex method , how do we know that the number of basic variables will be exactly equal to n+1?

1k Views Asked by At

A simplex is a polytope of n+1 extreme points in $R^n$.

In linear programming, the algorithm of the simplex method works by iteratively constructing simplexes. Each iteration involves both an entering variable, which has the largest reduced cost, and an exiting variable, which is the variable which must leave in order to allow all of the constraints to be satisfied, when the entering variable enters.

Eventually we find a simplex which corresponds to the optimal solution. Each simplex corresponds to a basic feasible solution, with each extreme point/vertex of the simplex corresponding to a basic variable.

(this implies that all simplexes have n+1 extreme points). My question is - how do we know that the solution will have exactly n+1 basic variables?

Edits this is the resource i have been using: https://www.youtube.com/watch?v=Ci1vBGn9yRc

1

There are 1 best solutions below

7
On

I'm not sure your understanding of the simplex method is correct. it iterates over the vertexs/extreme points of a given polytope (given by the constraints). One of those extreme points is the maximum/minimum because the polytope(like all polytopes) is convex.

A simplex does not have to have a certain number of extreme points. although it will have extreme points for all intersection of constraints that are feasible and only those, it however can be difficult to see which intersections will be feasible .