CHAPTER 9
INTEGER PROGRAMMING
Review Questions
9.1-1 In some applications, such as assigning people, machines, or vehicles, decision variables
will make sense only if they have integer values. 9.1-2 Integer programming has the additional restriction that some or all of the decision variables
must have integer values. 9.1-3 The divisibility assumption of linear programming is a basic assumption that allows the
decision variables to have any values, including fractional values, that satisfy the functional and nonnegativity constraints. 9.1-4 The LP relaxation of an integer programming problem is the linear programming problem
obtained by deleting from the current integer programming problem the constraints that require the decision variables to have integer values. 9.1-5 Rather than stopping at the last instant that the straight edge still passes through the feasible
region, we now stop at the last instant that the straight edge passes through an integer point that lies within the feasible region. 9.1-6 No, rounding cannot be relied on to find an optimal solution, or even a good feasible
integer solution. 9.1-7 Pure integer programming problems are those where all the decision variables must be
integers. Mixed integer programming problems only require some of the variables to have integer values. 9.1-8 Binary integer programming problems are those where all the decision variables restricted
to integer values are further restricted to be binary variables. 9.2-1 The decisions are 1) whether to build a factory in Los Angeles, 2) whether to build a
factory in San Francisco, 3) whether to build a warehouse in Los Angeles, and 4) whether to build a warehouse in San Francisco. 9.2-2 Binary decision variables are appropriate because there are only two alternatives, choose
yes or choose no. 9.2-3 The objective is to find the feasible combination of investments that maximizes the total
net present value. 9.2-4 The mutually exclusive alternatives are to build a warehouse in Los Angeles or build a
warehouse in San Francisco. The form of the resulting constraint is that the sum of these variables must be less than or equal to 1 (x3 + x4 ≤ 1). 9.2-5 The contingent decisions are the decisions to build a warehouse. The forms of these
constraints are x3 ≤ x1 and x4 ≤ x2.
9-1
9.2-6 The amount of capital being made available to these investments ($10 million) is a
managerial decision on which sensitivity analysis needs to be performed. 9.3-1 A value of 1 is assigned for choosing yes and a value of 0 is assigned for choosing no. 9.3-2 Yes-or-no decisions for capital budgeting with fixed investments are whether or not to
make a certain fixed investment. 9.3-3 Yes-or-no decisions for site selections are whether or not a certain site should be selected
for the location of a certain new facility. 9.3-4 When designing a production and distribution network, yes-or-no decisions like should a
certain plant remain open, should a certain site be selected for a new plant, should a certain distribution center remain open, should a certain site be selected for a new distribution center, and should a certain distribution center be assigned to serve a certain market area might arise. 9.3-5 Should a certain route be selected for one of the trucks.
9.3-6 It is estimated that China is saving about $6.4 billion over the 15 years.
9.3-7 The form of each yes-or-no decision is should a certain asset be sold in a certain time
period. 9.3-8 The airline industry uses BIP for fleet assignment problems and crew scheduling problems. 9.4-1 A binary decision variable is a binary variable that represents a yes-or-no decision. An
auxiliary binary variable is an additional binary variable that is introduced into the model, not to represent a yes-or-no decision, but simply to help formulate the model as a BIP problem. 9.4-2 The net profit is no longer directly proportional to the number of units produced so a linear
programming formulation is no longer valid. 9.4-3 An auxiliary binary variable can be introduced for a setup cost and can be defined as 1 if
the setup is performed to initiate the production of a certain product and 0 if the setup is not performed. 9.4-4 Mutually exclusive products exist when at most one product can be chosen for production
due to competition for the same customers. 9.4-5 An auxiliary binary variable can be defined as 1 if the product can be produced and 0 if the
product cannot be produced. 9.4-6 An either-or constraint arises because the products are to be produced at either Plant 3 or
Plant 4, not both. 9.4-7 An auxiliary binary variable can be defined as 1 if the first constraint must hold and 0 if the
second constraint must hold. 9.5-1 Restriction 1 is similar to the restriction imposed in Variation 2 except that it involves more
products and choices. 9.5-2 The constraint y1 + y2 + y3 ≤ 2 forces choosing at most two of the possible new products.
9-2
9.5-3 It is not possible to write a legitimate objective function because profit is not proportional
to the number of TV spots allocated to that product. 9.5-4 The groups of mutually exclusive alternative in Example 2 are x1 = 0, 1, 2, or 3, x2 = 0, 1, 2,
or 3, and x3 = 0,1,2, or 3. 9.5-5 The mathematical form of the constraint is x1 + x4 + x7 + x10 ≥ 1. This constraint says that
sequence 1, 4, 7, and 10 include a necessary flight and that one of the sequences must be chosen to ensure that a crew covers the flight.
Problems
9.1
a) Let T = the number of tow bars to produce
S = the number of stabilizer bars to produce Maximize Profit = $130T + $150S subject to 3.2T + 2.4S ≤ 16 hours 2T + 3S ≤ 15 hours and T ≥ 0, S ≥ 0 T, S are integers. b) Optimal solution: (T,S) = (0,5). Profit = $750.
c)
A123456789BC
DEFUnit ProfitMachine 1Machine 2Tow Bars$130Stabilizer Bars$150HoursUsed1215<=<=HoursAvailable1615Total Profit$750Hours Used Per Unit Produced3.22.423Tow Bars0Stabilizer Bars5Units Produced 9-3
9.2 a)
A12345678910111213BCDEFModel A(high speed)Unit Cost$6,000Model B(lower speed)$4,000TotalCapacity80,000>=Total6>=6CapacityNeeded75,000Total Cost$28,000CapacityCopies per Day20,00010,000Model A(high speed)2>=1Model B(lower speed)4Min NeededPurchase
b) Let A = the number of Model A (high-speed) copiers to buy B = the number of Model B (lower-speed) copiers to buy Minimize Cost = $6,000A + $4,000B subject to A + B ≥ 6 copiers A ≥ 1 copier 20,000A + 10,000B ≥ 75,000 copies/day and A ≥ 0, B ≥ 0 A, B are integers. c) Optimal solution: (A,B) = (2,4). Cost = $28,000.
9-4