CHAPTER 10
Integer Programming, Goal Programming, and
Nonlinear Programming
TEACHING SUGGESTIONS
Teaching Suggestion 10.1: Topics in This Chapter.
The overall purpose of this chapter is to provide a framework for the topics of integer program-
Teaching Suggestion 10.2: Using the Computer to Solve Mixed-Integer Programming Problems.
Note that the Excel printout in Program 10.2 allows users to specify which variables are integers
and which, by default, can be fractional.
Teaching Suggestion 10.3: Multiple Goals.
Ask students what other goals a company might have beyond maximizing profit. Socially con-
Teaching Suggestion 10.4: Deviational Variables Are the Key in Goal Programming.
The concept of deviational variables requires careful explanation to the class. Students are accus-
Teaching Suggestion 10.5: Difficulty of Graphical Goal Programming.
Solving goal programming problems graphically can be a confusing concept relative to graphical
LP. Students often have difficulty with the direction of deviational variables.
ALTERNATIVE EXAMPLES
Alternative Example 10.1: 0–1 Integer Programming.
Indiana’s prison budget allows it to consider four new installations next year. They are
X1 = 1 if maximum security prison in Ft. Wayne,
= 0 otherwise
X2 = 1 if minimum security prison in Bloomington,
= 0 otherwise
SOLUTIONS TO DISCUSSION QUESTIONS AND PROBLEMS
10-1. a. Linear programming allows only one goal (for example, profit maximization)
whereas goal programming permits multiple goals.
10-2. When integer constraints are added to an LP formulation, the size of the feasible region is
reduced dramatically. That is to say, instead of an infinite number of feasible solutions, the addi-
10-3. a. Rounding off is the easiest way to solve an integer program, but it can give an in-
10-4. The three types of integer programs are (1) pure integer programming, where all variables
10-6. Deviational variables, similar to slack variables in LP, are the difference between set goals
10-7. A college president’s goals might be to (1) increase enrollments by 1,000 students; (2) stay
10-8. Ranking goals just means more weight can be placed on one goal over another. The high-
er-ranked goals must be achieved completely before goal programming moves on to meet lower-
ranked goals.
10-9. a. Linear
b. Nonlinear because of 8X1X2 in objective
10-10. a. Let X = number of prime time ads per week
Y = number of off-peak ads per week
Maximize audience exposure = 8200X + 5100Y
Subject to:
390X + 240Y 1800
X 2
10-11. a. Let Xi = 1 if item i is selected and 0 otherwise, for i = 1 to 8.
Maximize 80X1 + 20X2 + 50X3 + 55X4 + 50X5 + 75X6 + 30X7 + 70X8
Subject to: 8X1 + X2 + 7X3 + 6X4 + 3X5 + 12X6 + 5X7 + 14X8 35
Xi = 0, 1
Solution using QM for Windows Integer and Mixed Integer Programming Module:
Objective function = 285
10-12. X1 = number of larger posters
X2 = number of smaller posters
See graph below.
Step 1. Optimal LP solution at a is (X1 = 21/2, X2 = 5, profit = $17.50). Step 2. Integer solution at
10-13. X1 = number of Boeing 757s purchased
X2 = number of Boeing 767s purchased
Maximize passenger carrying capability = 125,000X1 + 81,000X2
subject to
This is a pure integer programming problem.
The QM for Windows integer programming solution is:
X1 = 5
X2 = 8
10-15. Let Xi = 1 if location i is selected and 0 otherwise, for i = 1 to 6.
Minimize X1 + X2 + X3 + X4 + X5 + X6
Subject to:
X1 + X6 1
X3 + X4 + X6 1
X2 + X5 1
X4 + X5 1
10-16.
a.
1 if location is selected
Let: 0 if location is not selected
i
i
Xi
=
10-17. a. Let X1 = 1 if apartment project is undertaken; 0 otherwise
Let X2 = 1 if shopping center project is undertaken; 0 otherwise
Let X3 = 1 if mini-warehouse project is undertaken; 0 otherwise
10-18. a. X1 X2 This means that if the apartment is not built (X1 = 0), the shopping center can-
not be built (X2 must equal 0).
b. X1 + X2 + X3 = 2
10-19. a. Let Xij = 1 if generator i is functioning during time period j, and 0 otherwise; where i =
1, 2, 3 and j = 1 for 6–2 time period; j = 2 for 2–10 time period; j = 3 for 6–10 time period.
Let Yij = megawatts produced by generator i in time period j, where i = 1, 2, 3 and j = 1 for 6–2
time period; j = 2 for 2–10 time period.
Y11 2,400(X11 + X13) maximum megawatts from #1 from 6–2
Y12 2,400(X12 + X13) maximum megawatts from #1 from 2–10
Y21 2,100(X21 + X23) maximum megawatts from #2 from 6–2
Y22 2,100(X22 + X23) maximum megawatts from #2 from 2–10
Y31 3,300(X31 + X33) maximum megawatts from #3 from 6–2
Y32 3,300(X32 + X33) maximum megawatts from #3 from 2–10
b. The solution is: X12 = 1, X33 = 1, Y12 = 2,400, Y31 = 3,200, Y32 = 3,300, total cost = $74,700.
Thus, generator #1 will be utilized in the period 2–10 and will generate 2,400 megawatts of elec-
tricity. Generator #3 will be started at 6 and utilized for the entire 16 hours. It will generate 3,200
megawatts during the 6–2 time period, and 3,300 megawatts during the 2–10 time period.
10-20. Let T = number of TV ads, R = number of newspaper ads, B = number of billboard ads,
(1) number of people reached
40,000T + 32,000R + 34,000B + 17,000N – d1+ + d1– = 1,500,000
(4) restriction on number of each individual type of ad
T – d4+ + d4– = 10
R – d5+ + d5– = 10
B – d6+ + d6– = 10
N – d7+ + d7– = 10
10-21. Let: X1 = number of two-drawer cabinets produced each week
X2 = number of three-drawer cabinets produced each week
Minimize deviations
= P1d1– + P1d1+ + P2d2– + P3d3– + P3d4–
subject to
10X1 + 15X2 + d1– – d1+ = $11,000 (profit target)
10-22. Because we want to achieve the profit goal as closely as possible (minimize both d1– and
d1+), the line ABC becomes the feasible region. When the P2 priority is included, the feasible re-
10-23. X1 = number of 64MB chips produced
X2 = number of 256MB chips produced
X3 = number of 512MB chips produced
d1– = underfilling customer’s order of 64MB chips
Minimize deviations
= P1d1– + P1d2– + P2d3– + P2d4– + P2d5– + P3d6–
subject to
X1 + d1– – d1+ = 30 (64MB chips order)
X2 + d2– – d2+ = 35 (256MB chips order)
10-24 The best solution found using the computer is
X1 = 15
X2 = 20
d1+ = 30
10-25. a.
d1– = underachievement of class and study goal
Major Bligh’s objective function becomes
minimize = d1– + d1+ + d2+ + d3–
subject to constraints (per week)
1X1 + 1X2 + 1X3 + 1X4 168
All variables 0
Since the goals have priority, they can be rewritten in this order, yielding to the absolute comple-
tion of each goal before attempting to achieve the next goal. The objective function would be-
come
Minimize = P1d1– + P1d1+ + P2d2+ + P3d3–
where P1 = meet class and study goal