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 x_{i} = no. of tons of factory i waste processed. (i = 1, 2 and 3).
Min z = 
15 x_{1} 
+ 10 x_{2} 
+ 20 x_{3} 



0.1 x_{1} 
+ 0.2 x_{2} 
+ 0.4 x_{3} 
≥ 30 
(Pollutant 1 constraint) 

0.45 x_{1} 
+ 0.25 x_{2} 
+ 0.3 x_{3} 
≥ 40 
(Pollutant 2 constraint) 

x_{1}, x_{2}, x_{3} 
≥ 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 x_{i} = no. of days spent in mine i (i =1,2)
Min z = 
x_{1} 
+ x_{2} 



2 x_{1} 
+ x_{2} 
≥ 12 
(Gold constraint) 

2 x_{1} 
+ 3 x_{2} 
≥ 18 
(Silver constraint) 

x_{1}, x_{2} 
≥ 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 x_{ij} = 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 = x_{11} + x_{12} + x_{13}
Ounces of Slugger Candy produced = x_{21} + x_{22} + x_{23}
Therefore, to have 20 % of nuts in Easy Out Candy, then:
Multiplying by x_{11} + x_{12} + x_{13} on both sides and rearranging, we have
0.8 x_{12} – 0.2 x_{11} – 0.2 x_{13} ≥ 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 x_{11} 
+ 25 x_{12} 
+ 25x_{13} 
+ 20 x_{21} 
+ 20 x_{22} 
+ 20 x_{23} 



x_{11} 


+ x_{21} 


≤ 100 
(Sugar) 


+ x_{12} 


+ x_{22} 

≤ 20 
(Nuts) 



x_{13} 


+ x_{23} 
≤ 30 
(Chocolate) 

0.2x_{11} 
+ 0.8x_{12} 
 0.2 x_{13} 



≥ 0 
(Nuts in Easy Out) 




 0.1 x_{21} 
+ 0.9x_{22} 
 0.1 x_{23} 
≥ 0 
(Nuts in Slugger) 




 0.1 x_{21} 
 0.1 x_{22} 
+ 0.9x_{23} 
≥ 0 
(Choc. in Slugger) 

x_{ij} _{ }≥ 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 x_{ij} = 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 = x_{11} + x_{21}
Total no. of pounds of oranges sold as juice = x_{12} + x_{22}
Therefore, to have an average grade of 7 for oranges sold in the bags will be:
_{ }
Therefore, crossmultiplying and rearranging we have
x_{11} + 2x_{21} ≥ 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) (x_{11} + x_{21}) = $0.30 x_{11} + $0.30 x_{21}
Therefore, cost of oranges as juice = ($1.50  $1.05) (x_{12} + x_{22}) = $0.45 x_{12} + $0.45 x_{22}
Max z = 
0.30 x_{11} 
+ 0.45 x_{12} 
+0.30 x_{21} 
+ 0.45 x_{22} 



x_{11} 
+ x_{12} 


≤ 120,000 
(Grade 6 oranges) 



x_{21} 
+ x_{22} 
≤ 100, 000 
(Grade 9 oranges) 

 x_{11} 

+ 2 x_{21} 

≥ 0 
( ≥ grade 7 bags) 


 2 x_{12} 

+ x_{22} 

(≥ grade 8 juice) 

x_{ij} 
≥ 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 perbarrel 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 x_{i } = no. of hours process i is run per week (where i =1,2,3)
Let o_{i} = no. of barrels of oil i that is purchased per week (i =1,2)
Let g_{2} = 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(2x_{1}) 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(2x_{3}). Gas 2 sold is represented by g_{2}, 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(2x_{1}) + 10 g_{2} + 24(2x_{3}) – 5x_{1} – 4x_{2} – x_{3} – 2o_{1} – 3o_{2}
Therefore, rewriting we have z = 13x_{1} – 4x_{2} + 47x_{3} + 10 g_{2} – 2o_{1} – 3o_{2}
In addition the total oil 1 used in process 1 and 2 is, i.e. o_{1} = 2x_{1} + x_{2}
Therefore, rewriting we would have 2 x_{1} + x_{2} – o_{1} = 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.
g_{2} + 3 x_{3} = x_{1} + 3 x_{2}
Rewriting
g_{2} + 3x_{3} – x_{1} – 3 x_{2} = 0 (gas 2 production balance)
Max z = 
13 x_{1} 
 4 x_{2} 
+ 47 x_{3} 
+ 10 g_{2} 
 2 o_{1} 
 3 o_{2} 



2 x_{1} 
x_{2} 


 o_{1} 

= 0 
(Oil 1 used) 

3 x_{1} 
+ 3 x_{2} 
+ 2 x_{3} 


 o_{2} 
= 0 
(Oil 2 used) 





o_{1} 

≤ 200 
(Oil 1 constraint) 






o_{2} 
≤ 300 
(Oil 2 constraint) 

x_{1} 
+ 3 x_{2} 
 3 x_{3} 
 g_{2} 


= 0 
(Gas 2 production) 

x_{1} 
+ x_{2} 
+ x_{3} 
_{ } 
_{ } 
_{ } 
≤100 
(Processing time) 

x_{i, }o_{i}, g_{2} 
≥ 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 x_{i} = no. of tucker automobiles produced at plant i.
Min z = 
15 x_{1} 
+ 10 x_{2} 
+ 9 x_{3} 
+ 7 x_{4} 



x_{1} 
+ x_{2} 
+ x_{3} 
+ x_{4} 
≥ 1000 
(automobile constraint) 



x_{3} 

≥ 400 
(plant 3 constraint) 

2 x_{1} 
+ 3 x_{2} 
+ 4 x_{3} 
+ 5 x_{4} 
≤ 3300 
(labour constraint) 

3 x_{1} 
+ 4 x_{2} 
+ 5 x_{3} 
+ 6 x_{4} 
≤ 4000 
(raw material) 

x_{i} 
≥ 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 200acre 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 




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