(MBA課程)管理運籌學第四章線性規(guī)劃在工商管理中的應(yīng)用課件

1、第四章、線性規(guī)劃在工商管理中的應(yīng)用 通過線性規(guī)劃的圖解法，我們對線性規(guī)劃的求解及靈敏度分析的基本概念、基本原理已有所了解，又通過線性規(guī)劃問題的計算機求解的學習，我們掌握了用計算機軟件這一有用工具去求解線性規(guī)劃問題及其靈敏度分析。在這一章我們來研究線性規(guī)劃在工商管理中的應(yīng)用，解決工商管理中的實際問題。1第四章、線性規(guī)劃在工商管理中的應(yīng)用 通過線性規(guī)劃的4.1、人力資源分配的問題4.2、生產(chǎn)計劃的問題4.3、套裁下料問題4.4、配料問題4.5、投資問題主要內(nèi)容24.1、人力資源分配的問題主要內(nèi)容2 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所 需司機和乘務(wù)人員數(shù)如下： 設(shè)司機和乘務(wù)人員分別在各時間段一開始

2、時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?班次時間所需人數(shù)16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030例14.1、人力資源分配的問題3 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所 解：設(shè)xi表示第i班次時開始上班的司機和乘務(wù)人員數(shù)，可以知道在第i班工作的人數(shù)應(yīng)包括第 i-1班次時開始上班的人員數(shù)和第i班次時開始上班的人員數(shù)，例如有x1+x270。又要求這六個班次時開始上班的所有人員最少，即要求x1+x2+x3+x4+x5+

3、x6最小，這樣我們建立如下的數(shù)學模型。 目標函數(shù)： min x1+x2+x3+x4+x5+x6 約束條件： x1+x660， x1+x270， x2+x360， x3+x450， x4+x520， x5+x630， x1, x2, x3, x4, x5, x604解：設(shè)xi表示第i班次時開始上班的司機和乘務(wù)人員數(shù)，可以知道用“管理運籌學”軟件可以求得此問題的解： x1=50， x2=20，x3=50， x4=0， x5=20， x6=10，24小時內(nèi)一共需要司機和乘務(wù)人員150人。此問題的解不唯一，用LINDO軟件計算得到：X1=60,X2=10, X3=50, X4=0, X5=30, X6

4、=0目標函數(shù)值=1505用“管理運籌學”軟件可以求得此問題的解： x1=50 福安商場是個中型的百貨商場，它對售貨 人員的需求經(jīng)過統(tǒng)計分析如下所示：星期一：15人；星期二：24人；星期三：25人；星期四：19人；星期五：31人；星期六：28人；星期日：28人。 為了保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應(yīng)該如何安排售貨人員的作息，既滿足了工作需要，又使配備的售貨人員的人數(shù)最少? 解：設(shè)x1為星期一開始休息的人數(shù)，x2為星期二開始休息的人數(shù)，x7為星期日開始休息的人數(shù)。目標是要求售貨人員的總數(shù)最少。因為每個售貨員都工作五天，休息兩天，所以只要計算出連續(xù)

5、休息兩天的售貨員人數(shù)，也就計算出了售貨員的總數(shù)。把連續(xù)休息兩天的售貨員按照開始休息的時間分成7類，各類的人數(shù)分別為X1，X2，X7，即有目標函數(shù): min X1+X2+X3+X4+X5+X6+X7例26 福安商場是個中型的百貨商場，它對售貨 模型： 再按照每天所需售貨員的人數(shù)寫出約束條件，例如星期日需要28人，我們知道商場中的全體售貨員中除了星期六開始休息和星期日開始休息的人外都應(yīng)該上班，即有x1+x2+x3+x4+x528，喂！請問數(shù)學模型？7模型： 再按照每天所需售貨員的人數(shù)寫出約束條件，例如星上機求解得：x1=12,x2=0,x3=11,x4=5,x5=0,x6=8,x7=0,目標函數(shù)最

6、小值=36. 也就是說配備36個售貨員，并安排12人休息星期一、二；安排11 人休息星期三、四；安排5人休息星期四、五；安排8人休息星期六、日。這 樣的安排既滿足了工作需要，又使配備的售貨員最少。軟件對此問題的解如下： 目標函數(shù)最優(yōu)值為：36 變量 最優(yōu)解 相差值 x1 12 0 x2 0 0.333 x3 11 0 x4 5 0 x5 0 0 x6 8 0 x7 0 08上機求解得：x1=12,x2=0,x3=11,x4=5,x5約束 松馳/剩余變量 對偶價格1 0 -0.3332 9 03 0 -0.3334 0 -0.3335 1 06 0 -0.3337 0 0由于所有約束條件的對偶價

7、格都小于或等于0，故增加約束條件的常數(shù)項都不會使目標值變小。即增加售貨員是不利的。但對于約束1、3、4、6來講，減少一售貨員會使目標函數(shù)值變小，是有利的。9約束 松馳/剩余變量 對偶價格目標函數(shù)系數(shù)范圍：變量 下限 當前值 上限X1 0 1 1.5X2 0.667 1 無上限X3 0 1 1.5X4 1 1 1X5 1 1 無上限X6 0 1 1X7 1 1 1.333安排星期二開始休息和星期五開始休息的人員可以無限制，此時最優(yōu)解仍然不變。10目標函數(shù)系數(shù)范圍：10常數(shù)項范圍：約束 下限 當前值 上限1 19 28 282 無下限 15 243 15 24 424 10 25 41.55 無下

