Industrial Engineering 335 Operations Research - Optimization Spring 2017 Homework 2 1 Directions: Due: Monday February 13, 2017, beginning of class. Motivate all your answers. The deadline is hard. If you do not make the class deadline, you may submit your homework until Thursday Feb. 14 at noon, with a 25 point penalty (late homework papers must be submitted by email to the TAs.). No homework will be accepted later than noon of Feb. 14. Show all work. When you are asked to use Matlab, include the code as text in your submission. (preferably \"print\" the code in the editor as a pdf file). Recall from the syllabus that the teaching staff will not answer any questions about the homework within 24 hours of the deadline. 2 Problems Problem 1. [20 points] Part I (12 points) Find ALL local and global optimal solutions of the following minimization problems, whose objective function is denoted by f and feasible set by X (do NOT use Matlab or any other solver): (a) f (x) = sin x and X = [0, 3]; (b) f (x) = sin x and X = [0, 4]; (c) f (x) = sin x and X = [/4, (11/4)]; (d) f (x) = max(0, x2 1) and X = (, ); ( 1 sin (x) , if x 6= 0 (e) f (x) = x and X = [0, (2/3)]; 0, if x = 0; Part II (8 points) Provide an example of optimization problem (a) that does not have any GLOBAL optimal solution but it does have at least one LOCAL optimal solution; (b) whose set of local optimal solutions coincides with that of the global optimal solutions. 1 Problem 2. [15 points] Part I (5 points) Say which of the following functions is LINEAR (remember that linear is different from affine): (a) 2x1 + x1 x2 x3 (b) (log 5)x1 x25 (c) sin(x1 ) x25 (d) x1 x3 + 5x4 (e) x1 x3 + 5x4 + 1 (f) x1 + 2x2 4x3 x1 + 2.5x2 + x3 (g) x1 + x2 + x33 Part II (10 points) (i) Suppose that the value of a linear function at [2, 1, 1]T is 4. Which is the value of the same function at [4, 2, 2]T (note that [4, 2, 2]T = 2 [2, 1, 1]T )? Which property of the function did you use to answer? (ii) Suppose that the values of a linear function at [2, 1, 1]T and [2, 0, 1]T are 4 and 7, respectively. Which is the value of the same function at [4, 1, 0]T = [2, 1, 1]T + [2, 0, 1]T ? Which property of the function did you use to answer? Problem 3 (15 points). Taking the xj as decision variables, and all other symbols as given constants, determine whether each of the following is a linear or nonlinear constraint, and briefly explain why. (a) x1 + x2 4x3 + x11 7 (b) x4 / + 11x13 80 (c) x1 x2 ln(x3 ) 19 P7 j (d) j=1 e xj = 234 Assuming that the zj are decision variables, determine whether each of the following optimization models is best described as a linear program (LP), a nonlinear program (NLP), an integer linear program (ILP), or an integer nonlinear program (INLP), and briefly explain why. (e) maximize s.t. 44z1 + 2z2 + 98z3 12z1 1 + 92z2 + 88z3 95 zj 0 for j = 1, . . . , 3 2 (f) minimize s.t. 7z1 + sin(z2 ) + 8/z3 4z1 + 16z2 + z3 29 0 zj 1 (g) minimize s.t. for j = 1, . . . , 3 8z1 z2 + 14z3 z1 3z2 zj 0 for j = 1, . . . , 3 z3 integer Consider the optimization models given in parts (e)-(g). Determine which of each of the following pairs would normally be most tractable, and briefly explain why. (h) Model (e) versus (f) (i) Model (e) versus (g) 3 Problem 4. [25 points] Part I (13 points) Solve graphically the following optimization problems: (a) maximize x1 , x 2 s.t. x1 + 3 x2 x1 + x2 3 x1 + x2 1 x1 + 2x2 4 x1 0, x2 0 (b) maximize x1 , x 2 s.t. x1 + 3 x2 x1 + x2 3 x1 + x2 1 x1 + 2x2 2 x1 0, x2 0 (c) minimize x1 , x 2 s.t. x1 + 4 x2 x1 + x2 3 x1 + x2 1 x1 0, x2 0 Part II (12 points) Consider problem (a) above. 1. Change the objective function (to be maximize) so that [4, 0]T becomes the optimal solution of the problem; 2. Provide a justification of (i) why the point [4, 1]T can never be an optimal solution of the problem; and (ii) why the point [3, 0.25]T can never be an optimal solution of the problem. Problem 5. [25 points] A small airline, Ivy Air, flies between three cities: Ithaca, Newark, and Boston. They offer several flights but, for this problem, let us focus on the Friday afternoon flight that departs from Ithaca, stops in Newark, and continues to Boston. There are three types of passengers: (a) Those traveling from Ithaca to Newark. (b) Those traveling from Newark to Boston. (c) Those traveling from Ithaca to Boston. 4 The aircraft is a small commuter plane that seats 30 passengers. The airline offers three fare classes: (a) Y class: full coach. (b) B class: nonrefundable. (c) M class: nonrefundable, 3-week advanced purchase. Ticket prices, which are largely determined by external influences (i.e., competitors), have been set and advertised as follows: Y B M Ithaca-Newark 300 220 100 Newark-Boston 160 130 80 Ithaca-Boston 360 280 140 Based on past experience, demand forecasters at Ivy Air have determined the following upper bounds on the number of potential customers in each of the nine possible origin-destination/fare-class combinations: Y B M Ithaca-Newark 4 8 22 Newark-Boston 8 13 20 Ithaca-Boston 3 10 18 The goal is to decide how many tickets from each of the nine origin/destination/fare-class combinations to sell. The constraints are that the plane cannot be overbooked on either of the two legs of the flight and that the number of tickets made available cannot exceed the forecasted maximum demand. The objective is to maximize the revenue. Formulate this problem as optimization problem. Note: assume that any ticket you decide to sell will be sold (i.e. there are enough people willing to purchase). 5