運(yùn)籌學(xué)課件 1

1、1,管理運(yùn)籌學(xué)課件,2,1、緒 論 2、線 性 規(guī) 劃 3、對(duì)偶 問(wèn) 題 4、運(yùn) 輸 問(wèn) 題 5、動(dòng) 態(tài) 規(guī)劃 6、圖與網(wǎng)絡(luò)分析 7、決策論,運(yùn) 籌 學(xué) ——目錄,說(shuō) 明 本教學(xué)課件是與教材緊密配合使用的，教材為： 《管理運(yùn)籌學(xué)》，韓大衛(wèi)編著，大連理工大學(xué)出版社。 參考書：《運(yùn)籌學(xué)》清華大學(xué)出版社《管理運(yùn)籌學(xué)》方面本科教材的相關(guān)內(nèi)容,3,緒 論,運(yùn)籌學(xué)（Op

2、erational Research) 直譯為“運(yùn)作研究” 運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、量化等）來(lái)決定如何最佳地運(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ā)展,4,運(yùn)籌學(xué)解決問(wèn)題的過(guò)程,1）提出問(wèn)題：認(rèn)清問(wèn)題2）尋求可行方案：建模、求解3）確定評(píng)估目標(biāo)及方案的標(biāo)準(zhǔn)或方

3、法、途徑4）評(píng)估各個(gè)方案：解的檢驗(yàn)、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實(shí)施：回到實(shí)踐中7）后評(píng)估：考察問(wèn)題是否得到完滿解決1）2）3）：形成問(wèn)題；4）5）分析問(wèn)題：定性分析與定量分析。構(gòu)成決策。,5,運(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)籌方法可靠性理論等,6,運(yùn)籌學(xué)在工商管理中的應(yīng)用,生產(chǎn)計(jì)劃：生產(chǎn)作業(yè)的計(jì)劃

4、、日程表的編排、合理下 料、配料問(wèn)題、物料管理等庫(kù)存管理：多種物資庫(kù)存量的管理，庫(kù)存方式、庫(kù)存 量等運(yùn)輸問(wèn)題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、 運(yùn)輸工具的調(diào)度以及建廠地址的選擇等人事管理：對(duì)人員的需求和使用的預(yù)測(cè)，確定人員編 制、人員合

5、理分配，建立人才評(píng)價(jià)體系等市場(chǎng)營(yíng)銷：廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開(kāi)發(fā)與 銷售計(jì)劃制定等財(cái)務(wù)和會(huì)計(jì)：預(yù)測(cè)、貸款、成本分析、定價(jià)、證券管 理、現(xiàn)金管理等 *** 設(shè)備維修、更新，項(xiàng)目選擇、評(píng)價(jià)，工程優(yōu)化設(shè)計(jì)與管理等,7,運(yùn)籌學(xué)方法使用情況(美1983)（%）,8,運(yùn)籌學(xué)方法在中國(guó)使用情況(隨機(jī)抽樣)（%）,9,運(yùn)籌學(xué)的推廣應(yīng)用前景

6、,據(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é)方面有大量的工作要做,10,學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在自學(xué)過(guò)程中，應(yīng)該多向自己提問(wèn)，如一個(gè)方法的實(shí)質(zhì)是什么，為什么這樣做，怎么做等。自學(xué)時(shí)要掌握三個(gè)重要環(huán)節(jié)

7、 1、認(rèn)真閱讀教材和參考資料，以指定教材為主，同時(shí)參考其他有關(guān)書籍。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致的。注意主從，參考資料會(huì)幫助你開(kāi)闊思路，使學(xué)習(xí)深入。但是，把時(shí)間過(guò)多放在參考資料上，會(huì)導(dǎo)致思路分散，不利于學(xué)好。 2、要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時(shí)還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨(dú)立完

8、成，不要怕出錯(cuò)。因?yàn)?，整個(gè)課程是一個(gè)整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識(shí)融會(huì)貫通起來(lái)，你做題的正確性自己就有判斷。 3、要學(xué)會(huì)做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會(huì)用精煉的語(yǔ)言來(lái)該書所學(xué)內(nèi)容。這樣，你才能夠從較高的角度來(lái)看問(wèn)題，更深刻的理解有關(guān)知識(shí)和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合自己參考大量文獻(xiàn)后的深入理解，把相關(guān)知識(shí)從更深入、廣泛的角度進(jìn)行論述，則稱之為“把書讀厚”在建數(shù)學(xué)模型時(shí)要結(jié)合實(shí)際應(yīng)用，要學(xué)會(huì)用