8、限 19 206 16 31 38.57 28 28 3611常數(shù)項范圍：11法二：設(shè)x1為星期一開始上班的人數(shù)，x2為星期二開始上班的人數(shù)，x7為星期日開始上班的人數(shù)。目標是要求售貨人員的總數(shù)最少。(P40-2a.ltx) 目標函數(shù): min X1+X2+X3+X4+X5+X6+X7 約束條件：星期日 X3+X4+X5+X6+X7 28星期一 X1+X4+X5+X6+X7 15星期二 X1+X2+X5+X6+X7 24星期三 X1+X2+X3+X6+X7 25星期四 X1+X2+X3+X4+X7 19星期五 X1+X2+X3+X4+X531星期六 X2+X3+X4+X5+X628解: 函數(shù)值

9、=36,X1=3,x2=5,x3=12,X4=0,x5=11,x6=0X7=5,則周1休息人數(shù)為周3上班的+周2上班的=12+5=17,與法一是一樣的周1開始休息仍為17-5=12人12法二：設(shè)x1為星期一開始上班的人數(shù)，x2為星期二開始上班的人 明興公司面臨一個是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。有關(guān)情況見表43；公司中可利用的總工時為：鑄造8000小時，機加工12000小時和裝配10000小時。公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生

10、產(chǎn)多少件?甲、乙兩種產(chǎn)品的鑄造應(yīng)多少由本公司鑄造?應(yīng)多少由外包協(xié)作？例34.2、生產(chǎn)計劃的問題13 明興公司面臨一個是外包協(xié)作表4-3解：設(shè)x1、x2、x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，設(shè)x4、x5分別為由外協(xié)鑄造再由本公司機加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 計算每件產(chǎn)品的利潤分別如下： 工時與成本 甲乙丙每件鑄造工時(小時)5107每件機加工工時(小時) 648 每件裝配工時（小時)322 自產(chǎn)鑄件每件成本(元) 354外協(xié)鑄件每件成本(元) 56 機加工每件成本(元) 213 裝配每件成本(元) 322每件產(chǎn)品售價(元) 23181614表4-3解：設(shè)x1、x2

11、、x3分別為三道工序都由本公司加工的產(chǎn)品甲全部自制的利潤=23-(3+2+3)=15(元)產(chǎn)品甲鑄造外協(xié)，其余自制的利潤=23-(5+2+3)=13(元)產(chǎn)品乙全部自制的利潤=18-(5+1+2)=10(元)產(chǎn)品乙鑄造外協(xié)，其余自制的利潤=18-(6+1+2)=9(元)產(chǎn)品丙的利潤 =16-(4+3+2)=7(元) 工時與成本 甲乙丙每件鑄造工時(小時)5107每件機加工工時(小時) 648 每件裝配工時（小時)322 自產(chǎn)鑄件每件成本(元) 354外協(xié)鑄件每件成本(元) 56 機加工每件成本(元) 213 裝配每件成本(元) 322每件產(chǎn)品售價(元) 23181615產(chǎn)品甲全部自制的利潤=2

12、3-(3+2+3)=15(元) 工時建立數(shù)學模型如下： 目標函數(shù)： max 15X1+10X2+7X3+13X4+9X5 約束條件： 5X1+10X2+7X38000(這里沒包括外協(xié)鑄造時間)， 6X1+4X2+8X3+6X4+4X512000(機加工)， 3X1+2X2+2X3+3X4+2X510000(裝配)， X1，X2，X3，X4，X50用“管理運籌學”軟件進行計算，計算機計算結(jié)果顯示在圖4-1中。詳見上機計算。 工時與成本 甲乙丙每件鑄造工時(小時)5107每件機加工工時(小時) 648 每件裝配工時（小時)32216建立數(shù)學模型如下： 工時與成本 甲乙丙每件目標函數(shù)最優(yōu)值為：294

13、00 變量 最優(yōu)解 相差值 x1 1600 0 x2 0 2 x3 0 13.1 x4 0 0.5 x5 600 0 結(jié)果分析：最大的利潤為29400元，其最優(yōu)的生產(chǎn)計劃為全部由自己生產(chǎn)的甲產(chǎn)品1600件，鑄造外協(xié)、其余自制生產(chǎn)乙產(chǎn)品600件，而丙產(chǎn)品不生產(chǎn)。從相差值一欄中可知，如果全部由自己生產(chǎn)的乙產(chǎn)品的利潤再增加2元達到每件12元利潤，那么全部自制的乙產(chǎn)品才有可能上馬生產(chǎn)，否則乙產(chǎn)品還是鑄造外協(xié)、其余自制的利潤更大。同樣丙產(chǎn)品的利潤要再增加13.1元達到每件利潤20.1元，丙產(chǎn)品才有可能上馬生產(chǎn)；鑄造外協(xié)、其余自制的甲產(chǎn)品利潤再增加0.5元達到13.5元，才有可能上馬生產(chǎn)。17目標函數(shù)最優(yōu)

14、值為：29400 結(jié)果分析：約束 松馳/剩余變量 對偶價格1 0 0.32 0 2.253 4000 0 從對偶價格欄可知鑄造每工時的對偶價格為0.3元，機加工每工時的對偶價格為2.25元，裝配每工時的對偶價格為零元。這樣如果有人以低于鑄造和機加工的對偶價格來提供鑄造及機加工的工時則可以購入來獲取差價（例如外協(xié)鑄造工時價格低于0.3元，則外協(xié)鑄造合算)。同樣如果有人要購買該公司的鑄造與機加工的工時，則出價必須扣除成本外，還必須高于其對偶價格，否則就不宜出售。至于裝配每工時的對偶價格為零，這是由于在此生產(chǎn)計劃下還有4000個裝配工時沒有完。注意:從計算中可知,如果把松馳或者剩余變量看作變量時引入

