|
Chapter 6 | 
|
MULTIDIMENSIONAL SEARCH
Problems 6.1 to 6.10 | Problems 6.11 to 6.20 | Problems 6.21 to 6.25
problem6.21 | problem6.22 | problem6.23 | problem6.24 | problem6.25
6-21. Solve the following problem by quadratic programming.
minimize: 2x12 + 2x1x2 + x22 - 20x1 - 14x2
subject to: x1 + 3x2 < 5
2x1 - x2 < 4
Solution:
To solve the quadratic programming problem, the standard format is:
maximize: 20x1 + 14x2 - ½(4x12 + 2x1x2 + 2x2x1 + 2x22)
subject to: x1 + 3x2 < 5
2x1 - x2 < 4
The values of the coefficients for the linear programming problem are:
c1 = 20 q11 = 4 q21 = 2 a11 = 1 a12 = 3 b1 = 5
c2 = 14 q12 = 2 q22 = 2 a21 = 2 a22 = -1 b2 = 4
The linear programming problem formed from the above is:
minimize: z1 + z2
subject to: 4x1 + 2x2 + l1 + 2l2 - s1 + 20z1 = 20
2x1 + 2x2 + 3l1 - l2 - s2 + 14z2 = 14
x1 + 3x2 + x3 = 5
2x1 - x2 + x4 = 4
Eliminating z1 and z2 from the objective function and solving by the Simplex Method gives:
-0.341x1 - 0.243x2 - 0.264l1 - 0.171 l2 + 0.055s1 + 0.071s2 = P-2
0.20x1 + 0.10 x2 + 0.05 l1 + 0.1 l2 - 0.05 s1 + z1 = 1
0.143x1 + 0.143x2 + 0.214l1 + 0.071l2 - 0.071 s1 + z2 = 1
x1 + 3x2 + x3 = 5
2x1 - x2 + x4 = 4
________________________________________________________________________
x1 enters the basis, and x4 leaves the basis
- 0.414x2 + 0.171x4 - 0.264l1 - 0.029 l2 + 0.05s1 + 0.071s2 = P - 1.314
0.20 x2 - 0.10 x4 + 0.05 l1 + 0.10 l2 - 0.05s1 + z1 = 0.6
0.214x2 - 0.071 x4 + 0.214l1 + 0.071l2 - 0.071s2 + z2 = 0.714
3.50 x2 + x3 - 0.5 x4 = 3
x1 - 0.5 x2 + 0.5 x4 = 2
________________________________________________________________________
x2 enters the basis and x3 leaves the basis
0.0118x3 + 0.112x4 - 0.264l1 - 0.029l2 + 0.05s1 + 0.017s2 = P-0.959
- 0.057x3 - 0.071x4 + 0.05 l1 + 0.10 l2 - 0.05s1 + z1 = 0.429
- 0.061x3 - 0.041x4 + 0.214l1 + 0.071l2 - 0.071s2 + z2 = 0.531
x2 + 0.286x3 - 0.143x4 = 0.857
x1 + 0.143x3 + 0.429x4 = 2.429
________________________________________________________________________
l1 enters the basis and z2 leaves the basis
0.043x3 + 0.062x4 - 0.117l2 + 0.05s1 - 0.017s2 + 1.23 z2 = P - 0.305
- 0.043x3 + 0.062x4 + 0.117l2 - 0.05s1 + 0.017s2 + z1 - 0.233z2 = 0.305
- 0.286x3 - 0.190x4 + l1 + 0.333l2 - 0.333s2 + 4.67 z2 = 2.48
x2 + 0.286x3 - 0.143x4 = 0.857
x1 + 0.143x3 + 0.429x4 = 2.43
________________________________________________________________________
l2 enters the basis and z1 leaves the basis
z1 + z2 = P-0
- 0.367x3 - 0.531x4 + l2 - 0.429s1 + 0.143s2 + 0.857z1 - 2z2 = 2.61
- 0.408x3 - 0.367x4 + l1 - 0.143s1 - 0.286s2 + 2.857z1 + 4z2 = 3.35
x2 + 0.286x3 - 0.143x4 = 0.857
x1 + 0.143x3 + 0.429x4 = 2.43
________________________________________________________________________
The coefficients of the variables in the objective function are positive and the optimum has been reached. The optimum solution is:
x1 = 2.43 x2 = 0.857 l1 = 3.35 l2 = 2.61 y = -43.9
The solution by the method of Lagrange multipliers from Problem 2-8 is:
x1 = 17/7 x2 = 6/7 l1 = 164/49 l2 = 128/49 y = -43.9
which agrees with these results.
6-22. Solve the following problem by the generalized reduced gradient method starting at the feasible point xo(1,1,19) to find the optimum located at x*(4,3,0). Use the optimum point to determine the appropriate value of the parameter of the reduced gradient line for one line search to arrive at the optimum.
maximize: 3x12 + 2x22 - x3
subject to: x12 + x22 - 25 = 0
9x1 - x22 + x3 - 27 = 0
Solution:
Select x1 as the nonbasic variable, and x2 and x3 as basic variables.
Computing partial derivatives gives:
¶y/¶x1 = 6x1 ¶y/¶x2 = 4x2 ¶y/¶x3 = -1
¶f1/¶x1 = 2x1 ¶f1/¶x2 = 2x2 ¶f1/¶x3 = 0
¶f2/¶x1 = 9 ¶f2/¶x2 = -2x2 ¶f2/¶x3 = 1
The reduced gradient is
ÑTY(xnb) = ÑTy(xnb) - ÑTy(xb) B-1b Bnb
Inverse of B-1b is computed using the cofactor method.
The reduced gradient is:
= 6x1 - (2x1 - 9) = 4x1 + 9
The reduced gradient line from x10 is:
x1 = x10 + a ¶Y(xo)/¶x1
x1 = x10 + a (4x1 + 9)
Starting at feasible point xo (1,1,19) gives:
x1 = 1 + a(4 + 9)
x1 = 1 + 13a
Since the optimum is known at x* = (4,3,0), a line search is not required if x1 = 4 is used to calculate in the above equation. This gives a = 3/13. Then the constraints can be used to compute x2 and x3 as:
(4)2 + x22 - 25 = 0
9(4) - x22 + x3 - 27 = 0
x2 = 3, x3 = 0
The optimal solution is x* = (4,3,0) with y(x*) = 66.
6-23(11). Solve the following problem by the generalized reduced gradient method. Start at the point xo = (2,1,3,1) and have x1 and x4 be the basic or dependent variables and x2 and x3 the nonbasic or independent variables.
minimize: x12 + 4x22
subject to: x1 + 2x2 - x3 = 1
-x1 + x2 + x4 = 0
Solution:
The following partial derivatives are needed for the reduced gradient, equation (6-57).
¶y/¶x1 = 2x1 ¶y/¶x2 = 8x2 ¶y/¶x3 = 0 ¶y/¶x4 = 0
¶f1/¶x1 = 1 ¶f1¶/x2 = 2 ¶f1/¶x3 = -1 ¶f1/¶x4 = 0
¶f2/¶x1 = -1 ¶f2/¶x2 = 1 ¶f2/¶x3 = 0 ¶f2/¶x4 = 1
The reduced gradient, equation (6-57) is:
ÑTY(xnb) = ÑTy(xnb) - ÑTy(xb) B-1b Bnb
where x1 and x4 are the basic variables, and x2 and x3 are the nonbasic variables.
The reduced gradient line, equation (6-58), is:
x2 = x20 + a (-4x1 + 8x2)
x3 = x30 + a(2x1)
Starting at point xo = (2,1,3,1), the reduced gradient line becomes:
x2 = 1
x3 = 3+ 4a
For the basic variables which must remain positive, the constraint equations can be used to obtain:
x1 = 1 - 2x2 + x3 = 2 + 4a
x4 = x1 - x2 = 1 + 4a
An exact line search is used to locate the optimum value of .
y = (2+4)2 + 4(1)2
The optimum values of the nonbasic variables are:
x2 = 1
x3 = 1
The corresponding values of the basic variables are:
x1 = 0
x4 = -1
This point (0,1,1,-1) is infeasible since x4 is negative. Thus, the value of a is reduced to have x4 be zero, i.e.
0 = 1 + 4a and a = -¼
Then the new feasible point x1 is:
x1 = 1 x2 = 1 x3 = 2 x4 = 0
y = 5
At this step x4 = 0, and the second constraint equation is tight. This gives ¶f2/¶x4 = 0. Then, x4 will become a nonbasic variable; and x2 is selected to be a basic variable, i.e. xb = (x1,x2) and xnb = (x3,x4).
The reduced gradient becomes:
or
The reduced gradient line at x1 (1, 1, 2, 0) is:
x3 = 2 + 10/3a x1 = 1/3(1 + x3 + 2x4) = 1 + 10/9a
x4 = 0 + 0a x2 = 1/3(1 + x3 - x4) = 1 + 10/9a
and x4 could have been omitted from the above procedure. An exact line search is used to locate the optimum value of a.
y = (1 + 10/9a)2 + 4(1 + 10/9a)2
Computing the values of the nonbasic and basic variables gives:
x1 = 0 x2 = 0 x3 = -1 x4 = 0
This point (0,0,-1,0) is infeasible since x3 is negative. Thus, the value of is reduced to have x3 be zero, i.e.,
0 = 2 + 10/3a and a = -3/5
Then the new feasible point x2 is:
x1 = 1/3 x2 = 1/3 x3 = 0 x4 = 0 y=5/9
At this step x3 = 0, and the first constraint equations is tight. This gives ¶f2/¶x3 = 0. Because x3 is a nonbasic variable already, it is not necessary to change basic and nonbasic variables. Also, ¶f2/¶x4 = 1 and not zero to allow the solution to move away from the constraint. The reduced gradient becomes:
The reduced gradient line at x2(1/3,1/3,0,0) is:
x3 = 0 + 0a x1 = 1/3(1 + x3 + 2x4) = 1/3 - 8/27a
x4 = 0 - 4/9a x2 = 1/3(1 + x3 - x4) = 1/3 + 4/27a
An exact line search is used to locate the optimum value of a.
y = (1/3 - 8/27a)2 + 4(1/3 + 4/27a)2
Computing the values of the basic and nonbasic variables gives:
x1 = ½ x2 = ¼ x3 = 0 x4 = ¼ y = ½
The minimum has been reached and the constraints are satisfied. It can be shown that the reduced gradient is zero at this point, and the procedure stops.
6-24. Solve the following problem by the generalized reduced gradient method starting at point xo(2,4,5). Show that the value of the parameter of the reduced gradient line a1 = -1/120 from the starting point locates the minimum of the economic model and satisfies the constraints.
minimize: 4x1 - x22 + x32 - 12
subject to: - x12 - x22 + 20 = 0
x1 + x3 - 7 = 0
Solution:
To begin, select x1 as the nonbasic variable with x2 and x3 being the basic variables for this case of two constraint equations and three variables. Computing the values of the partial derivatives of the economic model and constraint equations gives:
The reduced gradient, equation (6-57), is:
Computing the inverse of the matrix Bb gives:
and expanding gives the equation for the reduced gradient:
A feasible starting point xo(2,4,5) where y(xo) = 5 is used to begin the generalized reduced gradient method. Equation (6-58) is used to move in the direction of the optimum which is x*(2½, 4½, Ö55/2) and y(x*) = 4½.
or
x1,1 = 2 + a1 [4 - 2(2) - 2(5)] = 2 - 10a1
At this point a value of a1 has to be selected as the first one in a single variable search to minimize the economic model and satisfy the constraint equations. Using a1 = -1/20 gives x1,1 = 2½ and the values of x2,1 and x3,1 are computed to have a feasible solution using the constraint equations i.e.,
-(2½)2 - x22,1 + 20 = 0
2½ + x3,1 - 7 = 0
Solving gives x2,1 = Ö55/2, x3,1 = 4½ and y1 = 4½, which is the optimal solution. If a1 had been a different value than the one giving the optimal value of x1, the single variable search would have had to be continued. As values of the nonbasic variable x1 were generated, the constraints would be used to compute the corresponding values of the basic variables, x2 and x3.
6-25(17). Find the minimum of the following function starting at the point xo(1,1,0). However, this time experimental error is involved; and the Kiefer-Wolfowitz procedure must be used, employing ak = 1/k and ck = 1/k¼ with k = 1, 2, ..., 12. Simulate experimental error by flipping a coin and adding (subtracting) 0.1 from y if the coin turns up heads (tails).
y = x12 + 3x22 + 5x32
Solution:
k = 1, xo = (1,1,0)
y(x1) = 372 ; toss = head
y = 372 + 0.1 = 372.1
k = 2, x1 = (-3,-11,0)
y(x2) = 9084 ; toss = tail
y = 9084 - 0.1 = 9083.9
k = 3, (x2) = (3,55,0)
y(x3) = 81676; toss = head
y = 81676 + 0.1 = 81676.1
k = 4, (x3) = (-1,-165,0)
y(x4) = 326700 ; toss = tail
y = 326700 - 0.1 = 326699.9
k = 5, x4 = (0,330,0)
y(x5) = 640332 ; toss = tail
y = 640332 - 0.1 = 640331.9
k = 6, x5 = (0,-462,0)
y(x6) = 640332 ; toss = head
y = 640332 + 0.1 = 640332.1
k = 7, x6 = (0,462,0)
y(x6) = 326700 ; toss = head
y = 326700 + 0.1 = 326700.1
k = 8, x7 = (0,-330,0)
y(x8) = 166663.47 ; toss = head
y = 166663.47 + 0.1 = 166663.57
k = 9, x8 = (0,235.7,0)
y(x9) = 18518.2 ; toss = tail
y = 18518.2 - 0.1 = 18518.1
k = 10, x9 = (0,-78.6,0)
y(x10) = 737.59 ; toss = head
y = 737.59 + 0.1 = 737.69
k = 11, x10 = (0,15.68,0)
y(x11) = 6.096 ; toss = head
y = 6.096 + 0.1 = 6.196
k = 12, x11 = (0,-1.425,0)
y(x12) = 0 ; toss = head
y = 0.1
The optimum solution is x* = (0,0,0) with y(x11*) = 0.
