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

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

3、x6最小，這樣我們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(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班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù)，可以知道用“管理運(yùn)籌學(xué)”軟件可以求得此問題的解： x1=50， x2=20，x3=50， x4=0， x5=20， x6=10，24小時(shí)內(nèi)一共需要司機(jī)和乘務(wù)人員150人。此問題的解不唯一，用LINDO軟件計(jì)算得到：X1=60,X2=10, X3=50, X4=0, X5=30, X6

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

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

6、小值=36. 也就是說配備36個(gè)售貨員，并安排12人休息星期一、二；安排11 人休息星期三、四；安排5人休息星期四、五；安排8人休息星期六、日。這 樣的安排既滿足了工作需要，又使配備的售貨員最少。軟件對此問題的解如下： 目標(biāo)函數(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上機(jī)求解得：x1=12,x2=0,x3=11,x4=5,x5約束 松馳/剩余變量 對偶價(jià)格1 0 -0.3332 9 03 0 -0.3334 0 -0.3335 1 06 0 -0.3337 0 0由于所有約束條件的對偶價(jià)

7、格都小于或等于0，故增加約束條件的常數(shù)項(xiàng)都不會(huì)使目標(biāo)值變小。即增加售貨員是不利的。但對于約束1、3、4、6來講，減少一售貨員會(huì)使目標(biāo)函數(shù)值變小，是有利的。9約束 松馳/剩余變量 對偶價(jià)格目標(biāo)函數(shù)系數(shù)范圍：變量 下限 當(dāng)前值 上限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安排星期二開始休息和星期五開始休息的人員可以無限制，此時(shí)最優(yōu)解仍然不變。10目標(biāo)函數(shù)系數(shù)范圍：10常數(shù)項(xiàng)范圍：約束 下限 當(dāng)前值 上限1 19 28 282 無下限 15 243 15 24 424 10 25 41.55 無下

8、限 19 206 16 31 38.57 28 28 3611常數(shù)項(xiàng)范圍：11法二：設(shè)x1為星期一開始上班的人數(shù)，x2為星期二開始上班的人數(shù)，x7為星期日開始上班的人數(shù)。目標(biāo)是要求售貨人員的總數(shù)最少。(P40-2a.ltx) 目標(biāo)函數(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為星期二開始上班的人 明興公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。有關(guān)情況見表43；公司中可利用的總工時(shí)為：鑄造8000小時(shí)，機(jī)加工12000小時(shí)和裝配10000小時(shí)。公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品各生

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

12、3-(3+2+3)=15(元) 工時(shí)建立數(shù)學(xué)模型如下： 目標(biāo)函數(shù)： max 15X1+10X2+7X3+13X4+9X5 約束條件： 5X1+10X2+7X38000(這里沒包括外協(xié)鑄造時(shí)間)， 6X1+4X2+8X3+6X4+4X512000(機(jī)加工)， 3X1+2X2+2X3+3X4+2X510000(裝配)， X1，X2，X3，X4，X50用“管理運(yùn)籌學(xué)”軟件進(jìn)行計(jì)算，計(jì)算機(jī)計(jì)算結(jié)果顯示在圖4-1中。詳見上機(jī)計(jì)算。 工時(shí)與成本 甲乙丙每件鑄造工時(shí)(小時(shí))5107每件機(jī)加工工時(shí)(小時(shí)) 648 每件裝配工時(shí)（小時(shí))32216建立數(shù)學(xué)模型如下： 工時(shí)與成本 甲乙丙每件目標(biāo)函數(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)計(jì)劃為全部由自己生產(chǎn)的甲產(chǎn)品1600件，鑄造外協(xié)、其余自制生產(chǎn)乙產(chǎn)品600件，而丙產(chǎn)品不生產(chǎn)。從相差值一欄中可知，如果全部由自己生產(chǎn)的乙產(chǎn)品的利潤再增加2元達(dá)到每件12元利潤，那么全部自制的乙產(chǎn)品才有可能上馬生產(chǎn)，否則乙產(chǎn)品還是鑄造外協(xié)、其余自制的利潤更大。同樣丙產(chǎn)品的利潤要再增加13.1元達(dá)到每件利潤20.1元，丙產(chǎn)品才有可能上馬生產(chǎn)；鑄造外協(xié)、其余自制的甲產(chǎn)品利潤再增加0.5元達(dá)到13.5元，才有可能上馬生產(chǎn)。17目標(biāo)函數(shù)最優(yōu)

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

15、格，在作市場決策時(shí)，某種資源市場價(jià)格低于對偶價(jià)格時(shí)，可適量買進(jìn)這種資源，組織和增加生產(chǎn)。相反當(dāng)市場價(jià)格高于對偶價(jià)格時(shí)，可以賣出資源而不安排生產(chǎn)或提高產(chǎn)品的價(jià)格。注意?。?9 對偶價(jià)格不是市場價(jià)格，在作市場決策時(shí)，某目標(biāo)函數(shù)系數(shù)范圍：變量 下限 當(dāng)前值 上限X1 14 15 無上限X2 無下限 10 12X3 無下限 7 20.1X4 無下限 13 13.5X5 8.667 9 10 從目標(biāo)函數(shù)決策變量系數(shù)一欄中知道，當(dāng)全部自己生產(chǎn)的每件甲產(chǎn)品的利潤在14到+內(nèi)變化時(shí)，其最優(yōu)解不變；全部自己生產(chǎn)的每件乙產(chǎn)品的利潤只要不超過12元，則其最優(yōu)解不變；當(dāng)每件丙產(chǎn)品的利潤不超過20.1元時(shí)，則其最優(yōu)解不

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

17、也就是說當(dāng)常數(shù)項(xiàng)超出上面的范圍時(shí)其對偶價(jià)格可能已變，這時(shí)某種資源的市場價(jià)格與對偶價(jià)格的關(guān)系隨之發(fā)生變化。21常數(shù)項(xiàng)范圍約束 下限 當(dāng)前值 永久機(jī)械廠生產(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工序時(shí)，只能在B1設(shè)備上加工。產(chǎn)品只能在A2與B2設(shè)備上加工。已知在各種設(shè)備上加工的單件工時(shí)、原料單價(jià)、產(chǎn)品銷售單價(jià)、各種設(shè)備的有效臺(tái)時(shí)以及滿負(fù)荷操作時(shí)的設(shè)備費(fèi)用如表4 4示，要求制定最優(yōu)的產(chǎn)品加工方案

18、，使該廠利潤最大。例422 永久機(jī)械廠生產(chǎn)、表4-4設(shè) 備 產(chǎn)品單件工時(shí)設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用2791210000321B1684000250B24117000783B374000200原料單價(jià)(元件)0.250.350.5銷售單價(jià)(元件)1.2522.823表4-4設(shè) 備 產(chǎn)品單件工時(shí)設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)解：設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(A工序用1表示，B工序用2表示)的第k種設(shè)備上加工的數(shù)量。如x123表示第種產(chǎn)品在B道工序上用B3設(shè)備加工的數(shù)量。則約束 5x111+10 x2116000， (設(shè)備A1) 7x112+9x212+12x3

19、1210000， (設(shè)備A2) 6x121+8x2214000， (設(shè)備B1)， 4x122+11x3227000 (設(shè)備B2) , 7x1234000 (設(shè)備B3)設(shè) 備 產(chǎn)品單件工時(shí)設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X123400020024解：設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(A工序用1表示，設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(A工序用1表示，B工序用2表示)的第k種設(shè)備上加工的數(shù)量。恒

20、等約束： 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è)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X1234000200應(yīng)該是0才合理25設(shè)Xijk表示第i種產(chǎn)品在第j種工序上(A工序用1表示，B工設(shè) 備 產(chǎn)品

21、單件工時(shí)設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用A15,X11110,X2116000300A27,X1129,X21212,X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X1234000200原料單價(jià)(元件)0.250.350.5銷售單價(jià)(元件)1.2522.8應(yīng)該是1.25(X121+X122+X123)-0.25(X111+X112)才合理。26設(shè) 備 產(chǎn)品單件工時(shí)設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用設(shè) 備 產(chǎn)品單件工時(shí)設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用A15,X11110,X2116000300A27,X1129,X21212,

22、X31210000321B16,X1218,X2214000250B24,X12211,X3227000783B37,X123400020027設(shè) 備 產(chǎn)品單件工時(shí)設(shè)備的有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用 5x111+10 x2116000， (設(shè)備A1) 7x112+9x212+12x31210000， (設(shè)備A2) 6x121+8x2214000， (設(shè)備B1)， 4x122+11x3227000 (設(shè)備B2) , 7x1234000 (設(shè)備B3)X111+X112-X121-X122 X123=0，(產(chǎn)品在A、B工序上加工的數(shù)量相等) X211+X212-X221=0, (產(chǎn)品在A、B工序上加工

23、的數(shù)量相等) X312-X322=0, (產(chǎn)品在A、B工序上加工的數(shù)量相等) 28 5x111+10 x2116000， (設(shè)備A1)模型 將模型輸入計(jì)算機(jī)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模型 將模型輸入計(jì)算機(jī)x111=1200，x112=23 由于本題要求的決策變量的單位是件，所以答案應(yīng)該是整數(shù)。本題與例1、例2、例3實(shí)質(zhì)上都是整數(shù)規(guī)劃的問題，但是這類問題可以作

24、為線性規(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 由于本題要求的決策變量的單位是件，所以答案應(yīng) 本問題最優(yōu)的方案為生產(chǎn)產(chǎn)品1430件（X111+X112=1200+23

25、0=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=1200X211=0A2X112=230X212=500X312=324B1X121=0X221=500B2X122=

26、859X322=324B3X123= 57131 本問題最優(yōu)的方案為生產(chǎn)產(chǎn)品1430件（X111如果分別按實(shí)際產(chǎn)品和原材料來計(jì)算則有：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+8x2214000， (設(shè)備B1)， 4x122+11x3227000 (設(shè)備B2) , 7x1234000 (設(shè)備B3)X111

27、+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如果分別按實(shí)際產(chǎn)品和原材料來計(jì)算則有：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件，由A2設(shè)備加工0件。 產(chǎn)品的第B道工序由B2設(shè)備加工628.572件，由B3設(shè)備加工571.428件。 生產(chǎn)產(chǎn)品5

28、00件，它的第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)如何下料，可使所用原料最省。 解：最簡單的做法是，在每根原材料上截取2.9m、2.1m和1.5m的圓鋼各一根組成一套，每根原材料省下料頭0.

29、9m。為了做100套鋼架，需要原材料100根，共有90m的料頭。若改用套裁可以節(jié)約不少原材料，為了找到一個(gè)省料的套裁方案，先設(shè)計(jì)出較好的幾個(gè)下料方案，所謂較好，第一要求每個(gè)方案下料后的料頭較短，第二要求這些方案的總體能裁下所有各種規(guī)格的圓鋼，并且不同方案有著不同的各種所需圓鋼的比。這樣套裁才能滿足對各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的。為此設(shè)計(jì)出以下5種下料方案以供套裁用。見表45。例54.3、套裁下料問題34 某工廠要做100套鋼架，每套用長為2.表45。下料數(shù) 方案（根）長度2.9120102.1002211.531203合計(jì)7.47.37.27.16.6料頭00.10.20.30.8其

30、它方案的料頭較多，不考慮，如1根2.9,1根2.1,1根1.5,料頭為0.9m35表45。下料數(shù) 方案2.9120102. 解：為了用最少的原材料得到100套鋼架，需要混合使用上述五種下料方案，設(shè)按I，V方案下料的原材料根數(shù)分別為x1，x2，x3，x4，x5，可列出下面的數(shù)學(xué)模型。 目標(biāo)函數(shù)： min X1+X2+X3+X4+ X5 約束條件： X1+2X2+ X4 100， 2X3+ 2X4+X5 100， 3X1+X2+2X3+3X5 100， X1， X2， X3， X4， X5 0 上機(jī)計(jì)算得到如下最優(yōu)下料方案：按方案下料30根；按方案下料10根，按方案下料50根(即x1=30，x2=

31、10，x3=0，x4=50，x5=0)，只需90根原材料(即目標(biāo)函數(shù)最小值為90)即可制造100套鋼架。36 解：為了用最少的原材料得到100套鋼架，需要混合使用上述思考如果只取方案前四個(gè)或前三個(gè)或再增加其它方案，結(jié)果如何？37思考如果只取方案前四個(gè)或前三個(gè)或再增加其它方案，結(jié)果如何？3其它方案列表（不是所有）(P46-5b)12345678910111213142.9120101100000002.1002211032100001.531203120124321合計(jì)7.47.37.27.16.66.55.96.35.75.164.531.5料頭00.10.20.30.80.91.51.11.

32、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其它方案列表（不是所有）(P46-5b)1234567891模型 將模型輸入計(jì)算機(jī)解為：目標(biāo)函數(shù)值=90, x1=0,x2=40,x3=30,x4=20,其它x為0。從這里看出模型有多個(gè)解。料頭多的方案一般為0。39模型 將模型輸入計(jì)

33、算機(jī)解為：目標(biāo)函數(shù)值=90, x1= 注意！ 在建立此數(shù)學(xué)模型時(shí)，約束條件用大于等于號(hào)比用等于號(hào)要好。因?yàn)橛袝r(shí)在套用一些下料方案時(shí)可能會(huì)多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號(hào)，這個(gè)套用方案就不是可行解了。 約束條件用大于等于號(hào)時(shí)，目標(biāo)函數(shù)本來求所用原材料最少和求料頭最少是一樣的，但由于在第一個(gè)下料方案中料頭為零，無論按第一下料方案下多少根料，料頭都為零，也就是說不管第一下料方案下料是200根還是150都可使目標(biāo)函數(shù)值達(dá)到最小，這顯然不合理。所以目標(biāo)函數(shù)就一定要求原材料最少。如果所有方案料頭都不為零，則可用料頭作為最小值函數(shù)變量。40 注意！ 在建立此數(shù)學(xué)模型時(shí)，約束條件用大于

34、等于號(hào)比思考：如果原材不止一種規(guī)格，如還有10M長的原材，則如何設(shè)計(jì)模型？41思考：41 某工廠要用三種原料1，2，3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，已知產(chǎn)品的規(guī)格要求、產(chǎn)品的單價(jià)、每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)，分別見表4-6和表47。該廠應(yīng)如何安排生產(chǎn)，使利潤收入為最大? 產(chǎn)品名稱 規(guī)格要求 單價(jià)(元千克)甲 原材料1不少于50，原材料2不超過25 50 乙原材料1不少于25， 原材料2不超過50 35丙 不限 25表4-6 現(xiàn)在講第四個(gè)問題 ：4.4配料問題例642 某工廠要用三種原料1，2，3混合調(diào)配出三 解：設(shè)xij表示第i種產(chǎn)品中原材料j的含量(分別用 產(chǎn)品1，2，3表

35、示產(chǎn)品甲、乙、丙)。例如x23就表 示乙產(chǎn)品中第3種原材料的含量，目標(biāo)是使利潤 最大，利潤的計(jì)算公式如下： 原材料名稱 每天最多供應(yīng)量 單價(jià)（元/千克）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(X21+X22+X23) X220.5(X21+X22+X23)由表4-5得到：X11+X21+X31100X12+X22+X32100X13+X23+X336044由表4-6得到： X110.5(X11+X12+X13)

