線性規(guī)劃單純形法

線性規(guī)劃單純形法第一頁，共一百二十九頁，2022年，8月28日1《運籌學(xué)》課程

教學(xué)大綱課時安排：

序號

課程內(nèi)容

學(xué)時

1第一講管理運籌學(xué)序論

12第二講線性規(guī)劃93第二講線性規(guī)劃的對偶理論與靈敏度分析5第二講運輸問題3第二講目標(biāo)規(guī)劃44第四講整數(shù)規(guī)劃35第五講動態(tài)規(guī)劃86第七講圖與網(wǎng)絡(luò)分析77上機，習(xí)題課8第二頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用20世紀(jì)整個世界參與規(guī)模最大的事件是什么？第二次世界大戰(zhàn)！整個世界的資源都投入到了第二次世界大戰(zhàn)中。如何才能更好地利用資源，分配有限的資源，這是一個值得研究的問題。當(dāng)時在英國軍隊中率先成立了研究小組——運籌小組來研究這些問題，這就是著名的OR小組.很快美軍中也相繼成立了OR小組。戰(zhàn)爭——

運籌學(xué)誕生的溫床。第三頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用二戰(zhàn)中成功的運籌學(xué)案例：英國防空部門如何布置防空雷達(dá)，建立最有效的防空警報系統(tǒng)。英，美空軍如何提高對地面目標(biāo)轟炸的命中率。如何安排反潛飛機的巡邏飛行線路。深水炸彈的合理爆炸深度，摧毀德軍潛艇數(shù)增加400%。商船如何編隊，遭潛艇攻擊時如何減少損失。使船只受敵機攻擊時，中彈數(shù)由47%降到29%。這些研究大大提高了盟軍的作戰(zhàn)能力，為反法西斯戰(zhàn)爭的最后勝利作出了巨大的貢獻！第四頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用戰(zhàn)爭結(jié)束了！

整個世界投入到了戰(zhàn)后的重建國家的經(jīng)濟之中。運籌學(xué)的方法相繼在工業(yè)，農(nóng)業(yè)，經(jīng)濟，社會問題等各個領(lǐng)域中展開了應(yīng)用。與此同時，運籌數(shù)學(xué)有了飛快的發(fā)展，并形成了許多運籌學(xué)的分支。線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃，動態(tài)規(guī)劃，圖與網(wǎng)絡(luò)分析，統(tǒng)籌方法，排隊論，存儲論，對策論，決策論，多目標(biāo)決策。第五頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用運籌學(xué)的性質(zhì)和特點一種哲學(xué)方法論;研究“事”而非“物”;科學(xué)性，實踐性，系統(tǒng)性，綜合性;模型的特點——系統(tǒng)優(yōu)化模型。運籌學(xué)——

為決策機構(gòu)在對其控制下業(yè)務(wù)活動進行決策時，提供以數(shù)量化為基礎(chǔ)的科學(xué)方法。運籌學(xué)——

一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法，解決實際中提出的專門問題。運籌學(xué)——

是一種給出問題壞的答案的藝術(shù)，否則問題的結(jié)果會更壞。第六頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用運籌學(xué)的工作步驟

運籌學(xué)在解決大量實際問題的過程中形成了自己的工作步驟：提出和形成問題。即弄清問題的目標(biāo)，可能的約束，問題的可控變量以及有關(guān)參數(shù)，搜集有關(guān)資料;建立模型。即把問題中可控變量，參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來;求解。用各種手段（主要是數(shù)學(xué)方法，也可用其他方法）將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計算機，解的精度要可由求決策者提出。第七頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用運籌學(xué)的工作步驟解的檢驗。首先檢查求解步驟和程序有無錯誤，然后檢查解是否反映現(xiàn)實問題；解的控制。通過控制解的變化過程決定是否要作一定的改變；解的實施。是指將解用到實際中必須考慮到實施的問題，如向?qū)嶋H部門講清解的用法，在實施中可能產(chǎn)生的問題和修改。第八頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用運籌學(xué)的模型模型的三種基本形式：（1）形象模型，（2）模擬模型，（3）符號或數(shù)學(xué)模型。構(gòu)造模型是一種創(chuàng)造性勞動，成功的模型往往是科學(xué)和藝術(shù)的結(jié)晶，構(gòu)造模型的方法和思路通常有以下幾種：第九頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用直接分析法

