Abstract
在這篇論文當中，我們要解決從經濟模型來的大型DYNAMIC LEONTIEF TYPE 線性規劃問題。我們採用不同於以前的SIMPLEX METHOD線性規劃問題。我們採用不同於以前的SIMPLEX METHOD，而用GILL ET. AL.的PROJECTED NEWTON BARRIER METHOD 類似於KARMARKAR'S METHOD而最小平方問題是這個方法中最費時的部份，我們將DYNAMIC LEONTIEF TYPE 的限制矩陣展開，發現能將一個大型矩陣化成一個NARROW BAND 矩陣。所以，我們能夠有效地解決這個問題。在第一節中，我們從一個多工廠的公司生產模型介紹DYNAMIC LEONTIEF TYPE PROBLEM 。假設它有ｍ個工廠且分成Ｔ個時段來生產，每一個工廠都有相互的關係（用矩陣Ａ來表示）要滿足每個時段的需求及要增加生產能力（用矩陣Ｂ來表示）在這種條件的限制下，求最小的生產成本。而這種問題基本上就是線性規劃的問題。在第二節中，我們介紹GILL ET. AL.的PROJECTED NEWTON BARRIER METHOD 而引出最小平方問題。對於在PHASE Ⅰ及PHASE Ⅱ的限制，矩陣是差RANK ONE，而在PHASE Ⅱ我們能夠有效地解決這個問題。在PHASE Ⅰ我們利用SHERMAN-MORRISON公式，使得只要比PHASE Ⅱ多兩次內積與一次BACKWAR AND FORWARD SUBSITUTION 就能解決。對於PROJECTED NEWTON BARRIER METHOD 的LINE SEARCH 部分，我們藉著GILL ET. AL.所提供的概念找出一種方法能夠在很少的SEARCH次數中找出滿足遞減的條件。在第三節中，我們對DYNAMIC LEONTIEF TYPE 線性規劃的最小平方問題做詳細的分析，利用BLOCK ELIMINATION 將NORMAL EQUATION 的大型矩陣化成BAND矩陣並且計算它的運算次數比一般的方法快約Ｏ（Ｔ2 ）佔，而且這種方法的穩定問題並不會太差。在第四節，是討論數值的結果及收斂的條件並分析對SIMPLEX 及PROJECTED NEWTONBARRIER METHOD的運算次數與實驗的結果。第五節，結論：如果最小平方問題能夠有效地被解決那PROJECTED NEWTON BARRIER METHOD 就能成功，我們的方法對Ａ，Ｂ矩陣是DENSE 且ｍ小Ｔ大增進較大。我們相信如對Ａ，Ｂ矩陣是SPARSE的話最小平方問題PRECONDITIONED CONJUGATE METHOD 會比我們的好。對Ａ，Ｂ矩陣在每個時段不一樣，我們的方法依舊適用。