36、，得問題模型如下(必須整理后上機(jī)求解）：45得問題模型如下(必須整理后上機(jī)求解）：45模型 將模型輸入計(jì)算機(jī)解為：x11=100，x12=50,x13=50，其余的xij=0，也就是說每天只生產(chǎn)甲產(chǎn)品200千克，分別需要用1原料100千克，2原料50千克，3原料50千克。其它乙、丙產(chǎn)品不生產(chǎn)。目標(biāo)函數(shù)值=500元46模型 將模型輸入計(jì)算機(jī)解為：x11=100，x12=50 VARIABLE VALUE REDUCED COST X11 100.000000 0.000000 X12 50.000000 0.000000 X13 50.000000 0.000000 X21 0.000000 1

37、5.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 從相差值中可看出：只有當(dāng)X21的系數(shù)從-30增加15元?jiǎng)t乙產(chǎn)品才生產(chǎn)，只有當(dāng)X31和X33的系數(shù)分別從-40增加45元和從-10增加10元?jiǎng)t丙產(chǎn)品才生產(chǎn)，47 VARIABLE VALUE 汽油混合問題。 一種汽油的特性可用兩種指標(biāo)描述，用“辛烷數(shù)”來定量描述其點(diǎn)火性，用“蒸汽壓力”來定量描述其揮發(fā)性。某煉油廠有1，2，3，4種標(biāo)準(zhǔn)汽油，其特性和庫存量列于

