1運籌學北京理工大學管理與經(jīng)濟學院吳祈宗教授1運籌學北京理工大學2

1、緒論

2、線性規(guī)劃

3、運輸問題

4、動態(tài)規(guī)劃

5、圖與網(wǎng)絡分析

6、排隊論

7、教學日歷運籌學——目錄說明本教學課件是與教材緊密配合使用的，教材為：《運籌學》楊民助編著西安交通大學出版社，2000年6月參考書：《運籌學》清華大學出版社或其他的《運籌學》方面本科教材的相關(guān)內(nèi)容下面所標注的頁號，均為本課程教材的頁號。例如：p123

表示第123頁p31-34

表示從第31頁到第34頁21、緒論運籌學——目錄說明3緒論

運籌學（OperationalResearch)直譯為“運作研究”運籌學是運用科學的方法（如分析、試驗、量化等）來決定如何最佳地運營和設計各種系統(tǒng)的一門學科。運籌學對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。

運籌學有廣泛應用（可以自己找一些參考書看）運籌學的產(chǎn)生和發(fā)展（可以自己找一些參考書看）3緒論運籌學（OperationalRese4運籌學解決問題的過程1）提出問題：認清問題2）尋求可行方案：建模、求解3）確定評估目標及方案的標準或方法、途徑4）評估各個方案：解的檢驗、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實施：回到實踐中7）后評估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。4運籌學解決問題的過程1）提出問題：認清問題5運籌學的分支線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃多目標規(guī)劃隨機規(guī)劃模糊規(guī)劃等圖與網(wǎng)絡理論存儲論排隊論決策論對策論排序與統(tǒng)籌方法可靠性理論等5運籌學的分支線性規(guī)劃圖與網(wǎng)絡理論6運籌學在工商管理中的應用生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等庫存管理：多種物資庫存量的管理，庫存方式、庫存量等運輸問題：確定最小成本的運輸線路、物資的調(diào)撥、運輸工具的調(diào)度以及建廠地址的選擇等人事管理：對人員的需求和使用的預測，確定人員編制、人員合理分配，建立人才評價體系等市場營銷：廣告預算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等財務和會計：預測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等***設備維修、更新，項目選擇、評價，工程優(yōu)化設計與管理等6運籌學在工商管理中的應用生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的7運籌學方法使用情況(美1983)（%）7運籌學方法使用情況(美1983)（%）8運籌學方法在中國使用情況(隨機抽樣)（%）8運籌學方法在中國使用情況(隨機抽樣)（%）9運籌學的推廣應用前景據(jù)美勞工局1992年統(tǒng)計預測:

運籌學應用分析人員需求從1990年到2005年的增長百分比預測為73%,增長速度排到各項職業(yè)的前三位.結(jié)論:運籌學在國內(nèi)或國外的推廣前景是非常廣闊的工商企業(yè)對運籌學應用和需求是很大的在工商企業(yè)推廣運籌學方面有大量的工作要做9運籌學的推廣應用前景據(jù)美勞工局1992年統(tǒng)計預測:

10學習運籌學要把重點放在分析、理解有關(guān)的概念、思路上。在自學過程中，應該多向自己提問，如一個方法的實質(zhì)是什么，為什么這樣做，怎么做等。自學時要掌握三個重要環(huán)節(jié)：

1、認真閱讀教材和參考資料，以指定教材為主，同時參考其他有關(guān)書籍。一般每一本運籌學教材都有自己的特點，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學習深入。但是，把時間過多放在參考資料上，會導致思路分散，不利于學好。

2、要在理解了基本概念和理論的基礎上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習的主要作用也是這樣，它同時還有讓你自己檢查自己學習的作用。因此，做題要有信心，要獨立完成，不要怕出錯。因為，整個課程是一個整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學到一定程度，知識融會貫通起來，你做題的正確性自己就有判斷。

