北京理工大學(xué)--運(yùn)籌學(xué)

1、1,運(yùn)籌學(xué),北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院吳祈宗教授,2,1、緒 論 2、線 性 規(guī) 劃 3、運(yùn) 輸 問 題 4、動 態(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é)出版社或其

2、他的《運(yùn)籌學(xué)》方面本科教材的相關(guān)內(nèi)容下面所標(biāo)注的頁號，均為本課程教材的頁號。例如：p123 表示第123頁p31-34 表示從第31頁到第34頁,3,緒 論,運(yùn)籌學(xué)（Operational Research) 直譯為“運(yùn)作研究” 運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法（如分析、試驗(yàn)、量化等）來決定如何最佳地運(yùn)營和設(shè)計各種系統(tǒng)的一門學(xué)科。運(yùn)籌學(xué)對經(jīng)濟(jì)管理系統(tǒng)中的人力、物力、財力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)

3、的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。 運(yùn)籌學(xué)有廣泛應(yīng)用（可以自己找一些參考書看）運(yùn)籌學(xué)的產(chǎn)生和發(fā)展（可以自己找一些參考書看）,4,運(yùn)籌學(xué)解決問題的過程,1）提出問題：認(rèn)清問題2）尋求可行方案：建模、求解3）確定評估目標(biāo)及方案的標(biāo)準(zhǔn)或方法、途徑4）評估各個方案：解的檢驗(yàn)、靈敏性分析等5）選擇最優(yōu)方案：決策6）方案實(shí)施：回到實(shí)踐中7）后評估：考察問題是否得到完滿解決1）2）3）：形成問題；4）5）分析問題：定性分析

4、與定量分析。構(gòu)成決策。,5,運(yùn)籌學(xué)的分支,線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃多目標(biāo)規(guī)劃隨機(jī)規(guī)劃模糊規(guī)劃等,圖與網(wǎng)絡(luò)理論存儲論排隊(duì)論決策論對策論排序與統(tǒng)籌方法可靠性理論等,6,運(yùn)籌學(xué)在工商管理中的應(yīng)用,生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下 料、配料問題、物料管理等庫存管理：多種物資庫存量的管理，庫存方式、庫存

5、 量等運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、 運(yùn)輸工具的調(diào)度以及建廠地址的選擇等人事管理：對人員的需求和使用的預(yù)測，確定人員編 制、人員合理分配，建立人才評價體系等市場營銷：廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與 銷售計劃制定等財務(wù)和會計：預(yù)測、貸款、成本分析、定價、證券管

6、 理、現(xiàn)金管理等 *** 設(shè)備維修、更新，項(xiàng)目選擇、評價，工程優(yōu)化設(shè)計與管理等,7,運(yùn)籌學(xué)方法使用情況(美1983)（%）,8,運(yùn)籌學(xué)方法在中國使用情況(隨機(jī)抽樣)（%）,9,運(yùn)籌學(xué)的推廣應(yīng)用前景,據(jù)美勞工局1992年統(tǒng)計預(yù)測: 運(yùn)籌學(xué)應(yīng)用分析人員需求從1990年到2005年的增長百分比預(yù)測為73%,增長速度排到各項(xiàng)職業(yè)的前三位.結(jié)論:運(yùn)籌學(xué)在國內(nèi)或國外的推廣前景是非常廣

7、闊的工商企業(yè)對運(yùn)籌學(xué)應(yīng)用和需求是很大的在工商企業(yè)推廣運(yùn)籌學(xué)方面有大量的工作要做,10,學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在自學(xué)過程中，應(yīng)該多向自己提問，如一個方法的實(shí)質(zhì)是什么，為什么這樣做，怎么做等。自學(xué)時要掌握三個重要環(huán)節(jié)： 1、認(rèn)真閱讀教材和參考資料，以指定教材為主，同時參考其他有關(guān)書籍。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學(xué)習(xí)深入

8、。但是，把時間過多放在參考資料上，會導(dǎo)致思路分散，不利于學(xué)好。 2、要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助你理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨(dú)立完成，不要怕出錯。因?yàn)椋麄€課程是一個整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識融會貫通起來，你做題的正確性自己就有判斷。 3、要學(xué)會做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會用精

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

10、1 + 100 x2 約束條件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250

11、 x1 , x2 ≥ 0**看 p 7--9 例1-1，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)函