38、表48中，將這四種標(biāo)準(zhǔn)汽油混合，可得到標(biāo)號(hào)為1，2的兩種飛機(jī)汽油，這兩種飛機(jī)汽油的性能指標(biāo)及產(chǎn)量需求列于表49中。問應(yīng)如何根據(jù)庫存情況適量混合各種標(biāo)準(zhǔn)汽油，既滿足飛機(jī)汽油的性能指標(biāo)，又使2號(hào)飛機(jī)汽油滿足需求，并使得1號(hào)飛機(jī)汽油產(chǎn)量最高。例748 汽油混合問題。 一種汽油的特性可用兩種指標(biāo)描設(shè)Xij為飛機(jī)汽油i 中所用標(biāo)準(zhǔn)汽油j的數(shù)量，這樣可知X11+X12+X13+X14為飛機(jī)汽油1總產(chǎn)量，總產(chǎn)量越多越好，所以有目標(biāo)函數(shù)為 max X11+X12+X13+X14 約束條件之一：X21+X22+X23+X24250000飛機(jī)汽油 辛烷數(shù) 蒸汽壓力(gcm2) 產(chǎn)量需求(L) 1不小于91不大于9

39、.9610-2越多越好2不小于100不大于9.9610-2不少于250000表4-949設(shè)Xij為飛機(jī)汽油i 中所用標(biāo)準(zhǔn)汽油j的數(shù)量，這樣可知X11表4-8:得到有關(guān)庫存量和產(chǎn)量指標(biāo)的約束條件：X11+X21380000, X12+X22265200, X13+X23408100,X14+X24130100,Xij0. 標(biāo)準(zhǔn)汽油 辛烷數(shù) 蒸汽壓力(scm2) 庫存量(L)1107.57.1110-238000029311.3810-22652003875.6910-2408100410828.4510-213010050表4-8:得到有關(guān)庫存量和產(chǎn)量指標(biāo)的約束條件： 標(biāo)準(zhǔn)汽油 下面再列出有關(guān)辛

