1、線性規(guī)劃單純形法（優(yōu)選）線性規(guī)劃單純形法2緒論 歷史，性質(zhì)，應(yīng)用20世紀(jì)整個(gè)世界參與規(guī)模最大的事件是什么？第二次世界大戰(zhàn)！整個(gè)世界的資源都投入到了第二次世界大戰(zhàn)中。如何才能更好地利用資源，分配有限的資源，這是一個(gè)值得研究的問題。當(dāng)時(shí)在英國軍隊(duì)中率先成立了研究小組運(yùn)籌小組 來研究這些問題，這就是著名的OR小組.很快美軍中 也相繼成立了OR小組。戰(zhàn)爭 運(yùn)籌學(xué)誕生的溫床。 3緒論 歷史，性質(zhì)，應(yīng)用二戰(zhàn)中成功的運(yùn)籌學(xué)案例英國防空部門如何布置防空雷達(dá)，建立最有效的防空警報(bào)系統(tǒng)。英，美空軍如何提高對地面目標(biāo)轟炸的命中率。如何安排反潛飛機(jī)的巡邏飛行線路。深水炸彈的合理爆炸深度，摧毀德軍潛艇數(shù)增加400%。商

2、船如何編隊(duì)，遭潛艇攻擊時(shí)如何減少損失。 使船只受敵機(jī)攻擊時(shí)，中彈數(shù)由47%降到29%。這些研究大大提高了盟軍的作戰(zhàn)能力，為反法西斯 戰(zhàn)爭的最后勝利作出了巨大的貢獻(xiàn)！4緒論 歷史，性質(zhì)，應(yīng)用戰(zhàn)爭結(jié)束了！ 整個(gè)世界投入到了戰(zhàn)后的重建國家的經(jīng)濟(jì)之中。運(yùn)籌學(xué)的方法相繼在工業(yè)，農(nóng)業(yè)，經(jīng)濟(jì)，社會(huì)問題等各個(gè)領(lǐng)域中展開了應(yīng)用。與此同時(shí)，運(yùn)籌數(shù)學(xué)有了飛快的發(fā)展，并形成了許多運(yùn)籌學(xué)的分支。線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃，動(dòng)態(tài)規(guī)劃，圖與網(wǎng)絡(luò)分析，統(tǒng)籌方法，排隊(duì)論，存儲(chǔ)論，對策論，決策論，多目標(biāo)決策。5緒論 歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的性質(zhì)和特點(diǎn)一種哲學(xué)方法論; 研究“事”而非“物”; 科學(xué)性，實(shí)踐性，系統(tǒng)性，

3、綜合性;模型的特點(diǎn)系統(tǒng)優(yōu)化模型。運(yùn)籌學(xué) 為決策機(jī)構(gòu)在對其控制下業(yè)務(wù)活動(dòng)進(jìn)行決策時(shí)，提供以數(shù)量化為基礎(chǔ)的科學(xué)方法。運(yùn)籌學(xué) 一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解決實(shí)際中提出的專門問題。運(yùn)籌學(xué) 是一種給出問題壞的答案的藝術(shù)，否則問題的結(jié)果會(huì)更壞。6緒論 歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的工作步驟 運(yùn)籌學(xué)在解決大量實(shí)際問題的過程中形成了自己的工作步驟提出和形成問題。 即弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)，搜集有關(guān)資料;建立模型。 即把問題中可控變量，參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來;求解。用各種手段（主要是數(shù)學(xué)方法，也可用其他方法）將模型求解。解可以是最優(yōu)解

4、、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要可由求決策者提出。7緒論 歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的工作步驟解的檢驗(yàn)。首先檢查求解步驟和程序有無錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)問題；解的控制。通過控制解的變化過程決定是否要作一定的改變；解的實(shí)施。是指將解用到實(shí)際中必須考慮到實(shí)施的問題，如向?qū)嶋H部門講清解的用法，在實(shí)施中可能產(chǎn)生的問題和修改。8設(shè)線性規(guī)劃問題變量取值限制一般情況下，決策變量取正值（非負(fù)值）。正式提出了運(yùn)籌學(xué)的一個(gè)新領(lǐng)域數(shù)據(jù)包絡(luò)分析。線性規(guī)劃 Linear Programming（LP）AX b s.表中當(dāng)前所指基本可行解即為最優(yōu)解。X4= 50 - 2X1 - X2 （1.線性規(guī)

5、劃 Linear Programming（LP）按研究者對問題內(nèi)在機(jī)理的認(rèn)識(shí)直接構(gòu)造出模型。2X1+ X2 + X4 = 50a11x1 + a12x2 + a1nxn = b1am1x1 + am2x2 + + amnxn bm線性規(guī)劃 Linear Programming（LP）表中當(dāng)前所指基本可行解即為最優(yōu)解。唯一最優(yōu)解 X=（9/2，3/2）相對有效性評價(jià)問題例子（優(yōu)選）線性規(guī)劃單純形法線性規(guī)劃 Linear Programming（LP）緒論 歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的模型模型的三種基本形式 （1）形象模型，（2）模擬模型，（3）符號(hào)或數(shù)學(xué)模型。構(gòu)造模型是一種創(chuàng)造性勞動(dòng)，成功的模型往往

