精品数据模型与决策运筹学课后习题和案例答案009

1、chapter 9 integer programming review questions 9.1-1in some applications, such as assigning people, machines, or vehicles, decision variables will make sense only if they have integer values. 9.1-2integer programming has the additional restriction that some or all of the decision variables must have

2、 integer values. 9.1-3the 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-4the lp relaxation of an integer programming problem is the

3、 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-5rather than stopping at the last instant that the straight edge still passes through the feasible region, we now stop at the

4、last instant that the straight edge passes through an integer point that lies within the feasible region. 9.1-6no, rounding cannot be relied on to find an optimal solution, or even a good feasible integer solution. 9.1-7pure integer programming problems are those where all the decision variables mus

5、t be integers. mixed integer programming problems only require some of the variables to have integer values. 9.1-8binary integer programming problems are those where all the decision variables restricted to integer values are further restricted to be binary variables. 9.2-1the decisions are 1) wheth

6、er 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-2binary decision variables are appropriate because there are only two alternatives, choose yes or choose no.

7、 9.2-3the objective is to find the feasible combination of investments that maximizes the total net present value. 9.2-4the 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 var

8、iables must be less than or equal to 1 (x3 + x4 1). 9.2-5the contingent decisions are the decisions to build a warehouse. the forms of these constraints are x3 x1 and x4 x2. 9.2-6the amount of capital being made available to these investments ($10 million) is a managerial decision on which sensitivi

9、ty analysis needs to be performed. 9.3-1a value of 1 is assigned for choosing yes and a value of 0 is assigned for choosing no. 9.3-2yes-or-no decisions for capital budgeting with fixed investments are whether or not to make a certain fixed investment. 9.3-3yes-or-no decisions for site selections ar

10、e whether or not a certain site should be selected for the location of a certain new facility. 9.3-4when 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 cent

11、er 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-5should a certain route be selected for one of the trucks. 9.3-6it is estimated that china is saving about $6.4 billio

12、n over the 15 years. 9.3-7the form of each yes-or-no decision is should a certain asset be sold in a certain time period. 9.3-8the airline industry uses bip for fleet assignment problems and crew scheduling problems. 9.4-1a binary decision variable is a binary variable that represents a yes-or-no de

13、cision. 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-2the net profit is no longer directly proportional to the number of units produced so a linear

14、programming formulation is no longer valid. 9.4-3an 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-4mutually exclusive products exist when at most

15、one product can be chosen for production due to competition for the same customers. 9.4-5an auxiliary binary variable can be defined as 1 if the product can be produced and 0 if the product cannot be produced. 9.4-6an either-or constraint arises because the products are to be produced at either plan

16、t 3 or plant 4, not both. 9.4-7an auxiliary binary variable can be defined as 1 if the first constraint must hold and 0 if the second constraint must hold. 9.5-1restriction 1 is similar to the restriction imposed in variation 2 except that it involves more products and choices. 9.5-2the constraint y

17、1 + y2 + y3 2 forces choosing at most two of the possible new products. 9.5-3it 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-4the groups of mutually exclusive alternative in example 2 are x1 = 0,

18、1, 2, or 3, x2 = 0, 1, 2, or 3, and x3 = 0,1,2, or 3. 9.5-5the 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

19、a) let t = the number of tow bars to produce s = the number of stabilizer bars to produce maximize profit = $130t + $150s subject to3.2t + 2.4s 16 hours 2t + 3s 15 hours andt 0, s 0 t, s are integers. b) optimal solution: (t,s) = (0,5). profit = $750. c) 1 2 3 4 5 6 7 8 9 abcdef tow barsstabilizer b

20、ars unit profit$130$150 hourshours usedavailable machine 13.22.412=16 machine 22315=75,000 model amodel b (high speed)(lower speed)totaltotal cost purchase246$28,000 = 1min needed6 copies per day b) let a = the number of model a (high-speed) copiers to buy b = the number of model b (lower-speed) cop

21、iers to buy minimize cost = $6,000a + $4,000b subject toa + b 6 copiers a 1 copier 20,000a + 10,000b 75,000 copies/day anda 0, b 0 a, b are integers. c) optimal solution: (a,b) = (2,4). cost = $28,000. 9.3a) optimal solution: (x1, x2) = (2, 3). profit = 13. b) the optimal solution to the lp-relaxati

22、on is (x1, x2) = (2.6, 1.6). profit = 14.6. rounded to the nearest integer, (x1, x2) = (3, 2). this is not feasible since it violates the third constraint. rounded solutionfeasible?constraint violatedp (3,2)no3rd- (3,1)no2nd w1, w3; l1, l3; c1, c2; o1, o2, o4; d2; s1, s3; and r2, r3, and r4. this co

23、mbination allows four different kitchen sets to be in stockset 8, 15, 18, and 20. note that this is not a unique solution. the value of the objective function is always four complete kitchen sets, but the specific items and kitchen sets stocked may be different. throughout this solution, we will ref

24、er to the optimal solution shown above, but because other optimal solutions exist, student answers may differ from the solution somewhat. c) we model this new problem by changing the capacity constraint for the dishwashers and ranges. now, instead of being able to stock a combination of only four di

