Horrible Harry's is a chain of 47 self service gas stations served by a small refinery and mixing plant. Each day's product requirements are met by blending feedstocks on hand at midnight. The volumes vary daily, depending on the previous day's refinery output and on bulk receipts.
The entire operation is run by the owner, Harry Oldaker. Although dozens of chemicals and byproducts are generated by the refinery, Harry's major concern is the retail distribution of gasoline products.
On a particular Tuesday there are sufficient volumes of leaded and unleaded regular gasoline's at the stations. Only the two hybrid petroleum products- gasohol and petrolmeth- will be shipped that day.
Both products are blended from 90-octane unleaded gasoline. Ethyl alcohol, the only additive to gasohol, cannot exceed 10% of the final product's volume. Petrolmeth mat contain both ethyl and methyl alcohols, but these combined ingredients must not exceed 30% of the final product's volume. The octane ratings are 120 for ethyl alcohol and 110 for methyl alcohol. Final product octane ratings must equal the average octane ratings for the ingredients by volume. Gasohol must have an octane rating of at least 91, and petrolmeth must have a rating of at least 93.
There are 20,000 gallons of gasoline presently available for blending, at a cost of $1.00 per gallon. Up to 5,000 gallons of methyl alcohol can be acquired for $.50 per gallon, and 3,000 gallons of ethyl alcohol are available at $1.50 per gallon. The demands are at least 10,000 gallons for gasohol and 5,000 gallons for petrolmeth.
Until now Harry has determined product blends by trail and error. A new staff analyst says that she can save a considerable amount of money by using a linear programming to establish a minimum-cost blending formulation. Harry is a bit skeptical, but he offers her the challenge to do better than the following:
9,000 gallons of unleaded gas to gasohol
1,000 gallons ethyl alcohol to gasohol
3,500 gallons of unleaded gas to petrolmeth
1,500 gallons of methyl alcohol to petrolmeth
Cost = $14,750
If the analyst can save a significant amount, she will use linear programming for all future blending decisions.
1. Formulate Horrible Harry's decision problem as a linear program.
2. Run the linear program on a computer to determine the optimal volume to be blended. How much lower is the cost of the optional solution than that of Harry's original plan?