單純形法的矩陣描述及改進單純形法介紹

《單純形法的矩陣描述及改進單純形法介紹》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第一節(jié)單純形法的矩陣描述及改進單純形法介紹單純形法的矩陣描述改進單純形法介紹返回繼續(xù)單純形法的矩陣描述不妨設基為基變量非基變量設線性規(guī)劃問題則單純形法的矩陣描述其中令得當前的基解為：當前基解約束方程組當前目標值目標函數(shù)令得當前的目標函數(shù)值為：單純形法的矩陣描述當前檢驗數(shù)單純形法的矩陣描述檢驗數(shù)其中當前對應的系數(shù)列矩陣單純形法計算的描述線性規(guī)劃問題化為標準型，引入松弛變量初始單純形表非基變量基變量初始基變量矩陣單純形法計算的描述基變量非基變量當基變量為時，新的單純形表矩陣單純形法計算的描述當前檢驗數(shù)當前基解修正單純形法簡介原因：單純形法的目的是要求問題的最優(yōu)解，

2、而在迭代過程中，單純形表中的某些列與求最優(yōu)解關系不大。因此，對單純形法進行修正。需要換入的變量對應的列思路：每次迭代關鍵求出修正單純形法的優(yōu)點：能夠從問題的原來參數(shù)（A，b，C），計算出單純形表中所有的數(shù)據(jù)，只要導出即可。單純形表中的任一數(shù)字，只要作部分的矩陣乘法即可獲得。修正單純形法簡介有關公式：當換入變量，換出變量時，新的為：修正單純形法簡介單純形乘子（行向量）其中確定新的換入變量確定新的換出變量有關公式：修正單純形法簡介修正單純形法要點：尋求初始可行解，方法與單純形法相同。其迭代過程如下：確定換入變量，方法與單純形法相同。確定換出變量，方法與單純形法相同

3、。確定新的基可行解：首先導出B-1然后計算XB=B-1b迭代終止原則與單純形法相同。修正單純形法簡介第二節(jié)變量有界的大規(guī)模線性規(guī)劃返回1、基本可行解概念的推廣考慮線性規(guī)劃問題：A為m*n,秩為m基本解X(0)：X(0)為AX=b的一個解，其中m個分量對應A的列線性無關，其余n-m個分量取上界或下界值?；究尚薪釾(0)：基本解X(0)中m個基變量的值介于上下界之間。推廣基本可行解的表達式：推廣基本可行解集與可行域凸集K的極點集等價2、基本可行解的改進設X(0)是一個基本可行解目標函數(shù)值討論最優(yōu)性條件換入變量？換出變量？設x是線性規(guī)劃（LP）的一個基本可行解，若

4、對每個取下界值的非基變量，有對每個取上界值的非基變量，有則x是最優(yōu)解。討論最優(yōu)性條件3、計算步驟例、解下列線性規(guī)劃問題：第三節(jié)可分解的大規(guī)模線性規(guī)劃返回學生討論報告線性規(guī)劃應用－－－數(shù)據(jù)包絡分析法數(shù)據(jù)包絡分析法（DataEnvelopmentAnalysis,簡稱DEA），是著名運籌學家A.Charnes和W.W.Copper等學者以“相對效率”概念為基礎，以凸分析和線性規(guī)劃為工具，根據(jù)多指標投入和多指標產出對相同類型的單位（部門）進行相對有效性或效益評價的一種新的系統(tǒng)分析方法。它是處理多目標決策問題的好方法。重要概念決策單元（DecisionMakingU

5、nits,簡稱DMU）一個經(jīng)濟系統(tǒng)可以看成一個單元在一定可能范圍內，通過投入一定數(shù)量的生產要素并產出一定數(shù)量的產品的活動，這樣的單元就被稱為決策單元。(當然，一個單元的不同時間階段也可以看做是不同的決策單元）。特點：具有一定的輸入和輸出在將輸入轉換成輸出的過程中，努力實現(xiàn)自身的決策目標。重要概念決策單元的相對有效性評價的依據(jù)是決策單元的“輸入”和“輸出”數(shù)據(jù)，根據(jù)輸入和輸出數(shù)據(jù)來評價決策單元的優(yōu)劣。決策單元的相對有效性（即決策單元的優(yōu)劣）被稱為DEA有效，它用數(shù)學規(guī)劃模型計算比較決策單元之間的相對效率，為評價對象作出評價。DEA步驟假設設某個DMU的輸入向量為

6、,輸出向量為。則n個（）對應的輸入、輸出向量分別為：而且即每個決策單元都有m種類型的輸入以及s種類型的輸出為第j個決策單元對第i種類型輸入的投入量；為第j個決策單元對第r種類型輸出的產出量。這些都是已知的數(shù)據(jù)。DEA步驟假設現(xiàn)在，我們是要最優(yōu)化這些決策單元，那么我們假設一個假想決策單元滿足產出最大，同時投入最小。在此基礎上，我們來判斷是否真的滿足該條件。因此，我們假設該決策單元的第i項投入為產出為且構造數(shù)學模型我們進行檢驗，先假設存在其他的決策單元組合的產出不低于而且投入盡可能的比小，構造數(shù)學模型如下：求解并判斷當求解結果為時，說明存在其他的決策單元比該決策單

7、元更滿足條件，所以，該決策單元非DEA有效；當時，該決策單元DEA有效。并可以根據(jù)所求得的最優(yōu)解重新分配各決策單元的比例，也就是系數(shù),再生成新的決策單元，又繼續(xù)檢驗。習題例8振華銀行的4個分理處的投入產出情況如表1-16所示。要求分別確定各分理處的運行是否DEA有效。分理處投入產出職員數(shù)營業(yè)面積（）儲蓄存取貸款中間業(yè)務分理處11514018002001600分理處22013010003501000分理處3211208004501300分理處4201359004201500表1-16產出單位：處理筆數(shù)/月解：根據(jù)數(shù)據(jù)包絡法，我們假設構造一個決策單元組合，使得

8、其第i個項的投入為第r項的產出為