|
Chapter 6 | 
|
MULTIDIMENSIONAL SEARCH
Problems 6.1 to 6.10 | Problems 6.11 to 6.20 | Problems 6.21 to 6.25
problem6.11 | problem6.12 | problem6.13 | problem6.14 | problem6.15
problem6.16 | problem6.17 | problem6.18 | problem6.19 | problem6.20
6-11. Solve the following optimization problem by successive linear programming starting at xo(0,0.5) using limits of (1,1). Reduce the limits by one-half if infeasible points are encountered.
minimize: (x1 - 2)2 + (x2 - 1)2
subject to: (-1/4)x1 - x22 + 1 > 0
x1 - 2x2 + 1 = 0
Solution:
Placing the above problem in the form of equation (6-34) gives:
minimize: (2x1k - 4)Dx1+ + (2x2k - 2)Dx2+ - (2x1k - 4)Dx1-
-(2x1k - 2)Dx2- = y - [(x1k - 2)2 + (x2k - 1)2]
subject to: -¼Dx1+ - 2x2kDx2+ + ¼Dx1- + 2x2kDx2- > ¼ x1k + x2k2 - 1
Dx1+ - 2Dx2+ - Dx1- + 2Dx2- = -x1k + 2x2k - 1
Dx1+ - Dx1- < (u1 - x1k) = m1 = 1
Dx2+ - Dx2- < (u2 - x2k) = m2 = 1
-Dx1+ + Dx1- < (x1k - l1) = m1 = 1
-Dx2+ + Dx2- < (x2k - l2) = m2 = 1
The results of successive applications of
the Simplex Method are tabulated below:
The step size, m1 = m2 = 0.078, is small; and the value of the cost function is essentially constant. Thus, the procedure is terminated. For comparison, the optimal solution using analytical methods is x1 = 0.792, x2 = 0.896 and y = 1.471.
6-12. Solve the following optimization problem by successive linear programming starting at point xo(1,1) using limits of (1,1).
maximize: 4x1 + x2
subject to: x12 + 2x22 < 20.25
x12 - x22 < 8.25
Solution:
Placing the problem in the form of equation (6-34) gives:
maximize: 4Dx1+ + Dx2+ - 4Dx1- - Dx2- = y - [4x1k + x2k]
subject to: 2x1kDx1+ + 4x2kDx2+ - 2x1kDx1- - 4x2kDx2- < 20.25 - [x1k2 + 2x2k2]
2x1kDx1+ - 2x2kDx2+ - 2x1kDx1- + 2x2kDx2- < 8.25 - [x1k2 - x2k2]
Dx1+ - Dx1- < (u1 - x1k) = m1 = 1
Dx2+ - Dx2- < (u2 - x2k) = m2 = 1
-Dx1+ + Dx1- < (x1k - l1) = m1 = 1
-Dx2+ + Dx2- < (x2k - l2) = m2 = 1
The results of successive applications of the Simplex Method are tabulated below:
The step sizes, m1 and m2, have gone to zero; and the value of the cost function remains constant. Thus, the procedure is terminated. For comparison, the optimal solution by analytical methods in x1 = 3.5, x2 = 2.0 and y = 16. However, it was necessary to set m2 = 0 at step 1 to have the procedure move to step 2. If this was not done, the method would stop at point (2,2) by reducing the step size.
6-13. Solve the following optimization problem by successive linear programming starting at point xo(1,1) using limits of (1,1). Reduce the limits by one-half if infeasible points are encountered.
minimize: y = 2x12 + 2x1x2 + x22 - 20x1 - 14x2
subject to: x12 + x22 < 25
x12 - x22 < 7
Solution:
Using the format equation (6-34), the problem becomes:
minimize: (4x1k + 2x2k - 20)x1+ + (2x1k + 2x2k - 14)x2+ -
(4x1k + 2x2k - 20)x1- - (2x1k + 2x2k - 14)x2- = y
-(2x1k2 + 2x1kx2k + x2k2 - 20x1k - 14x2k)
subject to: 2x1kDx1+ + 2x2kDx2+ - 2x1kDx1- - 2x2kDx2- < 25 - (x1k2 + x2k2)
2x1Dx1+ - 2x2Dx2+ - 2x1Dx1- + 2x2Dx2- < 7 - (x1k2 - x2k2)
Dx1+ - Dx1- < (u1 - xk1) = m1 = 1
Dx2+ - Dx2- < (u2 - xk2) = m2 = 1
-Dx1+ + Dx1- < (x1k - l1) = m1 = 1
-Dx2+ + Dx2- < (x2k - l2) = m2 = 1
The results of successive applications of the Simplex Method are tabulated below:
The step size, m1 = m2 = 0.016 is small; and the value of the cost function remains constant. Thus, the procedure is terminated. For comparison, the optimal solution by analytical methods is x1 = 3, x2 = 4 and y = 58.
6-14(26). Solve the following problem by successive linear programming starting at point (2,1) using limits of (½,½). Reduce the limit by one-half if infeasible points are encountered.
maximize: 2x12 - x1x2 + 3x22
subject to: 3x1 + 4x2 < 12
x12 - x22 > 1
Solution:
Placing the problem in the form of equation (6-34) gives:
maximize: (4x1k - x2k)Dx1+ - (x1k - 6x2k)Dx2+ - (4x1k - x2k)Dx1- + (x1k - 6x2k)Dx2- = y - [2x1k2 - x1kx2k + 3x2k2]
subject to: 3Dx1+ - 3Dx1- + 4Dx2+ - 4Dx2- < 12 - [3x1k - 4x2k]
2x1kDx1+ - 2x1kDx1- - 2x2kDx2+ + 2x2kDx2- > 1 - [x1k2 - x2k2]
Dx1+ - Dx1- < m1 = ½
Dx2+ - Dx2- < m2 = ½
-Dx1+ + Dx1- < m1 = ½
-Dx2+ + Dx2- < m2 = ½
The results of successive application of the Simplex Method are tabulated below:
* Only lower bound set to zero; upper bound remains at 0.125
The optimal solution is reached at x1 = 4, x2 = 0 and y = 32, and the procedure is terminated.
6-15(34). Solve the following problem by successive linear programming starting at point xo(1,1) using limits of (2,2). Reduce the limits by one-half if infeasible points are encountered.
maximize: 3x12 + 2x22
subject to: x12 + x22 < 25
9x1 - x22 < 27
Solution:
Placing the problem in the form of equation (6-34) gives:
maximize: 6x1kDx1+ + 4x2kDx2+ - 6x1kDx1- - 4x2kDx2- = y - [3x1k2 + 2x2k2]
subject to: 2x1kDx1+ - 2x1kDx1- + 2x2kDx2+ - 2x2kDx2- < 25 - [x21k - x2k2]
9Dx1+ - 9Dx1- - 2x2kDx2+ + 2x2kDx2- < 27 - [9x1k - x2k2]
Dx1+ - Dx1- < m1 = 2
Dx2+ - Dx2- < m2 = 2
-Dx1+ + Dx1- < m1 = 2
-Dx2+ + Dx2- < m2 = 2
The results of successive applications of the Simplex Method are tabulated below:
Continuing, the procedure will converge to x1 = 3.5, x2 = 3.5 which is not the optimum. Using the infeasible point obtained above and continuing, gives:
The optimum solution is reached at x1 = 4, x2 = 3, and y = 66, but it was necessary to use an infeasible point in the sequence. This is an acceptable procedure, and the extent but to which infeasible points can be used is the subject of on-going research.
6-16. The following multivariable optimization problem is shown in Figure 6-7.
minimize: -2x1 - 4x2 + x12 + x22 + 5
subject to: - x1 + 2x2 < 2
x1 + x2 < 4
a. Give the successive linear programming algorithm for this problem in the form of equation (6-34). The upper and lower bounds are the same and are equal to 1.0.
b. For starting point xo = (0,0) apply the algorithm from part a to search for the optimum by successive linear programming.
Solution:
a. Give the successive linear programming algorithm in the form of equations (6-34).
for i = 1, 2, ..., m
Dxj+ - Dxj- < (uj - xjk)
Dxj+ - Dxj- > (lj - xjk)
for j = 1, 2, ..., n
Equation (6-34) becomes
minimize: (-2 + 2x1k)Dx1+ + (-4 + 2x2k)Dx2+ - (-2 + 2x1k)Dx1- - (-4 + 2x2k)Dx2- = y - [-2x1k - 4x2k + x1k2 + x2k2 + 5]
subject to: -Dx1+ + 2Dx2+ + Dx1- - 2Dx2- < 2 - (-x1k + 2x2k)
Dx1+ + Dx2+ - Dx1- - Dx2- < 4 - (x1k + x2k)
Dx1+ - Dx1- < 1
Dx2+ - Dx2- < 1
-Dx1+ + Dx2- < 1
-Dx2+ + Dx2- < 1
b. For starting point xo(0,0) apply the algorithm to move to point x1.
minimize: -2Dx1+ - 4Dx2+ + 2Dx1- + 4Dx2- = y - 5 y = 5
subject to: - Dx1+ + 2Dx2+ + Dx1- - 2Dx2- + x1s = 2 x1s = 2
Dx1+ + Dx2+ - Dx1- - Dx2- + x2s = 4 x2s = 4
Dx1+ - Dx1- + x3s = 1 x3s = 1
Dx2+ - Dx2- + x4s = 1 x4s = 1
- Dx1+ + Dx1- + x5s = 1 x5s = 1
- Dx2+ + Dx2- + x6s = 1 x6s = 1
____________________________________________________________
Dx2+ enters the basis, x4s leaves the basis.
minimize: -2Dx1+ + 2Dx1- + 4x3s = y - 1 y = 1
subject to: - Dx1+ + Dx1- + x1s -2x4s = 0 x1s = 0
Dx1+ - Dx1- + x2s - x4s = 3 x2s = 3
Dx1+ - Dx1- + x3s = 1 x3s = 1
Dx2+ - Dx2- + x4s = 1 Dx2+ = 1
- Dx1+ + Dx1- + x5s = 1 x5s = 1
x4s + x6s = 2 x6s = 2
____________________________________________________________
Dx1+ enters the basis, x3s leaves the basis
minimize: 2x3s + 4x4s = y + 1 y = -1
subject to: x1s + x3s - 2x4s = 1 x1s = 1
x2s - x3s - x4s = 2 x2s = 2
Dx1+ - Dx1- + x3s = 1 Dx1+ = 1
Dx2+ - Dx2- + x4s = 1 Dx2+ = 1
x3s + x5s = 2 x5s = 2
x4s + x6s = 2 x6s = 2
____________________________________________________________
The minimum has been reached; all coefficients in the objective function are positive.
Dx1+ = 1 Dx2+ = 1
New point, x1, is: x1,1 = x10 + Dx1+ - Dx1- = 0 + 1 - 0 = 1
x2,1 = x20 + Dx2+ - Dx2- = 0 + 1 - 0 = 1
Repeating the procedure at x1 and continuing, the following results from the successive linear programming solutions were obtained:
x1 x2 y
x2 1.0 1.5 0.250
x3 1.1 1.6 0.212
x4 1.2 1.6 0.200 optimal solution (see Figure 6-7)
6-17. Solve problem 6-16 by quadratic programming.
Solution:
The problem to be solved by quadratic programming is the same as example 6-11.
minimize: - 2x1 - 4x2 + x12 + x22 +5 or
maximize: 2x1 + 4x2 - ½(2x12 + 2x22) -5
subject to: - x1 + 2x2 < 2
x1 + x2 < 4
To formulate the quadratic programming problem, the following are computed.
c1 = 2 q11 = 2 a11 = -1 a12 = 2
c2 = 4 q12 = 0 = q21 a21 = 1 a22 = 1
q22 = 2
The linear programming problem formed from the above is:
minimize: z1 + z2
subject to: 2x1 - l1 + l2 - s1 + 2z1 = 2
2x2 + 2l1 + l2 - s2 + 4z2 = 4
-x1 + 2x2 + x3 = 2
x1 + x2 + x4 = 4
or
minimize: z1 + z2 = c
subject to: 2x1 - l1 + l2 - s1 + 2z1 = 2
2x2 + 2l1 + l2 - s2 + 4z2 = 4
-x1 + 2x2 + x3 = 2
x1 + x2 + x4 = 4
_____________________________________________________________________
Eliminating z1 and z2 from the objective function gives:
minimize: -x1 - 1/2x2 - 3/4l2 + 1/2s1 + 1/4s2 = c-2 c=2
2x1 - l1 + l2 - s1 + 2z1 = 2 z1 = 1
2x2 + 2l1 + l2 - s2 + 4z2 = 4 z2 = 1
-x1 + 2x2 + x3 = 2 x3 = 2
x1 + x2 + x4 = 4 x4 = 4
_____________________________________________________________________
x1 enters the basis and z1 leaves the basis.
minimize: -½x2 - ½l1 - ¼l2 + ¼s2 + z1 = c-1 c = 1
subject to: x1 - ½l1 + ½l2 - ½s1 + z1 = 1 x1 = 1
2x2 + 2l1 + l2 - s2 + 4z2 = 4 z2 = 1
2x2 + x3 - ½l1 + ½l2 - ½s1 + z1 = 3 x3 = 3
x2 + x4 + ½l1 - ½l2 + ½s1 - z1 = 3 x4 = 3
_____________________________________________________________________
x2 enters the basis, x3 leaves the basis.
minimize: ¼x3 - 5/8l1- 1/8l2 - 1/8s1 + ¼s2 +1¼z1 = c-¼ c = ¼
subject to: x1 - ½l1+ ½l2 - ½s1 + z1 = 1 x1 = 1
- x3 + 2½l1+ ½l2 + ½s1 - s2 - z1 + 4z2 = 1 z2 = ¼
x2 + ½x3 - ¼l1+ ¼l2 - ¼s1 + ½z1 = 3/2 x2 = 3/2
- ½x3 + x4 + 3/4l1- 3/4l2 + 3/4s1 - 1½z1 = 3/2 x4 = 3/2
_____________________________________________________________________
l1 enters the basis, z2 leaves the basis.
minimize: z1 + z2 = c c = 0
subject to: x1 - 1/5x3 + 3/5l2 - 2/5s1 - 1/5s2 + 4/5z1 + 4/5z2 = 1 1/5 x1 = 1 1/5
- 2/5x3 +l1 + 1/5l2 + 1/5s1 - 2/5s2 - 2/5z1 + 8/5z2 = 2/5 l1 = 2/5
x2 + 2/5x3 +13/10l2 - 1/4s1 - 1 /10s2 + 2/5z1 + 2/5z2 = 1 3/5 x2 = 1 3/5
- 1/5x3 + x4 - 9/10l2 + 3/5s1 + 3/10s2 + 9/5z1 - 6/5z2 = 1 1/5 x4 = 1 1/5
The optimum has been found, and the complimentary slackness conditions are satisfied. x1 = 1 1/5, x2 = 1 3/5, x3 = 0, x4 = 1 1/5, l1 = 2/5, l2 = 0, y = 1/5.
6-18(26). Solve the following problem by quadratic programming.
maximize: -2x12 - x22 + 4x1 + 6x2
subject to: x1 + 3x2 < 3
Solution:
To solve the problem by quadratic programming the standard form is:
maximize: 4x1 + 6x2 - ½(4x12 + 2x22)
subject to: x1 + 3x2 < 3
The linear programming problem formed from the above is:
minimize: z1 + z2
subject to: 4x1 + l1 - s1 + 4z1 = 4
2x2 + 3l1 - s2 + 6z2 = 6
x1 + 3x2 + x3 = 3
Eliminating z1 and z2 from the objective function, and solving by the Simplex Method gives:
minimize: -x1 - 1/3x2 - 3/4l1 + 1/4s1 + 1/6s2 = c-2 c = 2
subject to: x1 + 1/4l1 - 1/4s1 + z1 = 1 z1 = 1
1/3x2 + 1/2l1 - 1/6s2 + z2 = 1 z2 = 1
x1 + 3x2 + x3 = 3 x3 = 3
_____________________________________________________________________
x1 enters and z1 leaves the basis
minimize: -1/3x2 - 1/2l1 + 1/6s2 + z1 = c-1 c = 1
subject to: x1 + 1/4l1 - 1/4s1 + z1 = 1 x1 = 1
1/3x2 + 1/2l1 - 1/6s2 + z2 = 1 z2 = 1
3x2 + x3 - 1/4l1 + 1/4s1 - z1 = 2 x3 = 2
_____________________________________________________________________
Since l, x3 = 0, both x1 and x3 cannot be non-zero simultaneously, x2 enters and x3 leaves the basis.
minimize: 1/9x3 - 19/36l1 + 1/36s1 + 1/6s2 + 8/9z1 = c-7/9 c = 7/9
subject to: x1 + 1/4l1 - 1/4s1 + z1 = 1 x1 = 1
- 1/9x3 + 19/36l1 - 1/36s1 - 1/6s2 + 1/9z1 + z2 = 7/9 z2 = 7/9
x2 + 1/3x3 - 1/12l1 + 1/12s1 - 1/3z1 = 2/3 x2 = 2/3
_____________________________________________________________________
l1 enters and z2 leaves the basis
minimize: z1 + z2 = c c=0
subject to: x1 + 1/19x3 - 9/38s1 + 3/38s2 + 86/38z1 - 9/19z2 = 12/19 x1 = 12/19
- 4/19x3 + l1 - 1/19s1 - 6/19s2 + 4/19z1 + 36/19z2 = 28/19 l1 = 29/19
x2 - 6/19x3 + 3/38s1 - 1/38s2 - 6/19z1 + 3/19z2 = 15/19 x2 = 15/19
This is the optimal solution.
x1 = 12/19; x2 = 15/19, l = 28/19 and y = 111/19
6-19(27). Solve the following problem by quadratic programming.
maximize: 6x1 - 2x12 + 2x1x2 - 2x22
subject to: x1 + x2 < 2
Solution:
The standard format for the solution is:
maximize: 6x1 - ½(4x12 - 2x1x2 - 2x2x1 + 4x22)
subject to: x1 + x2 < 2
The linear programming problem formed from the above is:
minimize: z1 + z2
subject to: 4x1 - 2x2 + l - s1 + z1 = 6
- 2x1 + 4x2 + l - s2 + z2 = 0
x1 + x2 + x3 = 2
Coefficients of one on z1 and z2 were used for convenience. Eliminating z1 and z2 from the basis and solving by the Simplex Method gives:
minimize: - 2x1 - 2x2 - 2l + s1 + s2 = c - 6 c = 6
subject to: 4x1 - 2x2 + l - s1 + z1 = 6 z1 = 6
- 2x1 + 4x2 + l + s2 + z2 = 0 z2 = 0
x1 + x2 + x3 = 2 x3 = 2
_____________________________________________________________________
x1 enters the basis, and z1 leaves the basis
minimize: - 3x2 - 1½l - ½s1 + s2 + ½z1 = c-3 c = 3
subject to: x1 - ½x2 + ¼l - ¼s1 + ¼z1 = 1½ x1 = 1½
3x2 + 1½l - ½s1 - s2 + ½z1 + z2 = 3 z2 = 3
1½x2 + x3 - ¼l + ¼s1 - ¼z1 = ½ x3 = ½
_____________________________________________________________________
x2 enters the basis and x3 leaves the basis
minimize: x3 - 2l + s1 + s2 = c - 2 c = 2
subject to: x1 + 1/3x3 + 1/6l - 1/6s1 + 1/6z1 = 1 2/3 x1 = 1 2/3
- 2x3 + 2l - s1 - s2 + z1 + z2 = 2 z2 = 2
x2 + 2/3x3 - 1/6l + 1/6s1 - 1/6z1 = 1/3 x2 = 1/3
_____________________________________________________________________
l enters the basis, and z2 leaves the basis
minimize: z1 + z2 = c - 0 c = 0
subject to: x1 + ½x3 + 1/12s1 - 1/12s2 + 1/12z1 + 1/12z2 = 1½ x1 = 1½
- x3 + l - 1/12s1 - 1/12s2 + ½z1 + ½z2 = 1 l = 1
x2 + ½x3 + 1/12s1 - 1/12s2 - 1/12z1 + 1/12z2 = ½ x2 = ½
_____________________________________________________________________
The optimum has been reached, and the optimal solution is:
x1 = 1½, x2 = ½, l = 1, y = 5½
6-20(28). Solve the following problem by quadratic programming.
maximize: 9x2 + x12
subject to: x1 + 2x2 = 10
Solution:
Using equation (6-41) c1 = 0 q11 = -2
c2 = 9 qjk = 0 except for q11
j = 1,2 n = 2 a11 = 1
i = 1 m = 1 a12 = 2
b1 = 10
Using the results given in equation (6-41), the linear programming problem is:
minimize: z1 + z2
subject to: -2x1 + l1 - s1 + 0z1 = 0 j = 1
2l1 - s2 + 9z2 = 9 j = 2
x1 + 2x2 = 10
Rearranging gives:
minimize: z1 + z2
subject to: -2x1 + l1 - s1 = 0
2l1 - s2 + 9z2 = 9
x1 + 2x2 = 10
An initially feasible basis is needed; and z1 can be deleted from the function being minimized, since z1 does not appear in the constraint equations. Select x1, x2 and z2 to be the initially feasible basis. Algebraic manipulations are required to eliminate x1 from the third constraint. The following results are obtained:
minimize: z2 = P
subject to: x1 + ½l1 + ½s1 = 0 x1 = 0
2l1 - s2 + 9z2 = 9 x2 = 9
2x2 + ½l1 - ½s1 = 10 x2 = 5
_____________________________________________________________________
z2 has to be eliminated from the objective function to perform the Simplex Method
minimize: - 2/9l1 + 1/9s2 = P-1 P = 1
subject to: x1 - 1/2l1 + 1/2s1 = 0 x1 = 0
2/9l1 - 1/9s2 + z2 = 1 z2 = 1
2x2 + 1/2l1 - 1/2s1 = 10 x2 = 5
_____________________________________________________________________
l1 enters the basis and cannot be zero since it is associated with an equality constraint. z2 leaves the basis.
minimize: + z2 = P - 0 P = 0
subject to: x1 + 1/2s1 - 1/4s2 + 9/4z2 = 9/4 x1 = 2 1/4
l1 - 1/2s2 + 9/2z2 = 9/2 l1 = 4 1/2
2x2 - 1/2s1 + 1/4s2 - 9/4z2 = 7 3/4 x2 = 3 7/8
The optimum has been reached, since coefficient of variable in objective function is positive, and it is an artificial variable. The optimal solution is:
x1 = 2¼, x2 = 3 7/8, l1 = 4½ and y = 8 15/16