40、烷數(shù)和蒸汽壓力的約束條件: 物理中的“分壓定律”可敘述如下：“設(shè)有一種混合氣體，由n種氣體組成。設(shè)混合氣體的壓力為P，所占總?cè)莘e為V，各組成成分的壓力及其所占容積分別為p1,pn，及v1,vn,，則PV=pj vj”。用此分壓定律可寫出有關(guān)蒸汽壓力的約束條件。飛機(jī)汽油1的蒸汽壓力不能大于9.9610-2,，即有:51 下面再列出有關(guān)辛烷數(shù)和蒸汽壓力的約束條件: 5 同樣，可以得到有關(guān)飛機(jī)汽油2的蒸汽壓力的約束條件為：2.85x21-1.42x22+4.27x23-18.40 x240.52 同樣，可以得到有關(guān)飛機(jī)汽油2的蒸汽壓力的約束條件同樣可以寫有關(guān)辛烷數(shù)的約束條件，對于飛機(jī)汽油1有：(10

41、7.5x11+93x12+87x13+108x14)/(x11+x12+x13+x14) 91. 經(jīng)整理得： 16.5x11+2x12-4x13+17x140. 對于飛機(jī)汽油2有： 7.5x21-7x22-13x23+8x240.綜上所述得到此問題的數(shù)學(xué)模型 : 標(biāo)準(zhǔn)汽油 辛烷數(shù) 蒸汽壓力(scm2)1107.57.1110-229311.3810-23875.6910-2410828.4510-253同樣可以寫有關(guān)辛烷數(shù)的約束條件，對于飛機(jī)汽油1有： 標(biāo)準(zhǔn)汽油 目標(biāo)函數(shù)：max X11+X12+X13+X14 約束條件：X21+X22+X23+X24250000, X11+X21380000