6、是科學(xué)和藝術(shù)的結(jié)晶，構(gòu)造模型的方法和思路通常有以下幾種9緒論 歷史，性質(zhì)，應(yīng)用直接分析法 按研究者對問題內(nèi)在機(jī)理的認(rèn)識(shí)直接構(gòu)造出模型。類比法 有些問題可以用不同方法構(gòu)造出模型；而這些模型的結(jié)構(gòu)性質(zhì)是類同的，這就可以互相類比。數(shù)據(jù)分析法 對有些問題的機(jī)理尚未了解清楚，若能搜集到與此問題密切有關(guān)的大量數(shù)據(jù)，或通過某些試驗(yàn)獲得大量數(shù)據(jù)，這就可以用統(tǒng)計(jì)分析法建摸。10緒論 歷史，性質(zhì)，應(yīng)用試驗(yàn)分析法 有些問題的機(jī)理不清，又不能作大量試驗(yàn)來獲得數(shù)據(jù)，這時(shí)只能通過做局部試驗(yàn)的數(shù)據(jù)加上分析來構(gòu)造模型。想定（構(gòu)想）法 當(dāng)有些問題的機(jī)理不清，又缺少數(shù)據(jù)，又不能作試驗(yàn)來獲得數(shù)據(jù)時(shí)，人們只能在已有的知識(shí)、經(jīng)驗(yàn)的基礎(chǔ)

7、上，對于未來可能發(fā)生的情況給出邏輯上合理的設(shè)想和描述。然后用已有的方法構(gòu)造模型，并不斷修正完善，直至比較滿意為止。11緒論 歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的主要應(yīng)用 二戰(zhàn)后運(yùn)籌學(xué)的應(yīng)用迅速轉(zhuǎn)向了民用，下面對某些重要領(lǐng)域給于簡述市場銷售廣告預(yù)算和媒介選擇、競爭性定價(jià)、新品開發(fā)、銷售計(jì)劃的制訂。（美）杜邦公司在五十年代起就非常重視將運(yùn)籌學(xué)用于如何做好廣告工作、產(chǎn)品定價(jià)、新品引入。生產(chǎn)計(jì)劃從總體確定生產(chǎn)、存儲(chǔ)和勞動(dòng)力的配合等計(jì)劃適應(yīng)波動(dòng)的需求計(jì)劃。巴基斯坦一重型制造廠用線性規(guī)劃安排生產(chǎn)計(jì)劃，節(jié)省10%的生產(chǎn)費(fèi)用。12緒論 歷史，性質(zhì)，應(yīng)用運(yùn)輸問題涉及空運(yùn)、水運(yùn)、公路、鐵路運(yùn)輸、管道運(yùn)輸?shù)取９肪W(wǎng)的設(shè)計(jì)和分析

8、，市內(nèi)公共汽車路線的選擇和行車時(shí)刻表的安排，出租車的調(diào)度等。人事管理需求估計(jì)，教育和培訓(xùn)，人員分配（各種指派問題），合理利用，人才評價(jià)等。設(shè)備維修，更新和可靠性等。13緒論 歷史，性質(zhì)，應(yīng)用計(jì)算機(jī)和信息系統(tǒng)內(nèi)存分配研究，網(wǎng)絡(luò)設(shè)計(jì)分析等。城市管理緊急服務(wù)系統(tǒng)的設(shè)計(jì)和運(yùn)用，區(qū)域布局規(guī)劃，管道網(wǎng)絡(luò)設(shè)計(jì)等。（美）曾用排隊(duì)論確定紐約市緊急電話站的值班人數(shù)，（加）設(shè)計(jì)城市警車配置和負(fù)責(zé)范圍、指揮接警后的行走路線等。對策研究價(jià)格競爭，中央與地方政府投資分配博弈，工會(huì)與雇主間的博弈。14第一講線性規(guī)劃 Linear Programming( LP )目標(biāo)規(guī)劃 Goal Programming( GP )整數(shù)規(guī)

9、劃 Integer Programming( IP ) 15表中當(dāng)前所指基本可行解即為最優(yōu)解。例 一連鎖餐飲企業(yè)擁有遍布全國的20家連鎖餐廳，每家餐廳的每周運(yùn)營時(shí)間、員工人數(shù)以及每周利潤和所占市場份額如下表在本例中，空軍基地有 7 個(gè)，分別記為 A 、B 、C 、D 、E 、F 、G 。X4= 50 2X1 X2 0B N I求各個(gè)分理處的運(yùn)行是否DEA有效。2X1+ X2 + X4 = 50使用DEA進(jìn)行評價(jià)，結(jié)果基本合理。緒論 歷史，性質(zhì)，應(yīng)用研究“事”而非“物”;綜上所述決策者所需考慮的區(qū)域內(nèi)各個(gè)化工廠應(yīng)處理的工業(yè)污水量 Xi應(yīng)滿足上述所有不等式方程。64X9 2.給定線性規(guī)劃問題（標(biāo)準(zhǔn)

10、形式）11 = 2X1 + X2X4 +0.復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要可由求決策者提出。am1 am2 amn緒論 歷史，性質(zhì)，應(yīng)用設(shè)線性規(guī)劃問題焦炭是產(chǎn)鋼必不可少的原料，每年 NBS 需要采購約11.第一章線性規(guī)劃及單純形法線性規(guī)劃 Linear Programming（LP）16引 言線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，也是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一。調(diào)查表明，在世界500家最大的企業(yè)中，有85%的企業(yè)都曾使用線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計(jì)的資金。解決有限資源在有競爭的使用方向中如何進(jìn)行最佳分配。線性規(guī)劃 Linear Programm

