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.
P ( x ) = P (x
; x
; : : : ; x
) be the objective function of a Linear Programming prob-
Let !
1
2
n
lem that has a feasible area F . Show
!
!
!
F
!
!
!
x
F
;
P ( x ) = max P ( x )
j
x
2
g ,
P ( x ) = min
f
P ( x )
j
2
g
f
i.e. the max of
P ( x ) occurs at the same location as the min of
P ( x ).
!
!
2.
Let F = f[0; 0]T ; [1; 2]T ; [4; 1]T g. Present (without proof) a graph of
(a) af f(F ).
(b) conv(F ).
(c) coni(F ).
3. Determine for each of the following sets if the set is a ne, 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 = f[x; y]T j x + y 5; y 0; x 1g.
(b) S2 = f[x; y]T j y jxj; y 0; x 0g.
(c) S3 = f[x; y]T j y x2 + 6x 9; y 0; x 0g.
! !
4. Determine the extreme (corner) point(s) P = fP 1; :::; P sg of S2 in the previous question.
! !
Then nd direction vectors D = f d 1; :::; d tg of S2 such that
S2 = conv(P ) + coni(D)
as in the Finite Basis Theorem and Fundamental Theorem of Linear Programming.
1
