幾何規劃之全域最佳化新法及其管理與工程之應用

Abstract

許多管理與工程設計問題多可轉化為幾何規劃(Generalized Geometric Program)問題。GGP問題若以一般數值方法如牛頓法(Newton』s method)、基因演算法(genetic algorithm)、類神經網路法(neuro-net methods)求解，常只能得到局部最佳解(local optimum)。如何求解非線性模式以求得全域最佳解，是近十年來最佳化領域的重要課題。目前最常用的全域最佳化法為指數轉化法(exponential-based method)。此法缺點有二：一為變數不許可為零或負數，另一為引用的0-1變數太多以致計算時間甚長。本研究用意在深入探討全域最佳化理論與方法，如凸形化(convexification)、值域減化(range reduction)、乘積線性化(product linearization)、分支價量(branch-price)等，以發展新一代的全域最佳化解法。此一新方法將與目前常用的全域最佳化軟體(如LINGO)相比較，並以之應用於求解機械與土木設計問題、決策球問題、基因序列定址問題等

Many management and engineering problems can be reformulated as generalized geometric programming (GGP) problems. Resolving GGP problems by traditional methods such as Newton』s methods, genetic algorithms and neuro-net methods may only find locally optimal solutions. How to treat GGP problems to find globally optimal solutions is one of critical issues in the optimization field. Currently, a widely used method for solving nonlinear models to obtain the globally optimal solution is the exponential-based approach (Maranas and Floudas, 1997; Floudas, 1999; Floudas2000). Floudas』 approach, however, has two drawbacks. Firstly, the variables within that approach are not allowed to be non-positive. Secondly, Floudas』 approach requires embedding large number of binary variables, which causes heavy computational burden. This study intends to investigate the related theories of global optimization thus to develop a novel method for solving GGP problems. These theories include convexification, range reduction, product linearization and branch-and-price algorithms. The developed method will also be applied to solve the engineering design problems, the decision-ball problem, and the DNA consensus sequence identification problems.