Forecasting: Time series and trend analysis
395
1. Understand the difference between LP and integer programming.
2. Understand and solve the three types of integer pro- gramming problems.
10.1 Introduction
10.2 Integer Programming
10.3 Modeling with 0–1 (Binary) Variables
10.4 Goal Programming
10.5 Nonlinear Programming
3. Formulate and solve goal programming problems using Excel and QM for Windows.
4. Formulate nonlinear programming problems and solve using Excel.
After completing this chapter, students will be able to:
10
CHAPTER OUTLINE
LEARNING OBJECTIVES
Integer Programming, Goal Programming, and Nonlinear Programming
CHAPTER
Summary • Glossary • Solved Problems • Self-Test • Discussion Questions and Problems • Internet Homework
Problems • Case Study: Schank Marketing Research • Case Study: Oakton River Bridge • Bibliography
10.1 Introduction
This chapter presents a series of other important mathematical programming models that arise when some of the basic assumptions of LP are made more or less restrictive. For example, one assumption of LP is that decision variables can take on fractional values such as
. Yet a large number of business problems can be solved only if variables have integer values. When an airline decides how many Boeing 757s or Boeing 777s to purchase, it can’t place an order for 5.38 aircraft; it must order 4, 5, 6, 7, or some other integer amount. In this chapter we present the general topic of integer programming, and we specifically consider the use of special variables that must be either 0 or 1.
A major limitation of LP is that it forces the decision maker to state one objective only. But what if a business has several objectives? Management may indeed want to maximize profit, but it might also want to maximize market share, maintain full employment, and minimize costs. Many of these goals can be conflicting and difficult to quantify. South States Power and Light, for example, wants to build a nuclear power plant in Taft, Louisiana. Its objectives are to maxi- mize power generated, reliability, and safety, and to minimize cost of operating the system and the environmental effects on the community. Goal programming is an extension to LP that can permit multiple objectives such as these.
Linear programming can, of course, be applied only to cases in which the constraints and objective function are linear. Yet in many situations this is not the case. The price of various products, for example, may be a function of the number of units produced. As more are made, the price per unit decreases. Hence an objective function may read as follows:
Because of the squared terms, this is a nonlinear programming problem. Let’s examine each of these extensions of LP—integer, goal, and nonlinear programming—
one at a time.
Maximize profit = 25X1 - 0.4X1 2 + 30X2 - 0.5X2
2
X1 = 0.33, X2 = 1.57, or X3 = 109.4
Integer programming is the extension of LP that solves problems requiring integer solutions.
Goal programming is the extension of LP that permits more than one objective to be stated.
Nonlinear programming is the case in which objectives or constraints are nonlinear.
10.2 Integer Programming
An integer programming model is a model that has constraints and an objective function identi- cal to that formulated by LP. The only difference is that one or more of the decision variables has to take on an integer value in the final solution. There are three types of integer program- ming problems:
1. Pure integer programming problems are cases in which all variables are required to have integer values.
2. Mixed-integer programming problems are cases in which some, but not all, of the decision variables are required to have integer values.
3. Zero–one integer programming problems are special cases in which all the decision variables must have integer solution values of 0 or 1.
Solving an integer programming problem is much more difficult than solving an LP prob- lem. The solution time required to solve some of these may be excessive even on the fastest computer.
Harrison Electric Company Example of Integer Programming The Harrison Electric Company, located in Chicago’s Old Town area, produces two products popular with home renovators: old-fashioned chandeliers and ceiling fans. Both the chandeliers and fans require a two-step production process involving wiring and assembly. It takes about 2 hours to wire each chandelier and 3 hours to wire a ceiling fan. Final assembly of the chande- liers and fans requires 6 and 5 hours, respectively. The production capability is such that only 12 hours of wiring time and 30 hours of assembly time are available. If each chandelier
396 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Solution values must be whole numbers in integer programming.
There are three types of integer programs: pure integer programming; mixed-integer programming; and 0–1 integer programming.
6
5
4
3
2
1
0 1 2 3 4 5 6
X2
X1
6X1 + 5X2 ≤ 30
+ = Possible Integer Solution
Optimal LP Solution (X1 = 3.75, X2 = 1.5, Profit = $35.25)
2X1 + 3X2 ≤ 12
FIGURE 10.1 Harrison Electric Problem
10.2 INTEGER PROGRAMMING 397
produced nets the firm $7 and each fan $6, Harrison’s production mix decision can be formu- lated using LP as follows:
where
With only two variables and two constraints, Harrison’s production planner, Wes Wallace, employed the graphical LP approach (see Figure 10.1) to generate the optimal solution of
chandeliers and ceiling fans during the production cycle. Recognizing that the company could not produce and sell a fraction of a product, Wes decided that he was dealing with an integer programming problem.
It seemed to Wes that the simplest approach was to round off the optimal fractional solu- tions for and to integer values of chandeliers and ceiling fans. Unfortu- nately, rounding can produce two problems. First, the new integer solution may not be in the feasible region and thus is not a practical answer. This is the case if we round to . Second, even if we round off to a feasible solution, such as , it may not be the optimal feasible integer solution.
Listing all feasible solutions and selecting the one with the best objective function value is called the enumeration method. Obviously this can be quite tedious for even small problems, and it is virtually impossible for large problems as the number of feasible integer solutions is extremely large.
X1 = 4, X2 = 1 X1 = 4, X2 = 2
X2 = 2X1 = 4X2X1
X2 = 1.5X1 = 3.75
X2 = number of ceiling fans produced
X1 = number of chandeliers produced
X1, X2 Ú 0
6X1 + 5X2 … 30 1assembly hours2 subject to 2X1 + 3X2 … 12 1wiring hours2 Maximize profit = $7X1 + $6X2
Although enumeration is feasible for some small integer program- ming problems, it can be difficult or impossible for large ones.
Rounding off is one way to reach integer solution values, but it often does not yield the best solution.
398 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Table 10.1 lists the entire set of integer-valued solutions to the Harrison Electric problem. By inspecting the right-hand column, we see that the optimal integer solution is
Note that this integer restriction results in a lower profit level than the original optimal LP solu- tion. As a matter of fact, an integer programming solution can never produce a greater profit than the LP solution to the same problem; usually, it means a lesser value.
Using Software to Solve the Harrison Integer Programming Problem QM for Windows and Excel spreadsheets are capable of handling integer programming prob- lems such as the Harrison Electric case. Program 10.1A illustrates the input data to QM for Windows, and Program 10.1B provides the results.
To use QM for Windows, select the Integer & Mixed Integer Programming module. Specify the number of constraints and the number of variables. Program 10.1A provides the input screen, with data entered for the Harrison Electric example. The last row of the table allows you to classify each variable according to type of variable (Integer, Real, or 0–1). Once all variables have been correctly specified, click Solve, and you will see the output in Program 10.1B.
Solver in Excel 2010 can also be used to solve this problem, as shown in Program 10.2. The Solver parameters and selections are shown, and the key formulas are displayed. To specify that the variables must be integers, a special constraint is entered in Solver. After opening the Solver Parameters window, select Add just as you would do to enter other constraints. When the Add Constraint window opens, enter the range containing the solution values, as shown in Program 10.2. Then click the tab to open the drop-down menu and then change the type of con- straint to int, for integer. Click OK to return to the Solver Parameters window. Then enter the other constraints, specify the parameters and selections, and click Solve. The solution is shown to be 5 chandeliers and 0 fans, for a profit of $35.
X1 = 5 chandeliers, X2 = 0 ceiling fans, with a profit = $35
An important concept to understand is that an integer programming solution can never be better than the solution to the same LP problem. The integer problem is usually worse in terms of higher cost or lower profit.
CHANDELIERS CEILING FANS PROFIT
0 0 $0
1 0 7
2 0 14
3 0 21
4 0 28
5 0 35 Optimal solution
0 1 6 to integer programming
1 1 13 problem
2 1 20
3 1 27
4 1 34 Solution if rounding
0 2 12 is used
1 2 19
2 2 26
3 2 33
0 3 18
1 3 25
0 4 24
1$7X1 � $6X221X221X12
TABLE 10.1 Integer Solutions to the Harrison Electric Company Problem
10.2 INTEGER PROGRAMMING 399
PROGRAM 10.1A QM for Windows Input Screen for Harrison Electric Problem
PROGRAM 10.1B QM for Windows Solution Screen for Harrison Electric Problem
PROGRAM 10.2 Excel 2010 Solver Solution for Harrison Electric Problem
Set Objective: D5 By Changing cells: B4:C4 To: Max Subject to the Constraints:
D8:D9 <= F8:F9 B4:C4 = integer
Solving Method: Simplex LP � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy D5 to D8:D9
400 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Mixed-Integer Programming Problem Example Although the Harrison Electric example was a pure integer problem, there are many situations in which some of the variables are restricted to be integers and others are not. The following is an example of such a mixed-integer programming problem.
Bagwell Chemical Company, in Jackson, Mississippi, produces two industrial chemicals. The first product, xyline, must be produced in 50-pound bags; the second, hexall, is sold by the pound in dry bulk and hence can be produced in any quantity. Both xyline and hexall are com- posed of three ingredients—A, B, and C—as follows:
Defining the Problem The U. S. Postal Service (USPS) operates one of the largest transporation networks in the world, delivering one-fifth of a trillion items every year. The inherent transportation-related problems are, obviously, very large. Nevertheless, USPS’s problem is how to deliver mail in the most cost-efficient manner possible.
Developing a Model A large-scale integer program known as the Highway Corridor Analytical Program (HCAP) was developed to help solve the problem. More specifically, the HCAP solves a Vehicle Routing Problem (VRP) with known pickup and delivery locations. That is, the model takes into account all the different modes of transporta- tion, the capacities inherent to the system, all the pickup locations, and all the delivery locations and then assigns trucks to routes as the (binary) decision variable of interest.
Acquiring Input Data Geographic information system (GIS) data of all the pickup and delivery locations is integrated into the model. Realistic time and distance constraints were placed on the model to prevent drivers from being assigned a pickup in one area and a delivery in an area too far away.
Testing the Solution The model was loaded into a large-scale mathematical programming solver. Several versions and models were tested.
Analyizing the Results Decision makers found improvements in several areas. For example, one of the model outputs resulted in a 20% reduction in redundant trips.
Implementing the Results USPS has already realized over $5 million in transportation savings due to its implementation of the HCAP integer programming optimization model. Efforts are under way to seek out additional efficiencies through the use of HCAP.
Source: Based on A. Pajunas, E. J. Matto, M. Trick, and L.F. Zuluaga. “Optimizing Highway Transporation at the United States Postal Service,” Interfaces 37, 6(2007): 515-525.
MODELING IN THE REAL WORLD: Integer Programming at the USPS
Defining the Problem
Developing a Model
Acquiring Input Data
Testing the Solution
Analyzing the Results
Implementing the Results
AMOUNT PER 50-POUND BAG AMOUNT PER POUND AMOUNT OF INGREDIENTS OF XYLINE (LB) OF HEXALL (LB) AVAILABLE
30 0.5 2,000 lb—ingredient A
18 0.4 800 lb—ingredient B
2 0.1 200 lb—ingredient C
Bagwell sells 50-pound bags of xyline for $85 and hexall in any weight for $1.50 per pound.
10.2 INTEGER PROGRAMMING 401
Limits are used, and the best solution available after a certain time is presented.
Notice that only X must be integer, while Y may be any real number.
PROGRAM 10.3 QM for Windows Solution for Bagwell Chemical Problem
If we let X = number of 50-pound bags of xyline produced and Y = number of pounds of hexall (in dry bulk) mixed, Bagwell’s problem can be described with mixed-integer programming:
.
Note that Y represents bulk weight of hexall and is not required to be integer valued.
USING QM FOR WINDOWS AND EXCEL TO SOLVE BAGWELL’S INTEGER PROGRAMMING MODEL The solution to Bagwell’s problem is to produce 44 bags of xyline and 20 pounds of hexall, yielding a profit of $3,770. (The optimal linear solution, by the way, is to produce 44.444 bags of xyline and 0 pounds of hexall, yielding a profit of $3,777.78.) This is first illustrated in Program 10.3, which uses the Mixed Integer Programming module in QM for Windows. Note that variable X is identified as Integer, while Y is Real in Program 10.3.
In Program 10.4, we use Excel to provide an alternative solution method.
X, Y Ú 0 and X integer
2X + 0.1Y … 200
18X + 0.4Y … 800
subject to 30X + 0.5Y … 2,000
Maximize profit = $85X + $1.50Y
Mixed-Integer Programming in the IBM Supply Chain
The manufacture of semiconductors is a very expensive opera- tion, often requiring investments in the billions of dollars. The IBM Systems and Technology Group has used mixed-integer program- ming (MIP) along with other operations research techniques to plan and optimize its semiconductor supply chain. The business of supply-chain optimization (SCO) has been deemed business critical and must incorporate a variety of planning criteria and constraints.
IBM uses a central planning engine (CPE) to balance the supply chain’s resources against the semiconductor demand. The MIP is an important part of this CPE. The MIP model is a cost-minimization problem with constraints related to material flows and other aspect of the supply chain.
Some of the models involved in SCO include sourcing among multiple plants, the logistics of interplant shipping, and the devel- opment of production plans for all the plants within the system. They may involve a planning horizon of a few days, a few months, or even a few years, depending on the specific type of application.
While LP is commonly used in supply-chain modeling, it is neces- sary to use models in which some of the variables are required to be integers. The resulting MIP models are so large (millions of vari- ables) that they cannot be solved with even the fastest computers. Therefore, the IBM Systems and Technology Group developed heuristic methods to solve the optimization models as part of the company’s advanced planning systems.
The benefits of the CPE are many. The on-time deliveries improved by 15%. A 25% to 30% reduction in inventory was observed as a result of the model. The company also observed an improvement in asset allocation of between 2% and 4% of costs. This model allowed “what-if” questions to be quickly answered— a process that was not possible in the past. Strategic planning was also facilitated by the CPE. IBM benefited greatly from the use of MIP in managing the semiconductor supply chain.
Source: Based on Brian. T. Denton, John Forrest, and R. John Milne. “IBM Solves a Mixed-Integer Program to Optimize Its Semiconductor Supply Chain,” Interfaces 36, 5 (September–October 2006): 386–399.
IN ACTION
PROGRAM 10.4 Excel 2010 Solver Solution for Bagwell Chemical Problem
10.3 Modeling with 0–1 (Binary) Variables
In this section we demonstrate how 0–1 variables can be used to model several diverse situa- tions. Typically a 0–1 variable is assigned a value of 0 if a certain condition is not met and 1 if the condition is met. Another name for a 0–1 variable is a binary variable. A common problem of this type, the assignment problem, involves deciding which individuals to assign to a set of jobs. (This is discussed in Chapter 9.) In this assignment problem, a value of 1 indicates a per- son is assigned to a specific job, and a value of 0 indicates the assignment was not made. We present other types of 0–1 problems to show the wide applicability of this modeling technique.
Capital Budgeting Example A common capital budgeting decision involves selecting from a set of possible projects when budget limitations make it impossible to select all of these. A separate 0–1 variable can be defined for each project. We will see this in the following example.
Quemo Chemical Company is considering three possible improvement projects for its plant: a new catalytic converter, a new software program for controlling operations, and expanding the warehouse used for storage. Capital requirements and budget limitations in the next two years prevent the firm from undertaking all of these at this time. The net present value (the future value of the project discounted back to the present time) of each of the projects, the capital require- ments, and the available funds for the next two years are given in Table 10.2.
To formulate this as an integer programming problem, we identify the objective function and the constraints as follows:
Total funds used in year 2 … $16,000
subject to Total funds used in year 1 … $20,000
Maximize net present value of projects undertaken
402 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Set Objective: D5 By Changing cells: B4:C4 To: Max Subject to the Constraints:
D8:D10 <= F8:F10 B4 = integer
Solving Method: Simplex LP � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy D5 to D8:D10
10.3 MODELING WITH 0–1 (BINARY) VARIABLES 403
We define the decision variables as
The mathematical statement of the integer programming problem becomes
Program 10.5 provides the Solver solution in Excel 2010. You specify the variables to be binary (0–1) by selecting bin from the Add Constraint window. The optimal solution is X1 = 1,
X1, X2, X3 = 0 or 1
7,000X1 + 4,000X2 + 8,000X3 … 16,000
subject to 8,000X1 + 6,000X2 + 12,000X3 … 20,000
Maximize NPV = 25,000X1 + 18,000X2 + 32,000X3
X3 = b1 if warehouse expansion project is funded
0 otherwise
X2 = b1 if software project is funded
0 otherwise
X1 = b1 if catalytic converter project is funded
0 otherwise
PROGRAM 10.5 Excel 2010 Solver Solution for Quemo Chemical Problem
PROJECT NET PRESENT VALUE YEAR 1 YEAR 2
Catalytic Converter $25,000 $8,000 $7,000
Software $18,000 $6,000 $4,000
Warehouse Expansion $32,000 $12,000 $8,000
Available Funds $20,000 $16,000
TABLE 10.2 Quemo Chemical Company Information
Set Objective: E5 By Changing cells: B4:D4 To: Max Subject to the Constraints:
E8:E9 <= G8:G9 B4:D4 = binary
Solving Method: Simplex LP � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy E5 to E8:E9
with an objective function value of 57,000. This means that Quemo should fund the catalytic converter project and the warehouse expansion project but not the new software project. The net present value of these investments will be $57,000.
Limiting the Number of Alternatives Selected One common use of 0–1 variables involves limiting the number of projects or items that are se- lected from a group. Suppose that in the Quemo Chemical Company example, the company is required to select no more than two of the three projects regardless of the funds available. This could be modeled by adding the following constraint to the problem:
If we wished to force the selection of exactly two of the three projects for funding, the following constraint should be used:
This forces exactly two of the variables to have values of 1, whereas the other variable must have a value of 0.
Dependent Selections At times the selection of one project depends in some way upon the selection of another project. This situation can be modeled with the use of 0–1 variables. Now suppose in the Quemo Chem- ical problem that the new catalytic converter could be purchased only if the software was pur- chased also. The following constraint would force this to occur:
or, equivalently,
Thus, if the software is not purchased, the value of is 0, and the value of must be 0 also because of this constraint. However, if the software is purchased , then it is possible that the catalytic converter could be purchased also, although this is not required.
If we wished for the catalytic converter and the software projects to either both be selected or both not be selected, we should use the following constraint:
or, equivalently,
Thus, if either of these variables is equal to 0, the other must be 0 also. If either of these is equal to 1, the other must be 1 also.
Fixed-Charge Problem Example Often businesses are faced with decisions involving a fixed charge that will affect the cost of fu- ture operations. Building a new factory or entering into a long-term lease on an existing facility would involve a fixed cost that might vary depending upon the size of the facility and the loca- tion. Once a factory is built, the variable production costs will be affected by the labor cost in the particular city where it is located. An example follows.
Sitka Manufacturing is planning to build at least one new plant, and three cities are being considered: Baytown, Texas; Lake Charles, Louisiana; and Mobile, Alabama. Once the plant or plants have been constructed, the company wishes to have sufficient capacity to produce at least 38,000 units each year. The costs associated with the possible locations are given in Table 10.3.
In modeling this as an integer program, the objective function is to minimize the total of the fixed cost and the variable cost. The constraints are: (1) total production capacity is at least 38,000; (2) number of units produced at the Baytown plant is 0 if the plant is not built, and it is no more than 21,000 if the plant is built; (3) number of units produced at the Lake Charles plant is 0 if the plant is not built, and it is no more than 20,000 if the plant is built; (4) number of units produced at the Mobile plant is 0 if the plant is not built, and it is no more than 19,000 if the plant is built.
X1 - X2 = 0
X1 = X2
1X1 = 12 1X2 = 12 X1X2
X1 - X2 … 0
X1 … X2
X1 + X2 + X3 = 2
X1 + X2 + X3 … 2
X2 = 0, X3 = 1
404 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
10.3 MODELING WITH 0–1 (BINARY) VARIABLES 405
Then we define the decision variables as
The integer programming problem formulation becomes
Notice that if (meaning Baytown plant is not built), then (number of units produced at Baytown plant) must equal zero also due to the second constraint. If , then may be any integer value less than or equal to the limit of 21,000. The third and fourth constraints are similarly used to guarantee that no units are produced at the other locations if the plants are not built. The optimal solution, shown in Program 10.6, is
This means that factories will be built at Lake Charles and Mobile. Each of these will produce 19,000 units each year, and the total annual cost will be $1,757,000.
Financial Investment Example Numerous financial applications exist with 0–1 variables. A very common type of problem in- volves selecting from a group of investment opportunities. The following example illustrates this application.
The Houston-based investment firm of Simkin, Simkin, and Steinberg specializes in rec- ommending oil stock portfolios for wealthy clients. One such client has made the following specifications: (1) at least two Texas oil firms must be in the portfolio, (2) no more than one in- vestment can be made in foreign oil companies, (3) one of the two California oil stocks must be purchased. The client has up to $3 million available for investments and insists on purchas- ing large blocks of shares of each company that he invests in. Table 10.4 describes various stocks that Simkin considers. The objective is to maximize annual return on investment subject to the constraints.
Objective function value = 1,757,000
X1 = 0, X2 = 1, X3 = 1, X4 = 0, X5 = 19,000, X6 = 19,000
X4X1 = 1 X4X1 = 0
X1, X2, X3 = 0 or 1; X4, X5, X6 Ú 0 and integer
X6 … 19,000X3
X5 … 20,000X2
X4 … 21,000X1
subject to X4 + X5 + X6 Ú 38,000
Minimize cost = 340,000X1 + 270,000X2 + 290,000X3 + 32X4 + 33X5 + 30X6
X6 = number of units produced at Mobile plant
X5 = number of units produced at Lake Charles plant
X4 = number of units produced at Baytown plant
X2 = b1 if factory is built in Mobile
0 otherwise
X2 = b1 if factory is built in Lake Charles
0 otherwise
X1 = b1 if factory is built in Baytown
0 otherwise
The number of units produced must be 0 if the plant is not built.
Here is an example of stock portfolio analysis wiht 0–1 programming
ANNUAL VARIABLE COST ANNUAL SITE FIXED COST PER UNIT CAPACITY
Baytown, TX $340,000 $32 21,000
Lake Charles, LA $270,000 $33 20,000
Mobile, AL $290,000 $30 19,000
TABLE 10.3 Fixed and Variable Costs for Sitka Manufacturing
To formulate this as a 0–1 integer programming problem, Simkin lets be a 0–1 integer variable, where if stock i is purchased and if stock i is not purchased:
The solution from using Solver in Excel 2010 is shown is Program 10.7
Xi = 0 or 1 for all i
1$3 million limit2 480X1 + 540X2 + 680X3 + 1,000X4 + 700X5 + 510X6 + 900X7 … 3,000
X6 + X7 = 1 1California constraint2X2 + X3 … 1 1foreign oil constraint2 subject to X1 + X4 + X5 Ú 2 1Texas constraint2 Maximize return = 50X1 + 80X2 + 90X3 + 120X4 + 110X5 + 40X6 + 75X7
Xi = 0Xi = 1 Xi
406 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Firms usually have more than one goal.
PROGRAM 10.6 Excel 2010 Solver Solution for Sitka Manufacturing Problem
Set Objective: H5 By Changing cells: B4:G4 To: Min Subject to the Constraints:
H8 >= J8 H9:H11 <= J9:J11 B4:D4 = binary
Solving Method: Simplex LP � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy H5 to H8:H11
EXPECTED ANNUAL COST FOR BLOCK OF STOCK COMPANY NAME RETURN ($1,000s) SHARES ($1,000s)
1 Trans-Texas Oil 50 480
2 British Petroleum 80 540
3 Dutch Shell 90 680
4 Houston Drilling 120 1,000
5 Texas Petroleum 110 700
6 San Diego Oil 40 510
7 California Petro 75 900
TABLE 10.4 Oil Investment Opportunities
10.4 Goal Programming In today’s business environment, profit maximization or cost minimization are not always the only objectives that a firm sets forth. Often, maximizing total profit is just one of several goals, including such contradictory objectives as maximizing market share, maintaining full employ- ment, providing quality ecological management, minimizing noise level in the neighborhood, and meeting numerous other noneconomic goals.
10.4 GOAL PROGRAMMING 407
PROGRAM 10.7 Excel 2010 Solver Solution for Financial Investment Problem
Set Objective: I5 By Changing cells: B4:H4 To: Max Subject to the Constraints:
I7 >= K7 I8 <= K8 I9 = K9 I10 <= K10 B4:H4 = binary
Solving Method: Simplex LP � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy I5 to I7:I10
Continental Airlines Saves $40 Million Using CrewSolver
Airlines use state-of-the-art processes and automated tools to develop schedules that maximize profit. These schedules will assign aircraft to specific routes, and then schedule pilots and flight attendant crews to each of these aircraft. When disruptions occur, planes and personnel are often left in positions where they are unable to adhere to the next day’s assignments. Airlines face schedule disruptions from a variety of unexpected reasons such as bad weather, mechanical problems, and crew unavailability.
In 1993, Continental Airlines began an effort to develop a system of dealing with disruptions in real time. Working with CALEB Technologies, Continental developed the CrewSolver and OptSolver systems (based on 0–1 integer programming models) to produce comprehensive recovery solutions for both aircraft and crews. These solutions retain revenue and promote customer sat- isfaction by reducing flight cancellations and minimizing delays. These crew recovery solutions are low cost while maintaining a high quality of life for pilots and flight attendants.
In late 2000 and throughout 2001, Continental and other air- lines experienced four major disruptions. The first two were due to severe snowstorms in early January and in March 2001. The Hous- ton floods caused by Tropical Storm Allison closed a major hub in June 2001 and left aircraft in locations where they were not sched- uled to be. The terrorist attacks of September 11, 2001 left aircraft and crews scattered about and totally disrupted the flight sched- ules. The CrewSolver system provided a faster and more efficient recovery than had been possible in the past. It is estimated that the CrewSolver system saved approximately $40 million for these ma- jor disruptions in 2001. This system also saved additional money and made recovery much easier when there were minor disruptions due to local weather problems at other times throughout the year.
Source: Based on Gang Yu, Michael Arguello, Gao Song, Sandra M. McCowan, and Anna White. “A New Era for Crew Recovery at Continental Airlines,” Interfaces 33, (January–February 2003): 5–22.
IN ACTION
The shortcoming of mathematical programming techniques such as linear and integer programming is that their objective function is measured in one dimension only. It’s not possible for LP to have multiple goals unless they are all measured in the same units (such as dollars), a highly unusual situation. An important technique that has been developed to supplement LP is called goal programming.
Goal programming permits multiple goals.
Goal programming is capable of handling decision problems involving multiple goals. A four-decade old concept, it began with the work of Charnes and Cooper in 1961 and was refined and extended by Lee and Ignizio in the 1970s and 1980s (see the Bibliography).
In typical decision-making situations, the goals set by management can be achieved only at the expense of other goals. It is necessary to establish a hierarchy of importance among these goals so that lower-priority goals are tackled only after higher-priority goals are satisfied. Since it is not always possible to achieve every goal to the extent the decision maker desires, goal pro- gramming attempts to reach a satisfactory level of multiple objectives. This, of course, differs from LP, which tries to find the best possible outcome for a single objective. Nobel laureate Herbert A. Simon, of Carnegie-Mellon University, states that modern managers may not be able to optimize, but may instead have to “satisfice” or “come as close as possible” to reaching goals. This is the case with models such as goal programming.
How, specifically, does goal programming differ from LP? The objective function is the main difference. Instead of trying to maximize or minimize the objective function directly, with goal programming we try to minimize deviations between set goals and what we can actually achieve within the given constraints. In the LP simplex approach, such deviations are called slack and surplus variables. Because the coefficient for each of these in the objective function is zero, slack and surplus variables do not have an impact on the optimal solution. In goal program- ming, the deviational variables are typically the only variables in the objective function, and the objective is to minimize the total of these deviational variables.
When the goal programming model is formulated, the computational algorithm is almost the same as a minimization problem solved by the simplex method.
Example of Goal Programming: Harrison Electric Company Revisited To illustrate the formulation of a goal programming problem, let’s look back at the Harrison Electric Company case presented earlier in this chapter as an integer programming problem. That problem’s LP formulation, you recall, is
where
We saw that if Harrison’s management had a single goal, say profit, LP could be used to find the optimal solution. But let’s assume that the firm is moving to a new location during a particular production period and feels that maximizing profit is not a realistic goal. Management sets a profit level, which would be satisfactory during the adjustment period, of $30. We now have a goal programming problem in which we want to find the production mix that achieves this goal as closely as possible, given the production time constraints. This simple case will pro- vide a good starting point for tackling more complicated goal programs.
We first define two deviational variables:
Now we can state the Harrison Electric problem as a single-goal programming model:
X1, X2, d1 -, d1
+ Ú 0
6X1 + 5X2 … 30 1assembly hours constraint2 2X1 + 3X2 … 12 1wiring hours constraint2 subject to $7X1 + $6X2 + d1 - - d1
+ = $30 1profit goal constraint2 Minimize under or overachievement of profit target = d1 - + d1
+
d1 + = overachievement of the profit target
d1 - = underachievement of the profit target
X2 = number of ceiling fans produced
X1 = number of chandeliers produced
X1, X2 Ú 0
6X1 + 5X2 … 30 1assembly hours2 subject to 2X1 + 3X2 … 12 1wiring hours2 Maximize profit = $7X1 + $6X2
408 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Goal programming “satisfices,” as opposed to LP, which tries to “optimize.” This means coming as close as possible to reaching goals.
The objective function is the main difference between goal programming and LP.
In goal programming we want to minimize deviational variables, which are the only terms in the objective function.
10.4 GOAL PROGRAMMING 409
Note that the first constraint states that the profit made, , plus any underachieve- ment of profit minus any overachievement of profit has to equal the target of $30. For example, if chandeliers and ceiling fans, then $33 profit has been made. This exceeds $30 by $3, so must be equal to 3. Since the profit goal constraint was overachieved, Harrison did not underachieve and will clearly be equal to zero. This problem is now ready for solution by a goal programming algorithm.
If the target profit of $30 is exactly achieved, we see that both and are equal to zero. The objective function will also be minimized at zero. If Harrison’s management was only con- cerned with underachievement of the target goal, how would the objective function change? It would be as follows: minimize underachievement . This is also a reasonable goal since the firm would probably not be upset with an overachievement of its target.
In general, once all goals and constraints are identified in a problem, management should analyze each goal to see if underachievement or overachievement of that goal is an acceptable situation. If overachievement is acceptable, the appropriate variable can be eliminated from the objective function. If underachievement is okay, the variable should be dropped. If man- agement seeks to attain a goal exactly, both and must appear in the objective function.
Extension to Equally Important Multiple Goals Let’s now look at the situation in which Harrison’s management wants to achieve several goals, each equal in priority.
Goal 1: to produce profit of $30 if possible during the production period
Goal 2: to fully utilize the available wiring department hours
Goal 3: to avoid overtime in the assembly department
Goal 4: to meet a contract requirement to produce at least seven ceiling fans
The deviational variables can be defined as follows:
Management is unconcerned about whether there is overachievement of the profit goal, over- time in the wiring department, idle time in the assembly department, or more than seven ceiling fans are produced: hence, , and may be omitted from the objective function. The new objective function and constraints are
Ranking Goals with Priority Levels In most goal programming problems, one goal will be more important than another, which in turn will be more important than a third. The idea is that goals can be ranked with respect to their importance in management’s eyes. Lower-order goals are considered only after higher-order goals are met. Priorities ( ) are assigned to each deviational variable—with the ranking that
is the most important goal, the next most important, then , and so on.P3P2P1
Pi ’s
All Xi, di variables Ú 0.
X2 + d4 - - d4
+ = 7 1ceiling fan constraint2 6X1 + 5X2 + d3 - - d3
+ = 30 1assembly constraint2 2X1 + 3X2 + d2 - - d2
+ = 12 1wiring hours constraint2 subject to 7X1 + 6X2 + d1 - - d1
+ = 30 1profit constraint2 Minimize total deviation = d1 - + d2
- + d3 + + d4
-
d4 +d1
+, d2 +, d3
-
d4 + = overachievement of the ceiling fan goal
d4 - = underachievement of the ceiling fan goal
d3 + = overtime in the assembly department 1overutilization2d3 - = idle time in the assembly department 1underutilization2d2 + = overtime in the wiring department 1overutilization2d2 - = idle time in the wiring department 1underutilization2d1 + = overachievement of the profit target
d1 - = underachievement of the profit target
d+d- d-
d+
= d1 -
d1 -d1
+
d1 -
d1 +
X2 = 2X1 = 3
$7X1 + $6X2
We need a clear definition of deviational variables, such as these.
Deviational variables are zero if a goal is completely obtained.
A key idea in goal programming is that one goal is more important than another. Priorities are assigned to each deviational variable.
Let’s say Harrison Electric sets the priorities shown in the following table:
410 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Priority 1 is infinitely more important than Priority 2, which is infinitely more important than the next goal, and so on.
GOAL PRIORITY
Reach a profit as much above $30 as possible P1
Fully use wiring department hours available P2
Avoid assembly department overtime P3
Produce at least seven ceiling fans P4
This means, in effect, that the priority of meeting the profit goal is infinitely more important than the wiring goal , which is, in turn, infinitely more important than the assem- bly goal , which is infinitely more important than producing at least seven ceiling fans .
With ranking of goals considered, the new objective function becomes
The constraints remain identical to the previous ones.
Goal Programming with Weighted Goals When priority levels are used in goal programming, any goal in the top priority level is infinitely more important than the goals in lower priority levels. However, there may be times when one goal is more important than another goal, but it may be only two or three times as important. Instead of placing these goals in different priority levels, they would be placed in the same pri- ority level but with different weights. When using weighted goal programming, the coefficients in the objective function for the deviational variables include both the priority level and the weight. If all goals are in the same priority level, then simply using the weights as objective function coefficients is sufficient.
Consider the Harrison Electric example, in which the least important goal is goal 4 (pro- duce at least seven ceiling fans). Suppose Harrison decides to add another goal of producing at least two chandeliers. The goal of seven ceiling fans is considered twice as important as this goal, so both of these should be in the same priority level. The goal of 2 chandeliers is assigned
Minimize total deviation = P1d1 - + P2d2
- + P3d3 + + P4d4
-
1P421P32 1P22 1P12
The Use of Goal Programming for Tuberculosis Drug Allocation in Manila
Allocation of resources is critical when applied to the health in- dustry. It is a matter of life and death when neither the right sup- ply nor the correct quantity is available to meet patient demand. This was the case faced by the Manila (Philippines) Health Center, whose drug supply to patients afflicted with Category I tubercu- losis (TB) was not being efficiently allocated to its 45 regional health centers. When the TB drug supply does not reach patients on time, the disease becomes worse and can result in death. Only 74% of TB patients were being cured in Manila, 11% short of the 85% target cure rate set by the government. Unlike other dis- eases, TB can only be treated with four medicines and cannot be cured by alternative drugs.
Researchers at the Mapka Institute of Technology set out to create a model, using goal programming, to optimize the allocation of resources for TB treatment while considering sup- ply constraints. The objective function of the model was to meet the target cure rate of 85% (which is the equivalent of
minimizing the underachievement in the allocation of anti-TB drugs to the 45 centers). Four goal constraints considered the interrelationships among variables in the distribution system. Goal 1 was to satisfy the medication requirement (a 6-month regimen) for each patient. Goal 2 was to supply each health center with the proper allocation. Goal 3 was to satisfy the cure rate of 85%. Goal 4 was to satisfy the drug requirements of each health center.
The goal programming model successfully dealt with all of these goals and raised the TB cure rate to 88%, a 13% improve- ment in drug allocation over the previous distribution approach. This means that 335 lives per year were saved through this thoughtful use of goal programming.
Source: Based on G. J. C. Esmeria. “An Application of Goal Programming in the Allocation of Anti-TB Drugs in Rural Health Centers in the Philippines,” Proceedings of the 12th Annual Conference of the Production and Operations Management Society (March 2001), Orlando, FL: 50.
IN ACTION
PROGRAM 10.8A Harrison Electric’s Goal Programming Analysis Using QM for Windows: Inputs
10.5 NONLINEAR PROGRAMMING 411
a weight of 1, while the 7 ceiling fan goal will be given a weight of 2. Both of these will be in priority level 4. A new constraint (goal) would be added:
The new objective function value would be
Note that the ceiling fan goal has a weight of 2. The weight for the chandelier goal is 1. Techni- cally all of the goals in the other priority levels are assigned weights of 1 also.
USING QM FOR WINDOWS TO SOLVE HARRISON’S PROBLEM QM for Windows goal program- ming module is illustrated in Programs 10.8A and 10.8B. The input screen is shown first, in Program 10.8A. Note in this first screen that there are two priority level columns for each con- straint. For this example, the priority for either the positive or the negative deviation will be zero since the objective function does not contain both types of deviational variables for any of these goals. If a problem had a goal with both deviational variables in the objective function, both pri- ority level columns for this goal (constraint) would contain values other than zero. Also, the weight for each deviational variable contained in the objective function is listed as 1. (It is 0 if the variable is not appearing in the objective function.) If different weights are used, they would be placed in the appropriate weight column within one priority level.
The solution with an analysis of deviations and goal achievement is shown in Program 10.8B. We see that the first two constraints have negative deviational variables equal to 0, indi- cating full achievement of those goals. In fact, the positive deviational variables both have val- ues of 6, indicating overachievement of these goals by 6 units each. Goal (constraint) 3 has both deviational variables equal to 0, indicating complete achievement of that goal, whereas goal 4 has a negative deviational variable equal to 1, indicating underachievement by 1 unit.
Minimize total deviation = P1d1 - + P2d2
- + P3d3 + + P412d4
-2 + P4d5 -
X1 + d5 - - d5
+ = 2 1chandeliers2
PROGRAM 10.8B Summary Solution Screen for Harrison Electric’s Goal Programming Problem Using QM for Windows
10.5 Nonlinear Programming Linear, integer, and goal programming all assume that a problem’s objective function and con- straints are linear. That means that they contain no nonlinear terms such as , or
. Yet in many mathematical programming problems, the objective function and/or one or more of the constraints are nonlinear.
Unlike with linear programming methods, computational procedures for solving many nonlinear programming (NLP) problems do not always yield the optimal solution. In many
5X1X2
X1 3, 1>X2, log X3
412 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
NLP problems, a particular solution may be better than any other point nearby, but it may not be the overall best point. This is called a local optimum, and the overall best solution is called the global optimum. Thus, for a particular problem, a solution technique may indicate that an optimum solution has been found, but it is only a local optimum, so there may be a global optimum that is better. The mathematics involved in solving these problems is beyond the scope of this text. We will rely on Solver in Excel to solve the nonlinear problems pre- sented in this section.
In this section, we examine three categories of NLP problems and illustrate how Excel can be used to search for the solution to these problems. In Solved Problem 10–3, we will see how NLP in Excel can help find the best parameter to use in an exponential smoothing fore- casting model.
Nonlinear Objective Function and Linear Constraints The Great Western Appliance Company sells two models of toaster ovens, the Microtoaster and the Self-Clean Toaster Oven . The firm earns a profit of $28 for each Microtoaster re- gardless of the number sold. Profits for the Self-Clean model, however, increase as more units are sold because of fixed overhead. Profit on this model may be expressed as .
Hence the firm’s objective function is nonlinear:
Great Western’s profit is subject to two linear constraints on production capacity and sales time available:
When an objective function contains squared terms (such as ) and the problem’s con- straints are linear, it is called a quadratic programming problem. A number of useful problems in the field of portfolio selection fall into this category. Quadratic programs can be solved by a modified method of the simplex method. Such work is outside the scope of this book but can be found in sources listed in the Bibliography.
The solution to the Great Western Appliance nonlinear programming problem is shown in Program 10.9. This was found using Solver in Excel 2010, and there are two important features of this spreadsheet that are different from the previous linear and integer programming examples.
0.25X2 2
X1, X2 Ú 0
0.5X1 + 0.4X2 … 500 1hours of sales time available2X1 + X2 … 1,000 1units of production capacity2 Maximize profit = 28X1 + 21X2 + 0.25X2
2
21X2 + 0.25X2 2
1X22 1X12
Quadratic programming contains squared terms in the objective function.
Goal Programming Model for Prison Expenditures in Virginia
Prisons across the United States are overcrowded, and there is need for immediate expansion of their capacity and replacement or renovation of obsolete facilities. This study demonstrates how goal programming was used on the capital allocation problem faced by the Department of Corrections of Virginia.
The expenditure items considered by the Virginia corrections department included new and renovated maximum, medium, and minimum security facilities; community diversion programs; and personnel increases. The goal programming technique forced all prison projects to be completely accepted or rejected.
Model variables defined the construction, renovation, or es- tablishment of a particular type of correctional facility for a spe- cific location or purpose and indicated the people required by the facilities. The goal constraints fell into five categories: addi- tional inmate capacity created by new and renovated correc- tional facilities; operating and personnel costs associated with
each expenditure item; the impact of facility construction and renovation on imprisonment, sentence length, and early releases and parole; the mix of different facility types required by the sys- tem; and the personnel requirements resulting from the various capital expenditures for correctional facilities.
The solution results for Virginia were one new maximum security facility for drug, alcohol, and psychiatric treatment activities; one new minimum security facility for youthful offenders; two new regular minimum security facilities; two new community diversion programs in urban areas, renovation of one existing medium security and one minimum security facility; 250 new correctional officers; four new administrators; 46 new treatment specialist/counselors; and six new medical personnel.
Source: Based on R. Russell, B. Taylor, and A. Keown. Computer Environ- mental Urban Systems 11, 4 (1986): 135–146.
IN ACTION
Here is an example of a nonlinear objective function
10.5 NONLINEAR PROGRAMMING 413
First, the solving method used for this in Solver is GRG Nonlinear instead of Simplex LP. The second change involves the objective function and the changing cells. For the sake of consistency, values for both (cell C4) and (cell D7) are shown in Program 10.9. However, cell D7 is simply cell C4 squared. Thus, when cell C4 changes, D7 will automatically change, and the Changing cells specified in Solver are B4:C4, while D7 is not included.
Both Nonlinear Objective Function and Nonlinear Constraints The annual profit at a medium-sized (200–400 beds) Hospicare Corporation–owned hospital depends on the number of medical patients admitted and the number of surgical patients admitted . The nonlinear objective function for Hospicare is
The corporation identifies three constraints, two of which are also nonlinear, that affect opera- tions. They are
8X1 - 2X2 … 61 1marketing budget required, in thousands of $2X1 + X2 3 … 75 1x–ray capacity, in thousands2 2X1
2 + 4X2 … 90 1nursing capcity, in thousands of labor–days2 $13X1 + $6X1X2 + $5X2 + $1>X2
1X22 1X12
X2 2X2
PROGRAM 10.9 Excel 2010 Solver Solution for Great Western Appliance NLP Problem
Set Objective: E8 By Changing cells: B4:C4 To: Max Subject to the Constraints:
E11:E12 <= G11:G12 Solving Method: GRG Nonlinear � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
An example in which the objective and constraints are both nonlinear.
An example of nonlinear constraints.
414 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Excel’s Solver is capable of formulating such a problem. The optimal solution is provided in Program 10.10.
Linear Objective Function with Nonlinear Constraints Thermlock Corp. produces massive rubber washers and gaskets like the type used to seal joints on the NASA Space Shuttles. To do so, it combines two ingredients: rubber and oil . The cost of the industrial-quality rubber used is $5 per pound and the cost of the high-viscosity oil is $7 per pound. Two of the three constraints Thermlock faces are nonlinear. The firm’s objective function and constraints are
To solve this nonlinear programming, we turn again to Excel. The output is provided in Program 10.11.
0.7X1 + X2 Ú 17 1elasticity2 13X1 + X1 3 Ú 80 1tensile strength2 subject to 3X1 + 0.25X1
2 + 4X2 + 0.3X2 2 Ú 125 1hardness contraint2 Minimize costs = $5X1 + $7X2
1X221X12
PROGRAM 10.10 Excel 2010 Solution for Hospicare NLP Problem
Set Objective: H8 By Changing cells: B4:C4 To: Max Subject to the Constraints:
H11:H13 <= J11:J13 Solving Method: GRG Nonlinear � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy H8 to H11:H13
GLOSSARY 415
Summary
This chapter addresses three special types of LP problems. The first, integer programming, examines LP problems that cannot have fractional answers. We also note that there are three types of integer programming problems: (1) pure or all-integer pro- grams, (2) mixed problems, in which some solution variables need not be integer, and (3) 0–1 problems, in which all solu- tions are either 0 or 1. We also demonstrate how 0–1 variables can be used to model special situations such as fixed charge problems. QM for Windows and Excel are used to illustrate computer approaches to these problems.
The latter part of the chapter deals with goal program- ming. This extension of LP allows problems to have multiple goals. Again, software such as QM for Windows is a powerful tool in solving this offshoot of LP. Finally, the advanced topic of NLP is introduced as a special mathematical programming problem. Excel is seen to be a useful tool in solving simple NLP models.
However, it is important to remember that the solution found for an NLP problem might be a local optimum and not a global optimum.
PROGRAM 10.11 Excel 2010 Solution for Thermlock NLP Problem
Set Objective: D5 By Changing cells: B4:C4 To: Min Subject to the Constraints:
G10:G12 >= I10:I12 Solving Method: GRG Nonlinear � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy G10 to G11:G12
Glossary
Deviational Variables Terms that are minimized in a goal programming problem. Like slack variables in LP, they are real. They are the only terms in the objective function.
Global Optimum The overall best solution to a nonlinear programming problem.
Goal Programming A mathematical programming technique that permits decision makers to set and prioritize multiple objectives.
Integer Programming A mathematical programming tech- nique that produces integer solutions to linear programming problems.
Local Optimum A solution to a nonliner programming problem which is better than any nearby point, but which may not be the global optimum.
Nonlinear Programming A category of mathematical pro- gramming techniques that allows the objective function and/or constraints to be nonlinear.
Satisficing The process of coming as close as possible to reaching your set of objectives.
0–1 Integer Programming Problems in which all decision variables must have integer values of 0 or 1. This is also called a binary variable
416 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
Solved Problems
Solved Problem 10-1 Consider the 0–1 integer programming problem that follows:
Now reformulate this problem with additional constraints so that no more than two of the three vari- ables can take on a value equal to 1 in the solution. Further, make sure that if , then also. Then solve the new problem using Excel.
Solution Excel can handle all-integer, mixed-integer, and 0–1 integer problems. Program 10.12 below shows two new constraints to handle the reformulated problem. These constraints are
and
The optimal solution is , with an objective function value of 95.X1 = 1, X2 = 1, X3 = 0
X1 - X2 … 0
X1 + X2 + X3 … 2
X2 = 1X1 = 1
X1, X2, X3 must be either 0 or 1
22X1 + 13X2 + 12X3 … 40
subject to 19X1 + 27X2 + 34X3 … 80
Maximize 50X1 + 45X2 + 48X3
PROGRAM 10.12 Excel 2010 Solution for Solved Problem 10-1
Set Objectives: E5 By Changing cells: B4:D4 To: Max Subject to the Constraints:
E8:E11 <= G8:G11 B4:D4 = binary
Solving Method: Simplex LP � Make Variables Non-Negative
Solver Parameter Inputs and Selections Key Formulas
Copy E5 to E8:E11
SOLVED PROBLEMS 417
Solved Problem 10-2 Recall the Harrison Electric Company goal programming problem seen in Section 10.4. Its LP formula- tion was
where
number of chandeliers produced
number of ceiling fans produced
Reformulate Harrison Electrical as a goal programming model with the following goals:
Priority 1: Produce at least 4 chandeliers and 3 ceiling fans.
Priority 2: Limit overtime in the assembly department to 10 hours and in the wiring department to 6 hours.
Priority 3: Maximize profit.
Solution
In the priority 3 goal constraint, the 99,999 represents an unrealistically high profit. It is just a mathe- matical trick to use as a target so that we can get as close as possible to the maximum profit.
Solved Problem 10-3 In Chapter 5, the exponential smoothing method for forecasting time series was presented. Program 10.13A provides an example of this, with the smoothing constant (α) selected to be 0.1. The fore- cast in time period 1 is assumed to be perfect, so the error and the absolute value of the error are both 0. The mean absolute deviation (MAD) is the measure of accuracy, and the first time period er- ror is not used in computing this since it was simply assumed to be perfect. The MAD is very de- pendent on the value of α. Use Excel to find the value of α that will minimize the MAD. Hint: Instead of writing the entire objective function, simply use the cell already developed in Excel for the MAD. Remember, α must be between 0 and 1.
Solution The MAD is a nonlinear function, so Solver in Excel can be used to solve this. There is only one con- straint: The smoothing constant, α, must be less than or equal to 1. This can be entered directly into the Add Constraint window in Solver, with a 1 entered on the right-hand side of the inequality. Program 10.13B provides the information and the final solution for this. The value for α that minimizes the MAD is 0.3478, and this yields an MAD of 16.70. Note: Solver can be used in a similar manner to find the best weights to use in a weighted moving aver- age forecast.
7X1 + 6X2 + d5 - - d5
+ = 99,999} Priority 3
2X1 + 3X2 + d3 - - d3
+ = 18
6X1 + 5X2 + d4 - - d4
+ = 40 f Priority 2
subject to X1 + d1
- - d1 + = 4
X2 + d2 - - d2
+ = 3 f Priority 1
Minimize P11d1 - + d2
-2 + P21d3 + + d4
+2 + P3d5 -
X2
X1
X1, X2 Ú 0
6X1 + 5X2 … 30 1assembly hours2 subject to 2X1 + 3X2 … 12 1wiring hours2 Maximize profit = $7X1 + $6X2
418 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
PROGRAM 10.13A Excel 2010 Spreadsheet for Solved Problem 10-3
PROGRAM 10.13B Excel 2010 Spreadsheet Solution for Solved Problem 10-3
Key Formulas
Copy C6:E6 to C7:E11
Set Objectives: E12 By Changing cells: B3 To: Min Subject to the Constraints:
B3 <= 1 Solving Method: GRG Nonlinear � Make Variables Non-Negative
Solver Parameter Inputs and Selections
DISCUSSION QUESTIONS AND PROBLEMS 419
Discussion Questions and Problems
Discussion Questions 10-1 Compare the similarities and differences of linear
and goal programming.
10-2 A linear programming problem was developed, and the feasible region was found. If the additional re- striction that all variables must be integers were added to the problem, how would the size of the fea- sible region change? How would the optimal value of the objective function change?
10-3 List the advantages and disadvantages of solving inte- ger programming problems by (a) rounding off and (b) enumeration.
10-4 What is the difference between the three types of integer programming problems? Which do you think is most common, and why?
10-5 What is meant by “satisficing,” and why is the term often used in conjunction with goal programming?
10-6 What are deviational variables? How do they differ from decision variables in traditional LP problems?
Self-Test
� Before taking the self-test, refer to the learning objectives at the beginning of the chapter, the notes in the margins, and the glossary at the end of the chapter.
� Use the key at the back of the book to correct your answers. � Restudy pages that correspond to any questions that you answered incorrectly or material you feel uncertain about.
7. Nobel Laureate Herbert A. Simon of Carnegie-Mellon University says that modern managers should always op- timize, not satisfice. a. True b. False
8. The fixed charge problem is typically classified as a. a goal programming problem. b. a 0–1 integer problem. c. a quadratic programming problem. d. an assignment problem.
9. The 0–1 integer programming problem a. requires the decision variables to have values between
0 and 1. b. requires that the constraints all have coefficients
between 0 and 1. c. requires that the decision variables have coefficients
between 0 and 1. d. requires the decision variables to be equal to 0 or 1.
10. Goal programming a. requires only that you know whether the goal is direct
profit maximization or cost minimization. b. allows you to have multiple goals. c. is an algorithm with the goal of a quicker solution to
the pure integer programming problem. d. is an algorithm with the goal of a quicker solution to
the mixed-integer programming problem. 11. Nonlinear programming includes problems
a. in which the objective function is linear but some constraints are not linear.
b. in which the constraints are linear but the objective function is not linear.
c. in which both the objective function and all of the con- straints are not linear.
d. solvable by quadratic programming. e. all of the above.
1. If all of the decision variables require integer solutions, the problem is a. a pure integer programming type of problem. b. a simplex method type of problem. c. a mixed-integer programming type of problem. d. a Gorsky type of problem.
2. In a mixed-integer programming problem a. some integers must be even and others must be odd. b. some decision variables must require integer results
only and some variables must allow for continuous results.
c. different objectives are mixed together even though they sometimes have relative priorities established.
3. A model containing a linear objective function and linear constraints but requiring that one or more of the decision variables take on an integer value in the final solution is called a. an integer programming problem. b. a goal programming problem. c. a nonlinear programming problem. d. a multiple objective LP problem.
4. An integer programming solution can never produce a greater profit than the LP solution to the same problem. a. True b. False
5. In goal programming, if all the goals are achieved, the value of the objective function will always be zero. a. True b. False
6. The objective in a goal programming problem with one priority level is to maximize the sum of the deviational variables. a. True b. False
420 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
10-7 If you were the president of the college you are attending and were employing goal programming to assist in decision making, what might your goals be? What kinds of constraints would you include in your model?
10-8 What does it mean to rank goals in goal program- ming? How does this affect the problem’s solution?
10-9 Which of the following are NLP problems, and why?
(a)
(b)
(c)
(d)
(e)
Are any of these quadratic programming problems?
Problems* 10-10 Elizabeth Bailey is the owner and general manager of
Princess Brides, which provides a wedding planning service in Southwest Louisiana. She uses radio adver- tising to market her business. Two types of ads are available—those during prime time hours and those at other times. Each prime time ad costs $390 and reaches 8,200 people, while the offpeak ads each cost $240 and reach 5,100 people. Bailey has budgeted $1,800 per week for advertising. Based on comments from her customers, Bailey wants to have at least 2 prime time ads and no more than 6 off peak ads. (a) Formulate this as a linear program. (b) Find a good or optimal integer solution part (a)
by rounding off or making an educated guess at the answer.
(c) Solve this as an integer programming problem using a computer.
X1 + X2 Ú 18
subject to 4X1 - 3X2 Ú 8
Minimize cost = 18X1 + 5X2 + X2 2
3X1 + 4X2 Ú 12
subject to X1 2 - 5X2 Ú 8
Maximize profit = 3X1 + 4X2
X1 + d3 - - d3
+ = 100
X2 + d2 - - d2
+ = 200
subject to X1 + X2 + d1 - - d1
+ = 300
Maximize Z = P1d1 - + P2d2
+ + P3 +
0.0005X1 - X2 = 11
X1 + X2 Ú 12
subject to X1 Ú 8
Maximize cost = 25X1 + 30X2 + 8X1X2
X3 Ú 18
X2 … 5
subject to X1 Ú 10
Maximize profit = 3X1 + 5X2 + 99X3
10-11 A group of college students is planning a camping trip during the upcoming break. The group must hike several miles through the woods to get to the campsite, and anything that is needed on this trip must be packed in a knapsack and carried to the campsite. One particular student, Tina Shawl, has identified eight items that she would like to take on the trip, but the combined weight is too great to take all of them. She has decided to rate the utility of each item on a scale of 1 to 100, with 100 being the most beneficial. The item weights in pounds and their utility values are given below.
ITEM 1 2 3 4 5 6 7 8
WEIGHT 8 1 7 6 3 12 5 14
UTILITY 80 20 50 55 50 75 30 70
Recognizing that the hike to the campsite is a long one, a limit of 35 pounds has been set as the maxi- mum total weight of the items to be carried. (a) Formulate this as a 0–1 programming problem to
maximize the total utility of the items carried. Solve this knapsack problem using a computer.
(b) Suppose item number 3 is an extra battery pack, which may be used with several of the other items. Tina has decided that she will only take item number 5, a CD player, if she also takes item number 3. On the other hand, if she takes item number 3, she may or may not take item number 5. Modify this problem to reflect this and solve the new problem.
10-12 Student Enterprises sells two sizes of wall posters, a large 3- by 4-foot poster and a smaller 2- by 3-foot poster. The profit earned from the sale of each large poster is $3; each smaller poster earns $2. The firm, although profitable, is not large; it consists of one art student, Jan Meising, at the University of Kentucky. Because of her classroom schedule, Jan has the fol- lowing weekly constraints: (1) up to three large posters can be sold, (2) up to five smaller posters can be sold, (3) up to 10 hours can be spent on posters during the week, with each large poster requiring 2 hours of work and each small one taking 1 hour. With the semester almost over, Jan plans on taking a three-month summer vacation to England and doesn’t want to leave any unfinished posters behind. Find the integer solution that will maximize her profit.
10-13 An airline owns an aging fleet of Boeing 737 jet air- planes. It is considering a major purchase of up to 17 new Boeing model 757 and 767 jets. The decision must take into account numerous cost and capability factors, including the following: (1) the airline can
Note: means the problem may be solved with QM for Windows; means the problem may be
solved with Excel; and means the problem may be solved with QM for Windows and/or Excel.
DISCUSSION QUESTIONS AND PROBLEMS 421
finance up to $1.6 billion in purchases; (2) each Boeing 757 will cost $80 million, and each Boeing 767 will cost $110 million; (3) at least one-third of the planes purchased should be the longer-range 757; (4) the annual maintenance budget is to be no more than $8 million; (5) the annual maintenance cost per 757 is estimated to be $800,000, and it is $500,000 for each 767 purchased; and (6) each 757 can carry 125,000 passengers per year, whereas each 767 can fly 81,000 passengers annually. Formulate this as an integer programming problem to maxi- mize the annual passenger-carrying capability. What category of integer programming problem is this? Solve this problem.
10-14 Trapeze Investments is a venture capital firm that is currently evaluating six different investment oppor- tunities. There is not sufficient capital to invest in all of these, but more than one will be selected. A 0–1 integer programming model is planned to help determine which of the six opportunities to choose. Variables represent the six choices. For each of the following situations, write a constraint (or several constraints) that would be used. (a) At least 3 of these choices are to be selected. (b) Either investment 1 or investment 4 must be
undertaken, but not both. (c) If investment 4 is selected, then investment
6 must also be selected. However, if investment 4 is not selected, it is still possible to select num- ber 6.
(d) Investment 5 cannot be selected unless both in- vestments 2 and 3 are also selected.
(e) Investment 5 must be selected if both invest- ments 2 and 3 are also selected.
10-15 Horizon Wireless, a cellular telephone company, is expanding into a new era. Relay towers are neces- sary to provide wireless telephone coverage to the different areas of the city. A grid is superimposed on a map of the city to help determine where the towers should be located. The grid consists of 8 areas labeled A through H. Six possible tower locations (numbered 1–6) have been identified, and each loca- tion could serve several areas. The table below indi- cates the areas served by each of the towers.
X1, X2, X3, X4, X5, and X6
Innis has identified eight potential locations to con- struct new single-family dwellings, but he cannot put up homes on all of the sites because he has only $300,000 to invest in all projects. The accompany- ing table shows the cost of constructing homes in each area and the expected profit to be made from the sale of each home. Note that the home-building costs differ considerably due to lot costs, site prepa- ration, and differences in the models to be built. Note also that a fraction of a home cannot be built.
TOWER LOCATION 1 2 3 4 5 6
AREAS SERVED A, B, D B, C, G C, D, E, F E, F, H E, G, H A, D, F
Formulate this as a 0–1 programming model to min- imize the total number of towers required to cover all the areas. Solve this using a computer.
10-16 Innis Construction Company specializes in building moderately priced homes in Cincinnati, Ohio. Tom
COST OF BUILDING EXPECTED PROFIT LOCATION AT THIS SITE ($) ($)
Clifton 60,000 5,000
Mt. Auburn 50,000 6,000
Mt. Adams 82,000 10,000
Amberly 103,000 12,000
Norwood 50,000 8,000
Covington 41,000 3,000
Roselawn 80,000 9,000
Eden Park 69,000 10,000
(a) Formulate Innis’s problem using 0–1 integer programming.
(b) Solve with QM for Windows or Excel.
10-17 A real estate developer is considering three possible projects: a small apartment complex, a small shop- ping center, and a mini-warehouse. Each of these re- quires different funding over the next two years, and the net present value of the investments also varies. The following table provides the required invest- ment amounts (in $1,000s) and the net present value (NPV) of each (also expressed in $1,000s):
INVESTMENT
NPV YEAR 1 YEAR 2
Apartment 18 40 30
Shopping center 15 30 20
Mini-warehouse 14 20 20
The company has $80,000 to invest in year 1 and $50,000 to invest in year 2. (a) Develop an integer programming model to max-
imize the NPV in this situation. (b) Solve the problem in part (a) using computer
software. Which of the three projects would be undertaken if NPV is maximized? How much money would be used each year?
10-18 Refer to the real estate investment situation in Prob- lem 10-17. (a) Suppose that the shopping center and the apart-
ment would be on adjacent properties, and the
422 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
shopping center would only be considered if the apartment were also built. Formulate the con- straint that would stipulate this.
(b) Formulate a constraint that would force exactly two of the three projects to be undertaken.
10-19 Triangle Utilities provides electricity for three cities. The company has four electric generators that are used to provide electricity. The main generator oper- ates 24 hours per day, with an occasional shutdown for routine maintenance. Three other generators (1, 2, and 3) are available to provide additional power when needed. A startup cost is incurred each time one of these generators is started. The startup costs are $6,000 for 1, $5,000 for 2, and $4,000 for 3. These generators are used in the following ways: A generator may be started at 6:00 A.M. and run for either 8 hours or 16 hours, or it may be started at 2:00 P.M. and run for 8 hours (until 10:00 P.M.). All generators except the main generator are shut down at 10:00 P.M. Forecasts indicate the need for 3,200 megawatts more than provided by the main genera- tor before 2:00 P.M., and this need goes up to 5,700 megawatts between 2:00 and 10:00 P.M. Generator 1 may provide up to 2,400 megawatts, generator 2 may provide up to 2,100 megawatts, and generator 3 may provide up to 3,300 megawatts. The cost per megawatt used per eight hour period is $8 for 1, $9 for 2, and $7 for 3. (a) Formulate this problem as an integer program-
ming problem to determine the least-cost way to meet the needs of the area.
(b) Solve using computer software.
10-20 The campaign manager for a politician who is run- ning for reelection to a political office is planning the campaign. Four ways to advertise have been se- lected: TV ads, radio ads, billboards, and newspaper ads. The cost of these are $900 for each TV ad, $500 for each radio ad, $600 for a billboard for one month, and $180 for each newspaper ad. The audi- ence reached by each type of advertising has been estimated to be 40,000 for each TV ad, 32,000 for each radio ad, 34,000 for each billboard, and 17,000 for each newspaper ad. The total monthly advertis- ing budget is $16,000. The following goals have been established and ranked:
1. The number of people reached should be at least 1,500,000.
2. The total monthly advertising budget should not be exceeded.
3. Together, the number of ads on either TV or radio should be at least 6.
4. No more than 10 ads of any one type of ad- vertising should be used.
(a) Formulate this as a goal programming problem. (b) Solve this using computer software. (c) Which goals are completely met and which of
them are not?
10-21 Geraldine Shawhan is president of Shawhan File Works, a firm that manufactures two types of metal file cabinets. The demand for her two-drawer model is up to 600 cabinets per week; demand for a three- drawer cabinet is limited to 400 per week. Shawhan File Works has a weekly operating capacity of 1,300 hours, with the two-drawer cabinet taking 1 hour to produce and the three-drawer cabinet requiring 2 hours. Each two-drawer model sold yields a $10 profit, and the profit for the large model is $15. Shawhan has listed the following goals in order of importance:
1. Attain a profit as close to $11,000 as possi- ble each week.
2. Avoid underutilization of the firm’s produc- tion capacity.
3. Sell as many two- and three-drawer cabinets as the demand indicates.
Set this up as a goal programming problem.
10-22 Solve Problem 10-21. Are any goals unachieved in this solution? Explain.
10-23 Hilliard Electronics produces specially coded com- puter chips for laser surgery in 64MB, 256MB, and 512MB sizes. (1MB means that the chip holds 1 mil- lion bytes of information.) To produce a 64MB chip requires 8 hours of labor, a 256MB chip takes 13 hours, and a 512MB chip requires 16 hours. Hilliard’s monthly production capacity is 1,200 hours. Mr. Blank, the firm’s sales manager, esti- mates that the maximum monthly sales of the 64MB, 256MB, and 512MB chips are 40, 50, and 60, respectively. The company has the following goals (ranked in order from most important to least important):
1. Fill an order from the best customer for thirty 64MB chips and thirty-five 256MB chips.
2. Provide sufficient chips to at least equal the sales estimates set by Mr. Blank.
3. Avoid underutilization of the production capacity.
Formulate this problem using goal programming.
10-24 An Oklahoma manufacturer makes two products: speaker telephones and pushbutton telephones
. The following goal programming model has been formulated to find the number of each to pro- duce each day to meet the firm’s goals:
Find the optimal solution using a computer.
10-25 Major Bill Bligh, director of the Army War Col- lege’s new 6-month attaché training program, is
all Xi, di Ú 0
8X1 + 6X2 + d3 - - d3
+ = 240
8X1 + 10X2 + d2 - - d2
+ = 320
subject to 2X1 + 4X2 + d1 - - d1
+ = 80
Minimize P1d1 - + P2d2
- + P3d3 + + P4d1
+
1X22 1X12
DISCUSSION QUESTIONS AND PROBLEMS 423
concerned about how the 20 officers taking the course spend their precious time while in his charge. Major Bligh recognizes that there are 168 hours per week and thinks that his students have been using them rather inefficiently. Bligh lets
He thinks that students should study 30 hours a week to have time to absorb material. This is his most im- portant goal. Bligh feels that students need at most 7 hours sleep per night on average and that this goal is number 2. He believes that goal number 3 is to pro- vide at least 20 hours per week of social time. (a) Formulate this as a goal programming problem. (b) Solve the problem using computer software.
10-26 Mick Garcia, a certified financial planner (CFP) has been asked by a client to invest $250,000. This money may be placed in stocks, bonds, or a mutual fund in real estate. The expected return on investment is 13% for stocks, 8% for bonds, and 10% for real estate. While the client would like a very high expected re- turn, she would be satisfied with a 10% expected re- turn on her money. Due to risk considerations, several goals have been established to keep the risk at an ac- ceptable level. One goal is to put at least 30% of the money in bonds. Another goal is that the amount of money in real estate should not exceed 50% of the money invested in stocks and bonds combined. In ad- dition to these goals, there is one absolute restriction. Under no circumstances should more than $150,000 be invested in any one area. (a) Formulate this as a goal programming problem.
Assume that all of the goals are equally important. (b) Use any available software to solve this problem.
How much money should be put in each of the investment options? What is the total return? Which of the goals are not met?
10-27 Hinkel Rotary Engine, Ltd., produces four- and six- cylinder models of automobile engines. The firm’s profit for each four-cylinder engine sold during its quarterly production cycle is , where is the number sold. Hinkel makes
for each of the larger engines sold, with equal to the number of six-cylinder engines sold. There are 5,000 hours of production time avail- able during each production cycle. A four-cylinder engine requires 100 hours of production time, whereas six-cylinder engines take 130 hours to man- ufacture. Formulate this production planning prob- lem for Hinkel.
10-28 Motorcross of Wisconsin produces two models of snowmobiles, the XJ6 and the XJ8. In any given
X2
$2,400 - $70X2
X1
$1,800 - $50X1
1dating, sports, family visits, and so on2X4 = number of hours of social time off base
X3 = number of hours of class and studying
hygiene, handling laundary, and so on2X2 = number of personal hours 1eating, personal
X1 = number of hours of sleep needed per week
production-planning week Motorcross has 40 hours available in its final testing bay. Each XJ6 requires 1 hour to test and each XJ8 takes 2 hours. The revenue (in $1,000s) for the firm is nonlinear and is stated as (Number of XJ6s)(4 � 0.1 number of XJ6s) + (Number of XJ8s)(5 � 0.2 number of XJ8s). (a) Formulate this problem. (b) Solve using Excel.
10-29 During the busiest season of the year, Green-Gro Fertilizer produces two types of fertilizers. The stan- dard type (X) is just fertilizer, and the other type (Y) is a special fertilizer and weed-killer combination. The following model has been developed to deter- mine how much of each type should be produced to maximize profit subject to a labor constraint:
Find the optimal solution to this problem.
10-30 Pat McCormack, a financial advisor for Investors R Us, is evaluating two stocks in a particular industry. He wants to minimize the variance of a portfolio consisting of these two stocks, but he wants to have an expected return of at least 9%. After obtaining historical data on the variance and returns, he devel- ops the following nonlinear program:
where
Solve this using Excel and determine how much to in- vest in each of the two stocks. What is the return for this portfolio? What is the variance of this portfolio?
10-31 Summertime Tees sells two very popular styles of embroidered shirts in southern Florida: a tank top and a regular T-shirt. The cost of the tank top is $6, and the cost of the T-shirt is $8. The demand for these is sensitive to the price, and historical data in- dicate that the weekly demands are given by
where
P2 = price for regular T-shirt
X1 = demand for regular T-shirt
P1 = price for tank top
X1 = demand for tank top
X2 = 400 - 15P2
X1 = 500 - 12P1
Y = proportion of money invested in stock 2
X = proportion of money invested in stock 1
X, Y Ú 0
investment2 0.11X + 0.08Y Ú 0.09 1return on the
be invested2 subject to X + Y = 1 1all funds must
Minimize portfolio variance = 0.16X2 + 0.2XY + 0.09Y2
X, Y Ú 0
subject to 2X + 4Y … 160 hours
Maximize profit = 12X - 0.04X2 + 15Y - 0.06Y2
424 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
(a) Develop an equation for the total profit. (b) Use Excel to find the optimal solution to the fol-
lowing nonlinear program. Use the profit func- tion developed in part (a).
10-32 The integer programming problem in the box below has been developed to help First National Bank decide where, out of 10 possible sites, to locate four new branch offices:
where Xi represents Winter Park, Maitland, Osceola, Downtown, South Orlando, Airport, Winter Garden, Apopka, Lake Mary, Cocoa Beach, for i equals 1 to 10, respectively. (a) Where should the four new sites be located, and
what will be the expected return? (b) If at least one new branch must be opened in Mait-
land or Osceola, will this change the answers? Add the new constraint and rerun.
X1, P1, X2, P2 Ú 0
P2 … 25
P1 … 20
X2 = 400 - 15P2
subject to X1 = 500 - 12P1
Maximize profit
(c) The expected return at Apopka was overesti- mated. The correct value is $160,000 per year (that is, 160). Using the original assumptions (namely, ignoring (b)), does your answer to part (a) change?
10-33 In Solved Problem 10-3, nonlinear programming was used to find the best value for the smoothing constant, �, in an exponential smoothing forecasting problem. To see how much the MAD can vary due to the selection of the smoothing constant, use Excel and the data in Program 10.13A to find the value of the smoothing constant that would maximize the MAD. Compare this MAD to the minimum MAD found in the solved problem.
10-34 Using the data in Solved Problem 10-3, develop a spreadsheet for a 2-period weighted moving average forecast with weights of 0.6 (w1) for the most recent period and 0.4 (w2) for the other period. Note these weights sum to 1, so the forecast is simply
Find the weights for this 2-period weighted moving average that would minimize the MAD. (Hint: The weights must sum to 1.)
current period2 + w21Value in last period2 Forecast for next period = w11Value in
IP for Problem 10-32
subject to
= 120X1 + 100X2 + 110X3 + 140X4 + 155X5 + 128X6 + 145X7 + 190X8 + 170X9 + 150X10Maximize expected returns
all Xi = 0 or 1
X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 + X10 … 4
X1 + X3 + X10 Ú 1
X2 + X3 + X5 + X8 + X9 Ú 2
X2 + X6 + X7 + X9 + X10 … 3
15X1 + 5X2 + 20X3 + 20X4 + 5X5 + 5X6 + 10X7 + 20X8 + 5X9 + 20X10 … 50
20X1 + 30X2 + 20X3 + 25X4 + 30X5 + 30X6 + 25X7 + 20X8 + 25X9 + 30X10 … 110
See our Internet home page, at www.pearsonhighered.com/render, for additional home- work problems 10-35 to 10-40.
INTERNET HOMEWORK PROBLEMS
CASE STUDY 425
Case Study
Schank Marketing Research
Schank Marketing Research has just signed contracts to con- duct studies for four clients. At present, three project managers are free for assignment to the tasks. Although all are capable of handling each assignment, the times and costs to complete the studies depend on the experience and knowledge of each man- ager. Using his judgment, John Schank, the president, has been able to establish a cost for each possible assignment. These costs, which are really the salaries each manager would draw on each task, are summarized in the following table.
Schank is very hesitant about neglecting NASA, which has been an important customer in the past. (NASA has employed the firm to study the public’s attitude toward the Space Shuttle and proposed Space Station.) In addition, Schank has promised to try to provide Ruth a salary of at least $3,000 on his next as- signment. From previous contracts, Schank also knows that Gardener does not get along well with the management at CBT Television, so he hopes to avoid assigning her to CBT. Finally, as Hines Corporation is also an old and valued client, Schank
feels that it is twice as important to assign a project manager im- mediately to Hines’s task as it is to provide one to General Foundry, a brand-new client. Schank wants to minimize the to- tal costs of all projects while considering each of these goals. He feels that all of these goals are important, but if he had to rank them, he would put his concern about NASA first, his worry about Gardener second, his need to keep Hines Corpora- tion happy third, his promise to Ruth fourth, and his concern about minimizing all costs last.
Each project manager can handle, at most, one new client.
Discussion Questions 1. If Schank were not concerned about noncost goals, how
would he formulate this problem so that it could be solved quantitatively?
2. Develop a formulation that will incorporate all five objectives.
CLIENT
PROJECT MANAGER HINES CORP. NASA GENERAL FOUNDRY CBT TELEVISION
Gardener $3,200 $3,000 $2,800 $2,900
Ruth 2,700 3,200 3,000 3,100
Hardgraves 1,900 2,100 3,300 2,100
Case Study
Oakton River Bridge
The Oakton River had long been considered an impediment to the development of a certain medium-sized metropolitan area in the southeast. Lying to the east of the city, the river made it difficult for people living on its eastern bank to com- mute to jobs in and around the city and to take advantage of the shopping and cultural attractions that the city had to offer. Similarly, the river inhibited those on its western bank from access to the ocean resorts lying one hour to the east. The bridge over the Oakton River had been built prior to World War II and was grossly inadequate to handle the existing traf- fic, much less the increased traffic that would accompany the forecasted growth in the area. A congressional delegation
from the state prevailed upon the federal government to fund a major portion of a new toll bridge over the Oakton River and the state legislature appropriated the rest of the needed monies for the project.
Progress in construction of the bridge has been in accor- dance with what was anticipated at the start of construction. The state highway commission, which will have operational jurisdiction over the bridge, has concluded that the opening of the bridge for traffic is likely to take place at the beginning of the next summer, as scheduled. A personnel task force has been established to recruit, train, and schedule the workers needed to operate the toll facility.
426 CHAPTER 10 • INTEGER PROGRAMMING, GOAL PROGRAMMING, AND NONLINEAR PROGRAMMING
The personnel task force is well aware of the budgetary problems facing the state. They have taken as part of their man- date the requirement that personnel costs be kept as low as pos- sible. One particular area of concern is the number of toll collectors that will be needed. The bridge is scheduling three shifts of collectors: shift A from midnight to 8 A.M., shift B from 8 A.M. to 4 P.M., and shift C from 4 P.M. to midnight. Recently, the state employees union negotiated a contract with the state which requires that all toll collectors be permanent, full-time employees. In addition, all collectors must work a five-on, two-off schedule on the same shift. Thus, for example, a worker could be assigned to work Tuesday, Wednesday, Thursday, Friday, and Saturday on shift A, followed by Sunday and Monday off. An employee could not be scheduled to work, say, Tuesday on shift A followed by Wednesday, Thursday, Fri- day, and Saturday on shift B or on any other mixture of shifts during a 5-day block. The employees would choose their as- signments in order of their seniority.
The task force has received projections of traffic flow on the bridge by day and hour. These projections are based on ex- trapolations of existing traffic patterns—the pattern of commut- ing, shopping, and beach traffic currently experienced with growth projections factored in. Standards data from other state- operated toll facilities have allowed the task force to convert these traffic flows into toll collector requirements, that is, the minimum number of collectors required per shift, per day, to handle the anticipated traffic load. These toll collector require- ments are summarized in the following table:
The numbers in the table include one or two extra collec- tors per shift to fill in for collectors who call in sick and to pro- vide relief for collectors on their scheduled breaks. Note that each of the eight collectors needed for shift A on Sunday, for example, could have come from any of the A shifts scheduled to begin on Wednesday, Thursday, Friday, Saturday, or Sunday.
Discussion Questions 1. Determine the minimum number of toll collectors that
would have to be hired to meet the requirements ex- pressed in the table.
2. The union had indicated that it might lift its opposition to the mixing of shifts in a 5-day block in exchange for addi- tional compensation and benefits. By how much could the number of toll collectors required be reduced if this is done?
Source: Based on B. Render, R. M. Stair, and I. Greenberg. Cases and Readings in Management Science, 2nd ed., 1990, pp. 55–56. Reprinted by permission of Pren- tice Hall, Upper Saddle River, NJ.
SHIFT SUN. MON. TUE. WED. THU. FRI. SAT.
A 8 13 12 12 13 13 15
B 10 10 10 10 10 13 15
C 15 13 13 12 12 13 8
Minimum Number of Toll Collectors Required per Shift
Bibliography Aköz, Onur, and Dobrila Petrovic. “A Fuzzy Goal Programming Method with
Imprecise Goal Hierarchy,” European Journal of Operational Research 181, 3 (September 2007): 1427–1433.
Araz, Ceyhun, Pinar Mizrak Ozfirat, and Irem Ozkarahan. “An Integrated Multicriteria Decision-Making Methodology for Outsourcing Manage- ment,” Computers & Operations Research 34, 12 (December 2007): 3738–3756.
Bertsimas, Dimitris, Christopher Darnell, and Robert Soucy. “Portfolio Con- struction through Mixed-Integer Programming at Grantham, Mayo, Van Otterloo and Company,” Interfaces 29, 1 (January 1999): 49–66.
Chang, Ching-Ter. “Multi-Choice Goal Programming,” Omega 25, 4 (August 2007): 389–396.
Charnes, A., and W. W. Cooper. Management Models and Industrial Applica- tions of Linear Programming, Vols. I and II. New York: John Wiley & Sons, Inc.1961.
Dawid, Herbert, Johannes Konig, and Christine Strauss. “An Enhanced Ros- tering Model for Airline Crews,” Computers and Operations Research 28, 7 (June 2001): 671–688.
Drees, Lawrence David, and Wilbert E. Wilhelm. “Scheduling Experiments on a Nuclear Reactor Using Mixed Integer Programming,” Computers and Operations Research 28, 10 (September 2001): 1013–1037.
Hueter, Jackie, and William Swart. “An Integrated Labor-Management System for Taco Bell,” Interfaces 28, 1 (January–February 1998): 75–91.
Ignizio, James P. Introduction to Linear Goal Programming. Beverly Hills: Sage Publications, 1985.
Katok, Elena, and Dennis Ott. “Using Mixed-Integer Programming to Reduce Label Changes in the Coors Aluminum Can Plant,” Interfaces 30, 2 (March 2000): 1–12.
Land, Alisa, and Susan Powell. “A Survey of the Operational Use of ILP Models,” Annals of Operations Research 149, 1 (2007): 147–156.
Lee, Sang M., and Marc J. Schniederjans. “A Multicriterial Assignment Prob- lem: A Goal Programming Approach, ”Interfaces 13, 4 (August 1983): 75–79.
BIBLIOGRAPHY 427
Pati, Rupesh Kumar, Prem Vrat, and Pradeep Kumar. “A Goal Programming Model for a Paper Recycling System,” Omega 36, 3 (June 2008): 405–417.
Reyes, Pedro M., and Gregory V. Frazier. “Goal Programming Model for Gro- cery Shelf Space Allocation,” European Journal of Operational Research 181, 2 (September 2007): 634–644.
Wadhwa, Vijay, and A. Ravi Ravindran. “Vendor Selection in Outsourcing,” Computers & Operations Research 34, 12 (December 2007): 3725–3737.
Zangwill, W. I. Nonlinear Programming: A Unified Approach. Upper Saddle River, NJ: Prentice Hall, 1969.
This page intentionally left blank
- CHAPTER 10 Integer Programming, Goal Programming, and Nonlinear Programming
- 10.1 Introduction
- 10.2 Integer Programming
- Harrison Electric Company Example of Integer Programming
- Using Software to Solve the Harrison Integer Programming Problem
- Mixed-Integer Programming Problem Example
- 10.3 Modeling with 0–1 (Binary) Variables
- Capital Budgeting Example
- Limiting the Number of Alternatives Selected
- Dependent Selections
- Fixed-Charge Problem Example
- Financial Investment Example
- 10.4 Goal Programming
- Example of Goal Programming: Harrison Electric Company Revisited
- Extension to Equally Important Multiple Goals
- Ranking Goals with Priority Levels
- Goal Programming with Weighted Goals
- 10.5 Nonlinear Programming
- Nonlinear Objective Function and Linear Constraints
- Both Nonlinear Objective Function and Nonlinear Constraints
- Linear Objective Function with Nonlinear Constraints
- Summary
- Glossary
- Solved Problems
- Self-Test
- Discussion Questions and Problems
- Case Study: Schank Marketing Research
- Case Study: Oakton River Bridge
- Bibliography