運用確定性全域最佳化方法求解工程與管理問題

A Deterministic Global Optimization Approach for Engineering and Management Problems

王佩淳(Pei-Chun Wang)

指導教授 ： 蔡榮發教授

國立臺北科技大學/管理學院/工商管理研究所/博士(2012年)

https://doi.org/10.6841/NTUT.2012.00050

摘要

確定性的全域最佳化演算法普遍應用在各種工程與管理的問題，運用最佳化演算法在管理方面可量化並結構化獲得最佳決策，而在工程最佳化方面要求絕對的精確度，因此全域最佳解成為求解的重點。然而實際的工程與管理問題所建構的數學模型大部份皆為非凸規劃(nonconvex programming)模型，無法以簡單的最佳化演算法求得全域最佳解。若能將非凸規劃轉換為凸規劃(convex programming)，便能以簡單的確定性最佳化演算法求得全域最佳解。因此，許多凸化(convexification)方法皆探討如何將非凸函數有效率的轉換為凸函數以確保獲得全域最佳解。然而為確保求解品質，模型中的非凸函數通常需要運用不同的凸化方法來轉換，此外，由函數轉換而產生的非線性(nonlinear)限制式需透過線性化(linearization)來達成獲得全域最佳解的目的。因此，本研究運用全域最佳化演算法求解不同的工程與管理問題以獲得全域最佳解，透過整合運用不同的凸化方法，同時將模型中包括正(posynomial)與非正(signomial)的非凸函數轉換為凸函數，接著，利用逐段線性化(piecewise linearization)方法將非線性限制式線性化，使模型成為一凸規劃模型達成確保獲取全域最佳解的目的。本研究主要具有以下優點，首先，全域最佳化演算法在工程與管理的應用方面能夠獲得滿足各條件下的精確解答以及最佳決策。第二是相較於啟發式演算法，本研究所探討的最佳化演算法可保證其解為全域最佳解。第三，本研究所探討的最佳化演算法能夠以最少的限制式與二元變數進行轉換，相較於其他確定性演算法為最有效率之演算法。第四，本研究運用多重解演算法獲取最佳的替代策略，提昇最佳化管理應用方面的決策彈性，使企業具備快速應變的能力。

關鍵字

全域最佳化 ； 凸化 ； 線性化 ； 管理科學

並列摘要

Deterministic global optimization has been applied in many applications of engineering and management area. Global optimization enables management problems to obtain an optimal decision, and applications to engineering problems usually require very precise solution. Thus the global optimal solution of the applications plays critical roles. These real-world optimization problems lead to nonconvex problems. In most of the previously study on engineering and management problems involving nonconvexties, the emphasis has not been on global optimization since it is difficult to globally optimize such models. However, most nonconvex problems cannot be dealt with by conventional optimization algorithms to guarantee global optimality. Therefore, deterministic optimization approaches have been developed for convexifying the nonconvex function to obtain globally optimal solutions. This dissertation utilizes deterministic optimization approach to find the global optimum of various engineering and management problems. The presented deterministic optimization approach transforms a nonconvex program into a convex program by convexification and linearization techniques and is thus guaranteed to reach a global optimum. The advantages of this study are summarized as follows. First, deterministic global optimization applications to engineering and management problems can obtain precise solution and optimal decision. Second, the obtained solution is guaranteed to reach a global optimum thus better than heuristic algorithms. Third, compared with other deterministic methods, the presented method utilizes less additional binary variables and constraints to reformulate the problem. Then the computational efficiency can be improved greatly. Fourth, the presented approach finds alternative optimal solutions to enhance the flexibility of the decision making.

並列關鍵字

Global optimization ； Convexification ； Linearization ； Management science

參考文獻

[1]Abdel-Malek, L. and Areeratchakul, N. A. (2007). Quadratic programming approach to the multi-product newsvendor problem with side constraints. European Journal of Operational Research, 176(3), 1607-1619.

[2]Abdel-Malek, L., Montanari, R. and Morales, L.C. (2003). Exact, approximate, and generic iterative models for the multi-product newsboy with budget constraint. International Journal of Production Economics, 91(2), 189-198.

[3]Adjiman, C.S., Androulakis, I.P. and Floudas, C.A. (2000). Global optimization of mixed integer nonlinear problems. AICHE Journal, 46(9), 1769-1797.

[4]A1-Khayyal, F.A., Larsen, C. and Voorhis, T. A. Van. (1995). Relaxation method for nonconvex quadratically constrained quadratic programs. Journal of Global Optimization, 6(3), 215-230.

[5]Akhtar, S. Tai, K. and Ray, T. (2002). A socio-behavioural simulation model for engineering design optimization. Engineering Optimization, 34(4), 341-354.