3、要學會做學習小結(jié)。每一節(jié)或一章學完后，必須學會用精煉的語言來該書所學內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關(guān)知識和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合自己參考大量文獻后的深入理解，把相關(guān)知識從更深入、廣泛的角度進行論述，則稱之為“把書讀厚”在建數(shù)學模型時要結(jié)合實際應用，要學會用計算機軟件解決問題。如何學習運籌學課程返回目錄10學習運籌學要把重點放在分析、理解有關(guān)的概念、思路上。在自11各章節(jié)的重點、難點

及注意事項11各章節(jié)的重點、難點

及注意事項121、線性規(guī)劃線性規(guī)劃模型：目標函數(shù)：Maxz=50x1+100x2

約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0**看p7--9例1-1，1-2例1.某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗以及資源的限制，如下表：問題：工廠應分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？121、線性規(guī)劃線性規(guī)劃模型：例1.某工廠在131、線性規(guī)劃（續(xù)1.1）1.1線性規(guī)劃的概念線性規(guī)劃的組成：

目標函數(shù)Maxf或Minf

約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素

一般形式(p10--p11)目標函數(shù)：Max（Min）z=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0

標準形式(p11--p15，例1-3)目標函數(shù)：Maxz=c1x1+c2x2+…+cnxn

約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0**練習：p68--70習題11-1，1-2131、線性規(guī)劃（續(xù)1.1）1.1線性規(guī)劃的141、線性規(guī)劃（續(xù)1.2）1.2線性規(guī)劃問題解的概念及性質(zhì)熟悉下列一些解的概念（p15--16）可行解、可行解集（可行域），最優(yōu)解、最優(yōu)值，基、基變量、非基變量，基本解、基本可行解，可行基、最優(yōu)基。

圖解方法及各有關(guān)概念的意義（p16--20）看：圖解法步驟，例1-4，1-5，1-6，1-7，1-8，1-9

下一頁是一個圖解法解題的一個例子，右圖中的陰影部分為可行域。

單純形法的理論基礎（p20--30）

1.2.3段要求看懂，了解如何直接通過對約束矩陣的分析求出基本可行解

1.2.4,1.2.5兩段應注重結(jié)論的了解，如單純形法思想和關(guān)于線性規(guī)劃解的四個定理，而對證明過程則可根據(jù)自己的數(shù)學基礎來掌握：基礎很好，可要求掌握；否則，也可略去不看。**習題：p70習題11-3，1-4141、線性規(guī)劃（續(xù)1.2）1.2線性規(guī)劃問151、線性規(guī)劃（續(xù)1.2）例1.目標函數(shù)：

Maxz=50x1+100x2約束條件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標值z=27500151、線性規(guī)劃（續(xù)1.2）例1.161、線性規(guī)劃（續(xù)1.3）1.3單純形法利用單純形表的方法求解線性規(guī)劃——重點(p30--451.3.1,1.3.2,1.3.3)

此項內(nèi)容是本章的重點，學習中應注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內(nèi)容以及大量練習來掌握。161、線性規(guī)劃（續(xù)1.3）1.3單純形法171、線性規(guī)劃（續(xù)1.3）表格單純形法(p40--p45)

考慮：bi>0i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

≤b1

a21x1+a22x2+…+a2nxn

≤b2…………

am1x1+am2x2+…+amnxn

≤bm

x1，x2，…，xn≥0加入松弛變量：

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn，xn+1，…，xn+m≥0171、線性規(guī)劃（續(xù)1.3）表格單純形法(p418顯然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解對應的基是單位矩陣。以下是初始單純形表：

mm其中：f=-∑cn+ibi

j=cj-∑cn+iaij為檢驗數(shù)cn+i

=0i=1,…,m

i=1i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,…,m1、線性規(guī)劃（續(xù)1.3）18顯然，xj=0j=1,…,n;x191、線性規(guī)劃（續(xù)1.3單純形法解題例）例1?；瘶藴市问剑篗axz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0最優(yōu)解x1=50x2=250x4=50（松弛標量，表示原料A有50個單位的剩余）191、線性規(guī)劃（續(xù)1.3單純形法解題例）例1。化20注意：單純形法中，

1、每一步運算只能用矩陣初等行變換；

2、表中第3列的數(shù)總應保持非負（≥0）；

3、當所有檢驗數(shù)均非正（≤0）時，得到最優(yōu)單純形表。1、線性規(guī)劃（續(xù)1.3）20注意：單純形法中，1、線性規(guī)劃（續(xù)1.3）211、線性規(guī)劃（續(xù)1.3）一般情況的處理及注意事項的強調(diào)（p45--55）

1.3.4段主要是討論初始基本可行解不明顯時，常用的方法。要弄清它的原理，并通過例1-14~例1-17掌握這些方法，同時進一步熟悉用單純形法解題?？紤]一般問題：