按研究者對問題內(nèi)在機理的認(rèn)識直接構(gòu)造出模型。類比法

有些問題可以用不同方法構(gòu)造出模型；而這些模型的結(jié)構(gòu)性質(zhì)是類同的，這就可以互相類比。數(shù)據(jù)分析法

對有些問題的機理尚未了解清楚，若能搜集到與此問題密切有關(guān)的大量數(shù)據(jù)，或通過某些試驗獲得大量數(shù)據(jù)，這就可以用統(tǒng)計分析法建摸。第十頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用試驗分析法

有些問題的機理不清，又不能作大量試驗來獲得數(shù)據(jù)，這時只能通過做局部試驗的數(shù)據(jù)加上分析來構(gòu)造模型。想定（構(gòu)想）法當(dāng)有些問題的機理不清，又缺少數(shù)據(jù)，又不能作試驗來獲得數(shù)據(jù)時，人們只能在已有的知識、經(jīng)驗的基礎(chǔ)上，對于未來可能發(fā)生的情況給出邏輯上合理的設(shè)想和描述。然后用已有的方法構(gòu)造模型，并不斷修正完善，直至比較滿意為止。第十一頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用運籌學(xué)的主要應(yīng)用

二戰(zhàn)后運籌學(xué)的應(yīng)用迅速轉(zhuǎn)向了民用，下面對某些重要領(lǐng)域給于簡述：市場銷售廣告預(yù)算和媒介選擇、競爭性定價、新品開發(fā)、銷售計劃的制訂。（美）杜邦公司在五十年代起就非常重視將運籌學(xué)用于如何做好廣告工作、產(chǎn)品定價、新品引入。生產(chǎn)計劃從總體確定生產(chǎn)、存儲和勞動力的配合等計劃適應(yīng)波動的需求計劃。巴基斯坦一重型制造廠用線性規(guī)劃安排生產(chǎn)計劃，節(jié)省10%的生產(chǎn)費用。第十二頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用運輸問題涉及空運、水運、公路、鐵路運輸、管道運輸?shù)?。公路網(wǎng)的設(shè)計和分析，市內(nèi)公共汽車路線的選擇和行車時刻表的安排，出租車的調(diào)度等。人事管理需求估計，教育和培訓(xùn)，人員分配（各種指派問題），合理利用，人才評價等。設(shè)備維修，更新和可靠性等。第十三頁，共一百二十九頁，2022年，8月28日緒論

