Share
Explore BrainMass

Extreme Points of Polyhedral Sets and Recession Directions

1. Find all basic solutions of the following system:

-x1 + 2x2 + x3 + 3x4 - 2x5 = 4
x1 - 2x2 + 2x4 + x5 = 2

2. Find all extreme points of the following polyhedral set

X = {(x1, x2, x3) : x1 - x2 + x3 ≤ 1, x1 -2x2 ≤ 4, x1, x2, x3 ≥ 0}

Does X have any recession directions? Why?

3. Let X = {( x1, x2) : x1 - x2 ≤ 3, -x1 + 3x2 ≤ 3, x1 ≥ -3}
Find all extreme points of X and represent x = (0,1) as a convex combination of extreme points.

4. Assuming that a LP (Linear Problem) is in standard form(all restrictions are equalities and all variables are nonnegative) prove the following theorem: "If for a vector x in P (feasible region) the columns of matrix A associated with the positive components of x are linearly independent, then x is an extreme point."
---

Attachments

Solution Summary

Extreme Points of Polyhedral Sets and Recession Directions are investigated.

$2.19