Supplementary Chapter C—Modeling Using Linear Programming
TRUE/FALSE
1. The term ‘programming’ is used in linear programming because these models find the best
‘program’ or course of action to follow.
2. Solutions to a linear programming model that satisfy all constraints are referred to as opti-
mal.
3. is linear since x is to the first power.
4. The constraint that requires the ending inventory from previous month plus current produc-
tion minus ending inventory of this month equals this month’s demand is known as a demand
requirement.
5. If a single variable is used to represent the change in production level, only positive changes
would be permitted, because of the nonnegativity requirement.
6. Since price is usually set by market conditions, the blending problem’s use of linear pro-
gramming attempts to meet the demand at a minimum cost.
7. Deciding on how much of each grade of gasoline to produce is an example of the linear pro-
gramming model for blending applications.
8. The transportation problem is a special type of linear programming that arises in planning
the distribution of goods and services from only one supply point to several demand locations.
9. For linear programming to work for project crashing decisions, a dummy activity is needed at
the beginning of the project, with a duration of zero (0) time.
OM5 Test Bank Supplementary Chapter C 2
10. The total project cost can be minimized by minimizing crash costs.
11. Excel Solver can handle basic linear programming but not the special transportation prob-
lem.
MULTIPLE CHOICE
12. Constant terms in the objective function are called objective function _____.
a.
variables
b.
decisions
c.
coefficients
d.
constraints
13. Any particular combination of decision variables is referred to as a(n) _____.
a.
objective
b.
solution
c.
constraint
d.
coefficient
14. The constraint x1 and x2 0 refers to:
a.
feasibility.
b.
maximization.
c.
binding.
d.
nonnegativity.
15. If Rm = increase in the total production level during month ‘m’ compared to month m–1 and
Dm = decrease in the total production level during month ‘m’ compared to month m–1, which of
the following statements can be correct?
a.
Rm = Dm = 0.
b.
Both Rm and Dm are positive.
c.
Both Rm and Dm are negative.
d.
One variable can be positive and the other negative.
16. In production scheduling, (ending inventory from the previous month) + (current produc-
tion)–(ending inventory this month) = _____.
OM5 Test Bank Supplementary Chapter C 3
a. production rate change
b. this month’s demand
c. amount of overtime/undertime
d. next month’s inventory
17. Which of the following factors would generally NOT be part of a linear programming model
for production scheduling?
a.
Fluctuations in production
b.
Inventory levels
c.
Waiting time probability distributions
d.
Storage capacity
18. If a company has a demand of 1,600 units for the month of May and a beginning of 900
units, and if Xm = production in May and Lm = the number of lost sales in May, which of the fol-
lowing equations represents the material-balance constraint?
a.
Xm – Im + 900 + Lm = 1,600
b.
Xm + Im – 900 + Lm = 1,600
c.
Xm – Im + 900 – Lm = 1,600
d.
–Xm – Im + 900 – Lm = 1,600
19. In a production inventory, (a month’s production) + (beginning inventory) (ending
inventory) – (number of lost sales for the month) = _____.
a.
overtime limits
b.
demand in the month
c.
increase in production
d.
decrease in production
20. A company has normal capacity for 2,500 units a month. If, x11 and x21 represent the pro-
duction decisions variables, which of the following equations represents the occurrence of
change?
a.
x11 + x21 − 2500
b.
x11 − x21 − 2500
c.
x12 − x21 − 2500
d.
x12 + x21 − 2500
21. A company is considering a rate change, either an increase or a decrease in production,
where
OM5 Test Bank Supplementary Chapter C 4
Xt = production in a time period; Rt = increase in production rate from Period t−1 to Period t; Dt
= decrease in production rate from Period t−1 to Period t. Which of the following is correct?
a.
Xt − Xt – 1 = Dt − Rt
b.
Xt – 1 − Xt = Dt − Rt
c.
Xt – 1 − Xt = Rt − Dt
d.
Xt − Xt – 1 = Rt − Dt
22. Which of the following factors would generally NOT be part of a linear programming model
for blending?
a.
Revenue
b.
Cost
c.
Product/component specifications
d.
Supply = demand
23. Which of the following is generally TRUE of the transportation problem of linear program-
ming?
a.
A specified quantity of goods is needed at each demand location.
b.
The objective is to maximize profit.
c.
The shipping cost from each source to each destination is the same.
d.
An exponential loading/unloading distribution is assumed.
24. The precedence relationships in a network limit the activity _____.
a.
nonnegativity time
b.
overtime
c.
crash time
d.
inventory time
25. If Activity C directly precedes both D and E on a project network, and C can be crashed
three (3) times using linear programming, then:
a.
crash time affects only C.
b.
crash time affects only C and D.
c.
crash time affects only C and E.
d.
crash time affects both D and E.
SHORT ANSWER
26. Discuss the concept of optimization models with examples.
27. Differentiate between a feasible solution and an optimal solution.
28. What characterizes a linear function?
ar.
29. Explain the essence of a blending problem.
30. Explain the essence of a transportation problem.
OM5 Test Bank Supplementary Chapter C 6
31. Explain the steps necessary to solve a linear programming problem using Microsoft Excel’s
Solver.
PROBLEMS
32. The Pacific Computer Company makes two models of notebook personal computers: Model
410 with CD-ROM drive, and Model 540 with DVD drive. Profits on each model are $100 and
$150, respectively. Weekly manufacturing data (in minutes) are given below:
Notebook
Dept. A
Dept. B
Model
Manuf. Time
Manuf. Time
Assembly Time
410
5
14
25
540
10
7
40
Manufacturing time available in department A for the coming week is 300 minutes, and for de-
partment B, it is 420 minutes. Total time available during the week to assemble the fabricated
units is 1600 minutes.
a. What is the objective function if the company wants to maximize profits?
b. What is the constraint corresponding to Department A assuming x1 corresponds to Model
410?
c. What is the optimum solution point for this problem?
d. What is the maximum possible total profit?
33. The Northwest Flower Company owns a greenhouse, which supplies roses and carnations to
florists in Oregon, Washington, and Idaho. The greenhouse can grow any combination of the
two flowers. They sell the flowers in “bunches” with 25 blooms to a bunch. They have 10,000
square feet available for planting this year. Each bunch of roses takes about 4 square feet and
each bunch of carnations about 5 square feet. A special fertilizer is required for the flowers:
roses need 5 pounds and carnations 2 pounds. The availability of the fertilizer is limited to 5000
pounds. Sales commitments require the company to grow at least 500 bunches of roses. Profit
contributions are $6 per bunch of roses and $8 per bunch of carnations.
a. What is the objective function if the company wants to maximize its profits?
b. What is the constraint for the square footage assuming x1 corresponds to roses?
c. What is the optimal solution point for this problem?
d. What is the optimal value of the objective function?
OM5 Test Bank Supplementary Chapter C 8
34. A company manufactures 50-inch and 75-inch rear projection television sets. Each 50-inch
set contributes $200 to profits and each 75-inch set contributes $475 to profits. The company
has purchase commitments for 500 50-inch sets and 200 75-inch sets for the next month, so
they want to make at least that many television sets. Although they think they can sell all the
50-inch sets that they could currently make, they do not think they can sell more than 375 75-
inch sets. Their production capacity allows them to make only 975 sets in total including both
types of television sets. They want to know how many of each type to make so as to maximize
profits.
a. What is the objective function for this LP problem?
b. What are the constraints involving x1, assuming that x1 corresponds to 50-inch TV sets?
c. What is the optimal solution point for this problem?
d. What is the optimal value of the objective function?
35. A small lumber company produces two types of pine boards used in home construction:
2x4s and 2x6s (dimensions in inches). It is attempting to determine how many of each to pro-
duce so as to minimize its costs on a per-minute basis. It has sales commitments to produce
OM5 Test Bank Supplementary Chapter C 9
four 2x4s and two 2x6s per minute, but the management thinks they should not produce any
more than eight 2x6s because of market demand. The company is also trying to support the
community by employing people. Thus, it wants to keep at least 12 men employed, but only
needs 2 men to produce each 2x4 and 1 person to produce each 2×6 per minute. It costs the
company $.50 to produce a 2×4 and $.80 to produce a 2×6 per minute.
a. What is the objective function for this LP problem?
b. What is the constraint for the employment issue, assuming x1 corresponds to 2x4s?
c. What is the optimal solution point for this problem?
d. What is the optimal value of the objective function?
36. The Alpha Beta Corporation makes laser and inkjet printers for personal computers. Each
laser printer yields $40.00 in profits and each ink jet printer provides $20.00. Each of the print-
ers goes through two assembly areas. The following table provides processing times per unit (in
minutes) as well as total available processing times per department:
Printer
Dept. A
Dept. B
Laser
9
12
Inkjet
6
8
Total time per day
216
384
Sales commitments require at least 5 laser printers and 10 inkjet printers to be made per day.
The company is interested in determining how many of each printer to produce so as to max-
imize its profit.
a. What is the objective function for this LP problem?
b. What are the constraints corresponding to Dept. A if x1 corresponds to laser printers?
c. What are the optimal solution points for this problem?
d. What is the optimal value of the objective function?
37. A food processing company makes meatloaf to be sold in the frozen food section of super-
markets.
Each week, the recipe used changes based on the current cost of ingredients. Ingredients and
current costs are as shown below:
Ingredient
Cost/pound
pork
$2.87
hamburger
$1.63
wheat filler
$0.22
corn filler
$0.16
For each batch made, at least 300 pounds of pork and 100 pounds of hamburger are required.
No more than 200 pounds of wheat filler can be used per batch, and the amount of corn filler
has to range between 50 and 150 pounds. Moreover, each batch must contain at least 500
pounds of meat and no more than 200 pounds of filler.
a. What is the objective function if the company seeks to minimize costs?
b. If x1 is the amount of pork used, what are the constraints associated with it?
c. If x3 is the amount of wheat filler used, what are the constraints associated with it?
38. ABC Products Inc. produces three products (A, B, and C) on three machines. Machines 1 and
2 are available for 40 hours a week, and Machine 3 is available for 60 hours a week. Profit con-
tribution and standard production time in hours are given in the following table:
Product
A
B
C
Profit Contribution/Unit
$40
$60
$30
Machine #1 (time/unit)
0.6
2.2
1.8
Machine #2 (time/unit)
1.2
0.8
0.7
Machine #3 (time/unit)
2.4
2.8
2.0
Only one operator per machine is required on Machines #1 and #2. Two operators are required
for Machine #3. Therefore, two hours of labor must be scheduled for each hour of Machine
#3’s time. To restate this requirement, two operators must be scheduled for each hour of Ma-
chine #3’s operation, as well as one operator for each hour of Machine #1’s operation and one
operator for each hour of Machine #2’s operation. A total of 110 labor hours is available for
assignment to the three machines during the coming week. Other production requirements are
that Product A cannot account for more than 40% of the units produced and that Product C
must account for at least 25% of the units produced.
a. Develop the constraint for the capacity limit of Machine #1.
b. Develop the constraint for the capacity limit of Machine #3.
c. Develop the constraint for the labor capacity limit.
d. Develop the constraint for limiting Product A to no more than 40% of the units produced.
e. Develop the constraint that ensures Product C accounts for at least 25% of the units
produced.
OM5 Test Bank Supplementary Chapter C 12
39. A cement company has three factories that they identify as Alpha, Beta, and Gamma. They
supply cement to three warehouses referred to as X, Y, and Z. The company wants to deter-
mine how much cement should be shipped from each factory to each warehouse to minimize
shipping costs. The cost to ship each 100-pound bag, along with warehouse requirements and
factory capacities in bags are shown in the table below:
Warehouses
Factories
X
Y
Z
Capacities (bags)
Alpha
$.40
$.60
$.78
10,000
Beta
0.65
0.78
0.59
9,000
Gamma
0.56
0.61
0.71
7,000
Requirements (bags)
10,000
5,000
10,000
a. How many decision variables are there in this problem?
b. What is (are) the constraint(s) corresponding to factory Alpha?
c. How many constraints are required for this problem?
1. 40. Power Fuels Corporation is developing a new additive for rocket fuel. The additive is a
OM5 Test Bank Supplementary Chapter C 13
mixture of liquid ingredients A, B, and C. For proper performance, the total amount of ad-
ditive must be at least 18 ounces per gallon of fuel. For safety reasons, the total amount of
additive must not exceed 22 ounces per gallon. At least 2 ounces of A must be used for
every ounce of C. The amount of B must be greater than one-half the amount of A.
a. The cost per ounce for ingredients A, B, and C is $50, $40, and $70, respectively. What is the
objective function?
b. Develop the constraint for limiting the additives for safety reasons.
c. Develop the constraint for ensuring the performance requirement is met.
d. Develop the constraint for the relationship between Ingredient A and Ingredient C.
e. Develop the constraint that states the relationship between Ingredient B and Ingredient C.
41. A cargo airline company in South America ferries materials from four different airfields in
Brazil (called A, B, C, and D) to two different airfields in Peru (numbered 1 and 2). Distances in
hundreds of miles between the six different airfields are as shown below:
Brazil
Peru
A
B
C
D
1
2
6
17
5
2
12
8
12
9
Capacities
60
40
75
55
Requirements for airfield 1 are 140 tons per year and 80 tons per year for airfield 2. The presi-
dent of the airlines wants to determine how much material should be shipped from each air-
field in Brazil to each airfield in Peru so as to minimize total travel distance.
a. How many decision variables are there in this problem?
b. What is the constraint corresponding to airfield 1?
c. What is the constraint corresponding to airfield B?
OM5 Test Bank Supplementary Chapter C 14
42. A computer manufacturing company wants to develop a monthly plan for shipping finished
products from three of its manufacturing facilities to three regional warehouses. It is thinking
about using a transportation LP formulation to exactly matched capacities and requirements.
Data on transportation costs (in dollars per unit), capacities, and requirements are given below:
Plant
Plant
Plant
Warehouse
1
2
3
Requirements
X
2.41
1.63
2.09
8,000
Y
3.18
5.62
1.74
2,000
Z
4.12
3.16
3.09
3,000
Capacities
4,000
6,000
3,000
a. How many variables are involved in the LP formulation?
b. How many constraints are there in this problem?
c. What is the constraint corresponding to plant 2?
43. A clothing distributor has four warehouses that serve four large cities. Each warehouse has
a monthly capacity of 5,000 blue jeans. They are considering using a transportation LP ap-
proach to match demand and capacity. The following table provides data on their shipping
cost, capacity, and demand constraints on a per-month basis:
Warehouse
City E
City F
City G
City H
OM5 Test Bank Supplementary Chapter C 15
A
0.53
0.21
0.52
0.41
B
0.31
0.38
0.41
0.29
C
0.56
0.32
0.54
0.33
D
0.42
0.55
0.34
0.52
City demand
2,000
3,000
3,500
5,500
a. How many variables are there in this formulation?
b. How many constraints are involved in this problem?
c. What is the constraint corresponding to City F?
44. Given the partial project network below and the fact that F can be crashed three times if xt
= start
time of Activity i, and yi = amount of crash time used for Activity i.
a. Which of the following is correct? xF xD + 10 − yD or xF xE + 10 + yE or yD, yE 0 or xF −
xD − xE + 10 3
b. Which of the following is correct? yD 3 or yE 3 or yF = yD + yE or yF 3