Solutions to the problems

Here are the solutions to the problems[1] found in the previous page.

Question 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.

Let xi = no. of tons of factory i waste processed. (i = 1, 2 and 3).

 Min z = 15 x1 +    10 x2 +  20 x3 0.1 x1 +   0.2 x2 + 0.4 x3 ≥ 30 (Pollutant 1 constraint) 0.45 x­1 + 0.25 x2 + 0.3 x3 ≥ 40 (Pollutant 2 constraint) x1, x2, x3 ≥ 0

Question 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.

Let xi = no. of days spent in mine i (i =1,2)

 Min z = x1 +   x2 2 x1 +   x2 ≥ 12 (Gold constraint) 2 x1 +  3 x2 ≥ 18 (Silver constraint) x1, x2 ≥ 0

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.

Let xij = no. of ounces of product j in candy i. Where j = 1,2 and 3 represents sugar, nuts and chocolate respectively and i = 1 and 2 represents Easy Out and Slugger Candy respectively.

Note:    Ounces of Easy Out Candy produced = x11 + x­12 + x13

Ounces of Slugger Candy produced = x21 + x22 + x23

Therefore, to have 20 % of nuts in Easy Out Candy, then:

Multiplying by x11 + x­12 + x13 on both sides and rearranging, we have

0.8 x12 – 0.2 x11 – 0.2 x13 ≥ 0                                      (Nuts in Easy Out Constraint)

The same procedure will follow for finding the no. of ounces of nuts and chocolate in Slugger Candy.

 Max z = 25 x11 + 25 x12 + 25x13 + 20 x21 + 20 x22 + 20 x23 x11 +      x21 ≤ 100 (Sugar) +      x12 +      x22 ≤ 20 (Nuts) x13 +      x23 ≤ 30 (Chocolate) -0.2x11 + 0.8x12 - 0.2 x13 ≥ 0 (Nuts in Easy Out) - 0.1 x21 + 0.9x22 - 0.1 x23 ≥ 0 (Nuts in Slugger) - 0.1 x21 - 0.1 x22 + 0.9x23 ≥ 0 (Choc. in Slugger) xij  ≥ 0

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.

Let xij = no. of pounds of grade i oranges used in product from j. Where i = 1: grade 6 and i = 2: grade 9. Where j = 1: bags and j = 2: juice

Note: Total no. of pounds of oranges sold in bags is = x11 + x21

Total no. of pounds of oranges sold as juice = x12 + x22

Therefore, to have an average grade of 7 for oranges sold in the bags will be:

Therefore, cross-multiplying and rearranging we have

-x11 + 2x21 ≥ 0                                                                         (Bags Grade 7 constraint)

The same procedure will apply for finding the average grade of oranges in juice.

Note also the cost of oranges in bag = Revenue – variable cost = (\$0.50 - \$0.20) (x11 + x21) = \$0.30 x11 + \$0.30 x21

Therefore, cost of oranges as juice = (\$1.50 - \$1.05) (x12 + x22) = \$0.45 x12 + \$0.45 x22

 Max z = 0.30 x11 + 0.45 x12 +0.30 x21 + 0.45 x22 x11 +         x12 ≤ 120,000 (Grade 6 oranges) x21 +         x22 ≤ 100, 000 (Grade 9 oranges) -  x11 +     2 x21 ≥ 0 ( ≥ grade 7 bags) -      2 x12 +         x22 (≥ grade 8 juice) xij ≥ 0

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.

Let xi  = no. of hours process i is run per week (where i =1,2,3)

Let oi = no. of barrels of oil i that is purchased per week (i =1,2)

Let g2 = no. of barrels of gas 2 sold per week

This is a production problem – this particular problem is kind of difficult to formulate.

This problem is formulated in terms of oil used rather than gas produced. Only the variable for gas 2 sold is used since, the remaining gas 2 will be used in producing gas 3.

Now for the objective function, in the first process, running it for 1 hr, 2 barrels of gas 1 is produced, thus 9(2x1) will give the revenue from gas 1 (remember, gas 1 is sold for \$9), similarly for gas 3, the process 3 generates 2 barrels of gas 3, thus the revenue from gas 3 is 24(2x3). Gas 2 sold is represented by g2, there is no need to represent it in terms of hours – plus it would have presented a problem in formulating the LP to show the amount of gas 2 from process 1 and process 2 were used in process 3. In addition, we have to account for the cost for oil and processing hours.

So, z = 9(2x1) + 10 g2 + 24(2x3) – 5x1 – 4x2 – x3 – 2o1 – 3o2

Therefore, rewriting we have z = 13x1 – 4x2 + 47x3 + 10 g2 – 2o1 – 3o2

