Informative essay on integer programming

Introduction to ManagementScience, 10e (Taylor) Chapter 5 Integer Programming 1) The 3 types of integer programming models are total, 0 – 1, and mixed. Answer: TRUE Diff: 1Page Ref: 182 Main Heading: Integer Programming Models Key words: integer programming models 2) In a total integer model, all decision variables have integer solution values. Answer: TRUE Diff: 1Page Ref: 182 Main Heading: Integer Programming Models Key words: integer programming models 3) In a 0 – 1 integer model, the solution values of the decision variables are 0 or 1. Answer: TRUE Diff: 1Page Ref: 182

Main Heading: Integer Programming Models Key words: integer programming models 4) In a mixed integer model, some solution values for decision variables are integer and others can be non-integer. Answer: TRUE Diff: 1Page Ref: 183 Main Heading: Integer Programming Models Key words: integer programming models 5) In a mixed integer model, all decision variables have integer solution values. Answer: FALSE Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: integer programming models 6) In a mixed integer model, the solution values of the decision variables are 0 or 1.

Answer: FALSE Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: integer programming models 7) The branch and bound method can only be used for maximization integer programming problems. Answer: FALSE Diff: 1Page Ref: 187 Main Heading: Integer Programming Models Key words: integer programming models, branch and bound 8) The branch and bound solution method cannot be applied only to 0-1 integer programming problems. Answer: FALSE Diff: 2Page Ref: 187 Main Heading: Integer Programming Models Key words: integer programming models, branch and bound method ) In a problem involving capital budgeting applications, the 0-1 variables designate the acceptance or rejection of the different projects. Answer: TRUE Diff: 2Page Ref: 196 Main Heading: Integer Programming Models Key words: capital budgeting, 0-1 variables 10) In a 0-1 integer programming problem involving a capital budgeting application (where xj = 1, if project j is selected, xj = 0, otherwise) the constraint x1 – x2 ? 0 implies that if project 2 is selected, project 1 can not be selected. Answer: FALSE Diff: 2Page Ref: 196 Main Heading: Integer Programming Models Key words: capital budgeting, 0-1 variables 1) The divisibility assumption is violated by integer programming. Answer: TRUE Diff: 1Page Ref: 182 Main Heading: Integer Programming Models Key words: integer linear programming models, multiple choice constraint 12) One type of constraint in an integer program is a multiple choice constraint. Answer: TRUE Diff: 1Page Ref: 184 Main Heading: Integer Programming Models Key words: integer linear programming models, multiple choice constraint 13) If exactly 3 projects are to be selected from a set of 5 projects, this would be written as 3 separate constraints in an integer program. Answer: FALSE Diff: 2Page Ref: 184

Main Heading: Integer Programming Models Key words: integer linear programming models, multiple choice constraint 14) A conditional constraint specifies the conditions under which variables are integers or real variables. Answer: FALSE Diff: 1Page Ref: 184 Main Heading: Integer Programming Models Key words: integer linear programming models, constraint 15) Rounding non-integer solution values up to the nearest integer value can result in an infeasible solution to an integer programming problem. Answer: TRUE Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: integer programming models, graphical solution 6) A feasible solution to an integer programming problem is ensured by rounding down non-integer solution values. Answer: TRUE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, graphical solution 17) A feasible solution to an integer programming problem is ensured by rounding down integer solution values. Answer: FALSE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, graphical solution 18) A rounded-down integer solution can result in a less than optimal solution to an integer programming problem.

Answer: TRUE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, graphical solution 19) Rounding down integer solution values ensures an infeasible solution to an integer linear programming problem. Answer: FALSE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, graphical solution 20) Rounding non-integer solution values up to the nearest integer value will result in an infeasible solution to an integer linear programming problem. Answer: FALSE Diff: 2Page Ref: 186

Main Heading: Integer Programming Models Key words: integer programming models, graphical solution 21) Rounding non-integer solution values up to the nearest integer value will still result in a feasible solution. Answer: FALSE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, graphical solution 22) The solution to the LP relaxation of a maximization integer linear program provides a lower bound for the value of the objective function. Answer: FALSE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models