歷史，性質(zhì)，應(yīng)用計算機和信息系統(tǒng)內(nèi)存分配研究，網(wǎng)絡(luò)設(shè)計分析等。城市管理緊急服務(wù)系統(tǒng)的設(shè)計和運用，區(qū)域布局規(guī)劃，管道網(wǎng)絡(luò)設(shè)計等。（美）曾用排隊論確定紐約市緊急電話站的值班人數(shù)，（加）設(shè)計城市警車配置和負(fù)責(zé)范圍、指揮接警后的行走路線等。對策研究價格競爭，中央與地方政府投資分配博弈，工會與雇主間的博弈。第十四頁，共一百二十九頁，2022年，8月28日第一講線性規(guī)劃LinearProgramming(LP)目標(biāo)規(guī)劃GoalProgramming(GP)整數(shù)規(guī)劃IntegerProgramming(IP)第十五頁，共一百二十九頁，2022年，8月28日第一章線性規(guī)劃及單純形法線性規(guī)劃LinearProgramming（LP）第十六頁，共一百二十九頁，2022年，8月28日引言線性規(guī)劃是運籌學(xué)的一個重要分支，也是運籌學(xué)中應(yīng)用最廣泛的方法之一。調(diào)查表明，在世界500家最大的企業(yè)中，有85%的企業(yè)都曾使用線性規(guī)劃解決經(jīng)營管理中遇到的復(fù)雜問題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬計的資金。解決有限資源在有競爭的使用方向中如何進行最佳分配。線性規(guī)劃LinearProgramming（LP）第十七頁，共一百二十九頁，2022年，8月28日本講中我們將討論什么是線性規(guī)劃問題，線性規(guī)劃問題的數(shù)學(xué)表示，基本理論、概念和求解方法。線性規(guī)劃問題是什么樣的一類問題呢？請看案例線性規(guī)劃LinearProgramming（LP）第十八頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。案例河流污染治理規(guī)劃問題第十九頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第二十頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。今日認(rèn)識未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第二十一頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）今日認(rèn)識未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。曾幾何時長江水，哺育華夏代代人;誰知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問題第二十二頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）案例河流污染治理規(guī)劃問題背景資料:長江流域某區(qū)域內(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è)污水的總費用最少。第二十三頁，共一百二十九頁，2022年，8月28日背景資料:線性規(guī)劃LinearProgramming（LP）化工廠11.2化工廠42化工廠72化工廠21化工廠51化工廠80.8化工廠33化工廠61化工廠91.5表-1污水產(chǎn)生量單位：萬m3表-2流經(jīng)各化工廠的河流流量單位：萬m3表-3治理工業(yè)污水的成本單位：百萬元/萬m3化工廠1500化工廠41200化工廠71200化工廠2300化工廠5600化工廠8200化工廠31800化工廠6400化工廠9700化工廠13化工廠44化工廠71化工廠25化工廠55化工廠82化工廠32化工廠66化工廠93第二十四頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）194582637問題分析：區(qū)域污染治理的決策——各個化工廠應(yīng)處理的工業(yè)污水量（或應(yīng)排放的工業(yè)污水量）。區(qū)域污染治理的約束——即滿足環(huán)保要求排放工業(yè)污水（區(qū)域內(nèi)河流中任何點檢測都應(yīng)符合環(huán)保標(biāo)準(zhǔn)）。區(qū)域污染治理的目標(biāo)——總治理成本最少。這類問題的共同特點：三大要素決策，目標(biāo)，約束第二十五頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）194582637建模分析：設(shè)第i個化工廠應(yīng)處理的工業(yè)污水量為Xi萬m3，則根據(jù)問題描述的情況以化工廠1、2、…、9加以分析則可得如下近似關(guān)系式對化工廠2應(yīng)有

（1-X2）/300≦0.2%對化工廠8應(yīng)有

（0.8-X8）/200≦0.2%對化工廠1應(yīng)有

｛（1.2-X1）+0.8（1-X2）+（0.8-X8）｝/500≦0.2%第二十六頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）194582637對化工廠9應(yīng)有——

（1.5-X9）/700≦0.2%對化工廠7應(yīng)有——

（2-X7）+0.8（1.5-X9）

/1200≦0.2%……此外顯然還應(yīng)有

Xi≧0（i=1，2，3…8，9）綜上所述決策者所需考慮的區(qū)域內(nèi)各個化工廠應(yīng)處理的工業(yè)污水量Xi應(yīng)滿足上述所有不等式方程。我們將這些不等式方程構(gòu)成的方程組稱為污水治理的約束條件。第二十七頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）194582637另一方面污水治理的總成本可表示為ZZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9

而決策者的目標(biāo)是確定滿足約束條件的Xi使得Z取得最小值。將上述分析歸納后即可得如下數(shù)學(xué)符合模型：第二十八頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）河流污染治理規(guī)劃問題數(shù)學(xué)模型（整理之后）194582637MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9X2≧0.4X8≧0.4X1+0.8X2+0.8X8≧1.64X9≧0.1X7+0.8X9≧0.8X4+0.8X7+0.64X9≧2.16X6≧0.2X5+0.8X6≧0.6X3+0.8X4+0.8X5+0.64X6+0.64X7+5.12X9≧9.4Xi≧0（i=1，2，3，4，5，6，7，8，9）s.t.第二十九頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念

線性規(guī)劃模型——

LinearProgrammingModel

或LinearOptimizationModel

用線性規(guī)劃方法解決實際經(jīng)濟與管理問題的第一步是分析建立能夠完整描述和反映實際問題的線性規(guī)劃模型。第三十頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念通常建立LP模型有以下幾個基本步驟：確定決策變量：決策變量是模型要確定的未知變量，也是模型最重要的參數(shù)，是決策者解決實際問題的控制變量。確定目標(biāo)函數(shù)：目標(biāo)函數(shù)決定線性規(guī)劃問題的優(yōu)化方向，是模型的重要組成部分。實際問題的目標(biāo)可表示為決策變量的一個線性函數(shù)，并根據(jù)實際問題的優(yōu)化方向求其最大化（max）或最小化（min）。第三十一頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念

