運籌學(xué)PPT完整版

運籌學(xué)

(OperationsResearch)經(jīng)濟(jì)管理學(xué)核心課程運籌帷幄之中決勝千里之外緒論Introduction第一章緒論（1）運籌學(xué)簡述（2）運籌學(xué)的主要內(nèi)容（3）本課程的教材及參考書（4）本課程的特點和要求（5）本課程授課方式與考核（6）運籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用本章主要內(nèi)容：緒論什么是運籌學(xué)?OperationalResearch運用研究、運作研究緒論什么是運籌學(xué)是一門應(yīng)用學(xué)科，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供量化依據(jù)。運籌學(xué)簡述運籌學(xué)（OperationsResearch,簡寫OR

） 系統(tǒng)工程的最重要的理論基礎(chǔ)之一，在美國有人把運籌學(xué)稱之為管理科學(xué)(ManagementScience)。運籌學(xué)所研究的問題，可簡單地歸結(jié)為一句話：“依照給定條件和目標(biāo)，從眾多方案中選擇最佳方案”故有人稱之為最優(yōu)化技術(shù)。緒論運籌學(xué)的歷史與發(fā)展“運籌學(xué)思想的出現(xiàn)可以追溯到很早—“田忌賽馬”。

齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排：齊王 上 中 下 田忌 下 上 中 緒論丁謂的皇宮修復(fù)工程北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開封皇宮。他的施工方案是：先將皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運輸任務(wù)；修復(fù)工程完成后，實施大溝排水，并將原廢墟物回填，修復(fù)成原來的大街。丁謂將取材、運輸及清廢用“一溝三用”巧妙地解決了，體現(xiàn)了系統(tǒng)規(guī)劃的思想。緒論

國際上運籌學(xué)的思想可追溯到1914年，當(dāng)時的蘭徹斯特提出了軍事運籌學(xué)的作戰(zhàn)模型。1917年，丹麥工程師埃爾朗在研究自動電話系統(tǒng)中通話線路與用戶呼叫的數(shù)量關(guān)系問題時，提出了埃爾朗公式，研究了隨機(jī)服務(wù)系統(tǒng)中的系統(tǒng)排隊與系統(tǒng)擁擠問題。存儲論的最優(yōu)批量公式是在20世紀(jì)20年代初提出的。運籌學(xué)簡述“運作研究(OperationalResearch)小組”:解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題。例如：如何合理運用雷達(dá)有效地對付德軍德空襲對商船如何進(jìn)行編隊護(hù)航，使船隊遭受德國潛艇攻擊時損失最少；在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對德國潛艇的殺傷力等。緒論

在生產(chǎn)管理方面的應(yīng)用，最早是1939年前蘇聯(lián)的康特洛為奇提出了生產(chǎn)組織與計劃中的線性規(guī)劃問題，并給出解乘數(shù)法的求解方法，出版了第一部關(guān)于線性規(guī)劃的著作《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》。但當(dāng)時并沒有引起重視，直到1960年康特洛為奇再次出版了《最佳資源利用的經(jīng)濟(jì)計算》，才受到國內(nèi)外的一致重視，為此康特洛為奇獲得了諾貝爾經(jīng)濟(jì)學(xué)獎。線性規(guī)劃提出后很快受到經(jīng)濟(jì)學(xué)家的重視，如：二次世界大戰(zhàn)中從事運輸模型研究的美國經(jīng)濟(jì)學(xué)家?guī)炱章梗═.C.Koopmans），他很快看到了線性規(guī)劃在經(jīng)濟(jì)中應(yīng)用的意義，并呼吁年輕的經(jīng)濟(jì)學(xué)家要關(guān)注線性規(guī)劃。其中阿羅、薩謬爾遜、西蒙、多夫曼和胡爾威茨等都獲得了諾貝爾獎。緒論

20世紀(jì)50年代中期，錢學(xué)森、許國志等教授在國內(nèi)全面介紹和推廣運籌學(xué)知識，1956年，中國科學(xué)院成立第一個運籌學(xué)研究室，1957年運籌學(xué)運用到建筑和紡織業(yè)中，1958年提出了圖上作業(yè)法，山東大學(xué)的管梅谷教授提出了“中國郵遞員問題”，1970年，在華羅庚教授的直接指導(dǎo)下，在全國范圍內(nèi)推廣統(tǒng)籌方法和優(yōu)選法。

