Management Chapter 2 Compared With Standard Linear Programming Algorithms

CHAPTER 2

INTRODUCTION TO MANAGEMENT SCIENCE MODELS

TRUE/FALSE QUESTIONS

1. Linear programming models are a subset of constrained

optimization models that require the assumptions of continuity of

the variables, certainty of the coefficients, additivity of terms,

and proportionality of costs, profits, and the use of resources to

2. When specifying linear constraints, the modeler must take into

account the unit specification of the decision variables so that the

units represented by the left side of the constraints are consistent

with the units represented by the right side of the constraints.

3. Minimization linear programming models may not involve “”

4. A linear programming problem with all “” functional

constraints and nonnegative right hand side values will never be

5. A non-binding constraint is always a redundant constraint.

6. If two extreme points are optimal, then so is every point on

7. “Range of optimality” describes the impact of simultaneous

changes in objective function values and right-hand-side values.

8. Linear programming and integer linear programming both yield a

9. Binary linear programming allows for the possibility of

10. Each decision variable must appear in at least two

12. The difference between a boundary point and an extreme point

13. An optimal solution must have no slack on at least one

14. One of the reasons we cannot use sensitivity analysis for an

integer linear program is that the shadow prices do not produce

linear effects. That is, although in a linear program the shadow

price for a resource represents the marginal improvement for each

added unit of that resource, in an integer linear program, we cannot

assume that each added unit of a resource will produce the same

15. The complementary slackness principle states that either there

MULTIPLE CHOICE QUESTIONS

1. Compared with standard linear programming algorithms, those

for treating integer linear programming problems usually are:

a. less complex due to fewer possible solutions.

b. less amenable to “what if” analysis.

c. always heuristic.

d. easier to formulate.

2. In the branch-and-bound technique for solving integer linear

programming models with a maximization objective function:

a. Once a feasible solution is found, it is optimal.

b. If the solution generated at one stage is X1 = 5.7, X2 = 3

but gives an objective function value higher than that

of the best integer solution found to date, X2 must be

either 0, 1, or 2 in the optimal solution.

c. If the solution generated at one stage is X1 = 5.7, X2 = 3

but gives an objective function value higher than that

of the best integer solution found to date, a new linear

programming problem is solved with two constraints

added: X1  6 and X1  5.

d. If the solution generated at one stage is X1 = 5.7, X2 = 3

but gives an objective function value higher than that

of the best integer solution found to date, two new

linear programs are solved, one with the constraint

X1  6 added, the other with the constraint X1  5 added.

3. In solving an integer linear programming problem, lifting the

integer requirements and first solving the underlying standard

linear programming problem:

a. never yields an optimal solution.

b. is not part of the branch-and-bound technique.

c. is not part of the cutting plane technique.

d. may yield an integer-valued solution.

4. When compared with standard linear programming, integer linear

programming typically has:

a. more feasible solution points to evaluate.

b. fewer feasible solution points to evaluate.

c. the same number of feasible solution points to evaluate.

d. more linear constraints.

5. Which of the following is not a necessary linear programming

assumption?

a. The decision variable values are discrete.

b. The parameters are specified with certainty.

c. Constant returns to scale in the linear constraints and

the object function coefficients.

d. No interactions permitted between decision variables.

6. The feasible region does not include:

a. interior points.

b. boundary points.

c. points at which at least one of the decision variables

is zero.

d. points which violate at least one of the functional or

non-negativity constraints.

7. A “non–binding” constraint is:

a. redundant.

b. not satisfied with an equality at the optimal solution.

c. one having zero slack or surplus

d. never a non-negativity variable constraint.

8. In a model with two decision variables, the restriction

3X1 + 2X2  6 represents:

a. a straight line.

b. the region of infeasibility.

c. an extreme point.

d. a linear constraint.

9. The effect of deleting a linear constraint from a linear

programming model depends on whether or not that constraint:

a. is a “” or a “” constraint.

b. had negative coefficients.

c. is redundant.

d. is binding.

10. An over-constrained linear programming problem results in what

type of solution?

a. Unbounded.

b. Degenerate.

c. Infeasible.

d. Sub-optimal.

11. The functional constraints of a linear model with nonnegative