通常建立LP模型有以下幾個步驟：確定約束方程：一個正確的線性規(guī)劃模型應(yīng)能通過約束方程來描述和反映一系列客觀條件或環(huán)境的限制，這些限制通過一系列線性等式或不等式方程組來描述。變量取值限制：一般情況下，決策變量取正值（非負(fù)值）。因此，模型中應(yīng)有變量的非負(fù)約束即Xj≥0，但要注意也存在例外的情形。第三十二頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念線性規(guī)劃的一般形式:

max（或min）z=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn（≤=≥）b1a21x1+a22x2+…+a2nxn

（≤=≥）b2s.t.………………am1x1+am2x2+…+amnxn（≤=≥）bm

xj≥0（j=1，2…n）第三十三頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念線性規(guī)劃問題的標(biāo)準(zhǔn)形式1、目標(biāo)函數(shù)極大化——“max”2、等式約束條件——“=”且右端常數(shù)bi非負(fù)3、變量非負(fù)——“xj≥0”maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）第三十四頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念化標(biāo)準(zhǔn)形式的一般步驟目標(biāo)函數(shù)極小化“極大化”約束條件的右端項bi≤0“bi≥0”約束條件為不等式≤或≥“=”取值無約束（自由）變量“非負(fù)變量”取值非正變量“非負(fù)變量”第三十五頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念線性規(guī)劃問題的求解解：（圖解）如何求解一般的線性規(guī)劃呢？下面我們分析一下簡單的情況——

只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。第三十六頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念例1（page11）maxz=2x1+x25x2

≤15s.t.6x1+2x2

≤24x1+x2

≤5x1

，x2

≥0第三十七頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1

，x2≥0唯一最優(yōu)解X=（9/2，3/2）第三十八頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念例

maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0第三十九頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=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）DmaxZminZ此點是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域第四十頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=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

maxZminZ（3.8，4）34.2=3X1+5.7X2

綠色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏虻谒氖豁?，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點是唯一最優(yōu)解第四十二頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念minZ=5X1+4X2x1x2oD可行域第四十三頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2oD可行域maxZminZ最優(yōu)解目標(biāo)值Z趨于無窮第四十四頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2o可行解域為空第四十五頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）基本概念圖解法的啟示線性規(guī)劃問題解的可能情況

a.唯一最優(yōu)解

b.無窮多最優(yōu)解

c.無解（沒有有界最優(yōu)解，無可行解）若線性規(guī)劃問題的可行域非空，則可行域是一個凸集；若線性規(guī)劃問題的最優(yōu)解存在，則一定可以在可行域的凸集的某個頂點上達(dá)到。第四十六頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法

單純形方法是于1947年首先發(fā)明的。近50年來，一直是求解線性規(guī)劃的最有效的方法之一，被廣泛應(yīng)用于各種線性規(guī)劃問題的求解。本節(jié)討論單純形法的基本概念、原理及算法。第四十七頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法給定線性規(guī)劃問題（標(biāo)準(zhǔn)形式）maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn

=b1a21x1+a22x2+…+a2nxn

=b2s.t.……………am1x1+am2x2+…+amnxn

=bmxj≥0（j=1，2…n）第四十八頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法一、線性規(guī)劃問題的解的概念

可行解最優(yōu)解基基解（基本解）基可行解可行基第四十九頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法二、凸集及其頂點凸集頂點（極點）凸集凹集第五十頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）12345678基解（可行）基解（不可行）第五十一頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法三、線性規(guī)劃基本定理基本定理1

線性規(guī)劃所有可行解組成的集合S={X|AX=b，X≥0}是凸集。基本定理2

X是線性規(guī)劃問題的基本可行解的充要條件為是

X是凸集S={X|AX=b，X≥0}的極點。基本定理3

給定線性規(guī)劃問題，

A是秩為

m的

mn矩陣，

（i）若線性規(guī)劃問題存在可行解，則必存在基本可行解（ii）若線性規(guī)劃問題存在有界最優(yōu)解，則必存在有界最優(yōu)基本可行解。第五十二頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法單純形法迭代原理及其思路單純形法的初步討論例1.8求解LP問題

化為標(biāo)準(zhǔn)型MaxZ=50X1+30X2s.t.4X1+3X2≤