42、, 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ù)學(xué)模型：54 目標(biāo)函數(shù)：max X11+X12+X13+X模型 將模型輸入計(jì)算機(jī)X11=261966.078，X12=265200，x13=315672.219，X 14 =90561.688，X 21 =118033.906，X 22 =0，X 23

43、 =92427.758，X 24 =39538.309， 最優(yōu)值=933399.938。55模型 將模型輸入計(jì)算機(jī)X11=261966.078，X1結(jié)論： 表明用1號(hào)標(biāo)準(zhǔn)汽油261966.078升，2號(hào)標(biāo)準(zhǔn)汽油265200升，3號(hào)標(biāo)準(zhǔn)汽油315672.219升，4號(hào)標(biāo)準(zhǔn)汽油90561.688升，混合成933399.938升1號(hào)飛機(jī)汽油；用1號(hào)標(biāo)準(zhǔn)汽油118033.906升，2號(hào)標(biāo)準(zhǔn)汽油零升，3號(hào)標(biāo)準(zhǔn)汽油92427.758升，4號(hào)標(biāo)準(zhǔn)汽油39538.309升混合成250000升2號(hào)飛機(jī)汽油，這是既滿足需求，又使1號(hào)汽油的產(chǎn)量為最高的最優(yōu)方案。56結(jié)論： 561、此模型有多組解，如用lindo軟件

