第一節(jié)單純形法的矩陣描述及改進(jìn)單純形法介紹

單純形法的矩陣描述改進(jìn)單純形法介紹返回繼續(xù)

單純形法的矩陣描述不妨設(shè)基為基變量非基變量設(shè)線性規(guī)劃問題則

單純形法的矩陣描述其中令得當(dāng)前的基解為：當(dāng)前基解約束方程組當(dāng)前目標(biāo)值目標(biāo)函數(shù)令得當(dāng)前的目標(biāo)函數(shù)值為：

單純形法的矩陣描述當(dāng)前檢驗(yàn)數(shù)

單純形法的矩陣描述檢驗(yàn)數(shù)其中當(dāng)前對(duì)應(yīng)的系數(shù)列矩陣單純形法計(jì)算的描述線性規(guī)劃問題化為標(biāo)準(zhǔn)型，引入松弛變量初始單純形表非基變量基變量初始基變量矩陣單純形法計(jì)算的描述基變量非基變量當(dāng)基變量為時(shí)，新的單純形表矩陣單純形法計(jì)算的描述當(dāng)前檢驗(yàn)數(shù)當(dāng)前基解修正單純形法簡(jiǎn)介原因：

單純形法的目的是要求問題的最優(yōu)解，而在迭代過程中，單純形表中的某些列與求最優(yōu)解關(guān)系不大。因此，對(duì)單純形法進(jìn)行修正。需要換入的變量對(duì)應(yīng)的列思路：每次迭代關(guān)鍵求出修正單純形法的優(yōu)點(diǎn)：能夠從問題的原來參數(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)：尋求初始可行解，方法與單純形法相同。其迭代過程如下：確定換入變量，方法與單純形法相同。確定換出變量，方法與單純形法相同。確定新的基可行解：首先導(dǎo)出B-1然后計(jì)算XB=B-1b迭代終止原則與單純形法相同。修正單純形法簡(jiǎn)介第二節(jié)變量有界的

大規(guī)模線性規(guī)劃返回1、基本可行解概念的推廣考慮線性規(guī)劃問題：A為m*n,秩為m基本解X(0)：X(0)為AX=b的一個(gè)解，其中m個(gè)分量對(duì)應(yīng)A的列線性無關(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ī)劃（LP）的一個(gè)基本可行解，若對(duì)每個(gè)取下界值的非基變量，有對(duì)每個(gè)取上界值的非基變量，有則x是最優(yōu)解。討論最優(yōu)性條件3、計(jì)算步驟例、解下列線性規(guī)劃問題：第三節(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ì)相同類型的單位（部門）進(jìn)行相對(duì)有效性或效益評(píng)價(jià)的一種新的系統(tǒng)分析方法。它是處理多目標(biāo)決策問題的好方法。

重要概念決策單元（DecisionMakingUnits,簡(jiǎn)稱DMU）

一個(gè)經(jīng)濟(jì)系統(tǒng)可以看成一個(gè)單元在一定可能范圍內(nèi)，通過投入一定數(shù)量的生產(chǎn)要素并產(chǎn)出一定數(shù)量的產(chǎn)品的活動(dòng)，這樣的單元就被稱為決策單元。(當(dāng)然，一個(gè)單元的不同時(shí)間階段也可以看做是不同的決策單元）。特點(diǎn)：具有一定的輸入和輸出在將輸入轉(zhuǎn)換成輸出的過程中，努力實(shí)現(xiàn)自身的決策目標(biāo)。重要概念決策單元的相對(duì)有效性

評(píng)價(jià)的依據(jù)是決策單元的“輸入”和“輸出”數(shù)據(jù)，根據(jù)輸入和輸出數(shù)據(jù)來評(píng)價(jià)決策單元的優(yōu)劣。決策單元的相對(duì)有效性（即決策單元的優(yōu)劣）被稱為DEA有效，它用數(shù)學(xué)規(guī)劃模型計(jì)算比較決策單元之間的相對(duì)效率，為評(píng)價(jià)對(duì)象作出評(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ǔ)上，我們來判斷是否真的滿足該條件。因此，我們假設(shè)該決策單元的第i項(xiàng)投入為產(chǎn)出為且構(gòu)造數(shù)學(xué)模型我們進(jìn)行檢驗(yàn)，先假設(shè)存在其他的決策單元組合的產(chǎn)出不低于而且投入盡可能的比小，構(gòu)造數(shù)學(xué)模型如下：

求解并判斷

當(dāng)求解結(jié)果為時(shí)，說明存在其他的決策單元比該決策單元更滿足條件，所以，該決策單元非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)出單位：處理筆數(shù)/月解：根據(jù)數(shù)據(jù)包絡(luò)法，我們假設(shè)構(gòu)造一個(gè)決策單元組合，

使得其第i個(gè)項(xiàng)的投入為

第r項(xiàng)的產(chǎn)出為

且

然后，讓我們以分理處1為例，將分理處1作為，來判斷分理處1的運(yùn)行是否DEA有效。建立數(shù)學(xué)模型如下：將該模型代入到Excel電子表格中進(jìn)行求解得θ=1。同理分別以分理處2，3，4作為要衡量的決策單元，得θ=0.966，1，1。因此，這幾個(gè)分理處的有效性見下表：分理處θ結(jié)論分理處11DEA有效分理處20.966非DEA有效分理處31DEA有效分理處41DEA有效DEA在評(píng)價(jià)城市發(fā)展的可持續(xù)性中的應(yīng)用案例背景分析目前對(duì)城市可持續(xù)發(fā)展影響最大的是環(huán)境問題。所以，我們把城市的可持續(xù)發(fā)展系統(tǒng)視作DEA中的一個(gè)決策單元，它具有特定的輸入輸出，在將輸入轉(zhuǎn)化成輸出的過程中，努力實(shí)現(xiàn)系統(tǒng)的可持續(xù)發(fā)展目標(biāo)。現(xiàn)在，我們利用DEA方法對(duì)天津市的可持續(xù)發(fā)展進(jìn)行評(píng)價(jià)。在這里選取具有代表性的指標(biāo)作為輸入變量和輸出變量。輸入變量：政府財(cái)政收入占GDP的比重、環(huán)保投資占GDP的比重、每千人科技人員數(shù)；輸出變量：經(jīng)濟(jì)發(fā)展（用人均GDP表示）、環(huán)境發(fā)展（用城市環(huán)境質(zhì)量指數(shù)表示，在計(jì)算過程中，城市環(huán)境指數(shù)的數(shù)值作了歸一化處理）。（具體數(shù)值見下表）序號(hào)決策單元政府財(cái)政收入占GDP的比重環(huán)保投資占GDP的比重每千人科技人員數(shù)人均GDP城市環(huán)境質(zhì)量指數(shù)1199014.400.6531.303621.000.002199116.900.7232.203943.000.093199215.530.7231.874086.670.074199315.400.7632.234904.670.135199414.170.7632.406311.670.376199513.330.6930.778173.330.597199612.830.6129.2310236.000.518199713.000.6328.2012094.330.449199813.400.7528.8013603.330.5810199914.000.8429.1014841.001.00同樣的,我們以序號(hào)1（1990年）為例建立數(shù)學(xué)模型同樣將該模型代入到Excel電子表格中進(jìn)行求解得θ=0.2854同理可得其他的θ的最優(yōu)解,所有決策單元的結(jié)果如下表所示:年份θ結(jié)論19900.2854非DEA有效19910.2902非DEA有效19920.2968非DEA有效19