Key words: integer programming models, LP relaxation 23) The solution to the LP relaxation of a maximization integer linear program provides an upper bound for the value of the objective function. Answer: TRUE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, LP relaxation 24) The solution to the LP relaxation of a minimization integer linear program provides a lower bound for the value of the objective function. Answer: TRUE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, LP relaxation 5) The solution to the LP relaxation of a minimization integer linear program provides an upper bound for the value of the objective function. Answer: FALSE Diff: 2Page Ref: 186 Main Heading: Integer Programming Models Key words: integer programming models, LP relaxation 26) If we perform sensitivity analysis for an integer linear programming problem, we can provide the same interpretation as we would have obtained from interpreting the corresponding linear programming problem. Answer: FALSE Diff: 2Page Ref: 182 Main Heading: Integer Programming Models Key words: integer programming models, sensitivity analysis 7) If we are solving a 0-1 integer programming problem, the constraint x1 + x2 + x3 ? 3 is a mutually exclusive constraint. Answer: FALSE Diff: 2Page Ref: 183 Main Heading: Integer Programming Models Key words: integer linear programming models, 0-1 variables 28) If we are solving a 0-1 integer programming problem, the constraint x1 + x2 ? 1 is a mutually exclusive constraint. Answer: TRUE Diff: 2Page Ref: 183 Main Heading: Integer Programming Models Key words: integer linear programming models, 0-1 variables 29) If we are solving a 0-1 integer programming problem, the constraint x1 + x2 = 1 is a mutually exclusive constraint.

Answer: FALSE Diff: 2Page Ref: 183 Main Heading: Integer Programming Models Key words: 0-1 variables, multiple choice constraint 30) If we are solving a 0-1 integer programming problem, the constraint x1 ? x2 is a mutually exclusive constraint. Answer: FALSE Diff: 2Page Ref: 183 Main Heading: Integer Programming Models Key words: 0-1 variables, conditional constraints 31) If we are solving a 0-1 integer programming problem, the constraint x1 = x2 is a conditional constraint. Answer: FALSE Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: 0-1 variables, corequisite constraints 2) If we are solving a 0-1 integer programming problem, the constraint x1 ? x2 is a conditional constraint. Answer: TRUE Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: 0-1 variables, multiple choice constraint 33) In a __________ linear programming model, some of the solution values for the decision variables are required to assume integer values and others can be integer or noninteger. Answer: mixed integer Diff: 1Page Ref: 183 Main Heading: Integer Programming Models Key words: integer programming models, mixed integer programming models 4) In a __________ linear programming model, the solution values of the decision variables are zero or one. Answer: 0-1 integer Diff: 1Page Ref: 183 Main Heading: Integer Programming Models Key words: integer programming models, 0-1 integer programming models 35) If exactly one investment is to be selected from a set of five investment options, then the constrain is often called a __________ constraint. Answer: multiple-choice Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: integer linear programming formulation, capital budgeting 6) If we graph the problem that requires x1 and x2 to be an integer, it has a feasible region consisting of __________. Answer: dots Diff: 3Page Ref: 187 Main Heading: Integer Programming Models Key words: integer linear programming models, graphical solution 37) __________ variables are best suited to be the decision variables when dealing with yes-or-no decisions. Answer: 0-1 Diff: 2Page Ref: 183 Main Heading: Integer Programming Models Key words: integer linear programming models, 0-1 variables 38) If we are solving a 0-1 integer programming problem, the constraint x1 + x2 ? is a __________ constraint. Answer: mutually exclusive Diff: 2Page Ref: 183 Main Heading: Integer Programming Graphical Solution Key words: integer linear programming models, 0-1 variables 39) If we are solving a 0-1 integer programming problem, the constraint x1 + x2 = 1 is a __________ constraint. Answer: multiple-choice Diff: 2Page Ref: 184 Main Heading: Integer Programming Graphical Solution Key words: 0-1 variables, multiple choice constraint 40) If we are solving a 0-1 integer programming problem, the constraint x1 ? x2 is a __________ constraint. Answer: conditional Diff: 2Page Ref: 184

