CHAPTER 13
NONLINEAR MODELS:
DYNAMIC, GOAL, AND NONLINEAR PROGRAMMING
TRUE/FALSE QUESTIONS
1. Sootaway Chimney Cleaners has a preemptive goal programming
model for their three goals: reduce cost, reduce personnel, and
raise quality. If goal 2 has a higher priority than goal 3, it is
not possible for goal 3 to be met unless goal 2 has been met first.
2. One solution approach for solving a dynamic programming model
3. Simply put, Bellman’s principle of optimality states that the
optimal path to the end of the process does not depend upon how the
4. A knapsack problem can be modeled as a longest path network
5. A goal programming problem can be transformed into a series of
linear programming problems, each of which has a different objective
6. In a convex programming problem, while the objective function
can have any shape, the set of constraints must form a convex set.
7. In a mathematical model with two variables, a function which
8. For a convex nonlinear programming problem, the Kuhn-Tucker
9. LaGrange multipliers are like shadow prices in that they give
10. While the optimal solution to a constrained nonlinear model
need not occur at an extreme point, it must occur at a boundary
11. According to goal programming proponents, most business
problems have conflicting objectives and cannot be solved by
optimizing a linear programming model with a single objective
12. Efficient solution procedures, guaranteed to provide optimal
solutions, exist for convex programming and quadratic programming.
13. Altering the order of the stages of a dynamic program will
14. In a dynamic program, the boundary conditions refer to the
first stage, and the stopping rule refers to the last stage.
15. The optimal solution for an unconstrained concave function
MULTIPLE CHOICE QUESTIONS
1. Quadratic programming is a special case of __________
programming.
a. standard linear
b. general nonlinear
c. goal
d. dynamic
2. In applying Bellman’s principle of optimality for dynamic
programming using backwards recursion for a maximization problem, at
a given state within a given stage:
a. it does not matter how that state is reached.
b. that state was reached using an optimal set of decisions
from the first stage.
c. the shortest distance route to the next stage will be
selected.
d. the longest distance route to the next stage will be
selected.
3. Which of the following may be said to have no single form?
a. Standard linear programming.
b. Integer linear programming.
c. Binary linear programming.
d. Dynamic programming.
4. Variables raised to a power other than 1, may be found in a
nonlinear programming problem. Other nonlinearities include:
a. cross products, but not quotients.
b. quotients, but not cross products.
c. either cross products or quotients.
d. neither cross products nor quotients.
5. Dynamic programming is so named because:
a. optimal solutions derived change over time.
b. it deals with multistage scenarios.
c. its parameters are not constant.
d. it allows for a range of decisions.
6. Stages in a dynamic programming problem might represent any of
the following except:
a. system states.
b. time, in months.
c. projects.
d. “knapsack” items.
7. The fundamental approach to solving dynamic programming
problems may be characterized as:
a. forward incursion.
b. backwards recursion.
c. total enumeration.
d. networking.
8. The “knapsack problem” may be solved using a __________
programming technique.
a. dynamic
b. goal
c. quadratic
d. binary
9. Which of the following need not be part of a dynamic
programming model?
a. Linear constraints.
b. Boundary conditions.
c. A return function for each possible decision at each
stage.
d. An optimal value function.
10. In goal programming, the multiple objectives (goals) must be:
a. complementary.
b. conflicting.
c. preemptive.
d. prioritized.
11. Which of the following is true about the optimal solution to a
general nonlinear model?
a. All partial derivatives of the objective function must
equal 0.
b. It must occur at a boundary point.
c. All nonlinear constraints must be satisfied.
d. The LaGrange multipliers must all be 0.
12. In goal programming, the weights assigned to deviations from
goals:
a. must sum to 1.
b. may not be equal.
c. may be negative.
d. must all be nonnegative.
13. In goal programming, deviation variables, E1 and U1:
a. may appear in the objective function and several
constraints.
b. will appear in the objective function and exactly one
constraint.
c. must both be 0 in the optimal solution.
d. can both be positive in the optimal solution.
14. In a goal programming model in which goal 1 has a higher
priority than goal 2:
a. if goal 1 is not met, goal 2 will not be met.
b. if goal 2 is met, goal 1 will be met.
c. goal 2 may be met even if goal 1 is not.
d. goal 1 and goal 2 cannot both be met.
15. For general nonlinear programming problems, the Kuhn-Tucker
conditions:
a. will not be satisfied by a non-optimal solution.
b. must be satisfied by an optimal solution.
c. are satisfied only at boundary points.
d. are satisfied at extreme points and may be satisfied at
boundary points.
16. LaGrange multipliers are:
a. partial derivatives.
b. nonzero only for an optimal solution.
c. shadow prices.
d. used to verify feasibility.
17. The optimal solution to a constrained nonlinear programming
problem __________ occur at a boundary point.
a. must
b. cannot
c. need not
d. should not
18. How can we investigate minor changes to the parameters of a
dynamic programming problem?
a. Sensitivity analysis.
b. Trial and error.
c. Kuhn-Tucker equations.
d. Review the output from the intermediate stages.
19. The objective of goal programming is a solution that:
a. meets the highest priority goal and satisfies all
constraints.
b. satisfies all constraints and comes closest to meeting
the goals.
c. meets the goals and minimizes constraint violation.
d. satisfies constraints as modified by the detrimental
deviations.
20. Which of the following is not a true description of concave
functions?
a. No sharp points or discontinuities.
b. A single peak.
c. A line between two points on the curve will lie on or
below the curve.
d. Nonlinear.
SHORT ANSWER QUESTIONS
1. What is “dynamic” about a dynamic programming problem?
2. What differentiates preemptive from nonpreemptive goal
programming?
3. Under what conditions would you choose to use a standard
linear programming technique for a nonlinear programming problem?
4. Briefly describe the concept of backwards recursion in the
dynamic programming solution approach.
5. If, in a nonlinear programming model classified as convex, the
goal is to maximize a concave objective function, why is it referred
to as a convex problem? What would happen if the objective function
were convex?
6. Can a dynamic programming approach be used to solve a
production/inventory problem possessing an infinite planning
horizon?
7. Without writing equations, what are the basic components to
the Kuhn-Tucker conditions for a maximization problem with “≤”
constraints?
8. How does the number of computations for a dynamic programming
model compare to total enumeration?
9. How can you convert a dynamic program to a network model?
10. What are detrimental deviations?
FORMULATION/SOLUTION/ANALYSIS QUESTIONS
1. A college student has five full days until his next, and last,
final exam. While he feels the need to study heavily for the test,
he also needs to put in time on his job to pay living expenses.
His job pays $6.25 per hour, and daily he can work as many or as few
hours as he wishes. He figures that each hour he spends studying,
daily, will contribute 10 points to his final exam score. To
maintain his scholarship, he must achieve at least an 85 on the
exam. (Of course, he must score at least 50 to avoid failing the
course.) Also, to stay abreast of his bills, he would like to earn
$50 daily. A quick calculation verifies that he will need 16.5 hours
a day to meet both objectives. Failing the course is to be avoided,
at all costs. However, he believes he can devote only 14 hours daily
to the two endeavors.
A. Formulate this as a goal programming problem, where achieving
an 85 exam score is twice as important as earning $50 daily.
B. What should the student do?
2. Terrestrial Telescope manufactures the Orion telescope at its
Ohio plant. It has been determined that the number of telescopes it
can make weekly is a function of the amount of its $20,000 weekly
budget allocated to salaries, X1, and to equipment, X2. When X1 and
X2 are expressed in $1,000’s, an economic study has shown that the
number of telescopes produced can be expressed as the concave
function
212
2
21
2
12482242XXXXXX ++−+−
212
2
21
2
12482242XXXXXX ++−+−
. No more than
$15,000 of its weekly budget will be spent on machines.
A. Formulate a nonlinear programming model to maximize the weekly
B. Write the Kuhn Tucker conditions for this problem. Are they
necessary conditions for optimality? Sufficient?
3. Consider the problem faced by Terrestrial Telescopes in
problem 2.
A. What is the optimal allocation of the weekly budget between
C. What is the value (in terms of extra telescopes produce) of
$1000 of total extra budget. (ii) No value.) (medium)
D. Other than solving the Kuhn-Tucker conditions by trial and error,
what is another solution approach for solving this model?
4. Kelso Construction has three projects and 6 total work crews
it can assign to these projects. While each project requires the use
of at least one crew, the number of days required to complete each
project will vary with the number of crews assigned to it as given
in the following table.
Crews assigned Project 1 Project 2 Project 3
1 31 38 40
2 25 30 32
3 20 22 25
4 15 15 17
Formulate a dynamic programming model for minimizing the total
completion time of the projects by giving the boundary conditions,
the optimal value function and the recursion relation, and the
stopping rule.
5. For the problem faced by Kelso Construction in problem 4, how
should the crews be allocated?
6. A scout leader wants to fill one knapsack with at most 20
pounds (= 320 ounces) of food packets that will yield the highest
total of protein. The prepackaged food packets come with various
amounts of jerky, vegetable chips, and cookies. The weights of each
packet and their protein value are given below:
A. What are two methods that could be used to solved the scout
leader’s problem.
B. How should the leader fill his knapsack?
C. Suppose the knapsack could only hold 319 ounces. Why do you know
7. As part of its Welfare to Work program, the Georgia
legislature has allocated $28,800,000 to a new program designed to
get skilled and unskilled workers off welfare. Unskilled workers
would be paid $7.20 per hour whereas skilled workers would be paid
$12.00 per hour under this program. The goals of the program are:
(1) to generate at least 2,000,000 man-hours of work;
(2) having at least as many skilled hours as unskilled hours; and,
(3) utilize no more than 800,000 skilled hours (beyond that it will
be “make work”.)
A. Formulate this problem as a preemptive goal programming model.
B. What is the optimal allocation of hours for this situation.
8. Consider the Welfare to Work program in problem 8. Suppose now
that a nonpreemptive approach is used in which each hour under
2,000,000 is considered 5 times worse than each unskilled hour that
exceeds the skilled hours, which in turn is 2 times worse than each
skilled hour above 800,000.
A. Formulate this problem as a nonpreemptive goal programming model.
B. What is the optimal allocation of hours for this situation.
(1,000,000 unskilled hours, 1,000,000 skilled hours.) (medium)
9. It costs Extel $25 per chip to make its E86 chip used in
notebook and other personal computers. Extel can sell all the chips
it manufactures using a unit pricing model of ($60 – $0.01X) where X
is the daily production of the chip. Fixed daily production costs
are $700.
A. Formulate an unconstrained nonlinear model that models Extel’s
daily profit for its E86 chip.
B. What should be Extel’s daily production of the chip, its price,
and the daily profit from producing the chip?
C. Suppose its capacity to make chips is limited to 2000 per day.
What should be Extel’s daily production of the chip, its price, and
the daily profit from producing the chip?
D. Suppose its capacity to make chips is limited to 1500 per day.
What should be Extel’s daily production of the chip, its price, and
the daily profit from producing the chip?
E. Write the Kuhn-Tucker conditions for the model for part D, and
show that your solution satisfies these conditions.
(The model is:
10. Fred Salter has a budget of $40,000 to prepare his house for
sale. Fred’s yard needs work, and the kitchen and bathroom could
both use improvement. Fred has estimated the costs and expected
return (increase in the value of his house) of different options.
The cost and return are expressed in thousands of dollars. Fred
wants to use dynamic programming to solve the problem.
ROOM
COST
RETURN
YARD
2
2
5
8
15
20
KITCHEN
10
12
25
40
15
20
BATHROOM
5
10
10
18
20
31