Chapter 3 - Geometric Programming
Introduction
In 1961 Clarence M. Zener, Director of Science at Westinghouse, published the first of several papers (1) on a new optimization technique he had discovered while working on the optimal design of transformers. These papers attracted the attention of Professor D.J. Wilde of Stanford University, and in 1963 he described them to the author of this textbook who obtained copies from Dr. Zener. In this work, Dr. Zener used the result called Canchy's arithmetic-geometric inequality which showed that the arithmetic mean of a group of terms always was greater than or equal to the geometric mean of the group, and he was able to convert the optimization of the nonlinear economic model for transformer design to one of solving a set of linear algebraic equation to obtain the optimum. The use of Cauchy's arithmetic-geometric inequality led to the name of geometric programming for the technique.
Two relatively parallel and somewhat independent efforts began to expand and extend the ideas about geometric programming. These were by Zener and colleagues and by Wilde and his students. A professor of mathematics at Carnegie Mellon University, Richard Duffin, began collaborating with Zener to extend the procedure. They were joined by Elmor Peterson, a Ph.D. student of Duffin. In 1967 Duffin, Peterson, and Zener (2) published a text on their work entitled Geometric Programming. In this work the economic model was limited to minimizing the cost of the sum of positive terms.
Wilde and his student Ury Passey (3) developed the theory for negative coefficients and inequality constraints using Lagrange methods. This research went directly into the text Foundations of Optimization, which was published in 1967, and the result is that geometric programming is now applicable to a polynomial economic model with polynomial constraints as equalities and inequalities.
Four other books have followed the publication of those mentioned above. Zener (4) followed with a book entitled Engineering Design by Geometric Programming in 1971. Nijhamp wrote a book on the subject, entitled Planning of Industrial Complexes by Means of Geometric Programming in 1972. The third and fourth volumes, completely covering the theory and application of the subject, were Applied Geometric Programming by Beightler and Phillips(6), published in 1976, and Globally Optimal Design by Wilde (14) published in 1978.
The more important results for this optimization procedure will be described in this book, which will take us through unconstrained polynomial optimization. This will show the advantages and disadvantages of the techniques and how the method capitalizes on the mathematical structure of the optimization problem. Also, this will give those who are interested the ability to proceed with additional material on the topic given in the previously mentioned books without significant difficulty. Beginnning with posynomial optimization, we will then proceed to polynomial optimization. We will find that the global minimum is obtained with posynomials, but only local stationary points are obtained when the economic model is a polynomial. Our approach will follow that of Wilde and Passey (3). On seeing Zener's work, they were able to obtain the same results from the classical theory of maxima and minima and extend this to polynomials. Consequently, we will use the classical theory to develop geometric programming, although this will not describe Zener's original development using the geometric-arithmetic inequality. However, it will require less effort to obtain the final result, since the background arguments associated with the geometric-arithmetic inequality will not be required, and the results for polynomial optimization will follow directly from posynomial optimization.
Optimization of Posynomials
It is typical to find cost equations for preliminary equipment design to be posynomials, a polynomial whose terms are all positive. The cost equation in example 2-2 of the previous chapter is an exmple of a posynomial. In general form, a posynomial can be written as:
where the ct's are the positive cost coefficients, the xn's are the independent variables, the atn's are the exponents on the independent variables, N is the total number of independent variables, and T is the total number of terms in the cost equation.
The cost equation from the simple process from example 2-2 is given below as an illustration of equation (3-1).
y = 1000x1 + 4 x 109 x1-1 x2-1 + 2.5 x 105 x2 (3-2)
In this case T = 3 and N = 2, with the values of the ct's and atn's given below:
c1 = 1000 a11 = 1 a21 = -1 a31 = 0
c2 = 4 x 109 a12 = 0 a22 = -1 a32 = 1
c3 = 2.5 x 105
The classical theory of Chapter 2 will be used to develop the geometric programming
method of optimizing posynomials. Also, some counterintuitive manipulations will be
required to obtain the orthogonality and normality conditions of geometric programming.
The result will be another problem to be solved that arises from the original problem.
This will be encountered in other methods also, where the original or primal optimizations
problem is converted into another related or dual optimizations problem. This dual
problem should be easier to solve for the optimum for the procedure to be successful,
and there will be a one-to-one correspondence between the optimal solution of the
primal and dual problems.
To begin, the first partial derivatives of equation (3-1) with respect to each of the n independent variables, are set equal to zero according to the necessary conditions given in Chapter 2. This gives the following set of equations
which after multiplying by xi can be rewritten as:
This is a set of N nonlinear algebraic equations, and, if solved by the classical theory, there will be all of the problems associated with attempting to optimize equation (2-56) as described at the end of Chapter 2.
Another procedure was suggested (2) where a dual problem is developed using equations (3-1) and (3-4). We will say that equation (3-4) has been solved for the optimal values of the xi's and the minimum cost has been computed using equation (3-1). This is the counterintuitive part of the development where the optimal values of the xi's and y are used in principle, but their numerical values are not known specifically.
First, both sides of equation (3-1) are divided by the optimal value of y to give:
Then the terms in the brackets of equation 3-5 are defined as optimal weights wt, and equation (3-5) becomes
Now the equation set from the necessary conditions, equation (3-4), can be divided by the optimal value of y and written as:
for i = 1, 2, ..., N, and in terms of the optimal weights this equation becomes:
for n = 1,2,...,N, where the subscript n has been used in the place of i for convenience.
At this point there is a set of N+1 linear algebraic equation which have been obtained from the original problem. These equations are referred to as the normality and orthogonality conditions of geometric programming
It will be necessary to pursue some additional algebraic manipulations to obtain an equation that relates the optimal value of y with the optimal weights wt and the cost coefficients ct. We begin using equation (3-6) as an exponent on y as:
Equation (3-7) is now used to eliminate y from the right-hand side of equation (3-10), and introduce ct and wt as:
which can be written as:
The double-product term can be simplified using equation (3-9) as:
and equation (3-12) simplifies to the following:
which is the equation needed to relate the optimal value of y with the optimal weights wt and the cost coefficients ct.
The following example will illustrate the use of equation (3-6), (3-7), (3-9), and (3-14) to find the minimum cost of the simple process given in example 2-2. This will give the geometric programming solution for posynomials, and this computational procedure is different than other methods. First, the values of the optimal weights are computed using equations (3-6) and (3-9). Then the minimum cost is evaluated using equation (3-14). Finally the optimal values of the independent variables are calculated using the definition of the optimal weights, equation (3-7).
Example 3-1 (3)
Find the minimum cost of the simple process of example 2-2 by geometric programming. The cost function is:
y = 1000x1 + 4 × 109 x1-1x2-1 + 2.5 × 105 x2
Normality and orthogonality conditions from equations (3-6) and (3-9) are:
w1 + w2 + w3 = 1
w1 - w2 = 0
- w2 + w3 = 0
Solving simultaneously gives
w1= w2 = w3 = 1/3
Solving for the minimum cost using equation (3-14) gives:
y = [1000/(1/3)]1/3 [4 × 109/(1/3)]1/3 [2.5 × 105/(1/3)]1/3 = 3 × 106
which is the same result as obtained previously. To calculate the optimal values of
the independent variables using equation (3-7), there is a choice, i.e., three equations
for the wt's and two xi's:
w1 = 1000x1 / 3 ×106 = 1/3®x1 = 1000
w2 = 4 ×109 x1-1x2-1 / 3 ×106 = 1/3
w3 = 2.5 ×105 x2 / 3 ×106 = 1/3® x2 = 4
The equations that most readily permit the evaluation of the optimal values of the
independent variables are selected. In this case they were w1 and w3.
In example 3-1 it turned out that the number of terms in the cost function, T, was one more than the number of independent variables N. Consequently, there were the same number of optimal weights as there were equations from the normality and orthogonality conditions, and the values of the optimal weights could be determined uniquely. Then these optimal weights were used to compute the minimum cost and the optimal values of the independent variables. However, if the number of terms T is greater than the number of independent variables plus one, then the method of geometric programming becomes a constrained optimization as stated below
The above is a statement of the dual problem of geometric programming obtained from the primal problem which is to minimize equation (3-1). The significance of this dual problem will be discussed further, but first, let us examine the following example, which is a modification of example 3-1. It illustrates the effect of having an additional term in the cost function.
Example 3-2 (3)
Find the minimum cost of the simple process where an additional annual cost of $9000x1x2 for a purifying device must be added. The cost function becomes:
y = 1000x1 + 4 ×109 x1-1x2-1 + 2.5 ×105x2 + 9000x1x2
Normality and orthogonality conditions from equations (3-6) and (3-9) are
w1 + w2 + w3 + w4 = 1
w1 - w2 + w4 = 0
- w2 + w3 + w4 = 0
which must be solved along with dual function of equation (3-14), i.e.:
y = (c1/w1)w1 (c2 /w2)w2 (c3 /w3)w3 (c4 /w4)w4
The methods of Chapter 2 for constrained optimization are required. All of those methods would require differentiating the dual function with respect to the wi's. The direct substitution approach (3) gives:
w1 = (1 - 2w4)/3
w2 = (1 + w4)/3
w3 = (1 - 2w4)/3
And the function to differentiate with respect to w4 to locate the minimum cost is:
y = [3000/(1-2w4)](1-2w4)/3 [12 ×109/(1+w4)](1+w4)/3 [7.5 ×105/(1-2w4)](1-2w4)/3[9000/w4]w4
At this point it is only reasonable to return to the primal problem which in unconstrained, and solve it for the minimum cost rather than continuing with the dual problem which is significantly more complicated algebraically. (See Reference 3 for the solution.) It is said that this problem has a degree of difficulty of 1, i.e.
T - (N+1) = 4 - (2+1) = 1
and the problem of example 3-1 had a degree of difficulty of zero.
T - (N+1) = 3 - (2+1) = 0
Geometric programming problems can be classified by their degree of difficulty which
can be determined prior to attempting to solve the optimization problem by this method.
We will summarize the results obtained in terms of the degrees of difficulty as measured
by T-(N+1), having seen that if the degree of difficulty is zero only a set of linear
algebraic equations need be solved for the minimum cost. However, if the degree of
difficulty is greater than zero a constrained optimization problem has to be solved.
The primal problem is:
The dual problem is:
There is a direct correspondence between the primal and dual problems, i.e., the dual problem is constructed from the primal problem. It has been shown (3) that the primal problem, a posynomial, has a global minimum and the dual problem has a global maximum. The numerical value of the minimum of the primal problem is the same as the maximum of the dual problem.
As has been seen if T - (N+1) is zero, the posynomial optimization problem is solved without difficulty; and if T - (N+1) is greater than zero, it may be easier to attempt the solution of the primal problem by a method other than geometric programming. Also, it is necessary to consider the case where T - (N+1) is less than zero, i.e., the number of terms is less than the number of variables plus one. In this situation the algebraic equation set from the normality and orthogonality conditions has more equations than variables, i.e., the equation set is overdetermined. Consequently, the primal problem can not be solved by geometric programming; and the dual problem is said not to be consistent with the primal problem, i.e., the primal problem does not give a dual problem with at least zero degrees of difficulty. However, it has been suggested (3) that a subset of the orthogonality equations could be selected to give several zero degree of difficulty problems to be solved. It was proposed that this would give some information about the optimization problem. This is equivalent to setting some of the independent variables in the primal problem equal to one, and, depending on the problem this might yield some useful information.
Before we move to optimization of polynomials by geometric programming, let us examine the solution of the economic model for the vapor condenser given at the end of Chapter 2. This will demonstrate the facility of the technique when fractional exponents are part of the economic model.
Example 3-3 (7)
The following cost equation was developed for the optimal design of a vapor condenser with a fixed heat load for use in a desalination plant and includes the cost of steam, fixed charges, and pumping costs.
C = aN-7/6D-1L-4/3 + bN-0.2D0.8L-1 + cNDL + dN-1.8D- 4.8L
where C is the cost in dollars per year; N is the number of tubes in the condenser;
D is the nominal diameter of the tubes in inches; L is the tube length in feet and
a, b, c and d, are coefficients that vary with the fluids involved and the construction
costs. For a sea water desalination plan using low pressure steam for heating, these
values are a = 3318.8, b = 1.1991, c = 3.4014 x 10-4 and d = 11.624.
The orthogonality and normality conditions are given below.
w1 + w2 + w3 + w4 = 1
-(7/6) w1 - 0.2w2 + w3 - 1.8w4 = 0
-w1 + 0.8w2 + w3 - 4.8w4 = 0
-(4/3) w1- w2 + w3 + w4 = 0
The degree of difficulty for this problem is zero, and a unique solution for the optimal
weights is obtained:
w1 = 2/5 w2 = 1/30 w3 = 8/15 w4 = 1/30
The minimum cost is computed using equation (3-16)
y = [1.724 × 105 × 5/2]2/5 [9.779 × 104 × 30]1/30[1.57 × 15/8]8/15 [3.82 × 10-2 × 30]1/30 = $526.50/yr.
The optimal values of N, D, and L can be obtained by solving three of the following equations.
(3318.8) N-7/6 D-1 L- 4/3/526.5 = 2/5
(1.199) N-0.2 D0.8 L-1/526.5 = 1/30
(3.4014 × 10-4) NDL/526.5 = 8/15
(11.624) N-1.8 D- 4.8 L/526.5 = 1/30
The solution of the above equations gives N = 112, D = 1.0 inch, and L = 14.0 ft.
An extension to a more detailed design is given by Avriel and Wilde (7).
Optimization of Polynomials
For this case either the cost or profit can be represented by a polynomial. The same procedure employing classical methods (8) will be used to obtain the dual problem, and the techniques will be essentially the same to find the optimum. However, the main difference is that stationary points will be found, and there will be no guarantee that either a maximum or a minimum has been located. It will be necessary to use the methods of Chapter 2 or local exploration to determine their character.
It is convenient to group the positive terms and the negative terms together to represent a general polynomial. This is written as:
An example of this equation, given below, will be used to illustrate the solution technique for polynomials.
y = 3x10.25 - 3x11.1 x20.6 - 115x2-1x3-1 - 2x3 (3-18)
and comparing equations (3-17) and (3-18) gives:
c1 = 3 c2 = 3 c3 = 115 c4 = 2
a11= 0.25 a21 = 1.1 c31 = 0 a41 = 0
a12 = 0 a22 = 0.6 a32 = -1 a42 = 0
a13 = 0 a23 = 0 a33 = -1 a43 = 1
As done previously, the first partial derivatives of equation (3-17) with respect to the n independent variables are set equal to zero according to the necessary conditions. This gives the following set of equations:
for i = 1, 2, 3, ..., N, which, after multiplying by xi /y can be written as:
for i = 1, 2, ..., N.
The definition of the optimal weights (equation 3-7) can now be used to give the orthogonality conditions for polynomial optimization, i.e.:
for n = 1, 2, ..., N, where the subscript n has been used in place of i for convenience.
Also the normality condition is obtained the same way as equation (3-6) by dividing equation (3-17) by the optimal value of y, which is known in principle from the solution of the set of equations given by equatio (3-20). The result is:
The only algebraic manipulations that remain are to obtain the equation comparable to equation (3-14) for a polynomial profit or cost function. The procedure is the same and uses equation (3-22) as follows:
Again the definition of the optimal weights, equation (3-7), is used to eliminate y from the right-hand side of equation (3-23) and introduce ct and wt as:
and the above can be written as
The term in the second bracket can be written as
Using equation (3-21) and performing the manipulations done to obtain equation (3-13), the result is comparable to equation (3-14) and is:
The primal and dual problems for the method of geometric programming for polynomials can be stated as:
The term optimize is used for both the primal and dual problems. A polynomial can represent a cost to be minimized or a profit to be maximized, since terms of both signs are used. The results obtained from the dual problem could be a maximum, a minimum, or a saddle point since stationary points are computed. Consequently, tests from Chapter 2 or local exploration would be required to determine the character of these stationary points. Before this is discussed further let us examine the geometric programming solution or equation (3-18) to illustrate the procedure.
Example 3-4
Obtain the geometric programming solution for equation (3-18).
y = 3x10.25 - 3x11.1x20.6 - 115x2-1x3-1 - 2x3
c1 = 3 c2 = 3 c3 = 115 c4 = 2
a11 = 0.25 a21 = 1.1 a31 = 0 a41 = 0
a12 = 0 a22 = 0.6 a32 = -1 a42 = 0
a13 = 0 a23 = 0 a33 = -1 a43 = 1
The normality and orthogonality conditions are:
w1 - w2 - w3 - w4 = 1
0.25w1 - 1.1 w2 = 0
- 0.6w2 + w3 = 0
w3 - w4 = 0
Solving simultaneously gives:
w1 = 2, w2 = 5/11, w3 = 3/11, w4 = 3/11
The optimal of y, in this case, is a maximum.
y = (3/2)2 / [(3 ×11/5)5/11 (115 × 11/3)3/11 (2 × 11/3)3/11] = 0.1067
and the optimal value of x1, x2, and x3 can be computed from the definitions of the
optimal weights by selecting the most convenient form from among the following:
3x10.25/0.1067 = 2
3x11.1x20.6/ 0.1067 = 5/11
115x2-1x3-1/0.1067 = 3/11
2x3 /0.1067 = 3/11
Using the first, third and fourth, gives:
x1 = 2.560 × 10-5, x2 = 2.716 × 105, x3 = 1.455 × 10-2
A problem can be encountered from the formulation of a geometric programming problem where the result will be negative values for the optimal weights (3,6). The dual problem required that the optimum values of y be positive. If the economic model is formulated in such a way that the optimal value is negative when calculated from the primal problem, the result will be negative weights computed in the dual problem, and it will not be possible to compute the optimum value of the function using equation (3-27). However, the value of the weights will be correct in numerical value but incorrect in sign. The previous example will be used to illustrate this difficulty, and the proof and further discussion is given by Beightler and Phillips(6).
In example 3-4 a maximum was found, and the value of the profit function was 0.1067. Had the example been to find the minimum cost, i.e., - y the result would have been -0.1067. However, this value could not have been calculated using equation (3-27). Reformulating the problem of -y with the positive terms first as:
y = 3x11.1x20.6 + 115x2-1x3-1+ 2x3 - 3x10.25
The normality and orthogonality conditions are:
w1 + w2 + w3 - w4 = 1
1.1w1 + - 0.25w4 = 0
0.6w1 - w2 = 0
- w2 + w3 = 0
The solution to the equation set is:
w1 = -5/11, w2 = -3/11, w3 = -3/11, w4 = -2
and unacceptable negative values of the optimal weights are obtained. Although not
obvious, the cause of this is that the value of the function is negative at the stationary
point, i.e., -0.1067. Reformulating the problem to find the stationary point of the
negative of the function will give positive optimal weights and a positive value of
the function as was illustrated in example 3-4.
In the illustration, example 3-4, the degree of difficulty, T - (N+1), was zero. As in posynomial optimization, the degree of difficulty must be zero or greater to be able to solve the problem by geometric programming. Also if the degree of difficulty is one or more, then the dual problem is a constrained optimization problem, which has to be solved by the procedures of Chapter 2 or other methods. However, Agognio (18) has proposed a primal-dual, normed space (PDNS) algorithm which used the primal problem and the dual problem together to locate the optimum. This algorithm consists of operations within the primal and dual programs and two sets of mappings between them which depend on a least-squares solution minimizing the two-norm of the overdetermined set of linear equations. The PDNS algorithm was tested on a number of standard problems and performed essentially equally as well as other methods. Also, the dissertation of Agogino (18) describes multiobjective optimization applications of the algorithm.
Closure
In this example we have covered the geometric programming optimization of unconstrained posynomials and polynomials. Posynomials represented the cost function of a process, and the procedure located the global minimum by solving the dual problem for the global maximum. Polynomials represented the cost or profit function of a process, and the procedure of solving the dual problem located stationary points which could be maxima, minima, or stationary points. Their character had to be determined by the methods of Chapter 2 or by local exploration. Also, for polynomials if the numerical value of the function being optimized was negative at the stationary point, this caused the optimal weights of the dual problem to be negative. It was then necessary to seek the optimum of the negative of the function to have a positive value at the stationary point. This gave positive optimal weights, and then numerical value of the function at the stationary point was computed using equation (3-27).
A complete discussion of geometric programming is given by Beightler and Phillips (6), which includes extensions to equality and inequality constraints. These extensions have the same complications as associated with the degrees of difficulty that occur with the unconstrained problems presented here. Because of these limitations the lengthy details for constraints will not be summarized here, and those who are interested in exploring this subject further are referred to the texts by Beightler and Phillips (6), and Reklaitis, et. al. (17).
The dual problem is solved when it is less complicated than the primal problem. An exponential transformation procedure for the dual problem has been described by Reklaitis et. al. (17) to make the computational problem easier when the degree of difficulty is greater than zero and also if constraints are involved. In addition, Reklaitis et. al. (17) reported on comparisons of computer codes for geometric programming optimization based on their research and that of others, including Dembo and Sarma. The testing showed that the best results were obtained with the quotient form of the generalized geometric programming problem, and second was the generalized reduced gradient solution of the exponential form of the primal problem. Also, results by Knopf, Okos, and Reklaitis (9) for batch and semicontinuous process optimization showed that the dual problem can be solved more readily than the primal problem using the generalized reduced gradient multidimensional search technique. Moreover, Phillips (10) has reported other successful applications with non-zero degrees of difficulty requiring multidimensional search methods, which are the topic of Chapter 6. In summary, if the economic model and constraints can be formulated as polynomials, there are many advantages of extensions of geometric programming which can be used for optimization.
References
1. Zener, C. M. "A Mathematical Aid in Optimizing Engineering Designs" Proceeding of the National Academy of Science, Vol. 47, No. 4, 537-9 (April, 1961).
2. Duffin, R. J., E. L. Peterson and C. M. Zener, Geometric Programming, John Wiley and Sons, Inc., New York (1967).
3. Wilde, D. J. and C. S. Beightler, Foundations of Optimization Prentice-Hall, Inc., Englewood Cliffs, N.J. (1967).
4. Zener, C. M., Engineering Design by Geometric Programming, John Wiley and Sons, Inc., New York (1971).
5. Nijhamp, P., Planning of Industrial Complexes by Means of Geometric Programming, Rotterdam Univ. Press, Rotterdam, Netherlands (1972).
6. Beightler, C. S. and D. T. Phillips, Applied Geometric Programming, John Wiley and Sons, Inc., New York (1976).
7. Avriel, M. and D. J. Wilde, "Optimal Condenser Design by Geometric Programming", Ind. and Engr. Chem., Process Design and Development, Vol.6, No. 2, 256 (April, 1967).
8. Chen, N. H., "A Simplified Approach to Optimization by Geometric Programming" Preprint 12b, 65th National Meeting, American Institute of Chemical Engineers, Cleveland, Ohio (May 4-7,1969).
9. Knopf, C. F., M. R. Okos, and G. V. Reklaitis, "Optimal Design of Batch/Semicontinuous Processes", Ind. Eng. Chem, Process Des. Dev., Vol 21, No.1, 79 (1982).
10. Phillips, D. T. Mathematical Programming for Operations Researchers and Computer Scientists, Ed. A. G. Holtzman, Marcel Dekker, Inc., New York (1981).
11. Stocker, W. F., Design of Thermal Systems, McGraw-Hill Book Co., New York (1971).
12. Sherwood, T. K., A Course in Process Design, MIT Press, Cambridge, Mass. (1963).
13. Beightler, C. S., D. T. Phillips and D. J. Wilde, Foundations of Optimization, 2nd Ed., Prentice-Hall, Inc., Englewood Cliffs, N.J. (1979).
14. Wilde, D. J., Globally Optimal Design, John Wiley and Sons, Inc., New York, (1978).
15. Ray, W. H. and J. Szekely, Process Optimization with Applications in Metallurgy and Chemical Engineering, John Wiley and Sons, Inc., New York (1973).
16. Beveridge, G. S. G. and R. S. Schechter, Optimization: Theory and Practice, McGraw-Hill Book Company, New York (1970).
17. Reklaitis, G. V., A. Ravindran and K. M. Ragsdell, Engineering Optimization: Methods and Applications, John Wiley and Sons, Inc., New York (1983).
18. Agogino, Alice M., A Primal-Dual Algorithm for Constrained Generalized Polynomial Programming: Application to Engineering Design and Multiobjective Optimization, Ph. D. Dissertation, Stanford University, Stanford, California (1984).
Problems
3-1. Solve the following problem by geometric programming
minimize: y = x12 + 2x22 + 3/x1x2 + 2x1x2
Solution
3-2.(10) Solve the following problem by geometric programming.
minimize: y = 5x1-1x2-3 + 2x12x2x3-2 + 10x1x24x3-1 + 20x32
Solution
3-3.(13) Solve the following problem by geometric programming.
minimize: y = 60x1-3x2-2 + 50x13x2 + 20x1-3x23
Solution
3- 4 a. Solve the following problem by geometric programming.
minimize: y = 4x1 + x1/x22 + 4x2 /x1
b. If an additional term, 2x2, is added to the function being minimized, set up the
necessary equations and discuss the procedure to find the optimum.
Solution
3-5. Solve the following problem by geometric programming.
minimize: y = 4x1-1x2-1x3-1 + 8x1x2 + 4x2x3 + 4x1x3
Solution
3-6.(16) Consider the following geometric programming problem.
minimize: y = x12 + x2 + 3/x1x2 + 2x1x2
a Show that the following is the dual problem
subject to: w1 + w2 + w3 + w4 = 1
2w1 - w3 + w4 = 0
2w2 - w3 + w4 = 0
Discuss the method of solution to obtain the optimal value of y and x1 and x2. It
is not necessary to carry out the calculations.
b. Two sets of values of the weights that satisfy the constraints w1 = (1/15, 2/15,
7/15, 1/3) and w2 = (1/10, 1/5, 9/20, 1/4). Calculate the optimal value of y for w1 and w2.
What is your conclusion?
Solution
3-7.(11) Treatment of a waste is accomplished by chemical treatment and dilution to meet effluent code requirements. The total cost is the sum of the treatment plant, pumping power requirements, and piping cost. This cost is given by the following equation
where C is in dollars, D in inches, and Q in cfs. Find the minimum cost and best vaues of D and Q by geometric programming.
Solution
3-8. The work done by a three stage compressor is given by the following equation.
W = (P1V1/e) [(P2/P1)e + (P3/P2)e + (P4 /P3)e - 3]
where P1 is the inlet pressure to stage 1, P2 is the discharge pressure from stage
1 and inlet pressure to stage 2, P3 is the discharge pressure from stage 2 and inlet
pressure to stage 3, P4 is the discharge pressure from stage 3, and e is equal to
(k-1)/k where k is the ratio of specific heats, a constant.
For specified inlet pressure P1 and volume V1 and exit pressure P4, determine intermediate pressures P2 and P3 which minimize the work by geometric programming.
Solution
3-9.(11) Determine the optimal pipe diameter for the minimum installed plus operating
costs by geometric programming for 100 ft. of pipe conveying a given flow rate of
water.
The installed cost in dollars is 150 D and the lifetime pumping cost in dollars is 122,500/D5. The diameter D is in inches.
Solution
3-10. Sherwood (12) considered the optimum design of a gas transmission line, and obtained the following expression for annual charges (less fixed expenses).
where L is equal to pipe length between compressors in feet, D is the diameter in inches, F = r 0.219-1, where r is the ratio of inlet to outlet pressure. Determine the minimum cost, and the optimal values of L, F, D and r.
Solution
3-11.(15) The economic model for the annual cost is given below for a furnace in which a slag-metal reaction is to be conducted.
C = 1 ×1013 / L3T 2 + 100L2 + 5 × 10-11L2 T 4
In this equation L is the characteristic length of the furnace in feet and T is the
temperature in oK.
a. Determine the minimum cost and the corresponding best value of L and T by geometric
programming
b If an additional term, 1000L3 is added to the cost function, give the geometric
programming problem to be solved, i.e., dual problem; and indicate how the solution
could be obtained.
c. If the cost function only contained the first two terms, deleting the third term,
indicate the effect on the solution by geometric programming.
Solution
3-12. The profit function for each of three chemical reactors operating in parallel with the same feed is given by the three equations below. Each reactor is operating with a different catalyst and conditions of temperature and pressure. The profit function for each reactor has the feed rates x1, x2, and x3 as the independent variable, and the parameters in the equation are determined by the catalyst and operating conditions.
P1 = 0.2x1 - 2(x1 /100)2
P2 = 0.2x2 - 4(x2 /100)2
P3 = 0.2x3 - 6(x3 /100)2
a. For the equation for the total profit (P = P1 + P2 + P3) from operating the three
reactors, give the geometric programming dual problem with the normality and orthogonality
conditions. Compute the optimal weights.
b. Calculate the maximum profit.
c. Calculate the values of the three flow rates of feed to the reactors using the
definition of the optimal weights.
Solution
3-13. A batch process has major equipment components which are a reactor, heat exchanger, centrifuge, and dryer. The total cost in dollars per batch of feed processed is given by the following equation, and it is the sum of the costs associated with each piece of equipment.
C = 315 V0.57t1-1 + 370 V-0.22t1 + 460 VO.54t2-1 + 450 V-0.72t2
reactor heat exchanger centrifuge dryer
where V is the volume of feed to be processed per batch in ft3, and t1 and t2 are
residence times in hours for the two sections of the process.
a. Find the optimum values of the volume of feed to be processed per batch, V; and
the residence times, t1 and t2, by geometric programming.
b. If packaging costs are added as 12OV0.52, set-up this geometric programming problem;
and discuss the procedure for finding the minimum cost.
c. Obtain the equations to be solved for the minimum cost by analytical methods, and
discuss the feasibility of solving the problem by this method (not with the packaging
costs).
Solution
3-14.(6) A total of 400 cubic yards of gravel must be ferried across a river. The gravel is to be shipped in an open box of length x1, width x2, and height x3. The ends and bottom of the box cost $20/sq.yd. to build, the sides, $5/sq.yd. Runners cost $2.50/yd., and two are required to slide the box. Each round trip on the ferry cost $0.10. The problem is to find the optimal dimensions of the box that minimized the total costs of construction and transportation. This total cost is given by:
y = 40x1-1x2-1x3-1 + 20x1x2 + 10x1x3 + 40x2x3 + 5x1
a. Give the orthorgonality and normality equations to solve this problem by Geometric
Programming. Discuss how the problem would be solved and any difficulties that would
be encountered. Beightler and Phillips(6) give the following results:
w1 = 0.3858 y* = $108.75 x1* = 1.542 yd.
w2 = 0.1575 x2* = 0.561 yd.
w3 = 0.1575 x3* = 1.107 yd.
w4 = 0.2284
w5 = 0.0709
b. Neglect the runner's cost, 5x1, and give the orthogonality and normality equation
set. Show that the solution to this equation set is:
w1 = 2/5, w2 = 1/5, w3 = 1/5, w4 = 1/5
c. Compute the minimum cost.
d. Compute the values of the independent variables and compare with the results obtained
in part a.
Solution