Scribd
Upload
2 views1 page

Problem Sheet 2

Uploaded by

Ishika Goel
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views1 page

Problem Sheet 2

Uploaded by

Ishika Goel
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

LINEAR PROGRAMMING ( MAT-388)

Problem Sheet -2

1. Let S = {(x1 , x2 ) ∈ R2 : x1 + |x2 | ≤ 1, x1 ≥ 0} and S1 = S ∪ {(1, 1)}. Let Conv(S1 )


be the convex hull of set S1 . Consider the maximization of 4x1 + 3x2 over Conv(S1 ).
Express this optimization problem as a linear programming problem.

2. Let S = {(x1 , x2 ) ∈ R2 |x1 − 2x2 ≤ 4, −x1 + x2 ≤ 3, x1 ≥ 0, x2 ≥ 0}. Find the


extreme points and extreme directions of S.

3. Let S = {(x1 , x2 ) ∈ R2 |x1 + x2 ≤ 1}. Find the extreme points and extreme directions
of S. Can you represent any point in S as a convex combinations of its extreme
points plus a nonnegative linear combination of its extreme directions?

4. Given the convex set S = {(x1 , x2 ) ∈ R2 |x21 + x22 ≤ 1}. Find the equation of sup-
porting hyperplane
√ √
at any boundary point (ξ, η) and the equation of supporting
hyperplane at ( 2 , 22 ).
2

5. Show that if C is a convex cone, then C has at most one extreme point, namely the
origin.

6. Write the solution of following LP problem without actually solving it

max x1 − x2 + x3 − x 4
subject to
0 ≤ x1 ≤ 8
−2 ≤ x2 ≤ 4
−2 ≤ x3 ≤ 4
0 ≤ x4 ≤ 10 .

You might also like