1202X1+X2≤50X1，X2≥0MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2

+X4

=50X1，X2，X3，X4

≥0（1.18）第五十三頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法此線性規(guī)劃問題轉(zhuǎn)化為了一個含有四個變量的標(biāo)準(zhǔn)形線性規(guī)劃問題，X3，X4為松弛變量。為求解上面的LP問題，我們要考慮滿足約束條件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下第五十四頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法確定初始基可行解：通過觀察可以發(fā)現(xiàn)，松弛變量X3和X4對應(yīng)的等式約束條件中的系數(shù)矩陣為單位矩陣可以作為初始可行基矩陣。因此取

X3，X4為基變量；X1，X2為非基變量。則（1.18）可變?yōu)椋?/p>

Max

Z

=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2（1.19）

X1，X2，X3，X4≥0第五十五頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法典式（1.19）或（1.18）稱為關(guān)于基的典式——1、等式約束條件中顯含基可行解

2、目標(biāo)函數(shù)中不含基變量MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2

+X4

=50(1.18)X1，X2，X3，X4≥0MaxZ

=50X1+30X2s.t.X3

=120-4X1-3X2

X4=50-2X1-X2（1.19）

X1，X2，X3，X4≥0第五十六頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法在典式（1.19）中令：X1=X2

=0，我們得到一個基本可行解

X1=（

X1，X2，X3，X4

）T=（0，0，120，50）T

，其對應(yīng)的目標(biāo)函數(shù)值Z1=50X1+30X2=0第五十七頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法最優(yōu)性檢驗：基本可行解X1是最優(yōu)解嗎？顯然不是。應(yīng)尋找更好的解。從問題的數(shù)學(xué)角度分析，在典式（1.19）的目標(biāo)函數(shù)中，非基變量X1，X2前的系數(shù)都為正，而此時的X1，X2均取零值，表明只要增加其值，則目標(biāo)函數(shù)值有增加的可能。因此，將目標(biāo)函數(shù)中系數(shù)為正的某一非基變量與某一基變量地位對換。第五十八頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法換基迭代：進行換基就是要從非基變量中選一個變量入基，再從基變量中選一個變量出基。并且換基后仍需滿足：

新的解仍是基本可行解；目標(biāo)函數(shù)值將得到改善。第五十九頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法選擇入基變量：

由于在目標(biāo)函數(shù)Z1

=50X1+30X2

中X1，X2的系數(shù)都為正，哪一個入基都可使目標(biāo)函數(shù)值得到改善。對于求目標(biāo)函數(shù)極大化的問題，我們希望目標(biāo)值增加得越快越好，因此系數(shù)最大的X1入基。選擇出基變量：

X1入基后，其值從零增加并由于約束條件的原因會引起其他變量的變化。由典式（1.19）以及變量必須取正值（可行）的條件，我們可以得到下列不等式關(guān)系：

X3=120-4X1-3X2≥0X4=50-2X1-X2≥0第六十頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法

因為迭代后X2仍為非基變量（仍會令其取值為零），則上式可簡化為：

120-4X1≥0，且50-2X1≥0，由此可以看出，雖然我們希望X1入基后取正值，取值越大目標(biāo)值增加越大，但是X1又得受到以上約束（保證其可行）。

顯然，當(dāng)取X1=min（120/4，50/2）=25時，才能使上述不等式成立，且此時恰使基變量X4變?yōu)榱?，這正好滿足非基變量必須取值零的條件，所以可令X4出基，這樣，新的基變量變?yōu)閄3，X1

，而X2，X4

成了非基變量，則第六十一頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法約束方程變?yōu)椋?/p>

4X1+X3=120-3X22X1=50-X2-X4化簡后得：新的典式方程

X3=20-X2+2X4X1=25-0.5X2-0.5X4第六十二頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法代入目標(biāo)函數(shù)可得：Z2

=1250+5X2-25X4

令非基變量X2=X4=0，即可得一個新的基本可行解X2=（25，0，20，0）T

，其對應(yīng)的目標(biāo)函數(shù)值Z2

=1250，并完成了第一次迭代。由于目標(biāo)函數(shù)Z2=1250+5X2-25X4中X2的系數(shù)仍為正，該解X2仍不是最優(yōu)解。重復(fù)上述迭代過程得到：X2入基，X3出基，則新的典式方程變?yōu)椋?/p>

