連續多項式近似最佳解法及其應用

Abstract

Sherali及Tuncbilek在[17]一文中，利用重建構線性化的技巧，將連續多 項式轉成線性式並得到求解問題的最佳解。Sheraili及Tuncbilek的方法 是目前文獻上所知最好的連續多項式線性轉換法。本文提出一線性轉換法 ，將連續多項式轉為一個近似的零壹整數問題。利用這個方法，我們可以 求解多項式規劃問題的近似最佳解，並可以使轉換後每一多項式項的誤差 值小於最大容忍誤差值。本法之優點為 1、解題步驟較Sherali及 Tuncbilek的方法來得簡單；2、可以求得近似最佳解；3、可以設定最大 容忍誤差值以控制所求解答的精確程度。本文亦利用此方法來求解文獻 [21]上的多項式規劃問題，並且都可以得到其近似最佳解。此外，本文亦 以設施設計問題為例，說明本研究方法如何應用到實際問題中。 Sherali and Tuncbilek[17] uses a Reformulation Linearization Technique to linearize a polynomial term with continous variables and obtains a global optimum. This method is known as the best one of linearization transformation method in literatures. This thesis proposes a linearization approach to transform a polynomial term with continous variables as a approximated 0-1 integer program. By using this approach, we could obtain a approximated optimal solution and control the error value under the maximum tolerable error value. The proposed has some advantages as following: 1. the solving steps of the proposed approach are much easier than Sherali and Tuncbilek; 2. the proposed approach could obtain a approximated optimal solution; 3. the proposed approach can set maximum tolerable error value for the accuracy of the approximated solution. This thesis uses the proposed approach to solve some polynomial programs in literature [21] and can also obtain the approximated optimal solutions. Moreover, we illustrate that how this proposed approach applies to facility layout problem.