1、1,管理運籌學課件,2,1、緒 論 2、線 性 規(guī) 劃 3、對偶 問 題 4、運 輸 問 題 5、動 態(tài) 規(guī)劃 6、圖與網(wǎng)絡分析 7、決策論,運 籌 學 目錄,說 明 本教學課件是與教材緊密配合使用的，教材為： 管理運籌學，韓大衛(wèi)編著，大連理工大學出版社。 參考書： 運籌學清華大學出版社 管理運籌學方面本科教材的相關內(nèi)容,3,緒 論,運籌學（Operational Research) 直譯為“運作研究” 運籌學是運用科學的方法（如分析、試驗、量化等）來決定如何最佳地運營和設計各種系統(tǒng)的一門學科。運籌學對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有

2、效的管理。 運籌學有廣泛應用 運籌學的產(chǎn)生和發(fā)展,4,運籌學解決問題的過程,1）提出問題：認清問題 2）尋求可行方案：建模、求解 3）確定評估目標及方案的標準或方法、途徑 4）評估各個方案：解的檢驗、靈敏性分析等 5）選擇最優(yōu)方案：決策 6）方案實施：回到實踐中 7）后評估：考察問題是否得到完滿解決 1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。,5,運籌學的分支,線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃 動態(tài)規(guī)劃 多目標規(guī)劃 隨機規(guī)劃 模糊規(guī)劃等,圖與網(wǎng)絡理論 存儲論 排隊論 決策論 對策論 排序與統(tǒng)籌方法 可靠性理論等,6,運籌學在工商管理中的應用,生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃

3、、日程表的編排、合理下 料、配料問題、物料管理等 庫存管理：多種物資庫存量的管理，庫存方式、庫存 量等 運輸問題：確定最小成本的運輸線路、物資的調(diào)撥、 運輸工具的調(diào)度以及建廠地址的選擇等 人事管理：對人員的需求和使用的預測，確定人員編 制、人員合理分配，建立人才評價體系等 市場營銷：廣告預算、媒介選擇、定價、產(chǎn)品開發(fā)與 銷售計劃制定等 財務和會計：預測、貸款、成本分析、定價、證券管 理、現(xiàn)金管理等 * 設備維修、更新，項目選擇、評價，工程優(yōu)化設計與管理等,7,運籌學方法使用情況(美1983)（%）,8,運籌學方法在中國使用情況(隨機抽樣)（%）,9,運籌學的推廣應用前景,據(jù)美勞工局1992年統(tǒng)

4、計預測: 運籌學應用分析人員需求從1990年到2005年的增長百分比預測為73%,增長速度排到各項職業(yè)的前三位. 結(jié)論: 運籌學在國內(nèi)或國外的推廣前景是非常廣闊的 工商企業(yè)對運籌學應用和需求是很大的 在工商企業(yè)推廣運籌學方面有大量的工作要做,10,學習運籌學要把重點放在分析、理解有關的概念、思路上。在自學過程中，應該多向自己提問，如一個方法的實質(zhì)是什么，為什么這樣做，怎么做等。 自學時要掌握三個重要環(huán)節(jié) 1、認真閱讀教材和參考資料，以指定教材為主，同時參考其他有關書籍。一般每一本運籌學教材都有自己的特點，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學習深入。但是，把時間

5、過多放在參考資料上，會導致思路分散，不利于學好。 2、要在理解了基本概念和理論的基礎上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習的主要作用也是這樣，它同時還有讓你自己檢查自己學習的作用。因此，做題要有信心，要獨立完成，不要怕出錯。因為，整個課程是一個整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學到一定程度，知識融會貫通起來，你做題的正確性自己就有判斷。 3、要學會做學習小結(jié)。每一節(jié)或一章學完后，必須學會用精煉的語言來該書所學內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻的理解有關知識和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合自己參考大量文獻后的深入理解，把相關知識從更深入、廣泛的角度進行論述，

