DSC2606/204/1/2016
Tutorial Letter 204/1/2016 Nonlinear mathematical programming
DSC2606 Semester 2 Department of Decision Sciences Solutions: Assignment 04 This tutorial letter contains solutions to the questions in Assignment 04.
Bar code
Learn without limits.
university of south africa
DSC2606/204/1
2
Dear Student Here are the solutions to the fourth compulsory assignment. You are welcome to contact your lecturer if you have any queries. The relevant information is available on the module’s myUnisa page.
3
DSC2606/204/1
Solutions: Assignment 04 First semester Answer to question 1 The formula for compound interest is as follows: A = P (1 + r)t
and
I =A−P
where A is the amount which accrues when an initial principal of P is invested at interest rate r per term for t terms, and where I is the compound interest. (a) For which value(s) of t is A a linear function of r? Answer: If t = 1, then A = P (1 + r), which is a linear function of r. (b) For which value(s) of t is A a nonlinear function of r? Answer: A = P (1 + r)t is a nonlinear function of r for 0 < t < 1 and t > 1, that is, if t 6= 1. (c) Determine dA/dr. Answer: dA = tP (1 + r)t−1 dr (d) Derive an expression for t in terms of A, P and r. Answer: Derive an expression for t from A = P (1 + r)t : (1 + r)t =
A P
Take natural logarithm both sides: A ln(1 + r) = ln P t
But ln(1 + r)t = t ln(1 + r) Therefore A ln P t= ln(1 + r) (e) At what interest rate per annum must money be invested if the accrued principal must treble in ten years?
4
DSC2606/204/1
Answer: Now t = 10 and
A P
= 3. A ln ln 3 P = = 0,10986 = K ln(1 + r) = t 10
Therefore r = eK − 1 = 0,116 The accrued principal will treble in ten years at an interest rate of 11,6% per annum.
Answer to question 2 The total cost T (n) (in rand) of ordering, purchasing, and storing inventory for a year is given by the cost equation 480 000 T (n) = + 12n + 146 400 n where n is the order quantity per order. (a) Prove that the function T (n) is convex over the interval (0; ∞). Answer: The total cost function is T (n) =
480 000 + 12n + 146 400 = 480 000n−1 + 12n + 146 400. n T ′ (n) = −480 000n−2 + 12. T ′′ (n) = 960 000n−3 > 0 because n > 0.
Therefore T (n) is convex over the interval (0; ∞). (b) Determine the optimal order quantity. (Which n minimises T (n)?)
Answer: The optimal order quantity n is where T ′ (n) = 0. T ′ (n) = −480 000n−2 + 12 = 0 ⇒ n2 = 40 000 ⇒ n = 200 because n ≥ 0.
5
DSC2606/204/1
Answer to question 3 Determine the optimal solution to the following nonlinear programming (NLP) problem: Maximise f (x) = 1 − e−x subject to 1 ≤ x ≤ 3. Show your reasoning. Answer: f (x) = 1 − e−x (a) f ′ (x) = −e−x .(−1) = e−x > 0 for all x. There is no solution to f ′ (x) = 0; so no stationary points or relative extreme points within the feasible region. The function f (x) is increasing. (b) f ′′ (x) = e−x .(−1) = −e−x < 0 for all x. The function f (x) is concave. The maximum must therefore be on the boundary of the feasible region 1 ≤ x ≤ 3, i.e. either at x = 1 or at x = 3.
Answer to question 4 Consider the cubic function f (x) = x3 − 9x2 + 15x + 74. (a) Determine the stationary points of the function f (x) and prove their nature (relative minimum or maximum) by applying the second derivative test.
Answer: f (x) = x3 − 9x2 + 15x + 74 The first and second derivatives are f ′ (x) = 3x2 − 18x + 15
f ′′ (x) = 6x − 18.
Stationary points are where f ′ (x) = 0: 3x2 − 18x + 15 = 0 3(x2 − 6x + 5) = 0
3(x − 1)(x − 5) = 0
x = 1 and x = 5.
6
DSC2606/204/1
Second derivative test: Evaluate f ′′ (x) at the stationary points: f ′′ (1) = 6(1) − 18 = −12 < 0 ⇒ relative maximum
f ′′ (5) = 6(5) − 18 = +12 > 0 ⇒ relative minimum. The corresponding f (x) values at the stationary points are
f (1) = 81 f (5) = 49.
The point (1; 81) is a relative maximum and the point (5; 49) is a relative minimum of f (x). (b) Determine the inflection point(s) of the function f (x). Answer: Inflection point(s) are where f ′′ (x) = 0: f ′′ (x) = 6x − 18 = 0
⇒ inflection point at x = 3
As f (3) = 65, the inflection point is (3; 65). (c) Determine the interval(s) where the function f (x) is 1. decreasing. 2. convex. Answer: f (x) is 1. decreasing on the interval (1; 5). 2. convex on the interval (3; ∞). (d) Calculate f (−1) en f (−3). From this, derive a meaningful starting interval for applying the bisection algorithm in determining a real root of the equation f (x) = 0. Answer: Calculate function values: 1. f (−1) = (−1)3 − 9(−1)2 + 15(−1) + 74 = −1 − 9 − 15 + 74 = 49 2. f (−3) = (−3)3 − 9(−3)2 + 15(−3) + 74 = −27 − 81 − 45 + 74 = −79 Because f (−1) > 0 and f (−3) < 0, a meaningful starting interval for the bisection algorithm is [−1; −3].
7
DSC2606/204/1
Answer to question 5 ; 1) on the Euclidean plane Find the point on the parabola y = 21 x2 that is closest to the point ( 27 2 (x; y). Answer: Minimise squared distance between the point ( 27 ; 1) and the point (x; y) on the parabola y = 12 x2 2 NLP formulation − x)2 + ( 21 − y)2 subject to y = 12 x2 . Minimise ( 27 2 Substitute for y = 21 x2 in the objective function. 1 27 f (x) = ( − x)2 + (1 − x2 )2 = 2 2
27 2
2
1 272 1 +1 − 27x + x2 + 1 − x2 + x4 = x4 − 27x + 4 4 4
Stationary points where f ′ (x) = x3 − 27 = 0. ⇒ x3 = 27 ⇒x=3 and y=
9 2
Second derivative test: Examine the sign of f ′′ (x) = 3x2 at the stationary point x = 3: f ′′ (3) = 3(3)2 = 27 > 0
⇒ relative minimum at x = 3.
The squared distance is minimised when x = 3 and y = 29 .
Answer to question 6 The trapezoidal rule is given by Z
b a
n−1
X h f (x) dx ≈ [f (a) + f (b)] + h f (xi ), 2 i=1
where the interval [a; b] is divided into n subintervals [xi ; xi+1 ] of width h = (b − a)/n, with x0 = a and xn = b.
8
DSC2606/204/1
(a) Estimate the area under the curve f (x) =
√
3x + 1
on the interval [1; 5] to three decimal places, by applying the trapezoidal rule with n = 2 intervals. (b) By how much does the estimate differ from the actual area? Answer: (a) Trapezoidal rule on f (x) = b = x2 = 5 =2 h = 5−1 2
√
3x + 1 over [1; 5]: a = x0 = 1
i xi 3xi + 1 f (xi ) 0 1,0 4,00
2,00
1 3,0 10,00
3,1623
2 5,0 16,00
4,00
Then Z
5
√
2 [f (1) + f (5)] + (2)[f (3)] 2 = 2,00 + 4,00 + 2 × 3,1623
3x + 1 dx =
1
≈ 12,325
(b) Apply fundamental theorem of calculus to determine the actual area under the curve.
Z
1
5
Z
5
√
Z
5
(3x + 1)1/2 dx 3x + 1 dx = 1 1 5 1 2 = (3x + 1)3/2 3 3 1 2 2 2 (3(5) + 1)3/2 − (3(1) + 1)3/2 = 163/2 − 43/2 = (43 − 23 ) = 9 9 9 2 2 = (64 − 8) = (56) = 12,444 9 9
f (x) dx =
The error is 12,444 − 12,325 = 0,12.
9
DSC2606/204/1
Answer to question 7 Consider the following nonlinear programming (NLP) problem: Minimise
f (x; y) =
50 20 + + xy x y
subject to x ≥ 3; y ≥ 2. (a) Calculate the objective function value for the point (10; 10). Answer: Objective function value for the point (10; 10): f (10; 10) =
50 20 + + (10)(10) = 5 + 2 + 100 = 107 10 10
(b) Is the point (1; 1) a feasible solution to the NLP problem? Substantiate your answer. Answer: No, the point (1; 1) is NOT a feasible solution, because both the constraints are violated: x = 1 < 3 and y = 1 < 2 (c) The Kuhn-Tucker necessary conditions for this NLP problem are as follows: −50x−2 + y − λ1 = 0
(1)
−20y −2 + x − λ2 = 0
(2)
λ1 (−3 − x) = 0
(3)
λ2 (−2 − y) = 0
(4)
λ1 , λ2 ≥ 0.
(5)
Verify whether the point (5; 2) satisfies (a) the Kuhn-Tucker necessary conditions. Answer: From (3), x = 5 ⇒ λ1 = 0 From (4), y = 2
⇒ λ2 ≥ 0
Into (1): λ1 = 2 −
50 52
=0
Into (2): λ2 = 5 −
20 22
=0
Yes, the point (5; 2) satisfies the Kuhn-Tucker necessary conditions. (b) the Kuhn-Tucker sufficient conditions. Answer: The second-order partial derivatives are ∂2f −3 2 (x; y) = 100x ∂x
∂2f (x; y) = 1 ∂y∂x
∂2f (x; y) = 1 ∂x∂y
∂2f −3 2 (x; y) = 40y . ∂y
10
DSC2606/204/1
The Hessian matrix is H(x; y) =
"
100x−3
1
1
40y −3
#
=
"
100(5)−3
1
1
40(2)−3
#
=
"
4 5
1
15
#
.
The first principal minors are both positive. The second principal minor is 54 × 5 − 1 = 3, which is also positive. Hence all principal minors are nonnegative and hence f (x; y) is a convex function. Therefore the point (x; y) = (5; 2) satisfies the Kuhn-Tucker sufficient conditions. (d) What conclusion about optimality can you draw from this? Answer: Conclusion: The point (5; 2) is the optimal solution. The maximum objective function value is f (5; 2) =
50 20 + + (5)(2) = 30. 5 2
Answer to question 8 Use the method of Lagrange multipliers to solve the following nonlinear programming (NLP) problem: Minimise f (x; y) = 2x2 + 3y 2 + x − 9y + 16 subject to x + y = 5.
Answer: The Lagrangian is L(x; y; λ) = 2x2 + 3y 2 + x − 9y + 16 + λ(5 − x − y). To determine the stationary points of L, set Then
∂L ∂L ∂L = = = 0. ∂x ∂y ∂λ
∂L = 4x + 1 − λ = 0 ∂x
⇒x=
λ−1 4
(1)
∂L = 6y − 9 − λ = 0 ∂y
⇒y=
λ+9 6
(2)
∂L =5−x−y = 0 ∂λ
⇒ x + y = 5.
(3)
11
DSC2606/204/1
Substitute (1) and (2) into (3), then λ−1 λ+9 + = 5 4 6 3λ − 3 + 2λ + 18 = 60 5λ = 45
λ = 9. Now x =
9−1 4
= 2 and y =
9+9 6
= 3.
The point (x; y; λ) = (2; 3; 9) is a stationary point of L. The function value is f (2; 3) = 2(2)2 + 3(3)2 + 2 − 9(3) + 16 = 26. We must also prove that (x; y) = (2; 3) is indeed the optimal solution. To do this, we must firstly determine the convexity/concavity of the objective function f (x; y) = 2x2 + 3y 2 + x − 9y + 16. The second-order partial derivatives are ∂2f = 4; ∂x2
∂2f = 0; ∂y∂x
∂2f = 6; ∂y 2
∂2f = 0. ∂x∂y
The Hessian matrix is H(x; y) =
"
4 0 0 6
#
.
The first principal minors are 4 and 6; both positive. The second principal minor is 24, also positive. All the principal minors are > 0. Therefore, the function f (x; y) is a convex function. Also, the constraint x + y = 5 is linear. We can conclude that the point (x; y) = (2; 3), with f (x; y) = 26, is the optimal solution. c
UNISA 2016
