運(yùn)籌學(xué)的分支

運(yùn)籌學(xué)北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院吳祈宗教授1第一頁，共一百二十八頁。

1、緒論

2、線性規(guī)劃

3、運(yùn)輸問題

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

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

6、排隊(duì)論

7、教學(xué)日歷運(yùn)籌學(xué)——目錄說明本教學(xué)課件是與教材緊密配合使用的，教材為：《運(yùn)籌學(xué)》楊民助編著西安交通大學(xué)出版社，2000年6月參考書：《運(yùn)籌學(xué)》清華大學(xué)出版社或其他的《運(yùn)籌學(xué)》方面本科教材的相關(guān)內(nèi)容下面所標(biāo)注的頁號(hào)，均為本課程教材的頁號(hào)。例如：p123表示第123頁p31-34表示從第31頁到第34頁2第二頁，共一百二十八頁。緒論

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

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

運(yùn)籌學(xué)應(yīng)用分析人員需求從1990年到2005年的增長(zhǎng)百分比預(yù)測(cè)為73%,增長(zhǎng)速度排到各項(xiàng)職業(yè)的前三位.結(jié)論:運(yùn)籌學(xué)在國(guó)內(nèi)或國(guó)外的推廣前景是非常廣闊的工商企業(yè)對(duì)運(yùn)籌學(xué)應(yīng)用和需求是很大的在工商企業(yè)推廣運(yùn)籌學(xué)方面有大量的工作要做9第九頁，共一百二十八頁。學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在自學(xué)過程中，應(yīng)該多向自己提問，如一個(gè)方法的實(shí)質(zhì)是什么，為什么這樣做，怎么做等。自學(xué)時(shí)要掌握三個(gè)重要環(huán)節(jié)：1、認(rèn)真閱讀教材和參考資料，以指定教材為主，同時(shí)參考其他有關(guān)書籍。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致的。注意主從，參考資料會(huì)幫助你開闊思路，使學(xué)習(xí)深入。但是，把時(shí)間過多放在參考資料上，會(huì)導(dǎo)致思路分散，不利于學(xué)好。2、要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時(shí)還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨(dú)立完成，不要怕出錯(cuò)。因?yàn)椋麄€(gè)課程是一個(gè)整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識(shí)融會(huì)貫通起來，你做題的正確性自己就有判斷。3、要學(xué)會(huì)做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會(huì)用精煉的語言來該書所學(xué)內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關(guān)知識(shí)和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合自己參考大量文獻(xiàn)后的深入理解，把相關(guān)知識(shí)從更深入、廣泛的角度進(jìn)行論述，則稱之為“把書讀厚”在建數(shù)學(xué)模型時(shí)要結(jié)合實(shí)際應(yīng)用，要學(xué)會(huì)用計(jì)算機(jī)軟件解決問題。如何學(xué)習(xí)運(yùn)籌學(xué)課程返回目錄10第十頁，共一百二十八頁。各章節(jié)的重點(diǎn)、難點(diǎn)

及注意事項(xiàng)11第十一頁，共一百二十八頁。1、線性規(guī)劃線性規(guī)劃模型：目標(biāo)函數(shù)：Maxz=50x1+100x2約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0**看p7--9例1-1，1-2例1.某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制，如下表：?jiǎn)栴}：工廠應(yīng)分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？12第十二頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.1）1.1線性規(guī)劃的概念線性規(guī)劃的組成：

