Editing Linear programming (section)

== Theory ==

=== Existence of optimal solutions ===
Geometrically, the linear constraints define the [[feasible region]], which is a [[convex polytope]]. A [[linear functional|linear function]] is a [[convex function]], which implies that every [[local minimum]] is a [[global minimum]]; similarly, a linear function is a [[concave function]], which implies that every [[local maximum]] is a [[global maximum]].

An optimal solution need not exist, for two reasons. First, if the constraints are inconsistent, then no feasible solution exists: For instance, the constraints '''x'''&nbsp;≥&nbsp;2 and '''x'''&nbsp;≤&nbsp;1 cannot be satisfied jointly; in this case, we say that the LP is ''infeasible''. Second, when the [[polytope]] is unbounded in the direction of the gradient of the objective function (where the gradient of the objective function is the vector of the coefficients of the objective function), then no optimal value is attained because it is always possible to do better than any finite value of the objective function.

=== Optimal vertices (and rays) of polyhedra ===
Otherwise, if a feasible solution exists and if the constraint set is bounded, then the optimum value is always attained on the boundary of the constraint set, by the ''[[maximum principle]]'' for ''[[convex function]]s'' (alternatively, by the ''minimum'' principle for ''[[concave function]]s'') since linear functions are both convex and concave. However, some problems have distinct optimal solutions; for example, the problem of finding a feasible solution to a system of linear inequalities is a linear programming problem in which the objective function is the zero function (i.e., the constant function taking the value zero everywhere). For this feasibility problem with the zero-function for its objective-function, if there are two distinct solutions, then every convex combination of the solutions is a solution.

The vertices of the polytope are also called ''basic feasible solutions''. The reason for this choice of name is as follows. Let ''d'' denote the number of variables. Then the fundamental theorem of linear inequalities implies (for feasible problems) that for every vertex '''x'''<sup>*</sup> of the LP feasible region, there exists a set of ''d'' (or fewer) inequality constraints from the LP such that, when we treat those ''d'' constraints as equalities, the unique solution is '''x'''<sup>*</sup>. Thereby we can study these vertices by means of looking at certain subsets of the set of all constraints (a discrete set), rather than the continuum of LP solutions. This principle underlies the [[simplex algorithm]] for solving linear programs.