運籌學(xué)課件 1

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

2、erational Research) 直譯為“運作研究” 運籌學(xué)是運用科學(xué)的方法（如分析、試驗、量化等）來決定如何最佳地運營和設(shè)計各種系統(tǒng)的一門學(xué)科。運籌學(xué)對經(jīng)濟管理系統(tǒng)中的人力、物力、財力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。 運籌學(xué)有廣泛應(yīng)用運籌學(xué)的產(chǎn)生和發(fā)展,4,運籌學(xué)解決問題的過程,1）提出問題：認(rèn)清問題2）尋求可行方案：建模、求解3）確定評估目標(biāo)及方案的標(biāo)準(zhǔn)或方

3、法、途徑4）評估各個方案：解的檢驗、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實施：回到實踐中7）后評估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析與定量分析。構(gòu)成決策。,5,運籌學(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è)的計劃

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

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

6、,據(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ì)是什么，為什么這樣做，怎么做等。自學(xué)時要掌握三個重要環(huán)節(jié)

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

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

9、計算機軟件解決問題。,如何學(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 ≤

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

11、制，如下表：問題：工廠應(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、 決策變量 用符號來表示可控制的因,一般形式 ( 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ī)劃問題解的概念及性質(zhì)熟悉下列一些解的概念（p12--18） 可行解、可行解集（可行域），最優(yōu)解、最優(yōu)值，基、基變量、非基變量，基本解、基本可行解，可行基、最優(yōu)基。,圖解方法及各有關(guān)概念的意義（p4--6） 看：圖解法步驟， p6 下一頁是一個圖解法解題的一個例子，右圖中的陰影部分為可行域。,單純

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

18、條件：≥,=,≤變量符號：：≥0, 自由,≤0線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：max約束條件：=變量符號：≥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)解在極點上,,,,,,,,,,,,,

19、,凸集,凸集,不是凸集,,極點,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、個極點。目標(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ǔ)可行解，表示可行域的一個極點。目標(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ǔ)解，但不是可行解，不是一個極點。,23

21、,,,,基變量x1、x2、x6，非基變量x3、x4、x5,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基礎(chǔ)可行解，表示可行域的一個極點。目標(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ǔ)可行解，表示可行域的一個極點。目標(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ù)概念,,約束直線,滿足一個等式約束的解,約束半平面,滿足一個不等式約束的解,約束半平面的交集：凸多邊形,滿足一組不等式約束的解,約束直線的交點,基礎(chǔ)解,可行域的極點,基礎(chǔ)可行解,,,,,,目標(biāo)函數(shù)等值線：一組平行線,目標(biāo)函數(shù)值等于一個常數(shù)的解,,34,單純形表,,35,求解線性規(guī)劃問題,寫成標(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ī)劃——重點 (p36—51) 此項內(nèi)容是本章的重點，學(xué)習(xí)中應(yīng)注意掌

28、握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內(nèi)容以及大量練習(xí)來掌握。,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 是基本可行解 對應(yīng)的基是單位矩陣。以下是初始單純形表： m m其中：f = ∑ cn+i bi ?j = ∑ cn+i aij - cj 為檢驗數(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,單純形法的計算步驟(1),43,單純形法的計算步驟(2),44,注意：單純形法中， 1

34、、每一步運算只能用矩陣初等行變換； 2、表中第3列的數(shù)總應(yīng)保持非負(fù)（≥ 0）； 3、當(dāng)所有檢驗數(shù)均為正（ ≥ 0）時，得到最優(yōu)單純形表。,單純形法的計算步驟(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由于所有檢驗系數(shù)都大于0,因此已得到最優(yōu)解X= (4，6，4，0, 0)T,z=42,46,1、 線 性 規(guī) 劃,一般情況的處理及注意事項的強調(diào)（p41--51） 這段主要是討論初始基本可行解不明顯時，常用的方法。弄清它的原理，并通過例題掌握這些方法，同時進(jì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 是基本可行解 對應(yīng)的基是單位矩陣。結(jié)論：1 .若得到的

41、最優(yōu)解X,而且X的基變矢中不含有人工變量,則X的前n個分量就構(gòu)成原LP問題的一個最優(yōu)基本解;否則原問題無可行解.,48,2.若迭代的最終結(jié)果為原問題解無界,此時若最末單純形表的“基列”中不含有人工變量,則原問題也是解界,否則原問題無可行解.注意:一旦某個人工變量離基,即可將其刪除,因此用單純形表計算時,離基的人工變量計算工作可以省去.,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第一階段求解上述問題顯然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解 對應(yīng)的基是單位矩陣。結(jié)論：(p43-4

44、4) 若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , … , m 則是原問題的基本可行解；否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。,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法問題（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兩階段法 ：第一階段問題

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）,得到原問題的基本可行解：(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)目標(biāo)值：112/3,54,1、 線 性 規(guī) 劃 （續(xù)1.3）,1.3.5 矩陣描述—— 此段為選讀，有困難者可不

51、看。 1.3.6 段單純形迭代過程中的幾點注意事項是對有關(guān)內(nèi)容的強調(diào)和補充，要認(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)用的例子，這些例子從多個方面介紹建模對未來是很有用的，應(yīng)認(rèn)真對待。 除了教材上的例子之外，還有許多其它應(yīng)用：* 合理利用線材問題：如何下料使用材最少* 配料問題：在原料供應(yīng)量的限制

52、下如何獲取最大利潤* 投資問題：從投資項目中選取方案，使投資回報最大* 產(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）,返回目錄

53、,56,例．某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下： 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?,例：人力資源分配的問題,57,解：設(shè) xi 表示第i班次時開始上班的司機和乘務(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、配的問題（續(xù)）,58,例、 明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？,例：生產(chǎn)計劃的問題,59,解：設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)， x4,x5 分

56、別為由外協(xié)鑄造再由本公司機加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 求 xi 的利潤：利潤 = 售價 - 各成本之和可得到 xi（i=1,2,3,4,5）的利潤分別為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)計劃的問題（續(xù)）,60,例、 永久機械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過A、B 兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成 A 工序；有三種規(guī)格的設(shè)備B1、B2、

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

59、的總臺時數(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)計劃的問題（續(xù)）,62,例、某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1

62、.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

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

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

65、數(shù)： 利潤最大，利潤 = 收入 - 原料支出 約束條件： 規(guī)格要求 4 個； 供應(yīng)量限制 3 個。,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不超過25%

66、） 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 + x

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

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

69、 設(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