運籌學(xué)（遠程）CAI課件.ppt

1、1,運籌學(xué),北京理工大學(xué) 管理與經(jīng)濟學(xué)院 吳祈宗教授,2,1、緒 論 2、線 性 規(guī) 劃 3、運 輸 問 題 4、動 態(tài) 規(guī) 劃 5、圖與網(wǎng)絡(luò)分析 6、排 隊 論 7、教學(xué)日歷,運 籌 學(xué) 目錄,說 明 本教學(xué)課件是與教材緊密配合使用的，教材為： 運籌學(xué) 楊民助編著 西安交通大學(xué)出版社，2000年6月 參考書： 運籌學(xué) 清華大學(xué)出版社 或其他的運籌學(xué)方面本科教材的相關(guān)內(nèi)容 下面所標(biāo)注的頁號，均為本課程教材的頁號。例如： p123 表示第123頁 p31-34 表示從第31頁到第34頁,3,緒 論,運籌學(xué)（Operational Research) 直譯為“運作研究” 運籌學(xué)是運用科學(xué)的方法（如

2、分析、試驗、量化等）來決定如何最佳地運營和設(shè)計各種系統(tǒng)的一門學(xué)科。運籌學(xué)對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。 運籌學(xué)有廣泛應(yīng)用（可以自己找一些參考書看） 運籌學(xué)的產(chǎn)生和發(fā)展（可以自己找一些參考書看）,4,運籌學(xué)解決問題的過程,1）提出問題：認清問題 2）尋求可行方案：建模、求解 3）確定評估目標(biāo)及方案的標(biāo)準或方法、途徑 4）評估各個方案：解的檢驗、靈敏性分析等 5）選擇最優(yōu)方案：決策 6）方案實施：回到實踐中 7）后評估：考察問題是否得到完滿解決 1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。,5,運

3、籌學(xué)的分支,線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃 動態(tài)規(guī)劃 多目標(biāo)規(guī)劃 隨機規(guī)劃 模糊規(guī)劃等,圖與網(wǎng)絡(luò)理論 存儲論 排隊論 決策論 對策論 排序與統(tǒng)籌方法 可靠性理論等,6,運籌學(xué)在工商管理中的應(yīng)用,生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下 料、配料問題、物料管理等 庫存管理：多種物資庫存量的管理，庫存方式、庫存 量等 運輸問題：確定最小成本的運輸線路、物資的調(diào)撥、 運輸工具的調(diào)度以及建廠地址的選擇等 人事管理：對人員的需求和使用的預(yù)測，確定人員編 制、人員合理分配，建立人才評價體系等 市場營銷：廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與 銷售計劃制定等 財務(wù)和會計：預(yù)測、貸款、成本分析、定價、證券

4、管 理、現(xiàn)金管理等 * 設(shè)備維修、更新，項目選擇、評價，工程優(yōu)化設(shè)計與管理等,7,運籌學(xué)方法使用情況(美1983)（%）,8,運籌學(xué)方法在中國使用情況(隨機抽樣)（%）,9,運籌學(xué)的推廣應(yīng)用前景,據(jù)美勞工局1992年統(tǒng)計預(yù)測: 運籌學(xué)應(yīng)用分析人員需求從1990年到2005年的增長百分比預(yù)測為73%,增長速度排到各項職業(yè)的前三位. 結(jié)論: 運籌學(xué)在國內(nèi)或國外的推廣前景是非常廣闊的 工商企業(yè)對運籌學(xué)應(yīng)用和需求是很大的 在工商企業(yè)推廣運籌學(xué)方面有大量的工作要做,10,學(xué)習(xí)運籌學(xué)要把重點放在分析、理解有關(guān)的概念、思路上。在自學(xué)過程中，應(yīng)該多向自己提問，如一個方法的實質(zhì)是什么，為什么這樣做，怎么做等。

5、自學(xué)時要掌握三個重要環(huán)節(jié)： 1、認真閱讀教材和參考資料，以指定教材為主，同時參考其他有關(guān)書籍。一般每一本運籌學(xué)教材都有自己的特點，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學(xué)習(xí)深入。但是，把時間過多放在參考資料上，會導(dǎo)致思路分散，不利于學(xué)好。 2、要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨立完成，不要怕出錯。因為，整個課程是一個整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識融會貫通起來，你做題的正確性自己就有判斷。 3、要學(xué)會做學(xué)習(xí)小結(jié)。每