12、數(shù) Max f 或 Min f 約束條件 s.t. (subject to) 滿足于 決策變量 用符號來表示可控制的因素,一般形式 ( p10-- p 11)目標(biāo)函數(shù)： Max （Min）

13、z = c1 x1 + c2 x2 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …

14、… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0,標(biāo)準(zhǔn)形式 ( p11-- p 15 ，例1-3)目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2

15、 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… ……

16、 am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0**練習(xí)：p 68--70 習(xí)題1 1-1，1-2,14,1、 線 性 規(guī) 劃 （續(xù)1.2）,1. 2 線性規(guī)劃問題解的概念及性質(zhì)熟悉下列一些解的概念（p15--16）

17、 可行解、可行解集（可行域），最優(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段要求看懂，了解如何直接通過對約束矩陣的分析求出基本可行解

18、 1.2.4, 1.2.5兩段應(yīng)注重結(jié)論的了解，如單純形法思想和關(guān)于線性規(guī)劃解的四個定理，而對證明過程則可根據(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

19、+ 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 =

20、 27500,16,1、 線 性 規(guī) 劃 （續(xù)1.3）,1. 3 單純形法 利用單純形表的方法求解線性規(guī)劃——重點(diǎn) (p30--45 1.3.1, 1.3.2, 1.3.3) 此項(xiàng)內(nèi)容是本章的重點(diǎn)，學(xué)習(xí)中應(yīng)注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內(nèi)容以及大量練習(xí)來掌握。,17,1、 線 性 規(guī) 劃 （續(xù)1.3）,表格單純形法 ( p40-- p 45)

21、 考慮： 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

22、 ≤ b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ，x2 ，… ，xn ≥ 0加入松弛變量： Max z = c1 x1 + c2

23、 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… ……

24、 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)的基是單位矩陣。以下是初始單純形表：

25、 m m其中：f = -∑ cn+i bi ?j = cj -∑ cn+i aij 為檢驗(yàn)數(shù) cn+i = 0 i= 1,…,m i = 1

26、 i = 1 an+i,i = 1 , an+i,j = 0 ( j≠i ) i , j = 1, … , m,1、 線 性 規(guī) 劃 （續(xù)1.3）,19,1、 線 性 規(guī) 劃 （續(xù)1.3單純形法解題例）,例1?；瘶?biāo)準(zhǔn)形式： Max z = 50 x1 + 100 x2 s.t. x

27、1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250

28、 x1 , x2 , x3 , x4 , x5 ≥ 0最優(yōu)解 x1 = 50 x2 = 250 x4 = 50（松弛標(biāo)量，表示原料A有50個單位的剩余）,20,注意：單純形法中， 1、每一步運(yùn)算只能用矩陣初等行變換； 2、表中第3列的數(shù)總應(yīng)保持非負(fù)（≥ 0）； 3、當(dāng)所有檢驗(yàn)數(shù)均非

29、正（≤ 0）時，得到最優(yōu)單純形表。,1、 線 性 規(guī) 劃 （續(xù)1.3）,21,1、 線 性 規(guī) 劃 （續(xù)1.3）,一般情況的處理及注意事項(xiàng)的強(qiáng)調(diào)（p45--55） 1.3.4段主要是討論初始基本可行解不明顯時，常用的方法。要弄清它的原理，并通過例1-14 ~ 例1-17掌握這些方法，同時進(jìn)一步熟悉用單純形法解題?？紤]一般問題： bi > 0 i = 1 , … , m Max

30、 z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… ……

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

32、+ 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 …… ……

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

34、 , 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

35、 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,

36、 … , 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 + 3 x3 -

37、 x4 s.t. x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x

38、2 + 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.

39、 x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26

40、 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0兩階段法 ：第一階段問題（LP - 1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15

41、 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0,25,1、 線

