Homework 5 - Theory of Linear Programming
Math 1101 - An Introduction to Optimization
Please submit the following problems at the beginning of class Wednesday, November 15.
Additionally, please staple this sheet to the front of your solutions.
1. Let P(
−→x ) = P(x1, x2, . . . , xn) be the objective function of a Linear Programming problem that has a feasible area F. Show
P(
−→x
∗
) = max{P(
−→x ) |
−→x ∈ F} ⇔ −P(
−→x
∗
) = min{−P(
−→x ) |
−→x ∈ F},
i.e. the max of P(
−→x ) occurs at the same location as the min of −P(
−→x ).
2. Let F = {[0, 0]T
, [1, 2]T
, [4, 1]T }. Present (without proof) a graph of
(a) aff(F).
(b) conv(F).
(c) coni(F).
3. Determine for each of the following sets if the set is affine, convex, or a convex cone with
vertex at the origin (“determine” means “prove or disprove”). As well, (without proof)
state whether each set is a convex polyhedron and/or a convex polytope. If a set is not
convex, state (without proof) its convex hull.
(a) S1 = {[x, y]
T
| x + y ≤ 5, y ≥ 0, x ≥ 1}.
(b) S2 = {[x, y]
T
| y ≤ |x|, y ≥ 0, x ≥ 0}.
(c) S3 = {[x, y]
T
| y − x
2 + 6x ≤ 9, y ≥ 0, x ≥ 0}.
4. Determine the extreme (corner) point(s) P = {
−→P 1, ...,
−→P s} of S2 in the previous question.
Then find direction vectors D = {
−→d 1, ...,
−→d t} of S2 such that
S2 = conv(P) + coni(D)
as in the Finite Basis Theorem and Fundamental Theorem of Linear Programming.
1