variables are 3X1 + 5X2  16 and 4X1 + X2  10. Which of the

following points could not be an optimal solution for the model?

a. X1 = 2.5, X2 = 0

b. X1 = 0, X2 = 3.2

c. X1 = 1, X2 = 2.25

d. X1 = 2, X2 = 2

12. Which statement is not true if a maximization problem has an

unbounded solution?

a. A data entry error has been made or a limiting

constraint has been omitted.

b. The objective function value goes to +.

c. The values of all decision variables go to +.

d. The feasible region is unbounded.

13. Squire Leathers produces two sizes of wallets from cowhide.

The first requires 60 squire inches of cowhide and the second

requires 100 square inches. The company has 1000 square feet of

cowhide. Part of the model is:

a. 60X1 + 100X2  144,000

b. 60X1 + 100X2  144,000

c. 60X1 + 100X2 = 144,000

d. 60X1  144,000 and 100X2  144,000

14. Banner Tools produces two styles of steel hammers with wooden

handles. The first sells for $6 and consists of .5 pounds of steel;

the second sells for $15 and consists of 1 pound of steel. Since

steel costs the firm $4 per pound and the handle, labor, and

packaging costs amount to $1 for either hammer, the profits

coefficients are $6 – .5($4) – $1 = $3 for the smaller hammer and

$15 – 1($4) – $1 = $10 for the larger hammer. Thus the objective

function for this model is MAX 3X1 + 10X2. Given that the shadow

price for steel is $2, which of the following statements is correct?

a. Banner should not buy more steel.

b. Banner should buy all the steel it can only if it can

purchase it for less than $2 per pound.

c. Banner should buy at least as much as the “ALLOWABLE

INCREASE”, but only if it can be purchased for less than

$2 per pound.

d. Banner should buy at least as much as the “ALLOWABLE

INCREASE”, but only if it can be purchase for less than

$6 per pound.

15. The principle of “complementary slackness” implies that:

a. if the reduced cost is not zero, than the value of the

decision variable is zero.

b. if a decision variable is zero, then its reduced cost

must be positive.

c. if a decision variable is zero, then its reduced cost

must be non-zero.

d. if a decision variable is zero, then its reduced cost

must be zero.

16. The objective function coefficients for X1, X2, and X3 are 15,

32, and 48 respectively. Excel prints that their ranges of

optimality are from 10 to 20, from 30 to 40, and from – to 50

respectively. If the objective function coefficients are changed to

14, 31, and 45, the optimal solution:

a. will not change.

b. may not change.

c. will definitely change.

d. may change.

17. Excel Solver reports “Solver could not find a feasible

solution.” What is your best logical alternative?

a. Change the objective function.

b. Run Excel Solver again.

c. Relax a constraint.

d. Add a constraint.

18. Dean Air uses a linear programming model to schedule flights,

assign crews and meet passenger demand. The objective function is

to minimize downtime. Constraints include a limit on pilot hours,

meeting passenger demand, and scheduled downtime. Which of the

following cannot be accomplished with sensitivity analysis?

a. Add a constraint of airport gate usage.

b. Change the objective to maximize profits.

c. Increase values for demand.

d. Drop the crew assignment constraint from the model.

19. If the points (5, 5, 5) and (7, 9, 5) are both optimal

solutions to a linear programming problem, what other point is also

optimal?

a. (6,7,8)

b. (6,7,5)

c. (7,5,5)

d. (5,9,5)

20. Which of the following constraints is redundant?

a. X1 + X2  10

b. X1 – X2  10

c. X1 + 3X2  20

d. X1, X2  0

SHORT ANSWER QUESTIONS

1. What is a linear programming model?

2. Define the additivity assumption.

3. Why would you not use linear programming to solve a problem

with a single decision variable linear objective function and

multiple constraints?

4. Compare the points that the Simplex method moves to with the

points touched by the graphical method for solving a two variable

linear program.

5. What is wrong with this linear programming model?

6. “Allowable Decrease” and “Allowable Increase” refer to what

range?

7. Explain the different interpretations of shadow costs when the

objective function is based on sunk costs versus included costs.

8. Explain the SUMPRODUCT function of Excel.

9. When running Excel, what does “The Set Cell values do not