bi>0i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0211、線性規(guī)劃（續(xù)1.3）一般情況的處理及注意事221、線性規(guī)劃（續(xù)1.3）大M法：引入人工變量xn+i≥0i=1,…,m;充分大正數(shù)M。得到，

Maxz=c1x1+c2x2+…+cnxn+Mxn+1+…+Mxn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn

，xn+1，…，xn+m≥0顯然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解對應的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足

xn+i=0

i=1,…,m則是原問題的最優(yōu)解；否則，原問題無可行解。221、線性規(guī)劃（續(xù)1.3）大M法：引入人工變231、線性規(guī)劃（續(xù)1.3）兩階段法：引入人工變量xn+i≥0，i=1,…,m；構(gòu)造，

Maxz=-xn+1-xn+2-…-xn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn

，xn+1，…，xn+m≥0第一階段求解上述問題：顯然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解對應的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足

xn+i=0

i=1,…,m則是原問題的基本可行解；否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。231、線性規(guī)劃（續(xù)1.3）兩階段法：引入人工變量241、線性規(guī)劃（續(xù)1.3）例題

例：（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0大M法問題（LP-M）

Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0兩階段法：第一階段問題（LP-1）

Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0241、線性規(guī)劃（續(xù)1.3）例題例：（LP）251、線性規(guī)劃（續(xù)1.3）大M法例大M法（LP-M）

得到最優(yōu)解：(25/3，10/3，0，11)T最優(yōu)目標值：112/3251、線性規(guī)劃（續(xù)1.3）大M法例大M法（261、線性規(guī)劃（續(xù)1.3）兩階段法例第一階段（LP-1）

得到原問題的基本可行解：(0，15/7，25/7，52/7)T

261、線性規(guī)劃（續(xù)1.3）兩階段法例第一階段271、線性規(guī)劃（續(xù)1.3）兩階段法例第二階段把基本可行解填入表中

得到原問題的最優(yōu)解：(25/3，10/3，0，11)T

最優(yōu)目標值：112/3271、線性規(guī)劃（續(xù)1.3）兩階段法例第二階段281、線性規(guī)劃（續(xù)1.3）1.3.5矩陣描述——

此段為選讀，有困難者可不看。

1.3.6段單純形迭代過程中的幾點注意事項是對有關(guān)內(nèi)容的強調(diào)和補充，要認真學習、理解。**習題：p70--71習題11-5，1-6281、線性規(guī)劃（續(xù)1.3）291.4線性規(guī)劃應用——建模（p55--68）本節(jié)介紹了些線性規(guī)劃應用的例子，這些例子從多個方面介紹建模對未來是很有用的，應認真對待。

除了教材上的例子之外，還有許多其它應用：*合理利用線材問題：如何下料使用材最少*配料問題：在原料供應量的限制下如何獲取最大利潤*投資問題：從投資項目中選取方案，使投資回報最大*產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大*勞動力安排：用最少的勞動力來滿足工作的需要*運輸問題：如何制定調(diào)運方案，使總運費最小**下面是一些建模的例子，有興趣者，可作為練習。這些例子有一定的難度，做起來會有一些困難。**習題：p72--73習題11-7，1-8，1-9，1-101、線性規(guī)劃（續(xù)1.4）返回目錄291.4線性規(guī)劃應用——建模（p55--68）130例．某晝夜服務的公交線路每天各時間段內(nèi)所需司機和乘務人員數(shù)如下：