11、ing（LP）17本講中我們將討論什么是線性規(guī)劃問題，線性規(guī)劃問題的數(shù)學(xué)表示，基本理論、概念和求解方法。線性規(guī)劃問題是什么樣的一類問題呢？ 請看案例線性規(guī)劃 Linear Programming（LP）18線性規(guī)劃 Linear Programming（LP）曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。案 例 河流污染治理規(guī)劃問題19線性規(guī)劃 Linear Programming（LP）曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案 例 河流污染治理規(guī)劃問題20線性規(guī)劃 Linear Programm

12、ing（LP）曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。今日認(rèn)識(shí)未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案 例 河流污染治理規(guī)劃問題21線性規(guī)劃 Linear Programming（LP）今日認(rèn)識(shí)未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。曾幾何時(shí)長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案 例 河流污染治理規(guī)劃問題22線性規(guī)劃 Linear Programming（LP）案 例 河流污染治理規(guī)劃問題背景資料:長江流域某區(qū)

13、域內(nèi)有9化工廠，各廠每月產(chǎn)生的工業(yè)污水量如表1，流經(jīng)各化工廠的河流流量如表2，各化工廠治理工業(yè)污水的成本如表3。上游廠排放的污水流到相鄰下游廠以前，有20%可自然凈化。 根據(jù)環(huán)保標(biāo)準(zhǔn)河流中此種工業(yè)污水的含量不應(yīng)超過0.2%。從該區(qū)域整體考慮，各化工廠應(yīng)該分別處理多少工業(yè)污水才能既滿足環(huán)保要求，又使9化工廠治理工業(yè)污水的總費(fèi)用最少。23背景資料:線性規(guī)劃 Linear Programming（LP）化工廠11.2化工廠42化工廠72化工廠21化工廠51化工廠80.8化工廠33化工廠61化工廠91.5表-1 污水產(chǎn)生量 單位：萬m3表-2 流經(jīng)各化工廠的河流流量 單位：萬m3表-3 治理工業(yè)污水的

14、成本 單位：百萬元/萬m3化工廠1500化工廠41200化工廠71200化工廠2300化工廠5600化工廠8200化工廠31800化工廠6400化工廠9700化工廠13化工廠44化工廠71化工廠25化工廠55化工廠82化工廠32化工廠66化工廠9324線性規(guī)劃 Linear Programming（LP）194582637問題分析區(qū)域污染治理的決策各個(gè)化工廠應(yīng)處理的工業(yè)污水量（或應(yīng)排放的工業(yè)污水量）。區(qū)域污染治理的約束即滿足環(huán)保要求排放工業(yè)污水（區(qū)域內(nèi)河流中任何點(diǎn)檢測都應(yīng)符合環(huán)保標(biāo)準(zhǔn)）。區(qū)域污染治理的目標(biāo)總治理成本最少。 這類問題的共同特點(diǎn)三大要素決策，目標(biāo)，約束25線性規(guī)劃 Linear P

15、rogramming（LP）194582637建模分析設(shè)第i個(gè)化工廠應(yīng)處理的工業(yè)污水量為Xi萬m3，則根據(jù)問題描述的情況以化工廠1、2、 、9 加以分析則可得如下近似關(guān)系式對化工廠2應(yīng)有 （1X2）/ 300 0.2%對化工廠8應(yīng)有 （0.8X8）/200 0.2%對化工廠1應(yīng)有 （1.2X1）+ 0.8（1X2）+（0.8X8） /500 0.2%26線性規(guī)劃 Linear Programming（LP）194582637對化工廠9應(yīng)有 （1.5X9）/ 700 0.2%對化工廠7應(yīng)有 （2X7）+ 0.8（1.5X9） / 1200 0.2% 此外顯然還應(yīng)有 Xi 0 （i=1，2，3 8

16、，9）綜上所述決策者所需考慮的區(qū)域內(nèi)各個(gè)化工廠應(yīng)處理的工業(yè)污水量 Xi應(yīng)滿足上述所有不等式方程。我們將這些不等式方程構(gòu)成的方程組稱為污水治理的約束條件。27線性規(guī)劃 Linear Programming（LP）194582637另一方面污水治理的總成本可表示為Z Z = 3X1+ 5X2+ 2X3+ 4X4+ 5X5+ 6X6+ 1X7+ 2X8+ 3X9 而決策者的目標(biāo)是確定滿足約束條件的Xi使得Z取得最小值。將上述分析歸納后即可得如下數(shù)學(xué)符合模型28線性規(guī)劃 Linear Programming（LP）a11x1 + a12x2 + a1nxn = b1j aij E aij0 （i =

17、1，2，m，E1）數(shù)據(jù)包絡(luò)分析DEA問題線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃 Linear Programming（LP）min Z = 5X1+4X2a11x1 + a12x2 + a1nxn + xn+1 = b1max z = 2x1 + x2區(qū)域污染治理的約束即滿足環(huán)保要求排放工業(yè)污水（區(qū)域內(nèi)河流中任何點(diǎn)檢測都應(yīng)符合環(huán)保標(biāo)準(zhǔn)）。線性規(guī)劃 Linear Programming（LP）運(yùn)輸問題涉及空運(yùn)、水運(yùn)、公路、鐵路運(yùn)輸、管道運(yùn)輸?shù)取B ，XN，XS 0確定目標(biāo)函數(shù) 目標(biāo)函數(shù)決定線性規(guī)劃問題的優(yōu)化方向，是模型的重要組成部分。上游廠排放的污水流到相鄰下游廠以前，有20%可自然凈化。（美）曾用排隊(duì)論確