6、一節(jié)或一章學(xué)完后，必須學(xué)會用精煉的語言來該書所學(xué)內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關(guān)知識和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合自己參考大量文獻后的深入理解，把相關(guān)知識從更深入、廣泛的角度進行論述，則稱之為“把書讀厚” 在建數(shù)學(xué)模型時要結(jié)合實際應(yīng)用，要學(xué)會用計算機軟件解決問題。,如何學(xué)習(xí)運籌學(xué)課程,返回目錄,11,各章節(jié)的重點、難點及注意事項,12,1、 線 性 規(guī) 劃,線性規(guī)劃模型： 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 *看 p 7-9 例1-1

7、，1-2,例1. 某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗以及資源的限制，如下表： 問題：工廠應(yīng)分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？,13,1、 線 性 規(guī) 劃 （續(xù)1.1）,1. 1 線性規(guī)劃的概念 線性規(guī)劃的組成： 目標(biāo)函數(shù) Max f 或 Min f 約束條件 s.t. (subject to) 滿足于 決策變量 用符號來表示可控制的因素,一般形式 ( p10- p 11) 目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + +

8、 a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0,標(biāo)準形式 ( p11- p 15 ，例1-3) 目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0 *練習(xí)：p 68-70

9、習(xí)題1 1-1，1-2,14,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 下一頁是一個圖解法解題的一個例子，右圖中的陰影部分為可行域。,單純形法的理論基礎(chǔ)（p20-30） 1.2.3段要求看懂，了解如何直接通過對約束矩陣的分析求出基本可行解 1.2.4, 1.2.5兩段應(yīng)注重結(jié)論的了解，如單純形法思想和關(guān)于線性規(guī)劃解

10、的四個 定理，而對證明過程則可根據(jù)自己的數(shù)學(xué)基礎(chǔ)來掌握： 基礎(chǔ)很好，可要求掌握；否則，也可略去不看。 *習(xí)題：p70 習(xí)題1 1-3，1-4,15,1、 線 性 規(guī) 劃 （續(xù)1.2）,例1. 目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 27500,16,1、 線 性 規(guī) 劃 （續(xù)1.3）,1. 3 單純形法 利用單純形表的方法求解線性規(guī)劃重點 (p30-45 1.3

11、.1, 1.3.2, 1.3.3) 此項內(nèi)容是本章的重點，學(xué)習(xí)中應(yīng)注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內(nèi)容以及大量練習(xí)來掌握。,17,1、 線 性 規(guī) 劃 （續(xù)1.3）,表格單純形法 ( p40- p 45) 考慮： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0 加入松弛變量： Max z = c1

12、x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0,18,顯然，xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是基本可行解 對應(yīng)的基是單位矩陣。 以下是初始單純形表： m m 其中：f = - cn+i bi j = cj - cn+i aij 為檢驗數(shù) cn+i = 0

13、 i= 1,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m,1、 線 性 規(guī) 劃 （續(xù)1.3）,19,1、 線 性 規(guī) 劃 （續(xù)1.3單純形法解題例）,例1?；瘶?biāo)準形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250 x1 , x2 , x3 , x4 , x5 0 最優(yōu)解 x1 = 50 x2 = 250 x4 = 50（松弛標(biāo)量，表示原料A有50個單位的剩余）,20,注意：單純形法中， 1、每一步運算只

14、能用矩陣初等行變換； 2、表中第3列的數(shù)總應(yīng)保持非負（ 0）； 3、當(dāng)所有檢驗數(shù)均非正（ 0）時，得到最優(yōu)單純形表。,1、 線 性 規(guī) 劃 （續(xù)1.3）,21,1、 線 性 規(guī) 劃 （續(xù)1.3）,一般情況的處理及注意事項的強調(diào)（p45-55） 1.3.4段主要是討論初始基本可行解不明顯時，常用的方法。要弄清它的原理，并通過例1-14 例1-17掌握這些方法，同時進一步熟悉用單純形法解題。 考慮一般問題： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a

15、22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0,22,1、 線 性 規(guī) 劃 （續(xù)1.3）,大M法： 引入人工變量 xn+i 0 i = 1 , , m ; 充分大正數(shù) M 。 得到， Max z = c1 x1 + c2 x2 + + cn xn + M xn+1 + + M xn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn +

16、 xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0 顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解 對應(yīng)的基是單位矩陣。 結(jié)論：若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , , m 則是原問題的最優(yōu)解；否則，原問題無可行解。,23,1、 線 性 規(guī) 劃 （續(xù)1.3）,兩階段法：引入人工變量 xn+i 0，i = 1 , , m；構(gòu)造， Max z = - xn+1 - xn+2 - - xn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22