1978年11月，在成都召開了全國數(shù)學(xué)年會，對運籌學(xué)的理論與應(yīng)用研究進(jìn)行了一次檢閱，1980年4月在山東濟(jì)南正式成立了“中國數(shù)學(xué)會運籌學(xué)會”，1984年在上海召開了“中國數(shù)學(xué)會運籌學(xué)會第二屆代表大會暨學(xué)術(shù)交流會”，并將學(xué)會改名為“中國運籌學(xué)會”。緒論成熟的學(xué)科分支向縱深發(fā)展新的研究領(lǐng)域產(chǎn)生與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀念不斷變化運籌學(xué)的發(fā)展趨勢運籌學(xué)的主要內(nèi)容數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)規(guī)劃等）圖論存儲論排隊論對策論排序與統(tǒng)籌方法決策分析運籌學(xué)的主要內(nèi)容1.線性規(guī)劃（LinearProgram）是一個成熟的分支，它有效的算法——單純形法，主要解決生產(chǎn)計劃問題，合理下料問題，最優(yōu)投資問題。2.整數(shù)規(guī)劃(IntegrateProgram)：在線性規(guī)劃的基礎(chǔ)上，變量加上整數(shù)約束。3.非線性規(guī)劃(NonlinearProgram)：目標(biāo)函數(shù)和約束條件是非線性函數(shù)，如證券投資組合優(yōu)化:如何合理投資使風(fēng)險最小。4.動態(tài)規(guī)劃(DynamicProgram)：多階段決策問題。是美國貝爾曼于1951年提出的。運籌學(xué)的主要內(nèi)容5、圖與網(wǎng)絡(luò)(GraphTheoryandNetwork)：中國郵遞員問題、哥尼斯堡城問題、最短路、最大流問題。6、存儲論（InventoryTheory)：主要解決生產(chǎn)中的庫存問題，訂貨周期和訂貨量等問題。7、排隊論(QueueTheory)：主要研究排隊系統(tǒng)中的系統(tǒng)排隊和系統(tǒng)擁擠現(xiàn)象，從而評估系統(tǒng)的服務(wù)質(zhì)量。8、對策論(GameTheory)：主要研究具有斗爭性質(zhì)的優(yōu)化問題。9、決策分析(DecisionAnalysis)：主要研究定量化決策。本課程的教材及參考書選用教材《運籌學(xué)教程》胡運權(quán)主編（第3版）清華出版社參考教材《運籌學(xué)基礎(chǔ)及應(yīng)用》胡運權(quán)主編哈工大出版社《管理運籌學(xué)》韓伯棠主編（第2版）高等教育出版社《運籌學(xué)》(修訂版)錢頌迪主編清華出版社

本課程的特點和要求先修課：高等數(shù)學(xué)，基礎(chǔ)概率、線性代數(shù)特點：系統(tǒng)整體優(yōu)化；多學(xué)科的配合；模型方法的應(yīng)用運籌學(xué)的研究的主要步驟：真實系統(tǒng)系統(tǒng)分析問題描述模型建立與修改模型求解與檢驗結(jié)果分析與實施數(shù)據(jù)準(zhǔn)備本課程授課方式與考核學(xué)科總成績平時成績（40％）課堂考勤（50％）平時作業(yè)（50％）期末成績（60％）講授為主，結(jié)合習(xí)題作業(yè)運籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用運籌學(xué)在經(jīng)濟(jì)管理中的應(yīng)用涉及的方面：生產(chǎn)計劃運輸問題人事管理庫存管理市場營銷財務(wù)和會計物流配送另外，還應(yīng)用于設(shè)備維修、更新和可靠性分析，項目的選擇與評價，工程優(yōu)化設(shè)計等?！肮芾磉\籌學(xué)”軟件介紹“管理運籌學(xué)”2.0版包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關(guān)鍵路徑、存儲論、排隊論、決策分析、預(yù)測問題和層次分析法，共15個子模塊。運籌帷幄之中決勝千里之外線性規(guī)劃及單純形法LinearProgramming第一章Chapter1線性規(guī)劃

(LinearProgramming)LP的數(shù)學(xué)模型圖解法單純形法單純形法的進(jìn)一步討論－人工變量法

LP模型的應(yīng)用本章主要內(nèi)容：線性規(guī)劃問題的數(shù)學(xué)模型1.規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤最大.）線性規(guī)劃問題的數(shù)學(xué)模型例1.1如圖所示，如何截取x使鐵皮所圍成的容積最大？xa線性規(guī)劃問題的數(shù)學(xué)模型例1.2某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤問：應(yīng)如何安排生產(chǎn)計劃，才能使總利潤最大？解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為

x1、x22.目標(biāo)函數(shù)：設(shè)總利潤為z，則有：

maxz=2x1+x23.約束條件：

5x2≤156x1+2x2≤24x1+x2≤5

x1，x2≥0線性規(guī)劃問題的數(shù)學(xué)模型例1.3已知資料如下表所示，問如何安排生產(chǎn)才能使利潤最大？或如何考慮利潤大，產(chǎn)品好銷。