Main Heading: Integer Programming Graphical Solution Key words: 0-1 variables, conditional constraints 41) If we are solving a 0-1 integer programming problem, the constraint x1 = x2 is a __________ constraint. Answer: corequisite Diff: 2Page Ref: 184 Main Heading: Integer Programming Graphical Solution Key words: 0-1 variables, corequisite constraints 42) Because of their structure, __________ types of linear programming problems always result in integer solutions, even though integer solutions are not specified in the linear program. Answer: Transportation or Assignment Diff: 2Page Ref: 203

Main Heading: Integer Programming Models Key words: integer linear programming models, transportation 43) If one location for a warehouse can be selected only if a specific location for a manufacturing facility is also selected, this decision can be represented by a __________ constraint. Answer: Conditional Diff: 2Page Ref: 183 Main Heading: Integer Programming Models Key words: integer linear programming models, constraint 44) In an integer program, if we were choosing between two locations to build a facility, this would be written as: __________. Answer: x1 + x2 = 1 Diff: 2Page Ref: 184

Main Heading: Integer Programming Models Key words: integer linear programming models, constraint 45) In an integer program, if building one facility required the construction of another type of facility, this would be written as: __________. Answer: x1 = x2 Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: integer linear programming models, constraint 46) Consider the following integer linear programming problem Max Z = 3×1 + 2×2 Subject to: 3×1 + 5×2 ? 30 4×1 + 2×2 ? 28 x1 ? 8 x1 , x2 ? 0 and integer The solution to the Linear programming relaxation is: x1 = 5. 14, x2 = 2. 571. What is the upper bound for the value of the objective function? What is the value of the objective function for the rounded down solution? Is the rounded down solution feasible? Answer: yes, 22. 286, 19 Diff: 1Page Ref: 187 Main Heading: Integer Programming Graphical Solution Key words: integer linear programming, integer programming solution 47) Consider the following integer linear programming problem Max Z = 3×1 + 2×2 Subject to: 3×1 + 5×2 ? 30 4×1 + 2×2 ? 28 x1 ? 8 x1 , x2 ? 0 and integer The solution to the Linear programming relaxation is: x1 = 5. 714, x2 = 2. 571.

What is the optimal solution to the integer linear programming problem? State the optimal values of decision variables and the value of the objective function. Answer: x1 = 6, x2 = 2, Z = 22 Diff: 2Page Ref: 187 Main Heading: Integer Programming Graphical Solution Key words: integer linear programming solution 48) Consider the following integer linear programming problem Max Z = 3×1 + 2×2 Subject to: 3×1 + 5×2 ? 30 5×1 + 2×2 ? 28 x1 ? 8 x1 , x2 ? 0 and integer The solution to the Linear programming relaxation is: x1 = 5. 714, x2= 2. 571. What is the optimal solution to the integer linear programming problem?

State the optimal values of decision variables and the value of the objective function. Answer: x1 = 4, x2 = 3, Z = 18 Diff: 2Page Ref: 187 Main Heading: Integer Programming Graphical Solution Key words: integer linear programming solution Consider a capital budgeting example with 5 projects from which to select. Let x1 = 1 if project a is selected, 0 if not, for a = 1, 2, 3, 4, 5. Projects cost $100, $200, $150, $75, and $300 respectively. The budget is $450. 49) Write the appropriate constraint for the following condition: Choose no fewer than 3 projects. Answer: x1+x2+x3+x4+x5 ? Diff: 1Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: formulation of 0-1 constraints 50) Write the appropriate constraint for the following condition: If project 3 is chosen, project 4 must be chosen. Answer: x3 – x4 ? 0 Diff: 1Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: formulation of 0-1 constraints 51) Write the appropriate constraint for the following condition: If project 1 is chosen, project 5 must not be chosen. Answer: x1 + x5 ? 1 Diff: 2Page Ref: 184

Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: formulation of 0-1 constraints The Wiethoff Company has a contract to produce 10000 garden hoses for a customer. Wiethoff has 4 different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same. [pic] 52) This problem requires 2 different kinds of decision variables. Clearly define each kind. Answer: xa = the number of hoses produced on machine a; ya= 1 if machine a is used, 0 if not Diff: 2Page Ref: 194-195