9、計(jì)算機(jī)軟件解決問(wèn)題。,如何學(xué)習(xí)運(yùn)籌學(xué)課程,返回目錄,11,各章節(jié)的重點(diǎn)、難點(diǎn)及注意事項(xiàng),12,1、 線 性 規(guī) 劃,線性規(guī)劃模型： 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤

10、400 x2 ≤ 250 x1 , x2 ≥ 0**看 p 1 例1-1，1-2,例1. 某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限

11、制，如下表：?jiǎn)栴}：工廠應(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) 滿足于

12、 決策變量 用符號(hào)來(lái)表示可控制的因,一般形式 ( p10-- p 11)目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1

13、 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm

14、 x1 ，x2 ，… ，xn ≥ 0,標(biāo)準(zhǔn)形式 ( 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 x

15、2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0

16、**練習(xí)：p 28-29 習(xí)題1-3,14,1、 線 性 規(guī) 劃 （續(xù)1.2）,1. 2 線性規(guī)劃問(wèn)題解的概念及性質(zhì)熟悉下列一些解的概念（p12--18） 可行解、可行解集（可行域），最優(yōu)解、最優(yōu)值，基、基變量、非基變量，基本解、基本可行解，可行基、最優(yōu)基。,圖解方法及各有關(guān)概念的意義（p4--6） 看：圖解法步驟， p6 下一頁(yè)是一個(gè)圖解法解題的一個(gè)例子，右圖中的陰影部分為可行域。,單純

17、形法的理論基礎(chǔ)（p31--36） 1.2.3段要求看懂，了解如何直接通過(guò)對(duì)約束矩陣的分析求出基本可行解 1.2.4, 1.2.5兩段應(yīng)注重結(jié)論的了解，如單純形法思想和關(guān)于線性規(guī)劃解的四個(gè)定理，而對(duì)證明過(guò)程則可根據(jù)自己的數(shù)學(xué)基礎(chǔ)來(lái)掌握： 基礎(chǔ)很好，可要求掌握；否則，也可略去不看。**習(xí)題：p51 習(xí)題2-1,15,線性規(guī)劃模型,線性規(guī)劃模型的結(jié)構(gòu)目標(biāo)函數(shù) ：max，min約束

18、條件：≥,=,≤變量符號(hào)：：≥0, 自由,≤0線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：max約束條件：=變量符號(hào)：≥0,16,線性規(guī)劃的圖解,max z=x1+3x2s.t. x1+ x2≤6-x1+2x2≤8x1 ≥0, x2≥0,,,,,,,,,,,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,,6,4,-8,6,0,x1,x2,17,可行域的性質(zhì),線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解在極點(diǎn)上,,,,,,,,,,,,,

19、,凸集,凸集,不是凸集,,極點(diǎn),18,線性規(guī)劃的基本概念,線性規(guī)劃的基矩陣、基變量、非基變量,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,,,,=,,,,,,,,,,,,,目標(biāo)函數(shù),約束條件,行列式≠0基矩陣,右邊常數(shù),,,,19,20,,,,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基礎(chǔ)可行解，表示可行域的一

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

21、,,,,基變量x1、x2、x6，非基變量x3、x4、x5,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：z=18,24,,,,基變量x2、x3、x4，非基變量x1、x5、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基礎(chǔ)解，但不是可行解。,25,,,,非基變量x1、x4 、 x6 ，基變量x2 、

22、x3 、 x5..,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：z=15,26,,,,非基變量x1、 x4 、 x5 ，基變量x2 、 x3 、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基礎(chǔ)解但不是可行解。,27,目標(biāo)函數(shù),約束條件,基矩陣,右邊常數(shù),進(jìn)基變量、離基變量、基變換,,基變量,28

23、,進(jìn)基變量,離基變量,目標(biāo)函數(shù),約束條件,右邊常數(shù),29,目標(biāo)函數(shù),約束條件,新的基矩陣,右邊常數(shù),30,進(jìn)基變量,離基變量,目標(biāo)函數(shù),約束條件,基矩陣,31,目標(biāo)函數(shù),約束條件,新的基矩陣,右邊常數(shù),32,基礎(chǔ)解、基礎(chǔ)可行解,max z=x1+3x2Ds.t. x1+ x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0x1, x2,x3,x4≥0

24、x1=0 E O x2=0 A,,33,幾何概念,代數(shù)概念,,約束直線,滿足一個(gè)等式約束的解,約束半平面,滿足一個(gè)不等式約束的解,約束半平面的交集：凸多邊形,滿足一組不等式約束的解,約束直線的交點(diǎn),基礎(chǔ)解,可行域的極點(diǎn),基礎(chǔ)可行解,,,,,,目標(biāo)函數(shù)等值線：一組平行線,目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解,,34,單純形表,,35,求解線性規(guī)劃問(wèn)題,寫成標(biāo)準(zhǔn)化形式

25、,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進(jìn)基，,x5離基，,x1進(jìn)基，,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，x

26、4，x5，x6）=（14，11，0，0，0，0）max z=86,38,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)