X1

=15+0.5X3

-1.5X4

X2=20-X3+2X4

Z3

=1350-5X3-15X4第六十三頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法第三個基本可行解X3

=（15，20，0，0）T，其對應(yīng)的目標(biāo)函數(shù)值Z3

=1350。此時松弛變量都是非基變量（取值為零），這表明資源已用盡；并且目標(biāo)函數(shù)值Z3

=1350-5X3-15X4中非基變量X3，X4的系數(shù)全為負(fù)值，說明目標(biāo)函數(shù)已無法進一步改善，因此該解已是最優(yōu)解。第六十四頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法小結(jié)：

單純形法是這樣一種迭代算法——如下圖…當(dāng)

Zk

中非基變量的系數(shù)的系數(shù)全為負(fù)值時，這時的基本可行解Xk

即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。X1Z1保持單調(diào)增保持可行性保持可行性保持可行性保持可行性保持單調(diào)增保持單調(diào)增保持單調(diào)增X2X3...XkZ2Z3...Zk

當(dāng)

Zk

中非基變量的系數(shù)的系數(shù)全為負(fù)值時，這時的基本可行解Xk

即是線性規(guī)劃問題的最優(yōu)解，迭代結(jié)束。第六十五頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形表對于給定的線性規(guī)劃問題：maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2s.t.………am1x1+am2x2+…+amnxn≤bmxj≥0（j=1，2…n）

對此問題添加m個松弛變量后，可得下面線性規(guī)劃問題并且是典式的形式。第六十六頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形表線性規(guī)劃的典式maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+

xn+2=b2s.t.…am1x1+am2x2+…+amnxn+

xn+m=bmxj≥0（j=1，2…n，n+1，n+2，…n+m）第六十七頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形表：

將上面典式中各變量及系數(shù)填寫在一張表格中就形成下面的單純形表cj

c1

c2…cn00…0CB基變量基解x1x2…xnxn+1xn+2…xn+m0xn+1

b1a11a12…a1n1…10xn+2

b2a21a22…a2n1…2………………………………0xn+m

bmam1am2…amn…1j=cj–zjc1

c2…cn00…012…nn+1n+2…n+m基矩陣B=I非基矩陣N=ACNCBB-1b注意：在今后的迭代中基矩陣B會不斷地發(fā)生變化??！XB第六十八頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形表：

上面的單純形表還可以表示成矩陣的形式基解X

XSXSbAIj

C

0基解XB

XN

XSXSbBNIj

CB

CN

0或第六十九頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法由單純形表進行迭代步驟：選擇Xj入基：當(dāng)j行中

j=max{

i∣

i0}選擇Xi出基：當(dāng)i

=min{bi/aij∣aij0}換基迭代：當(dāng)確定了入基變量Xj

、出基變量Xi后，以aij作為主元對單純形表進行取主運算，取主運算——即采用初等行變換將主元

aij所在列，除將

aii變換為1而外，該列中的其余元素都變換為

0。注意這種變換只能采用初等行變換!第七十頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法最優(yōu)解檢驗：當(dāng)?shù)M行至某一步時，j行中所有檢驗數(shù)均小于等于零，則迭代結(jié)束。表中當(dāng)前所指基本可行解即為最優(yōu)解。當(dāng)?shù)M行至某一步時，j行中所有檢驗數(shù)均小于等于零，且此時至少有一個非基變量所對應(yīng)的檢驗數(shù)k等于零，則原線性規(guī)劃問題有無窮多個最優(yōu)解。當(dāng)?shù)M行至某一步時，j行中至少有一個檢驗數(shù)k大于零，且該檢驗數(shù)對應(yīng)的列中a1k，a2k，…amk，均小于等于零，則原線性規(guī)劃問題最優(yōu)解無界（maxZ→+∞）。第七十一頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形方法的矩陣描述：設(shè)線性規(guī)劃問題

maxZ=CXmaxZ=CX+0XS

s.t.AX≤bs.t.AX+IXS=b（I式）

X≥0X，XS≥0其中b≥0，I是mm單位矩陣。對上面（I式）經(jīng)過迭代，并設(shè)最終的最優(yōu)基矩陣為B（不妨設(shè)B