設(shè)備產(chǎn)品AB

C

D利潤（元）

Ⅰ

2

1

4

0

2

Ⅱ

2

2

0

4

3

有效臺時12

81612解：1.決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分別為

x1、x22.目標(biāo)函數(shù)：設(shè)總利潤為z，則有：

maxz=2x1+x23.約束條件：

x1≥0,x2≥0

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12線性規(guī)劃問題的數(shù)學(xué)模型例1.4

某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物量解：要求：生產(chǎn)A種藥物至少160單位；B種藥物恰好200單位，C種藥物不超過180單位，且使原料總成本最小。1.決策變量：設(shè)四種原料的使用量分別為：x1、x2、x3

、x42.目標(biāo)函數(shù)：設(shè)總成本為zmin

z=5x1+6x2+7x3+8x43.約束條件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝2003x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0

例1.5

某航運局現(xiàn)有船只種類、數(shù)量以及計劃期內(nèi)各條航線的貨運量、貨運成本如下表所示：航線號船隊類型編隊形式貨運成本（千元／隊）貨運量（千噸）拖輪A型駁船B型駁船1112—362521—4362023224724041—42720船只種類船只數(shù)拖輪30A型駁船34B型駁船52航線號合同貨運量12002400問：應(yīng)如何編隊，才能既完成合同任務(wù)，又使總貨運成本為最?。烤€性規(guī)劃問題的數(shù)學(xué)模型

解：設(shè)：xj為第j號類型船隊的隊數(shù)（j=1，2，3，4），

z為總貨運成本則：

minz=36x1+36x2+72x3+27x4

x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2

＝20040x3+20x4＝400xj≥0（j=1,2,3,4）線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

線性規(guī)劃問題的數(shù)學(xué)模型3.建模條件(1)

優(yōu)化條件：問題所要達(dá)到的目標(biāo)能用線型函數(shù)描述，且能夠用極值（max或min）來表示；(2)

限定條件：達(dá)到目標(biāo)受到一定的限制，且這些限制能夠用決策變量的線性等式或線性不等式表示；(3)

選擇條件：有多種可選擇的方案供決策者選擇，以便找出最優(yōu)方案。線性規(guī)劃問題的數(shù)學(xué)模型4.建模步驟(1)

確定決策變量：即需要我們作出決策或選擇的量。一般情況下，題目問什么就設(shè)什么為決策變量；(2)

找出所有限定條件：即決策變量受到的所有的約束；(3)

寫出目標(biāo)函數(shù)：即問題所要達(dá)到的目標(biāo)，并明確是max還是min。線性規(guī)劃問題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：5.線性規(guī)劃數(shù)學(xué)模型的一般形式簡寫為：線性規(guī)劃問題的數(shù)學(xué)模型向量形式：其中：線性規(guī)劃問題的數(shù)學(xué)模型矩陣形式：其中：線性規(guī)劃問題的數(shù)學(xué)模型6.線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點：(1)目標(biāo)函數(shù)求最大值（有時求最小值）(2)約束條件都為等式方程，且右端常數(shù)項bi都大于或等于零(3)決策變量xj為非負(fù)。線性規(guī)劃問題的數(shù)學(xué)模型（2）如何化標(biāo)準(zhǔn)形式

目標(biāo)函數(shù)的轉(zhuǎn)換

如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。也就是：令，可得到上式。即

若存在取值無約束的變量，可令其中：

變量的變換線性規(guī)劃問題的數(shù)學(xué)模型

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量

常量bi＜0

的變換:約束方程兩邊乘以（－1）線性規(guī)劃問題的數(shù)學(xué)模型例1.6

將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式用替換，且

