Operations Management, 11e (Heizer/Render)
Module B Linear Programming
Section 1 Why Use Linear Programming?
1) Linear programming helps operations managers make decisions necessary to make effective use of
resources such as machinery, labor, money, time, and raw materials.
2) In which of the following has LP been applied successfully?
A) minimizing distance traveled by school buses carrying children
B) minimizing 911 response time for police patrols
C) minimizing labor costs for bank tellers while maintaining service levels
D) determining the distribution system for multiple warehouses to multiple destinations
E) all of the above
3) ________ is a mathematical technique designed to help operations managers plan and make decisions
necessary to allocate resources.
4) What is linear programming?
5) Identify three examples of resources that are typically constrained in a linear programming problem.
Section 2 Requirements of a Linear Programming Problem
1) One requirement of a linear programming problem is that the objective function must be expressed as
a linear equation.
2) Linear programming is an appropriate problem-solving technique for decisions that have no
alternative courses of action.
3) Which of the following represents a valid constraint in linear programming?
A) 2X ≥ 7XY
B) (2X)(7Y) ≥ 500
C) 2X + 7Y ≥100
D) 2X2 + 7Y ≥ 50
E) All of the above are valid linear programming constraints.
4) Which of the following is not a requirement of a linear programming problem?
A) an objective function, expressed in linear terms
B) constraints, expressed as linear equations or inequalities
C) an objective function to be maximized or minimized
D) alternative courses of action
E) one constraint or resource limit for each decision variable
5) The requirements of linear programming problems include an objective function, the presence of
constraints, objective and constraints expressed in linear equalities or inequalities, and ________.
6) The ________ is a mathematical expression in linear programming that maximizes or minimizes some
quantity.
7) ________ are restrictions that limit the degree to which a manager can pursue an objective.
8) What are the requirements of all linear programming problems?
Section 3 Formulating Linear Programming Problems
1) A common form of the product-mix linear programming problem seeks to find that combination of
products and the quantity of each that maximizes profit in the presence of limited resources.
2) In linear programming, a statement such as “maximize contribution” becomes an objective function
when the problem is formulated.
3) In a linear programming formulation, a statement such as “maximize contribution” becomes a(n):
A) constraint.
B) slack variable.
C) objective function.
D) violation of linearity.
E) decision variable.
4) If cars sell for $500 profit and trucks sell for $300 profit, which of the following represents the objective
function?
A) Maximize profit = 500C + 300T
B) Minimize profit = 500C + 300T
C) Maximize profit = 500C – 300T
D) Minimize profit = 300T – 500C
E) Maximize profit = 800(T + C)
5) A linear programming problem contains a restriction that reads “the quantity of X must be at least
three times as large as the quantity of Y.” Which of the following inequalities is the proper formulation of
this constraint?
A) 3X ≥ Y
B) X ≤ 3Y
C) X + Y ≥ 3
D) X – 3Y ≥ 0
E) 3X ≤ Y
6) A linear programming problem contains a restriction that reads “the quantity of Q must be no larger
than the sum of R, S, and T.” Formulate this as a linear programming constraint.
A) Q + R + S + T ≤ 4
B) Q ≥ R + S + T
C) Q – R – S – T ≤ 0
D) Q / (R + S + T) ≤ 0
E) Q ≤ R + Q ≤ S + Q ≤ T
7) A linear programming problem contains a restriction that reads “the quantity of S must be no less than
one-fourth as large as T and U combined.” Formulate this as a linear programming constraint.
A) S / (T + U) ≥ 4
B) S – .25T –.25U ≥ 0
C) 4S ≤ T + U
D) S ≥ 4T / 4U
E) S ≥ .25T + S ≥ .25U
8) A firm makes two products, Y and Z. Each unit of Y costs $10 and sells for $40. Each unit of Z costs $5
and sells for $25. If the firm’s goal were to maximize profit, what would be the appropriate objective
function?
A) Maximize profit = $40Y = $25Z
B) Maximize profit = $40Y + $25Z
C) Maximize profit = $30Y + $20Z
D) Maximize profit = 0.25Y + 0.20Z
E) Maximize profit = $50(Y + Z)
9) A linear programming problem contains a restriction that reads “the quantity of X must be at least
twice as large as the quantity of Y.” Formulate this as a linear programming constraint.
10) A linear programming problem contains a restriction that reads “the quantity of Q must be at least as
large as the sum of R, S, and T.” Formulate this as a linear programming constraint.
11) A linear programming problem contains a restriction that reads “the quantity of S must be no more
than one-fourth as large as T and U combined.” Formulate this as a linear programming constraint.
1) In terms of linear programming, the fact that the solution is infeasible implies that the “profit” can
increase without limit.
2) The region that satisfies all of the constraints in linear programming is called the region of optimality.
B-7
3) Solving a linear programming problem with the iso-profit line solution method requires that we move
the iso-profit line to each corner of the feasible region until the optimum is identified.
4) The optimal solution to a linear programming problem lies within the feasible region.
6) In linear programming, if there are three constraints, each representing a resource that can be used up,
the optimal solution must use up all of each of the three resources.
7) In the graphical solution to a linear program, the region that satisfies the constraint 4X + 15Z ≥ 1000
includes the origin of the graph.
8) The feasible region in the diagram below is consistent with which one of the following constraints?
A) 8X1 + 4X2 ≤ 160
B) 8X1 + 4X2 ≥ 160
C) 4X1 + 8X2 ≤ 160
D) 8X1 – 4X2 ≤ 160
E) 4X1 – 8X2 ≤ 160
9) The feasible region in the diagram below is consistent with which one of the following constraints?
A) 8X1 + 4X2 ≥ 160
B) 4X1 + 8X2 ≤ 160
C) 8X1 – 4X2 ≤ 160
D) 8X1 + 4X2 ≤ 160
E) 4X1 – 8X2 ≤ 160
10) An iso-profit line:
A) can be used to help solve a profit maximizing linear programming problem.
B) is parallel to all other iso-profit lines in the same problem.
C) is a line with the same profit at all points.
D) all of the above
E) none of the above
11) Which of the following combinations of constraints has no feasible region?
A) X + Y ≥ 15 and X – Y ≤ 10
B) X + Y ≥ 5 and X ≥ 10
C) X ≥ 10 and Y ≥ 20
D) X + Y ≥ 100 and X + Y ≤ 50
E) X ≤ -5
12) The corner-point solution method requires:
A) identifying the corner of the feasible region that has the sharpest angle.
B) moving the iso-profit line to the highest level that still touches some part of the feasible region.
C) moving the iso-profit line to the lowest level that still touches some part of the feasible region.
D) finding the coordinates at each corner of the feasible solution space.
E) none of the above
13) Which of the following sets of constraints results in an unbounded maximization problem?
A) X + Y ≥ 100 and X + Y ≤ 50
B) X + Y ≥ 15 and X – Y ≤ 10
C) X + Y ≤ 10 and X ≥ 5
D) X ≤ 10 and Y ≤ 20
E) All of the above have a bounded maximum.
14) What is the region that satisfies all of the constraints in linear programming called?
A) area of optimal solutions
B) area of feasible solutions
C) profit maximization space
D) region of optimality
E) region of non-negativity
15) Using the iso-profit line solution method to solve a maximization problem requires that we:
A) find the value of the objective function at the origin.
B) move the iso-profit line away from the origin until it barely touches some part of the feasible region.
C) move the iso-cost line to the lowest level that still touches some part of the feasible region.
D) test the objective function value of every corner point in the feasible region.
E) none of the above
16) For the constraints given below, which point is in the feasible region of this maximization problem?
(1) 14x + 6y ≤ 42 (2) x – y ≤ 3 (3) x, y ≥ 0
A) x = 2, y = 1
B) x = 1, y = 5
C) x = -1, y = 1
D) x = 4, y = 4
E) x = 2, y = 8
17) For the following constraints, which point is in the feasible region of this minimization problem?
(1) 14x + 6y > 42 (2) x – y > 3
A) x = -1, y = 1
B) x = 0, y = 4
C) x = 2, y = 1
D) x = 5, y = 1
E) x = 2, y = 0
18) What combination of x and y will yield the optimum for this problem?
Maximize $3x + $15y, subject to (1) 2x + 4y ≤ 12 and (2) 5x + 2y ≤ 10 and (3) x, y ≥ 0.
A) x = 2, y = 0
B) x = 0, y = 3
C) x = 0, y = 0
D) x = 1, y = 5
E) x = 0, y = 5
19) What combination of x and y will yield the optimum for this problem?
Minimize $3x + $15y, subject to (1) 2x + 4y ≤ 12 and (2) 5x + 2y ≤ 10 and (3) x, y ≥ 0.
A) x = 2, y = 0
B) x = 0, y = 3
C) x = 0, y = 0
D) x = 1, y = 5
E) x = 0, y = 5
20) What combination of a and b will yield the optimum for this problem?
Maximize $6a + $15b, subject to (1) 4a + 2b ≤ 12 and (2) 5a + 2b ≤ 20 and (3) x, y ≥ 0.
A) a = 0, b = 0
B) a = 3, b = 3
C) a = 0, b = 6
D) a = 6, b = 0
E) a = 0, b = 10
B-13
21) A maximizing linear programming problem has two constraints: 2X + 4Y ≤ 100 and 3X + 10Y ≤ 210, in
addition to constraints stating that both X and Y must be nonnegative. What are the corner points of the
feasible region of this problem?
A) (0, 0), (50, 0), (0, 21), and (20, 15)
B) (0, 0), (70, 0), (25, 0), and (15, 20)
C) (20, 15)
D) (0, 0), (0, 100), and (210, 0)
E) (0, 0), (0, 25), (50, 0), (0, 21), and (70, 0)
22) A linear programming problem has two constraints 2X + 4Y ≤ 100 and 1X + 8Y ≤ 100, plus
nonnegativity constraints on X and Y. Which of the following statements about its feasible region is
TRUE?
A) There are four corner points including (50, 0) and (0, 12.5).
B) The two corner points are (0, 0) and (50, 12.5).
C) The graphical origin (0, 0) is not in the feasible region.
D) The feasible region includes all points that satisfy one constraint, the other, or both.
E) The feasible region cannot be determined without knowing whether the problem is to be minimized or
maximized.
23) A linear programming problem has two constraints 2X + 4Y ≥ 100 and 1X + 8Y ≤ 100, plus
nonnegativity constraints on X and Y. Which of the following statements about its feasible region is
TRUE?
A) There are four corner points including (50, 0) and (0, 12.5).
B) The two corner points are (0, 0) and (50, 12.5).
C) The graphical origin (0, 0) is in the feasible region.
D) The feasible region is triangular in shape, bounded by (50, 0), (33.3333, 8.3333), and (100, 0).
E) The feasible region cannot be determined without knowing whether the problem is to be minimized or
maximized.
24) A linear programming problem has three constraints, plus nonnegativity constraints on X and Y. The
constraints are: 2X + 10Y ≤ 100; 4X + 6Y ≤ 120; 6X + 3Y ≤ 90.
What is the largest quantity of X that can be made without violating any of these constraints?
A) 50
B) 30
C) 20
D) 15
E) 10
25) Suppose that an iso-profit line is given to be X + Y = 10. Which of the following represents another iso–
profit line for the same scenario?
A) X + Y = 15
B) X – Y = 10
C) Y – X = 10
D) 2X + Y = 10
E) none of the above
26) Suppose that the feasible region of a maximization LP problem has corners of (0,0), (10,0), (5,5), and
(0,7). If profit is given to be $X + $2Y what is the maximum profit the company can earn?
A) $0
B) $10
C) $15
D) $14
E) $24
27) Suppose that the feasible region of a maximization LP problem has corners of (0,0), (5,0), and (0,5).
How many possible combinations of X and Y will yield the maximum profit if profit is given to be 5X +
5Y?
A) 0
B) 1
C) 2
D) 5
E) Infinite
28) Which of the following correctly describes all iso-profit lines for an LP maximization problem?
A) They all pass through the origin
B) They are all parallel.
C) They all pass through the point of maximum profit.
D) Each line passes through at least 2 corners.
E) all of the above
29) A linear programming problem has three constraints, plus nonnegativity constraints on X and Y. The
constraints are: 2X + 10Y ≤ 100; 4X + 6Y ≤ 120; 6X + 3Y ≥ 90.
What is the largest quantity of X that can be made without violating any of these constraints?
A) 50
B) 30
C) 20
D) 15
E) 10
30) Consider the following constraints from a two-variable linear program:X ≥ 1;Y ≥ 1;X + Y ≤ 9.
If these are the only constraints, which of the following points (X, Y) CANNOT be the optimal solution?
A) (1, 1)
B) (1, 8)
C) (8, 1)
D) (4, 4)
E) The question cannot be answered without knowing the objective function.
31) The ________ is the set of all feasible combinations of the decision variables.
32) Two methods of solving linear programming problems by hand include the corner-point method and
the ________.
33) What is the feasible region in a linear programming problem?
34) What are corner points? What is their relevance to solving linear programming problems?