In addition the total oil 1 used in process 1 and 2 is, i.e. o1 = 2x1 + x2

Therefore, rewriting we would have 2 x1 + x2 – o1 = 0.

Similarly, total oil 2 used will be found.

Note, that gas 2 production will be equal to gas 2 sold plus the gas 2 used in 3, that would have been produced in process 1 and 2, which we would represent by using the amount of gas 2 produced and used from each process i.e.

g2 + 3 x3 = x1 + 3 x2

Rewriting

g2 + 3x3 – x1 – 3 x2 = 0                                                       (gas 2 production balance)

 Max z = 13 x1 - 4  x2 + 47 x3 + 10 g2 - 2  o1 - 3  o2 2 x1 x2 -     o1 = 0 (Oil 1 used) 3 x1 + 3 x2 + 2   x3 -      o2 = 0 (Oil 2 used) o1 ≤ 200 (Oil 1 constraint) o2 ≤ 300 (Oil 2 constraint) x1 + 3 x2 -   3  x3 -      g2 = 0 (Gas 2 production) x1 +    x2 +      x3 ≤100 (Processing time) xi, oi, g2 ≥ 0

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.

Let ft =  no. of finished tables

uft = no. of unfinished tables

fc = no of finished chairs

ufc = no. of unfinished chairs.

For the objective function the profit from furniture = Revenue – Board cost. Since board cost is \$1 per ft then, for finished chairs, the profit is = (\$110 - \$30) fc = \$80 fc.

The same will apply for other furniture.

 Max z = 30   uft + 30   ufc + 100   ft + 90    fc 40  uft + 30   ufc + 40    ft +  30  fc ≤ 40,000 (Board constraint) 2  uft +   2   ufc +   5    ft +    4  fc ≤ 6, 000 (Hours constraint) uft, ufc fc, ft ≥0

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

Let xi = no. of tucker automobiles produced at plant i.

 Min z = 15   x1 +    10 x2 +  9   x3 + 7    x4 x1 +         x2 +       x3 +       x4 ≥ 1000 (automobile constraint) x3 ≥ 400 (plant 3 constraint) 2     x­1 + 3      x2 + 4    x3 + 5    x4 ≤ 3300 (labour constraint) 3     x1 + 4      x2 + 5    x3 + 6    x4 ≤ 4000 (raw material) xi ≥ 0

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.

Let nyp: no. of PCs produced in New York

lap: no. of PCs produced in Los Angeles

nyv: no. of VAXs produced in New York

lav: no. of VAXs produced in Los Angeles

The total profit for each computer = profit – labour cost

Therefore, for a nyp computers then = (\$600 – \$20(2)) NYP = \$560 nyp

The same will be done for the remaining computers

 Max z = 560  nyp +940   lap + 760 nyv +1220 lav nyp +        nyv ≤ 800 (New York comps.) lap +        lav ≤ 1000 (LA computers) nyp +        lap ≤ 900 (PCs constraint) nyv +        lav ≤ 900 (VAXs constraint) 2       nyp + 3      lap + 2     nyv + 4     lav ≤ 4000 (labour hours) nyp, nyv lav,lap ≥0

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

Let w = no. of  acres under wheat

a = no. of acres under alfalfa for sale

b = no. of acres under beef cattle

ab = no. of acres under alfalfa for beef

For the objective function, the profit from a product = Revenue – Labour costs

Therefore for wheat, = [(30)(50) – (15)(30)] w = 1050 w.

Note, that it costs \$30 per wheat bushel and each acre yields 50 bushels of wheat.

Also, note that any alfalfa used for beef would not be sold, ab, and thus the profit is negative, since associated with it, is a labour cost.

Note, that since 5 bushels of alfalfa is needed for every acre of beef cattle, then 5 bushels corresponds to 5/100 acres of alfalfa needed for every acre of beef cattle i.e. 100 bushels of alfalfa is produced for every acre. Therefore, the no. of acres dedicated for alfalfa for beef must equal to the no. of acres dedicated for beef.

0.05 ab – b = 0

 Max z = 1050   w +1700 a + 2250 b - 300  ab w +         a +          b +        ab ≤ 200 (acres constraint) a ≤ 1000 (alfalfa constraint) w ≤ 1000 (wheat constraint) 30       w + 20    a + 50    b + 20    ab ≤ 2000 (labour constraint) -         b + 0.05 ab = 0 (alfalfa for beef) w, a, b, ab ≥ 0

Back to ME30B main page

[1] Examples taken from Winston, W. (1994) “Operations Research – Application and Algorithms”, 3rd Ed. Duxbury Press, California