42、性 規(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.3）兩階段法例,第二階段 把基本可行解填入表中,得到原問題的最優(yōu)解：(25/3，10/3，0，11)T

43、 最優(yōu)目標(biāo)值：112/3,28,1、 線 性 規(guī) 劃 （續(xù)1.3）,1.3.5 矩陣描述—— 此段為選讀，有困難者可不看。 1.3.6 段單純形迭代過程中的幾點(diǎn)注意事項(xiàng)是對有關(guān)內(nèi)容的強(qiáng)調(diào)和補(bǔ)充，要認(rèn)真學(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)認(rèn)真對待

44、。 除了教材上的例子之外，還有許多其它應(yīng)用：* 合理利用線材問題：如何下料使用材最少* 配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤* 投資問題：從投資項(xiàng)目中選取方案，使投資回報最大* 產(chǎn)品生產(chǎn)計劃：合理利用人力、物力、財力等，使獲利最大* 勞動力安排：用最少的勞動力來滿足工作的需要* 運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小 **下面是一些建模的例子，有興趣者，可作為練習(xí)。這些例子有一定的難度，做起來會有

45、一些困難。**習(xí)題：p72--73 習(xí)題1 1-7，1-8，1-9，1-10,1、 線 性 規(guī) 劃 （續(xù)1.4）,返回目錄,30,例．某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?,例：人力資源分配的問題,31,解：設(shè) xi 表示第i班次時開始

46、上班的司機(jī)和乘務(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

47、 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0,例：人力資源分配的問題（續(xù)）,32,例、 明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如下表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少

48、件？,例：生產(chǎn)計劃的問題,33,解：設(shè) x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)， x4,x5 分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(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 + 9x

49、5 約束條件： s.t. 5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0,例：生產(chǎn)計劃的問題（續(xù)）,34,例、 永久機(jī)械廠

50、生產(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è)備上加工，但對B工序，只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤，應(yīng)如何制定產(chǎn)品加工方案？,例：生產(chǎn)計劃的問題（續(xù)）,35,解：設(shè) xijk 表示第 i 種產(chǎn)品，在第 j 種工序上的第

51、 k 種設(shè)備上加工的數(shù)量。 利潤 = [（銷售單價 - 原料單價）* 產(chǎn)品件數(shù)]之和 - （每臺時的設(shè)備費(fèi)用*設(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 + 10x211

52、 ≤ 6000 （ 設(shè)備 A1 ） 7x112 + 9x212 + 12x312 ≤ 10000 （ 設(shè)備 A2 ） 6x121 + 8x221 ≤ 4000 （ 設(shè)備 B1 ） 4x122 + 11x322 ≤ 7000 （ 設(shè)備 B2 ） 7x123

53、 ≤ 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

54、= 1,2; k = 1,2,3,例：生產(chǎn)計劃的問題（續(xù)）,36,例、某工廠要做100套鋼架，每套用長為2.9 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

55、約束條件： s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0,例：套裁下料問題,37,例6．某工廠要用三種

56、原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問：該廠應(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，

57、x31； 對于原料2： x12，x22，x32； 對于原料3： x13，x23，x33； 目標(biāo)函數(shù)： 利潤最大，利潤 = 收入 - 原料支出 約束條件： 規(guī)格要求 4 個； 供應(yīng)量限制 3 個。,39,Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 s.t. 0.5 x11-0.5 x12 -0.5 x1

58、3 ≥ 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)量限制）

59、x12+ x22 + x32 ≤ 100 (供應(yīng)量限制） x13+ x23 + x33 ≤ 60 (供應(yīng)量限制） xij ≥ 0 , i = 1,2,3; j = 1,2,3,例：配料問題（續(xù)）,40,例8．某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年

60、到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元； 據(jù)測定每萬元每次投資的風(fēng)險指數(shù)如右表：問：a）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年

61、投資額，使得第五年年末擁有資金的本利在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)項(xiàng)目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51

62、 B x12 x22 x32 x42 C x33 D x24,例：投資問題,41,2）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x11+ x12 = 200；第二年：B次當(dāng)年末才可收回投資故第二年年初的資金為 x11，于是 x2

63、1 + 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

64、，x24 ≤ 100 3）目標(biāo)函數(shù)及模型：a) Max z = 1.1x51+ 1.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； x5

65、1 = 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 = 20

66、0 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 +

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

68、 設(shè) y1 ，y2 ，y3 分別為每設(shè)備工時、 原料 A、B每單位的收取費(fèi)用Max z = 50 x1 + 100 x2 Min f = 300 y1 + 400 y2 + 250 y3 s.t. x

69、1 + x2 ≤ 300 s.t. y1 + 2 y2 + ≥ 50 2 x1 + x2 ≤ 400 （不少于甲產(chǎn)品的利潤） x2 ≤ 250 y1 + y2 + y3 ≥ 100