6、則稱之為“把書讀厚” 在建數(shù)學模型時要結(jié)合實際應用，要學會用計算機軟件解決問題。,如何學習運籌學課程,返回目錄,11,各章節(jié)的重點、難點及注意事項,12,1、 線 性 規(guī) 劃,線性規(guī)劃模型： 目標函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 *看 p 1 例1-1，1-2,例1. 某工廠在計劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原材料的消耗以及資源的限制，如下表： 問題：工廠應分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？,13,1、 線 性 規(guī)

7、 劃 （續(xù)1.1）,1. 1 線性規(guī)劃的概念 線性規(guī)劃的組成： 目標函數(shù) Max f 或 Min f 約束條件 s.t. (subject to) 滿足于 決策變量 用符號來表示可控制的因,一般形式 ( p10- p 11) 目標函數(shù)： Max （Min） 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,標準形式 ( p1

8、1- p 15 ，例1-3) 目標函數(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 *練習：p 28-29 習題1-3,14,1、 線 性 規(guī) 劃 （續(xù)1.2）,1. 2 線性規(guī)劃問題解的概念及性質(zhì) 熟悉下列一些解的概念（p12-18） 可行解、可行解集（可行域），最優(yōu)解、最優(yōu)值，基、基變量、非基變量，基本解、基本可行解，可行基、最

9、優(yōu)基。,圖解方法及各有關概念的意義（p4-6） 看：圖解法步驟， p6 下一頁是一個圖解法解題的一個例子，右圖中的陰影部分為可行域。,單純形法的理論基礎（p31-36） 1.2.3段要求看懂，了解如何直接通過對約束矩陣的分析求出基本可行解 1.2.4, 1.2.5兩段應注重結(jié)論的了解，如單純形法思想和關于線性規(guī)劃解的四個 定理，而對證明過程則可根據(jù)自己的數(shù)學基礎來掌握： 基礎很好，可要求掌握；否則，也可略去不看。 *習題：p51 習題2-1,15,線性規(guī)劃模型,線性規(guī)劃模型的結(jié)構(gòu) 目標函數(shù) ：max，min 約束條件：,=, 變量符號：0, 自由,0 線性規(guī)劃的標準形式 目標函數(shù)：max 約束

10、條件：= 變量符號：0,16,線性規(guī)劃的圖解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目標函數(shù)等值線,最優(yōu)解,6,4,-8,6,0,x1,x2,17,可行域的性質(zhì),線性規(guī)劃的可行域是凸集 線性規(guī)劃的最優(yōu)解在極點上,凸集,凸集,不是凸集,極點,18,線性規(guī)劃的基本概念,線性規(guī)劃的基矩陣、基變量、非基變量,=,=,目標函數(shù),約束條件,行列式0 基矩陣,右邊常數(shù),19,20,基變量x1、x2、x3，非基變量x4、x5、x6,基礎解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基礎可行解，表示可行域的一個極點。 目標函

11、數(shù)值為：z=20,21,基變量x1、x2、x4，非基變量x3、x5、x6,基礎解為 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基礎可行解，表示可行域的一個極點。 目標函數(shù)值為：z=18,22,基變量x1、x2、x5，非基變量x3、x4、x6,基礎解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基礎解，但不是可行解，不是一個極點。,23,基變量x1、x2、x6，非基變量x3、x4、x5,基礎解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基礎可行解，表示可行域的一個極點。 目標函數(shù)值為：z=18,2

12、4,基變量x2、x3、x4，非基變量x1、x5、x6,基礎解為 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基礎解，但不是可行解。,25,非基變量x1、x4 、 x6 ，基變量x2 、 x3 、 x5.,基礎解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基礎可行解，表示可行域的一個極點。 目標函數(shù)值為：z=15,26,非基變量x1、 x4 、 x5 ，基變量x2 、 x3 、x6,基礎解為 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基礎解但不是可行解。,27,目標函數(shù),約束條件,基

13、矩陣,右邊常數(shù),進基變量、離基變量、基變換,基變量,28,進基變量,離基變量,目標函數(shù),約束條件,右邊常數(shù),29,目標函數(shù),約束條件,新的基矩陣,右邊常數(shù),30,進基變量,離基變量,目標函數(shù),約束條件,基矩陣,31,目標函數(shù),約束條件,新的基矩陣,右邊常數(shù),32,基礎解、基礎可行解,max z=x1+3x2D s.t. x1+ x2+x3=6 B -x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A,33,幾何概念,代數(shù)概念,約束直線,滿足一個等式約束的解,約束半平面,滿足一個不等式約束的解,約束半平面的交集： 凸多邊形,滿足一組不等式

14、約束的解,約束直線的交點,基礎解,可行域的極點,基礎可行解,目標函數(shù)等值線： 一組平行線,目標函數(shù)值等于一個常數(shù)的解,34,單純形表,35,求解線性規(guī)劃問題,寫成標準化形式,36,寫出單純形表,25/1,36/2,0,3,2,0,2,72,0,1,1/2,0,1,-1/2,7/1/2,1,x5,1/2,1,0,1/2,18/1/2,4,7,18,-1,1/2,1/2,x2,0,x6離基，,x2進基，,x5離基，,x1進基，,37,0,4,2,2,1,86,0,1,1,0,2,-1,1,x1,0,1,-1,1,4,14,11,0,1,0,x2,3,得到最優(yōu)解，最優(yōu)解為：,（x1，x2，x3，x4

15、，x5，x6）=（14，11，0，0，0，0） max z=86,38,1、 線 性 規(guī) 劃 （續(xù)1.2）,例1. 目標函數(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)目標值 z = 27500,39,1、 線 性 規(guī) 劃 （續(xù)1.3）,1. 3 單純形法 利用單純形表的方法求解線性規(guī)劃重點 (p3651) 此項內(nèi)容是本章的重點，學習中應注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通

16、過讀懂教材內(nèi)容以及大量練習來掌握。,40,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 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1

17、 = 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,41,顯然，xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是基本可行解 對應的基是單位矩陣。 以下是初始單純形表： m m 其中：f = cn+i bi j = cn+i aij - cj 為檢驗數(shù) cn+i = 0 i= 1,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1,

18、 , m,1、 線 性 規(guī) 劃,42,單純形法的計算步驟(1),43,單純形法的計算步驟(2),44,注意：單純形法中， 1、每一步運算只能用矩陣初等行變換； 2、表中第3列的數(shù)總應保持非負（ 0）； 3、當所有檢驗數(shù)均為正（ 0）時，得到最優(yōu)單純形表。,單純形法的計算步驟(3),45,1、 線 性 規(guī)劃,例1?；瘶藴市问剑?Max z = 3 x1 + 5 x2 s.t. x1 + x3 = 8 2x2 + x4 = 12 3x1 +4x2 + x5 = 36 x1 , x2 , x3 , x4 , x5 0 由于所有檢驗系數(shù)都大于0,因此已得到最優(yōu)解 X= (4，6，4，0, 0)T,z=

19、42,46,1、 線 性 規(guī) 劃,一般情況的處理及注意事項的強調(diào)（p41-51） 這段主要是討論初始基本可行解不明顯時，常用的方法。弄清它的原理，并通過例題掌握這些方法，同時進一步熟悉用單純形法解題。 考慮一般問題： 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,47,1、 線 性 規(guī) 劃,大M法： 引入人工變量

20、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 + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0 顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解 對應的基是單位矩陣。

21、結(jié)論： 1 .若得到的最優(yōu)解X,而且X的基變矢中不含有人工變量,則X的前n個分量就構(gòu)成原LP問題的一個最優(yōu)基本解;否則原問題無可行解.,48,2.若迭代的最終結(jié)果為原問題解無界,此時若最末單純形表的“基列”中不含有人工變量,則原問題也是解界,否則原問題無可行解. 注意: 一旦某個人工變量離基,即可將其刪除,因此用單純形表計算時,離基的人工變量計算工作可以省去.,1、 線 性 規(guī) 劃,49,1、 線 性 規(guī) 劃,兩階段法：引入人工變量 xn+i 0，i = 1 , , m；構(gòu)造， Max z = - xn+1 - xn+2 - - xn+m s.t. a11 x1 + a12 x2 + + a1

22、n 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 第一階段求解上述問題 顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解 對應的基是單位矩陣。 結(jié)論：(p43-44) 若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , , m 則是原問題的基本可行解；否則，原問題無可行解。 得到原問題的基本可行解后，第二階段求解原問題。,50,1、 線 性 規(guī) 劃

23、（續(xù)1.3）例題,例：（LP） Max z = 5 x1 + 2 x2 + 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 ,

24、x3 , x4 , x5 , x6 0 兩階段法 ：第一階段問題（LP - 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,51,1、 線 性 規(guī) 劃 （續(xù)1.3）大M法例,大M法 （LP - M）,得到最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標值：112/3,52,1、 線 性 規(guī) 劃 （續(xù)1.3）兩階段法例,第一階段 （LP - 1）,得到原問題的基本可行解

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

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

27、人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員?,例：人力資源分配的問題,57,解：設 xi 表示第i班次時開始上班的司機和乘務人員數(shù),這樣我們建立如下的數(shù)學模型。 目標函數(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ù)）,58,例、 明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過

28、鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應多少件？,例：生產(chǎn)計劃的問題,59,解：設 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ù)：