18、定紐約市緊急電話站的值班人數(shù)，（加）設(shè)計(jì)城市警車配置和負(fù)責(zé)范圍、指揮接警后的行走路線等。X1 = 25 0.線性規(guī)劃 Linear Programming（LP）而這些模型的結(jié)構(gòu)性質(zhì)是類同的，這就可以互相類比。s.長江流域某區(qū)域內(nèi)有9化工廠，各廠每月產(chǎn)生的工業(yè)污水量如表1，流經(jīng)各化工廠的河流流量如表2，各化工廠治理工業(yè)污水的成本如表3。3x2 + x3 = 9線性規(guī)劃 Linear Programming（LP）河流污染治理規(guī)劃問題數(shù)學(xué)模型（整理之后）194582637Min Z= 3X1 +5X2 +2X3 +4X4 +5X5 +6X6 +1X7 +2X8 +3X9 X2 0.4 X8 0.

19、4 X1 +0.8X2 +0.8X8 1.64 X9 0.1 X7 +0.8 X9 0.8 X4 +0.8X7 +0.64X9 2.16 X6 0.2 X5 +0.8X6 0.6 X3 +0.8X4 +0.8X5 +0.64X6 +0.64X7 +5.12X9 9.4 Xi 0 （i=1，2，3，4，5，6，7，8，9）s.t.29線性規(guī)劃 Linear Programming（LP）基本概念 線性規(guī)劃模型 Linear Programming Model 或 Linear Optimization Model 用線性規(guī)劃方法解決實(shí)際經(jīng)濟(jì)與管理問題的第一步是分析建立能夠完整描述和反映實(shí)際問題的

20、線性規(guī)劃模型。30線性規(guī)劃 Linear Programming（LP）基本概念通常建立LP模型有以下幾個(gè)基本步驟確定決策變量 決策變量是模型要確定的未知變量，也是模型最重要的參數(shù)，是決策者解決實(shí)際問題的控制變量。確定目標(biāo)函數(shù) 目標(biāo)函數(shù)決定線性規(guī)劃問題的優(yōu)化方向，是模型的重要組成部分。實(shí)際問題的目標(biāo)可表示為決策變量的一個(gè)線性函數(shù)，并根據(jù)實(shí)際問題的優(yōu)化方向求其最大化（max）或最小化（min）。31線性規(guī)劃 Linear Programming（LP）基本概念 通常建立LP模型有以下幾個(gè)步驟確定約束方程一個(gè)正確的線性規(guī)劃模型應(yīng)能通過約束方程來描述和反映一系列客觀條件或環(huán)境的限制，這些限制通過一系

21、列線性等式或不等式方程組來描述。變量取值限制一般情況下，決策變量取正值（非負(fù)值）。因此，模型中應(yīng)有變量的非負(fù)約束即Xj0，但要注意也存在例外的情形。32線性規(guī)劃 Linear Programming（LP）基本概念線性規(guī)劃的一般形式: max（或min）z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn （ = ）b1 a21x1 + a22x2 + a2nxn （ = ）b2 s.t. am1x1 + am2x2 + amnxn （ = ）bm xj 0 （j=1，2 n）33線性規(guī)劃 Linear Programming（LP）基本概念線性規(guī)劃問題

22、的標(biāo)準(zhǔn)形式1、目標(biāo)函數(shù)極大化 “ max ”2、等式約束條件 “ = ” 且右端常數(shù)bi非負(fù)3、變量非負(fù) “ xj 0 ” max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s.t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）34線性規(guī)劃 Linear Programming（LP）基本概念化標(biāo)準(zhǔn)形式的一般步驟目標(biāo)函數(shù)極小化“極大化”約束條件的右端項(xiàng) bi0 “bi0” 約束條件為不等式 或 “=”取值無約束（自由）變量“非負(fù)變量”取值非正

23、變量“非負(fù)變量”35線性規(guī)劃 Linear Programming（LP）基本概念線性規(guī)劃問題的求解解（圖解） 如何求解一般的線性規(guī)劃呢？ 下面我們分析一下簡單的情況 只有兩個(gè)決策變量的線性規(guī)劃問題，這時(shí)可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。36線性規(guī)劃 Linear Programming（LP）基本概念例1（page 11）max z = 2x1 + x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 037線性規(guī)劃 Linear Programming（LP）基本概念max z = 2x1 +

24、x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0唯一最優(yōu)解 X=（9/2，3/2）38線性規(guī)劃 Linear Programming（LP）基本概念例 max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 1.9X2 3.8 s.t. X1 + 1.9X2 10.2 X1 1.9X2 3.8 X1 ，X2 039x1 + x2 + x3 4a11x1 + a12x2 + a1nxn + xn+1 = b1很快美軍中 也相繼成立了OR小組。2X1 = 50 X2 X4然后用已有的方法構(gòu)造模型，并不斷修正完善，直至比較滿意為止。線性規(guī)劃 L

