單純形法矩陣描述及改進(jìn)單純形法介紹

《單純形法矩陣描述及改進(jìn)單純形法介紹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第一節(jié)單純形法的矩陣描述及改進(jìn)單純形法介紹單純形法的矩陣描述改進(jìn)單純形法介紹返回繼續(xù)單純形法的矩陣描述不妨設(shè)基為基變量非基變量設(shè)線性規(guī)劃問(wèn)題則單純形法的矩陣描述其中令得當(dāng)前的基解為：當(dāng)前基解約束方程組當(dāng)前目標(biāo)值目標(biāo)函數(shù)令得當(dāng)前的目標(biāo)函數(shù)值為：?jiǎn)渭冃畏ǖ木仃嚸枋霎?dāng)前檢驗(yàn)數(shù)單純形法的矩陣描述檢驗(yàn)數(shù)其中當(dāng)前對(duì)應(yīng)的系數(shù)列矩陣單純形法計(jì)算的描述線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型，引入松弛變量初始單純形表非基變量基變量初始基變量矩陣單純形法計(jì)算的描述基變量非基變量當(dāng)基變量為時(shí)，新的單純形表矩陣單純形法計(jì)算的描述當(dāng)前檢驗(yàn)數(shù)當(dāng)前基解修正單純形法簡(jiǎn)介原因：?jiǎn)渭冃畏ǖ哪康氖且髥?wèn)題

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

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

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

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

6、象作出評(píng)價(jià)。DEA步驟假設(shè)設(shè)某個(gè)DMU的輸入向量為,輸出向量為。則n個(gè)（）對(duì)應(yīng)的輸入、輸出向量分別為：而且即每個(gè)決策單元都有m種類型的輸入以及s種類型的輸出為第j個(gè)決策單元對(duì)第i種類型輸入的投入量；為第j個(gè)決策單元對(duì)第r種類型輸出的產(chǎn)出量。這些都是已知的數(shù)據(jù)。DEA步驟假設(shè)現(xiàn)在，我們是要最優(yōu)化這些決策單元，那么我們假設(shè)一個(gè)假想決策單元滿足產(chǎn)出最大，同時(shí)投入最小。在此基礎(chǔ)上，我們來(lái)判斷是否真的滿足該條件。因此，我們假設(shè)該決策單元的第i項(xiàng)投入為產(chǎn)出為且構(gòu)造數(shù)學(xué)模型我們進(jìn)行檢驗(yàn)，先假設(shè)存在其他的決策單元組合的產(chǎn)出不低于而且投入盡可能的比小，構(gòu)造數(shù)學(xué)模型如下

7、：求解并判斷當(dāng)求解結(jié)果為時(shí)，說(shuō)明存在其他的決策單元比該決策單元更滿足條件，所以，該決策單元非DEA有效；當(dāng)時(shí)，該決策單元DEA有效。并可以根據(jù)所求得的最優(yōu)解重新分配各決策單元的比例，也就是系數(shù),再生成新的決策單元，又繼續(xù)檢驗(yàn)。習(xí)題例8振華銀行的4個(gè)分理處的投入產(chǎn)出情況如表1-16所示。要求分別確定各分理處的運(yùn)行是否DEA有效。分理處投入產(chǎn)出職員數(shù)營(yíng)業(yè)面積（）儲(chǔ)蓄存取貸款中間業(yè)務(wù)分理處11514018002001600分理處22013010003501000分理處3211208004501300分理處4201359004201500表1-16產(chǎn)出單位：

8、處理筆數(shù)/月解：根據(jù)數(shù)據(jù)包絡(luò)法，我們假設(shè)構(gòu)造一個(gè)決策單元組合，使得其第i個(gè)項(xiàng)的投入為第r項(xiàng)的產(chǎn)出為