Main Heading: Integer Programming Models Key words: integer program prob formulation, decision variable definition 53) Write the objective function. Answer: MIN Z = 1. 25X1 + 1. 50X2 + 1. 00X3 + 2. 000X4+ 750Y1 + 500Y2 +1000Y3 + 300Y4 Diff: 2Page Ref: 194-195 Main Heading: Integer Programming Models Key words: integer programming problem formulation, model constraints 54) Write a constraint to ensure that if machine 4 is used, machine 1 will not be used. Answer: y1 + y4 ? 1 Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: integer programming problem formulation, model constraints 5) Write a constraint that will ensure that Weithoff purchases exactly 2 machine. s Answer: Y1 + Y2 + Y3 + Y4 = 2 Diff: 2Page Ref: 184 Main Heading: Integer Programming Models Key words: integer programming formulation, constraint 56) Max Z = x1 + 6×2 Subject to: 17×1 + 8×2 ? 136 3×1 + 4×2 ? 36 x1, x2 ? 0 and integer Find the optimal solution. Answer: x1 = 0, x2 = 9, Z = 54 Diff: 2Page Ref: 191-194 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming problem computer solution 57) Max Z = 3×1 + 5×2 Subject to: 7×1 + 12×2 ? 136 3×1 + 5×2 ? 36 x1, x2 ? 0 and integer

Find the optimal solution. Answer: x1 = 2, x2 = 6, Z = 36 Diff: 2Page Ref: 191-194 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming problem computer solution 58) Solve the following integer linear program graphically. MAX Z = 5×1 + 8×2 s. t. x1 + x2 ? 6 5×1 + 9×2 ? 45 x1, x2 ? 0 and integer Answer: x1 = 0, x2 = 5, Z = 40 Diff: 3Page Ref: 191-194 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming graphical solution 59) You have been asked to select at least 3 out of 7 possible sites for oil exploration.

Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are: Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7. Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5. Restriction 3. Of all the sites, at least 3 should be assessed. Assuming that Si is a binary variable, write the constraint for the first restriction. Answer: S1 + S3 +S7 ? 2 Diff: 3Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming formulation, constraint 0) You have been asked to select at least 3 out of 7 possible sites for oil exploration. Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are: Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7. Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5. Restriction 3. Of all the sites, at least 3 should be assessed. Assuming that Si is a binary variable, write the constraint(s) for the second restriction. Answer: S2 +S5 ? 1, S4 +S5 ? 1 Diff: 3Page Ref: 184

Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming formulation, constraint 61) You have been asked to select at least 3 out of 7 possible sites for oil exploration. Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are: Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7. Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5. Restriction 3. Of all the sites, at least 3 should be assessed. Assuming that Si is a binary variable, write the constraint for the third restriction.

Answer: S1 + S2 + S3 +S4 + S5 + S6 + S7 ? 3 Diff: 1Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming formulation, constraint Due to increased sales, a company is considering building 3 new distribution centers (DCs) to serve 4 regional sales areas. The annual cost to operate DC 1 is $500 (in thousands of dollars). The cost to operate DC 2 is $600 (in thousands of dollars. ). The cost to operate DC 3 is $525 (thousands of dollars). Assume that the variable cost of operating at each location is the same, and therefore not a consideration in making the location decision.

The table below shows the cost ($ per item) for shipping from each DC to each region. Region | DC | A | B | C | D | | 1 | 1 | 3 | 3 | 2 | | 2 | 2 | 4 | 1 | 3 | | 3 | 3 | 2 | 2 | 3 | The demand for region A is 70, 000 units; for region B, 100, 000 units; for region C, 50, 000 units; and for region D, 80, 000 units. Assume that the minimum capacity for the distribution center will be 500, 000 units. 62) Define the decision variables for this situation.

Answer: y1 = 1 if DC1 is selected, 0 otherwise y2 = 1 if DC2 is selected, 0 otherwise y3 = 1 if DC3 is selected, 0 otherwise x1A = quantity shipped from DC 1 to Region A x1B = quantity shipped from DC 1 to Region B x1C = quantity shipped from DC 1 to Region C x1D = quantity shipped from DC 1 to Region D x2A = quantity shipped from DC 2 to Region A x2B = quantity shipped from DC 2 to Region B x2C = quantity shipped from DC 2 to Region C x2D = quantity shipped from DC 2 to Region D x3A = quantity shipped from DC 3 to Region A x3B = quantity shipped from DC 3 to Region B x3C = quantity shipped from DC 3 to Region C 3D = quantity shipped from DC 3 to Region D Diff: 2Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: facility location example, mixed integer programming 63) Write the objective function for this problem . Answer: Min Z = 1x1A + 3x1B + 3 x1C + 2x1D + 2x2A + 4x2B + 1x2C + 3x2D + 3x3A + 2x3B + 2x3C +3 x3D + 500y1 + 600y2 + 525y3 Diff: 2Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: facility location example, mixed integer programming 64) Write the constraints for the 3 distribution centers.