17、x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0 第一階段求解上述問題： 顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解 對應(yīng)的基是單位矩陣。 結(jié)論：若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , , m 則是原問題的基本可行解；否則，原問題無可行解。 得到原問題的基本可行解后，第二階段求解原問題。,24,1、 線 性 規(guī) 劃 （續(xù)1.3）例題,例：（LP） Max z = 5 x1 + 2 x2 +

18、3 x3 - x4 s.t. x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 0 大M法問題（LP - M） Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0 兩階段法 ：第一階段問題（LP -

19、1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0,25,1、 線 性 規(guī) 劃 （續(xù)1.3）大M法例,大M法 （LP - M）,得到最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：112/3,26,1、 線 性 規(guī) 劃 （續(xù)1.3）兩階段法例,第一階段 （LP - 1）,得到原問題的基本可行解：(0，15/7，25/7，52/7)T,27,1、 線 性 規(guī) 劃 （續(xù)1

20、.3）兩階段法例,第二階段 把基本可行解填入表中,得到原問題的最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：112/3,28,1、 線 性 規(guī) 劃 （續(xù)1.3）,1.3.5 矩陣描述 此段為選讀，有困難者可不看。 1.3.6 段單純形迭代過程中的幾點注意事項是對有關(guān)內(nèi)容的強調(diào)和補充，要認真學(xué)習(xí)、理解。 *習(xí)題：p70-71 習(xí)題1 1-5，1-6,29,1. 4 線性規(guī)劃應(yīng)用 建模（p55-68） 本節(jié)介紹了些線性規(guī)劃應(yīng)用的例子，這些例子從多個方面介紹建模對未來是很有用的，應(yīng)認真對待。 除了教材上的例子之外，還有許多其它應(yīng)用： * 合理利用線材問題：如何下料使用材最少 * 配料問題：

21、在原料供應(yīng)量的限制下如何獲取最大利潤 * 投資問題：從投資項目中選取方案，使投資回報最大 * 產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大 * 勞動力安排：用最少的勞動力來滿足工作的需要 * 運輸問題：如何制定調(diào)運方案，使總運費最小 *下面是一些建模的例子，有興趣者，可作為練習(xí)。這些例子有一定的難度，做起來會有一些困難。 *習(xí)題：p72-73 習(xí)題1 1-7，1-8，1-9，1-10,1、 線 性 規(guī) 劃 （續(xù)1.4）,返回目錄,30,例某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下： 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和

22、乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?,例：人力資源分配的問題,31,解：設(shè) xi 表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min x1 + 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ù)）,32,例、 明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)

23、，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？,例：生產(chǎn)計劃的問題,33,解：設(shè) 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ù)學(xué)模型。 目標(biāo)函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約

24、束條件： s.t. 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0,例：生產(chǎn)計劃的問題（續(xù)）,34,例、 永久機械廠生產(chǎn)、三種產(chǎn)品，均要經(jīng)過A、B 兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成 A 工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成 B 工序?？稍贏、B的任何規(guī)格的設(shè)備上加工； 可在任意規(guī)格的A設(shè)備上加工，但對B工序，只能在B1設(shè)備上加工；只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤，應(yīng)如何制

25、定產(chǎn)品加工方案？,例：生產(chǎn)計劃的問題（續(xù)）,35,解：設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設(shè)備上加工的數(shù)量。 利潤 = （銷售單價 - 原料單價）* 產(chǎn)品件數(shù)之和 - （每臺時的設(shè)備費用*設(shè)備實際使用的總臺時數(shù)）之和。 這樣我們建立如下的數(shù)學(xué)模型: Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t. 5x111 + 10 x211 6000 （ 設(shè)備 A1 ） 7x112 + 9x212 + 12x31

26、2 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)計劃的問題（續(xù)）,36,例、某工廠要做100套鋼架，每套用長為2.9

27、m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應(yīng)如何下料，可使所用原料最??？ 解： 設(shè)計下列 5 種下料方案,假設(shè) x1,x2,x3,x4,x5 分別為上面前 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 約束條件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0,例：套裁下料問題,37,例6某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：

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

29、22-40 x31-10 x33 s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 0 （原材料2不超過25%） 0.75x21-0.25x22 -0.25x23 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 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,例：配料問題（

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

