Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 16

Let P be a polyhedron and x* ∈ P. The point x* is an extreme point if and only if x* is a vertex and x* is a basic admissible solution.

DEFINITION 1.5.– Let P be a polyhedron. A vector x ∈ P is an extreme point of P if it cannot be expressed as a convex combination of two other points of P.

DEFINITION 1.6.– Let P be a polyhedron. A vector x ∈ P is a vertex of P if there exists c such that

for every y in P not equal to x.

THEOREM 1.2.– In linear programming, if the admissible domain is neither empty nor the whole of ℝn, it is a convex polytope with finitely many vertices that can either be bounded or unbounded. If an extreme point exists, it is attained at one of the vertices of the polytope. A point in the interior of the domain is never an extreme point if f ≠ 0. If the polytope is bounded, f attains both a minimum and a maximum on it.

This theorem gives us a graphical solving method.