# ADMS 3330 Study Guide - Linear Programming Relaxation, Sensitivity Analysis, Feasible Region

by OC86253

This

**preview**shows pages 1-3. to view the full**15 pages of the document.**11

Integer Linear Programming

MULTIPLE CHOICE

1. Which of the following is the most useful contribution of integer programming?

a. finding whole number solutions where fractional solutions would not be appropriate

b. using 0-1 variables for modeling flexibility

c. increased ease of solution

d. provision for solution procedures for transportation and assignment problems

ANSWER: b

TOPIC: Introduction

2. In a model, x1 > 0 and integer, x2 > 0, and x3 = 0, 1. Which solution would not be feasible?

a. x1 = 5, x2 = 3, x3 = 0

b. x1 = 4, x2 = .389, x3 = 1

c. x1 = 2, x2 = 3, x3 = .578

d. x1 = 0, x2 = 8, x3 = 0

ANSWER: c

TOPIC: Introduction

3. Rounded solutions to linear programs must be evaluated for

a. feasibility and optimality.

b. sensitivity and duality.

c. relaxation and boundedness.

d. each of the above is true.

ANSWER: a

TOPIC: LP relaxation

4. Rounding the solution of an LP Relaxation to the nearest integer values provides

a. a feasible but not necessarily optimal integer solution.

b. an integer solution that is optimal.

c. an integer solution that might be neither feasible nor optimal.

d. an infeasible solution.

ANSWER: c

TOPIC: Graphical solution

1

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

2Chapter 11 Integer Linear Programming

5. The solution to the LP Relaxation of a maximization integer linear program provides

a. an upper bound for the value of the objective function.

b. a lower bound for the value of the objective function.

c. an upper bound for the value of the decision variables

d. a lower bound for the value of the decision variables

ANSWER: a

TOPIC: Graphical solution

6. The graph of a problem that requires x1 and x2 to be integer has a feasible region

a. the same as its LP relaxation.

b. of dots.

c. of horizontal stripes.

d. of vertical stripes.

ANSWER: b

TOPIC: Graphical solution

7. The 0-1 variables in the fixed cost models correspond to

a. a process for which a fixed cost occurs.

b. the number of products produced.

c. the number of units produced.

d. the actual value of the fixed cost.

ANSWER: a

TOPIC: Fixed costs

8. Sensitivity analysis for integer linear programming

a. can be provided only by computer.

b. has precisely the same interpretation as that from linear programming.

c. does not have the same interpretation and should be disregarded.

d. is most useful for 0 - 1 models.

ANSWER: c

TOPIC: Sensitivity analysis

9. Let x1 and x2 be 0 - 1 variables whose values indicate whether projects 1 and 2 are not done or are done.

Which answer below indicates that project 2 can be done only if project 1 is done?

a. x1 + x2 = 1

b. x1 + x2 = 2

c. x1 - x2 < 0

d. x1 - x2 > 0

ANSWER: d

TOPIC: Conditional and corequisite constraints

10. Let x1 , x2 , and x3 be 0 - 1 variables whose values indicate whether the projects are not done (0) or are

done (1). Which answer below indicates that at least two of the projects must be done?

a. x1 + x2 + x3 > 2

b. x1 + x2 + x3 < 2

c. x1 + x2 + x3 = 2

d. x1 - x2 = 0

ANSWER: a

TOPIC: k out of n alternatives constraints

11. If the acceptance of project A is conditional on the acceptance of project B, and vice versa, the appropriate

constraint to use is a

a. multiple-choice constraint.

b. k out of n alternatives constraint.

c. mutually exclusive constraint.

d. corequisite constraint.

ANSWER: d

TOPIC: Modeling flexibility provided by 0-1 integer variables

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Chapter 11 Integer Linear Programming 3

12. In an all-integer linear program,

a. all objective function coefficients must be integer.

b. all right-hand side values must be integer.

c. all variables must be integer.

d. all objective function coefficients and right-hand side values must be integer.

ANSWER: c

TOPIC: Types of integer linear programming models

13. To perform sensitivity analysis involving an integer linear program, it is recommended to

a. use the dual prices very cautiously.

b. make multiple computer runs.

c. use the same approach as you would for a linear program.

d. use LP relaxation.

ANSWER: b

TOPIC: A cautionary note about sensitivity analysis

14. Modeling a fixed cost problem as an integer linear program requires

a. adding the fixed costs to the corresponding variable costs in the objective function.

b. using 0-1 variables.

c. using multiple-choice constraints.

d. using LP relaxation.

ANSWER: b

TOPIC: Applications involving 0-1 variables

15. Most practical applications of integer linear programming involve

a. only 0-1 integer variables and not ordinary integer variables.

b. mostly ordinary integer variables and a small number of 0-1 integer variables.

c. only ordinary integer variables.

d. a near equal number of ordinary integer variables and 0-1 integer variables.

ANSWER: a

TOPIC: Applications involving 0-1 variables

TRUE/FALSE

1. The LP Relaxation contains the objective function and constraints of the IP problem, but drops all integer

restrictions.

ANSWER: True

TOPIC: LP relaxation

2. In general, rounding large values of decision variables to the nearest integer value causes fewer problems

than rounding small values.

ANSWER: True

TOPIC: LP relaxation

3. The solution to the LP Relaxation of a minimization problem will always be less than or equal to the value

of the integer program minimization problem.

ANSWER: False

TOPIC: Graphical solution

4. If the optimal solution to the LP relaxation problem is integer, it is the optimal solution to the integer

linear program.

ANSWER: True

TOPIC: LP relaxation

###### You're Reading a Preview

Unlock to view full version