為A的首m列，則將（I式）改寫后有第七十二頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形方法的矩陣描述：maxZ=CBXB+CNXN+0XS

s.t.BXB+NXN+IXS=bXB

，XN，XS≥0

maxZ=CBB-1+（CN-CBB-1）XN-

CBB-1XS

s.t.XB+B-1NXN+B-1XS=B-1bXB

，XN，XS≥0

B式中最優(yōu)目標(biāo)函數(shù)值Z*=CBB

-1

，檢驗數(shù)CN-CBB

-1≤0

，-

CBB

-1≤0單純形方法迭代（I式）（B式）第七十三頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形方法的矩陣描述：基解XB

XN

XSXSb

BNIj

CB

CN

0基解XB

XN

XSXBB-1b

IB-1NB-1j

0

CN-CBB

–1N-

CBB

-1對應(yīng)I式的單純形表——

I

表對應(yīng)B

式的單純形表——B

表迭代第七十四頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形表計算步驟舉例給定線性規(guī)劃問題maxz=50X1+30X2s.t.4X1+3X2≤

1202X1+X2

≤50X1，X2

≥0maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2

，X3

，X4

≥0第七十五頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形表計算步驟舉例maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2

，X3

，X4≥0Cj503000基XB解B-1bX1X2X3X4X31204310X4502101檢驗數(shù)j

503000初始單純形表：基矩陣B非基矩陣NCBCNB-1b基變量非基變量第七十六頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形表計算步驟舉例maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2

，X3

，X4≥0基XB解B-1bX1X2X3X4X31204310X4502101檢驗數(shù)j

5030002120/450/2X111/201/2250201-2050-2520/125×211X2150-1/23/210-5-15第七十七頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法的進一步討論人工變量法：當(dāng)一般線性規(guī)劃問題標(biāo)準(zhǔn)化之后，我們或可得到一個顯然的基本可行解（如松弛變量作為基變量的一個初始基本可行解），這樣我們就可以馬上進入單純形表的運算步驟。然而，并非所有問題標(biāo)準(zhǔn)化之后我們都可得到一個顯然的初始基本可行解，這時就需要我們首先確定出一個基本可行解作為初始基本可行解。通常采用的是人工變量法來確定這樣的初始基本可行解。這種情況下一般有兩種方法：

大M法（罰因子法）兩階段法第七十八頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）單純形法的進一步討論1、大M法（罰因子法）maxz=-3X1+X3

x1+x2+x3

≤4-2x1+x2–x3

≥13x2+x3=9x1

，x2

，x3

≥0LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1

，x2

，x3

，x4

，x5

，x6

，x7

≥0第七十九頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）1、大M法LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1

，x2

，x3

，x4

，x5

，x6

，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j-30100-M-M第八十頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j-3-2M4M10-M00第八十一頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013檢驗數(shù)j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31檢驗數(shù)j-3+6M01+4M03M-4M0第八十二頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311檢驗數(shù)j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6檢驗數(shù)j00301.5-1.5-M0.5-M第八十三頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2檢驗數(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檢驗數(shù)j-9/2000-3/43/4-M-1/4-M第八十四頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）采用大M法求解線性規(guī)劃問題時可能出現(xiàn)的幾種情況：當(dāng)采用單純形法求解LPM

得到最優(yōu)解時，基變量不含任何人工變量，則所得到的最優(yōu)解就是原問題的最優(yōu)解；當(dāng)采用單純形法求解LPM

得到最優(yōu)解時，基變量至少含有一個人工變量且非零，則原問題無可行解；當(dāng)采用單純形法求解LPM

得到最優(yōu)解時，基變量至少含有一個人工變量且人工變量都為零，則通過變換得到原問題最優(yōu)解；第八十五頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）2、兩階段法maxz=-3X1+X3

x1+x2+x3≤4-2x1+x2–x3≥13x2+x3=9x1

，x2

，x3≥0I階段問題

maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1

，x2

，x3

，x4

，x5

，x6

，x7

≥0第八十六頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）2、兩階段法I階段問題

maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1

，x2

，x3

，x4

，x5

，x6

，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001檢驗數(shù)j00000-1-1第八十七頁，共一百二十九頁，2022年，8月28日線性規(guī)劃LinearProgramming（LP）2、兩階段法——第I階段基XB解B-1bX