27、 x1 ≥ 0 (D) x2 ≥ 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 27500,39,1、 線 性 規(guī) 劃 （續(xù)1.3）,1. 3 單純形法 利用單純形表的方法求解線性規(guī)劃——重點(diǎn) (p36—51) 此項(xiàng)內(nèi)容是本章的重點(diǎn)，學(xué)習(xí)中應(yīng)注意掌

28、握表格單純形法求解線性規(guī)劃問(wèn)題的基本過(guò)程。要通過(guò)讀懂教材內(nèi)容以及大量練習(xí)來(lá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 + a1

29、2 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ bm

30、 x1 ，x2 ，… ，xn ≥ 0加入松弛變量： Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n

31、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, …

32、, n ; xn+i = bi i = 1 , … , m 是基本可行解 對(duì)應(yīng)的基是單位矩陣。以下是初始單純形表： m m其中：f = ∑ cn+i bi ?j = ∑ cn+i aij - cj 為檢驗(yàn)數(shù) cn+i = 0

33、 i= 1,…,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( j≠i ) i , j = 1, … , m,1、 線 性 規(guī) 劃,42,單純形法的計(jì)算步驟(1),43,單純形法的計(jì)算步驟(2),44,注意：?jiǎn)渭冃畏ㄖ校?1

34、、每一步運(yùn)算只能用矩陣初等行變換； 2、表中第3列的數(shù)總應(yīng)保持非負(fù)（≥ 0）； 3、當(dāng)所有檢驗(yàn)數(shù)均為正（ ≥ 0）時(shí)，得到最優(yōu)單純形表。,單純形法的計(jì)算步驟(3),45,1、 線 性 規(guī)劃,例1?；瘶?biāo)準(zhǔn)形式： Max z = 3 x1 + 5 x2 s.t. x1 + x3 =

35、 8 2x2 + x4 = 12 3x1 +4x2 + x5 = 36 x1 , x

36、2 , x3 , x4 , x5 ≥ 0由于所有檢驗(yàn)系數(shù)都大于0,因此已得到最優(yōu)解X= (4，6，4，0, 0)T,z=42,46,1、 線 性 規(guī) 劃,一般情況的處理及注意事項(xiàng)的強(qiáng)調(diào)（p41--51） 這段主要是討論初始基本可行解不明顯時(shí)，常用的方法。弄清它的原理，并通過(guò)例題掌握這些方法，同時(shí)進(jìn)一步熟悉用單純形法解題?？紤]一般問(wèn)題： bi > 0 i =

37、 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

38、 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0,47,1、 線 性 規(guī) 劃,大M法： 引入人工變量 xn+i ≥ 0 i = 1 , … , m ; 充分大正數(shù) M 。 得到，

39、 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

40、 …… …… 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 是基本可行解 對(duì)應(yīng)的基是單位矩陣。結(jié)論：1 .若得到的

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

42、 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 x2 + … + a2n xn + xn+2 = b2 ……

43、 …… am1 x1 + am2 x2 + … + amn xn + xn+m = bm x1 ，x2 ，… ，xn ，xn+1 ，… ，xn+m ≥ 0第一階段求解上述問(wèn)題顯然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解 對(duì)應(yīng)的基是單位矩陣。結(jié)論：(p43-4

44、4) 若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , … , m 則是原問(wèn)題的基本可行解；否則，原問(wèn)題無(wú)可行解。得到原問(wèn)題的基本可行解后，第二階段求解原問(wèn)題。,50,1、 線 性 規(guī) 劃 （續(xù)1.3）例題,例：（LP） Max z = 5 x1 + 2 x2 + 3 x3 - x4 s.t. x1 + 2 x2 + 3 x3

45、 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26

46、x1 , x2 , x3 , x4 ≥ 0大M法問(wèn)題（LP - M） Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15

47、 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0兩階段法 ：第一階段問(wèn)題

48、（LP - 1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20

49、 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)目標(biāo)值

50、：112/3,52,1、 線 性 規(guī) 劃 （續(xù)1.3）兩階段法例,第一階段 （LP - 1）,得到原問(wèn)題的基本可行解：(0，15/7，25/7，52/7)T,53,1、 線 性 規(guī) 劃 （續(xù)1.3）兩階段法例,第二階段 把基本可行解填入表中,得到原問(wèn)題的最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：112/3,54,1、 線 性 規(guī) 劃 （續(xù)1.3）,1.3.5 矩陣描述—— 此段為選讀，有困難者可不