解:（１）因為x3無符號要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以線性規(guī)劃問題的數(shù)學(xué)模型(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；(3)第二個約束條件是“≥”號，在“≥”左端減去剩余變量x5，x5≥0；(4)第3個約束方程右端常數(shù)項為-5，方程兩邊同乘以(-1),將右端常數(shù)項化為正數(shù)；

(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令z′=-z,得到maxz′=-z，即當(dāng)z達(dá)到最小值時z′達(dá)到最大值，反之亦然;線性規(guī)劃問題的數(shù)學(xué)模型標(biāo)準(zhǔn)形式如下：

例1.7將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式為無約束（無非負(fù)限制）線性規(guī)劃問題的數(shù)學(xué)模型

解:用替換，且，將第3個約束方程兩邊乘以（－1）將極小值問題反號，變?yōu)榍髽O大值標(biāo)準(zhǔn)形式如下：引入變量線性規(guī)劃問題的數(shù)學(xué)模型

例1.8將線性規(guī)劃問題化為標(biāo)準(zhǔn)型解：線性規(guī)劃問題的數(shù)學(xué)模型

例1.9將線性規(guī)劃問題化為標(biāo)準(zhǔn)型解：Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0；x2無約束

Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型7.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標(biāo)函數(shù)(1)達(dá)到最大值。線性規(guī)劃問題的數(shù)學(xué)模型

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

基：設(shè)A為約束條件②的m×n階系數(shù)矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問題的一個基。設(shè)：稱B中每個列向量Pj(j=12…

…m)

為基向量。與基向量Pj

對應(yīng)的變量xj

為基變量。除基變量以外的變量為非基變量。線性規(guī)劃問題的數(shù)學(xué)模型

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數(shù)不大于方程數(shù)m，基解的總數(shù)不超過

基可行解：滿足變量非負(fù)約束條件的基本解，簡稱基可行解。可行基：對應(yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解線性規(guī)劃問題的數(shù)學(xué)模型例1.10

求線性規(guī)劃問題的所有基矩陣。解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即圖解法線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡單的情況——

只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。

解題步驟4將最優(yōu)解代入目標(biāo)函數(shù)，求出最優(yōu)值。1在直角平面坐標(biāo)系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中的點稱為可行解。2標(biāo)出目標(biāo)函數(shù)值增加或者減小的方向。3若求最大（?。┲担瑒t令目標(biāo)函數(shù)等值線沿（逆）目標(biāo)函數(shù)值增加的方向平行移動，找與可行域最后相交的點，該點就是最優(yōu)解。圖解法圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.11用圖解法求解線性規(guī)劃問題圖解法x1x2oX1-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可行域maxZ=2X1+X2圖解法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

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

藍(lán)色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的。可行域圖解法minZ=5X1+4X2x1x2oX1-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)解圖解法246x1x2246無界解(無最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZx1x2O10203040102030405050無可行解(即無最優(yōu)解)maxZ=3x1+4x2例1.7

由圖解法得到的幾種情況

根據(jù)以上例題，進(jìn)一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況：

1.可行域為封閉的有界區(qū)域

(a)有唯一的最優(yōu)解；(b)有無窮多個最優(yōu)解；

2.可行域為封閉的無界區(qū)域

(c)有唯一的最優(yōu)解；(d)有無窮多個最優(yōu)解；

(e)目標(biāo)函數(shù)無界(即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無限增大或無限減少)，因而沒有有限最優(yōu)解。

3.可行域為空集

(f)沒有可行解，原問題無最優(yōu)解圖解法

由圖解法得到的啟示(1)線性規(guī)劃問題解的情況：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解(3)最優(yōu)解一定是在凸集的某個頂點(2)線性規(guī)劃問題的可行域是凸集（凸多邊形）(4)解題思路是，先找出凸集的任一頂點，計算其目標(biāo)函數(shù)值，再與周圍頂點的目標(biāo)函數(shù)值比較，如不是最大，繼續(xù)比較，直到找出最大為止。圖解法圖解法

學(xué)習(xí)要點：

1.通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）

2.作圖的關(guān)鍵有三點：

(1)可行解區(qū)域要畫正確

(2)目標(biāo)函數(shù)增加的方向不能畫錯

(3)目標(biāo)函數(shù)的直線怎樣平行移動

連接幾何形體中任意兩點的線段仍完全在該幾何形體之中。有限個凸集的交集仍然是凸集。單純形法基本原理單純形法基本原理凸集：如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，稱C為凸集。凸集凸集不是凸集頂點

頂點：如果凸集C中不存在任何兩個不同的點X1，X2，使X成為這兩個點連線上的一個點單純形法基本原理定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應(yīng)可行域(凸集)的頂點。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）單純形法的計算步驟單純形法的思路找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束單純形法的計算步驟單純形表單純形法的計算步驟例1.12用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗數(shù)單純形法的計算步驟3）進(jìn)行最優(yōu)性檢驗如果表中所有檢驗數(shù)，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗數(shù)大于0時，一般選擇最大的一個檢驗數(shù)，即：，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計算并選擇θ

，選最小的θ對應(yīng)基變量作為換出變量。 單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5）重復(fù)3）、4）步直到計算結(jié)束為止。 單純形法的計算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1單純形法的計算步驟例1.13

用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計算。單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3變成標(biāo)準(zhǔn)型單純形法的計算步驟例1.14用單純形法求解約束方程的系數(shù)矩陣為基變量為非基變量I為單位矩陣且線性獨立單純形法的計算步驟單純形法的計算步驟－cjcBxBb0000x3x4x5x61281612

2x2

單純形法的計算步驟

學(xué)習(xí)要點：

1.線性規(guī)劃解的概念以及3個基本定理

2.熟練掌握線性規(guī)劃問題的標(biāo)準(zhǔn)化

3.熟練掌握單純形法的解題思路及求解步驟單純形法的進(jìn)一步討論－人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。單純形法的進(jìn)一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。單純形法的進(jìn)一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。單純形法的進(jìn)一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M-Mx63-650-1013/50x58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——0x531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→單純形法的進(jìn)一步討論－人工變量法例1.11用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。單純形法的進(jìn)一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。單純形法的進(jìn)一步討論－人工變量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000x4103-20100-1－-Mx610100-11-21-1x31-2010001－Z-M-11-1+M00-M0-3M+1→→單純形法的進(jìn)一步討論－人工變量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4123001-22-54-1x210100-11-2－-1x31-2010001－Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3→單純形法的進(jìn)一步討論－兩階段法

用計算機(jī)處理數(shù)據(jù)時，只能用很大的數(shù)代替M,可能造成計算機(jī)上的錯誤，故多采用兩階段法。

第一階段：在原線性規(guī)劃問題中加入人工變量，構(gòu)造如下模型：

對上述模型求解（單純形法），若ω=0,說明問題存在基可行解，可以進(jìn)行第二個階段；否則，原問題無可行解，停止運算。單純形法的進(jìn)一步討論－兩階段法第一階段的線性規(guī)劃問題可寫為：第一階段單純形法迭代的過程見下表（注意：沒有化為極大化問題）單純形法的進(jìn)一步討論－兩階段法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011ω46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－ω10-1001030x4123001-22-50x210100-11-20x31-2010000ω00000011→→單純形法的進(jìn)一步討論－兩階段法

第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計算的初始表（用單純形法計算）。例：單純形法的進(jìn)一步討論－兩階段法cj3-1-100cBxBbx1x2x3x4x50x4123001-24-1x210100-1－-1x31-20100－Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3→第二階段：∴最優(yōu)解為（41900），目標(biāo)函數(shù)Z=2單純形法的進(jìn)一步討論

通過大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。

無可行解C-3-2-1000-M-MCB

XB

bx1x2x3x4x5x6x7x8

θ0-M-Mx4x7x8

6431111000010-10-101001-100-1016/1-3/1Z-7M-6-4M-15-M

-3+M-2+M-1-2M0-M-M000-M-2x4x7x2

3431021010-110-10-101001-100-1013/14/1-ZZ-3+M0-3-M0-M-202-M-3-M-2x1x7x2

3131021010-100-3-1-1-11101-100-101

003-3M3-M-M1-M0-1例單純形法的進(jìn)一步討論運算到檢驗數(shù)全負(fù)為止，仍含有人工變量，無可行解。單純形法的進(jìn)一步討論

無最優(yōu)解與無可行解時兩個不同的概念。無可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線性規(guī)劃問題的可行域為空集；無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無窮大（或者無窮?。o最優(yōu)解也稱為有限最優(yōu)解，或無界解。

判別方法：無最優(yōu)解判別定理在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗行存在某個大于零的檢驗數(shù)，但是該檢驗數(shù)所對應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題無最優(yōu)解

無最優(yōu)解C

2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原問題無最優(yōu)解單純形法的進(jìn)一步討論

退化即計算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。為避免出現(xiàn)計算的循環(huán)，勃蘭特(Bland)提出一個簡便有效的規(guī)則（攝動法原理）：⑴當(dāng)存在多個時，選下標(biāo)最小的非基變量為換入變量；(2)當(dāng)θ值出現(xiàn)兩個以上相同的最小值時，選下標(biāo)最小的基變量為換出變量。單純形法的進(jìn)一步討論000-242-8030Z-5-60-420-805Z10001001x3

212060-2411x1

3321300-803x5

00-30-425-800Z11001001x7

00106-1-2410x1

30-1130-3-800x5

0-11001001x7

000106-1-2410x6

0000136-4-3210x5

0x7

x6

x5

x4

x3

x2

x1

bXB

CB

000-242-803Cθ

第一次迭代中使用了攝動法原理，選擇下標(biāo)為6的基變量x6離基?？傻米顑?yōu)解maxZ=５，單純形法的進(jìn)一步討論

無窮多最優(yōu)解若線性規(guī)劃問題某個基本可行解所有的非基變量檢驗數(shù)都小于等于零，但其中存在一個檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例３：最優(yōu)表：非基變量檢驗數(shù)，

所以有無窮多最優(yōu)解。C12000θCBXBb

x1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’8

0000-1單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。單純形法的進(jìn)一步討論單純性法小結(jié):建立模型個數(shù)取值右端項等式或不等式極大或極小新加變量系數(shù)兩個三個以上xj≥0xj無約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-MA

線性規(guī)劃模型的應(yīng)用

一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。

要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)存在著多種方案要求達(dá)到的目標(biāo)是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述