Answer: x1A + x1B +x1c – 500y1 ? 0 x2A + x2B +x2c – 500y2 ? 0 x3A + x3B +x3c – 500y3 ? 0 Diff: 2Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: facility location example, mixed integer programming 65) Types of integer programming models are __________. A) total B) 0 – 1 C) mixed D) all of the above Answer: D Diff: 1Page Ref: 182 Main Heading: Integer Programming Problems Key words: integer programming models 66) In a __________ integer model, some solution values for decision variables are integers and others can be non-integer. A) total

B) 0 – 1 C) mixed D) all of the above Answer: C Diff: 2Page Ref: 182 Main Heading: Integer Programming Problems Key words: integer programming models, mixed integer models 67) In a __________ integer model, all decision variables have integer solution values. A) total B) 0 – 1 C) mixed D) all of the above Answer: A Diff: 2Page Ref: 182 Main Heading: Integer Programming Problems Key words: integer programming models 68) In a __________ integer model, the solution values of the decision variables are 0 or 1. A) total B) 0 – 1 C) mixed D) all of the above Answer: B Diff: 2Page Ref: 183

Main Heading: Integer Programming Problems Key words: integer programming models 69) Binary variables are A) 0 or 1 only B) any integer value C) any continuous value D) any negative integer value Answer: A Diff: 1Page Ref: 183 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming formulation 70) Which of the following is not an integer linear programming problem? A) pure integer B) mixed integer C) 0-1integer D) continuous Answer: D Diff: 2Page Ref: 182 Main Heading: Integer Programming Problems Key words: integer programming models 1) If the solution values of a linear program are rounded in order to obtain an integer solution, the solution is A) always optimal and feasible B) sometimes optimal and feasible C) always optimal D) always feasible E) never optimal and feasible Answer: B Diff: 3Page Ref: 186 Main Heading: Integer Programming Problems Key words: integer programming models 72) The branch and bound method of solving linear integer programming problems is __________. A) an integer method B) a relaxation method C) a graphical solution D) an enumeration method Answer: D Diff: 2Page Ref: 187 Main Heading: Integer Programming Problems

Key words: integer programming solution methods, branch and bound method 73) If a maximization linear programming problem consist of all less-than-or-equal-to constraints with all positive coefficients and the objective function consists of all positive objective function coefficients, then rounding down the linear programming optimal solution values of the decision variables will __________ result in a(n) __________ solution to the integer linear programming problem. A) always, optimal B) always, non-optimal C) never, non-optimal D) sometimes, optimal E) never, optimal Answer: D Diff: 2Page Ref: 187

Main Heading: Integer Programming Problems Key words: integer programming solution, rounding off 74) If a maximization linear programming problem consist of all less-than-or-equal-to constraints with all positive coefficients and the objective function consists of all positive objective function coefficients, then rounding down the linear programming optimal solution values of the decision variables will __________ result in a feasible solution to the integer linear programming problem. A) always B) sometimes C) never Answer: A Diff: 2Page Ref: 187 Main Heading: Integer Programming Problems

Key words: integer programming solution, rounding off 75) If we are solving a 0-1 integer programming problem, the constraint x1 + x2 ? 1 is a __________ constraint. A) multiple choice B) mutually exclusive C) conditional D) corequisite E) none of the above Answer: B Diff: 2Page Ref: 183 Main Heading: Integer Programming Problems Key words: mutually exclusive constraints, 0-1 variables 76) If we are solving a 0-1 integer programming problem, the constraint x1 + x2 = 1 is a __________ constraint. A) multiple choice B) mutually exclusive C) conditional D) corequisite E) none of the above Answer: A Diff: 2Page Ref: 184