44、算得：目標(biāo)值=933400.0X11=163529.40625, X12=265200, X13=408100, X14=96570.585938,X21=216470.59375, X22=0, X23=0,X24=33529.410156.2、目標(biāo)函數(shù)也可設(shè)為：（加上飛機(jī)汽油2的產(chǎn)量）max X11+X12+X13+X14+ X21+X22+X23+X24約束條件不變。最優(yōu)值是一樣，目標(biāo)值=118340,減去飛機(jī)汽油2的產(chǎn)量250000升，結(jié)果是一樣的。注解571、此模型有多組解，如用lindo軟件算得：注解57 某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項(xiàng)目投資，已知項(xiàng)目A：從第一

45、年到第五年每年年初都可投資，當(dāng)年末能收回本利110。項(xiàng)目B：從第一年到第三年每年年初都可以投資，次年末回收本利125，但規(guī)定每年最大投資額不能超過30萬元。項(xiàng)目C：第三年初需要投資，到第五年末能回收本利140，但規(guī)定最大投資額不能超過80萬元。項(xiàng)目D：第二年初需要投資，到第五年未能回收本利155，但規(guī)定最大投資額不能超過100萬元。例84.5投資問題58 某部門現(xiàn)有資金200萬據(jù)測定每萬元每次投資的風(fēng)險(xiǎn)指數(shù)如下所示：問： （1） 應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年末擁有資金的本利金額為最大? （2） 應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年末擁有資金的本利在330萬的基礎(chǔ)上使得其投資

