Study Guides
(238,486)

Canada
(115,176)

York University
(9,816)

Administrative Studies
(1,382)

ADMS 3330
(37)

hassanq
(3)

# 3330_Ch11.doc

Unlock Document

York University

Administrative Studies

ADMS 3330

hassanq

Winter

Description

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, x 1 0 and integer, x 2 0, and x =30, 1. Which solution would not be feasible?
a. x1= 5, x 2 3, x 3 0
b. x1= 4, x 2 .389, x 3 1
c. x1= 2, x 2 3, x 3 .578
d. x1= 0, x 2 8, x 3 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 2 Chapter 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 x and1x to b2 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 x 1nd x b2 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+ x 2 1
b. x1+ x 2 2
c. x1- x 2 0
d. x - x > 0
1 2
ANSWER: d
TOPIC: Conditional and corequisite constraints
10. Let x 1 x 2 and x b3 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+ x 2 x >32
b. x1+ x 2 x <32
c. x1+ x 2 x =32
d. x - x = 0
1 2
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 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 4 Chapter 11 Integer Linear Programming
5. Slack and surplus variables are not useful in integer linear programs.
ANSWER: False
TOPIC: Capital budgeting
6. A multiple choice constraint involves selecting k out of n alternatives, where k > 2.
ANSWER: False
TOPIC: Multiple choice constraint
7. In a model involving fixed costs, the 0 - 1 variable guarantees that the capacity is not available unless the
cost has been incurred.
ANSWER: True
TOPIC: Fixed costs
8. If 1 + 2 < 500y1and y 1s 0 - 1, then if1y is 01 x and2x will be 0.
ANSWER: True
TOPIC: Distribution system design
9. The constraint 1 + x2+ x3+ x 4 2 means that two out of the first four projects must be selected.
ANSWER: False
TOPIC: k out of n alternatives constraint
10. The constraint 1 - 2 = 0 implies that if project 1 is selected, project 2 cannot be.
ANSWER: False
TOPIC: Conditional and corequisite constraints
11. The product design and market share optimization problem presented in the textbook is formulated as a
0-1 integer linear programming model.
ANSWER: True
TOPIC: Product design and market share optimization problem
12. The objective of the product design and market share optimization problem presented in the textbook is to
choose the levels of each product attribute that will maximize the number of sampled customers preferring
the brand in question.
ANSWER: True
TOPIC: Product design and market share optimization problem
13. If a problem has only less-than-or-equal-to constraints with positive coefficients for the variables,
rounding down will always provide a feasible integer solution.
ANSWER: True
TOPIC: Rounding to obtain an integer solution
14. Dual prices cannot be used for integer programming sensitivity analysis because they are designed for
linear programs.
ANSWER: True
TOPIC: A cautionary note about sensitivity analysis
15. Some linear programming problems have a special structure that guarantees the variables will have
integer values.
ANSWER: True
TOPIC: Introduction to integer linear programming
16. Generally, the optimal solution to an integer linear program is less sensitive to the constraint coefficients
than is a linear program.
ANSWER: False
TOPIC: A cautionary note about sensitivity analysis
17. The classic assignment problem can be modeled as a 0-1 integer program.
ANSWER: True Chapter 11 Integer Linear Programming 5
TOPIC: Applications involving 0-1 variables
18. If Project 5 must be completed before Project 6, the constraint would be5x –6x < 0.
ANSWER: False
TOPIC: Conditional and co-requisite constraints
19. If the LP relaxation of an integer program has a feasible solution, then the integer program has a feasible
solution.
ANSWER: False
TOPIC: Rounding to obtain an integer solution
20. Multiple choice constraints involve binary variables.
ANSWER: True
TOPIC: Multiple choice and mutually exclusive constraints
SHORT ANSWER
1. The use of integer variables creates additional restrictions but provides additional flexibility. Explain.
TOPIC: Introduction
2. Why are 0 - 1 variables sometimes called logical variables?
TOPIC: Introduction
3. Give a verbal interpretation of each of these constraints in the context of a capital budgeting problem.
a. x1- x2> 0
b. x - x = 0
1 2
c. x1+ x2+ x 3 2
TOPIC: Capital budgeting
4. Explain how integer and 0-1 variables can be used in an objective function to minimize the sum of fixed
and variable costs for production on two machines.
TOPIC: Distribution system design
5. Explain how integer and 0-1 variables can be used in a constraint to enable production.
TOPIC: Distribution system design
PROBLEMS
1. Solve the following problem graphically.
Max 5X + 6Y
s.t. 17X + 8Y < 136
3X + 4Y < 36
X, Y > 0 and integer
a. Graph the constraints for this problem. Indicate all feasible solutions.
b. Find the optimal solution to the LP Relaxation. Round down to find a feasible integer solution. Is
this solution optimal?
c. Find the optimal solution.
TOPIC: Graphical solution 6 Chapter 11 Integer Linear Programming
2. Solve the following problem graphically.
Max X + 2Y
s.t. 6X + 8Y < 48
7X + 5Y > 35
X, Y > 0
Y integer
a. Graph the constraints for this problem. Indicate all feasible solutions.
b. Find the optimal solution to the LP Relaxation. Round down to find a feasible integer solution. Is
this solution optimal?
c. Find the optimal solution.
TOPIC: Graphical solution
3. Solve the following problem graphically.
Min 6X + 11Y
s.t. 9X + 3Y > 27
7X + 6Y > 42
4X + 8Y > 32
X, Y > 0 and integer
a. Graph the constraints for this problem. Indicate all feasible solutions.
b. Find the optimal solution to the LP Relaxation. Round up to find a feasible integer solution. Is
this solution optimal?
c. Find the optimal solution.
TOPIC: Graphical solution
4. Consider a capital budgeting example with five projects from which to select. Lei x = 1 if project i is
selected, 0 if not, for i = 1,...,5. Write the appropriate constraint(s) for each condition. Conditions are
independent.
a. Choose no fewer than three projects.
b. If project 3 is chosen, project 4 must be chosen.
c. If project 1 is chosen, project 5 must not be chosen.
d. Projects cost 100, 200, 150, 75, and 300 respectively. The budget is 450.
d. No more than two of projects 1, 2, and 3 can be chosen.
TOPIC: Capital budgeting
5. Grush Consulting has five projects to consider. Each will require time in the next two quarters according
to the table below.
Project Time in first quarter Time in second quarter Revenue
A 5 8 12000
B 3 12 10000
C 7 5 15000
D 2 3 5000
E 15 1 20000
Revenue from each project is also shown. Develop a model whose solution would maximize revenue,
meet the time budget of 25 in the first quarter and 20 in the second quarter, and not do both projects C
and D.
TOPIC: Capital budgeting Chapter 11 Integer Linear Programming 7
6. The Westfall Company has a contract to produce 10,000 garden hoses for a large discount chain. Westfall
has four 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.
Fixed Cost to Set Variable Cost
Machine Up Production Run Per Hose Capacity
1 750 1.25 6000
2 500 1.50 7500
3 1000 1.00 4000
4 300 2.00 5000
a. This problem requires two different kinds of decision variables. Clearly define each kind.
b. The company wants to minimize total cost. Give the objective function.
c. Give the constraints for the problem.
d. Write a constraint to ensure that if machine 4 is used, machine 1 cannot be.
TOPIC: Fixed cost
7. Hansen Controls has been awarded a contract for a large number of control panels. To meet this demand,
it will use its existing plants in San Diego and Houston, and consider new plants in Tulsa, St. Louis, and
Portland. Finished control panels are to be shipped to Seattle, Denver, and Kansas City. Pertinent
information is given in the table.
Shipping Cost to Destination:
Construction Kansas
Sources Cost Seattle Denver City Capacity
San Diego ---- 5 7 8 2,500
Houston ---- 10 8 6 2,500
Tulsa 350,000 9 4 3 10,000
St. Louis 200,000 12 6 2 10,000
Portland 480,000 4 10 11 10,000
Demand 3,000 8,000 9,000
Develop a model whose solution would reveal which plants to build and the optimal shipping schedule.
TOPIC: Distribution system design
8. Simplon Manufacturing must decide on the processes to use to produce 1650 units. If machine 1 is used,
its production will be between 300 and 1500 units. Machine 2 and/or machine 3 can be used only if
machine 1's production is at least 1000 units. Machine 4 can be used with no restrictions.
Fixed Variable Minimum Maximum
Machine cost cost Production Production
1 500 2.00 300 1500
2 800 0.50 500 1200
3 200 3.00 100 800
4 50 5.00 any any
(HINT: Use an additional 0 - 1 variable to indicate when machines 2 and 3 can be used.)
TOPIC: Distribution system design
9. Your express package courier company is drawing up new zones for the location of drop boxes for
customers. The city has been divided into the seven zones shown below. You have targeted six possible
locations for drop boxes. The list of which drop boxes could be reached easily from each zone is listed
below. 8 Chapter 11 Integer Linear Programming
Zone Can Be Served By Locations:
Downtown Financial 1, 2, 5, 6
Downtown Legal 2, 4, 5
Retail South 1, 2, 4, 6
Retail East 3, 4, 5
Manufacturing North 1, 2, 5
Manufacturing East 3, 4
Corporate West 1, 2, 6
Let xi= 1 if drop box location i is used, 0 otherwise. Develop a model to provide the smallest number of
locations yet make sure that each zone is covered by at least two boxes.
TOPIC: Applications of integer linear programming
10. Consider the problem faced by a summer camp recreation director who is trying to choose activities for a
rainy day. Information about possible choices is given in the table below.
Popularity Popularity with
Category Activity Time with Campers Counselors
(minutes)
Art 1 - Painting 30 4 2
2 - Drawing 20 5 2
3 - Nature craft 30 3 1
Music 4 - Rhythm band 20 5 5
Sports 5 - Relay races 45 2 1
6 - Basketball 60 1 3
Computer 7 - Internet 45 1 1
8 - Creative writing 30 4 3
9 - Games 40

More
Less
Related notes for ADMS 3330