Main Heading: Integer Programming Problems Key words: multiple choice constraints, 0-1 variables 77) If we are solving a 0-1 integer programming problem, the constraint x1 ? x2 is a __________ constraint. A) multiple choice B) mutually exclusive C) conditional D) corequisite E) none of the above Answer: C Diff: 2Page Ref: 184 Main Heading: Integer Programming Problems Key words: conditional constraints, 0-1 variables 78) If we are solving a 0-1 integer programming problem, the constraint x1 = x2 is a __________ constraint. A) multiple choice B) mutually exclusive C) conditional D) corequisite E) none of the above

Answer: D Diff: 2Page Ref: 184 Main Heading: Integer Programming Problems Key words: corequisite constraints, 0-1 variables 79) For a maximization integer linear programming problem, feasible solution is ensured by rounding __________ non-integer solution values if all of the constraints are less-than -or equal-to type. A) up and down B) up C) down D) up or down Answer: C Diff: 2Page Ref: 186 Main Heading: Integer Programming Graphical Solution Key words: integer linear programming solution 80) The implicit enumeration method A) generates an optimal integer solution when no new constraints can be added o the relaxed linear programming model B) eliminates obviously infeasible solutions and evaluates the remaining solutions to determine which one is optimal C) is used to solve a mixed integer linear programming model D) cannot be used to solve linear programming models with multiple infeasible solutions Answer: B Diff: 3Page Ref: 187 Main Heading: Integer Programming Graphical Solution Key words: integer programming solution method 81) The linear programming relaxation contains the objective function and the original constraints of the integer programming problem, but drops all __________.

A) different variables B) slack values C) integer restrictions D) decision variables E) nonnegativity constraints Answer: C Diff: 2Page Ref: 187 Main Heading: Integer Programming Graphical Solution Key words: integer linear programming, model formulation and solution 82) The solution to the linear programming relaxation of a minimization problem will always be __________ the value of the integer programming minimization problem. A) greater than or equal to B) less than or equal to C) equal to D) different than Answer: B Diff: 1Page Ref: 187 Main Heading: Integer Programming Graphical Solution

Key words: integer linear programming model solution 83) If the optimal solution to the linear programming relaxation problem is integer, it is __________ to the integer linear programming problem. A) a real solution B) a degenerate solution C) an infeasible solution D) the optimal solution E) a feasible solution Answer: D Diff: 3Page Ref: 187 Main Heading: Integer Programming Graphical Solution Key words: integer linear programming model solution 84) In a capital budgeting problem, if either project 1 or project 2 is selected, then project 5 cannot be selected.

Which of the alternatives listed below correctly models this situation? A) x1 + x2 + x5 ? 1 B) x1 + x2 + x5 ? 1 C) x1 + x5 ? 1, x2 + x5 ? 1 D) x1 – x5 ? 1, x2 – x5 ? 1 E) x1 – x5 = 0, x2 – x5 = 0 Answer: C Diff: 2Page Ref: 184 Main Heading: Integer Programming Graphical Solution Key words: integer programming formulation, constraint 85) You have been asked to select at least 3 out of 7 possible sites for oil exploration. Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are: Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7.

Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5. Restriction 3. Of all the sites, at least 3 should be assessed. Assuming that Si is a binary variable, the constraint for the first restriction is A) S1 + S3 + S7 ? 1 B) S1 + S3 + S7 ? 1 C) S1 + S3 + S7 = 2 D) S1 + S3 + S7 ? 2 E) S1 + S3 + S7 = 3 Answer: D Diff: 3Page Ref: 184 Main Heading: Integer Programming Graphical Solution Key words: integer programming formulation, constraint Due to increased sales, a company is considering building 3 new distribution centers (DCs) to serve 4 regional sales areas.

