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

2、船如何編隊，遭潛艇攻擊時如何減少損失。 使船只受敵機攻擊時，中彈數由47%降到29%。這些研究大大提高了盟軍的作戰能力，為反法西斯 戰爭的最后勝利作出了巨大的貢獻！4緒論 歷史，性質，應用戰爭結束了！ 整個世界投入到了戰后的重建國家的經濟之中。運籌學的方法相繼在工業，農業，經濟，社會問題等各個領域中展開了應用。與此同時，運籌數學有了飛快的發展，并形成了許多運籌學的分支。線性規劃，非線性規劃，整數規劃，目標規劃，動態規劃，圖與網絡分析，統籌方法，排隊論，存儲論，對策論，決策論，多目標決策。5緒論 歷史，性質，應用運籌學的性質和特點一種哲學方法論; 研究“事”而非“物”; 科學性，實踐性，系統性，

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

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

5、劃 Linear Programming（LP）按研究者對問題內在機理的認識直接構造出模型。2X1+ X2 + X4 = 50a11x1 + a12x2 + a1nxn = b1am1x1 + am2x2 + + amnxn bm線性規劃 Linear Programming（LP）表中當前所指基本可行解即為最優解。唯一最優解 X=（9/2，3/2）相對有效性評價問題例子（優選）線性規劃單純形法線性規劃 Linear Programming（LP）緒論 歷史，性質，應用運籌學的模型模型的三種基本形式 （1）形象模型，（2）模擬模型，（3）符號或數學模型。構造模型是一種創造性勞動，成功的模型往往

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

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

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

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

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

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

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

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

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

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

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

17、1，2，m，E1）數據包絡分析DEA問題線性規劃數學模型線性規劃 Linear Programming（LP）min Z = 5X1+4X2a11x1 + a12x2 + a1nxn + xn+1 = b1max z = 2x1 + x2區域污染治理的約束即滿足環保要求排放工業污水（區域內河流中任何點檢測都應符合環保標準）。線性規劃 Linear Programming（LP）運輸問題涉及空運、水運、公路、鐵路運輸、管道運輸等。XB ，XN，XS 0確定目標函數 目標函數決定線性規劃問題的優化方向，是模型的重要組成部分。上游廠排放的污水流到相鄰下游廠以前，有20%可自然凈化。（美）曾用排隊論確

18、定紐約市緊急電話站的值班人數，（加）設計城市警車配置和負責范圍、指揮接警后的行走路線等。X1 = 25 0.線性規劃 Linear Programming（LP）而這些模型的結構性質是類同的，這就可以互相類比。s.長江流域某區域內有9化工廠，各廠每月產生的工業污水量如表1，流經各化工廠的河流流量如表2，各化工廠治理工業污水的成本如表3。3x2 + x3 = 9線性規劃 Linear Programming（LP）河流污染治理規劃問題數學模型（整理之后）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線性規劃 Linear Programming（LP）基本概念 線性規劃模型 Linear Programming Model 或 Linear Optimization Model 用線性規劃方法解決實際經濟與管理問題的第一步是分析建立能夠完整描述和反映實際問題的

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

21、列線性等式或不等式方程組來描述。變量取值限制一般情況下，決策變量取正值（非負值）。因此，模型中應有變量的非負約束即Xj0，但要注意也存在例外的情形。32線性規劃 Linear Programming（LP）基本概念線性規劃的一般形式: 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線性規劃 Linear Programming（LP）基本概念線性規劃問題

22、的標準形式1、目標函數極大化 “ max ”2、等式約束條件 “ = ” 且右端常數bi非負3、變量非負 “ 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線性規劃 Linear Programming（LP）基本概念化標準形式的一般步驟目標函數極小化“極大化”約束條件的右端項 bi0 “bi0” 約束條件為不等式 或 “=”取值無約束（自由）變量“非負變量”取值非正

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

24、x2 5x2 15s.t. 6x1 + 2x2 24 x1 + x2 5 x1 ，x2 0唯一最優解 X=（9/2，3/2）38線性規劃 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然后用已有的方法構造模型，并不斷修正完善，直至比較滿意為止。線性規劃 L

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