15、模型時，對偶價格實際上是松馳或者剩余變量 的相差值的絕對值。 18約束 松馳/剩余變量 對偶價格 對偶價格不是市場價格，在作市場決策時，某種資源市場價格低于對偶價格時，可適量買進這種資源，組織和增加生產(chǎn)。相反當市場價格高于對偶價格時，可以賣出資源而不安排生產(chǎn)或提高產(chǎn)品的價格。注意??！19 對偶價格不是市場價格，在作市場決策時，某目標函數(shù)系數(shù)范圍：變量 下限 當前值 上限X1 14 15 無上限X2 無下限 10 12X3 無下限 7 20.1X4 無下限 13 13.5X5 8.667 9 10 從目標函數(shù)決策變量系數(shù)一欄中知道，當全部自己生產(chǎn)的每件甲產(chǎn)品的利潤在14到+內(nèi)變化時，其最優(yōu)解不變

16、；全部自己生產(chǎn)的每件乙產(chǎn)品的利潤只要不超過12元，則其最優(yōu)解不變；當每件丙產(chǎn)品的利潤不超過20.1元時，則其最優(yōu)解不變；當鑄造外協(xié)其余自制的每件甲產(chǎn)品的利潤不超過13.5元時，其最優(yōu)解不變；當鑄造外協(xié)，其余自制的每件乙產(chǎn)品的利潤在8.667到10元內(nèi)變化時，則其最優(yōu)解不變。在這里當某產(chǎn)品利潤變化時都假設(shè)其余產(chǎn)品的利潤是不變的。20目標函數(shù)系數(shù)范圍：變量 下限 常數(shù)項范圍約束 下限 當前值 上限1 0 8000 100002 9600 12000 200003 6000 10000 無上限從約束條件右邊常數(shù)變化范圍欄可知，當鑄造工時在0到10000小時間變化時其對偶價格都為0.3元；當機加工工時

17、在9600到20000小時內(nèi)變化時，其對偶價格都為2.25元；當裝配工時在6000到+內(nèi)變化時，其對偶價格都為零。 也就是說當常數(shù)項超出上面的范圍時其對偶價格可能已變，這時某種資源的市場價格與對偶價格的關(guān)系隨之發(fā)生變化。21常數(shù)項范圍約束 下限 當前值 永久機械廠生產(chǎn)、三種產(chǎn)品。每種產(chǎn)品均要經(jīng)過A、B兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成A工序，它們以A1、A2表示；有三種規(guī)格的設(shè)備能完成B工序，它們以B1，B2，B3表示。產(chǎn)品可在A、B的任何規(guī)格的設(shè)備上加工。產(chǎn)品可在任何一種規(guī)格的A設(shè)備上加工，但完成B工序時，只能在B1設(shè)備上加工。產(chǎn)品只能在A2與B2設(shè)備上加工。已知在各種設(shè)備上加工的單

18、件工時、原料單價、產(chǎn)品銷售單價、各種設(shè)備的有效臺時以及滿負荷操作時的設(shè)備費用如表4 4示，要求制定最優(yōu)的產(chǎn)品加工方案，使該廠利潤最大。例422 永久機械廠生產(chǎn)、表4-4設(shè) 備 產(chǎn)品單件工時設(shè)備的有效臺時滿負荷時的設(shè)備費用2791210000321B1684000250B24117000783B374000200原料單價(元件)0.250.350.5銷售單價(元件)1.2522.823表4-4設(shè) 備 產(chǎn)品單件工時設(shè)備的有效臺時滿負荷時的設(shè)解：設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(A工序用1表示，B工序用2表示)的第k種設(shè)備上加工的數(shù)量。如x123表示第種產(chǎn)品在B道工序

19、上用B3設(shè)備加工的數(shù)量。則約束 5x111+10 x2116000， (設(shè)備A1) 7x112+9x212+12x31210000， (設(shè)備A2) 6x121+8x2214000， (設(shè)備B1)， 4x122+11x3227000 (設(shè)備B2) , 7x1234000 (設(shè)備B3)設(shè) 備 產(chǎn)品單件工時設(shè)備的有效臺時滿負荷時的設(shè)備費用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X123400020024解：設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(

20、A工序用1表示，設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(A工序用1表示，B工序用2表示)的第k種設(shè)備上加工的數(shù)量。恒等約束： 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ù)量相等) 設(shè) 備 產(chǎn)品單件工時設(shè)備的有效臺時滿負荷時的設(shè)備費用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B3