29、 Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件： 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ù)）,60,例、 永久機械廠生產(chǎn)、三種產(chǎn)品，均要經(jīng)過A、B 兩道工序加工。假設有兩種規(guī)格的設備A1、A2能完成 A 工序；有三種規(guī)格的設備B1、B2、B3能完成 B 工序?？稍贏、B的任何規(guī)格的設備上加工； 可在任意規(guī)格的A設備上加工，但對B工序，只能在B1設備上加工

30、；只能在A2與B2設備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤，應如何制定產(chǎn)品加工方案？,例：生產(chǎn)計劃的問題（續(xù)）,61,解：設 xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設備上加工的數(shù)量。 利潤 = （銷售單價 - 原料單價）* 產(chǎn)品件數(shù)之和 - （每臺時的設備費用*設備實際使用的總臺時數(shù)）之和。 這樣我們建立如下的數(shù)學模型: 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 x21

31、1 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,例

32、：生產(chǎn)計劃的問題（續(xù)）,62,例、某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應如何下料，可使所用原料最??？ 解： 設計下列 5 種下料方案,假設 x1,x2,x3,x4,x5 分別為上面前 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。 目標函數(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,例：套裁下料問題,63,例6某工廠要

33、用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應如何安排生產(chǎn)，使利潤收入為最大？,例：配料問題,64,例：配料問題（續(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 個。,65,

34、Max z = -15x11+25x12+15x13-30 x21+10 x22-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 (供應量限制） x12+ x22 + x32 100 (供應量限制） x13+ x23 + x33 60 (供應量限制

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

36、資額，使得第五年年末擁有資金的本利金額為最大？ b）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330萬元的基礎上使得其投資總的風險系數(shù)為最小？,解： 1）確定決策變量：連續(xù)投資問題 設 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,例：投資問題,67,2）約束條件： 第一年：A當年末可收回投資，故第一年年初應把全部資金投出去，于是 x11+ x1

37、2 = 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 100 3）目標函數(shù)及模型： a) Max z = 1.1x51+ 1.

38、25x42+ 1.4x33 + 1.55x24 s.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) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+

39、 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 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,例：投資問題（續(xù)）,68,2、線性規(guī)劃問題的進一步研究（2.1）,2. 1 對偶原理 1、對偶問題：考慮前文例 1 若設備和原料都用于外

40、協(xié)加工，工廠收取加工費。試問：設備工時和原料A、B 各如何收費才最有競爭力？ 設 y1 ，y2 ，y3 分別為每設備工時、 原料 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,69,2、對偶定義 對稱形式： 互為對偶 (LP) Max z = cT x (DP) Min f = bT y

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

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

43、f / bi = yi* yi* 表示 bi 變化1個單位對目標 f 產(chǎn)生的影響，稱 yi* 為 bi的影子價格。 注意：若 B 是最優(yōu)基， y* = (BT)-1 cB 為影子價格向量。,2、線性規(guī)劃問題的進一步研究（2.1）,72,5、由最優(yōu)單純形表求對偶問題最優(yōu)解 第1章例1?；瘶藴市问剑?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)解

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

45、題過程： 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)?1，該列其他元變?yōu)?0，轉(zhuǎn)2。,75,例：求解線性規(guī)劃問題： Min f = 2 x1 + 3 x2 + 4 x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3

