Linear Programming Applied Practice Solutions Problem 1: Finance- Allocation of Funds Madison Finance has a total of $ and auto loans. On the average, homeowner loans have a 10% yield a 12% annual rate of return. Management has also stipula loans should be greater than or equal to four times the total am total amount of loans of each type Madison should extend to ea tice Solutions of Funds Madison Finance has a total of $20 million earmarked for homeowner e average, homeowner loans have a 10% annual rate of return, whereas auto loans te of return. Management has also stipulated that the total amount of homeowner er than or equal to four times the total amount of automobile loans. Determine the of each type Madison should extend to each category in order to maximize its returns. Problem Manufacturing-Production Scheduling An acoustical company manufactures a be bought fully assembled or as a kit. Each cabinet is processed in the fabrications department. If the fabrication department only manufactures fully assembled cabi 200 units/day; but if it only manufactures kits, then it can produce 300 units/day. E contributes $40 of profit, while each cabinet kit contributes $50 of profit. How man how many kits should the company produce per day in order to maximize its profit ny manufactures a CD storage cabinet that can d in the fabrications department and the assembly lly assembled cabinets, then it can produce ce 300 units/day. Each fully assembled cabinet of profit. How many fully assembled units and maximize its profits? Problem Nutrition-Diet Planning Suppose a person has decided to include brown rice and The goal is to design the lowest-cost diet that provides certain minimum levels of p (or riboflavin). One cup of uncooked brown rice costs 21 cents and contains 15 gra 1/9 of a milligram of riboflavin. One cup of uncooked soy beans costs 14 cents and 270 calories, and 1/3 of a milligram of riboflavin. If minimum daily requirements a calories, and 1 milligram of riboflavin, design the lowest-cost diet meeting these sp lude brown rice and soybeans as part of his daily diet. minimum levels of protein, calories, and vitamin B2 and contains 15 grams of protein, 810 calories, and costs 14 cents and contains 22.5 grams of protein, aily requirements are 90 grams of protein, 1620 et meeting these specifications. Problem Manufacturing-Production Scheduling A company manufactures products A, B in three departments; I, II and III. The total available labor-hours per week for depa 900, 1080, and 840, respectively. The time requirements(in hour per unit) and profi as follows: Product Product Product A B C Dept. I 2 1 2 Dept. II 3 1 2 Dept. III 2 2 1 Profit $18 $12 $15 How many units of each product should the company produce in order to maximize tures products A, B and C. Each product is processed per week for departments I, II, and III are r per unit) and profit per unit for each product are n order to maximize its profit? Problem Manufacturing-Production Planning An oil refinery produces gasoline, jet fuel, gallon from the sale of these fuels are $0.15, $0.12, and $0.10 respectively. The re airline to deliver a minimum of 20,000 gallons per day of jet fuel and/or gasoline (o has a contract with a trucking firm to deliver a minimum of 50,000 gallons per day (or some of each). The refinery can produce 100,000 gallons of fuel per day, distr any fashion. It wishes to produce at least 5,000 gallons per day of each type of fue should be produced daily in order to maximize the profit? s gasoline, jet fuel, and diesel fuel. The profits per espectively. The refinery has a contract with an l and/or gasoline (or some of each). The refinery 000 gallons per day of jet fuel and/or gasoline f fuel per day, distributed among the fuels in of each type of fuel. How many gallons of each Problem Shipping - Product Mix A produce dealer in Florida ships oranges, grapefruits, a by truck. Each truckload consists of 100 crates, of which at least 20 crates must c 10 crates must contain grapefruits, at least 30 crates must contain avocados, and many crates of oranges as grapefruits. The profit per crate is $5 for oranges, $6 fo avocados. How many crates of each type should be shipped per truckload in order nges, grapefruits, and avocados to New York st 20 crates must contain oranges, at least tain avocados, and there must be at least as 5 for oranges, $6 for grapefruits, and $4 for r truckload in order to maximize profit? Problem Manufacturing-Production Planning A mining company owns 2 different mine and graded into three classes: high, medium, and low grade. The company has a plant with at least 13 tons of high-grade, 9 tons of medium-grade, and 24 tons of l two mines have different operating characteristics, as outlined in the table below: Mine #Tons/ #Tons/ #Tons/ Day Day Day High Mediu m Low #1 3 3 4 #2 2 1 6 The operating costs for Mine #1 are $12,000 per day and the operating costs for M Each mine operates at most 5 days per week. How many days per week should ea exceed the smelting plant contract and minimize the total cost? ns 2 different mines that produce ore, which is crushed The company has a contract to provide a smelting de, and 24 tons of low-grade ore per week. The n the table below: perating costs for Mine #2 are $10,000 per day. per week should each mine operate to meet or Problem Production A factory that manufactures knives sells sets of kitchen knives. The 2 utility knives and 1 chef's knife. The Regular Set consists of 2 utility knives, 1 ch The Deluxe Set consists of 3 utility knives, 1 chef's knife, and 1 slicer. Each Basic S Each Regular Set yields a $40 profit and each Deluxe Set yields a $60 profit. The utility knives, 400 chef's knives, and 200 slicers on hand. Assuming that all set are how many sets of each type should be made so that profit is maximized? tchen knives. The Basis Set consists of utility knives, 1 chef's knife, and 1 slicer. slicer. Each Basic Set yields a $30 profit. a $60 profit. The factory has 800 ming that all set are availale for sale, aximized? Problem Investments An investor is considering three types of investments: a high-risk v leases with a potential return of 15%, a medium-risk investment into stocks with a of 9%, and a relatively safe bond investment with a potential return of 5%. He has invest. Because of the risk, he will limit his investment in oil leases and stocks to 3 investment in oil leases and bonds to 50%. Assuming that investment returns are how much should be invested in each in order to maxmimize his return? ments: a high-risk venture into oil t into stocks with a potential return turn of 5%. He has $50,000 to ases and stocks to 30% and his estment returns are as expected, s return? Linear Programming Applied Practice Solutions Problem 1: Finance- Allocation of Funds Madison Finance has a total of $20 million earmarked for homeowner and auto loans. On the average, homeowner loans have a 10% annual rate of return, whereas auto loans yield a 12% annual rate of return. Management has also stipulated that the total amount of homeowner loans should be greater than or equal to four times the total amount of automobile loans. Determine the total amount of loans of each type Madison should extend to each category in order to maximize its returns. Solution: Let h = the amount of $$ earmarked for homeowner loans Let a = the amount of $$ earmarked for auto loans Objective Function: Returns, R = 10%*h + 12%*a Constraints h + a = 20,000,000 <---Total of $20 million earmarked for loans h >= 4a <---Total amount of homeowner loans should be greater than or equal to four times the total amount of automobile loans which becomes h - 4a >= 0 h>= 0, a >= 0 <---Non negativity constraints Using the Solver tool Objective Function $ 2,080,000.00 the amount of $$ earmarked for homeowner loans (h) $ 16,000,000.00 the amount of $$ earmarked for auto loans (a) $ 4,000,000.00 Decision Variables Constraints total of $20 million 20000000 20000000 0 0 nonnegativity for h 16000000 0 nonnegativity for a 4000000 0 home loans >= 4 times auto loans Conclusion Maximum return will occur when $16,000,000 is earmarked for home loans and $4,000,000 is earmarked for auto loans. The maximum return will be $2,080,000. Problem 2: Manufacturing-Production Scheduling An acoustical company manufactures a CD storage cabinet that can be bought fully assembled or as a kit. Each cabinet is processed in the fabrications department and the assembly department. If the fabrication department only manufactures fully assembled cabinets, then it can produce 200 units/day; but if it only manufactures kits, then it can produce 300 units/day. Each fully assembled cabinet contributes $40 of profit, while each cabinet kit contributes $50 of profit. How many fully assembled units and how many kits should the company produce per day in order to maximize its profits? Solution: Let f = the number of fully assembled cabinets Let k = the number of cabinet kits Objective Function: Profit, P = 40f + 50k Constraints f <= 200 <---No more than 200 assembled cabinets can be produced per day k <= 300 <---No more than 300 cabinet kits can be produced per day f>= 0, k >= 0 <---Non negativity constraints Using the Solver tool Objective Function 23000 Decision Variables the number of fully assembled cabinets (f) 200 the number of cabinet kits (k) 300 no more than 200 assembled cabinets per day 200 200 no more than 300 cabinet kits per day 300 300 nonnegativity for f 200 0 nonnegativity for k 300 0 Constraints Conclusion Maximum profit occurs when 200 fully assembled cabinets and 300 cabinet kits are produced each day. The maximum profit per day will be $23,000. Problem 3: Nutrition-Diet Planning Suppose a person has decided to include brown rice and soybeans as part of his daily diet. The goal is to design the lowest-cost diet that provides certain minimum levels of protein, calories, and vitamin B2 (or riboflavin). One cup of uncooked brown rice costs 21 cents and contains 15 grams of protein, 810 calories, and 1/9 of a milligram of riboflavin. One cup of uncooked soy beans costs 14 cents and contains 22.5 grams of protein, 270 calories, and 1/3 of a milligram of riboflavin. If minimum daily requirements are 90 grams of protein, 1620 calories, and 1 milligram of riboflavin, design the lowest-cost diet meeting these specifications. Solution: Let r = the number of cups of brown rice Let s = the number of cups of soybeans Objective Function: Cost, C = 0.21r + 0.14s Constraints 15r + 22.5s >= 90 <---Daily requirements of protein 810r + 270s >= 1620 <---Daily requirements of calories (1/9)r + (1/3)s >= 1 <---Daily requirements of riboflavin r>= 0, s >= 0 <---Non negativity constraints Using the Solver tool Objective Function 0.66 Decision Variables the number of cups of brown rice 0.8571 the number of cups of soybeans 3.4286 Constraints at least 90 gram of protein per day at least 1620 calories per day 90 90 1620 1620 at least 1 milligram of riboflavin per day 1.2381 1 nonnegativity for r 0.8571 0 nonnegativity for s 3.4286 0 Conclusion Ion order to minimize costs, 0.857 cups of uncooked brown rice and 3.429 cups of uncooked soybeans should be included in the daily diet. The minimum cost will be $0.66 per day. Problem 4: Manufacturing-Production Scheduling A company manufactures products A, B and C. Each product is processed in three departments; I, II and III. The total available labor-hours per week for departments I, II, and III are 900, 1080, and 840, respectively. The time requirements(in hour per unit) and profit per unit for each product are as follows: Product Product Product A B C Dept. I 2 1 2 Dept. II 3 1 2 Dept. III 2 2 1 Profit $18 $12 $15 How many units of each product should the company produce in order to maximize its profit? Solution: Let a = the number of units of product A Let b = the number of units of product B Let c = the number of units of product C Objective Function: Profit, P = 18*a + 12*b + 15*c Constraints 2a + b + 2c <= 900 <---Total labor-hours for department I 3a + b + 2c <= 1080 <---Total labor-hours for department II 2a + 2b + c <= 840 <---Total labor-hours for department III a >= 0, b >= 0, c >= 0 <---Non negativity constraints Using the Solver tool Objective Function $ 7,920.00 Decision Variables the number of units of product A 180 the number of units of product B 140 the number of units of product C 200 Constraints no more than 900 labor-hours for department I 900 900 no more than 1080 labor-hours for department II 1080 1080 no more than 840 labor-hours for department III 840 840 nonnegativity for a 180 0 nonnegativity for b 140 0 nonnegativity for c 200 0 Conclusion In order to maximize profit within these constraints, 180 units of product A, 140 units of product B, and 200 units of product C should be manufactured per week. The maximum weekly profit will be $7,920.00. Problem 5: Manufacturing-Production Planning An oil refinery produces gasoline, jet fuel, and diesel fuel. The profits per gallon from the sale of these fuels are $0.15, $0.12, and $0.10 respectively. The refinery has a contract with an airline to deliver a minimum of 20,000 gallons per day of jet fuel and/or gasoline (or some of each). The refinery has a contract with a trucking firm to deliver a minimum of 50,000 gallons per day of jet fuel and/or gasoline (or some of each). The refinery can produce 100,000 gallons of fuel per day, distributed among the fuels in any fashion. It wishes to produce at least 5,000 gallons per day of each type of fuel. How many gallons of each should be produced daily in order to maximize the profit? Solution: Let g = the number of gallons of gasoline produced daily Let j = the number of gallons of jet fuel produced daily Let d = the number of diesel gallons produced daily Objective Function: Profit, P = 0.15g + 0.12j + 0.10d Constraints g + j + d >= 20,000 <---Number of gallons contracted with the airline g + j + d >= 50,000 <---Number of gallons contracted with the trucking firm g + j + d <= 100,000 <---The refinery can produce up to 100,000 gallons per day g >= 5,000, j >= 5,000, d >= 5,000 <---Refinery wishes to produce at least 5,000 gallons of each type daily g >= 0, j >= 0, d >= 0 <---Non negativity constraints (not really needed b/c of the constraints in the above line) Using the Solver tool Objective Function $ 14,600.00 Decision Variables the number of gallons of gasoline produced daily 90000 the number of gallons of jet fuel produced daily 5000 the number of gallons of diesel produced daily 5000 Constraints number of gallons contracted with the airline 100000 number of gallons contracted with the trucking firm 100000 20000 50000 refinery can produce up to 100,000 gallons per day 100000 100000 at least 5000 gallons per day of gasoline 90000 5000 at least 5000 gallons per day of jet fuel 5000 5000 at least 5000 gallons per day of diesel 5000 5000 Conclusion In order to maximize daily profit, the refinery must produce 90,000 gallons of gasoline, 5,000 gallons of jet fuel, and 5,000 gallons of diesel fuel daily. The maximum daily profit will be $14,600.00. Problem 6: Shipping - Product Mix A produce dealer in Florida ships oranges, grapefruits, and avocados to New York by truck. Each truckload consists of 100 crates, of which at least 20 crates must contain oranges, at least 10 crates must contain grapefruits, at least 30 crates must contain avocados, and there must be at least as many crates of oranges as grapefruits. The profit per crate is $5 for oranges, $6 for grapefruits, and $4 for avocados. How many crates of each type should be shipped per truckload in order to maximize profit? Solution: Let o = the number of crates of oranges Let g = the number of crates of grapefruits Let a = the number of crates of avocados Objective Function: Profit, P = 5o + 6g + 4a Constraints o + g + d = 100 <---Each truck contains 100 crates. o >= 20 <---At least 20 crates of oranges g >= 10 <---At least 10 crates of grapefruits a >= 30 <---At least 30 crates of avocados o >= g <---There must be more crates of oranges than grapefruits. which becomes o - g >= 0 o >= 0, g >= 0, a >= 0 <---Non negativity constraints Using the Solver tool Objective Function $ 505.00 Decision Variables the number of crates of oranges 35 the number of crates of grapefruits 35 the number of crates of avocados 30 Constraints Each truck contains 100 crates. 100 100 At least 20 crates of oranges 35 20 At least 10 crates of grapefruits 35 10 At least 30 crates of avocados 30 30 More crates of oranges than grapefruits 0 0 Non negativity constraints for orange crates 35 0 Non negativity constraints for grapefruit crates 35 0 Non negativity constraints for avocado crates 30 0 Conclusion In order to maximize profit, each truck should deliver 35 crates of oranges, 35 crates of grapefruits, and 30 crates of avocados to New York. The maximum profit will be $505.00. Problem 7: Manufacturing-Production Planning A mining company owns 2 different mines that produce ore, which is crushed and graded into three classes: high, medium, and low grade. The company has a contract to provide a smelting plant with at least 13 tons of high-grade, 9 tons of medium-grade, and 24 tons of low-grade ore per week. The two mines have different operating characteristics, as outlined in the table below: Mine #Tons/Day #Tons/Day #Tons/Day High Medium Low #1 3 3 4 #2 2 1 6 The operating costs for Mine #1 are $12,000 per day and the operating costs for Mine #2 are $10,000 per day. Each mine operates at most 5 days per week. How many days per week should each mine operate to meet or exceed the smelting plant contract and minimize the total cost? Solution: Let x = the number of days per week that Mine 1 operates per week Let y = the number of days per week that Mine 2 operates per week Objective Function: Cost, C = 12000x + 10000y Constraints 3x + 2y >= 13 <---number of tons of high-grade 3x + y >= 9 <---number of tons of high-grade 4x + 6y >= 24 <---number of tons of low-grade x <= 5, y <= 5 <---each mine operates up to 5 days per week x >= 0, y >= 0 <---Non negativity constraints Using the Solver tool Objective Function $ 56,000.00 Decision Variables the number of days/week for Mine #1 3 the number of days/week for Mine #2 2 Constraints number of tons of high-grade 13 number of tons of high-grade 11 13 9 number of tons of low-grade 24 24 no more than 5 days/week for Mine #1 3 5 no more than 5 days/week for Mine #2 2 5 nonnegativity for x 3 0 nonnegativity for y 2 0 Conclusion In order to minimize costs and satisfy the contract for the smelting plant, Mine #1 should operate 3 days per week and Mine #2 should operate 2 days per week. The minimum operating cost would be $56,000.00 Problem 8: Production A factory that manufactures knives sells sets of kitchen knives. The Basis Set consists of 2 utility knives and 1 chef's knife. The Regular Set consists of 2 utility knives, 1 chef's knife, and 1 slicer. The Deluxe Set consists of 3 utility knives, 1 chef's knife, and 1 slicer. Each Basic Set yields a $30 profit. Each Regular Set yields a $40 profit and each Deluxe Set yields a $60 profit. The factory has 800 utility knives, 400 chef's knives, and 200 slicers on hand. Assuming that all set are availale for sale, how many sets of each type should be made so that profit is maximized? Solution: Let b = the number of Basic Sets Let r = the number of Regular Sets Let d = the number of Deluxe Sets Objective Function: Profit, P = 30b + 40r + 60d Constraints 2b + 2r + 3c <= 800 <---number of utility knives b + r + c <= 400 <---number of chef's knives 0b + b + c <= 200 <---number of slicers b >= 0, r >= 0, c <= 0 <---Non negativity constraints Using the Solver tool Objective Function $ 15,000.00 Decision Variables the number of Basic Sets (b) the number of Regular Sets ( r) 100 0 the number of Deluxe Sets (d) 200 number of utility knives 800 800 number of chef's knives 300 400 number of slicers 200 200 nonnegativity for b 100 0 nonnegativity for r 0 0 nonnegativity for c 200 0 Constraints Conclusion In order to maximize profit, 100 Basic Sets, 0 Regular Sets, and 200 Deluxe Sets need to be made. Maximum profit will be $15,000. Problem 9: Investments An investor is considering three types of investments: a high-risk venture into oil leases with a potential return of 15%, a medium-risk investment into stocks with a potential return of 9%, and a relatively safe bond investment with a potential return of 5%. He has $50,000 to invest. Because of the risk, he will limit his investment in oil leases and stocks to 30% and his investment in oil leases and bonds to 50%. Assuming that investment returns are as expected, how much should be invested in each in order to maxmimize his return? Solution: Let o = the amount invested in oil leases Let s = the amount invested in stocks Let b = the amount invested in bonds Objective Function: Return, R = 15%*o + 9%*s + 5%*b Constraints o + s + b = 50,000 <---total invested o + s <= 30%*50,000 <---limit invested in oil leases and stocks o + b <= 50%*50,000 <---limit invested in oil leases and bonds o >= 0, s >= 0, b <= 0 <---Non negativity constraints Using the Solver tool Objective Function 2600 Decision Variables the amount invested in oil lease (o) the amount invested in stocks (s) 0 15000 the amount invested in bonds (b) 25000 total invested 40000 50000 invested in oil and stocks 15000 15000 invested in oil and bonds Constraints 25000 25000 nonnegativity for o 0 0 nonnegativity for s 15000 0 nonnegativity for b 25000 0 Conclusion The maximum return of $2,600 will be attained when $0 is invested in oil leases, $15,000 is invested in stocks, and $25,000 is invested in bonds. So only $40,000 should be invested