線性規(guī)劃模型的應(yīng)用常見問題合理利用線材問題：如何下料使用材最少。配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤。投資問題：從投資項目中選取方案，使投資回報最大。產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大。勞動力安排：用最少的勞動力來滿足工作的需要。運輸問題：如何制定調(diào)運方案，使總運費最小。

線性規(guī)劃模型的應(yīng)用(1)設(shè)立決策變量；

(2)明確約束條件并用決策變量的線性等式或不等式表示；

(3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in）；

(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。建立線性規(guī)劃模型的過程可以分為四個步驟：

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用1.資源的合理利用

某廠計劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2,…Bn種產(chǎn)品，要消耗A1,A2,…Am種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤如表所示，問如何安排生產(chǎn)計劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤最大？單件產(chǎn)消耗品資源資源限制單件利潤

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用2.生產(chǎn)組織與計劃問題

某工廠用機(jī)床A1,A2,…Am加工B1,B2,…Bn

種零件。在一個周期內(nèi)，各機(jī)床可能工作的機(jī)時（臺時），工廠必須完成各種零件的數(shù)量、各機(jī)床加工每個零件的時間（機(jī)時/個）和加工每個零件的成本（元/個）如表所示，問如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？加工零時間件機(jī)床機(jī)時限制必須零件數(shù)加工零成本件機(jī)床

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用

某廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。設(shè)A工序可分別在設(shè)備A1和A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序。已知產(chǎn)品Ⅰ可在A、B任何一種設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格的A設(shè)備上加工，但完成B工序時，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工。加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)如下表，試安排最優(yōu)生產(chǎn)計劃，使該廠獲利最大。

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用設(shè)備產(chǎn)品設(shè)備有效臺時設(shè)備加工費（單位小時）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料費（每件）0.250.350.5售價（每件）1.252.002.8解：設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量。約束條件有：

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用

線性規(guī)劃在管理中的應(yīng)用目標(biāo)是利潤最大化，即利潤的計算公式如下：帶入數(shù)據(jù)整理得到：

線性規(guī)劃在管理中的應(yīng)用因此該規(guī)劃問題的模型為：

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用例：現(xiàn)有一批某種型號的圓鋼長8米，需要截取2.5米長的毛坯100根，長1.3米的毛坯200根。問如何才能既滿足需要，又能使總的用料最少？解：為了找到一個省料的套裁方案，必須先設(shè)計出較好的幾個下料方案。其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，以滿足對各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的，為此可以設(shè)計出4種下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料頭0.50.40.30.23.合理下料問題

線性規(guī)劃在管理中的應(yīng)用設(shè)按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根數(shù)分別為xj

(j=1，2,3,4)，可列出下面的數(shù)學(xué)模型：

線性規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用4.合理配料問題

某飼養(yǎng)場用n種飼料B1,B2,…Bn配置成含有m種營養(yǎng)成分A1,A2,…Am的混合飼料，其余資料如表所示。問應(yīng)如何配料，才能既滿足需要，又使混合飼料的總成本最低？解：

線性規(guī)劃在管理中的應(yīng)用例：某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下：問兩種食物各食用多少，才能既滿足需要、又使總費用最?。?/p>

21.5原料單價1.007.5010.00

0.10.151.70.751.101.30A1A2A3

最低需要量

甲乙含量食物成分

線性規(guī)劃在管理中的應(yīng)用解：設(shè)Xj

表示Bj

種食物用量

線性規(guī)劃在管理中的應(yīng)用5.人力資源分配問題例1.11某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次時間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機(jī)和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)減少?

