ME30B Problems

Hey guys! Ok, got some examples of formulating LP problems here. I am taking these examples all from the book "Operations Research - Applications and Algorithms" by W.L. Winston. Now, I expect you to try the formulation for these problems before you go look at the answer (please try - you won't get the hang of these unless you practice them yourself) - you will have to click on the appropriate link to get the formulation answer. The solver worksheet links are located both on this page and the answer page - note you have to download the excel worksheets.

If you want to go directly to the page with the answers click here. If you need help in LP formulation, click here.

1. There are three factories on the Moniss River (1, 2, and 3). Each emits two types of pollutants (1 and 2) into the river. If the waste from each factory is processed, the pollution in the river can be reduced. It costs $15 to process a ton of factory 1 waste, and each ton processed reduces the amount of pollutant 1 by 0.10 ton and amount of pollutant 2 by 0.45 ton. It costs $10 to process a ton of factory 2 waste, and each ton processed will reduce the amount of pollutant 1 by 0.20 ton and the amount of pollutant 2 by 0.25 ton. It costs $20 to process a ton of factory 3 waste, and each ton processed will reduce the amount of pollutant 1 by 0.40 ton and the amount of pollutant 2 by 0.30 ton. The state wants to reduce the amount of pollutant 1 in the river by at least 30 tons and the amount of pollutant 2 in the river by at least 40 tons. Formulate and LP that will minimize the cost of reducing pollution by the desired amounts.

2. Goldilocks needs to find at least 12 lbs of gold and at least 18 lbs of silver to pay the monthly rent. There are two mines in which Goldilocks can find gold and silver. Each day that Goldilocks spends in mine 1, she finds 2 lbs of gold and 2 lbs of silver. Each day that Goldilocks spends in mine 2, she finds 1 lb of gold and 3 lbs of silver. Formulate an LP to help Goldilocks meet her requirements while spending as little time as possible in the mines.

3. You have decided to enter the candy business. You are considering producing two types of candies. Slugger Candy and Easy Out Candy, both of which consist of solely of sugar, nuts and chocolate. At present, you have in stock 100 oz of sugar, 20 oz of nuts, and 30 oz of chocolate. The mixture used to make Easy Out Candy must contain at least 20 % nuts. The mixture used to make Slugger Candy must contain at least 10% nuts and 10% chocolate. Each ounce of Easy Out Candy can be sold for 25 cents, and each ounce of Slugger Candy for 20 cents. Formulate and LP that will enable you to maximize your revenue from candy sales.

4. O.J. Juice Company sells bags of oranges and cartons of orange juice. O.J. grades oranges on a scale of 1 (poor) to 10 (excellent). At present, O.J. has on hand 100,000 lb of grade 9 oranges and 120, 000 lb of grade 6 oranges. The average quality of oranges sold in bags must be at least 7, and the average quality of the oranges used to produce orange juice must be at least 8. Each pound of oranges that is used for juice yields a revenue of $1.50 and incurs a variable cost (consisting of labour costs, variable overhead costs, inventory costs etc.) of $1.05. Each pound of oranges sold in bags yields a revenue of 50 cents and incurs a variable cost of 20 cents. Formulate and LP to help O.J. maximize profit.

5. Sunco oil has three different processes that can be used to manufacture various types of gasoline. Each process involves blending oils in the company's catalytic cracker. Running process 1 for an hour costs $5 and requires 2 barrels of crude oil 1 and 3 barrels of crude oil 2. The output from running process 1 for an hour is 2 barrels of gas 1 and 1 barrel of gas 2. Running process 2 for an hour costs $4 and requires 1 barrel of crude 1 and 3 barrels of crude 2. The output from process 2 for an hour is 3 barrels of gas 2. Running process 3 for an hour costs $1 and requires 2 barrels of crude 2 and 3 barrels of gas 2. The output from running process 3 for an hour is 2 barrels of gas 3. Each week, 200 barrels of crude 1, at $2/ barrel, and 300 barrels of crude 2 at $3/barrel, may be purchased. All gas produced can be sold at the following per-barrel prices: gas 1, $9; gas 2, $10; gas 3, $24. Formulate an LP whose solution will maximize revenues less costs. Assume that only 100 hours of time on the catalytic cracker are available each week.

6. Furnco manufactures tables and chairs. A table requires 40 board ft of wood, and a chair requires 30 board ft of wood. Wood may be purchased at a cost of $1 per board ft, and 40, 000 board ft of wood are available for purchase. It takes 2 hours of skilled labour to manufacture an unfinished table or an unfinished chair. Three more hours of skilled labour will turn an unfinished table into a finished table, and 2 more hours of skilled labour will turn an unfinished chair into a finished chair. A total of 6000 hours of skilled labour are available (and have already been paid for). All furniture produced can be sold at the following unit prices: unfinished table, $70; finished table, $140; unfinished chair, $60; finished chair, $110. Formulate an LP that will maximize the contribution to profit and manufacturing tables and chairs.

7. Tucker Inc. must produce 1000 Tucker automobiles. The company has four production plants. The cost of producing a Tucker at each plant, along with the raw material and labour needed is shown in the table below. The autoworkers' labour union requires that at least 400 cars be produced at plant 3; 3300 hours of labour and 4000 units of raw material are available for allocation to the four plants. Formulate and LP whose solution will enable Tucker Inc. to minimize the cost of producing 1000 cars.

Plant | Cost (in '000 of dollars) | Labour | Raw material |

1 | 15 | 2 | 3 |

2 | 10 | 3 | 4 |

3 | 9 | 4 | 5 |

4 | 7 | 5 | 6 |

8. HAL produces two types of computers: PCs and VAXes. The computers are produced in two locations: New York and Los Angeles. New York can produce up to 800 computers and Los Angeles, up to 1000 computers. HAL can sell up to 900 PCs and 900 VAXes. The profit associated associated with each production site and computer sale is as follows: New York - PC, $600; VAX, $800; Los Angeles - PC, $1000; VAX, $1300. The skilled labour required to build each computer at each location is as follows: New York - PC, 2 hours; VAX, 2 hours; Los Angeles - PC, 3 hours; VAX, 4 hours. A total of 4000 hours of labour are available. Labour is purchased at a cost of $20 per hour. Formulate a LP to maximize the profit received by HAL.

9. Old MacDonald's 200-acre farm sells wheat, alfalfa, and beef. Wheat sells for $30 per bushel, alfalfa sells for $20 per bushel and beef sells for $300 per ton. Up to 1000 bushels of wheat and up to 1000 bushels of alfalfa can be sold, but demand beef is unlimited. If an acre of land is devoted to raising wheat, alfalfa or beef, the yield and the required labour are given in the table below. Up to 2000 hours of labour can be purchased at $15 per hour. Each acre devoted to beef requires 5 bushels of alfalfa. Formulate a LP to maximize the profits received by Old MacDonald.

Crop | Yield/acre | Labour/acre |

Wheat | 50 bushels | 30 hours |

Alfalfa | 100 bushels | 20 hours |

Beef | 10 tons | 50 hours |