46、總的風(fēng)險(xiǎn)系數(shù)為最小?項(xiàng)目風(fēng)險(xiǎn)指數(shù)（每萬元每次）A1B3C4D5.559據(jù)測定每萬元每次投資的風(fēng)險(xiǎn)指數(shù)如下所示：問： （1） 應(yīng)解： 第一 確定變量：（1）這是一個(gè)連續(xù)投資的問題，設(shè)xij為第i年初投資于j項(xiàng)目的金額(單位萬元)，根據(jù)給定條件，將變量列于下表： 年份項(xiàng)目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D 第二 確定約束條件 因?yàn)轫?xiàng)目A每年都可以投資，并且當(dāng)年末都能收回本息，所以該部門每年都應(yīng)把資金都投出去，手中不應(yīng)當(dāng)有剩余的呆滯資金，因此第一年：該部門年初有資金200萬元，故有 X1A+X1B=20060解： 第一 確定變量：（1）這是一個(gè)連續(xù)投

47、資的問題，設(shè)xij第二年：因第一年給項(xiàng)目B的投資要到第二年末才能回收，所以該部門在第二年初擁有資金僅為項(xiàng)目A在第一年投資額所回收的本息110X1A，故有 X2A+X2B+X2D =1.1x1A. 第三年：第三年初的資金額是從項(xiàng)目A第二年投資和項(xiàng)目B第一年投資所回收的本息總和 1.1X2A+1.25x1B 故有 X3A+X3B+X3C =1.1X2A+1.25X1B 年份項(xiàng)目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D61第二年：因第一年給項(xiàng)目B的投資要到第二年末才能回收，所以該部第四年：同以上分析，可得 X4A+X4B =1.1X3A+1.25X2B 第

48、五年： X5A =1.1X4A+1.25X3B 另外，由于對項(xiàng)目B，C，D的投資額的限制有xiB30, ( i=1,2,3,4)x3c80, x2D100. 年份項(xiàng)目12345Ax1Ax2Ax3Ax4Ax5ABx1Bx2Bx3Bx4BCx3CDx2D62第四年：同以上分析，可得 年份12345Ax1Ax第三、目標(biāo)函數(shù)和模型該問題要求在第五年末該部門手擁有的資金額達(dá)到最大，這個(gè)目標(biāo)函數(shù)可以表示為: max (1.1X5A+1.25X4B+1.4X3C+1.55X2D)模型為：目標(biāo)函數(shù)：max z=1.1X5A+1.25X4B+1.4X3C+1.55X2D S.t. X1A+X1B=200 X2A