25、inear Programming（LP）Xi 0 （i=1，2，3 8，9）a21 a22 a2n每個(gè)廣告的成本（萬元）采用大 M 法求解線性規(guī)劃問題時(shí)可能出現(xiàn)的幾種情況線性規(guī)劃 Linear Programming（LP）至少要影響 500 萬人口；線性規(guī)劃 Linear Programming（LP）2、兩階段法第I 階段4X1+ 3X2 + X3 = 120Max Z = 50X1+30X2想定（構(gòu)想）法 當(dāng)有些問題的機(jī)理不清，又缺少數(shù)據(jù)，又不能作試驗(yàn)來獲得數(shù)據(jù)時(shí)，人們只能在已有的知識(shí)、經(jīng)驗(yàn)的基礎(chǔ)上，對于未來可能發(fā)生的情況給出邏輯上合理的設(shè)想和描述。如果該假想單元的各項(xiàng)產(chǎn)出均不低于 j

26、0 決策單元的各項(xiàng)產(chǎn)出，它的各項(xiàng)投入均低于 j0 決策單元的各項(xiàng)的各項(xiàng)投入。線性規(guī)劃 Linear Programming（LP）基本概念max Z = 2X1 + X2x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值 max Z=17.2可行域40線性規(guī)劃 Linea

27、r Programming（LP）基本概念max Z = 3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z min Z（3.8，4）34.2 = 3X1+5.7X2 綠色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max Z=34.2是唯一的。可行域41線性規(guī)劃 Linear Programming（LP）基本概念min Z = 5X1+4X2x1x2oX1 - 1.9X2 = 3.

28、8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域此點(diǎn)是唯一最優(yōu)解42線性規(guī)劃 Linear Programming（LP）基本概念min Z = 5X1+4X2x1x2oD可行域43線性規(guī)劃 Linear Programming（LP）基本概念max Z = 5X1+4X2x1x2oD可行域 max Z min Z最優(yōu)解目標(biāo)值Z趨于無窮44線性規(guī)劃 Linear Programming（LP）基本概念max Z

29、 = 5X1+4X2x1x2o可行解域?yàn)榭?5線性規(guī)劃 Linear Programming（LP）基本概念圖解法的啟示線性規(guī)劃問題解的可能情況 a.唯一最優(yōu)解 b.無窮多最優(yōu)解 c.無解（沒有有界最優(yōu)解，無可行解）若線性規(guī)劃問題的可行域非空，則可行域是一個(gè)凸集；若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的某個(gè)頂點(diǎn)上達(dá)到。46線性規(guī)劃 Linear Programming（LP）單純形法 單純形方法是G.B.Danzig于1947年首先發(fā)明的。近50年來，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。本節(jié)討論單純形法的基本概念、原理及算法。47線性規(guī)劃 L

30、inear Programming（LP）單純形法給定線性規(guī)劃問題（標(biāo)準(zhǔn)形式） max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s .t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）48線性規(guī)劃 Linear Programming（LP）單純形法一、線性規(guī)劃問題的解的概念 可行解 最優(yōu)解 基 基解（基本解） 基可行解 可行基49線性規(guī)劃 Linear Programming（LP）單純形法二、凸集及其頂點(diǎn) 凸集 頂點(diǎn)（極點(diǎn)）凸集凹集50

31、線性規(guī)劃 Linear Programming（LP）12345678基解（可行）基解（不可行）51線性規(guī)劃 Linear Programming（LP）單純形法三、線性規(guī)劃基本定理基本定理 1 線性規(guī)劃所有可行解組成的集合S= X | AX = b，X 0 是凸集。基本定理 2 X是線性規(guī)劃問題的基本可行解的充要條件為是 X 是凸集S= X | AX = b，X 0 的極點(diǎn)。基本定理 3 給定線性規(guī)劃問題， A是秩為 m 的 mn 矩陣， （i） 若線性規(guī)劃問題存在可行解，則必存在基本可行解 （ii）若線性規(guī)劃問題存在有界最優(yōu)解，則必存在有界最優(yōu)基本可行解。52線性規(guī)劃 Linear Pro

32、gramming（LP）單純形法單純形法迭代原理及其思路單純形法的初步討論例1.8 求解LP問題 化為標(biāo)準(zhǔn)型Max Z = 50X1+30X2s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0Max Z = 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 X1，X2，X3，X4 0（1.18）53線性規(guī)劃 Linear Programming（LP）單純形法 此線性規(guī)劃問題轉(zhuǎn)化為了一個(gè)含有四個(gè)變量的標(biāo)準(zhǔn)形線性規(guī)劃問題，X3，X4為松弛變量。為求解上面的LP問題，我們要考慮滿足約束條件s.t.并使 Z 取得Max的X1，X2

33、，X3，X4的值，由此分析如下54線性規(guī)劃 Linear Programming（LP）單純形法確定初始基可行解 通過觀察可以發(fā)現(xiàn)，松弛變量X3和X4對應(yīng)的等式約束條件中的系數(shù)矩陣為單位矩陣可以作為初始可行基矩陣。因此取 X3，X4為基變量；X1，X2為非基變量。則（1.18）可變?yōu)?Max Z = 50X1+30X2 s.t. X3 = 120 - 4X1 - 3X2 X4= 50 - 2X1 - X2 （1.19） X1，X2，X3，X4055線性規(guī)劃 Linear Programming（LP）單純形法典式（1.19）或（1.18）稱為關(guān)于基的典式 1、等式約束條件中顯含基可行解 2、目

