Optimization Methods: Problem Set 2

Problem Set 2 Problem 1: LP Geometry (30 Points) The goal behind this problem is to get you familiar with the basic properties of linear program feasible regions and to get used to working with basic geometric definitions and representations. Consider the following Problem: min z = x + y s.t : x − y ≤1 2x + y ≥ 6 x, y ≥ 0 Part A: Graph the feasible region Part B: Is the feasible region unbounded? Part C: Solve the problem using the geometric method. Part D: Now suppose we change the min to a max. What is the new optimal solution to the problem. Part E: Come up with two different vectors that point in the unbounded direction (also known as a direction of unboundedness). Call these two vectors C = (c1, c2) and D= (d1, d2). This means that for any solution (a’, b’) and for any non-negative real number r, both (a’ + rc1, b’ + rc2) and (a’ + rd1, b’ + rd2) are feasible solutions. Page 1 of 11 Part F: A ray that is an edge to the feasible region is called an extreme ray. How many extreme rays are there in this LP and what are they. Then express the ray’s in the alternative form given in lecture three shown below: Ray: (1-λ)p1 + λp2 for 0 ≤ λ ≤ ∞. Part G: Give an objective function (other then the function z=0 or z=constant) for the original problem that yields multiple optimal solutions. Part H: Add a constraint that makes the problem infeasible, show this graphically. Part I: Consider the original problem with the added constraint that y is at most 6 as shown below. min z = x + y s.t : x − y ≤1 2x + y ≥ 6 y≤6 x, y ≥ 0 What is the new optimal solution to this problem? Part J: Express the feasible region as a convex hull using the representation theorem. Part K: Consider the following modified problem Page 2 of 11 min z = x + y s.t : x − y ≤1 2x + y ≥ G y≤6 x, y ≥ 0 Let Z(G) be the optimal objective value for a given G. Plot Z(G) for Z=-50 to z=50 Part L: As described in Part K graph Z’(G) for Z=-50 to Z=50 Problem 2: Lindsey Lohan and Time Management (20 Points) In this problem you will get to first formulate a linear program and then explore the effects of a change in parameter on both the feasible region as well as the objective function. It is also meant to give you additional practice with the basic concepts of linear programming geometry. Lindsey Lohan has recently been losing many roles due to her excessive partying. According to E! online: In the wake of harsh criticism that Lindsay Lohan has not been taking her recovery seriously, E! has learned that Lindsay has been replaced by Jessica Beil in "A Woman of No Importance". Since hearing this news, she has been looking for advice on time management. While in rehab she had a chance to watch the Shining and the phrase “All work and no play makes Jack a dull boy.” came to mind. In trying to balance the two she recognizes that: • Play is twice as much fun as work • In order to be successful she must work at least as much as she plays • She has at most 10 hours to work and play in a given day (She sleeps at least 14 hours) • Due to alcohol abuse she can play for a maximum of four hours per day Part A: Page 3 of 11 Using Lindsey’s considerations above formulate a linear program that will optimally allocate the number of hours to work and play in a given day. Part B: Graph the constraints of your LP in Part A. Part C: Shade in the feasible region. Part D: Are any of the constraints redundant? If so which name one? Part E: Solve the LP using the graphical method. Part F: Are there multiple optimal solutions? Part G: Suppose that after a week of this regiment Lindsey realizes that play is ‘m’ times as much fun as work. For every unit you increase m by(Start with m=2) how much does the objective function change by? Does the feasible region change as you increase m? Part H: Frustrated by the results in part G (Hint) since says “Screw it, ill party as much as I want to, but I am still committed to working as much as partying”. Given this new info draw the new feasible region and indicate the new optimal solution. (Assume m=2 here). Part I: Assume for this part Lindsey still says: “Screw it, ill party as much as I want to, but I am still committed to working as much as partying”. Find a value of m such that multiple optimal solutions exist. Explain your answer fully. Problem 3: Nooz and Olli’s Formulation (20 Points) This problem is intended to give you additional practice with formulations. Specifically to be able to construct abstract formulations based on tutorial 1. Page 4 of 11 Nooz and Olli have decided to go into business together to conduct selling blue crabs that they catch along the Baltimore caost line. (which we will assume is straight). After they catch their crabs, they bring them back to their processing plant where they are cleaned clawed and wrapped to go. Following this process, they ship them to n different seafood restaurants located along the banks of the river. Assume the river bank is 10 miles long and we labeled the North(left side as shown below) as point zero and the south(right side as shown below) as point 10. 0 10 Nooz and Ollie’s goal is to locate their facility somewhere along the river bank to minimize the total transportation costs. Customer i is located at point ai and has a demand of d i blue crabs. At x the distance to customer i is ai − x if ai ≥ x and x − ai if the reverse is true. The unit transportation cost of shipping a crab is $c per mile. Part A: Formulate the problem of determining where Nooz and Ollie should locate their facility to minimize transportation costs as a mathematical program to meet all demands while minimizing transportation costs. Be sure that all variables constraints and objectives are defined in words before written algebraically). You may use absolute values in this part of the formulation. Part B: Convert the mathematical program of part A to a linear optimization problem. Part C: It is claimed that the optimal solution to the linear program is to locate the facility at one of the restaurants. Is this claim is true or false. (No explanation needed.) Bonus (2 Points): Show why it is true or false. Part D: Page 5 of 11 Suppose now the restaurants are located in the city of Baltimore(not on the river bank). The city of Baltimore is a 10 x 10 mile square which is grided(like Manhattan). Each restaurant i has two coordinates (ai1 , ai2 ) . With the new set of locations Nooz and Ollie need to reconsider where to open their facility to minimize transportation costs. The demands and transportation costs are the same as in the first part. Here we assume that distances are measured using the “Manhattan metric.” That is, all streets go either North-South or East-West. In this case, the distance from location (xi, yi) to (xj, yj) is |xi – xj| + |yi – yj|. Formulate the problem of determining where Nooz and Ollie should locate their facility as a mathematical program to meet all demands while minimizing transportation costs. You may use absolute values in this formulation. Part E: Convert the mathematical program of part D to a linear programming problem. Part F: It is claimed that the optimal solution to the linear program is to always locate the facility at one of the restaurants. Is this claim is true or false? (No explanation needed) Bonus (2 Points): Show why it is true or false. Part G: Bonus (4 Points): It is claimed that it is optimal to locate the facility at the x ordinate of one restaurant and y ordinate of one restaurant (they do not have to be the same restaurant). Is this claim is true or false? (No explanation needed) Show why it is true or false. Page 6 of 11 Olli Blue Crabs? Why are an Owl and a Fox getting into the fishing business? Be happy were not in the fox hunting business Nooz Problem 4: Short Answer (18 Points) This questions explores the effects of additional constraints and properties of the feasible region. It is meant to build intuition behind the linear programs feasible region. For each part indicate if the statement is true or false and explain why. For all false statements give a counter example Part A: If one constraint is a positive multiple of another constraint then there exists a redundant x + 2 y ≤ 5 constraint. e.g 3 x + 6 y ≤ 15 Part B: If one constraint is a negative multiple of another constraint then their exists a redundant constraint. e.g Page 7 of 11 x + 2y ≤ 5 − 3x − 6 y ≥ −15 Part C: If a non-negative linear combination of two inequality constraints (constraint 1 and constraint x+ y ≤5 2) is the same as a constraint 3 then constraint 3 is redundant. x − y ≤ 2 2x ≤ 7 Part D: If a non-negative linear combination of two inequality constraints(constraint 1 and constraint 2) is the same as a constraint 3 then at least one of the first two constraints is redundant. Part E: Can you create an objective function such that every point in the feasible region is optimal? If so give an example if not explain why not. (Assume the feasible region is not empty) Part F: Is it possible that for the same problem (e.g. same objective function and constraints) if we consider both maximizing and minimizing both problems could be unbounded? Problem 5: Convexity (20 Points) This problem is meant to help you work with the definition of convexity and to understand the properties of convex sets. For each of the following feasible regions explain why it is or is not convex, using the definition of a convex set. Explain your answers in order to receive full credit. Part A: Part B: Page 8 of 11 Part C: (The above is a cylinder) Part D: min z = x s.t : x ≤1 x, ≥ 0 Part E: min z = x s.t : x ≥1 x≥0 Part F: The Empty Set Part G: min z = x s.t : y <1 y≥6 Part H: Is the union of two convex sets convex? Part I: Is the intersection of two convex sets convex? Part J: Page 9 of 11 Is the convex hull of a set of points convex? Problem 6: Three Dimensions, Three Constraints (18 Points) The idea behind this problem is to explore the possible feasible regions when we have three planes. It should help build intuition about the feasible regions of linear programs in higher then two spaces. Suppose we have exactly three equality constraints and three decision variables(e.g. we are in 3D space). For each dimension explain if it is possible if that could be the feasible region and if so given an example: • The feasible region could be a single point • The feasible region could be a line segment • The feasible region could be a ray • The feasible region could be a line • The feasible region could be a bounded 2- dimensional set • The feasible region could be an unbounded plane • The feasible region could be a box in R^3 with positive volume. • The feasible region could be all of R3 • The feasible region could be empty Challenge Problem B (10 Points) A airline wants to assign telephone operators round the clock. The operators are located overseas, and they are willing to work for low wages and long hours. The airline breaks up each day into four 6-hour periods. They have decided how many operators are needed during each 6 hour period as shown below. Time Period 12 AM to 6 AM 6 AM to 12 PM 12 PM to 6 PM 6 PM to 12 AM Page 10 of 11 Operators Needed 12 6 8 11 Operators can be hired to work 12 or 18 hour consecutive shifts. Each operator works the same shifts seven days a week with no days off. Operators are paid $3.00 per hour for the first 12 hours they work and $4.00 per hour for the extra six if they work the longer length shift. Formulate a linear program that will minimize the total labor costs for the week, while satisfying the total demand. Note that operators are permitted to start at 12 AM or 6 AM or 12 PM or 6 PM. An operator starting at 6 PM would end his or her shift on the following day. (HINT: there should only be four constraints, other than non-negativity constraints.) Page 11 of 11