31、投資額，使得第五年年末擁有資金的本利在330萬元的基礎(chǔ)上使得其投資總的風(fēng)險系數(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)項目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24,例：投資問題,41,2）約束條件： 第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x11+ x12 = 200； 第二年：B次當(dāng)年末才可收回投資故第二年年初的資金為 x11

32、，于是 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 100 3）目標(biāo)函數(shù)及模型： a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12

33、= 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) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x3

34、1 + 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 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,例：投資問題（續(xù)）,42,2、線性規(guī)劃問題的進一步研究（2.1）,2. 1 對偶原理 1、對偶問題：考慮前文例 1 若設(shè)備和原料都用于外協(xié)加工，工廠收取加工費。試問：設(shè)備工時和原料A、B 各如何收費才最有競爭力？

35、 設(shè) y1 ，y2 ，y3 分別為每設(shè)備工時、 原料 A、B每單位的收取費用 Max z = 50 x1 + 100 x2 Min f = 300 y1 + 400 y2 + 250 y3 s.t. x1 + x2 300 s.t. y1 + 2 y2 + 50 2 x1 + x2 400 （不少于甲產(chǎn)品的利潤） x2 250 y1 + y2 + y3 100 x1 , x2 0 y1, y2 , y3 0,43,2、對偶定義 對稱形式： 互為對偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max -

36、” “Min- ” 一般形式： 若一個問題的某約束為等式，那么對應(yīng)的對偶問題的相應(yīng)變量無非負限制；反之， 若一個問題的某變量無非負限制，那么對應(yīng)的對偶問題的相應(yīng)約束為等式。,2、線性規(guī)劃問題的進一步研究（2.1）,44,3、對偶定理 （原問題與對偶問題解的關(guān)系） 考慮（LP）和（DP） 定理2-1 （弱對偶定理）若 x, y 分別為（LP）和（DP）的可行解，那么 cT x bT y 。 推論 若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。 定理2-2 （最優(yōu)性準則定理）若 x, y 分別為（LP）和（DP）的可行解，且 cT x = bT y ，那么 x, y分別

37、為（LP）和（DP）的最優(yōu)解。 定理2-3 （主對偶定理）若（LP）和（DP）均可行，那么（LP）和（DP）均有最優(yōu)解，且最優(yōu)值相等。 以上定理、推論對任意形式的相應(yīng)線性規(guī)劃的對偶均有效 *習(xí)題：p 99 習(xí)題2 2-1,2、線性規(guī)劃問題的進一步研究（2.1）,45,4、影子價格 是一個向量，它的分量表示最優(yōu)目標(biāo)值隨相應(yīng)資源數(shù)量變化的變化率。 若 x*, y* 分別為（LP）和（DP）的最優(yōu)解， 那么， cT x* = bT y* 。 根據(jù) f = bT y* = b1y1* + b2y2* + + bmym* 可知 f / bi = yi* yi* 表示 bi 變化1個單位對目標(biāo) f 產(chǎn)生的

38、影響，稱 yi* 為 bi的影子價格。 注意：若 B 是最優(yōu)基， y* = (BT)-1 cB 為影子價格向量。,2、線性規(guī)劃問題的進一步研究（2.1）,46,5、由最優(yōu)單純形表求對偶問題最優(yōu)解 第1章例1?；瘶?biāo)準形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 ， 2 x1 + x2 + x4 = 400 x2 + x5 = 250 ， x1 , x2 , x3 , x4 , x5 0 I O B=(p1 , p4 , p2 ) (BT)-1 cB B-1 最優(yōu)解 x1 = 50 x2 = 250 x4 = 50（松弛標(biāo)量，表示原料A有50

39、個單位的剩余）影子價格 y1 = 50 y2 = 0 y3 = 50 , B-1對應(yīng)的檢驗數(shù) (BT)-1 cB 。,2、線性規(guī)劃問題的進一步研究（2.1）,47,2. 2 對偶單純形法 對偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個基，其對應(yīng)的基本解滿足 單純形表的檢驗數(shù)行全部非正（對偶可行）； 變量取值可有負數(shù)（非可行解）。 *注：通過矩陣行變換運算，使所有相應(yīng)變量取值均為非負數(shù)即得到最優(yōu)單純性表。,2、線性規(guī)劃問題的進一步研究（2.2）,48,2、線性規(guī)劃問題的進一步研究（2.2）,對偶單純形法求解線性規(guī)劃問題過程： 1、建立初始對偶單純形表，對應(yīng)一個基本解，所有檢驗數(shù)均非正，轉(zhuǎn)2；