46、4 x1 , x2 , x3 0 標準化： 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.2）,76,表格對偶單純形法 *習題：p 100 習題2 2-2，2-3,2、線性規(guī)劃問題的進一步研究（2.2）,對偶線性規(guī)劃,對偶的定義 對偶問題的性質(zhì) 原始對偶關系 目標函數(shù)值之間的關系 最優(yōu)解之間的關系互補松弛關系 對偶可行基對偶單純形法 對偶的經(jīng)濟解釋,DUAL,一、對偶的定義,原始問題 m

47、in z=CTX s.t.AXb X 0,對偶問題 max y=bTW s.t. ATWC W 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,二、對偶問題的性質(zhì),1、對偶的對偶就是原始問題,2、其他形式問題的對偶,三、原始對偶關系,1、可行解的目標函數(shù)值之間的關系 設XF、WF分別是原始問題和對偶問題的可行解 z=CTXF WTAXF WTb=y 2、最優(yōu)解的目標函數(shù)值之間的關系 設Xo、Wo分別是原始問題和對偶問題的最優(yōu)解 z=CTXo=WoTAXo=WoTb=y,3、原始問題和對偶問題最優(yōu)解之間的互補松弛關系,min z=CTX s.t. AX-XS=b X, XS0,

48、max y=bTW s.t. ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,互補松弛關系,min z=CTX s.t.AX-XS=b X, XS 0,max y=bTW s.t. ATW+WS=C W, WS 0,XTWS=0 WTXS=0,m,n,=,W,WS,AT,I,C,n,=,A,XS,-I,b,n,m,m,X,原始問題和對偶問題變量、松弛變量的維數(shù),w1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,對偶問題的變量 對偶問題的松弛變量,原始問題的變量 原始問題的松

