Massachusetts Institute of TechnologyMASSACHUSETTS INSTITUTE OF TECHNOLOGY 15.053 – Introduction to Optimization (Spring 2005) Problem Set 1, Due February 10th , 2005 You will need 46 points out of 54 to receive a grade of 2.5. 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 3x1 +2x1x2 subject to 3x1+5x1x2 ≤ 7 x1 ≥ 0 x2 ≥ 0 b) minimize 32x1+2x3 subject to x1+x2+x3 ≤ 7 c) maximize 3x1 + 5x2 + x32 subject to 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 7d) 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. Desk Table Chair Availability Wood 8 cubic ft 6 cubic ft 1 cubic ft 48 cubic ft Building 2 hours 1.5 hours 0.5 hour 8 hours Finishing 4 hours 2 hours 1,5 hours 20 hours Profit $60 $30 $20 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 7maximize 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 Mon Tues Wed Thurs Fri Sat Sun Demand 17 13 15 19 14 16 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