Editing Linear programming (section)

=== 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.