49、弛變量,xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n) 在一對變量中，其中一個大于0，另一個一定等于0,Kuhn-Tucher 條件,3、原始問題和對偶問題最優(yōu)解的充分必要條件 (1)原始可行條件（PFC） AX-XS=b X, XS 0 (2)對偶可行條件（DFC） ATW+WS=C W, WS 0 (3)互補松弛條件（CSC） XTWS=0 WTXS=0,四、對偶單純形法,1、用單純形表求解原始問題的四種形式,min z=CTX s.t. AXb X 0,min z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0,max z=CTX

50、 s.t. AX b X 0,（2）,（3）,（4）,（1）,單純形表和對偶(1),min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,對偶問題,原始問題,引進松弛變量,引進松弛變量,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,WT=CBTB-1 WST=CT-WTA,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t.

51、ATW+WS=C W 0, WS0,min z=CTX s.t. AX b X 0,max y=bTW s.t. ATWC W 0,單純形表和對偶(2),對偶問題,原始問題,引進松弛變量,引進松弛變量,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,WT=CBTB-1 WST=CT-WTA,max z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW-WS=C W 0, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW C W 0,單純形

52、表和對偶(3),對偶問題,原始問題,引進松弛變量,引進松弛變量,max z=CTX s.t. AX-XS=b X, XS0,min y=bTW s.t. ATW-WS=C W 0, WS0,WT=CBTB-1 WST=WTA- CT,max z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW-WS=C W, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW C W 0,單純形表和對偶(4),對偶問題,原始問題,引進松弛變量,引進松弛變量,max z=CTX s.t. AX+XS=b X, XS0,min y=bT

53、W s.t. ATW-WS=C W, WS0,WT=CBTB-1 WST=WTA- CT,2、對偶單純形法（初始解原始不可行的問題）,已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 對偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,3、初始解原始、對偶都不可行的問題,解法1：先解決原始可行性,在得到原始可行解時同時得到對偶可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z

54、=17 對偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,解法2：先解決對偶可行性,已得到對偶可行解，再用對偶單純形法求解,得到原始可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 對偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,106,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 b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0 引入 m 個松弛變量后，通過計算得到最優(yōu)單純形表。應 -1 -1 能夠找