Abstract
近幾年來多目標線性規劃 (MOLP) 問題愈來愈受重視. 早期都是以 Simplex 演算法來解多目標線性規劃問題.在 1993-1994 年, Arbel 和 Oren 才首次提出了以內點法(interior-point methods) 來解多目標線性 規劃問題. 在本文中, 我們將根據 Arbel 的一篇primal-dual 解多目標 線性規劃問題內點法(primal-dual interior point MOLP algorithm),提 出其改進版本.在假設決策者 (Decision Maker) 明確地知道其價值函數 (utility function)為線性的情況下, 我們証明我們改進的版本是具有嚴 格遞增的性質.我們利用此改進的內點法去解三十四個由 Netlib 問題所 造出來的大型 MOLP 問題.據我們所知, 我們是首位使用 MOLP 內點法來 解大型的 MOLP 問題.我們所得的數值結果不很令人滿意. 我們的內點法 不能找到價值函數問題(utility program) 的最佳解. 我們將指出兩個可 能改進的研究方向. 以下為論文內容大綱. 第一節, 介紹多目標線性規劃 問題.第二節, 介紹 Arbel 解多目標線性規劃問題的 primal-dual 內點 法. 第三節, 提出我們改進版本的演算法並証明其收斂至邊界點. 第四 節, 改進版演算法的數值實驗. 第五節, 一個 cycling 例子証明 Arbel 演算法不收斂. 第六節, 改進版演算法對大型問題的數值結果.第七節, 未來可能研究方向. Arbel and Oren present the first interion-point multiobjective linear programming(MOLP) algorithms, whichare based on the interior-point algorithms for solvingthe usual (single- objective) linear programs. In this paper, we develop a variation of Arbel's MOLP primal-dual interior algorithm. Under the assumption that Decision Makerhas an explicitly known linear utility function, we prove that ouralgorithm is strictly increasing in the utility.We apply this algorithm to large MOLP problems with linear utility functions, which come from the well known Netlib set test problems. As far as we know, we are the first to use an interior-point algorithm for solving large MOLP problems. Since large MOLP are difficult, the numerical results show that our algorithm in general can not find the optimal solutions of the utilityprograms to satisfactory accuracies. We point out the reasons why MOLP are difficult and two possible improvements for future research.