34、標(biāo)函數(shù)中不含基變量Max Z = 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 ( 1.18 ) X1，X2，X3，X4 0Max Z =50X1+30X2s.t. X3 = 120 - 4X1 - 3X2 X4= 50 - 2X1 - X2 （1.19 ） X1，X2，X3，X4056線性規(guī)劃 Linear Programming（LP）單純形法 在典式（1.19）中令 X1=X2 =0，我們得到一個(gè)基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ，其對應(yīng)的目標(biāo)函數(shù)值 Z1 = 50X1 + 30X2 =

35、 057線性規(guī)劃 Linear Programming（LP）單純形法最優(yōu)性檢驗(yàn) 基本可行解 X1 是最優(yōu)解嗎？顯然不是。應(yīng)尋找更好的解。從問題的數(shù)學(xué)角度分析，在典式（1.19）的目標(biāo)函數(shù)中，非基變量X1，X2前的系數(shù)都為正，而此時(shí)的X1，X2均取零值，表明只要增加其值，則目標(biāo)函數(shù)值有增加的可能。因此，將目標(biāo)函數(shù)中系數(shù)為正的某一非基變量與某一基變量地位對換。58線性規(guī)劃 Linear Programming（LP）單純形法換基迭代 進(jìn)行換基就是要從非基變量中選一個(gè)變量入基，再從基變量中選一個(gè)變量出基。并且換基后仍需滿足 新的解仍是基本可行解； 目標(biāo)函數(shù)值將得到改善。59線性規(guī)劃 Linear

36、Programming（LP）單純形法選擇入基變量 由于在目標(biāo)函數(shù) Z1 =50X1+30X2 中X1，X2的系數(shù)都為正，哪一個(gè)入基都可使目標(biāo)函數(shù)值得到改善。對于求目標(biāo)函數(shù)極大化的問題，我們希望目標(biāo)值增加得越快越好，因此系數(shù)最大的X1入基。選擇出基變量 X1入基后，其值從零增加并由于約束條件的原因會(huì)引起其他變量的變化。由典式（1.19）以及變量必須取正值（可行）的條件，我們可以得到下列不等式關(guān)系 X3 = 120 4X1 3X2 0 X4= 50 2X1 X2 060線性規(guī)劃 Linear Programming（LP）單純形法 因?yàn)榈骕2仍為非基變量（仍會(huì)令其取值為零），則上式可簡化為

37、120 4X1 0 ，且 50 2X1 0 ， 由此可以看出，雖然我們希望X1入基后取正值，取值越大目標(biāo)值增加越大，但是 X1又得受到以上約束（保證其可行）。 顯然，當(dāng)取 X1 =min（120/4，50/2）=25時(shí)，才能使上述不等式成立，且此時(shí)恰使基變量X4變?yōu)榱悖@正好滿足非基變量必須取值零的條件，所以可令X4 出基，這樣，新的基變量變?yōu)閄3 ，X1 ，而 X2 ，X4 成了非基變量，則61線性規(guī)劃 Linear Programming（LP）單純形法約束方程變?yōu)?4X1+ X3 =120 3X2 2X1 = 50 X2 X4化簡后得新的典式方程 X3 = 20 X2 + 2X4 X1

38、= 25 0.5X2 0.5X462線性規(guī)劃 Linear Programming（LP）單純形法代入目標(biāo)函數(shù)可得 Z2 =1250+5X225X4 令非基變量X2 =X4 = 0，即可得一個(gè)新的基本可行解 X2 =（ 25，0，20，0）T ，其對應(yīng)的目標(biāo)函數(shù)值Z2 =1250，并完成了第一次迭代。由于目標(biāo)函數(shù) Z2 =1250+5X225X4中X2的系數(shù)仍為正，該解X2仍不是最優(yōu)解。重復(fù)上述迭代過程得到X2入基，X3出基，則新的典式方程變?yōu)?X1 = 15 +0.5X3 1.5X4 X2 =20 X3 + 2X4 Z3 =1350 5X3 15X463線性規(guī)劃 Linear Program

39、ming（LP）單純形法第三個(gè)基本可行解 X3 =（ 15，20，0，0）T，其對應(yīng)的目標(biāo)函數(shù)值 Z3 = 1350 。此時(shí)松弛變量 都是非基變量（取值為零），這表明資源已用盡；并且目標(biāo)函數(shù)值 Z3 =1350 5X3 15X4中非基變量X3，X4的系數(shù)全為負(fù)值，說明目標(biāo)函數(shù)已無法進(jìn)一步改善，因此該解已是最優(yōu)解。64線性規(guī)劃 Linear Programming（LP）單純形法小結(jié) 單純形法是這樣一種迭代算法如下圖當(dāng) Zk 中非基變量的系數(shù)的系數(shù)全為負(fù)值時(shí)，這時(shí)的基本可行解 Xk 即是 線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。X1Z1保持單調(diào)增保持可行性保持可行性保持可行性保持可行性保持單調(diào)增保持單調(diào)