線性規(guī)劃在管理中的應(yīng)用解：設(shè)xi表示第i班次時開始上班的司機(jī)和乘務(wù)人員人數(shù)。此問題最優(yōu)解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司機(jī)和乘務(wù)員150人。Chapter2對偶理論

(DualityTheory)

線性規(guī)劃的對偶模型對偶性質(zhì)對偶問題的經(jīng)濟(jì)解釋－影子價格對偶單純形法靈敏度分析本章主要內(nèi)容：線性規(guī)劃的對偶模型

設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備按A，B，C，D順序加工，每件產(chǎn)品加工所需的機(jī)時數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機(jī)時數(shù)列于下表：產(chǎn)品數(shù)據(jù)表

設(shè)備產(chǎn)品ABCD產(chǎn)品利潤（元／件）

甲

21402乙

22043設(shè)備可利用機(jī)時數(shù)（時）

1281612問：充分利用設(shè)備機(jī)時，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤？1.對偶問題的提出線性規(guī)劃的對偶模型解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及x2件，則數(shù)學(xué)模型為：反過來問：若廠長決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費，那么４種機(jī)器的機(jī)時如何定價才是最佳決策？線性規(guī)劃的對偶模型在市場競爭的時代，廠長的最佳決策顯然應(yīng)符合兩條：