25、fferent styles of dishwashers and ranges, we can stock a maximum of two different styles of dishwashers and a maximum of three different styles of ranges. because we only have two different styles of dishwashers available, we now effectively do not have a constraint on the number of dishwashers we c

26、an carry. the formulation of the problem in excel follows: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 abcdefghijklmnopqrstuvwxyz aa ab ac ad ae afagahai set infraction of t1 t2 t3 t4 w1 w2 w3 w4 l1 l2 l3 l4 c1 c2 c3 c4 o1 o2 o3 o4 d1 d2 s1 s2 s3 s4 r1 r2 r3 r4stock

27、?items in stock set 1111111110=0.25 set 2111111110=0.5 set 3 111111110=0.75 set 4111111111=1 set 5111111110=0.625 set 6111111110=0.5 set 7 111111110=0.75 set 8111111111=1 set 9111111110=0.625 set 10 111111110=0.75 set 11111111111=1 set 12111111110=0.5 set0.625 set 1411111110=0.571 set 1

28、511111111=1 set 1611111110=0.714 set 17 11111110=0.429 set 1811111110=0.571 set 1911111110=0.286 set 2011111111=1 item in stock? 011010101010101011101110101011 floor tile wallpaper light fixtures cabinets countertops sinks ranges total sets in stock total items22223235 = = = = = = = 20 sq. ft.)(= 5

29、rolls) floor tilewallpapersinksrangeslight fixturescabinetscountertopsdwash with the extra space, the number of kitchen sets we can stock increases from four to fivenow sets 4, 8, 11, 15, and 20. to keep these five sets in stock, we stock the following items: t2, t3; w1, w3; l1, l3; c1, c3; o1, o2,

30、o3; d1, d2; s1, s3; r1, r3, and r4. (this optimal solution is not unique.) the new space vacated by the nursery department provides us with the space to stock the new range. d) with the additional space, our constraints change. we eliminate the constraints limiting the maximum number of different st

31、yles of sinks and countertops we can stock. instead of stocking two of the four styles of light fixtures, we can now stock three of the four styles of light fixtures. finally, instead of stocking only two of the four cabinet styles, we can now stock three of the four cabinet styles. the problem form

32、ulated in excel follows. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 abcdefghijklmnopqrstuvwxyz aa ab ac ad ae afagahai set infraction of t1 t2 t3 t4 w1 w2 w3 w4 l1 l2 l3 l4 c1 c2 c3 c4 o1 o2 o3 o4 d1 d2 s1 s2 s3 s4 r1 r2 r3 r4stock?items in stock set 1111111110=0.5

33、 set 2111111110=0.5 set 3 111111110=0.75 set 4111111111=1 set 5111111110=0.75 set 6111111110=0.5 set 7 111111110=0.875 set 8111111111=1 set 9111111110=0.75 set 10 111111110=0.75 set 11111111111=1 set 12111111110=0.5 set0.75 set 1411111110=0.714 set 1511111111=1 set 1611111111=1.000 set

34、17 11111110=0.429 set 1811111110=0.571 set 1911111110=0.571 set 2011111111=1 item in stock? 011010101011101011101111101011 floor tile wallpaper light fixtures cabinets countertops sinks ranges total sets in stock total items22323336 = = = = = = = 20 sq. ft.)(= 5 rolls) floor tilewallpaper with the e

35、xtra space, we are now able to stock six complete kitchen setsset 4, 8, 11, 15, 16, and 20. the following items are stocked: t2, t3; w1, w3, l1, l3, l4; c1, c3, o1, o2, o3; d1, d2; s1, s2, s3; r1, r3, r4. (again, this optimal solution is not unique.) e) if the items composing a kitchen set could not

36、 be replenished immediately, we could not formulate this problem as a binary integer program. we would have to formulate the problem as an integer program since we may have to store more than one kitchen component or kitchen set to ensure that we meet demand. the assumption of immediate replenishmen

37、t is justified if the average time to replenish the component is significantly less than the average time between demands for that component. 9.4a) since a residential area cannot be split across multiple schools, the decision becomes which school to send each areas students to. this is formulated w

38、ith a binary variable for each area/school combination, representing the yes-or-no decision of whether that area should be assigned to that school. each area can only be sent to a single school, represented by the constraints totalassignments (e14:e19) = supply (g14:g19). the number of students in e

39、ach school is then calculated in studentassignments (b24:d29) based upon the results in areaassignments (b14:d19). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 abcdefgh data:percentagepercentagepercentage numberin 6thin 7thin 8t

40、hbussing cost ($/student) areaof studentsgradegradegradeschool 1school 2school 3 145032%38%30%$300$0$700 260037%28%35%$400$500 355030%32%38%$600$300$200 435028%40%32%$200$500 550039%34%27%$0$400 645034%28%38%$500$300$0 area assignmentstotal school 1school 2school 3assignmentssupply area 11001=1 area

41、 20101=1 area 30011=1 area 40101=1 area 50011=1 area 61001=1 student assignments school 1school 2school 3 area 145000 area 206000 area 300550total area 403500bussing area 500500cost area 645000$1,085,000 total in school9009501,050 = capacity9001,1001,000 grade constraints: 27028531530%of total in school = 6th graders297320360 7th graders2973