Scribd
Upload
2 views2 pages

Problem Sheet 1

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 views2 pages

Problem Sheet 1

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 -1

1. Solve the following linear programming (LP) problems graphically

(1) max 2x1 + 4x2


subject to
3x1 + 5x2 ≤ 15
3x1 + 2x2 ≤ 12
x1 , x2 ≥ 0.

(2) max 2x1 + x2


subject to
2x1 + x2 ≤ 4
−x1 + x2 ≥ 1
x1 , x2 ≥ 0.

(3) max 6x1 − 2x2


subject to
2x1 − x2 ≤ 2
x1 ≤ 4
x1 , x2 ≥ 0.

(4) max x1 − 2x2


subject to
x1 + x2 ≥2
−x1 + x2 ≥1
x2 ≤3
x1 , x2 ≥ 0.

(5) max x2
subject to
|x1 | + |x2 | ≤ 2
x1 ≥ 0.

2. Is the following a LP problem


max 4x1 + 3x2
subject to (x1 + x2 ≤ 8 or 2x1 + x2 ≤ 10)
x1 , x2 ≥ 0 .
Solve the given problem graphically.

1
3. Let S = {(x1 , x2 ) ∈ R2 : x1 − x2 ≤ 4, x1 + x2 ≥ −3, x2 ≤ 8}. Find all extreme points
of S and hence express the point (2, 1) as a convex combination of these extreme
points.

4. When does one half space contain another? give conditions under which

{x ∈ Rn |aT x ≤ b} ⊆ {x ∈ Rn |cT x ≤ d}

where a, c ∈ Rn are nonzero and b, d ∈ R.

5. Provide an example of a convex set K ⊆ R2 and a linear objective function cT x such


that min{cT x|x ∈ K} > −∞ but there does not exist an x∗ ∈ K with cT x∗ ≤ cT x
for all x ∈ K.

You might also like