simplexmetoden

The simplexmetoden, or simplex method, is an algorithm for solving linear programming problems. It seeks to maximize or minimize a linear objective function subject to linear constraints.

The method operates by moving along the edges of the feasible region, a convex polytope defined by the constraints, from one basic feasible solution to another. Because the objective is linear, an optimum, if it exists, lies at a vertex of the feasible region. The simplexmetoden exploits this by performing a sequence of pivot operations that improve the objective value at each step.

A problem is usually written in standard form: maximize c^T x subject to Ax ≤ b and x ≥ 0 (often converted to equalities with slack variables). At any step, a set of basic variables forms a vertex, while the remaining variables are nonbasic and set to zero. The algorithm iterates by selecting an entering variable (one with a favorable reduced cost) and a leaving variable (determined by a minimum ratio test to maintain feasibility), then pivoting to update the basic feasible solution. This can be carried out using either the primal or the dual form, and in a revised form that uses fewer computations.

Common variants include the two-phase simplex method, used when a feasible starting solution is not readily available, and the Big-M method, which incorporates artificial variables into the objective. The dual simplex method can be advantageous when the current solution remains feasible for the dual problem.

The simplexmetoden is widely used in operations research for problems such as production planning, transportation, scheduling, and resource allocation. It is efficient in practice but has exponential worst-case time; alternative polynomial-time methods exist, such as interior-point algorithms, which complement the simplex approach in large-scale problems.