1、Page 1運籌學運籌學-線性規劃線性規劃Page 2例例2.1 某工廠在計劃期內要安排某工廠在計劃期內要安排、兩種產品的生產，已兩種產品的生產，已知生產單位產品所需的設備臺時及知生產單位產品所需的設備臺時及A、B兩種原材料的消耗、兩種原材料的消耗、資源的限制，如下表：資源的限制，如下表：問題：工廠應分別生產多少單位問題：工廠應分別生產多少單位、產品才能使工廠獲利產品才能使工廠獲利最多？最多？Page 3解：設生產產品解：設生產產品I和產品和產品 的產量分別為的產量分別為x1和和x2 。 則有如下模型：則有如下模型： Page 4例例2.2 某企業計劃生產甲、乙兩種產品。這些產品分某企業計劃生

2、產甲、乙兩種產品。這些產品分別要在別要在A、B、C、D、四種不同的設備上加工。按工、四種不同的設備上加工。按工藝資料規定，單件產品在不同設備上加工所需要的臺藝資料規定，單件產品在不同設備上加工所需要的臺時如下表所示，企業決策者應如何安排生產計劃，使時如下表所示，企業決策者應如何安排生產計劃，使企業總的利潤最大？企業總的利潤最大？ 設設 備備產產 品品 A B C D利潤（元）利潤（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 臺臺 時時 12 8 16 12Page 5解：設解：設x1、x2分別為甲、乙兩種產品的產量，則數學模型為：分別為甲、乙兩種產品的產量，則數學模型

3、為：Page 6例例2.3 假定一個成年人每天需要從食物中獲取假定一個成年人每天需要從食物中獲取3000卡熱量，卡熱量，55克蛋白質和克蛋白質和800毫克鈣。如果市場上只有四種食品可供選擇，它們每千克所含熱量和營毫克鈣。如果市場上只有四種食品可供選擇，它們每千克所含熱量和營養成分以及市場價格如下表所示。養成分以及市場價格如下表所示。問如何選擇才能滿足營養的前提下使購買食品的費用最小？問如何選擇才能滿足營養的前提下使購買食品的費用最小？序號序號食品名稱食品名稱熱量（卡）熱量（卡）蛋白質（克）蛋白質（克）鈣（毫克）鈣（毫克）價格（元）價格（元）1豬肉豬肉100050400102雞蛋雞蛋800602

4、0063大米大米9002030034白菜白菜200105002請同學們自己列出模型？請同學們自己列出模型？Page 7Page 8Page 900 )( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡寫為：簡寫為：Page 10 Page 11) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中：Page 12 mnmnaaaaA1111 0 )