40、增保持單調(diào)增X2X3.XkZ2Z3.Zk 當(dāng) Zk 中非基變量的系數(shù)的系數(shù)全為負(fù)值時(shí)，這時(shí)的基本可行解 Xk 即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。65線性規(guī)劃 Linear Programming（LP）單純形表對于給定的線性規(guī)劃問題max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2s.t. am1x1 + am2x2 + + amnxn bm xj 0 （j=1，2 n） 對此問題添加m個(gè)松弛變量后，可得下面線性規(guī)劃問題并且是典式的形式。66線性規(guī)劃 Linear Program

41、ming（LP）單純形表線性規(guī)劃的典式max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2s.t. am1x1 + am2x2 + amnxn + xn+m = bm xj 0 （j=1，2 n，n+1，n+2，n+m）67線性規(guī)劃 Linear Programming（LP）單純形表 將上面典式中各變量及系數(shù)填寫在一張表格中就形成下面的單純形表cj c1 c2cn000CB基變量基解x1x2xnxn+1xn+2xn+m0 xn+1 b1a11a12a1n

42、110 xn+2 b2a21a22a2n120 xn+m bmam1am2amn1j = cj zj c1 c2cn00012nn+1n+2n+m基矩陣B=I非基矩陣N=ACNCBB-1b注意：在今后的迭代中基矩陣 B 會(huì)不斷地發(fā)生變化！XB68線性規(guī)劃 Linear Programming（LP）單純形表 上面的單純形表還可以表示成矩陣的形式基解 X XSXSb A Ij C 0基解 XB XN XSXSb B N Ij CB CN 0或69線性規(guī)劃 Linear Programming（LP）單純形法由單純形表進(jìn)行迭代步驟選擇 Xj 入基當(dāng) j 行中 j= max i i 0 選擇 Xi

43、出基當(dāng) i = min bi/aijaij 0 換基迭代當(dāng)確定了入基變量 Xj 、出基變量 Xi 后，以 aij 作為主元對單純形表進(jìn)行取主運(yùn)算，取主運(yùn)算即采用初等行變換將主元 aij 所在列，除將 aii 變換為1而外，該列中的其余元素都變換為 0。注意這種變換只能采用初等行變換!70線性規(guī)劃 Linear Programming（LP）單純形法最優(yōu)解檢驗(yàn)當(dāng)?shù)M(jìn)行至某一步時(shí)，j 行中所有檢驗(yàn)數(shù)均小于等于零，則迭代結(jié)束。表中當(dāng)前所指基本可行解即為最優(yōu)解。當(dāng)?shù)M(jìn)行至某一步時(shí)，j 行中所有檢驗(yàn)數(shù)均小于等于零，且此時(shí)至少有一個(gè)非基變量所對應(yīng)的檢驗(yàn)數(shù)k 等于零，則原線性規(guī)劃問題有無窮多個(gè)最優(yōu)解。當(dāng)

44、迭代進(jìn)行至某一步時(shí)，j 行中至少有一個(gè)檢驗(yàn)數(shù) k 大于零，且該檢驗(yàn)數(shù)對應(yīng)的列中a1k ，a2k ， amk ，均小于等于零，則原線性規(guī)劃問題最優(yōu)解無界（ max Z +）。71線性規(guī)劃 Linear Programming（LP）單純形方法的矩陣描述設(shè)線性規(guī)劃問題 max Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I 式） X 0 X ，XS 0其中 b 0 ，I 是 mm 單位矩陣。對上面（I 式）經(jīng)過迭代，并設(shè)最終的最優(yōu)基矩陣為B（不妨設(shè)B 為A 的首m 列，則將（I 式）改寫后有72線性規(guī)劃 Linear Programm

45、ing（LP）單純形方法的矩陣描述max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS 0 max Z = CB B -1+（CN- CB B -1）XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS 0 B 式中最優(yōu)目標(biāo)函數(shù)值Z*= CB B -1 ，檢驗(yàn)數(shù) CN - CB B -1 0 ， - CB B -1 0單純形方法迭代（I 式）（B 式）73線性規(guī)劃 Linear Programming（LP）單純形方法的矩陣描述基解 XB XN XSXSb B

46、 N Ij CB CN 0基解 XB XN XSXBB -1b I B -1N B -1j 0 CN - CB B 1N - CB B -1對應(yīng)I 式的單純形表 I 表對應(yīng)B 式的單純形表 B 表迭代74線性規(guī)劃 Linear Programming（LP）單純形表計(jì)算步驟舉例給定線性規(guī)劃問題max z = 50X1 + 30X2s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 075線性規(guī)劃 Linear Program

47、ming（LP）單純形表計(jì)算步驟舉例max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0Cj 503000基XB解B-1bX1X2X3X4X31204310X4502101檢驗(yàn)數(shù) j 503000初始單純形表：基矩陣B非基矩陣NCBCNB-1b基變量非基變量76線性規(guī)劃 Linear Programming（LP）單純形表計(jì)算步驟舉例max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0基X

48、B解B-1bX1X2X3X4X31204310X4502101檢驗(yàn)數(shù) j 5030002120/450/2X111/201/2250201- 2050- 2520/125211X2150- 1/23/210- 5- 1577線性規(guī)劃 Linear Programming（LP）單純形法的進(jìn)一步討論人工變量法 當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們或可得到一個(gè)顯然的基本可行解（如松弛變量作為基變量的一個(gè)初始基本可行解），這樣我們就可以馬上進(jìn)入單純形表的運(yùn)算步驟。然而，并非所有問題標(biāo)準(zhǔn)化之后我們都可得到一個(gè)顯然的初始基本可行解，這時(shí)就需要我們首先確定出一個(gè)基本可行解作為初始基本可行解。通常采用的是人工

