Optimization Methods in Management Science, Problem Set 1 Solutions

Optimization Methods in Management Science Problem Set 1 (First Group of Students) Students with first letter of surnames A–F Problem Set Rules: 1. Each student should hand in an individual problem set. 2. Discussing problem sets with other students is permitted. Copying from another person or solution set is not permitted. 3. Late assignments will not be accepted. No exceptions. 4. The non-Excel solution should be handed in at the beginning of class on the day the problem set is due. The Excel solutions, if required, should be posted on the website by the beginning of class on the day the problem set is due. Questions that require an Excel submission are marked with Excel submission . For Excel submission questions, only the Excel spreadsheet will be graded. Problem 1 (35 points total) The first problem asks you to formulate a 3-variable linear program in three different ways (four ways if you also count the algebraic formulation). Both of the first two ways are fairly natural. The third way is a bit obscure. And the algebraic formulation may seem overly complex. In practice, there are advantages to formulating linear programs in different ways. And there are huge advantages in the algebraic formulation. (One can express huge problems efficiently on a computer using a modeling language, which is based on the algebraic formulation.) In addition, formulating an LP in multiple ways provides insight into the LP models. Accessories & co. is producing three kinds of covers for Apple products: one for iPod, one for iPad, and one for iPhone. The company’s production facilities are such that if we devote the entire production to iPod covers, we can produce 6000 of them in one day. If we devote the entire production to iPhone covers or iPad covers, we can produce 5000 or 3000 of them in one day. The production schedule is one week (5 working days), and the week’s production must be stored before distribution. Storing 1000 iPod covers (packaging included) takes up 40 cubic feet of space. Storing 1000 iPhone covers (packaging included) takes up 45 cubic feet of space, and storing 1000 iPad covers (packaging included) takes up 210 cubic feet of space. The total storage space available is 6000 cubic feet. Due to commercial agreements with Apple, Accessories & co. has to deliver at least 5000 iPod covers and 4000 iPad covers per week in order to strengthen the product’s diffusion. The marketing department estimates that the weekly demand for iPod covers, iPhone, and iPad covers does not exceed 10000 and 15000, and 8000 units, therefore the company does not want to produce more than these amounts for iPod, iPhone, and iPad covers. Finally, the net profit per each iPod cover, iPhone cover, and iPad cover is $4, $6, and $10, respectively. The aim is to determine a weekly production schedule that maximizes the total net profit. (a) (5 points) Write a Linear Programming formulation for the problem. Start by stating any assumptions that you make. Label each constraint (except nonnegativity). For this first formulation, the decision variables should represent the proportion of time spent each day on producing each of the two items: x1 = proportion of time devoted each day to iPod cover production, x2 = proportion of time devoted each day to iPhone cover production, x3 = proportion of time devoted each day to iPad cover production. (Different formulations will be required for parts (b) and (c).) Solution. As required, we let: x1 = proportion of time devoted each day to iPod smart cover production, x2 = proportion of time devoted each day to iPhone smart cover production, and x3 = proportion of time devoted each day to iPad smart cover production. We assume: (a) that the production can be split between the two products in any desired way (that is, fractional values for x1 , x2 , and x3 are acceptable), and (b) that the number of produced item of each type is directly proportional to the time devoted to producing the item. Given these assumptions, we can formulate the problem as an LP as follows: max 120000x1 + 150000x2 + 150000x3 s.t.: Max daily production: x1 + x2 + x3 Storage: 1200x1 + 1125x2 + 3150x3 Min iPod production: 30000x1 Min iPad production: 15000x3 Max iPod demand: 30000x1 Max iPhone demand: 25000x2 Max iPad demand: 15000x3 x1 , x2 , x3 ≤ ≤ ≥ ≥ ≤ ≤ ≤ ≥ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 1 ⎪ ⎪ ⎪ 6000 ⎪ ⎪ ⎪ ⎬ 5000 4000 ⎪ ⎪ ⎪ ⎪ 10000 ⎪ ⎪ ⎪ ⎪ 15000 ⎪ ⎪ ⎪ ⎪ 8000 ⎪ ⎪ ⎭ 0. (1) Because x1 already has a lower bound, omitting the nonnegativity constraint for x1 is not considered an error (no penalty). (b) (5 points) Write a second Linear Programming formulation for the problem. Label each constraint (except nonnegativity). For this second formulation, the decision variables should represent the number of items of each type produced over the week: y1 = number of iPod covers produced over the week, y2 = number of iPhone covers produced over the week, y3 = number of iPad covers produced over the week. The problem data is the same but you must make sure that everything matches the new decision variables. Solution. As required, we let: y1 = number of iPod covers produced over the week, y2 = number of iPhone covers produced over the week, and y3 = number of iPad covers 2 produced over the week. We make the same assumptions as for part (a). We can formulate the problem as an LP as follows: max 4y1 + 6y2 + 10y3 s.t.: Max weekly production: 1/6000y1 + 1/5000y2 + 1/3000y1 Storage: 0.04y1 + 0.045y2 + 0.21y3 Min iPod production: y1 Min iPad production: y3 Max iPod demand: y1 Max iPhone demand: y2 Max iPad demand: y3 y1 , y2 , y3 ≤ ≤ ≥ ≥ ≤ ≤ ≤ ≥ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 5 ⎪ ⎪ ⎪ 6000 ⎪ ⎪ ⎪ ⎬ 5000 4000 ⎪ ⎪ ⎪ ⎪ 10000 ⎪ ⎪ ⎪ ⎪ 15000 ⎪ ⎪ ⎪ ⎪ 8000 ⎪ ⎪ ⎭ 0. (2) Because y1 already has a lower bound, omitting the nonnegativity constraint for y1 is not considered an error (no penalty). (c) (5 points) Write a third Linear Programming formulation for the problem. Label each constraint (except nonnegativity). Assume that each working day has 8 working hours. For this third formulation, the decision variables should be: z1 = number of hours devoted to the production of iPod smart covers in one week , z2 = number of hours devoted to the production of iPhone smart covers in one week, z3 = total number of production hours employed during the week. Express the objective function in thousands of dollars. The problem data is the same but you must make sure that everything matches the new decision variables. Solution. As requested, we use two decision variables: z1 is the number of hours devoted to iPod cover production, z2 is the number of hours devoted to iPhone cover production, and z3 is the total number of production hours employed for the week. It follows that the number of hours devoted to iPad cover production is z3 − z1 − z2 , which should be a nonnegative number (i.e. we must impose z1 + z2 ≤ z3 ). We can therefore formulate the problem as follows: ⎫ ⎪ max 3000z1 + 3750z2 + 3750(z3 − z1 − z2 ) ⎪ ⎪ ⎪ ⎪ s.t.: ⎪ ⎪ ⎪ ⎪ iPad Production: z1 ≤ 40 ⎪ ⎪ ⎪ ⎪ iPhone Production: z2 ≤ 40 ⎪ ⎪ ⎪ Storage: 30z1 + 28.125z2 + 78.75(z3 − z1 − z2 ) ≤ 6000 ⎪ ⎬ Min iPod production: 750z1 ≥ 5000 ⎪ Min iPad production: 375(z3 − z1 − z2 ) ≥ 4000 ⎪ ⎪ ⎪ ⎪ ⎪ Max iPod demand: 750z1 ≤ 10000 ⎪ ⎪ ⎪ ⎪ Max iPhone demand: 625z2 ≤ 15000 ⎪ ⎪ ⎪ ⎪ Max iPad demand: 375(z3 − z1 − z2 ) ≤ 8000 ⎪ ⎪ ⎪ ⎭ z , z ≥ 0. 1 2 (d) (5 points) What is the relationship between the variables z1 , z2 , z3 of part (c) and the variables x1 , x2 , x3 of part (a) of this problem? Give a formula to compute z1 , z2 , z3 from 3 x1 , x2 , x3 . Solution. The relationship between z1 , z2 , z3 of part (d) and x1 , x2 , z3 of part (a) is the following. z1 = 40x1 because x1 represents the percentage of time of each day dedicated to iPad cover production; multiplying x1 by the total number of hours in a production period (= 40) yields the number hours spent on iPods. Similarly, we have z2 = 40x2 . Then, z3 = 40(x1 + x2 + x3 ) because x1 + x2 + x3 represents the fraction of time used during the day; multiplying this by the total number of hours in a production period yields the total number of hours employed during the week. (e) (5 points) Excel submission Solve the problem using Excel Solver, following the guidelines given in the Excel Workbook that comes with this problem set. Pay attention to the formulation in the Excel Workbook: it is similar to the one required for part (b), but it is not exactly the same. Solution. Nonzero variables in the optimal solution: x1 = 5, x2 = 7.5, x3 = 8. Objec­ tive value: 145000. (f) (10 points) Write an algebraic formulation of the weekly production schedule problem de­ scribed above using the following notation: • n is the number of product types, • xj is the number of days devoted to the production of products of type j, • pj is the number of items of type j that can be manufactured in one day, assuming that the process is devoted to products of type j. • P is the number of production days in one week, • sj is the storage space required by one item of type j, • S is the total storage space available for the week’s production, • rj is the unit profit for each product of type j, • dj is the weekly maximum demand for an item of type j. • bj is the weekly minimum demand for an item of type j. Solution. We denote by xj the number of days devoted to the production of the j-th item. This is one possible formulation. Other correct formulations are possible. ⎫ n ⎪ max r p x j j j ⎪ j=1 ⎪ ⎪ ⎪ s.t.: ⎪ ⎪ ⎪ n ⎪ x ≤ P Production: ⎬ j j=1 n Storage: j=1 sj pj xj ≤ S ⎪ ⎪ Max demand:∀j = 1, . . . , T pj xj ≤ dj ⎪ ⎪ ⎪ ⎪ Min demand:∀j = 1, . . . , T pj xj ≥ bj ⎪ ⎪ ⎪ ∀j = 1, . . . , T xj ≥ 0. ⎭ Problem 2 (10 points total). Problem 2 reviews the transformations from nonlinear constraints or objec­ tives into linear constraints and objectives, as mentioned in the second lecture and discussed in 4 the tutorial “LP Transformation Tricks”. In each part, transform the corresponding mathematical program to an equivalent linear program. Do not solve the linear program. (a) (5 points) Problem formulation: ⎫ min max{2.3x1 + x2 , 4.3x1 − 0.5x2 , 2.5x1 + 3.5x2 } ⎪ ⎪ ⎪ ⎪ s.t.: ⎪ ⎪ ⎪ Constr1 : x1 /(x1 + x2 ) ≤ 0.5 ⎪ ⎬ Constr2 : 10x1 + 28x2 = 3.4 ⎪ Constr3 : x1 + x2 ≥ 0 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ x1 free ⎪ ⎭ x2 free (3) Solution. The objective function can be reformulated as a linear objective function by introducing an extra variable w and adding three constraints. In addition, we require to multiply through by x1 + x2 (which is nonnegative) the constraint that has x3 the denominator. The resulting problem is as follows min w s.t.: Obj Ref1 : 2.3x1 + x2 − w ≤ Obj Ref2 : 4.3x1 − 0.5x2 − w ≤ Obj Ref2 : 2.5x1 + 3.5x2 − w ≥ Constr1 : 0.5x1 − 0.5x2 ≤ Constr2 : 10x1 + 28x2 = Constr3 : x1 + x2 ≥ x1 free x2 free 0 0 0 0 3.4 0 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (b) (5 points) Problem formulation: min |0.8x1 + 0.9x2 | s.t.: Constr1 : |0.9x1 + 1.2x2 | ≤ 10 x1 ≥ 0 x2 free ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ (4) ⎪ ⎪ ⎪ ⎪ ⎭ Solution. Can be reformulated by introducing an extra variable w to reformulate the objective function, and splitting Constr1 into two constraints: ⎫ min w ⎪ ⎪ ⎪ ⎪ s.t.: ⎪ ⎪ ⎪ ⎪ Obj Ref1 : 0.8x1 + 0.9x2 − w ≤ 0 ⎪ ⎪ ⎬ Obj Ref2 : −0.8x1 − 0.9x2 − w ≤ 0 Constr1 Ref1 : 0.9x1 + 1.2x2 ≤ 10 ⎪ ⎪ ⎪ ⎪ Constr1 Ref2 : −0.9x1 − 1.2x2 ≤ 10 ⎪ ⎪ ⎪ ⎪ ⎪ x1 ≥ 0 ⎪ ⎭ x2 free 5 Problem 3 (First group of students) (55 points total) This problem is based on Problem 11 of Applied Mathematical Programming, Chapter 1. This is a more complex model than the one in Problem 1. For many product mix examples, each product uses a fixed set of materials. In this example, if one makes one gal­ lon Deluxe, one does not know a priori how much of Additive A and Additive C are used. In fact, the decision maker must determine the optimal amounts of A and C to be added to Deluxe. A corporation that produces gasoline and oil specialty additives purchases four grades of petroleum distillates, A, B, C, and D. The company then combines the four according to spec­ ifications of the maximum or minimum percentages of grades A, C, or D in each blend, given in Table 1. Mixture Deluxe Standard Economy Max % allowed for Additive A 60% 15% – Min % allowed for Additive C 20% 60% 50% Max % allowed for Additive D 10% 25% 45% Selling price $/gallon 7.9 6.9 5.0 Table 1: Specifications of the three mixtures. Supplies of the three basic additives and their costs are given in Table 2. Distillate A B C D Max quantity available per day (gals) 4000 5000 3500 5500 Cost $/gallon 0.60 0.52 0.48 0.35 Table 2: Supplies and costs of petroleum grades. (a) (15 points) Formulate a Linear Program to determine the production policy that maximizes profits. Solution. We define twelve decision variables to indicate the gallons of each of the basic petroleum grades (additives) that contribute to the production of the three mixtures. We use the following labels: xAD indicates the quantity of additive A that is used for production of mixture Deluxe, xAS indicates the quantity of additive A that is used for production of mixture Standard, xAE indicates the quantity of additive A that is used for production of mixture Economy. Similarly, we use xBD , xBS , xBE to label the quantity of additive B used in each of the three mixtures, xCD , xCS , xCE for additive C, and and xDD , xDS , xDE for additive D. The gallons of mixture Deluxe produced can be computes as xAD +xBD +xCD ; similarly for mixture Standard and Economy. The objective function is the total profit, computed as revenues minus costs. Thus, we can formulate the problem 6 as follows: max s.t.: Availability A : Availability B : Availability C : Availability D : Mixture D Add A : Mixture D Add C : Mixture D Add D : Mixture S Add A : Mixture S Add C : Mixture S Add D : Mixture E Add C : Mixture E Add D : 7.9(xAD + xBD + xCD + xDD )+ 6.9(xAS + xBS + xCS + xDS )+ 5.0(xAE + xBE + xCE + xDE )+ −0.6(xAD + xAS + xAE )+ −0.52(xBD + xBS + xBE )+ −0.48(xCD + xCS + xCE )+ −0.35(xDD + xDS + xDE )+ xAD + xAS + xAE xBD + xBS + xBE xCD + xCS + xCE xDD + xDS + xDE xAD /(xAD + xBD + xCD + xDD ) xCD /(xAD + xBD + xCD + xDD ) xDD /(xAD + xBD + xCD + xDD ) xAS /(xAS + xBS + xCS + xDS ) xCS /(xAS + xBS + xCS + xDS ) xDS /(xAS + xBS + xCS + xDS ) xCE /(xAE + xBE + xCE + xDE ) xDE /(xAE + xBE + xCE + xDE ) xAD , xAS , xAE , xBD , xBS , xBE , xCD , xCS , xCE , xDD , xDS , xDE ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ≤ 4000 ⎪ ⎪ ⎪ ⎪ ≤ 5000 ⎪ ⎬ ≤ 3500 ⎪ ≤ 5500 ⎪ ⎪ ⎪ ⎪ ⎪ ≤ 0.6 ⎪ ⎪ ⎪ ⎪ ≥ 0.2 ⎪ ⎪ ⎪ ⎪ ≤ 0.1 ⎪ ⎪ ⎪ ⎪ ≤ 0.15 ⎪ ⎪ ⎪ ⎪ ≥ 0.6 ⎪ ⎪ ⎪ ⎪ ≤ 0.25 ⎪ ⎪ ⎪ ⎪ ≥ 0.5 ⎪ ⎪ ⎪ ⎪ ⎪ ≤ 0.45 ⎪ ⎪ ⎭ ≥ 0. This is not a Linear Program but can easily be reformulated as such by multiplying through by the denominators of the fractions (which are nonnegative). We can also carry out the calculations in the objective function. We obtain: 7.3xAD + 7.38xBD + 7.42xCD + 7.55xDD 6.3xAS + 6.38xBS + 6.42xCS + 6.55xDS 4.4xAE + 4.48xBE + 4.52xCE + 4.65xDE max s.t.: Availability A : Availability B : Availability C : Availability D : Mixture D Add A : Mixture D Add C : Mixture D Add D : Mixture S Add A : Mixture S Add C : Mixture S Add D : Mixture E Add C : Mixture E Add D : xAD + xAS + xAE xBD + xBS + xBE xCD + xCS + xCE xDD + xDS + xDE 0.4xAD − 0.6xBD − 0.6xCD − 0.6xDD −0.2xAD − 0.2xBD + 0.8xCD − 0.2xDD −0.1xAD − 0.1xBD − 0.1xCD + 0.9xDD 0.85xAS − 0.15xBS − 0.15xCS − 0.15xDS −0.6xAS − 0.6xBS + 0.4xCS − 0.6xDS −0.25xAS − 0.25xBS − 0.25xCS + 0.75xDS −0.5xAE − 0.5xBE + 0.5xCE − 0.5xDE −0.45xAE − 0.45xBE − 0.45xCE + 0.55xDE xAD , xAS , xAE , xBD , xBS , xBE , xCD , xCS , xCE , xDD , xDS , xDE ≤ ≤ ≤ ≤ ≤ ≥ ≤ ≤ ≥ ≤ ≥ ≤ ≥ (b) (10 points) Excel submission Write a spreadsheet for the problem and solve the problem using Excel Solver, following the guidelines given in the Excel Workbook that comes with this problem set. (Hint: The optimal value is $102986.7 . In the optimal solution, there 7 4000 5000 3500 5500 0 0 0 0 0 0 0 0 0. ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ are 12500 gallons of mixture Deluxe and 1666.667 gallons of mixture Standard. No mixture Economy is produced.) (c) Use the Excel spreadsheet to answer the following questions: i) (4 points) No mixture Economy is produced in the optimal solution. What would the minimum selling price need to be in order for Deluxe to be worth producing? (Be accurate to within 5 cents). Solution. to $5.20 It is worth producing mixture Economy when it selling price increases ii) (4 points) There are constraints on the maximum amount of distillate D that is used in producing the different mixtures. If you could violate any of these constraints on distillate A, would you? Which constraint would be most advantageous to delete? Solution. Deleting the constraint on the maximum percentage of distillate D in mixture Deluxe, Standard, and Economy results in profit of $ 129945, $ 104903, and $ 103402, respectively. Thus, the constraint on the percentage of distillate D in mixture Deluxe would be most advantageous to delete. iii) (4 points) Suppose that you can increase the selling price of Deluxe. What would be the increase in the profit if the selling price of mixture Deluxe per gallon increases to p for p = $ 7.95, $8.00, and $8.05 . (Assume that the selling price of mixtures Standard and Economy remain $6.9 and $5.0 per gallon, respectively.) The increase is the difference between the new profit and the profit from Part (a). Solution. The increase in the profit for the selling price p = $ 7.95, $8.00, and $8.05 is $ 625, $1250, $1875, respectively. iv) (4 points) Based on your answer in Part (ii), what do you think will be the profit if the selling price of mixture Deluxe increases by 5%? What is the formula for the optimum profit if the selling price of Deluxe per gallon increased by p? (You may assume that p is small enough). Solution. (p − 7.9). The increase in the profit at price p (for small enough p) is 12500 × v) (4 points) Based on your formula in part (iii), what is the contribution if the selling price of Deluxe per gallon increases to 8.5. Use Excel solver to see if the formula is correct. (It wont be.) Use Excel solver to determine the maximum value of p for which your formula is correct. (Be accurate to within 5 cents). Solution. The increase by the formula is $7500, while the increase in the profit by solving the problem is $7902. The maximum value of p for which your formula is correct is p = 8.20 vi) (5 points) The quantity available of distillate A is 4000 gals per day which is entirely used up in an optimal mixture. If you could buy (just a little bit) more, would you do so? At what price would be worthwhile to buy more? Solution. Yes. If we increase the amount of distillate A to 4001 gallons, the profit will increase from 102903 to 102911. So the increase in the objective function value is $8 per unit increase in the amount of distillate A. Thus, it would be worthwhile to buy more distillate A at any price less than or equal $8 + 0.60 = 8.60. (d) (10 points) Write an algebraic formulation for the problem using the following notation: 8 • m is the number of mixtures (final products), • n is the number of basic petroleum grades (additives), • pj is the selling price of mixture j, • ci is the cost of additive i, • ai is the maximum availability of additive i, • rij is the minimum percentage of additive i that is required in mixture j, • qij is the maximum percentage of additive i that can be blended in for mixture j, Solution. Define A × M decision variables xij , i = 1, . . . , A, j = 1, . . . , M , xij = quantityP of basic additive i used in mixture j. The total quantity of additive i employed PA M x , and the total quantity of mixture j produced is x is then j=1 ij i=1 ij . We can formulate a Linear Program to maximize the profit as follows: ⎫ PA PM ⎪ max (p − c )x j i ij ⎪ i=1 j=1 P ⎪ ⎪ M Availability : ∀i = 1, . . . , A xij ≤ ai ⎪ ⎬ j=1 P Min % : ∀i = 1, . . . , A, ∀j = 1, . . . , M (1 − rij )xij − k=1,...,A,k6=i rij xkj ≥ 0 P ⎪ ⎪ Max % : ∀i = 1, . . . , A, ∀j = 1, . . . , M (1 − qij )xij − k=1,...,A,k6=i qij xkj ≤ 0 ⎪ ⎪ ⎪ ⎭ ∀i = 1, . . . , A, ∀j = 1, . . . , M xij ≥ 0 9