Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Optimization Methods and Applications
Minati De
Department of Mathematics, Indian Institute of Technology Delhi, India.
Lecture 3: Introduction to LP (contd.)
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Table of Contents
1 Graphical Representation and Solution
2 Polyhedra and Convex Set
3 Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
What does the feasible region of an LP look like?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
What does the feasible region of an LP look like?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Table of Contents
1 Graphical Representation and Solution
2 Polyhedra and Convex Set
3 Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Hyperplane
Hyperplane
Let a be a nonzero vector in Rn and let b be a scalar.
The set {x ∈ Rn |aT x = b} is called a hyperplane.
Example:?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Halfspace
Halfspace
Let a be a nonzero vector in Rn and let b be a scalar.
The set {x ∈ Rn |aT x ≥ b} is called a Halfspace.
Example:?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Polyhedron
Polyhedron
A polyhedron is a set that can be decribed in the form
{x ∈ Rn |Ax ≥ b}, where A is an m × n matrix and b is a vector in
Rm .
Example:?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Polyhedron
Polyhedron
A polyhedron is a set that can be decribed in the form
{x ∈ Rn |Ax ≥ b}, where A is an m × n matrix and b is a vector in
Rm .
Example:
The feasible set of any linear programming problem can be
described by inequality constraints of the form of Ax ≥ b, and
is therefore a polyhedron.
A set of the form {x ∈ Rn |AT x = b, x ≥ 0} is also a
polyhedron, in a standard form representation.
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Convex Set
Convex Set
A set S ⊂ Rn is convex if for any x, y ∈ S, and any λ ∈ [0, 1], we
have λx + (1 − λ)y ∈ S.
Example:?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Convex Set
Theorem
The intersection of convex sets is convex.
Proof:?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Convex Set
Theorem
Every polyhedron is a convex set.
Proof:?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Table of Contents
1 Graphical Representation and Solution
2 Polyhedra and Convex Set
3 Optimality of Extreme Points
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Extreme Points
Extreme Point
Let P be a polyhedron. A vector x ∈ P is an extreme point of P if
we cannot find two vectors y , z ∈ P, both different from x, and a
scalar λ ∈ [0, 1], such that x = λy + (1 − λ)z.
Example:?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Existence of Extreme Points
What are the necessary and sufficient conditions for a polyhedron
to have at least one extreme point?
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Existence of Extreme Points
Theorem
Suppose that a polyhedron P = {x ∈ Rn |ai T x ≥ bi , i = 1, . . . , m}
is nonempty. Then, the following are equivalent:
The polyhedron P has at least one extreme point.
The polyhedron P does not contain a line.
There exists n vectors out of the family a1 , . . . , am , which are
linearly independent.
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Existence of Extreme Points
Every nonempty bounded polyhedron has at least one extreme
point.
Every nonempty polyhedron in standard form has at least one
extreme point.
M. De Optimization Methods and Applications
Graphical Representation and Solution
Polyhedra and Convex Set
Optimality of Extreme Points
Optimality of Extreme Points
Theorem
Consider the linear programming problem of minimizing c T x over
a polyhedron P. Suppose that P has at least one extreme point
and that there exists an optimal solution. Then, there exists an
optimal solution which is an extreme point of P.
Proof.
M. De Optimization Methods and Applications