49、變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法 大M法（罰因子法） 兩階段法78線性規(guī)劃 Linear Programming（LP）單純形法的進(jìn)一步討論1、大 M 法（罰因子法）max z = - 3X1 + X3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0LPM max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ，

50、 x5 ， x6 ， x7 079線性規(guī)劃 Linear Programming（LP）1、大 M 法LPM max z = - 3x1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j-30100-M-M80線性規(guī)劃 Linear Programming（LP）1、大 M

51、法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j-3-2M4M10-M0081線性規(guī)劃 Linear Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗(yàn)數(shù) j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21

52、-10-110X7660403-31檢驗(yàn)數(shù) j-3+6M01+4M03M-4M082線性規(guī)劃 Linear Programming（LP）1、大 M 法基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗(yàn)數(shù) j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù) j00301.5-1.5-M0.5-M83線性規(guī)劃 Linear Programming（LP）1、大 M 法基XB解B-1bX1X

53、2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2檢驗(yàn)數(shù) j00301.5-1.5-M0.5-M基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4檢驗(yàn)數(shù) j-9/2000-3/43/4-M-1/4-M84線性規(guī)劃 Linear Programming（LP）采用大 M 法求解線性規(guī)劃問題時(shí)可能出現(xiàn)的幾種情況當(dāng)采用單純形法求解 LPM 得到最優(yōu)解時(shí)，基變量不含任何人工變量，則所得到的最優(yōu)解就是原問題的

54、最優(yōu)解；當(dāng)采用單純形法求解 LPM 得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人工變量且非零，則原問題無可行解；當(dāng)采用單純形法求解 LPM 得到最優(yōu)解時(shí)，基變量至少含有一個(gè)人工變量且人工變量都為零，則通過變換得到原問題最優(yōu)解；85線性規(guī)劃 Linear Programming（LP）2、兩階段法max z = - 3X1 + X3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0I階段問題 max z = x6 x7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7

55、 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 086線性規(guī)劃 Linear Programming（LP）2、兩階段法I 階段問題 max z = x6 x7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j00000-1-187線性規(guī)劃 Linear Programming（LP）2、兩階段法第I 階

56、段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j00000-1-1基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗(yàn)數(shù) j-2400-10088線性規(guī)劃 Linear Programming（LP）2、兩階段法第I 階段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗(yàn)數(shù) j-2400-100基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X76

57、60403-31檢驗(yàn)數(shù) j60403-4089線性規(guī)劃 Linear Programming（LP）2、兩階段法第I 階段基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗(yàn)數(shù) j60403-40基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù) j00000-1-190線性規(guī)劃 Linear Programming（LP）2、兩階段法第II 階段基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/

58、2X23011/30001/3X11102/301/2-1/21/6檢驗(yàn)數(shù) j00000-1-1基XB解B-1bX1X2X3X4X5X400001-1/2X23011/300X11102/301/2檢驗(yàn)數(shù) j00303/2-3010091線性規(guī)劃 Linear Programming（LP）2、兩階段法第II 階段基XB解B-1bX1X2X3X4X5X400001-1/2X23011/3009X11102/301/23/2檢驗(yàn)數(shù) j00303/2基XB解B-1bX1X2X3X4X5X400001-1/2X25/2-1/2100-1/4X33/23/20103/4檢驗(yàn)數(shù) j-9/2000-3/4

59、92線性規(guī)劃 Linear Programming（LP）單純形法中的幾個(gè)問題目標(biāo)函數(shù)極小化時(shí)，解的最優(yōu)判別 j 0退化 一個(gè)或幾個(gè)基變量等于零，一個(gè)簡單易行的避免退化的方法是1974年由勃蘭德（Bland）提出的Bkand 法則。無可行解的判別 在采用人工變量求解線性規(guī)劃問題得到最優(yōu)解時(shí)，如果基變量中仍含有非零人工變量，則原問題無可行解。93線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA （date envelopment analysis）引言 一種基于線性規(guī)劃的用于評價(jià)同類型組織（或項(xiàng)目）工作績效相對有效性的特殊工具手段。這類組織例如學(xué)校、醫(yī)院、銀行的分支機(jī)構(gòu)、

60、超市的各個(gè)營業(yè)部等，各自具有相同的投入相同的產(chǎn)出。衡量這類組織之間的績效高低，通常采用投入產(chǎn)出比這個(gè)指標(biāo)，當(dāng)各自的投入產(chǎn)出均可折算成同一單位計(jì)量時(shí)，容易計(jì)算出各自的投入產(chǎn)出比并按其大小進(jìn)行績效排序。但當(dāng)被衡量的同類型組織有多項(xiàng)投入和多項(xiàng)產(chǎn)出，且不能折算成統(tǒng)一單位時(shí)，就無法算出投入產(chǎn)出比的數(shù)值，因而，需采用一種全新的方法進(jìn)行績效比較。這種方法就是二十世紀(jì)七十年代末產(chǎn)生的數(shù)據(jù)包絡(luò)分析DEA。94線性規(guī)劃 Linear Programming（LP）數(shù)據(jù)包絡(luò)分析DEA （date envelopment analysis）引言 1978年，著名運(yùn)籌學(xué)家、美國德克薩斯大學(xué)教授A.Charnes及W.W