The annual cost to operate DC 1 is $500 (in thousands of dollars). The cost to operate DC 2 is $600 (in thousands of dollars. ). The cost to operate DC 3 is $525 (thousands of dollars). Assume that the variable cost of operating at each location is the same, and therefore not a consideration in making the location decision. The table below shows the cost ($ per item) for shipping from each DC to each region. Region | DC | A | B | C | D | | 1 | 1 | 3 | 3 | 2 | | 2 | 2 | 4 | 1 | 3 | 3 | 3 | 2 | 2 | 3 | The demand for region A is 70, 000 units; for region B, 100, 000 units; for region C, 50, 000 units; and for region D, 80, 000 units. Assume that the minimum capacity for the distribution center will be 500, 000 units. Assume that Xij = quantity shipped from distribution i to region j, i = 1, 2, 3; j = 1, 2, 3, 4. Assume that Yi = 0 or 1 where i = distribution center 1, 2 or 3. 86) The constraint for distribution center 1 is: A) X11 + X12 +X13 + X14- 500y1 ? 0 B) X11 + X12 +X13 + X14D + 500y1 ? 0 C) X11 + X12 +X13 + X14 ? 500 D) X11 + X12 +X13 + X14 ? 500

Answer: A Diff: 2Page Ref: 183 Main Heading: Integer Programming Graphical Solution Key words: facility location example, mixed integer programming 87) The objective function is A) [pic] B) [pic] C) [pic] D) [pic] Answer: A Diff: 3Page Ref: 198 Main Heading: Integer Programming Graphical Solution Key words: facility location example, mixed integer programming 88) You have been asked to select at least 3 out of 7 possible sites for oil exploration. Designate each site as S1, S2, S3, S4, S5, S6, and S7. The restrictions are: Restriction 1. Evaluating sites S1 and S3 will prevent you from exploring site S7.

Restriction 2. Evaluating sites S2 or S4 will prevent you from assessing site S5. Restriction 3. Of all the sites, at least 3 should be assessed. Assuming that Si is a binary variable, write the constraint(s) for the second restriction A) S2 +S5 ? 1 B) S4 +S5 ? 1 C) S2 +S5 + S4 +S5 ? 2 D) S2 +S5 ? 1, S4 +S5 ? 1 Answer: D Diff: 3Page Ref: 184 Main Heading: Integer Programming Graphical Solution Key words: integer programming formulation, constraint Future Plastics manufactures plastic products for industrial use worldwide. In order to meet demand, they are considering setting up a facility in each egion in order to lower transportation cost and to possibly avoid duties that could be imposed if the product is imported from another region. The disadvantage of this approach is that plants are sized to meet local demand and may not fully exploit economies of scale. Therefore, Future Plastics is also interested in determining the appropriate size of facility to build in each location and are choosing between facilities with capacities of 5 or 10 million. The fixed costs of each facility as well as the cost of shipping between regions is shown in the table below.

The decision variables are defined as follows: Xij = quantity shipped from supply region i to demand region j. i = 1, 2, 3, 4 and j = 1, 2, 3, 4. Yik = 1 if facility k is selected for supply region i; 0 otherwise. where i = 1, 2, 3, 4 for each supply region; k = 1 (low capacity facility) or 2 (high capacity facility) | | Demand Region | Low Capacity | High Capacity | | | Production and Transportation Cost per 1, 000, 000 Units | | |

Supply Region | North America | South America | South Asia | Europe | Fixed Cost | Capacity | Fixed Cost | Capacity | | North America | 40 | 45 | 51 | 65 | 3, 000 | 5 | 4, 500 | 10 | | South America | 51 | 57 | 47 | 60 | 3, 200 | 5 | 4, 800 | 10 | | South Asia | 58 | 63 | 45 | 31 | 2, 000 | 5 | 3, 000 | 10 | | Europe | 71 | 50 | 51 | 53 | 1, 800 | 5 | 2, 700 | 10 | | Demand | 6 | 4 | 7 | 8 | | | | | | 89) The constraint for the North American supply region is: A) X11 + X21 + X31 + X34 – 5Y11 – 10Y21 ? 0 B) X11 + X12 + X13 + X14 – 5Y11 – 10Y12 ? 0 C) X11 + X12 + X13 + X14 – 3200Y11 – 4800Y12 ? 0 D) X11 + X12 + X13 + X14 – 5Y11 – 10Y12 = 0 Answer: B

