SELECTED LP APPLICATIONS
This section presents realistic LP models in which the definition of the variables and the construction of the objective function and constraints are not as straight-forward as in the case of the two-variable model. The areas covered by these appli-cations include the following:
1. Urban planning.
2. Currency arbitrage.
4. Production planning and inventory control.
5. Blending and oil refining.
6. Manpower planning.
Each model is fully developed and its optimum solution is analyzed and interpreted.
1. Urban Planning
Urban planning deals with three general areas: (1) building new housing develop-ments, (2) upgrading inner-city deteriorating housing and recreational areas, and (3) planning public facilities (such as schools and airports). The constraints associated with these projects are both economic (land, construction, financing) and social (schools, parks, income level). The objectives in urban planning vary. [n new housing develop-ments, profit is usually the motive for undertaking the project. In the remaining two categories, the goals involve social, political, economic, and cultural considerations. In-deed, in a publicized case in 2004, the mayor of a city in Ohio wanted to condemn an old area of the city to make way for a luxury housing development. The motive was to increase tax collection to help alleviate budget shortages. The example presented in this section is fashioned after the Ohio case.
Example 2.3-1 (Urban Renewal Model)
The project involves two phases: (1) demolishing substandard houses to provide land for the new development, and (2) building the new development. The following is a summary of the situation.
1. As many as 300 substandard houses can be demolished. Each house occupies a 25-acre lot. The cost of demolishing a condemned house is $2000.
2. Lot sizes for new single-, double-, triple-, and quadruple-family homes (units) are .18, .28, A, and.5 acre, respectively. Streets, open space, and utility easements account for 15% of available acreage.
3. In the new development the triple and quadruple units account for at least 25% of the total. Single units must be at least 20% of all units and double units at least 10%.
4. The tax levied per unit for single, double, triple, and quadruple units is $1,000, $1,900, $2,700, and $3,400, respectively.
5. The construction cost per unit for single-, double-, triple-, and quadruple- family homes is $50,000, $70,000, $130,000, and $160,000, respectively. Financing through a local bank can amount to a maximum of $15 million.
How many units of each type should be constructed to maximize tax collection?
Mathematical Model: Besides determining the number of units to be constructed of each type of housing, we also need to decide how many houses must be demolished to make room for the new development. Thus, the variables of the problem can be defined as follows:
xl = Number of units of single-family homes
x2 = Number of units of double-family homes
x3 = Number of units of triple-family homes
x4 = Number of units of quadruple-family homes
x5 = Number of old homes to be demolished
The objective is to maximize total tax collection from all four types of homes-that is,
Maximize z = 1000x1 + 1900x2 + 2700x3 + 3400x4
The first constraint of the problem deals with land availability.
Acreage used for. New home construction ≤ Net available acreage
From the data of the problem we have
Acreage needed for new homes = .18xl + .28x2 + Ax3 + .5x4
To determine the available acreage, each demolished home occupies a .25-acre lot, thus netting .25x5 acres. Allowing for 15% open space, streets, and easements, the net acreage available is .85(.25x5) = .2125x5' The resulting constraint is
.18x1 + .28x2 + .4x3 + .5x4 ≤ .2125x5
.18x1 + .28x2 + 4x3 + .5x4 + .2125x5 ≤ 0
The number of demolished homes cannot exceed 300, which translates to
X5 ≤ 300
Next we add the constraints limiting the number of units of each home type.
(Number of single units) ≥ (20% of all units)
(Number of double units) ≥ (10% of all units)
(Number of triple and quadruple units) ≥ (25% of all units)
These constraints translate mathematically to
x1 ≥ .2(x1 + x2 + x3 + X4)
x2 ≥ .1(x1 + x2 + x3 + x4)
x3 + x4 ≥ .25(x1 + x2 + x3 + x4)
The only remaining constraint deals with keeping the demolishition/construction cost within the allowable budget-that is,
(Construction and demolition cost) ≤ (Available budget)
Expressing all the costs in thousands of dollars, we get
(50x1 + 70x2+130x3 + 160x4 ) + 2 x5 ≤ 15000
The complete model thus becomes
Maximize z = 1000x1 + 1900x2 + 2700x3 + 3400x4
.18xl + .28x2 + .4x3 + .5x4 - .2125x5 ≤ 0
x5 ≤ 300
- .8x1 + .2x2 + .2x3 + .2x4 ≤ 0
.1x1 - .9x2 + .1x3 + .1x4 ≤ 0
.25x1 + .25x2 - .75x3 - .75x4 ≤ 0
50x1 + 70x2 + 130x3 + 160x4 + 2x5 ≤ 15000
x1, x2, x3, x4, x5 ≥ 0
The optimum solution (using file ampIEX2.3-1.txt or solverEx2.3-l.xls) is:
Number of single homes = x1 = 35.83 ≈ 36 units
Number of double homes = x2 = 98.53 ≈ 99 units
Number of triple homes = x3 = 44.79 ≈ 45 units
Number of quadruple homes =x4 ≈ 0 units
Number of homes demolished = x5 = 244.49 ≈ 245 units
Remarks. Linear programming does not guarantee an integer solution automatically, and this is the reason for rounding the continuous values to the closest integer. The rounded solution calls for constructing 180 (= 36 + 99 + 45) units and demolishing 245 old homes, which yields $345,600 in taxes. Keep in mind, however, that, in general, the rounded solution may not be feasible. In fact, the current rounded solution violates the budget constraint by $70,000 (verify!). Interestingly, the true optimum integer solution (using the algorithms in Chapter 9) is xl = 36, x2 = 98, x3 = 45, x4 = 0, and x5 = 245 with z = $343,700. Carefully note that the rounded solution yields a better objective value, which appears contradictory. The reason is that the rounded solution calls for producing an extra double home, which is feasible only if the bud-get is increased by $70,000.
PROBLEM SET 2.3A
1. A realtor is developing a rental housing and retail area. The housing area consists of efficiency apartments, duplexes, and single-family homes. Maximum demand by potential renters is estimated to be 500 efficiency apartments, 300 duplexes, and 250 single-family homes, but the number of duplexes must equal at least 50% of the number of efficiency apartments and single homes. Retail space is proportionate to the number of home units at the rates of at least 10 ft2 , 15 ft2, and 18 ft2 for efficiency, duplex, and single family units, respectively. However, land availability limits retail space to no more than 10,000 ft2. The monthly rental income is estimated at $600, $750, and $1200 for efficiency-, duplex-, and single-family units, respectively. The retail space rents for $100/ft2. Determine the optimal retail space area and the number of family residences.
2. The city council of Fayetteville is in the process of approving the construction of a new 200,000-ft2 convention center. Two sites have been proposed, and both require exercising the "eminent domain" law to acquire the property. The following table provides data about proposed (contiguous) properties in both sites together with the acquisition cost.
Partial acquisition of property is allowed. At least 75% of property 4 must be acquired if site 1 is selected, and at least 50% of property 3 must be acquired if site 2 is selected.
Although site 1 property is more expensive (on a per ft2 basis), the construction cost is less than at site 2, because the infrastructure at site 1 is in a much better shape. Construction cost is $25 million at site 1 and $27 million at site 2. Which site should be selected, and what properties should be acquired?
3. A city will undertake five urban renewal housing projects over the next five years. Each project has a different starting year and a different duration. The following table provides the basic data of the situation:
Projects 1 and 4 must be finished completely within their durations. The remaining two projects can be finished partially within budget limitations, if necessary. However, each project must be at least 25% completed within its duration. At the end of each year, the completed section of a project is immediately occupied by tenants and a proportional amount of in-come is realized. For example, if 40% of project 1 is completed in year 1 and 60% in year 3, the associated income over the five-year planning horizon is .4 x $50,000 for year 2) + .4 x $50,000 (for year 3) + (.4 + .6) x $50,000 (for year 4) + (.4 + .6) X $50,000 (for year 5) = (4 X .4 + 2 X .6) X $50,000. Determine the optimal schedule for the projects that will maximize the total income over the five-year horizon. For simplicity, disregard the time value of money.
4. The city of Fayetteville is embarking on an urban renewal project that will include lower-and middle-income row housing, upper-income luxury apartments, and public housing. The project also includes a public elementary school and retail facilities. The size of the elementary school (number of classrooms) is proportional to the number of pupils, and the retail space is proportional to the number of housing units. The following table pro-vides the pertinent data of the situation:
The new school can occupy a maximum space of 2 acres at the rate of at most 25 pupils per room. TIle operating annual cost per school room is $10,000. The project will be locat-ed on a 50-acre vacant property owned by the city. Additionally, the project can make use of an adjacent property occupied by 200 condemned slum homes. Each condemned home occupies .25 acre. The cost of buying and demolishing a slum unit is $7000. Open space, streets, and parking lots consume 15% of total available land.
Develop a linear program to determine the optimum plan for the project.
Realco owns 800 acres of undeveloped land on a scenic lake in the heart of the Ozark Mountains. In the past, little or no regulation was imposed upon new developments around the lake. The lake shores are now dotted with vacation homes, and septic tanks, most of them improperly installed, are in extensive use. Over the years, seepage from the septic tanks led to severe water pollution. To curb further degradation of the lake, county officials have approved stringent ordinances applicable to all future developments: (1) Only single-, double-, and triple-family homes can be constructed, with single-family homes accounting for at least 50% of the total. (2) To limit the number of septic tanks, minimum lot sizes of 2, 3, and 4 acres are required for single-, double-, and triple-family homes, respectively. (3) Recreation areas of 1 acre each must be established at the rate of one area per 200 families. (4) To preserve the ecology of the lake, underground water may not be pumped out for house or garden use. The president of Realco is studying the possibility of developing the 800-acre property. The new development will include single-, double-, and triple-family homes. It is estimated that 15% of the acreage will be allocated to streets and utility easements. Realco estimates the returns from the different housing uni ts as follows:
The cost of connecting water service to the area is proportionate to the number of units constructed. However, the county charges a minimum of $100,000 for the project. Additionally, the expansion of the water system beyond its present capacity is limited to 200,000 gallons per day during peak periods. The following data summarize the water service connection cost as well as the water consumption, assuming an average size family:
Develop an optimal plan for Realco.
Consider the Realco model of Problem 5. Suppose that an additional 100 acres of land can be purchased for $450,000, which will increase the total acreage to 900 acres. Is this a profitable deal for Realco?