40、 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)?1，該列其他元變?yōu)?0，轉(zhuǎn)2。,49,例：求解線性規(guī)劃問題： Min f = 2 x1 + 3 x2 + 4 x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 標(biāo)準化： Max Z = - 2x1 -

41、3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,2、線性規(guī)劃問題的進一步研究（2.2）,50,表格對偶單純形法 *習(xí)題：p 100 習(xí)題2 2-2，2-3,2、線性規(guī)劃問題的進一步研究（2.2）,51,2.3 靈敏度分析 進一步理解最優(yōu)單純形表中各元素的含義 考慮問題 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn

42、b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0 引入 m 個松弛變量后，通過計算得到最優(yōu)單純形表。應(yīng) -1 -1 能夠找到最優(yōu)基 B的逆矩陣 B ，以及 B N，檢驗數(shù)等。,2、線性規(guī)劃問題的進一步研究（2.3）,52,2、線性規(guī)劃問題的進一步研究（2.3）,最優(yōu)單純形表,B-1,(BT)-1cB,I,O,53,價值系數(shù)C發(fā)生變化： m 考慮檢驗數(shù) j = cj - cri arij j = 1,2,n i = 1 1、若 ck 是非基變量的系數(shù)： 設(shè) ck 變化為 ck + ck k= ck + ck - cri arik = k+ ck 只要

43、 k 0 ，即 ck - k ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù) k 用 k取代，繼續(xù)單純形法的表格計算。 例: Max Z = - 2x1 - 3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,2、線性規(guī)劃問題的進一步研究（2.3）,54,例：最優(yōu)單純形表 從表中看到 3 = C3 +C3 - （C2 * a13 + C1* a23 ） 可得到 C3 9/5 時，原最優(yōu)解不變。,2、線性規(guī)劃問題的進一步研究（2.3）,55,2、若 cs 是基

44、變量的系數(shù)： 設(shè) cs 變化為 cs + cs ，那么 j= cj - cri arij - ( cs + cs ) asj = j - cs asj ，對所有非基變量 i s 只要對所有非基變量 j 0 ，即 j cs asj ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù) j 用 j取代，繼續(xù)單純形法的表格計算。 Maxj / asj asj 0 cs Minj / asj asj 0 例: Max Z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5 S.t. x1 + 2x2+ x3 = 8 4x1 + x4 =16 4x2 +x5 = 12 x1 , x2 , x3 ,

45、 x4 , x5 0,2、線性規(guī)劃問題的進一步研究（2.3）,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）,57,右端項 b 發(fā)生變化 設(shè)分量 br 變化為 br + br ，根據(jù)第1章的討論，最優(yōu)解的基變量 xB = B-1b，那么只要保持 B-1(b + b) 0 ，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對偶單純形法繼續(xù)計算。 對于問題 (LP) M

46、ax z = cT x s.t. Ax b x 0 最優(yōu)單純形表中含有 B-1 = （ aij ）i = 1, , m ; j = n+1, , n+m 那么，新的 xi = (B-1b)i + br air i = 1, , m。由此可得，最優(yōu)基不變的條件是 Max-bi / air air 0 br Min-bi / air air 0 ,2、線性規(guī)劃問題的進一步研究（2.3）,58,例、上例最優(yōu)單純形表如下 0 0.25 0 這里 B-1 = -2 0.5 1 各列分別對應(yīng) b1、b2、b3 的單一 0.5 -0.125 0 變化。因此，設(shè) b1 增加 4，則 x1 , x5 , x2

47、分別變?yōu)椋?4 + 0*4 = 4，4 + (-2)*4 = - 4 0，2 + 0.5*4 = 4 用對偶單純形法進一步求解，可得： x* = ( 4, 3, 2, 0, 0 )T f* = 17,2、線性規(guī)劃問題的進一步研究（2.3）,59,增加一個變量 增加變量 xn+1 則有相應(yīng)的 pn+1 ， cn+1 。那么，計算出 B-1pn+1 n+1 = cn+1 - cri ari n+1 填入最優(yōu)單純形表，若 n+1 0 則最優(yōu)解不變；否則，進一步用單純形法求解。 例、前例增加 x6，p6 = ( 2, 6, 3 )T ，c6 = 5 。計算得到,2、線性規(guī)劃問題的進一步研究（2.3）,