49、+X2B+X2D =1.1X1A. X3A+X3B+X3C =1.1X2A+1.25X1B X4A+X4B =1.1X3A+1.25X2B X5A =1.1X4A+1.25X3B XiB30, ( i=1,2,3,4) X3c80, X2D100. Xij0.63第三、目標(biāo)函數(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.25

50、x3b=0X1b30 x2b 30 x3b 30 x4b 30 x3c 80 x2d 100化簡才能上機(jī) 化簡后得到：64max 1.1x5a+1.25x4b+1.4x3c+1.55模型 將模型輸入計(jì)算機(jī)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 第五年末擁有的資金的本利（即目標(biāo)函數(shù)最大值）為341.35萬元65模型 將模型輸入計(jì)算機(jī)x1A=170, x2A=57, 從對偶價(jià)格欄可知第一年初增加投資1萬元，將導(dǎo)致第五年末擁有資金的本利增加1.664萬元；目

51、前第一年投資額為200萬； 第二年初增加投資1萬元（比回收,因?yàn)閤2a+x2b+x2d-1.1x1a=0 ） ，將導(dǎo)致第五年末擁有資金的本利增加1.513萬元，目前第二年的投資金額來自第一年投資于項(xiàng)目A而回收的110的本利；同樣可知第三年初、第四年初、第五年初增加或減少投資1萬元，將導(dǎo)致第五年末擁有資金的本利分別增加或減少1.375萬元、1.210萬元、1.1萬元；約束 松馳/剩余變量 對偶價(jià)格 0 1.664 0 1.513 0 1.375 0 1.21 0 1.166 從對偶價(jià)格欄可知第一年初增加投資1萬元，將導(dǎo)致第五年末 從第6個(gè)至第9個(gè)約束方程對偶價(jià)格欄中可知：如果第一年、第二年、第三

52、年、第四年B項(xiàng)目的投資額的限制放松或收縮1萬元指標(biāo)(對應(yīng)于XiB30，I=1,2,3,4），將導(dǎo)致第五年末擁有的資金的本利分別增加或減少0.055萬元、0萬元、0萬元、0.040萬元；約束 松馳/剩余變量 對偶價(jià)格 6 0 0.0557 0 0 9.8 0 0 0.0467 從第6個(gè)至第9個(gè)約束方程對偶價(jià)格欄中可知：如果約束 松馳/剩余變量 對偶價(jià)格 10 0 0.025 11 0 0.037 從第10個(gè)和第11個(gè)約束方程對偶價(jià)格欄可知： 項(xiàng)目C（對應(yīng)于X3C80)、項(xiàng)目D （對應(yīng)于X2D100)的投資額的限制放松或收縮1萬元的指標(biāo)，將導(dǎo)致第五年末擁有的資金的本利分別增加或減少0.025萬元、

53、0.037萬元68約束 松馳/剩余變量 對偶價(jià) 第四個(gè)表格是關(guān)于保持對偶價(jià)格不變的右邊值的變化范圍的，當(dāng)某一個(gè)的右邊值在此范圍內(nèi)變化而其他右邊值不變時(shí)，對偶價(jià)格不變，例如如果第一年初現(xiàn)有資金為190萬元，從表上可知，190萬元屬于保持對偶價(jià)格不變的右邊值的變化范圍內(nèi)，故可以從其對偶價(jià)格計(jì)算出第五年末所擁有的資金的本利總數(shù)為： 341.35-(200-190) 1.664=324.71(萬元)但如第一年初現(xiàn)有資金低于變化下限177.8萬元時(shí)，則需要重新建模求解。當(dāng)幾個(gè)右邊值同時(shí)變化時(shí)則可用百分之一百法則判斷原來的對偶價(jià)格是否保持不變。常數(shù)項(xiàng)范圍：約束 下限 當(dāng)前值 上限1 177.8 200 202.669 第四個(gè)表格是關(guān)于保持對偶價(jià)格不變的右邊值的 在第三個(gè)表格中列出了目標(biāo)函數(shù)中變量系數(shù)的變化范圍，當(dāng)X5A、X4B、X3C和X2D中的一個(gè)變量在此范圍內(nèi)變化時(shí)，即項(xiàng)目A的第五年、項(xiàng)目B的第四年、項(xiàng)目C的第三年、項(xiàng)目D的第二年投資在第五年末的回收本利的百分比中的一個(gè)在此范圍變化時(shí)，最優(yōu)解保持不變。超出這個(gè)范圍，要重新建模求解，當(dāng)幾個(gè)系數(shù)同時(shí)變化時(shí)要用百分之百法則