21、7,X1234000200應(yīng)該是0才合理25設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(A工序用1表示，B工設(shè) 備 產(chǎn)品單件工時設(shè)備的有效臺時滿負荷時的設(shè)備費用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X1234000200原料單價(元件)0.250.350.5銷售單價(元件)1.2522.8應(yīng)該是1.25(X121+X122+X123)-0.25(X111+X112)才合理。26設(shè) 備 產(chǎn)品單件工時設(shè)備的有效臺時滿負荷時的設(shè)備費用設(shè) 備 產(chǎn)品單

22、件工時設(shè)備的有效臺時滿負荷時的設(shè)備費用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X123400020027設(shè) 備 產(chǎn)品單件工時設(shè)備的有效臺時滿負荷時的設(shè)備費用 5x111+10 x2116000， (設(shè)備A1) 7x112+9x212+12x31210000， (設(shè)備A2) 6x121+8x2214000， (設(shè)備B1)， 4x122+11x3227000 (設(shè)備B2) , 7x1234000 (設(shè)備B3)X111+X112-X121-X12

23、2 X123=0，(產(chǎn)品在A、B工序上加工的數(shù)量相等) X211+X212-X221=0, (產(chǎn)品在A、B工序上加工的數(shù)量相等) X312-X322=0, (產(chǎn)品在A、B工序上加工的數(shù)量相等) 28 5x111+10 x2116000， (設(shè)備A1)模型 將模型輸入計算機x111=1200，x112=230.0492，X211=0， X212 =500，X312 =324.138， X121 =0，X221 =500，X122 =858.6206，X322 =324.138，X123 =571.4286, 最優(yōu)值為1146.6。29模型 將模型輸入計算機x111=1200，x112=23 由于

24、本題要求的決策變量的單位是件，所以答案應(yīng)該是整數(shù)。本題與例1、例2、例3實質(zhì)上都是整數(shù)規(guī)劃的問題，但是這類問題可以作為線性規(guī)劃的問題來解，有些如例1，例2，例3的答案都是整數(shù)，而有些如本題答案是非整數(shù)，可以將答案舍入成整數(shù)也可能得到滿意的結(jié)果。如本題如果用軟件的整數(shù)規(guī)劃的來解，得到的答案為x111=1200，x112=230，X211=0，X212 =500，X312 =324， X121 =0，X221 =500，X122 =859，X322 =324，X123 =571.最優(yōu)值為1146.3622。其最優(yōu)解正好與四舍五入線性規(guī)劃結(jié)果一樣的。兩種方法的最優(yōu)值也相差無幾，只差0.3元。30 由

25、于本題要求的決策變量的單位是件，所以答案應(yīng) 本問題最優(yōu)的方案為生產(chǎn)產(chǎn)品1430件（X111+X112=1200+230=X121+X122+X123=0+859+571=1430)，產(chǎn)品第A道工序由A1設(shè)備加工1200件，由A2設(shè)備加工230件。 產(chǎn)品的第B道工序由B2設(shè)備加工859件，由B3設(shè)備加工571件。 生產(chǎn)產(chǎn)品500件，它的第A道工序全部由A2設(shè)備加工，它的第B道工序全部由B1設(shè)備加工。X212=X221=500。 生產(chǎn)產(chǎn)品324件，其第A道工序全部由A2加工，其第B道工序全部由B2設(shè)備加工，X312=X322=324，這樣能使工廠獲得最大利潤1146.3元。生產(chǎn)數(shù)量A1X111=1

26、200X211=0A2X112=230X212=500X312=324B1X121=0X221=500B2X122=859X322=324B3X123= 57131 本問題最優(yōu)的方案為生產(chǎn)產(chǎn)品1430件（X111如果分別按實際產(chǎn)品和原材料來計算則有：Max z=-0.5x111-0.6352x112-0.85x211-0.6389x212-0.8852x312+0.875x121+0.8024x122+0.9x123+1.5x221+1.5691x3225x111+10 x2116000， (設(shè)備A1) 7x112+9x212+12x31210000， (設(shè)備A2) 6x121+8x22140

27、00， (設(shè)備B1)， 4x122+11x3227000 (設(shè)備B2) , 7x1234000 (設(shè)備B3)X111+X112-X121-X122 X1230，(產(chǎn)品在A工序加工的數(shù)量大于B加工的數(shù)量) X211+X212-X2210, (產(chǎn)品在A工序上加工數(shù)量天于B的數(shù)量) X312-X3220, (產(chǎn)品在A工序上加工的數(shù)量大于B) 32如果分別按實際產(chǎn)品和原材料來計算則有：Max z=-0.5x結(jié)果如下：本問題最優(yōu)的方案為生產(chǎn)產(chǎn)品1200件（X111+X112=1200+0=X121+X122+X123=0+628.572+571.428=1200)，產(chǎn)品第A道工序由A1設(shè)備加工1200件

28、，由A2設(shè)備加工0件。 產(chǎn)品的第B道工序由B2設(shè)備加工628.572件，由B3設(shè)備加工571.428件。 生產(chǎn)產(chǎn)品500件，它的第A道工序全部由A2設(shè)備加工，它的第B道工序全部由B1設(shè)備加工。X212=X221=500。 生產(chǎn)產(chǎn)品324件，其第A道工序全部由A2加工，其第B道工序全部由B2設(shè)備加工，X312=X322=407.79，這樣能使工廠獲得最大利潤1128.091元。比上方法要少。此法合理。33結(jié)果如下：本問題最優(yōu)的方案為生產(chǎn)產(chǎn)品1200件（X111+ 某工廠要做100套鋼架，每套用長為2.9m，2.1 m 和1.5 m的圓鋼各一根。已知原料每根長7.4m，問應(yīng)如何下料，可使所用原料最

29、省。 解：最簡單的做法是，在每根原材料上截取2.9m、2.1m和1.5m的圓鋼各一根組成一套，每根原材料省下料頭0.9m。為了做100套鋼架，需要原材料100根，共有90m的料頭。若改用套裁可以節(jié)約不少原材料，為了找到一個省料的套裁方案，先設(shè)計出較好的幾個下料方案，所謂較好，第一要求每個方案下料后的料頭較短，第二要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，并且不同方案有著不同的各種所需圓鋼的比。這樣套裁才能滿足對各種不同規(guī)格圓鋼的需要并達到省料的目的。為此設(shè)計出以下5種下料方案以供套裁用。見表45。例54.3、套裁下料問題34 某工廠要做100套鋼架，每套用長為2.表45。下料數(shù) 方案（根）長