converge” mean?

10. What clue does Excel give to the possible existence of

alternate optimal solutions?

11. What is the major difference between a product mix problem and

a diet problem?

12. How do you designate variables as integers when using Excel

Solver?

13. Ira Wax solved an integer linear programming problem by

setting up a linear programming model without the integer

constraints and rounding the solution. List the possible problems

with this approach.

FORMULATION/SOLUTION/ANALYSIS QUESTIONS

1. Office2000 produces expensive, quality 2-drawer and 4-drawer

filing cabinets from solid oak for major corporations. A 2-drawer

model utilizes 2 labor hours to produce and package for a net profit

of $75. The 4–drawer model utilizes 3 labor hours to produce and

package and nets a profit of $125. Each month Office2000 has 360

labor hours available and can obtain up to 200 2-drawer frames, 200

4-drawer frames, and 400 drawers from its oak supplier.

Formulate a linear programming model to maximize monthly profit from

the manufacture of filing cabinets at Office2000.

2. Jungle Figures, Inc. produces two models of its stuffed

giraffes, which it markets to high-end retail stores. The large

giraffe requires 2 pounds of stuffing material and 6 minutes of

machine time. The small giraffe requires 1 pound of stuffing

material and 12 minutes of machine time since its tighter stitching

pattern requires it to be stitched twice. There are 800 pounds of

3. Consider the following sensitivity report from Excel for the

model in question 3, which has a profit of $5,400.

4. The University of Iowa is experimenting with a blend of soil

amendments to be used in an analysis of variance study of the

response of tomatoes to various amounts of sunlight. To perform

14. A farmer has three possible cereal grain crops to grow in the

coming planting season: barley, oats, and wheat. He has 240 acres

of arable land: 160 are considered high grade and the remainder is

low grade. He has $42,000 in available capital and can hire

virtually unlimited hours of field labor, locally, for $6 per hour.

Relevant crop factors are:

15. The Hawaii Surfboard Company produces three different styles

of surfboards (the Oahu, the Kauai, and the Maui) made from

combinations of three different materials, A, B, and C. The Oahu

model nets a $35 profit and requires 1 unit of A, 1 unit of B, and 1

unit of C. The Kauai model nets a $75 profit and requires 4 units

of A and 1 unit of B. The Maui model nets a $100 profit and

requires 1 unit of A, 4 units of B, and 1 unit of C. There are 200

units of A, 200 units of B, and 100 units of C available weekly.

16. The Carolina Chemical Company (CCC) makes two products, soap

and shampoo, both in liquid form. The same two raw material inputs,

glycerin and potash, and the same production line are used in the

manufacture of each. Each production day, one ton of glycerin and

17. Spee-D Delivery Service wants to blend two gasolines (R and S)

for use in its trucks. For the upcoming period, at least 10,000

gallons are required. Spee-D has a 20,000 gallon storage facility.

Any required quantities of R and S gasoline may be purchased from a

local refinery and mixed.

R is 87 octane and costs $0.90 a gallon. S is 93 octane and costs

$1.20 per gallon. Spee-D’s fleet of 100 trucks requires an octane

of no less than 89. Octane of the mixed output is linearly

proportional to input octane. For example, equal parts of R and S

would yield a 90 octane output. There is no gasoline loss in the

blending process.

Formulate a linear programming model for this problem. Is a

summation variable advisable here? Explain.

18. A small foundry has received an order for an iron alloy called

Falloy which has the following specifications:

19. Extel Industries produces integrated circuit components for

use in the next generation of automobiles. In particular, it can

make the AT50 unit that can control the air temperature in the car,

the V35 unit that monitors vibration and makes adjustments

accordingly, and the GM30 that regulates the engine so that the car

provides maximum efficiency. The unit profits on these units are

$84, $112, and $126, respectively. Each of these units uses

different quantities of three computer chips (as shown below), which

Extel purchases from a Taiwanese distributor.

20. The Finast Filter Company makes two types of filters for

domestic air purifiers: the standard (nicknamed the Cleaner) for

ordinary use, and the Scrubber for industrial-strength problems.

The Cleaners bring in a profit of $0.50 each, while the Scrubbers

command a profit of $1.25 each.