目標(biāo)函數(shù)Maxf或Minf約束條件s.t.(subjectto)滿足于決策變量用符號(hào)來表示可控制的因素一般形式(p10--p11)目標(biāo)函數(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標(biāo)準(zhǔn)形式(p11--p15，例1-3)目標(biāo)函數(shù)：Maxz=c1x1+c2x2+…+cnxn約束條件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0**練習(xí)：p68--70習(xí)題11-1，1-213第十三頁，共一百二十八頁。1、線性規(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下一頁是一個(gè)圖解法解題的一個(gè)例子，右圖中的陰影部分為可行域。

單純形法的理論基礎(chǔ)（p20--30）1.2.3段要求看懂，了解如何直接通過對(duì)約束矩陣的分析求出基本可行解1.2.4,1.2.5兩段應(yīng)注重結(jié)論的了解，如單純形法思想和關(guān)于線性規(guī)劃解的四個(gè)定理，而對(duì)證明過程則可根據(jù)自己的數(shù)學(xué)基礎(chǔ)來掌握：基礎(chǔ)很好，可要求掌握；否則，也可略去不看。**習(xí)題：p70習(xí)題11-3，1-414第十四頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.2）例1.目標(biāo)函數(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)目標(biāo)值z(mì)=2750015第十五頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.3）1.3單純形法利用單純形表的方法求解線性規(guī)劃——重點(diǎn)(p30--451.3.1,1.3.2,1.3.3)

此項(xiàng)內(nèi)容是本章的重點(diǎn)，學(xué)習(xí)中應(yīng)注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內(nèi)容以及大量練習(xí)來掌握。16第十六頁，共一百二十八頁。1、線性規(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≥017第十七頁，共一百二十八頁。顯然，xj=0j=1,…,n;

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

mm其中：f=-∑cn+ibi

j=cj-∑cn+iaij為檢驗(yàn)數(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第十八頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.3單純形法解題例）例1?；瘶?biāo)準(zhǔn)形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥0最優(yōu)解x1=50x2=250x4=50（松弛標(biāo)量，表示原料A有50個(gè)單位的剩余）19第十九頁，共一百二十八頁。注意：?jiǎn)渭冃畏ㄖ校?、每一步運(yùn)算只能用矩陣初等行變換；2、表中第3列的數(shù)總應(yīng)保持非負(fù)（≥0）；3、當(dāng)所有檢驗(yàn)數(shù)均非正（≤0）時(shí)，得到最優(yōu)單純形表。1、線性規(guī)劃（續(xù)1.3）20第二十頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.3）一般情況的處理及注意事項(xiàng)的強(qiáng)調(diào)（p45--55）1.3.4段主要是討論初始基本可行解不明顯時(shí)，常用的方法。要弄清它的原理，并通過例1-14~例1-17掌握這些方法，同時(shí)進(jìn)一步熟悉用單純形法解題?？紤]一般問題：bi>0i=1,…,mMaxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥021第二十一頁，共一百二十八頁。1、線性規(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是基本可行解對(duì)應(yīng)的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足

xn+i=0

i=1,…,m則是原問題的最優(yōu)解；否則，原問題無可行解。22第二十二頁，共一百二十八頁。1、線性規(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是基本可行解對(duì)應(yīng)的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足

xn+i=0

i=1,…,m則是原問題的基本可行解；否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。23第二十三頁，共一百二十八頁。1、線性規(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≥024第二十四頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.3）大M法例大M法（LP-M）

得到最優(yōu)解：(25/3，10/3，0，11)T最優(yōu)目標(biāo)值：112/325第二十五頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.3）兩階段法例第一階段（LP-1）

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

26第二十六頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.3）兩階段法例第二階段把基本可行解填入表中

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

最優(yōu)目標(biāo)值：112/327第二十七頁，共一百二十八頁。1、線性規(guī)劃（續(xù)1.3）1.3.5矩陣描述——此段為選讀，有困難者可不看。

1.3.6段單純形迭代過程中的幾點(diǎn)注意事項(xiàng)是對(duì)有關(guān)內(nèi)容的強(qiáng)調(diào)和補(bǔ)充，要認(rèn)真學(xué)習(xí)、理解。**習(xí)題：p70--71習(xí)題11-5，1-628第二十八頁，共一百二十八頁。1.4線性規(guī)劃應(yīng)用——建模（p55--68）本節(jié)介紹了些線性規(guī)劃應(yīng)用的例子，這些例子從多個(gè)方面介紹建模對(duì)未來是很有用的，應(yīng)認(rèn)真對(duì)待。

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

設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?例：人力資源分配的問題30第三十頁，共一百二十八頁。解：設(shè)xi表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(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第三十一頁，共一百二十八頁。例、明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？例：生產(chǎn)計(jì)劃的問題32第三十二頁，共一百二十八頁。解：設(shè)x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤(rùn)：利潤(rùn)=售價(jià)-各成本之和可得到xi（i=1,2,3,4,5）的利潤(rùn)分別為15、10、7、13、9元。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(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)計(jì)劃的問題（續(xù)）33第三十三頁，共一百二十八頁。例、永久機(jī)械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過A、B兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？例：生產(chǎn)計(jì)劃的問題（續(xù)）34第三十四頁，共一百二十八頁。解：設(shè)xijk表示第i種產(chǎn)品，在第j種工序上的第k種設(shè)備上加工的數(shù)量。利潤(rùn)=[（銷售單價(jià)-原料單價(jià)）*產(chǎn)品件數(shù)]之和-（每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。這樣我們建立如下的數(shù)學(xué)模型: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（設(shè)備A1）7x112+9x212+12x312≤10000（設(shè)備A2）6x121+8x221≤4000（設(shè)備B1）4x122+11x322≤7000（設(shè)備B2）7x123≤4000（設(shè)備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)計(jì)劃的問題（續(xù)）35第三十五頁，共一百二十八頁。例、某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問：應(yīng)如何下料，可使所用原料最??？解：設(shè)計(jì)下列5種下料方案假設(shè)x1,x2,x3,x4,x5分別為上面前5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(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第三十六頁，共一百二十八頁。例6．某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？例：配料問題37第三十七頁，共一百二十八頁。例：配料問題（續(xù)）解：設(shè)xij表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮：對(duì)于甲：x11，x12，x13；對(duì)于乙：x21，x22，x23；對(duì)于丙：x31，x32，x33；對(duì)于原料1：x11，x21，x31；對(duì)于原料2：x12，x22，x32；對(duì)于原料3：x13，x23，x33；目標(biāo)函數(shù)：利潤(rùn)最大，利潤(rùn)=收入-原料支出約束條件：規(guī)格要求4個(gè)；供應(yīng)量限制3個(gè)。38第三十八頁，共一百二十八頁。Maxz=-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(供應(yīng)量限制）

x12+x22+x32≤100(供應(yīng)量限制）

x13+x23+x33≤60(供應(yīng)量限制）xij≥0,i=1,2,3;j=1,2,3例：配料問題（續(xù)）39第三十九頁，共一百二十八頁。例8．某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元；據(jù)測(cè)定每萬元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺篴）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最??？

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

x21

x31

x41

x51

Bx12

x22

x32

x42Cx33

Dx24例：投資問題40第四十頁，共一百二十八頁。2）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x11+x12=200；第二年：B次當(dāng)年末才可收回投資故第二年年初的資金為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）目標(biāo)函數(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ù)）41第四十一頁，共一百二十八頁。2、線性規(guī)劃問題的進(jìn)一步研究（2.1）2.1對(duì)偶原理1、對(duì)偶問題：考慮前文例1若設(shè)備和原料都用于外協(xié)加工，工廠收取加工費(fèi)。試問：設(shè)備工時(shí)和原料A、B各如何收費(fèi)才最有競(jìng)爭(zhēng)力？

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

Minf=300y1+400y2+250y3s.t.x1+x2≤300s.t.y1+2y2+

≥502x1+x2≤400（不少于甲產(chǎn)品的利潤(rùn)）x2≤250y1+y2+y3≥100

x1,x2≥0y1,y2,y3≥042第四十二頁，共一百二十八頁。2、對(duì)偶定義對(duì)稱形式：互為對(duì)偶(LP)Maxz=cTx

(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”一般形式：若一個(gè)問題的某約束為等式，那么對(duì)應(yīng)的對(duì)偶問題的相應(yīng)變量無非負(fù)限制；反之，若一個(gè)問題的某變量無非負(fù)限制，那么對(duì)應(yīng)的對(duì)偶問題的相應(yīng)約束為等式。2、線性規(guī)劃問題的進(jìn)一步研究（2.1）43第四十三頁，共一百二十八頁。3、對(duì)偶定理（原問題與對(duì)偶問題解的關(guān)系）考慮（LP）和（DP）定理2-1（弱對(duì)偶定理）若x,y分別為（LP）和（DP）的可行解，那么cTx≤bTy。推論若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。定理2-2（最優(yōu)性準(zhǔn)則定理）若x,y分別為（LP）和（DP）的可行解，且cTx=bTy，那么x,y分別為（LP）和（DP）的最優(yōu)解。定理2-3（主對(duì)偶定理）若（LP）和（DP）均可行，那么（LP）和（DP）均有最優(yōu)解，且最優(yōu)值相等。以上定理、推論對(duì)任意形式的相應(yīng)線性規(guī)劃的對(duì)偶均有效**習(xí)題：p99習(xí)題22-12、線性規(guī)劃問題的進(jìn)一步研究（2.1）44第四十四頁，共一百二十八頁。4、影子價(jià)格——是一個(gè)向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。若x*,y*分別為（LP）和（DP）的最優(yōu)解，那么，cTx*=bTy*。根據(jù)f=bTy*=b1y1*+b2y2*++bmym*

可知f/bi=

yi*

yi*表示bi變化1個(gè)單位對(duì)目標(biāo)f產(chǎn)生的影響，稱yi*為bi的影子價(jià)格。注意：若B是最優(yōu)基，y*=(BT)-1cB為影子價(jià)格向量。2、線性規(guī)劃問題的進(jìn)一步研究（2.1）45第四十五頁，共一百二十八頁。5、由最優(yōu)單純形表求對(duì)偶問題最優(yōu)解第1章例1?；瘶?biāo)準(zhǔn)形式：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（松弛標(biāo)量，表示原料A有50個(gè)單位的剩余）影子價(jià)格y1=50y2=0y3=50,B-1對(duì)應(yīng)的檢驗(yàn)數(shù)(BT)-1cB。2、線性規(guī)劃問題的進(jìn)一步研究（2.1）46第四十六頁，共一百二十八頁。2.2對(duì)偶單純形法對(duì)偶單純形法在什么情況下使用：

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

1、建立初始對(duì)偶單純形表，對(duì)應(yīng)一個(gè)基本解，所有檢驗(yàn)數(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為進(jìn)基變量，轉(zhuǎn)4；4、以akr’為轉(zhuǎn)軸元，作矩陣行變換使其變?yōu)?，該列其他元變?yōu)?，轉(zhuǎn)2。48第四十八頁，共一百二十八頁。例：求解線性規(guī)劃問題：Minf=2x1+3x2+4x3

S.t.

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

x1,x2,x3≥0標(biāo)準(zhǔn)化：MaxZ=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線性規(guī)劃問題的進(jìn)一步研究（2.2）49第四十九頁，共一百二十八頁。表格對(duì)偶單純形法**習(xí)題：p100習(xí)題22-2，2-32、線性規(guī)劃問題的進(jìn)一步研究（2.2）50第五十頁，共一百二十八頁。2.3靈敏度分析進(jìn)一步理解最優(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個(gè)松弛變量后，通過計(jì)算得到最優(yōu)單純形表。應(yīng)

-1-1能夠找到最優(yōu)基B的逆矩陣B，以及BN，檢驗(yàn)數(shù)等。2、線性規(guī)劃問題的進(jìn)一步研究（2.3）51第五十一頁，共一百二十八頁。2、線性規(guī)劃問題的進(jìn)一步研究（2.3）最優(yōu)單純形表B-1(BT)-1cBIO52第五十二頁，共一百二十八頁。價(jià)值系數(shù)C發(fā)生變化：

m考慮檢驗(yàn)數(shù)

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

i=1

1、若ck是非基變量的系數(shù)：設(shè)ck變化為ck+ck

k’=ck+ck-∑criarik=k+ck只要k’≤0，即

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

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

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

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥02、線性規(guī)劃問題的進(jìn)一步研究（2.3）53第五十三頁，共一百二十八頁。例：最優(yōu)單純形表從表中看到σ3=C3+ΔC3-（C2*a13+C1*a23）可得到ΔC3

≤9/5時(shí)，原最優(yōu)解不變。2、線性規(guī)劃問題的進(jìn)一步研究（2.3）54第五十四頁，共一百二十八頁。2、若cs是基變量的系數(shù)：設(shè)cs變化為cs+cs，那么

j’=cj-∑criarij-(

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

i≠s

只要對(duì)所有非基變量j’≤0，即j

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

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

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ī)劃問題的進(jìn)一步研究（2.3）55第五十五頁，共一百二十八頁。例、下表為最優(yōu)單純形表，考慮基變量系數(shù)c2發(fā)生變化從表中看到σj=Cj-（C1*a1j+C5*a5j+（C2+ΔC2）*a2j）j=3、4可得到-3≤ΔC2

≤1時(shí)，原最優(yōu)解不變。2、線性規(guī)劃問題的進(jìn)一步研究（2.3）56第五十六頁，共一百二十八頁。右端項(xiàng)b發(fā)生變化設(shè)分量br變化為br+br，根據(jù)第1章的討論，最優(yōu)解的基變量xB=B-1b，那么只要保持B-1(b+b)≥0，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對(duì)偶單純形法繼續(xù)計(jì)算。對(duì)于問題(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ī)劃問題的進(jìn)一步研究（2.3）57第五十七頁，共一百二十八頁。例、上例最優(yōu)單純形表如下

00.250這里B-1=-20.51各列分別對(duì)應(yīng)b1、b2、b3的單一

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

x5,x2分別變?yōu)椋?+0*4=4，4+(-2)*4=-4<0，2+0.5*4=4用對(duì)偶單純形法進(jìn)一步求解，可得：x*=(4,3,2,0,0)Tf*=172、線性規(guī)劃問題的進(jìn)一步研究（2.3）58第五十八頁，共一百二十八頁。增加一個(gè)變量增加變量xn+1則有相應(yīng)的pn+1，cn+1。那么，計(jì)算出B-1pn+1n+1=cn+1-∑criarin+1填入最優(yōu)單純形表，若n+1≤0則最優(yōu)解不變；否則，進(jìn)一步用單純形法求解。例、前例增加x6，p6=(2,6,3)T，c6=5。計(jì)算得到2、線性規(guī)劃問題的進(jìn)一步研究（2.3）用單純形法進(jìn)一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.559第五十九頁，共一百二十八頁。增加一個(gè)約束增加約束一個(gè)之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過矩陣行變換把對(duì)應(yīng)基變量的元素變?yōu)?，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼?。例、前例增?x1+2x2≤15，原最優(yōu)解不滿足這個(gè)約束。于是2、線性規(guī)劃問題的進(jìn)一步研究（2.3）60第六十頁，共一百二十八頁。A中元素發(fā)生變化（只討論N中某一列變化情況）與增加變量xn+1的情況類似，假設(shè)pj變化。那么，重新計(jì)算出B-1pjj=cj-∑criarij填入最優(yōu)單純形表，若j≤0則最優(yōu)解不變；否則，進(jìn)一步用單純形法求解。2、線性規(guī)劃問題的進(jìn)一步研究（2.3）可得最優(yōu)解：x*=(3.2,0.8,0,0,2.4)Tf*=15.261第六十一頁，共一百二十八頁。2、線性規(guī)劃問題的進(jìn)一步研究（2.3）2.3靈敏度分析(內(nèi)容，為重點(diǎn))2.3.1Ci發(fā)生變化2.3.2Bj發(fā)生變化2.3.3增加一個(gè)變量2.3.4增加一個(gè)約束2.3.5A中元素發(fā)生變化**習(xí)題：p100習(xí)題22-4返回目錄62第六十二頁，共一百二十八頁。3.1運(yùn)輸問題模型與性質(zhì)運(yùn)輸模型

例、某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往個(gè)銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？3、運(yùn)輸問題（3.1）63第六十三頁，共一百二十八頁。解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）3、運(yùn)輸問題（3.1）64第六十四頁，共一百二十八頁。系數(shù)矩陣111000000111100100010010001001特點(diǎn)：

1、共有m+n行，分別表示產(chǎn)地和銷地；mn列分別表示各變量；2、每列只有兩個(gè)1，其余為0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用；3、運(yùn)輸問題（3.1）65第六十五頁，共一百二十八頁。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：mnMinf=cijxiji=1j=ins.t.xij=sii=1,2,…,m

j=1m

xij=djj=1,2,…,ni