26、0 決策單元的各項產出，它的各項投入均低于 j0 決策單元的各項的各項投入。線性規劃 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此點是唯一最優解，且最優目標函數值 max Z=17.2可行域40線性規劃 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 綠色線段上的所有點都是最優解這種情形為有無窮多最優解，但是最優目標函數值max Z=34.2是唯一的。可行域41線性規劃 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）可行域此點是唯一最優解42線性規劃 Linear Programming（LP）基本概念min Z = 5X1+4X2x1x2oD可行域43線性規劃 Linear Programming（LP）基本概念max Z = 5X1+4X2x1x2oD可行域 max Z min Z最優解目標值Z趨于無窮44線性規劃 Linear Programming（LP）基本概念max Z

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

30、inear Programming（LP）單純形法給定線性規劃問題（標準形式） 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線性規劃 Linear Programming（LP）單純形法一、線性規劃問題的解的概念 可行解 最優解 基 基解（基本解） 基可行解 可行基49線性規劃 Linear Programming（LP）單純形法二、凸集及其頂點 凸集 頂點（極點）凸集凹集50

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

32、gramming（LP）單純形法單純形法迭代原理及其思路單純形法的初步討論例1.8 求解LP問題 化為標準型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線性規劃 Linear Programming（LP）單純形法 此線性規劃問題轉化為了一個含有四個變量的標準形線性規劃問題，X3，X4為松弛變量。為求解上面的LP問題，我們要考慮滿足約束條件s.t.并使 Z 取得Max的X1，X2

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

34、標函數中不含基變量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線性規劃 Linear Programming（LP）單純形法 在典式（1.19）中令 X1=X2 =0，我們得到一個基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ，其對應的目標函數值 Z1 = 50X1 + 30X2 =

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

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

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

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

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

40、增保持單調增X2X3.XkZ2Z3.Zk 當 Zk 中非基變量的系數的系數全為負值時，這時的基本可行解 Xk 即是線性規劃問題的最優解，迭代結束。65線性規劃 Linear Programming（LP）單純形表對于給定的線性規劃問題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個松弛變量后，可得下面線性規劃問題并且是典式的形式。66線性規劃 Linear Program

41、ming（LP）單純形表線性規劃的典式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線性規劃 Linear Programming（LP）單純形表 將上面典式中各變量及系數填寫在一張表格中就形成下面的單純形表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 會不斷地發生變化！XB68線性規劃 Linear Programming（LP）單純形表 上面的單純形表還可以表示成矩陣的形式基解 X XSXSb A Ij C 0基解 XB XN XSXSb B N Ij CB CN 0或69線性規劃 Linear Programming（LP）單純形法由單純形表進行迭代步驟選擇 Xj 入基當 j 行中 j= max i i 0 選擇 Xi

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

44、迭代進行至某一步時，j 行中至少有一個檢驗數 k 大于零，且該檢驗數對應的列中a1k ，a2k ， amk ，均小于等于零，則原線性規劃問題最優解無界（ max Z +）。71線性規劃 Linear Programming（LP）單純形方法的矩陣描述設線性規劃問題 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 式）經過迭代，并設最終的最優基矩陣為B（不妨設B 為A 的首m 列，則將（I 式）改寫后有72線性規劃 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 式中最優目標函數值Z*= CB B -1 ，檢驗數 CN - CB B -1 0 ， - CB B -1 0單純形方法迭代（I 式）（B 式）73線性規劃 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對應I 式的單純形表 I 表對應B 式的單純形表 B 表迭代74線性規劃 Linear Programming（LP）單純形表計算步驟舉例給定線性規劃問題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線性規劃 Linear Program

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

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

49、變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法 大M法（罰因子法） 兩階段法78線性規劃 Linear Programming（LP）單純形法的進一步討論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線性規劃 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檢驗數 j-30100-M-M80線性規劃 Linear Programming（LP）1、大 M

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

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

53、2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2檢驗數 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檢驗數 j-9/2000-3/43/4-M-1/4-M84線性規劃 Linear Programming（LP）采用大 M 法求解線性規劃問題時可能出現的幾種情況當采用單純形法求解 LPM 得到最優解時，基變量不含任何人工變量，則所得到的最優解就是原問題的

54、最優解；當采用單純形法求解 LPM 得到最優解時，基變量至少含有一個人工變量且非零，則原問題無可行解；當采用單純形法求解 LPM 得到最優解時，基變量至少含有一個人工變量且人工變量都為零，則通過變換得到原問題最優解；85線性規劃 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線性規劃 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檢驗數 j00000-1-187線性規劃 Linear Programming（LP）2、兩階段法第I 階

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

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

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

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

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