Diff: 3Page Ref: 198 Main Heading: Integer Programming Models Key words: mixed integer linear programming problems 90) The constraint for the South Asia demand region is: A) X31 + X32 + X33 + X34 = 7 B) X31 + X32 + X33 + X34 ? 7 C) X13 + X23 + X33 + X43 ? 7 D) X13 + X23 + X33 + X43 = 7 Answer: A Diff: 3Page Ref: 198 Main Heading: Integer Programming Models Key words: mixed integer linear programming problems 91) Which of these constraints will ensure that either a low capacity or a high facility capacity facility is built in the European supply region? A) Y41 + Y42 = 1 B) Y41 + Y42 ? 1

C) Y14 + Y24 = 1 D) Y14 + Y24 ? 1 Answer: A Diff: 3Page Ref: 198 Main Heading: Integer Programming Models Key words: mixed integer linear programming problems 92) Which of these constraints will ensure that a low capacity facility is NOT built in South America? A) Y12 + Y22 ? 1 B) Y12 + Y22 = 1 C) Y12 + Y22 = 0 D) Y21 + Y22 ? 1 Answer: C Diff: 2Page Ref: 198 Main Heading: Integer Programming Models Key words: mixed integer linear programming problems 93) Max Z = 5×1 + 6×2 Subject to: 17×1 + 8×2 ? 136 3×1 + 4×2 ? 36 x1, x2 ? 0 and integer What is the optimal solution? A) x1 = 6, x2 = 4, Z = 54

B) x1 = 3, x2 = 6, Z = 51 C) x1 = 2, x2 = 6, Z = 46 D) x1 = 4, x2 = 6, Z = 56 E) x1 = 0, x2 = 9 Z = 54 Answer: D Diff: 2Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming solution 94) Assume that we are using 0-1 integer programming model to solve a capital budgeting problem and xj = 1 if project j is selected and xj = 0, otherwise. The constraint (x1 + x2 + x3 + x4 ? 2) means that __________ out of the 4 projects must be selected. A) exactly 1, 4 B) exactly 2, 4 C) at least 2, 4 D) at most 2, 4 Answer: B Diff: 2Page Ref: 196

Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming formulation, 0-1 integer programming 95) In a 0-1 integer programming model, if the constraint x1-x2 = 0, it means when project 1 is selected, project 2 __________ be selected. A) can also B) can sometimes C) can never D) must also Answer: D Diff: 2Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming formulation 96) In a 0-1 integer programming model, if the constraint x1-x2 ? 0, it means when project 2 is selected, project 1 __________ be selected.

A) must always B) can sometimes C) can never D) A and B Answer: B Diff: 2Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: integer programming formulation 97) In formulating a mixed integer programming problem, the constraint x1 + x2 ? 500y1 where y1 is a 0-1 variable and x1 and x2 are continuous variables, then x1 + x2 = 500 if y1 is __________. A) 0 B) 1 C) 0 or 1 D) none of the above Answer: B Diff: 3Page Ref: 184 Main Heading: Computer Solution of Integer Program Probs w/Excel, QM for Win Key words: mixed integer programming problem

The Wiethoff Company has a contract to produce 10000 garden hoses for a customer. Wiethoff has 4 different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same. [pic] 98) Write a constraint to ensure that if machine 4 is used, machine 1 will not be used. A) Y1 + Y4 ? 0 B) Y1 + Y4 = 0 C) Y1 + Y4 ? 1 D) Y1 + Y4 ? 0 E) Y1 + Y4 ? 1 Answer: C Diff: 3Page Ref: 183 Main Heading: Integer Programming Problems Key words: mixed integer programming problem, constraint formulation 9) Write the constraint for machine 4. A) Y4 = 11 B) Y4 ? 300 C) X4 ? 5000 D) X4 -300Y1 ? 0 E) 2X4 -300Y1? 5000 Answer: C Diff: 3Page Ref: 184 Main Heading: Integer Programming Problems Key words: mixed integer programming problem, constraint formulation 100) Write the constraint that indicates they can purchase no more than 3 machines. A) Y1 + Y2 + Y3+ Y4 ? 3 B) Y1 + Y2 + Y3+ Y4 = 3 C) Y1 + Y2 + Y3+ Y4 ? 3 D) Y1 + Y2 + Y3 = 3 Y2 + Y3+ Y4 = 3 E) none of the above Answer: A Diff: 3Page Ref: 184 Main Heading: Integer Programming Problems Key words: mixed integer programming problem, constraint formulation