Problem 1: LP Geometry You are given the following LP: Maximize 2 x1 − x2 s.t. -x1 + x2 ≥ 2 x1 − x2 ≤ 3 x1 ≥ 0 x2 ≥ 0 Part A: Find the solution to this LP using the Geometric Method. Part B: Add the following constraint to the problem: 2 / 3x1 + x2 ≤ 7 . Use the Geometric Method to find the solution to the LP with the new constraint. Part C: Use the representation theorem to express the constraints in a different form. Problem 2: Look at the figure that follows and answer the set of questions based on the figure. The feasible region is “striped”. The feasible region is infinite. The constraints are as follows: x –2y ≤ 4 x – y ≥ -2 x ≥ 0; y ≥ 0 Page 1 of 5 Part A: List all corner points, if there are none, please write “none” Part B: Give an example of an objective function such that both (2,0) and (0,0) are optimal, but (1,1) is not optimal (assume you are maximizing). Part C: Give an example of an objective function such that the optimal solution value is unbounded above (assume you are maximizing). Part D: Add a constraint that makes the problem infeasible. Part E: Write the “extreme rays” Part F: Use the representation theorem to write the convex hull of the corner points. Does it give you the whole feasible region? Part G: Express the entire feasible region using extreme rays and corner points Page 2 of 5 Problem 3: True or False: Part A: It is possible that the feasible region is unbounded yet a finite optimal solution exists. Part B: If there exists exactly one corner point “x” and the optimal cost is finite then “x” is an optimal solution. Part C: If there exists exactly one corner point “x” and the optimal cost is finite then it is possible that multiple optimal solutions exist Part D: Every feasible standard form LP has a corner point Part E: If there is a unique optimal solution to a piecewise linear LP then it is possible that this solution is an interior point. Part F: It is possible that an LP with at least one corner point contains a line Part G: Every LP has a non-empty feasible region Part H: It is possible for an LP to have exactly two optimal solutions Part I: Every optimal solution must lie at a corner point. Part J: Page 3 of 5 If an LP is infeasible, then it may be possible to change the objective function to make the LP feasible. Part K: If the feasible region in a linear program is unbounded and the objective is maximized then there are infinitely many feasible solutions and the limit of the objective values is infinity. Part L: If an LP has at least two optimal solutions, then it has an infinite number of different optimal solutions. Part M: If an LP has more then one optimal solution, then there are at least two corner points that are optimal. Part N: If we take the convex hull of a set of n points in 2D. Then any point on the hull will be a corner point. Problem 4: A Feasible Region Suppose the following is a feasible region for a linear program: (0,0.5) D C (1,1) B A E F G (4/3,0) Part A: If exactly one of these points is optimal, which point(s) could it be? Page 4 of 5 Part B: If point B is optimal, must any other of these point(s) be optimal too? If so, which one(s)? Part C: If point A and G are optimal what other points must be optimal Part D: Give an objective such that only point D is optimal. Part E: Can you form an objective such that the problem is unbounded Part F: Could this be the feasible region of a standard form problem in two dimensions. Part G: The line segment connecting points C and G is the line y= -3x+4, express this line segment as a linier combination of two points. Part H: Express the line Segment y= -3x+4 in a different form using the method done in lecture. Part I: Suppose we form a ray starting at C and extends through G all the way to infinity. Express this ray algebraically. Page 5 of 5