5、( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB1Page 135. 線性規劃問題的標準形式線性規劃問題的標準形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點：特點：(1) 目標函數求最大值（有時求最小值）目標函數求最大值（有時求最小值）(2) 約束條件都為等式方程，且右端常數項約束條件都為等式方程，且右端常數項bi都大于或等于零都大于或等于零(3) 決策變量決策變量xj為非負。為非負。Page 14 目標函數的轉換目標函數的轉換 如果是求極小值即如果是求極小值即 ，則可將目標函數乘以，則可將目標

6、函數乘以(-1)(-1)，可化，可化為求極大值問題。為求極大值問題。 jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即 若存在取值無約束的變量若存在取值無約束的變量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx 變量的變換變量的變換Page 15 約束方程的轉換：由不等式轉換為等式。約束方程的轉換：由不等式轉換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量 變量變量 的變換的變換 可令可令 ，顯然，顯然0 jxjjxx 0 jxPag

7、e 16例例2.4 將下列線性規劃問題化為標準形式將下列線性規劃問題化為標準形式 ,0,52324 7 532min321321321321321無無約約束束xxxxxxxxxxxxxxxZ用用 替換替換 ， 且且 解解:（）因為（）因為x3無符號要求無符號要求 ，即，即x3取正值也可取負值，標準取正值也可取負值，標準型中要求變量非負，所以型中要求變量非負，所以33xx 3x0,33 xxPage 17(2) 第一個約束條件是第一個約束條件是“”號，在號，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個約束條件是第二個約束條件是“”號，在號，在“”左端減去

8、剩余變量左端減去剩余變量x5，x50；(4) 第第3個約束方程右端常數項為個約束方程右端常數項為-5，方程兩邊同乘以，方程兩邊同乘以(-1),將右將右端常數項化為正數；端常數項化為正數； (5) 目標函數是最小值，為了化為求最大值，令目標函數是最小值，為了化為求最大值，令z=-z,得到得到max z=-z，即當，即當z達到最小值時達到最小值時z達到最大值，反之亦然達到最大值，反之亦然;Page 18 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標準形式如下：標準形式如下：Page

9、 196. 6. 線性規劃問題的解線性規劃問題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規劃問題線性規劃問題求解線性規劃問題，就是從滿足約束條件求解線性規劃問題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個解，使目標函數中找出一個解，使目標函數(1)達到最大值。達到最大值。Page 20 可行解可行解：滿足約束條件、的解為可行解。所有可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。的集合為可行域。 最優解最優解：使目標函數達到最大值的可行解。：使目標函數達到最大值的可行解。Pag

10、e 21線性規劃問題的求解方法線性規劃問題的求解方法一一 般般 有有兩種方法兩種方法圖圖 解解 法法單純形法單純形法兩個變量、直角坐標兩個變量、直角坐標三個變量、立體坐標三個變量、立體坐標適用于任意變量、但必需將適用于任意變量、但必需將一般形式變成標準形式一般形式變成標準形式下面我們分析一下簡單的情況下面我們分析一下簡單的情況 只有兩個決策只有兩個決策變量的線性規劃問題，這時可以通過圖解的方法變量的線性規劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學者窺來求解。圖解法具有簡單、直觀、便于初學者窺探線性規劃基本原理和幾何意義等優點。探線性規劃基本原理和幾何意義等優點。Pag

11、e 22max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例例2.5 用圖解法求解線性規劃問題用圖解法求解線性規劃問題Page 23x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zm

12、in Z此點是唯一最優解，此點是唯一最優解，且最優目標函數值且最優目標函數值 max Z=17.2可行域可行域max Z = 2X1 + X2Page 24max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 藍色線段上的所有點都是最藍色線段上的所有點都是最優解這種情形為有無窮多最優解這種情形為有無窮多最優解，但是最優目標函數值優解，但是最優目標函數值m

13、ax Z=34.2是唯一的。是唯一的。可行域可行域Page 25min Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此點是唯一最優解此點是唯一最優解Page 26 006346321212121xxxxxxxx、246x1x2246無界解無界解( (無最優解無最優解) )max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min

14、 Zx1x2O10203040102030405050無可行解無可行解(即無最優解即無最優解)0,050305.140221212121 xxxxxxxxmax Z=3x1+4x2例例1.7Page 28學習要點：學習要點：1. 通過圖解法了解線性規劃有幾種解的形式。通過圖解法了解線性規劃有幾種解的形式。 (1)唯一最優解唯一最優解：一定對應于可行域的頂點； (2)無窮多最優解：無窮多最優解：多重解； (3)無界解：無界解： 即無最優解的情況，原因：缺少必要的約束條件； (4)無可行解：無可行解：即可行域為空集，原因：出現了相互矛盾的約束條件。Page 29學習要點：學習要點：2. 作圖的關鍵

15、有三點：作圖的關鍵有三點： (1) 可行解區域要畫正確可行解區域要畫正確 (2) 目標函數增加的方向不能畫錯目標函數增加的方向不能畫錯 (3) 目標函數的直線怎樣平行移動目標函數的直線怎樣平行移動Page 30學習要點：學習要點：3.結論結論 (1)當線性規劃問題的可行域非空時，它是有界或當線性規劃問題的可行域非空時，它是有界或無解凸多邊形。無解凸多邊形。 (2)若線性規劃問題存在最優解，它一定在可行域若線性規劃問題存在最優解，它一定在可行域的某個頂點獲得。的某個頂點獲得。 (3)若在兩個頂點同時得到最優解，則它們連線上若在兩個頂點同時得到最優解，則它們連線上的任意一點都是最優解，即有無窮多最

16、優解。的任意一點都是最優解，即有無窮多最優解。Page 311.1.單純形法的基本思路單純形法的基本思路 基本思路：從可行域中某一個頂點開始，判斷此頂點是否從可行域中某一個頂點開始，判斷此頂點是否是最優解，如不是是最優解，如不是, ,則再找另一個使得其目標函數值更優的頂則再找另一個使得其目標函數值更優的頂點，稱之為迭代，再判斷此點是否是最優解。直到找到一個點，稱之為迭代，再判斷此點是否是最優解。直到找到一個頂點為其最優解，就是使得其目標函數值最優的解，或者能頂點為其最優解，就是使得其目標函數值最優的解，或者能判斷出線性規劃問題無最優解為止。判斷出線性規劃問題無最優解為止。Page 321.單純

17、形法的基本概念 基：設A為約束條件的mn階系數矩陣(m04010換換出出行行將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 45例例2.8 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數學模型化為標準形式：解：將數學模型化為標準形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難看出不難看出x4、x5可作為初始基變量，列單純形表計算。

18、可作為初始基變量，列單純形表計算。Page 46cj12100icB基變量基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 47學習要點：學習要點：1. 線性規劃解的概念以及線性規劃解的概念以及3個基本定理個基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟Page 48人工變量法：人工變量法：前面討論了在標準型中系數矩陣有單位矩陣，

19、很容易前面討論了在標準型中系數矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大的變量稱為人工變量，構成的可行基稱為人工基，用大MM法或兩階段法求解，這種用人工變量作橋梁的求解方法稱法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。為人工變量法。Page 49例例2

20、.9 用大用大M法解下列線性規劃法解下列線性規劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先將數學模型化為標準形式解：首先將數學模型化為標準形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系數矩陣中不存在系數矩陣中不存在單位矩陣，無法建單位矩陣，無法建立初始單純形表。立初始單純形表。Page 50故人為添加兩個單位向量，得到人工變量單純形法數學模型：故人為添加兩個單位向量，得到人工變量單純形法數學模型： 7 , 2 , 1, 012210243423max732

21、153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一個很大的抽象的數，不需要給出具體的數值，是一個很大的抽象的數，不需要給出具體的數值，可以理解為它能大于給定的任何一個確定數值；再用前面介可以理解為它能大于給定的任何一個確定數值；再用前面介紹的單純形法求解該模型，計算結果見下表。紹的單純形法求解該模型，計算結果見下表。 Page 51cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx5

22、8-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j Page 52解的判別：解的判別：1）唯一最優解判別：最優表中所有非基變量的檢驗數非零）唯一最優解判別：最優表中所有非基變量的檢驗數非零,則線則線 規劃具有唯一最優解。規劃具有唯一最優解。2）多重最優解判別：最優表中存在非基變量的檢驗數為零）多重最優解判別：最優表中存在非基變量的檢驗數為零,則線則性

23、規劃具有多重最優解（或無窮多最優解）。則線則性規劃具有多重最優解（或無窮多最優解）。3）無界解判別：某個）無界解判別：某個k0且且aik（i=1，2,m）則線性）則線性規劃具有無界解。規劃具有無界解。4）無可行解的判斷：當用大）無可行解的判斷：當用大M單純形法計算得到最優解并單純形法計算得到最優解并且存在且存在Ri0時，則表明原線性規劃無可行解。時，則表明原線性規劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。）退化解的判別：存在某個基變量為零的基本可行解。Page 53單純性法小結單純性法小結:建建立立模模型型個個 數數取取 值值右右 端端 項項等式或等式或不等式不等式極大或極

24、小極大或極小新加變量新加變量系數系數兩兩個個三個三個以上以上xj0 xj無無約束約束xj 0 bi 0bi 0=maxZminZxs xa求求解解圖圖解解法、法、單單純純形形法法單純單純形法形法不不處處理理令令xj = xj - xj xj 0 xj 0令令 xj =- xj不不處處理理約束條約束條件兩端件兩端同乘以同乘以-1加加松松弛弛變變量量xs加加入入人人工工變變量量xa減減去去xs加加入入xa不不處處理理令令z=- ZminZ=max z0-M停止停止A Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika對對任任一一)0( lklkiiaab 計計算算lkx

25、x替替換換基基變變量量用用非非基基變變量量新新單單純純形形表表列列出出下下一一個個ax含有含有量中是否量中是否基變基變 0 j非非基基變變量量的的有有某某個個最最優優解解一一唯唯 無無可可行行解解最優解最優解無窮多無窮多是是否否環環循循否否否否否否是是是是是是循環循環無無界界解解Page 55一般而言，一個經濟、管理問題凡是滿足以下條一般而言，一個經濟、管理問題凡是滿足以下條件時，才能建立線性規劃模型。件時，才能建立線性規劃模型。 要求解問題的目標函數能用數值指標來反映，且要求解問題的目標函數能用數值指標來反映，且為線性函數為線性函數 存在著多種方案存在著多種方案 要求達到的目標是在一定條件下

26、實現的，這些約要求達到的目標是在一定條件下實現的，這些約束可用線性等式或不等式描述束可用線性等式或不等式描述Page 56 人力資源分配問題人力資源分配問題 例例2.10 某晝夜服務的公交線路每天各時間段內所需司機某晝夜服務的公交線路每天各時間段內所需司機和乘務人員人數如下表所示：和乘務人員人數如下表所示：班次班次時間時間所需人員所需人員16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030 設司機和乘務人員分別在各時間段開始時上班，并連續工作設司機和乘務人員分別在各時間段開始時上班，并連續工作8小時

27、，小時，問該公交線路應怎樣安排司機和乘務人員，即能滿足工作需要，又使配問該公交線路應怎樣安排司機和乘務人員，即能滿足工作需要，又使配備司機和乘務人員的人數減少備司機和乘務人員的人數減少?Page 57解：設解：設xi表示第表示第i班次時開始上班的司機和乘務人員人數。班次時開始上班的司機和乘務人員人數。 0,302050607060.min654321655443322161654321xxxxxxxxxxxxxxxxxxtsxxxxxx此問題最優解：此問題最優解：x150， x220， x350， x40， x520， x610，一共需要司機和乘務員，一共需要司機和乘務員150人。人。Page

28、 58 例例2.11某公司面臨一個是外包協作還是自行生產的問題。該公司生某公司面臨一個是外包協作還是自行生產的問題。該公司生產甲、乙、丙三種產品，都需要經過鑄造、機加工和裝配三個車間。甲、產甲、乙、丙三種產品，都需要經過鑄造、機加工和裝配三個車間。甲、乙兩種產品的鑄件可以外包協作，亦可以自行生產，但產品丙必須本廠乙兩種產品的鑄件可以外包協作，亦可以自行生產，但產品丙必須本廠鑄造才能保證質量。數據如表。問：公司為了獲得最大利潤，甲、乙、鑄造才能保證質量。數據如表。問：公司為了獲得最大利潤，甲、乙、丙三種產品各生產多少件？甲、乙兩種產品的鑄造中，由本公司鑄造和丙三種產品各生產多少件？甲、乙兩種產品

29、的鑄造中，由本公司鑄造和由外包協作各應多少件？由外包協作各應多少件？甲乙丙資 源 限 制鑄 造 工 時 (小 時 /件 )51078000機 加 工 工 時 (小 時 /件 )64812000裝 配 工 時 (小 時 /件 )32210000自 產 鑄 件 成 本 (元 /件 )354外 協 鑄 件 成 本 (元 /件 )56-機 加 工 成 本 (元 /件 )213裝 配 成 本 (元 /件 )322產 品 售 價 (元 /件 )2318162. 生產計劃問題生產計劃問題Page 59 解：設解：設 x x1 1, ,x x2 2, ,x x3 3 分別為三道工序都由本公司加工的甲、乙、丙三

30、種分別為三道工序都由本公司加工的甲、乙、丙三種產品的件數，產品的件數，x x4 4, ,x x5 5 分別為由外協鑄造再由本公司加工和裝配的甲、乙兩分別為由外協鑄造再由本公司加工和裝配的甲、乙兩種產品的件數。種產品的件數。 求求 x xi i 的利潤：利潤的利潤：利潤 = = 售價售價 - - 各成本之和各成本之和 產品甲全部自制的利潤產品甲全部自制的利潤 =23-(3+2+3)=15=23-(3+2+3)=15 產品甲鑄造外協，其余自制的利潤產品甲鑄造外協，其余自制的利潤 =23-(5+2+3)=13=23-(5+2+3)=13 產品乙全部自制的利潤產品乙全部自制的利潤 =18-(5+1+2

31、)=10=18-(5+1+2)=10 產品乙鑄造外協，其余自制的利潤產品乙鑄造外協，其余自制的利潤 =18-(6+1+2)=9=18-(6+1+2)=9 產品丙的利潤產品丙的利潤 =16-(4+3+2)=7=16-(4+3+2)=7 可得到可得到 x xi i （i = 1,2,3,4,5i = 1,2,3,4,5） 的利潤分別為的利潤分別為 1515、1010、7 7、1313、9 9 元。元。Page 60通過以上分析通過以上分析, ,可建立如下的數學模型可建立如下的數學模型: :目標函數目標函數： Max 15Max 15x x1 1 + 10 + 10 x x2 2 + 7 + 7x

32、x3 3 + 13 + 13x x4 4 + 9 + 9x x5 5 約束條件約束條件： 5 5x x1 1 + 10 + 10 x x2 2 + 7 + 7x x3 3 8000 8000 6 6x x1 1 + 4 + 4x x2 2 + 8 + 8x x3 3 + 6 + 6x x4 4 + 4 + 4x x5 5 12000 12000 3 3x x1 1 + 2 + 2x x2 2 + 2 + 2x x3 3 + 3 + 3x x4 4 + 2 + 2x x5 5 10000 10000 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 0 0Pa

33、ge 612. 生產計劃問題生產計劃問題例例2.12. 某廠生產某廠生產、三種產品，都分別經三種產品，都分別經A、B兩道工兩道工序加工。設序加工。設A工序可分別在設備工序可分別在設備A1和和A2上完成，有上完成，有B1、B2、B3三種設備可用于完成三種設備可用于完成B工序。已知產品工序。已知產品可在可在A、B任何一種任何一種設備上加工；產品設備上加工；產品可在任何規格的可在任何規格的A設備上加工，但完成設備上加工，但完成B工序時，只能在工序時，只能在B1設備上加工；產品設備上加工；產品只能在只能在A2與與B2設備上設備上加工。加工單位產品所需工序時間及其他各項數據如下表，試加工。加工單位產品所

34、需工序時間及其他各項數據如下表，試安排最優生產計劃，使該廠獲利最大。安排最優生產計劃，使該廠獲利最大。Page 62設備設備產品產品設備有效設備有效臺時臺時設備加工費設備加工費（單位小時）（單位小時）27910 000321B168124000250B247000783B37114000200原料費（每件）原料費（每件）0.250.350.5售價（每件）售價（每件）1.252.002.8Page 63解：設解：設xijk表示產品表示產品i在工序在工序j的設備的設備k上加工的數量。約束條上加工的數量。約束條件有：件有：）（上加工的數量相等）上加工的數量相等），在工序在工

35、序（產品（產品上加工的數量相等）上加工的數量相等），在工序在工序（產品（產品上加工的數量相等）上加工的數量相等），在工序在工序（產品（產品設備設備設備設備）（設備（設備）（設備（設備設備設備3 , 2 , 1; 2 , 1; 3 , 2 , 10BAIIIBAIIBAI)3B(40007)2B(70001141B4000862A100001297)1A(6000105322312221212211123122121112111123322122221121312212112211111 kjixxxxxxxxxxxxxxxxxxxxxijkPage 64目標是利潤最大化，即利潤的計算公式如下：

36、目標是利潤最大化，即利潤的計算公式如下： 5131)()(ii該該設設備備實實際際使使用用臺臺時時每每臺臺時時的的設設備備費費用用該該產產品品件件數數銷銷售售單單價價原原料料單單價價利利潤潤帶入數據整理得到：帶入數據整理得到：12332212222112131221221111211135. 023. 1448. 05 . 0375. 0915. 136. 115. 1775. 075. 0maxxxxxxxxxxx Page 65因此該規劃問題的模型為：因此該規劃問題的模型為： ）（3,2,1;2,1;3,2,104000770001144000861000012976000105.35.0

37、23.1448.05.0375.0915.136.115.1775.075.0max322312221212211123122121112111123322122221121312212112211111123322122221121312212211112111kjixxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxijkPage 66 例例2.132.13某工廠要做某工廠要做100100套鋼架，每套用長為套鋼架，每套用長為2.9 m,2.1 m,1.5 m2.9 m,2.1 m,1.5 m的圓的圓鋼各一根。已知原料每根長鋼各一根。已知原料每根長7.4 m7.4 m，問：應如

38、何下料，可使所用原料最省？，問：應如何下料，可使所用原料最省？ 解：解： 共可設計下列共可設計下列5 5 種下料方案，見下表種下料方案，見下表 設 x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數。這樣我們建立如下的數學模型。 目標函數： 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 03. 套裁下料問題套裁下料問題Page 67 設 x1,x2,x3,x4,x5 分別為上面 5 種方案下料的

39、原材料根數。這樣我們建立如下的數學模型。 目標函數： 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 03. 套裁下料問題套裁下料問題Page 68用用“管理運籌學管理運籌學”軟件計算得出最優下料方案：按方案軟件計算得出最優下料方案：按方案1下料下料30根；按方案根；按方案2下下料料10根；按方案根；按方案4下料下料50根。根。 即即 x1=30; x2=10； x3=0； x4=50； x5=0； 只需只需90根

40、原材料就可制造出根原材料就可制造出100套鋼架。套鋼架。注意：在建立此類型數學模型時，約束條件用大于等于號比用等于號要好。因注意：在建立此類型數學模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規格的圓鋼，但它可能是最為有時在套用一些下料方案時可能會多出一根某種規格的圓鋼，但它可能是最優方案。如果用等于號，這一方案就不是可行解了。優方案。如果用等于號，這一方案就不是可行解了。Page 69 例例2.142.14某工廠要用三種原料某工廠要用三種原料1 1、2 2、3 3混合調配出三種不同規格的產品混合調配出三種不同規格的產品甲、乙、丙，數據如右表。問：該

41、廠應如何安排生產，使利潤收入為最大？甲、乙、丙，數據如右表。問：該廠應如何安排生產，使利潤收入為最大？產品名稱規格要求單價（元/kg）甲原材料1不少于50%，原材料2不超過25%50乙原材料1不少于25%，原材料2不超過50%35丙不限25原材料名稱每天最多供應量單價（元/kg）110065210025360354. 配料問題配料問題Page 70 解：設 xij 表示第 i 種（甲、乙、丙）產品中原料 j 的含量。這樣我們建立數學模型時，要考慮： 對于甲： x11，x12，x13； 對于乙： x21，x22，x23； 對于丙： x31，x32，x33； 對于原料1： x11，x21，x31；

42、 對于原料2： x12，x22，x32； 對于原料3： x13，x23，x33； 目標函數： 利潤最大，利潤 = 收入 - 原料支出 約束條件： 規格要求 4 個； 供應量限制 3 個。Page 71利潤利潤=總收入總收入-總成本總成本=甲乙丙三種產品的銷售單價甲乙丙三種產品的銷售單價*產品數量產品數量-甲乙丙使甲乙丙使用的原料單價用的原料單價*原料數量，故有原料數量，故有目標函數Max 50Max 50（x x1111+ +x x1212+ +x x1313）+35+35（x x2121+ +x x2222+ +x x2323）+25+25（x x3131+ +x x3232+ +x x33

43、33）-65-65（x x1111+ +x x2121+ +x x3131）- -2525（x x1212+ +x x2222+ +x x3232）-35-35（x x1313+ +x x2323+ +x x3333）= -15= -15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 約束條件： 從第從第1個表中有：個表中有： x x11110.5(0.5(x x1111+ +x x1212+ +x x1313) ) x x12120.25(0.25(x x111

44、1+ +x x1212+ +x x1313) ) x x21210.25(0.25(x x2121+ +x x2222+ +x x2323) ) x x22220.5(0.5(x x2121+ +x x2222+ +x x2323) )Page 72 從第從第2個表中，生產甲乙丙的原材料不能超過原個表中，生產甲乙丙的原材料不能超過原材料的供應限額，故有材料的供應限額，故有 ( (x x1111+ +x x2121+ +x x3131)100)100 ( (x x1212+ +x x2222+ +x x3232)100)100 ( (x x1313+ +x x2323+ +x x3333)60)

45、60 通過整理，得到以下模型：通過整理，得到以下模型：Page 73（續）（續）目標函數：目標函數：Max z = -15Max z = -15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 約束條件：約束條件： s.t. 0.5 s.t. 0.5 x x1111-0.5 -0.5 x x12 12 -0.5 -0.5 x x1313 0 0 （原材料（原材料1 1不少于不少于50%50%） -0.25-0.25x x1111+0.75+0.75x x1212 -

46、0.25 -0.25x x1313 0 0 （原材料（原材料2 2不超過不超過25%25%） 0.750.75x x2121-0.25-0.25x x2222 -0.25 -0.25x x2323 0 0 （原材料（原材料1 1不少于不少于25%25%） -0.5 -0.5 x x2121+0.5 +0.5 x x2222 -0.5 -0.5 x x2323 0 0 （原材料（原材料2 2不超過不超過50%50%） x x1111+ + x x2121 + + x x3131 100 ( 100 (供應量限制）供應量限制） x x1212+ + x x2222 + + x x3232 100

47、( 100 (供應量限制）供應量限制） x x1313+ + x x2323 + + x x3333 60 ( 60 (供應量限制）供應量限制） x xijij 0 , i = 1,2,3; j = 1,2,3 0 , i = 1,2,3; j = 1,2,3Page 74 例例2.152.15某部門現有資金某部門現有資金200200萬元，今后五年內考慮給以下的項目投資。已知：萬元，今后五年內考慮給以下的項目投資。已知：項目項目A A：從第一年到第五年每年年初都可投資，當年末能收回本利：從第一年到第五年每年年初都可投資，當年末能收回本利110%110%；項目項目B B：從第一年到第四年每年年初

48、都可投資，次年末能收回本利：從第一年到第四年每年年初都可投資，次年末能收回本利125%125%，但規定每年最，但規定每年最大投資額大投資額不能超過不能超過3030萬元；萬元；項目項目C C：需在第三年年初投資，第五年末能收回本利：需在第三年年初投資，第五年末能收回本利140%140%，但規定最大投資額不能超過，但規定最大投資額不能超過8080萬元；萬元；項目項目D D：需在第二年年初投資，第五年末能收回本利：需在第二年年初投資，第五年末能收回本利155%155%，但規定最大投資額不能超過，但規定最大投資額不能超過100100萬元。萬元。 據測定每萬元每次投資的風險指數如下表：據測定每萬元每次投

49、資的風險指數如下表：問：a a）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b b）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在）應如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利在330330萬元的萬元的基礎上使得其投資總的風險系數為最小？基礎上使得其投資總的風險系數為最小？項目風險指數（次/萬元）A1B3C4D5.55. 投資問題投資問題Page 75 解：解： 1 1）確定決策變量：連續投資問題）確定決策變量：連續投資問題 設 xij ( i = 15，j =

50、 14)表示第 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 x24Page 762 2）約束條件：）約束條件：第一年：第一年：A A當年末可收回投資，故第一年年初應把全部資金投出去，于是當年末可收回投資，故第一年年初應把全部資金投出去，于是 x x1111+ + x x12 12 = 200= 200；第二年：第二年：B B次年末才可收回投資，故第二年年初有資金次年末才可收回投資，故第二年年初有資金1.1 1.1 x x1111，于是

51、，于是 x x21 21 + + x x2222+ + x x2424 = = 1.11.1x x1111；第三年：年初有資金第三年：年初有資金 1.11.1x x2121+ 1.25+ 1.25x x1212，于是，于是 x x31 31 + + x x3232+ + x x3333 = 1.1 = 1.1x x2121+ 1.25+ 1.25x x1212；第四年：年初有資金第四年：年初有資金 1.11.1x x3131+ 1.25+ 1.25x x2222，于是，于是 x x41 41 + + x x4242 = 1.1 = 1.1x x3131+ 1.25+ 1.25x x2222；第

52、五年：年初有資金第五年：年初有資金 1.11.1x x4141+ 1.25+ 1.25x x3232，于是，于是 x x51 51 = 1.1= 1.1x x4141+ 1.25+ 1.25x x3232； B B、C C、D D的投資限制：的投資限制： x xi2 i2 30 ( i =1 30 ( i =1、2 2、3 3、4 )4 )，x x3333 80 80，x x2424 100 100 3 3）目標函數及模型：）目標函數及模型：a) Max z = 1.1Max z = 1.1x x5151+ 1.25+ 1.25x x4242+ 1.4+ 1.4x x33 33 + 1.55+

53、 1.55x x24 24 s.t. s.t. x x1111+ + x x12 12 = 200= 200 x x21 21 + + x x2222+ + x x2424 = 1.1 = 1.1x x1111； x x31 31 + + x x3232+ + x x3333 = 1.1 = 1.1x x2121+ 1.25+ 1.25x x1212； x x41 41 + + x x4242 = 1.1 = 1.1x x3131+ 1.25+ 1.25x x2222； x x51 51 = 1.1= 1.1x x4141+ 1.25+ 1.25x x3232； x xi2 i2 30 ( i

54、 =1 30 ( i =1、2 2、3 3、4 )4 )，x x3333 80 80，x x2424 100 100 x xijij 0 ( i = 1 0 ( i = 1、2 2、3 3、4 4、5 5；j = 1j = 1、2 2、3 3、4 4） Page 77一、靈敏度分析的含義與內容一、靈敏度分析的含義與內容1.1.靈敏度分析的含義靈敏度分析的含義 靈敏度分析：靈敏度分析：建立數學模型和求得最優解后，研究線性規劃的一個或多個建立數學模型和求得最優解后，研究線性規劃的一個或多個參數（系數）參數（系數）ci、aij、bi變化時，對最優解產生的影響。變化時，對最優解產生的影響。2.2.靈敏

55、度分析的作用（意義）靈敏度分析的作用（意義） 1 1）因為線性規劃中的）因為線性規劃中的cici、aijaij、bibi這些系數都是估計值和預測值，不這些系數都是估計值和預測值，不一定非常準確；一定非常準確； 2 2）即使這些系數值在某一時刻是精確值，它們也會隨著市場條件的）即使這些系數值在某一時刻是精確值，它們也會隨著市場條件的變化而變化，不會一成不變的。變化而變化，不會一成不變的。 那么如果這些系數變了，線性規劃已經求出的最優解會不會變化那么如果這些系數變了，線性規劃已經求出的最優解會不會變化呢？我們需要不要重新求解呢？有了靈敏度分析，我們就不必為了應付呢？我們需要不要重新求解呢？有了靈敏

56、度分析，我們就不必為了應付這些變化而不停地建立新的模型和求其新的最優解了；也不會由于系數這些變化而不停地建立新的模型和求其新的最優解了；也不會由于系數的估計和預測的精確性而對所求得的最優解存有不必要的懷疑。的估計和預測的精確性而對所求得的最優解存有不必要的懷疑。3.3.靈敏度分析的內容靈敏度分析的內容 Page 78x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400圖2-1例例2.1.目標函數： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (

57、D) x2 0 (E)得到最優解： x1 = 50， x2 = 250 最優目標值 z = 27500二、目標函數中的系數二、目標函數中的系數 ci 的靈敏度分析的靈敏度分析Page 79x1x2z=20000=50 x1+100 x2圖2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADEPage 80二、目標函數中的系數二、目標函數中的系數 ci ci 的靈敏度分析的靈敏度分析 考慮例考慮例2.12.1的情況，的情況， c ci i 的變化只影響目標函數等值線的斜率，的變化只影響目標函數等值線的斜率，目標函數目標函數

58、 z = 50 xz = 50 x1 1 + 100 x+ 100 x2 2 在在 z = xz = x2 2 (x(x2 2 = z = z 斜率為斜率為0 0 ) ) 到到 z = xz = x1 1 + x+ x2 2 (x(x2 2 = -x= -x1 1 + z + z 斜斜率為率為 -1-1 ) )之間時，原最優解之間時，原最優解 x x1 1 = 50= 50，x x2 2 = 100 = 100 仍是最優解。仍是最優解。一般情況：一般情況： z = cz = c1 1 x x1 1 + c+ c2 2 x x2 2 寫成斜截式寫成斜截式 x x2 2 = - (c = - (c1 1 / c/ c2 2 ) x ) x1 1 + z / c+ z / c2 2 目標函數等值線的斜率為目標函數等值線的斜率為 - (c- (c1 1 / c/ c2 2 ) ) ， 當當 -1 -1 - (c- (c1 1 / c/ c2 2 ) ) 0 0 （* *）