Deck 13: Nonlinear Models:dynamic, Goal, and Nonlinear Programming

Question 1

While the optimal solution to a constrained nonlinear model need not occur at an extreme point, it must occur at a boundary point.

Answer 1

False

Question 2

One solution approach for solving a dynamic programming model is a backwards recursion approach.

Answer 2

True

Question 3

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.

Answer 3

it deals with multistage scenarios.

Question 4

In a convex programming problem, while the objective function can have any shape, the set of constraints must form a convex set.

Question 5

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.

Question 6

Simply put, Bellman's principle of optimality states that the
optimal path to the end of the process does not depend upon how the
current state was reached.

Question 7

Efficient solution procedures, guaranteed to provide optimal solutions, exist for convex programming and quadratic programming.

Question 8

In a dynamic program, the boundary conditions refer to the first stage, and the stopping rule refers to the last stage.

Question 9

LaGrange multipliers are like shadow prices in that they give the "instantaneous" change to the objective function value for changes to right hand side coefficients.

Question 10

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.

Question 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 function.

Question 12

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.

Question 13

The optimal solution for an unconstrained concave function occurs where the slope equals zero for all variables.

Question 14

A goal programming problem can be transformed into a series of linear programming problems, each of which has a different objective function and one more constraint than the previous one in the series.

Question 15

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.

Question 16

Altering the order of the stages of a dynamic program will produce a different result.

Question 17

Quadratic programming is a special case of __________ programming.

A)standard linear
B)general nonlinear
C)goal
D)dynamic

Question 18

In a mathematical model with two variables, a function which is both concave and convex is a straight line.

Question 19

A knapsack problem can be modeled as a longest path network problem.

Question 20

For a convex nonlinear programming problem, the Kuhn-Tucker
conditions are both necessary and sufficient.

Question 21

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?

Question 22

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.

Question 23

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.

Question 24

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.

Question 25

The optimal solution to a constrained nonlinear programming problem __________ occur at a boundary point.

A)must
B)cannot
C)need not
D)should not

Question 26

What differentiates preemptivefrom nonpreemptive goal
programming?

Question 27

What is "dynamic" about a dynamic programming problem?

Question 28

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.

Question 29

LaGrange multipliers are:

A)partial derivatives.
B)nonzero only for an optimal solution.
C)shadow prices.
D)used to verify feasibility.

Question 30

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.

Question 31

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.

Question 32

Under what conditions would you choose to use a standard linear programming technique for a nonlinear programming problem?

Question 33

In goal programming, the multiple objectives (goals) must be:

A)complementary.
B)conflicting.
C)preemptive.
D)prioritized.

Question 34

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.

Question 35

The fundamental approach to solving dynamic programming problems may be characterized as:

A)forward incursion.
B)backwards recursion.
C)total enumeration.
D)networking.

Question 36

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.

Question 37

The "knapsack problem" may be solved using a __________ programming technique.

A)dynamic
B)goal
C)quadratic
D)binary

Question 38

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.

Question 39

In goal programming, deviation variables, E₁ and U₁:

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.

Question 40

Briefly describe the concept of backwards recursion in the dynamic programming solution approach.

Question 41

For the problem faced by Kelso Construction in problem 4, how should the crews be allocated?

Question 42

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?

Question 43

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.

Question 44

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.

Question 45

How can you convert a dynamic program to a network model?

Question 46

Can a dynamic programming approach be used to solve a production/inventory problem possessing an infinite planning horizon?

Question 47

What are detrimental deviations?

Question 48

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. $\begin{array}{ll}\text { ROOM}&\text {PROJECT}&\text { COST}&\text { RETURN} \\\text { YARD}&\text { Seed lawn \& plant shrubs } & 2&2 \\&\text { Re-sod } & 5&8 \\&\text { Plant trees } & 15 &20\\\text { KITCHEH}&\text { Reface cabinets } & 10 &12\\&\text { New cabinets } & 25&40 \\&\text { Tile Floor } & 15&20 \\\text { BATHR00M}&\text { Refinish } & 5&10 \\&\text { Replace tile } & 10&18 \\&\text { New toilet, tub, \& plumbing } & 20&31\end{array}$
A.Define the stage variables.
B.Define the state variables.
C.Define the decision variables.
D.Define the stage return values.
E.Define the optimal value function.
F.Define the boundary condition.
G.Define the stopping rule.
H.Define the recurrence relation.
I.Solve the problem.

Question 49

How does the number of computations for a dynamic programming model compare to total enumeration?

Question 50

Consider the problem faced by Terrestrial Telescopes in problem 2.A.What is the optimal allocation of the weekly budget between salaries and equipment?
B.How many Orion telescopes can be made weekly?
C.What is the value (in terms of extra telescopes produce) of
(i) only raising the overall budget?
(ii) only raising the maximum allocation for machinery?
D.Other than solving the Kuhn-Tucker conditions by trial and error,
what is another solution approach for solving this model?

Question 51

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.

Question 52

Without writing equations, what are the basic components to the Kuhn-Tucker conditions for a maximization problem with "?" constraints?

Question 53

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, X₁, and to equipment, X₂.When X₁ and X₂ are expressed in $1,000's, an economic study has shown that the number of telescopes produced can be expressed as the concave function $$- 2 X _ { 1 } ^ { 2 } + 24 X _ { 1 } - 2 X _ { 2 } ^ { 2 } + 48 X _ { 2 } + 2 X _ { 1 } X _ { 2 }$$ .No more than $15,000 of its weekly budget will be spent on machines.
A.Formulate a nonlinear programming model to maximize the weekly
production of Orion telescopes.
B.Write the Kuhn Tucker conditions for this problem.Are they
necessary conditions for optimality? Sufficient?
(Since the objective function is concave and the constraints are
linear, this is a convex programming model.Thus the Kuhn-Tucker
conditions will be both necessary and sufficient.Using Y₁, Y₂, Y₃, and Y₄ to represent the shadow prices