（1）不吃虧原則。即機(jī)時定價所賺利潤不能低于加工甲、乙型產(chǎn)品所獲利潤。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。（2）競爭性原則。即在上述不吃虧原則下，盡量降低機(jī)時總收費，以便爭取更多用戶。設(shè)A、B、C、D設(shè)備的機(jī)時價分別為y1、y2、y3、y4，則新的線性規(guī)劃數(shù)學(xué)模型為：線性規(guī)劃的對偶模型把同種問題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會發(fā)現(xiàn)一個有趣的現(xiàn)象。原問題與對偶問題對比表A（y1）

B（y2）C（y3）

D（y4）

甲（x1）

21402乙（x2）

220431281612

minωmaxz

對偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個線性規(guī)劃（LP）必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求maxZ的LP都有一個求minZ

的LP。其中的一個問題叫“原問題”，記為“P”，另一個稱為“對偶問題”，記為“D”。線性規(guī)劃的對偶模型2.原問題與對偶問題的對應(yīng)關(guān)系原問題-P對偶問題-D線性規(guī)劃的對偶模型23x1

x2

原問題12y1

22≤128y2

12≤816y340≤1612y404≤12對偶問題23線性規(guī)劃的對偶模型（1）對稱形式

特點：目標(biāo)函數(shù)求極大值時，所有約束條件為≤號，變量非負(fù);目標(biāo)函數(shù)求極小值時，所有約束條件為≥號，變量非負(fù).原問題對偶問題目標(biāo)函數(shù)maxmin約束條件≤≥變量數(shù)量約束條件個數(shù)約束條件個數(shù)變量數(shù)量線性規(guī)劃的對偶模型例2.1寫出線性規(guī)劃問題的對偶問題解：首先將原問題變形為對稱形式

注意：以后不強(qiáng)調(diào)等式右段項b≥0，原因在對偶單純型表中只保證而不保證，故b可以是負(fù)數(shù)。線性規(guī)劃的對偶模型線性規(guī)劃的對偶模型(2)非對稱型對偶問題

若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。也可直接按教材表2-2中的對應(yīng)關(guān)系寫出非對稱形式的對偶問題。線性規(guī)劃的對偶模型原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=b約束條件右端項目標(biāo)函數(shù)變量的系數(shù)C目標(biāo)函數(shù)變量的系數(shù)約束條件右端項線性規(guī)劃的對偶模型例2.2寫出下列線性規(guī)劃問題的對偶問題.解：原問題的對偶問題為無約束線性規(guī)劃的對偶模型例2.3寫出下列線性規(guī)劃問題的對偶問題.解：原問題的對偶問題為線性規(guī)劃的對偶模型例2.4線性規(guī)劃的對偶模型對偶性質(zhì)性質(zhì)1對稱性定理：對偶問題的對偶是原問題minZ’=-CXs.t.-AX≤-b X≥0

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0對偶的定義對偶的定義maxW’=-Ybs.t.YA≥CY≤0對偶性質(zhì)性質(zhì)2

弱對偶原理(弱對偶性)：設(shè)和分別是問題(P)和(D)的可行解，則必有推論1:原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之，對偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。推論2:

在一對對偶問題（P）和（D）中，若其中一個問題可行但目標(biāo)函數(shù)無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。對偶性質(zhì)無界（原）無可行解（對）關(guān)于無界性有如下結(jié)論：問題無界無可行解無可行解問題無界對偶問題原問題例2.5對偶性質(zhì)推論3：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行（如D），則該可行的問題目標(biāo)函數(shù)值無界。試估計它們目標(biāo)函數(shù)的界，并驗證弱對偶性原理。（P）例2.6對偶性質(zhì)解：（D）

由觀察可知：=（），=（1.1），分別是（P）和（D）的可行解。Z=10，W=40，故有，弱對偶定理成立。由推論⑴可知，W

的最小值不能小于10，Z

的最大值不能超過40。＜對偶性質(zhì)性質(zhì)3

最優(yōu)性定理：如果是原問題的可行解，是其對偶問題的可行解，并且:則是原問題的最優(yōu)解，是其對偶問題的最優(yōu)解。

例如:在一對對偶問題（P）和（D）中，可找到X*=（），Y*=（1.2，0.2）,且Z=W28，則X*，Y*分別是P和D的最優(yōu)解。對偶性質(zhì)性質(zhì)4強(qiáng)對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。