30、度2.9120102.1002211.531203合計7.47.37.27.16.6料頭00.10.20.30.8設(shè)y1,y2,y3三種圓鋼2.9m，2.1 m,1.5 m切割根數(shù),則應(yīng)滿足2.9y1+2.1y2+1.5y37.4，其切割方案很多，如果要求料頭不超過最短的1.5，則可能是次優(yōu)方案。35表45。下料數(shù) 方案2.9120102. 解：為了用最少的原材料得到100套鋼架，需要混合使用上述五種下料方案，設(shè)按I，V方案下料的原材料根數(shù)分別為x1，x2，x3，x4，x5，可列出下面的數(shù)學模型。 目標函數(shù)： min X1+X2+X3+X4+ X5 約束條件： X1+2X2+ X4 100，

31、2X3+ 2X4+X5 100， 3X1+X2+2X3+3X5 100， X1， X2， X3， X4， X5 0 上機計算得到如下最優(yōu)下料方案：按方案下料30根；按方案下料10根，按方案下料50根(即x1=30，x2=10，x3=0，x4=50，x5=0)，只需90根原材料(即目標函數(shù)最小值為90)即可制造100套鋼架。36 解：為了用最少的原材料得到100套鋼架，需要混合使用上述思考如果只取方案前四個或前三個或再增加其它方案，結(jié)果如何？37思考如果只取方案前四個或前三個或再增加其它方案，結(jié)果如何？3其它方案列表（不是所有）(P46-5b)12345678910111213142.91201

32、01100000002.1002211032100001.531203120124321合計7.47.37.27.16.66.55.96.35.75.164.531.5料頭00.10.20.30.80.91.51.11.72.31.44.44.45.9 min X1+X2+X3+X4+ X5+X6+X7+X8+X9+X10+X11+X12+X13+X14 約束條件： X1+2X2+ X4 +X6+X7100， 2X3+ 2X4+X5 +X6+3X8+2X9+X10100， 3X1+X2+2X3+3X5 +X6+2X7+X9+2X10+4X11+3X12+2X13+X1410038其它方案列表（

33、不是所有）(P46-5b)1234567891模型 將模型輸入計算機解為：目標函數(shù)值=90, x1=0,x2=40,x3=30,x4=20,其它x為0。從這里看出模型有多個解。料頭多的方案一般為0。39模型 將模型輸入計算機解為：目標函數(shù)值=90, x1= 注意！ 在建立此數(shù)學模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這個套用方案就不是可行解了。 約束條件用大于等于號時，目標函數(shù)本來求所用原材料最少和求料頭最少是一樣的，但由于在第一個下料方案中料頭為零，無論按第一下料方案下多少根料，料頭都為零，也就是

34、說不管第一下料方案下料是200根還是150都可使目標函數(shù)值達到最小，這顯然不合理。所以目標函數(shù)就一定要求原材料最少。如果所有方案料頭都不為零，則可用料頭作為最小值函數(shù)變量。40 注意！ 在建立此數(shù)學模型時，約束條件用大于等于號比思考：如果原材不止一種規(guī)格，如還有10M長的原材，則如何設(shè)計模型？41思考：41 某工廠要用三種原料1，2，3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，已知產(chǎn)品的規(guī)格要求、產(chǎn)品的單價、每天能供應(yīng)的原材料數(shù)量及原材料單價，分別見表4-6和表47。該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大? 產(chǎn)品名稱 規(guī)格要求 單價(元千克)甲 原材料1不少于50，原材料2不超過25 50 乙原材

