simplexalgoritmen

The simplex algorithm is a widely used method for solving linear programming problems. Developed by George Dantzig in 1947, it is an iterative procedure that moves from one vertex of the feasible region to an adjacent vertex, improving the objective function value at each step. The feasible region in a linear programming problem is a convex polytope, and the optimal solution, if it exists, is guaranteed to occur at one of its vertices.

The algorithm begins at a basic feasible solution, which corresponds to a vertex of the feasible region. It then checks if the current solution is optimal by examining the coefficients of the objective function. If the solution is not optimal, the algorithm identifies an entering variable (a non-basic variable that can improve the objective function) and a leaving variable (a basic variable that must become non-basic to maintain feasibility). The algorithm then moves to the adjacent vertex by pivoting on these variables. This process is repeated until an optimal solution is found or it is determined that the problem is unbounded.

The simplex algorithm can be presented in a tabular form called the simplex tableau. The tableau contains the coefficients of the objective function and the constraints, and it is used to perform the pivoting operations. While the simplex algorithm is guaranteed to find the optimal solution for a bounded linear programming problem, its worst-case time complexity can be exponential. However, in practice, it is generally very efficient. Variations of the simplex algorithm, such as the dual simplex algorithm and the revised simplex algorithm, exist to address specific types of linear programming problems or improve computational efficiency.