還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。性質(zhì)5

互補松弛性：設(shè)X0和Y0分別是P問題和D問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs、Ys為松弛變量對偶性質(zhì)性質(zhì)5的應(yīng)用： 該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊互補松弛條件由于松弛變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。對偶性質(zhì)例2.7

已知線性規(guī)劃的最優(yōu)解是X＊=(6,2,0)T,求其對偶問題的最優(yōu)解Y＊。解：寫出原問題的對偶問題，即標(biāo)準(zhǔn)化對偶性質(zhì)設(shè)對偶問題最優(yōu)解為Y＊＝(y1，y2),由互補松弛性定理可知，X＊和Y＊滿足：即：因為X1=6≠0，X2=2≠0，所以對偶問題的第一、二個約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。對偶性質(zhì)例2.8已知線性規(guī)劃的對偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。解:對偶問題是標(biāo)準(zhǔn)化無約束對偶性質(zhì)設(shè)對偶問題最優(yōu)解為X＊＝(x1，x2，x3)T,由互補松弛性定理可知，X＊和Y＊滿足：將Y＊=(0,-2)帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1?！遹2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0將x2，x5分別帶入原問題約束方程中，得：解方程組得：x1=-5,x3=-1,所以原問題的最優(yōu)解為X＊=(-5,0,-1)，最優(yōu)值z=-12對偶性質(zhì)原問題與對偶問題解的對應(yīng)關(guān)系小結(jié)對應(yīng)關(guān)系原問題最優(yōu)解無界解無可行解對偶問題最優(yōu)解(Y,Y)(N,N)————無界解————(Y,Y)無可行解——(Y,Y)無法判斷對偶問題的經(jīng)濟(jì)解釋－影子價格1.影子價格的數(shù)學(xué)分析：定義：在一對P和D中，若P的某個約束條件的右端項常數(shù)bi（第i種資源的擁有量）增加一個單位時，所引起目標(biāo)函數(shù)最優(yōu)值z*的改變量稱為第i種資源的影子價格，其值等于D問題中對偶變量yi*。由對偶問題得基本性質(zhì)可得：對偶問題的經(jīng)濟(jì)解釋－影子價格2.影子價格的經(jīng)濟(jì)意義1）影子價格是一種邊際價格 在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對偶變量yi

就是第i種資源的影子價格。即：

對偶問題的經(jīng)濟(jì)解釋－影子價格2）影子價格是一種機(jī)會成本 影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機(jī)會成本。若第i種資源的單位市場價格為mi

，則有當(dāng)yi*>mi

時，企業(yè)愿意購進(jìn)這種資源，單位純利為yi*－mi

，則有利可圖；如果yi*<mi

，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利mi－yi

*

，否則，企業(yè)無利可圖，甚至虧損。結(jié)論：若yi*>mi則購進(jìn)資源i，可獲單位純利yi*－mi

若yi*<mi則轉(zhuǎn)讓資源i，可獲單位純利mi－yi對偶問題的經(jīng)濟(jì)解釋－影子價格3）影子價格在資源利用中的應(yīng)用根據(jù)對偶理論的互補松弛性定理:Y*Xs=0,YsX*=0表明生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為0；若當(dāng)資源資源的影子價格不為0時，表明該種資源在生產(chǎn)中已耗費完。對偶問題的經(jīng)濟(jì)解釋－影子價格4）影子價格對單純形表計算的解釋單純形表中的檢驗數(shù)其中cj表示第j種產(chǎn)品的價格;表示生產(chǎn)該種產(chǎn)品所消耗的各項資源的影子價格的總和,即產(chǎn)品的隱含成本。當(dāng)產(chǎn)值大于隱含成本時，即，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。對偶單純形法

對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設(shè)計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。對偶單純形法原理對偶單純形法基本思路：

找出一個對偶問題的可行基，保持對偶問題為可行解的條件下，判斷XB是否可行（XB=b為非負(fù)），有最優(yōu)解。否則，通過變換基解，直到找到原問題基可行解（即XB為非負(fù)），這時原問題與對偶問題同時達(dá)到可行解，由定理4可得。對偶單純形法找出一個DP的可行基LP是否可行（XB≥0）保持DP為可行解情況下轉(zhuǎn)移到LP的另一個基本解最優(yōu)解是否循環(huán)結(jié)束對偶單純形法例2.9用對偶單純形法求解：解:（1）將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行（求max問題）。對偶單純形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-2-2-1100-100x5-2-3-1010-120x6-1-1-5001-14λj-9-12-150000對偶單純形法cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14對偶單純形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15