35、料1不少于25， 原材料2不超過50 35丙 不限 25表4-6 現(xiàn)在講第四個問題 ：4.4配料問題例642 某工廠要用三種原料1，2，3混合調(diào)配出三 解：設(shè)xij表示第i種產(chǎn)品中原材料j的含量(分別用 產(chǎn)品1，2，3表示產(chǎn)品甲、乙、丙)。例如x23就表 示乙產(chǎn)品中第3種原材料的含量，目標是使利潤 最大，利潤的計算公式如下： 原材料名稱 每天最多供應(yīng)量 單價（元/千克）1100652100253603543 解：設(shè)xij表示第i種產(chǎn)品中由表4-6得到： X110.5(X11+X12+X13)，(甲中原料1占甲產(chǎn)品數(shù)量不少于50%.) X120.25(X11+X12+X13) X210.25(X

36、21+X22+X23) X220.5(X21+X22+X23)由表4-5得到：X11+X21+X31100X12+X22+X32100X13+X23+X336044由表4-6得到： X110.5(X11+X12+X13)，得問題模型如下(必須整理后上機求解）：45得問題模型如下(必須整理后上機求解）：45模型 將模型輸入計算機解為：x11=100，x12=50,x13=50，其余的xij=0，也就是說每天只生產(chǎn)甲產(chǎn)品200千克，分別需要用1原料100千克，2原料50千克，3原料50千克。其它乙、丙產(chǎn)品不生產(chǎn)。目標函數(shù)值=500元46模型 將模型輸入計算機解為：x11=100，x12=50 VA

37、RIABLE VALUE REDUCED COST X11 100.000000 0.000000 X12 50.000000 0.000000 X13 50.000000 0.000000 X21 0.000000 15.000000 X22 0.000000 0.000000 X31 0.000000 45.000000 X33 0.000000 10.000000 X23 0.000000 0.000000 X32 0.000000 0.000000 從相差值中可看出：只有當X21的系數(shù)從-30增加15元則乙產(chǎn)品才生產(chǎn)，只有當X31和X33的系數(shù)分別從-40增加45元和從-10增加10元

38、則丙產(chǎn)品才生產(chǎn)，47 VARIABLE VALUE 汽油混合問題。 一種汽油的特性可用兩種指標描述，用“辛烷數(shù)”來定量描述其點火性，用“蒸汽壓力”來定量描述其揮發(fā)性。某煉油廠有1，2，3，4種標準汽油，其特性和庫存量列于表48中，將這四種標準汽油混合，可得到標號為1，2的兩種飛機汽油，這兩種飛機汽油的性能指標及產(chǎn)量需求列于表49中。問應(yīng)如何根據(jù)庫存情況適量混合各種標準汽油，既滿足飛機汽油的性能指標，又使2號飛機汽油滿足需求，并使得1號飛機汽油產(chǎn)量最高。例748 汽油混合問題。 一種汽油的特性可用兩種指標描設(shè)Xij為飛機汽油i 中所用標準汽油j的數(shù)量，這樣可知X11+X12+X13+X14為飛機

39、汽油1總產(chǎn)量，總產(chǎn)量越多越好，所以有目標函數(shù)為 max X11+X12+X13+X14 約束條件之一：X21+X22+X23+X24250000飛機汽油 辛烷數(shù) 蒸汽壓力(gcm2) 產(chǎn)量需求(L) 1不小于91不大于9.9610-2越多越好2不小于100不大于9.9610-2不少于250000表4-949設(shè)Xij為飛機汽油i 中所用標準汽油j的數(shù)量，這樣可知X11表4-8:得到有關(guān)庫存量和產(chǎn)量指標的約束條件：X11+X21380000, X12+X22265200, X13+X23408100,X14+X24130100,Xij0. 標準汽油 辛烷數(shù) 蒸汽壓力(scm2) 庫存量(L)110

40、7.57.1110-238000029311.3810-22652003875.6910-2408100410828.4510-213010050表4-8:得到有關(guān)庫存量和產(chǎn)量指標的約束條件： 標準汽油 下面再列出有關(guān)辛烷數(shù)和蒸汽壓力的約束條件: 物理中的“分壓定律”可敘述如下：“設(shè)有一種混合氣體，由n種氣體組成。設(shè)混合氣體的壓力為P，所占總?cè)莘e為V，各組成成分的壓力及其所占容積分別為p1,pn，及v1,vn,，則PV=pj vj”。用此分壓定律可寫出有關(guān)蒸汽壓力的約束條件。飛機汽油1的蒸汽壓力不能大于9.9610-2,，即有:51 下面再列出有關(guān)辛烷數(shù)和蒸汽壓力的約束條件: 5 同樣，可以得

41、到有關(guān)飛機汽油2的蒸汽壓力的約束條件為：2.85x21-1.42x22+4.27x23-18.40 x240.52 同樣，可以得到有關(guān)飛機汽油2的蒸汽壓力的約束條件同樣可以寫有關(guān)辛烷數(shù)的約束條件，對于飛機汽油1有：(107.5x11+93x12+87x13+108x14)/(x11+x12+x13+x14) 91. 經(jīng)整理得： 16.5x11+2x12-4x13+17x140. 對于飛機汽油2有： 7.5x21-7x22-13x23+8x240.綜上所述得到此問題的數(shù)學模型 : 標準汽油 辛烷數(shù) 蒸汽壓力(scm2)1107.57.1110-229311.3810-23875.6910-241

42、0828.4510-253同樣可以寫有關(guān)辛烷數(shù)的約束條件，對于飛機汽油1有： 標準汽油 目標函數(shù)：max X11+X12+X13+X14 約束條件：X21+X22+X23+X24250000, X11+X21380000, X12+X22265200, X13+X23408100, X14+X24130100, 2.85X11-1.42X12+4.27X13-18.49X140. 2.85X21-1.42X22+4.27X23-18.40X240. 16.5X11+2X12-4X13+17X140. 7.5X21-7X22-13X23+8X240. Xij0。數(shù)學模型：54 目標函數(shù)：max

43、X11+X12+X13+X模型 將模型輸入計算機X11=261966.078，X12=265200，x13=315672.219，X 14 =90561.688，X 21 =118033.906，X 22 =0，X 23 =92427.758，X 24 =39538.309， 最優(yōu)值=933399.938。55模型 將模型輸入計算機X11=261966.078，X1結(jié)論： 表明用1號標準汽油261966.078升，2號標準汽油265200升，3號標準汽油315672.219升，4號標準汽油90561.688升，混合成933399.938升1號飛機汽油；用1號標準汽油118033.906升，2號

44、標準汽油零升，3號標準汽油92427.758升，4號標準汽油39538.309升混合成250000升2號飛機汽油，這是既滿足需求，又使1號汽油的產(chǎn)量為最高的最優(yōu)方案。56結(jié)論： 561、此模型有多組解，如用lindo軟件算得：目標值=933400.0X11=163529.40625, X12=265200, X13=408100, X14=96570.585938,X21=216470.59375, X22=0, X23=0,X24=33529.410156.2、目標函數(shù)也可設(shè)為：（加上飛機汽油2的產(chǎn)量）max X11+X12+X13+X14+ X21+X22+X23+X24約束條件不變。最優(yōu)

45、值是一樣，目標值=118340,減去飛機汽油2的產(chǎn)量250000升，結(jié)果是一樣的。注解571、此模型有多組解，如用lindo軟件算得：注解57補充題，某鋼鐵公司生產(chǎn)一種合金，要求成分規(guī)格為：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%55%之間，不允許有其它成分，鋼鐵公司擬從五種不同級別的礦石中進行冶煉，每種礦物的成分含量和價格如下表，礦石雜質(zhì)在冶煉中廢棄，求每噸合金成本最低的礦物數(shù)量，假設(shè)礦石在冶煉過程中金屬含量沒有發(fā)生變化。 合金礦石錫%鋅%鉛%鎳%雜質(zhì)%費用(元/噸）12510102530340240003030260301552060180420200402023058

46、515175519058補充題，某鋼鐵公司生產(chǎn)一種合金，要求成分規(guī)格為：錫不少于28 合金礦石錫%鋅%鉛%鎳%雜質(zhì)%費用(元/噸）125101025303402400030302603015520601804202004020230585151755190解：設(shè)xi為第i種礦石的數(shù)量(噸)，目標是成本最低。則：Min Z=340 x1+260 x2+180 x3+230 x4+190 x5St: 0.25x1+0.4x2+0.2x4+0.08x50.280.1x1+0.15x3+0.2x4+0.05x50.150.1x1+0.05x3+0.15x5=0.10.35 0.25x1+0.3x2+0

47、.2x3+0.4x4+0.17x5 0.550.7x1+0.7x2+0.4x3+0.8x4+0.45x5=1, xi 059 合金錫%鋅%鉛%鎳%雜質(zhì)%費用(元/噸）125101模型的解為：60模型的解為：60如果設(shè)為： （0.25x1+0.4x2+0.2x4+0.08x5）/（0.7x1+0.7x2+0.4x3+0.8x4+0.45x5）0.28化簡為：0.054x1+0.204x2-0.112x3-0.024x4-0.046x50其它的同理可為：0.0054x1+0.105x2-0.09x3-0.08x4+0.0175x500.03x1-0.7x2+0.01x3+0.08x4+0.105x

48、5=00.135x1+0.085x2+0.02x3+0.04x4+0.0775x500.054x1+0.055x2+0.06x3+0.12x4+0.0125x50但是因為Min Z=340 x1+260 x2+180 x3+230 x4+190 x5此模型零解是滿足的。這樣設(shè)計有問題。61如果設(shè)為： （0.25x1+0.4x2+0.2x4+0.08 某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資，已知項目A：從第一年到第五年每年年初都可投資，當年末能收回本利110。項目B：從第一年到第三年每年年初都可以投資，次年末回收本利125，但規(guī)定每年最大投資額不能超過30萬元。項目C：第三年初

49、需要投資，到第五年末能回收本利140，但規(guī)定最大投資額不能超過80萬元。項目D：第二年初需要投資，到第五年未能回收本利155，但規(guī)定最大投資額不能超過100萬元。例84.5投資問題62 某部門現(xiàn)有資金200萬據(jù)測定每萬元每次投資的風險指數(shù)如下所示：問： （1） 應(yīng)如何確定這些項目的每年投資額，使得第五年末擁有資金的本利金額為最大? （2） 應(yīng)如何確定這些項目的每年投資額，使得第五年末擁有資金的本利在330萬的基礎(chǔ)上使得其投資總的風險系數(shù)為最小?項目風險指數(shù)（每萬元每次）A1B3C4D5.563據(jù)測定每萬元每次投資的風險指數(shù)如下所示：問： （1） 應(yīng)解： 第一 確定變量：（1）這是一個連續(xù)投資的

50、問題，設(shè)xij為第i年初投資于j項目的金額(單位萬元)，根據(jù)給定條件，將變量列于下表： 年份項目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D 第二 確定約束條件 因為項目A每年都可以投資，并且當年末都能收回本息，所以該部門每年都應(yīng)把資金都投出去，手中不應(yīng)當有剩余的呆滯資金，因此第一年：該部門年初有資金200萬元，故有 X1A+X1B=20064解： 第一 確定變量：（1）這是一個連續(xù)投資的問題，設(shè)xij第二年：因第一年給項目B的投資要到第二年末才能回收，所以該部門在第二年初擁有資金僅為項目A在第一年投資額所回收的本息110X1A，故有 X2A+X2B+X

51、2D =1.1x1A. 第三年：第三年初的資金額是從項目A第二年投資和項目B第一年投資所回收的本息總和 1.1X2A+1.25x1B 故有 X3A+X3B+X3C =1.1X2A+1.25X1B 年份項目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D65第二年：因第一年給項目B的投資要到第二年末才能回收，所以該部第四年：同以上分析，可得 X4A+X4B =1.1X3A+1.25X2B 第五年： X5A =1.1X4A+1.25X3B 另外，由于對項目B，C，D的投資額的限制有xiB30, ( i=1,2,3,4)x3c80, x2D100. 年份項目123

52、45Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D66第四年：同以上分析，可得 年份12345Ax1Ax第三、目標函數(shù)和模型該問題要求在第五年末該部門手擁有的資金額達到最大，這個目標函數(shù)可以表示為: max (1.1X5A+1.25X4B+1.4X3C+1.55X2D)模型為：目標函數(shù)：max z=1.1X5A+1.25X4B+1.4X3C+1.55X2D S.t. X1A+X1B=200 X2A+X2B+X2D =1.1X1A. X3A+X3B+X3C =1.1X2A+1.25X1B X4A+X4B =1.1X3A+1.25X2B X5A =1.1X4A+1.25

53、X3B XiB30, ( i=1,2,3,4) X3c80, X2D100. Xij0.67第三、目標函數(shù)和模型該問題要求在第五年末該部門手擁有的資金額max 1.1x5a+1.25x4b+1.4x3c+1.55x2dSt x1a+x1b=200 x2a+x2b+x2d-1.1x1a=0 x3a+x3b+x3c-1.1x2a-1.25x1b=0 x4a+x4b-1.1x3a-1.25x2b=0 x5a-1.1x4a-1.25x3b=0X1b30 x2b 30 x3b 30 x4b 30 x3c 80 x2d 100化簡才能上機 化簡后得到：68max 1.1x5a+1.25x4b+1.4x3c

54、+1.55模型 將模型輸入計算機x1A=170, x2A=57, x3A=0, x4A=7.5, x5A=33.5 ，x1B=30, x2B=30, x3B=20.2, x4B=30 x3C=80 ，x2D=100 第五年末擁有的資金的本利（即目標函數(shù)最大值）為341.35萬元69模型 將模型輸入計算機x1A=170, x2A=57, 從對偶價格欄可知第一年初增加投資1萬元，將導致第五年末擁有資金的本利增加1.664萬元；目前第一年投資額為200萬； 第二年初增加投資1萬元（比回收,因為x2a+x2b+x2d-1.1x1a=0 ） ，將導致第五年末擁有資金的本利增加1.513萬元，目前第二年的

55、投資金額來自第一年投資于項目A而回收的110的本利；同樣可知第三年初、第四年初、第五年初增加或減少投資1萬元，將導致第五年末擁有資金的本利分別增加或減少1.375萬元、1.210萬元、1.1萬元；約束 松馳/剩余變量 對偶價格 0 1.664 0 1.513 0 1.375 0 1.21 0 1.170 從對偶價格欄可知第一年初增加投資1萬元，將導致第五年末 從第6個至第9個約束方程對偶價格欄中可知：如果第一年、第二年、第三年、第四年B項目的投資額的限制放松或收縮1萬元指標(對應(yīng)于XiB30，I=1,2,3,4），將導致第五年末擁有的資金的本利分別增加或減少0.055萬元、0萬元、0萬元、0.

56、040萬元；約束 松馳/剩余變量 對偶價格 6 0 0.0557 0 0 9.8 0 0 0.0471 從第6個至第9個約束方程對偶價格欄中可知：如果約束 松馳/剩余變量 對偶價格 10 0 0.025 11 0 0.037 從第10個和第11個約束方程對偶價格欄可知： 項目C（對應(yīng)于X3C80)、項目D （對應(yīng)于X2D100)的投資額的限制放松或收縮1萬元的指標，將導致第五年末擁有的資金的本利分別增加或減少0.025萬元、0.037萬元72約束 松馳/剩余變量 對偶價 第四個表格是關(guān)于保持對偶價格不變的右邊值的變化范圍的，當某一個的右邊值在此范圍內(nèi)變化而其他右邊值不變時，對偶價格不變，例如如

57、果第一年初現(xiàn)有資金為190萬元，從表上可知，190萬元屬于保持對偶價格不變的右邊值的變化范圍內(nèi)，故可以從其對偶價格計算出第五年末所擁有的資金的本利總數(shù)為： 341.35-(200-190) 1.664=324.71(萬元)但如第一年初現(xiàn)有資金低于變化下限177.8萬元時，則需要重新建模求解。當幾個右邊值同時變化時則可用百分之一百法則判斷原來的對偶價格是否保持不變。常數(shù)項范圍：約束 下限 當前值 上限1 177.8 200 202.673 第四個表格是關(guān)于保持對偶價格不變的右邊值的 在第三個表格中列出了目標函數(shù)中變量系數(shù)的變化范圍，當X5A、X4B、X3C和X2D中的一個變量在此范圍內(nèi)變化時，即

58、項目A的第五年、項目B的第四年、項目C的第三年、項目D的第二年投資在第五年末的回收本利的百分比中的一個在此范圍變化時，最優(yōu)解保持不變。超出這個范圍，要重新建模求解，當幾個系數(shù)同時變化時要用百分之百法則判斷，部分目標系數(shù)變動范圍：變量 下限 當前值 上限X5A 0 1.1 1.12X4B 1.21 1.25 無上限X3C 1.375 1.4 無上限X2D 1.513 1.55 無上限74 在第三個表格中列出了目標函數(shù)中變量系數(shù)的變部分目標系數(shù)變動范圍改為（書上P53有錯）：變量 下限 當前值 上限X1A 無下限 0 0.055X1B -0.055 0 無上限X4A 無下限 0 0X3B 0 0 0.025X3A 無下限 0 0.044X2B -0.044 0 0X2A 0 0 0.04同時常數(shù)項范圍也有錯按如下為準：75部分目標系數(shù)變動范圍改為（書上P53有錯）：75常數(shù)項范圍：約束 下限 當前值 上限1 177.85 200 202.62 -24.36 0 2.913 -26.8 0 3.24 -7.5 0 3.645 -33.5 0 無上限6 0 30 87.37 24 30 無上限8 26.8 30 無上限9 26.4 30 37.510 76.8 80 106.811 97.1 100 124.476常數(shù)項范圍：76