51、看。 1.3.6 段單純形迭代過(guò)程中的幾點(diǎn)注意事項(xiàng)是對(duì)有關(guān)內(nèi)容的強(qiáng)調(diào)和補(bǔ)充，要認(rèn)真學(xué)習(xí)、理解。**習(xí)題：p70--71 習(xí)題1 1-5，1-6,55,1. 4 線性規(guī)劃應(yīng)用—— 建模（p55--68）本節(jié)介紹了些線性規(guī)劃應(yīng)用的例子，這些例子從多個(gè)方面介紹建模對(duì)未來(lái)是很有用的，應(yīng)認(rèn)真對(duì)待。 除了教材上的例子之外，還有許多其它應(yīng)用：* 合理利用線材問(wèn)題：如何下料使用材最少* 配料問(wèn)題：在原料供應(yīng)量的限制

52、下如何獲取最大利潤(rùn)* 投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大* 產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大* 勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要* 運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小 **下面是一些建模的例子，有興趣者，可作為練習(xí)。這些例子有一定的難度，做起來(lái)會(huì)有一些困難。**習(xí)題：p72--73 習(xí)題1 1-7，1-8，1-9，1-10,1、 線 性 規(guī) 劃 （續(xù)1.4）,返回目錄

53、,56,例．某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開(kāi)始時(shí)上班，并連續(xù)工作八小時(shí)，問(wèn)該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?,例：人力資源分配的問(wèn)題,57,解：設(shè) xi 表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 +

54、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,例：人力資源分

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

56、別為由外協(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ù)： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 約束條件： s.t. 5x1 + 10x2 + 7x3 ≤ 8000 6x1 +

57、 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0,例：生產(chǎn)計(jì)劃的問(wèn)題（續(xù)）,60,例、 永久機(jī)械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過(guò)A、B 兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成 A 工序；有三種規(guī)格的設(shè)備B1、B2、

58、B3能完成 B 工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ 可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問(wèn)：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？,例：生產(chǎn)計(jì)劃的問(wèn)題（續(xù)）,61,解：設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第 k 種設(shè)備上加工的數(shù)量。 利潤(rùn) = [（銷售單價(jià) - 原料單價(jià)）* 產(chǎn)品件數(shù)]之和 - （每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)際使用

59、的總臺(tái)時(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 + 10x211 ≤ 6000 （ 設(shè)備 A1 ） 7x112 + 9x212 + 12x312

60、 ≤ 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)品在

61、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ì)劃的問(wèn)題（續(xù)）,62,例、某工廠要做100套鋼架，每套用長(zhǎng)為2.9 m,2.1 m,1

62、.5 m的圓鋼各一根。已知原料每根長(zhǎng)7.4 m，問(wèn)：應(yīng)如何下料，可使所用原料最??？解： 設(shè)計(jì)下列 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

63、 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0,例：套裁下料問(wèn)題,63,例6．某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？,例：配料問(wèn)題,64,

64、例：配料問(wèn)題（續(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)函

65、數(shù)： 利潤(rùn)最大，利潤(rùn) = 收入 - 原料支出 約束條件： 規(guī)格要求 4 個(gè)； 供應(yīng)量限制 3 個(gè)。,65,Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 s.t. 0.5 x11-0.5 x12 -0.5 x13 ≥ 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 ≤ 0 （原材料2不超過(guò)25%

66、） 0.75x21-0.25x22 -0.25x23 ≥ 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 ≤ 0 （原材料2不超過(guò)50%） x11+ x21 + x31 ≤ 100 (供應(yīng)量限制） x12+ x22 + x32 ≤ 100 (供應(yīng)量限制） x13+ x23 + x

67、33 ≤ 60 (供應(yīng)量限制） xij ≥ 0 , i = 1,2,3; j = 1,2,3,例：配料問(wèn)題（續(xù)）,66,例8．某部門現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過(guò)30萬(wàn)元；項(xiàng)目C：需在第三年年初投資，第五年末能

68、收回本利140%，但規(guī)定最大投資額不能超過(guò)80萬(wàn)元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過(guò)100萬(wàn)元； 據(jù)測(cè)定每萬(wàn)元每次投資的風(fēng)險(xiǎn)指數(shù)如右表：?jiǎn)枺篴）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最小？,解： 1）確定決策變量：連續(xù)投資問(wèn)題

69、 設(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)目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C