Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
Operations Management: Processes and Supply Chains, 12e (Krajewski)
Supplement D Linear Programming
1) Linear programming is useful for allocating scarce resources among competing demands.
2) An = (equal to) constraint is often used for certain mandatory relationships.
3) Decision variables are represented in both the objective function and the constraints while formulating
a linear program.
4) A parameter is a region that represents all permissible combinations of the decision variables in a
linear programming model.
5) In linear programming, each parameter is assumed to be known with certainty.
6) The objective function Maximize Z = 3x2 + 4y is appropriate for linear programming.
7) One assumption of linear programming is that a decision maker cannot use negative quantities of the
parameters.
8) A manager is interested in using linear programming to analyze production for the ensuing week. She
knows that it will take exactly 1.5 hours to run a batch of product A and that this batch will consume two
tons of sugar. This is an example of the linear programming assumption of:
A) linearity.
B) certainty.
C) continuous variables.
D) whole numbers.
9) Which of the following statements regarding linear programming is best?
A) A parameter is also known as a decision variable.
B) Linearity assumes proportionality and additivity.
C) Since nonnegativity is required, parameters must be greater than or equal to zero.
D) Linear programming ensures the decision maker will reach a single, optimal solution.
10) ________ is useful for allocating scarce resources among competing demands.
11) The ________ is an expression in linear programming models that states mathematically what is being
maximized or minimized.
12) In a linear program, ________ represent choices the decision maker can control.
13) In a linear program, ________ are the limitations that restrict the permissible choices for the decision
variables.
14) The ________ represents all permissible combinations of the decision variables in a linear
programming model.
15) A(n) ________ is a value that the decision maker cannot control and that does not change when the
16) Parameters that are quantified without doubt meet the linear programming assumption of ________.
4
17) ________ is an assumption that the decision variables must be either positive or zero.
18) The assumption of ________ allows a decision maker to combine the profit from one product with the
profit from another to realize the total profit from a feasible solution.
19) What are the assumptions of linear programming? Provide examples of each.
Answer: The assumptions are certainty, linearity, and nonnegativity. The assumption of certainty is that
5
20) A manufacturer builds finished items A, B, and C from five different components. They currently
have several finished units, a number of items that are partially complete, and many components that
have just been delivered from their suppliers. The finished items, incomplete items and raw components
can all be assigned some monetary value even though the manufacturer typically does not sell anything
except finished items. The manufacturer needs to raise capital quickly so they formulate a linear program
to help them decide on the most profitable way ahead. Their linear programming expert forgets to restrict
their decision variables to non-negative values and is surprised when the computer output tells them that
finished item A and C should be negative. If the company always follows the advice of their linear
programming analysis, what should they do and why?
Answer: The assumption of nonnegativity is that decision variables must either be positive or zero. In
this case, it would appear that either A) the components are more valuable to the company than the
6
Copyright © 2019 Pearson Education, Inc.
D.2 Formulating a Linear Programming Model
1) In a linear programming model, the objective function answers the question What is to be maximized?
Scenario D.1
Lisa lives out in the country with her seven cats and avoids driving into the big city as much as possible.
She has decided to make her own cat food and has the following nutritional guidelines. Each four ounce
portion must contain 20 units of protein, 15 units of vitamin A, and 10 units of vitamin B. She has eggs,
tomatoes, and chicken meat as possible inputs to her cat food. Each ounce of eggs contains 5 units of
protein, 4 units of Vitamin A, and 3 units of Vitamin B. Each ounce of tomatoes contains 1 unit of protein,
5 units of Vitamin A, and 14 units of Vitamin B. Each ounce of chicken contains 22 units of protein, 14
units of Vitamin A, and 5 units of Vitamin B. Chicken costs 40 cents per ounce, tomatoes cost 8 cents per
ounce, and eggs cost 12 cents per ounce.
2) Referring to Scenario D.1, what is an appropriate objective function for this scenario?
A) Max Z = .12*Egg + .08*Tomato + .4*Chicken
B) Max Z = 20*Protein + 15*VitaminA + 10*VitaminB
C) Min Z = .12*Egg + .08*Tomato + .4*Chicken
D) Min Z = 20*Protein + 15*VitaminA + 10*VitaminB
3) Referring to Scenario D.1, what is an appropriate constraint for this scenario?
A) 4*Eggs + 5*Tomatoes + 14*Chicken ≥ 15
B) 22*Protein + 15*VitaminA + 8*VitaminB ≥ 8
C) .12*Egg + .5*Tomato + .4*Chicken ≥ 4
D) 22*Protein + 15*VitaminA + 8*VitaminB ≥ 4
4) Referring to Scenario D.1, what is an appropriate constraint for this scenario?
A) 4*Eggs + 8*Tomatoes + 14*Chicken ≤ 15
B) 5*Eggs + 1*Tomatoes + 22*Chicken ≥ 20
C) 4*Eggs + 8*Tomatoes + 14*Chicken = 15
D) 15*VitaminA = Eggs + Tomatoes + Chicken
5) Referring to Scenario D.1, which of the following statements is best?
A) Making the cat food out of only eggs is optimal
B) Making the cat food out of only eggs is less expensive than making it out of only tomatoes.
C) Making the cat food out of only eggs means that the Vitamin B constraint would not be satisfied.
D) Making the cat food out of only chicken means the Vitamin B constraint would not be satisfied.
6) Referring to Scenario D.1, assume that an optimal serving contains 0.89 ounces of chicken
and 0.52 ounces of tomatoes. Which of the following statements is best?
A) The serving costs about 20 cents.
B) The serving costs about 30 cents
C) The serving costs about 40 cents.
D) The serving costs about 50 cents.
7) The ________ problem is a one-period type of aggregate planning problem, the solution of which yields
optimal output quantities of a group of products or services, subject to resource capacity and market
demand conditions.
8) A producer has three products, A, B, and C, which are composed from many of the same raw materials
and subassemblies by the same skilled workforce. Each unit of product A uses 15 units of raw material X,
a single purge system subassembly, a case, a power cord, three labor hours in the assembly department,
and one labor hour in the finishing department. Each unit of product B uses 10 units of raw material X,
five units of raw material Y, two purge system subassemblies, a case, a power cord, five labor hours in
the assembly department, and 90 minutes in the finishing department. Each unit of product C uses five
units of raw material X, 25 units of raw material Y, two purge system subassemblies, a case, a power cord,
seven labor hours in the assembly department, and three labor hours in the finishing department. Labor
between the assembly and finishing departments is not transferable, but workers within each department
work on any of the three products. There are three full-time (40 hours/week) workers in the assembly
department and one full-time and one half-time (20 hours/week) worker in the finishing department. At
the start of this week, the company has 300 units of raw material X, 400 units of raw material Y, 60 purge
system subassemblies, 40 cases, and 50 power cords in inventory. No additional deliveries of raw
materials are expected this week. There is a $90 profit on product A, a $120 profit on product B, and a
$150 profit on product C. The operations manager doesn't have any firm orders, but would like to make
at least five of each product so he can have the products on the shelf in case a customer wanders in off the
street.
Formulate the objective function and all constraints, and clearly identify each constraint by the name of
the resource or condition it represents.
9) NYNEX must schedule round-the-clock coverage for its telephone operators. To keep the number of
different shifts down to a manageable level, it has only four different shifts. Operators work eight-hour
shifts and can begin work at either midnight, 8 a.m., noon, or 4 p.m. Operators are needed according to
the following demand pattern, given in four-hour time blocks.
Time Period
Operators
Needed
midnight to 4 a.m.
4
4 a.m. to 8 a.m.
6
8 a.m. to noon
90
Noon to 4 p.m.
85
4 p.m. to 8 p.m.
55
8 p.m. to midnight
20
Formulate this scheduling decision as a linear programming problem, defining fully your decision
variables and then giving the objective function and constraints.
10) A portfolio manager is trying to balance investments between bonds, stocks and cash. The return on
stocks is 12 percent, 9 percent on bonds, and 3 percent on cash. The total portfolio is $1 billion, and he or
she must keep 10 percent in cash in accordance with company policy. The fund's prospectus promises
that stocks cannot exceed 75 percent of the portfolio, and the ratio of stocks to bonds must equal two.
Formulate this investment decision as a linear programming problem, defining fully your decision
variables and then giving the objective function and constraints.
11) Lisa lives out in the country with her seven cats and avoids driving into the big city as much as
possible. She has decided to make her own cat food and has the following nutritional guidelines. Each
four ounce portion must contain 22 units of protein, 15 units of vitamin A, and 8 units of vitamin B. She
has eggs, tomatoes, and chicken meat as possible inputs to her cat food. Each ounce of eggs contains 6
units of protein, 4 units of Vitamin A, and 3 units of Vitamin B. Each ounce of tomatoes contains 1 unit of
protein, 8 units of Vitamin A, and 14 units of Vitamin B. Each ounce of chicken contains 22 units of
protein, 14 units of Vitamin A, and 8 units of Vitamin B. Chicken costs 40 cents per ounce, tomatoes cost 5
cents per ounce, and eggs cost 12 cents per ounce. To make the production process as easy as possible,
she would like to make exactly four ounces of cat food from her recipe. Formulate this decision as a linear
programming problem, defining fully your decision variables and then giving the objective function and
constraints.
12) Belsky Manufacturing makes three models of fans, identified by the unimaginative names of A, B, and
C. The fans are made out of nuts, bolts, wire, blades, and motors. The current inventory levels and parts
list for each type of fan is shown in the table.
Fan A
Fan B
Fan C
Component
# Needed
# Needed
# Needed
Current
Inventory
Wire
1
2
3
500
Nuts
8
12
14
700
Bolts
8
12
14
700
Motor
1
1
2
200
Blades
5
6
7
400
Fan A sells for $18, Fan B sells for $25, and Fan C sells for $30. Formulate this decision as a linear
programming problem, defining fully your decision variables and then giving the objective function and
constraints.
12
13) Belsky Manufacturing makes three models of fans, identified by the unimaginative names of A, B, and
C. The fans are made out of nuts, bolts, wire, blades, and motors. The current inventory levels and parts
list for each type of fan is shown in the table.
Fan A
Fan B
Fan C
Component
# Needed
# Needed
# Needed
Current
Inventory
Wire
1
2
3
500
Nuts
8
12
14
700
Bolts
8
12
14
700
Motor
1
1
2
200
Blades
5
6
7
400
Fan A sells for $18, Fan B sells for $25, and Fan C sells for $30.
Milo Belsky decided to arrive at an optimal production quantity using linear programming. His initial
solution was to produce 50 Fan As and 21.4 Fan Cs for a profit of $1,542.86.
Determine what his inventory would be.
Charlie Belsky made an important change to the model and ran the linear programming software again,
His solution was to produce 50 Fan As, -150 Fan Bs, and 150 Fan Cs for a profit of $1,650 units. What
change did he make to the model and what would the ending inventory be if they were to produce
according to this plan? What are the practical implications of this solution?
Answer: The ending inventory after the production of 50 Fan As and 21.4 Fan C is:
Part
Remaining
Wire
385.7
Nuts
0
Bolts
0
Motor
107.1
Blades
0
The change was to relax the nonnegativity assumption, hence the negative value for the Fan B decision
Part
Remaining
Wire
300
Nuts
0
Bolts
0
Motor
0
Blades
0
13
Copyright © 2019 Pearson Education, Inc.
D.3 Graphic Analysis
1) Only corner points should be considered for the optimal solution to a linear programming problem.
2) The graphical method is a practical method for solving product mix problems of any size, provided the
decision maker has sufficient quantities of graph paper.
3) When plotting constraints, it is best to ignore the inequality aspect of the equation.
4) A binding constraint has slack but does not have surplus.
5) The terms slack and surplus both refer to having too much of a resource.
6) An equality constraint requires that only the points on the line described by the constraint are feasible.
7) Which of the following statements regarding linear programming is not true?
A) A linear programming problem can have more than one optimal solution.
B) Most real-world linear programming problems are solved on a computer.
C) If a binding constraint were relaxed, the optimal solution wouldn't change.
D) A surplus variable is added to a > constraint to convert it to an equality.
8) For the line that has the equation 4X1 + 8X2 = 88, an axis intercept is:
A) (0, 22).
B) (6, 0).
C) (6, 22).
D) (0, 11).
9) Consider a corner point to a linear programming problem, which lies at the intersection of the
following two constraints:
6X1 + 15X2 < 390
2X1 + X2 < 50
Which of the following statements about the corner point is true?
A) X1 < 21
B) X1 > 25
C) X1 < 10
D) X1 > 17
10) A manager is interested in deciding production quantities for products A, B, and C. He has an
inventory of 20 tons each of raw materials 1, 2, 3, and 4 that are used in the production of products A, B,
and C. He can further assume that he can sell all of what he makes. Which of the following statements is
correct?
A) The manager has four decision variables.
B) The manager has three constraints.
C) The manager has three decision variables.
D) The manager can solve this problem graphically.
11) You are faced with a linear programming objective function of:
Max P = $20X + $30Y
and constraints of:
3X + 4Y = 24 (Constraint A)
5X - Y = 18 (Constraint B)
You discover that the shadow price for Constraint A is 7.5 and the shadow price for Constraint B is 0.
Which of these statements is true?
A) You can change quantities of X and Y at no cost for Constraint B.
B) For every additional unit of the objective function you create, you lose 0 units of B.
C) For every additional unit of the objective function you create, the price of A rises by $7.50.
D) The most you would want to pay for an additional unit of A would be $7.50.
12) While glancing over the sensitivity report, you note that the stitching labor has a shadow price of $10
and a lower limit of 24 hours with an upper limit of 36 hours. If your original right hand value for
stitching labor was 30 hours, you know that:
A) the next worker that offers to work an extra 8 hours should receive at least $80.
B) you can send someone home 6 hours early and still pay them the $60 they would have earned while on
the clock.
C) you would be willing pay up to $60 for someone to work another 6 hours.
D) you would lose $80 if one of your workers missed an entire 8 hour shift.
13) In linear programming, a(n) ________ is a point that lies at the intersection of two (or possibly more)
constraint lines on the boundary of the feasible region.
14) A(n) ________ limits the ability to improve the objective function.
15) ________ is the amount by which the left-hand side falls short of the right-hand side in a linear
programming model.
16) ________ is the amount by which the left-hand side exceeds the right-hand side in a linear
programming model.
17) A modeler is limited to two or fewer decision variables when using the ________.
18) The ________ is the upper and lower limit of an objective function coefficient over which the optimal
values of the decision variables remain unchanged.
19) For an "equal" constraint, only points ________ are feasible solutions.
20) A(n) ________ is the marginal improvement in the objective function value caused by relaxing a
constraint by one unit.
21) The interval over which the right-hand-side parameter of a constraint can vary while its shadow price
remains valid is the ________.
22) In a linear programming model formulation, what does the feasible region represent?
Answer: A simultaneous consideration of the constraints defines the feasible region, which represents all
permissible combinations of the decision variables. In some unusual situations, the problem is so tightly
constrained that there is only one possible solution–or perhaps none. However, in the usual case, the
feasibility region contains infinitely many possible solutions, assuming that the feasible combinations of
the decision variables can be fractional values. The goal of the decision maker is to find the best possible
23) In a linear programming model formulation, what is the meaning of a slack or surplus variable?
24) What are the limitations of the graphical method of linear programming?
25) You observe a linear programming problem that has been solved using the graphical method of linear
programming. The feasible region and optimal solution are clearly labeled. How could you identify the
slack or surplus amounts in the scenario?
26) Briefly describe the meaning of a shadow price. Provide an example of how a manager could use
information about shadow prices to improve operations?
19
27) Use the graphical technique to find the optimal solution for this objective function and associated
constraints.
Maximize: Z = 8A + 5B
Subject To:
Constraint 1 4A + 5B < 80
Constraint 2 7A + 4B < 120
A, B > 0
Graph the problem fully in the following space. Label the axes carefully, plot the constraints, shade the
feasibility region, identify all candidate corner points, and indicate which one yields the optimal answer.
20
Answer:
Intersection of Constraint 1 & 2
(7A + 4B = 120) × 5
-(4A + 5B = 80) × 4
19A = 280
A = 14.73, ∴ B = 4.21