設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員?例：人力資源分配的問題30例．某晝夜服務的公交線路每天各時間段內(nèi)所需司機和乘務人員31解：設xi

表示第i班次時開始上班的司機和乘務人員數(shù),這樣我們建立如下的數(shù)學模型。目標函數(shù)：Minx1+x2+x3+x4+x5+x6

約束條件：s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0例：人力資源分配的問題（續(xù)）31解：設xi表示第i班次時開始上班的司機和乘務人員數(shù),32

例、明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應多少件？例：生產(chǎn)計劃的問題32例、明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過33解：設x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5

分別為由外協(xié)鑄造再由本公司機加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤：利潤=售價-各成本之和可得到xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。這樣我們建立如下的數(shù)學模型。目標函數(shù)：Max15x1+10x2+7x3+13x4+9x5

約束條件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0例：生產(chǎn)計劃的問題（續(xù)）33解：設x1,x2,x3分別為三道工序都由本公司加工的34例、永久機械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過A、B兩道工序加工。假設有兩種規(guī)格的設備A1、A2能完成A工序；有三種規(guī)格的設備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規(guī)格的設備上加工；Ⅱ可在任意規(guī)格的A設備上加工，但對B工序，只能在B1設備上加工；Ⅲ只能在A2與B2設備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤，應如何制定產(chǎn)品加工方案？例：生產(chǎn)計劃的問題（續(xù)）34例、永久機械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過A、B35解：設xijk

表示第i種產(chǎn)品，在第j種工序上的第k種設備上加工的數(shù)量。利潤=[（銷售單價-原料單價）*產(chǎn)品件數(shù)]之和-（每臺時的設備費用*設備實際使用的總臺時數(shù)）之和。這樣我們建立如下的數(shù)學模型:Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123

s.t.5x111+10x211≤6000（設備A1

）

7x112+9x212+12x312≤10000（設備A2

）

6x121+8x221≤4000（設備B1

）

4x122+11x322≤7000（設備B2

）

7x123≤4000（設備B3

）

x111+x112-x121-x122-x123=0（Ⅰ產(chǎn)品在A、B工序加工的數(shù)量相等）

x211+x212-x221=0（Ⅱ產(chǎn)品在A、B工序加工的數(shù)量相等）

x312-x322=0（Ⅲ產(chǎn)品在A、B工序加工的數(shù)量相等）

xijk≥0,i=1,2,3;j=1,2;k=1,2,3例：生產(chǎn)計劃的問題（續(xù)）35解：設xijk表示第i種產(chǎn)品，在第j種工序上36例、某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應如何下料，可使所用原料最省？解：設計下列5種下料方案假設x1,x2,x3,x4,x5分別為上面前5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。目標函數(shù)：Minx1+x2+x3+x4+x5

約束條件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0例：套裁下料問題36例、某工廠要做100套鋼架，每套用長為2.9m,2.137例6．某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應如何安排生產(chǎn)，使利潤收入為最大？例：配料問題37例6．某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格38例：配料問題（續(xù)）解：設xij

表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學模型時，要考慮：對于甲：x11，x12，x13；對于乙：x21，x22，x23；對于丙：x31，x32，x33；對于原料1：x11，x21，x31；對于原料2：x12，x22，x32；對于原料3：x13，x23，x33；目標函數(shù)：利潤最大，利潤=收入-原料支出約束條件：規(guī)格要求4個；供應量限制3個。38例：配料問題（續(xù)）解：設xij表示第i種（甲、39Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）

-0.25x11+0.75x12-0.25x13≤0（原材料2不超過25%）

0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）

-0.5x21+0.5x22-0.5x23≤0（原材料2不超過50%）

