Set #1 1. Delectation Delicatessen Topics: Linear programming formulation, product-mix. Difficulty: Low Delectation Delicatessen is the best take-out sandwich shop in the neighborhood, and business is booming. Business is so good that it can sell all of the sandwiches that it can make. Delectation only sells two types of sandwiches: the \"Surf-n-Turf\" which sells for $6.95, and the \"Fish-n-Fowl\" which sells for $5.50. Ingredient lists from the recipes for the two sandwiches are: The Fish-n-Fowl: 0.25 pounds of tuna fish salad 0.5 pounds of sliced turkey 2 slices of rye bread 1 slice of pumpernickel bread The Surf-n-Turf: 0.40 pounds of sliced roast beef 0.25 pounds of tuna fish salad 1 slice of rye bread 1 slice of pumpernickel bread Delectation gets all of its meats and breads from Edith's Wholesale Restaurant Supply. Based on conversations he has had with his customers, Delectation's proprietor Joe has become convinced that it is the high quality of Edith's ingredients, as well as the deli's unique sandwich recipes, that makes Delectation Deli so popular. To assure a steady supply of ingredients, Delectation has entered into a long-term contract with Edith where, for a fixed sum of money, Edith's delivers 60 pounds of roast beef, 200 pounds of tuna salad, 260 pounds of turkey, 60 loaves of rye bread, and 32 loaves of pumpernickel bread each day. There are 25 usable slices in each loaf of bread. a) Delectation wants to determine the number of Fish-n-Fowl and the number of Surf-n-Turf sandwiches it should make each day to maximize the deli's revenues. Formulate this problem as a linear program. You should formulate the problem algebraically. Clearly define the decision variables and their units. Write the objective function and the constraints as linear functions of the decision variables. You should also identify each constraint by attaching a descriptive label to it. b) Implement the formulation in a spreadsheet and solve the problem using a spreadsheet optimizer. Attach a one-page printout showing your model and the optimal mix. OPIM 621: Decision Models & Uncertainty Page 1 Fall 2007 Homework Problem Set #1 2. Power Plant Problem Topics: Linear programming formulation, converting fractional constraints to linear constraints. Difficulty: Medium The management of One Mile Island Power Company (OMIPC) wants to make better short and long run decisions regarding the operation of its Keyport electric generation plant. Management's goal is to be able to run the plant to achieve maximum power generation during peak load hours. Power output is limited both by engineering capacity of the equipment and by environmental considerations. In particular, the plant must comply with the following emission standards: Maximum SO2 emissions are 3,300 parts per million (PPM) in the stack gas at all times. Maximum particulate emissions are 12 kg per hour. Coal is brought to the Keyport plant by railroad and dumped into stockpiles in the coal yard. From there it is carried by conveyor belt to a pulverizer and fed directly into the combustion chamber at the desired rate. The heat produced by the combustion produces steam, which drives the generation turbines. Two types of coal are used by the plant: hard coal which is expensive but has low sulfur content and softer chunky coal which, while cheaper, is smoky and has higher sulfur content. Technical specs on the coals are: Hard Coal Soft Coal SO2 Gas Output (PPM) 1,800 3,800 Particulate Output (kg/ton) 0.65 1.05 Heat Rating (BTU/ton) 24,000 20,000 When mixing the hard and soft coals, the sulfur content in the output is a weighted average of the two outputs. For example, a mixture consisting of equal parts of the coals would emit 2,800 PPM of sulfur gas. Similarly, a mixture consisting of three times as much hard coal as soft coal would emit 2,300 PPM of SO2. If the pulverizer were fed with hard coal only, it could handle 16 tons per hour. Similarly, if it were fed with soft coal only, it could handle 24 tons per hour. Thus, an input of 8 tons/hour of hard coal would require 50% of the entire pulverizer capacity. An input of 18 tons/hour of soft coal would require 75% of the entire pulverizer capacity. The pulverizer can be fed with any combination of hard and soft coal that does not exceed its capacity. OPIM 621: Decision Models & Uncertainty Page 2 Fall 2007 Homework Problem Set #1 The conveyor can handle up to 20 tons per hour of either coal. The conveyor can be fed with any combination of hard and soft coal that does not exceed its capacity. a) The management of OMIPC wants to determine the mix of coals that will maximize the amount of power (in BTU) produced per hour. This will be its summer-time peak hour operating plan. Algebraically formulate an LP to find the optimal plan, but do not solve the LP. Define the decision variables and their units of measurement and label each constraint in terms of the requirements of the problem. (Hint: This is a nontrivial formulation. Define your decision variables in terms of tons of coal used per hour. The constraints on PPM of SO2 and the pulverizer capacity might be the most difficult to formulate. For the former, it may help to express the SO2 content of a coal mix as the weighted average of the individual SO2 contents. Note that a nonlinear expression of the form x / y 1 can be converted into the equivalent linear form: x - y 0. For the pulverizer capacity constraint, it may help first to represent the constraint graphically, and then to deduce the algebraic version. The statement that the pulverizer can handle up to 16 tons per hour when fed only with hard coal and up to 24 tons per hour when fed only with soft coal gives you two points on the graph; and the line connecting them represents the constraint's boundary. Do not be discouraged if you fail to make much headway with this problem! Once you see the formulation, however, you should be able to see how it works.) b) OMIPC needs to produce 390,000 BTU per hour in off-peak conditions. If hard coal costs 15% more than soft coal, what will be the least cost way for OMIPC to meet this requirement? Reformulate your LP model above to solve this problem? Report only the algebraic formulation of the model. OPIM 621: Decision Models & Uncertainty Page 3 Fall 2007