48、用單純形法進一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5,60,增加一個約束 增加約束一個之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個新的非負變量（原約束若是小于等于形式可引入非負松弛變量，否則引入非負人工變量），并通過矩陣行變換把對應(yīng)基變量的元素變?yōu)?，進一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻?例、前例增加3x1+ 2x215，原最優(yōu)解不滿足這個約束。于是,2、線性規(guī)劃問題的進一步研究（2.3）,61,A中元素發(fā)生變化 （只討論 N 中某一列變化情況） 與增加變量 xn+1 的情況類似，假設(shè) pj 變化 。那么

49、，重新計算出 B-1pj j = cj - cri ari j 填入最優(yōu)單純形表，若 j 0 則最優(yōu)解不變；否則，進一步用單純形法求解。,2、線性規(guī)劃問題的進一步研究（2.3）,可得最優(yōu)解：x* = ( 3.2,0.8,0,0,2.4 )T f* = 15.2,62,2、線性規(guī)劃問題的進一步研究（2.3）,2. 3 靈敏度分析 (內(nèi)容，為重點) 2.3.1 Ci 發(fā)生變化 2.3.2 Bj發(fā)生變化 2.3.3 增加一個變量 2.3.4 增加一個約束 2.3.5 A中元素發(fā)生變化 *習(xí)題：p 100 習(xí)題2 2-4,返回目錄,63,3. 1 運輸問題模型與性質(zhì) 運輸模型 例、某公司從兩個產(chǎn)地A1

50、、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往個銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？,3、運 輸 問 題（3.1）,64,解： 產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：,Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；

51、j = 1、2、3）,3、運 輸 問 題（3.1）,65,系數(shù)矩陣 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 特點： 1、共有m+n行，分別表示產(chǎn)地和銷地；mn列分別表示各變量； 2、每列只有兩個 1，其余為 0，分別表示只有一個產(chǎn)地和一個銷地被使用；,3、運 輸 問 題（3.1）,66,設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型： m n Min f = cij xij i=1 j=i n s.t. xij = si i = 1,2,m j=1 m xij = dj j = 1,2,

52、n i=1 xij 0 (i = 1,2,m ; j = 1,2,n),一般運輸模型：產(chǎn)銷平衡 A1、 A2、 Am 表示某物資的m個產(chǎn)地； B1、B2、Bn 表示某物質(zhì)的n個銷地；si 表示產(chǎn)地Ai的產(chǎn)量； dj 表示銷地Bj 的銷量； cij 表示把物資為從產(chǎn)地Ai運往銷地Bj的單位運價。,3、運 輸 問 題（3.1續(xù)）,67,3、運 輸 問 題（3.1續(xù)）,變化： 1）有時目標(biāo)函數(shù)求最大，如求利潤最大或營業(yè)額最大等； 2）當(dāng)某些運輸線路上的能力有限制時，模型中可直接加入（等式或不等式）約束； 3）產(chǎn)銷不平衡時，可加入虛設(shè)的產(chǎn)地（產(chǎn)大于銷時）或銷地（銷大于產(chǎn)時）。,68,3、運 輸 問 題

53、（3.1續(xù)）,求解思路 是 基本可行解 最優(yōu)否 結(jié)束 否 換基 運輸問題基變量的特點 * 運輸問題的基變量共有 m + n -1 個，A的秩為 m + n -1。 * 運輸問題的 m + n -1 個變量構(gòu)成基變量的充分必要條件是不含閉回路。 要弄清下列概念 ：閉回路、閉回路的頂點。,69,3. 2 運輸問題的表上作業(yè)法 本章重點 1、初始基本可行解的確定： （1）西北角法：從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。 （2）最小元素法：從運價最小的

54、格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運價從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。 注：應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個元例外（同時劃去一行和一列）。當(dāng)填上一個數(shù)后行、列同時飽和時，也應(yīng)任意劃去一行（列）在保留的列（行）任意沒被劃去的格內(nèi)標(biāo)一個0。,3、運 輸 問 題（3.2）,70,*,3、運 輸 問 題（3.2）,71,*,3、運 輸 問 題（3.2）,72,2、最優(yōu)性檢驗： 因為求最小，當(dāng)所有檢驗數(shù)均大于等于0時為最優(yōu)解 （1）位勢法求檢驗數(shù)： 位勢：設(shè)對應(yīng)基變量 xij 的 m + n - 1 個 ij ，存在 ui , vj 滿足 ui + vj = cij ，i = 1, , m ; j = 1, , n . 稱這些 ui , vj 為該基本可行解對應(yīng)的位勢。 由于有 m + n 個變量（ ui , vj ），m + n - 1 個方程（基變量個數(shù)），故有