x11+x21+x31≤100(供應量限制）

x12+x22+x32≤100(供應量限制）

x13+x23+x33≤60(供應量限制）

xij≥0,i=1,2,3;j=1,2,3例：配料問題（續(xù)）39Maxz=-15x11+25x12+15x13-340

例8．某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資。已知：項目A：從第一年到第五年每年年初都可投資，當年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元；據(jù)測定每萬元每次投資的風險指數(shù)如右表：問：a）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎上使得其投資總的風險系數(shù)為最?。?/p>

解：1）確定決策變量：連續(xù)投資問題設xij(i=1-5，j=1、2、3、4)表示第i年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量：

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42Cx33

Dx24例：投資問題40例8．某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以412）約束條件：第一年：A當年末可收回投資，故第一年年初應把全部資金投出去，于是x11+x12=200；第二年：B次當年末才可收回投資故第二年年初的資金為x11，于是x21+x22+x24=1.1x11；第三年：年初的資金為x21+x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初的資金為x31+x22，于是x41+x42=1.1x31+1.25x22；第五年：年初的資金為x41+x32，于是x51=1.1x41+1.25x32；

B、C、D的投資限制：xi2≤30(I=1、2、3、4)，x33≤80，x24≤1003）目標函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(I=1、2、3、4)，x33≤80，x24≤100

xij≥0(i=1、2、3、4、5；j=1、2、3、4）

b)Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(I=1、2、3、4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330

xij≥0(i=1、2、3、4、5；j=1、2、3、4）例：投資問題（續(xù)）412）約束條件：例：投資問題（續(xù)）422、線性規(guī)劃問題的進一步研究（2.1）2.1對偶原理1、對偶問題：考慮前文例1

若設備和原料都用于外協(xié)加工，工廠收取加工費。試問：設備工時和原料A、B各如何收費才最有競爭力？

設y1，y2，y3分別為每設備工時、原料A、B每單位的收取費用Maxz=50x1+100x2

Minf=300y1+400y2+250y3

s.t.x1+x2≤300s.t.y1+2y2+

≥502x1+x2≤400（不少于甲產(chǎn)品的利潤）

x2≤250y1+y2+y3≥100

x1,x2≥0y1,y2,y3≥0422、線性規(guī)劃問題的進一步研究（2.1）2.1對偶原432、對偶定義對稱形式：互為對偶

(LP)Maxz=cTx

(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”一般形式：若一個問題的某約束為等式，那么對應的對偶問題的相應變量無非負限制；反之，若一個問題的某變量無非負限制，那么對應的對偶問題的相應約束為等式。2、線性規(guī)劃問題的進一步研究（2.1）432、對偶定義2、線性規(guī)劃問題的進一步研究（2.1）443、對偶定理（原問題與對偶問題解的關(guān)系）考慮（LP）和（DP）定理2-1（弱對偶定理）若x,y分別為（LP）和（DP）的可行解，那么cTx≤bTy。推論若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。定理2-2（最優(yōu)性準則定理）若x,y分別為（LP）和（DP）的可行解，且cTx=bTy，那么x,y分別為（LP）和（DP）的最優(yōu)解。定理2-3（主對偶定理）若（LP）和（DP）均可行，那么（LP）和（DP）均有最優(yōu)解，且最優(yōu)值相等。以上定理、推論對任意形式的相應線性規(guī)劃的對偶均有效**習題：p99習題22-12、線性規(guī)劃問題的進一步研究（2.1）443、對偶定理（原問題與對偶問題解的關(guān)系）2、線性規(guī)劃問454、影子價格

——是一個向量，它的分量表示最優(yōu)目標值隨相應資源數(shù)量變化的變化率。若x*,y*

分別為（LP）和（DP）的最優(yōu)解，那么，cTx*=bTy*

。根據(jù)f=bTy*=b1y1*+b2y2*++bmym*

可知f/bi=

yi*

yi*

表示bi變化1個單位對目標f產(chǎn)生的影響，稱yi*

為bi的影子價格。注意：若B是最優(yōu)基，y*=(BT)-1cB為影子價格向量。2、線性規(guī)劃問題的進一步研究（2.1）454、影子價格——是一個向量，它的分量表示最優(yōu)目標值隨465、由最優(yōu)單純形表求對偶問題最優(yōu)解第1章例1。化標準形式：Maxz=50x1+100x2s.t.x1+x2+x3=300，2x1+x2+x4=400x2+x5=250，x1,x2,x3,x4,x5≥0IOB=(p1,p4,p2)(BT)-1cB

B-1最優(yōu)解x1=50x2=250x4=50（松弛標量，表示原料A有50個單位的剩余）影子價格y1=50y2=0y3=50,B-1對應的檢驗數(shù)(BT)-1cB

。2、線性規(guī)劃問題的進一步研究（2.1）465、由最優(yōu)單純形表求對偶問題最優(yōu)解2、線性規(guī)劃問題的472.2對偶單純形法對偶單純形法在什么情況下使用：

應用前提：有一個基，其對應的基本解滿足①單純形表的檢驗數(shù)行全部非正（對偶可行）；②變量取值可有負數(shù)（非可行解）。**注：通過矩陣行變換運算，使所有相應變量取值均為非負數(shù)即得到最優(yōu)單純性表。2、線性規(guī)劃問題的進一步研究（2.2）472.2對偶單純形法2、線性規(guī)劃問題的進一步研究（2.482、線性規(guī)劃問題的進一步研究（2.2）對偶單純形法求解線性規(guī)劃問題過程：

1、建立初始對偶單純形表，對應一個基本解，所有檢驗數(shù)均非正，轉(zhuǎn)2；2、若b’≥0，則得到最優(yōu)解，停止；否則，若有bk<0則選k行的基變量為出基變量，轉(zhuǎn)3；3、若所有akj’≥0(j=1,2,…,n)，則原問題無可行解，停止；否則，若有akj’

<0則選

=min{j’/akj’

┃

akj’

<0}=r’/akr’那么r為進基變量，轉(zhuǎn)4；4、以akr’為轉(zhuǎn)軸元，作矩陣行變換使其變?yōu)?，該列其他元變?yōu)?，轉(zhuǎn)2。482、線性規(guī)劃問題的進一步研究（2.2）對偶單純形法求解線49例：求解線性規(guī)劃問題：

Minf=2x1+3x2+4x3

S.t.

x1+2x2+x3≥32x1-x2+x3≥4

x1,x2,x3≥0

標準化：

MaxZ=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線性規(guī)劃問題的進一步研究（2.2）49例：求解線性規(guī)劃問題：2、線性規(guī)劃問題的進一步研究（2.50表格對偶單純形法**習題：p100習題22-2，2-32、線性規(guī)劃問題的進一步研究（2.2）50表格對偶單純形法2、線性規(guī)劃問題的進一步研究（2.2）512.3靈敏度分析進一步理解最優(yōu)單純形表中各元素的含義考慮問題

Maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn

≤b1

a21x1+a22x2+…+a2nxn

≤b2…………

am1x1+am2x2+…+amnxn

≤bm

x1，x2，…，xn≥0

引入m個松弛變量后，通過計算得到最優(yōu)單純形表。應

-1-1能夠找到最優(yōu)基B的逆矩陣B，以及BN，檢驗數(shù)等。2、線性規(guī)劃問題的進一步研究（2.3）512.3靈敏度分析2、線性規(guī)劃問題的進一步研究（2.3）522、線性規(guī)劃問題的進一步研究（2.3）

最優(yōu)單純形表B-1(BT)-1cBIO522、線性規(guī)劃問題的進一步研究（2.3）最優(yōu)單純形53價值系數(shù)C發(fā)生變化：

m考慮檢驗數(shù)

j=cj-∑criarijj=1,2,……,n

i=1

1、若ck

是非基變量的系數(shù)：設ck

變化為ck+ck

k’=ck+ck-∑criarik=k+ck

只要k’≤0，即

ck≤-k，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)

k

用k’取代，繼續(xù)單純形法的表格計算。

例:MaxZ=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線性規(guī)劃問題的進一步研究（2.3）53價值系數(shù)C發(fā)生變化：2、線性規(guī)劃問題的進一步研究（2.354例：最優(yōu)單純形表從表中看到σ3=C3+ΔC3-（C2*a13+C1*a23）可得到ΔC3

≤9/5時，原最優(yōu)解不變。2、線性規(guī)劃問題的進一步研究（2.3）54例：最優(yōu)單純形表2、線性規(guī)劃問題的進一步研究（2.3）552、若cs

是基變量的系數(shù)：設cs

變化為cs+cs，那么

j’=cj-∑criarij-(

cs+cs)asj=j-csasj，對所有非基變量

i≠s

只要對所有非基變量j’≤0，即j

≤csasj，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù)

j

用j’取代，繼續(xù)單純形法的表格計算。

Max{j

/asj

asj>0}

≤cs≤Min{j

/asj

asj<0}

例:MaxZ=2x1+3x2+0x3+0x4+0x5

S.t.

x1+2x2+x3=84x1+x4=16

4x2+x5=

12x1,x2,x3,x4,x5≥0

2、線性規(guī)劃問題的進一步研究（2.3）552、若cs是基變量的系數(shù)：設cs變化為56例、下表為最優(yōu)單純形表，考慮基變量系數(shù)c2

發(fā)生變化從表中看到σj=Cj-（C1*a1j+C5*a5j+（C2+ΔC2）*a2j）j=3、4可得到-3≤ΔC2

≤1時，原最優(yōu)解不變。2、線性規(guī)劃問題的進一步研究（2.3）56例、下表為最優(yōu)單純形表，考慮基變量系數(shù)c2發(fā)生變化257右端項b發(fā)生變化設分量br變化為br+br，根據(jù)第1章的討論，最優(yōu)解的基變量xB=B-1b，那么只要保持B-1(b+b)≥0，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對偶單純形法繼續(xù)計算。對于問題(LP)Maxz=cTxs.t.Ax≤bx≥0

最優(yōu)單純形表中含有

B-1=（aij

）i=1,…,m;j=n+1,…,n+m那么，新的xi=(B-1b)i+brairi=1,…,m。由此可得，最優(yōu)基不變的條件是

Max{-bi

/air

air>0}

≤br≤Min{-bi

/air

air<0}2、線性規(guī)劃問題的進一步研究（2.3）57右端項b發(fā)生變化2、線性規(guī)劃問題的進一步研究（2.358例、上例最優(yōu)單純形表如下

00.250這里B-1=-20.51各列分別對應b1、b2、b3

的單一

0.5-0.1250變化。因此，設b1增加4，則x1,

x5,x2分別變?yōu)椋?/p>

4+0*4=4，4+(-2)*4=-4<0，2+0.5*4=4用對偶單純形法進一步求解，可得：

x*=(4,3,2,0,0)Tf*=172、線性規(guī)劃問題的進一步研究（2.3）58例、上例最優(yōu)單純形表如下2、線性規(guī)劃問題的進一步研究（259增加一個變量增加變量xn+1

則有相應的pn+1

，cn+1

。那么，計算出

B-1pn+1n+1=cn+1-∑criarin+1

填入最優(yōu)單純形表，若n+1≤0則最優(yōu)解不變；否則，進一步用單純形法求解。例、前例增加x6，p6=(2,6,3)T

，c6=5。計算得到2、線性規(guī)劃問題的進一步研究（2.3）用單純形法進一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.559增加一個變量2、線性規(guī)劃問題的進一步研究（2.3）用單純60增加一個約束增加約束一個之后，應把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個新的非負變量（原約束若是小于等于形式可引入非負松弛變量，否則引入非負人工變量），并通過矩陣行變換把對應基變量的元素變?yōu)?，進一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼?。例、前例增?x1+2x2≤15，原最優(yōu)解不滿足這個約束。于是2、線性規(guī)劃問題的進一步研究（2.3）60增