Introduction to Optimization Problem Set 1

Introduction to Optimization Problem Set 1, Notes: 1. Answers may be handed in as a team of two. 2. You will need Excel Solver to do several of these problems. If you do not already have Excel Solver installed on your computer, you will need to install it. If it is there, you can then use the "Add-in command"(under the tools menu). If you don't have it on your computer, you will need to install Solver using your Office CD disk. 3. When we include an error checking hint (sometimes just called a hint), its purpose is to let you know whether your solution is correct. 1. Linear Programing (3) Are the following problems linear programs? If not, why? a) maximize subject to 3x1 +2x1x2 3x1+5x1x2 ≤ 7 x1 ≥ 0 x2 ≥ 0 b) minimize subject to 32x1+2x3 x1+x2+x3 ≤ 7 c) maximize subject to 3x1 + 5x2 + x32 x1, x2, x3 ≥ 0 2 Trucko Manufacturing (6) Truckco manufactures two types of trucks: 1 and 2. Each truck must go through the painting shop and assembly shop. If the painting shop were completely devoted to painting Type 1 trucks, then 800 per day could be painted; if the painting shop were completely devoted to painting Type 2 trucks, then 700 per day could be painted. If the assembly shop where completely devoted to assembling truck 1 engines, then 1,500 per day could be assembled; if the assembly shop were completely devoted to assembling truck 2 engines, then 1,200 per day could be assembled. Each Type 1 truck contributes $300 to profit; each Type 2 truck contributes $500. The owner wants to maximize Truckco’s daily profit using linear programming. a) Determine the decision variables in the owners problem b) Determine the objective function c) Determine the constraints Page 1 of 7 d) Tomas, a worker at Truckco, has suggested manufacturing 380 Type 2 trucks and 320 Type 1 truck. Is this suggestion a feasible solution to the linear programming problem? If not why? If yes, do you think it is optimal? (justify your answer with one sentence) 3. Sólhúsgögn (6) Sólóhúsgögn, a manufacturer of handmade, high-quality furniture from Reykjavik, Iceland, produces desks, tables and chairs. Crafting each piece of furniture requires wood and two types of work: building and finishing. The following table specifies materiel and work requirements for each item, their daily availability, as well as the profits per item, e.g., for each desk sold the profit is $60. No profit is made of partial furniture; e.g., Sólhúsgögn can not sell half a table. Wood Building Finishing Profit Desk 8 cubic ft 2 hours 4 hours $60 Table 6 cubic ft 1.5 hours 2 hours $30 Chair 1 cubic ft 0.5 hour 1,5 hours $20 Availability 48 cubic ft 8 hours 20 hours Demand for handmade furniture vastly exceeds supply, and the firm assumes that it can sell anything it produces. The firm wants to maximize the profit given the resources available. a) Are all assumptions of linear program met? Why, why not? b) Now assume that all assumptions are met, and formulate the problem as a linear program. 4. Diet Problem (5) (This problem should be worked on individually, since the answers depend on individual preferences. If you are working in a team, please include solutions from both team members with your solutions for all the other problems) A classic example of a linear program is the diet problem. This problem is described in Chapter 4 of Applied Mathematical Programming (AMP) as Exercise 4.6. You can read details on the problem there. The goal in the diet problem is to find a mix of foods that satisfies minimum nutritional requirements and minimizes the overall cost. Here we ask you to find an excellent diet, not necessarily an optimal diet. Use the spreadsheet given on the website in Assignments ("diet_problem.xls") to find a really good diet for you. If you run solver on the spreadsheet as is, you will find a minimum cost diet, but you will likely come up with foods that you really don’t like very much. So, you can change the lower bounds and upper bounds on portions for each food to guarantee that the diet includes some foods that you really like and excludes foods that you don’t like. You can also change nutritional requirements if you want, but be reasonable. For example, you may wish to increase caloric amounts, or decrease them if you are on a diet. You can either minimize cost or maximize utility. (If you want to Page 2 of 7 maximize utility, you need to change the cell being optimized, and you need to put in utilities.) a) What is the “optimal” diet that you found using solver? (You can change information multiple times and solve multiple times. Here, we are looking only for the result that you like best.) What changes did you make in the data in order to come up with this answer? b) Is the answer in part “a” good for you? If it’s good why? If not, why not? c) Suppose that you permitted an additional 500 calories. Does your diet change? If so, list how the diet changes. (Try guessing in advance of running solver whether your diet will change.) 5. Scheduling Postal Workers (12) At the local post office, workers are scheduled for five days on followed by 2 days off, and this schedule is repeated weekly. Thus, a worker has the same two days off each week, and these days are consecutive (e.g., Sunday and Monday). The demand for workers is given in the table below. This demand must be met or exceeded on each day. The numbers represent the total number of workers who are working on that day. The cost of workers is $275 per weekday, and $300 per Saturday, and $325 on Sunday. Day Demand Mon 17 Tues 13 Wed 15 Thurs 19 Fri 14 Sat 16 Sun 11 a) Formulate a linear program that will minimize the total cost of postal workers needed to meet the daily demands. Note: the number of workers is integral, but for the purposes of this exercise, you may permit a fractional number of workers to start on any day. Hint: the key to this formulation is the correct choice of decision variables. Let x1 be the number of workers who work Monday to Friday, and have Saturday and Sunday off. (We can view these workers as working a shift of five days starting on Monday.). Let x2 be the number of workers who work Tuesday to Saturday. Define x3 to x7 similarly.) b) Use the Excel Solver sheet (the sheet labeled “5 Postal Workers” in homework1.xls ) provided on the web site as a starting point to solve this linear program. Note: the current Excel Solver spreadsheet is set to minimize the number of workers. You will need to adjust the LP formulation so that it minimizes the total cost of workers. [Error Checking Hint: The optimal objective function value is fractional and ends with an “8” when rounded to the nearest dollar.] c) How would the solution change if the number of workers required on Thursday lowered to 18? [Error Checking Hint: The optimal objective function value is an integer whose digits sum to 6.] d) Modify the spreadsheet so that it finds the solution with the minimum cost solution subject to the additional constraint that the number of workers who start on Saturday is at least 2 and the number of workers who start on Sunday is at least 2 (keep the minimum number of workers needed on Thursdays as 18). [Error Checking Hint: The optimal objective function value is an integer whose digits sum to 7.] Page 3 of 7 e) Write a linear program based on the following abstracted version of the Postal Worker Problem. At a local post office, workers are scheduled over n periods. The schedule repeats periodically. There are n possible shifts for the workers, one beginning in each of the n periods. Let aij = 1 if workers in shift j work during period i and zero otherwise. Let di denote the demand for workers in period i. Let ci be the cost of a worker during period i. Thus the cost of a shift is the sum of the costs of workers in the periods of the shift. Express as a linear program the problem of minimizing the cost of the workforce so as to meet or exceed demands in each period. For your decision variables, you should let xj denote the number of workers working on shift j. Let fj be the cost of worker on shift j. Clearly state what fj is in terms of the c’s. 6. Camera Production (8) (Based on AMP Exercise 1.9.) The Candid Camera Company manufactures three lines of cameras: the Cub, the Snap-a-matic, and the VIP, which sell for $5, $10, and $25, respectively. The distribution center requires that at least 250 Cubs, 375 Snap-a-matics, and 150 VIPs be produced each week. Producing each camera requires a certain amount of time to: (1) manufacture the body parts; (2) assemble the parts (lenses are purchased from outside sources and can be ignored in the production scheduling decision); and (3) inspect, test, and package the final product. The following table shows the requirements (in hours) for each line of camera. There are 250 hours per week of manufacturing time available, 350 hours of assembly, and 150 hours total to inspect, test, and package. Camera Line Cub Snap-a-matic VIP Manufacture 0.1 0.2 0.7 Assemble 0.2 0.35 0.1 Test, Inspect, Package 0.1 0.2 0.3 a) Formulate this production scheduling problem as a linear program that maximizes revenue. b) Use the Excel Solver to find the best production schedule. You will find the spreadsheet in the sheet labeled “6 Cameras” in Homework1.xls. Note: as in the previous problem, the number of each type of camera produced should be integral, but this constraint should be ignored for this problem. Error Checking Hint: The optimal objective function value is fractional and ends with a “7” when rounded to the nearest dollar. c) How would the solution change if the number of test/inspection hours per week increased to 170 (e.g., if a new part-time quality assurance employee was hired)? Error Checking Hint The optimal objective function value is an integer whose digits sum to 6. d) Suppose Candid Camera decides that, in addition to the minimum production levels for each camera line, Cubs should make up at least 35% of the total number of cameras produced each week. What is the optimal production schedule with this Page 4 of 7 added constraint? Error Checking Hint: The optimal objective function value is an integer whose digits sum to 6. Hint: Keep in mind that all constraints should be linear and therefore you need to think a little bit about how to formulate the new constraint. As an example say that you have a production problem with two products, y1 and y2 and that y2 should not exceed 40% of the total number units produced. This can be formulated as y2/(y1+y2) ≤0.4 to make the constraint linear, “move” (y1 +y2) to the right hand side and then simplify. 7. Flight Scheduling through Hubs (8). Consider the set of four flight segments below. It is part of an airline schedule involving thousands of flights every day. Flight # 1A 1B 2A 2B Depart Boston Chicago New York Chicago 8:00 AM 10:45 AM 7:45 AM 10:45 AM Arrive Chicago San Francisco Chicago Los Angeles 10:15 AM 12:15 PM 10:15 AM 12:15 PM Each airplane has 200 seats, and each seat can be allocated for each flight. From these four flights, one can obtain 8 distinct itineraries. Boston-Chicago, Boston - San Francisco, Boston - Los Angeles, New York - Chicago, New York - San Francisco, New York - Los Angeles, Chicago – San Francisco, and Chicago – Los Angeles. The fares and demands for the flights are given in the table below. Consider the problem of assigning seats on the flights to itineraries so that no more than 200 seats on any flight are assigned, and so that the demand for no itinerary is exceeded, and so as to maximize revenue. Itinerary B-C B-SF B-LA NY-C NY-SF NY-LA C-SF C-LA Fare and Demand $220 55 $300 110 $425 130 $225 88 $410 125 $450 85 $225 73 $250 51 a) Formulate this problem as a linear program. For your decision variables, let xBC denote the number of people on the itinerary from Boston to Chicago, and let xBS denote the number of people on the itinerary from Boston to San Francisco, etc. (If you want to use additional variables, that is OK, but this set of variables will be sufficient.) Page 5 of 7 b) Solve the problem using Excel. You will find the spreadsheet in the sheet labeled “7 Flight Schedulings” in homework1.xls, which might be helpful to you. In practice, this should be an integer program, in that there will be an integral number of persons assigned to each itinerary. However, for the purpose of this exercise, allow fractional assignments. Error Checking Hint: The optimal objective function value is an integer whose digits sum to 11. c) What would be the optimal solution if the airplanes could carry 210 passengers rather than 200 passengers? (Just write the solution and the solution value.) Error Checking Hint: The optimal objective function value is an integer whose digits sum to 23. d) What would be the optimal solution if each flight could carry 200 passengers, and each itinerary had to have at least 15 persons seats assigned? Error Checking Hint: The optimal objective function value is an integer whose digits sum to 11. 8. Scheduling Problem (6) A certain corporation has three plants with production capacity and plans to begin a production of a product that can be made in three sizes – large, medium and small – that yield a net unit profit of $420, $360 and $300 respectively. Plants 1, 2 and 3 have capacity to produce 750, 900, and 450 units per day of this product, respectively, regardless of the size or combination of sizes involved. The amount of available storage space also imposes a limitation on the production rates of the new product. Plants 1, 2, and 3 have 13,000, 12,000 and 5,000 square feet respectively, of in-process storage space available for a day’s production of this product. Each unit of the large, medium and small sizes produced per day requires 20, 15 and 12 square feet, respectively. Sales forecasts indicate that if available, 900, 1,200 and 750 units of the large, medium and small sizes, respectively would be sold per day. Management has decided that the plants should use the same percentage of their capacity to produce the new product. Managements wishes to know how much of each size should be produced by each plant to maximize profit. a) Formulate the problem as a linear program. You can ignore any restrictions on fractional solutions. (Hint, the key to the problem is to decide the decision variables, let xij be the amount produced of size j at factory i) Now consider the following problem: A certain corporations has 3 plants and plans to begin a production of a product that can be made in m sizes, that each yield a net unit profit of $pj. Each plant has a capacity to produce ci units per day of the product, regardless of the size or combination of sizes involved. Page 6 of 7 The amount of available storage space also imposes a limitation on the production rates of the new product. Plant i has si square feet of in-process storage space available for a day’s production of this product. Each unit of the product of size j takes fj square feet, respectively. Sales forecasts indicate that if available, kj units of product j could be sold per day. Management has decided that the plants should use the same percentage of their capacity to produce the new product. Managements wishes to know how much of each size should be produced by each plant to maximize profit. b) Formulate the problem as a linear program ( you can ignore any restrictions on fractional solutions). (Hint, use the same decision variables as in a; that is, let xij be the amount produced of size j at factory i). A. Challenging Problem From the informations sheet: “These problems are optional, but will count towards your raw grade on the homework. However, they are not necessary for obtaining 2.5 points (the maximum score)…. The challenge problems are recommended for those students who want to concentrate in Operations Research or who want to obtain a deeper knowledge of the material. In addition, at the end of the semester, the progress in challenge problems may help those students on a grade boundary” Formulation Challenge Consider a school district with I neighborhoods, J schools and G grades at each school. Each school j has a capacity of Cjg for grade g. In each neighborhood i, the student populations of grade g is Sig. Finally the distance of school j from neighborhood i is dij. Formulate a linear programming problem whose objective is to assign all students to schools, while minimizing the total distance traveled by all students. (You may ignore the fact that numbers of students must be integer.) Page 7 of 7