Optimization Methods: Problem Set 3

Problem Set 3 Problem 1: Britney’s New Life (30 Points) This problem allows you to practice the simplex algorithm and to review some concepts from geometry. Since splitting with Kevin, Britney is slowly learning the harsh realties of having to manage on her own. She no longer has Kevin to help her with taking care of the kids, cleaning the house, managing the garden, doing laundry, and most importantly solving her linear programs. Having not taken a linear programming class, she turns to “you” for help. Britney’s goal is to maximize her utility points. Currently Britney needs to divide her hours each day between activities including: partying with Paris and Lindsey, cutting her hair, and taking care of her children. • According to her mother, each hour of partying is worth 5 utility points; each hour she spends on her hair is worth 3 utility points; and each hour taking care of the kids is worth 1 utility point. • Due to the fact she has not toured or sold a CD in more then 5 years, Britney cannot spend more then $6 in a given day. Partying costs Britney $1 an hour. (Fortunately, Paris pays for all her drinks. Hair styling costs $1 an hour, and caring for the kids costs $3 an hour. (She actually watches while she pays a local teenager to care for them.) • In a given day, Britney has at most 15 units of energy to spend. Partying for one hour takes up 6 energy units; hair styling for an hour takes up 3 energy units; and caring for the kids for one hour takes up 6 energy units. • We assume that the total time spent on these activities can be at most 24 hours. Any amount of time not spend on these activities, she spends sleeping. Part A: Using Britney’s considerations above formulate a linear program that will optimally allocate the number of hours to partying, hair styling, and caring for the kids. (Hint: Your LP should have exactly three variables) Part B: Page 1 of 9 Convert the LP in Part A to standard form by adding variables. For each variable you added write a sentence about what that variable represents. Part C: Is the constraint that models “the total amount of time spent in a day on the three activities must be 24 hours or less redundant”. If it is explain why and remove it, if not explain why and leave it in the formulation. Part D: Identify a feasible solution where all basic variables are slack variables. Part E: Using your solution in part D fill out the first Simplex Tableau. Part F: Solve the problem using the Simplex Method. For each iteration write down the starting Tableau and indicate the pivot element. Part G: Does Britney have multiple optimal ways to divide her time? Please explain your answer. Part H: In the form of a line segment express all of the optimal solutions to Britney’s problem. Problem 2: Turkey Tim and the Simplex Tableau (25 Points) This problem is meant to help define some of the conditions that arise when running the simplex method on a standard form problem. Turkey Tim was trying to find the optimal solution to a maximization problem in decision variables xj ≥ 0 (for j = 1, 2, …,7). After performing several pivots, he came up with a tableau similar to the one below. However, Turkey Tim was watching the West crush the East in the NBA all star game while working on the problem, and he smudged some of the elements in the simplex tableau with buttered popcorn. Ollie replaced these questionable elements in the tableau with the letters (variables) A,B,C,D,E, and F hoping that you (a bright student taking 15.053) will be able to explain to Tim information about the values that these letters can represent. Consider this linear programming problem in canonical form (depending on F), described in terms of the following initial tableau: Page 2 of 9 z 1 0 0 0 x1 0 0 0 1 x2 0 1 0 0 x3 0 0 1 0 x4 A D -2 0 x5 3 1 2 -1 x6 B 0 E 2 x7 C 3 -1 1 RHS 1 F 2 3 Part A: What is the current objective value? Part B: Which of the variables are currently in the basis? Part C: What is the current basic feasible solution? You may express your answer in terms of the letters A to F if needed. Parts D-G: for each statement below, give sufficient conditions on all six unknowns A, B, C, D, E, F such that the statement is true. If there is nothing that can be done to make the statement true please explain why. If there are several ways of accomplishing this, please state only one. Part D: The corresponding basic solution is feasible but not optimal Part E: The corresponding basic solution is feasible, and there is a choice of the entering variable so that the first simplex iteration indicates that the optimal cost is infinity (unbounded from above). Part F: The corresponding basic solution is feasible, x6 is a candidate for entering the basis. Moreover, if x6 is the entering variable, then x3 leaves the basis. Part G: The corresponding basic solution is feasible, x7 is a candidate for entering the basis. Moreover, if x7 enters the basis, then the solution and the objective value remain unchanged after the pivot. This is called a degenerate BFS and a degenerate pivot, and we will learn more about these types of BFS’s next week Page 3 of 9 Part H: Suppose A=4, B=0, C=-2 and F=3. Perform a pivot using the simplex algorithm. Indicate the variable that enters the basis, the variable that leaves the basis, and the total change in profit. Also, write the resulting tableau. (The answer for some of the coefficients of the tableau will be in terms of D and E, which were not specified.) Why is the Simplex Method not so simple at first? Relax, Tim. Everything is difficult at first. After a bit of practice the Simplex Method will be as easy as carving a Turkey. Burn!!!! Problem 3: Simplex Paths (25 Points) This problem is meant to help you develop an understanding of how the simplex method moves form corner to corner. It should give some insights into pivoting. Our four friends: Ollie the Owl, Tim the Turkey, Cleaver the Beaver, and Nooz the Fox are all performing the simplex method with the feasible region shown below, all using the same objective function. Labels of the corner points A: (0,0,0) F: (0,1,1) B: (1,0,0) G: (1,0,1) C: (0,1,0) H: ( 1,1/2/,1) D: (0,0,1) I: (1,1,1/2) E: (1,1,0) J: (1/2,1,1) Point (0, 0, 0) is not visible here. Part A: (0, 0, 1) (1, 0, 1) (1, .5, 1) (.5, 1, 1) (1, 1, .5 ) (1, 0, 0) (0, 1, 0) (1, 1, 0) Page 4 of 9 (0, 1, 1) Tim suggests the following the following pairs of corner points could result from successive iterations. (A, B) (B, D) (E, H) (A, I) For each pair determine if Tim is correct and explain your reasoning. Part B: Suppose each character starts the simplex method at Point A. listed below are the paths each found by running the algorithm on the objective function, resulting in the optimal solution ‘H’. Ollie’s Path: A ⇒ B ⇒ G ⇒ H Cleaver’s Path: A ⇒ E ⇒ I ⇒ H Nooz’s Path: A ⇒ C ⇒ E ⇒ B ⇒ A ⇒ D ⇒ G ⇒ H For each of the above, determine from the information given if the path could have resulted when running the simplex method on the problem. If not explain why not. Part C: Now suppose each character decides to use a different objective function. They will start running the simplex method at point A. Their objectives are listed below: Tim’s Objective: Min Ollie’s Objective Min Nooz’s Objective Min z = −x1 + 2x 2 − 3x3 z = −5x1 − 2x 2 − 4x3 z = 2x1 − 7x 2 − 2x3 For each of the following objective functions determine which variable enters the basis as the first iteration, and what the next corner point will be. What is the improvement in the objective function. (If there are different choices of an entering variable, choose any of the ones that are possible.) Part D: Does the feasible region in the picture represent a problem in standard form, or does it represent a problem with inequality constraints. How many inequalities are there, other than nonnegativity constraints. Please explain your answer. Problem 4: Variables that come and Go (21 Points) Page 5 of 9 This problem is meant to build insight into how the simplex method works and to connect the mathematics behind the simplex method with the geometry of the simplex method. Suppose we are solving a minimization problem and the variable x3 is about to leave the basis. Part A: What can you say about the z-row coefficient of x3 prior to the pivot? Part B: After the pivot is carried out, can the z-row coefficient of x3 can be less then zero. Explain your answer. Part C: Is it true that a variable that has just left the basis can not reenter on the very next iteration? Briefly explain. Comment: a variable that has left the basis can reenter on any subsequent iteration after the first iteration. Part D: For a linear program with n variables, how many times can a variable (say x1) enter and leave the basis? (Give one answer, and you do not need to justify it.) a. at most 1 time. b. at most 2 times. c. possibly more than 2n-1 times. Part E: What is the maximum number of corner points (bfs’s) for a linear program with 3 linearly independent equality constraints and 5 variables as well as non-negativity constraints? Problem 5: Planning for Expressjet Airlines (15 Points) The idea behind the problem is to continue to build your skills at formulating linear programs and to practice abstraction. Page 6 of 9 Expressjet Airlines will no longer operate flights exclusively for Continental Airlines but also for their own independent new airlines “Express Jet”. Management believes that they will need the following number of pilots over the next five years. • • • • • Year 1: 60 Pilots Year 2: 70 Pilots Year 3: 50 Pilots Year 4: 65 Pilots Year 5: 75 Pilots At the beginning of each year, the company must decide how many pilots should be fired or hired. It costs Expressjet $4000 to hire a pilot and $2000 to fire a pilot. A pilot’s salary is $10,000 per year, as they are all flying on UROP wages. At the beginning of year 1, Expressjet has 50 pilots. A pilot hired at the beginning of a year may be used to meet the current year’s requirements and is paid full salary for the current year. It is feasible (but expensive) to have too many pilots Part A: Formulate an LP to minimize Expressjets’s labor costs over the next five years. Part B: Define a set of variables and data points and formulate the abstracted version of the problem. Be sure to clearly indicate the constants and variables you define. (For example, let hj be the cost of hiring a pilot in year j; let fj be the cost of firing a pilot in year j; and make up notation for any other terms you need.) Problem 6: The Knapsack Problem (20 Points) This problem is meant to help you practice abstract formulation and to build insight into the feasible regions of standard form problems with a single constraint. New best friends, Lance Armstrong and Matthew McConaughey have decided to go on a camping trip to Napa Valley to spend some quality time alone together. (Nothing is implied by this statement.) . They can pick between two types of food: Lean Cuisine and Hungry Man dinners to put in their back packs. Lean Cuisines weigh a1 pounds and have a utility of c1 . Hungry man dinners weight a2 pounds and have a utility of c 2 . The knapsack they will carry can hold at most b pounds. Part A: Page 7 of 9 Assuming fractional items are allowed, formulate a linear program that will maximize the utility of Lance and Matt’s backpack. Part B: Is it true that if: c2 c1 ≥ a2 a1 b Hungry Man dinners. a2 Briefly, explain your answer. (Please note that a formal argument or proof is not necessary.) Then the pair can maximize utility by filling the knapsack with Part C: Suppose now that there are n items. Each item i has weight ai and utility ci . Formulate the abstracted version of part A. Part D: What is the optimal solution to part C in terms of the coefficient vectors a and b? (HINT: generalize what you learned in part b.) Part E: Give a set of conditions that need to be present so that multiple optimal solutions exist. (HINT: your answer should follow from your answer to part D.) Challenge Problem C: (10 Points) Part A: Consider the following LP: Page 8 of 9 n Maximize ∑c x j i =1 j subject to n ∑a x i =1 ij = bi j xj ≥ 0 for i = 1 to m for j = 1 to n Suppose that x1′, x2′ ,..., xn′ is an optimal solution. Suppose that c1 is decreased and all of the other c’s are kept the same, and that x1* , x2* ,..., xn* is the new optimal solution. Show that x1* ≤ x1′ . Part B (5 points): Suppose that 0 is a corner point for the following feasible region. n ∑a x i =1 ij j ≥0 for i = 1 to m Show that it is the only corner point. A formal proof is not needed Page 9 of 9