1、部分習題一、 （該題已經講過了）某公司制造三種產品A、B、C，需要兩種資源（勞動力和原材料），現要確定總利潤最大的生產計劃，列出下述線性規劃求：（1）線性規劃問題的最優解；首先將問題標準化：cj31500CBXBbx1x2x3x4x500x4x54530 63 345【5】1001963150005x4x315633/5-14/50110-11/50-300-1最優解為X*=(x1,x2,x3,x4,x5)T=(0,0,6,15,0)T，最優目標值z*=30（2）求對偶問題的數學模型及其最優解；y1*=0,y2*=1 (3) 最優解不變的情況下，求產品A的利潤允許變化范圍；最優解不變的情況下，

2、（4）假定能以10元的價格購進15單位的材料，這樣做是否有利，為什么？有利單位材料的影子價格是1元，10元錢購進15單位的材料的單位價格為2/3元，低于影子價格。同時，在保持最優基不變的情況下購進15噸的原材料，最優基不變。該材料的影子價格仍為1元。（5）當可利用的資源增加到60單位時，求最優解。cj31500CBXBbx1x2x3x4x505x4x3-151233/5-14/50110【-1】1/50-300-105x5x3159-36/513/501-11/510-3-20-10最優解為X*=(x1,x2,x3,x4,x5)T=(0,0,9,0,15)T，最優目標值z*=45（6）當產品B

3、的原材料消耗減少為2個單位時，是否影響當前的最優解，為什么？x2在最有表是非基變量，該產品的原材料消耗只影響x2的檢驗數。（7）增加約束條件2x1+x2+3x320，對原最優解有何影響，對對偶解有何影響？增加的約束條件，相當于增加了一個約束方程 cj241000CBXBb x1x2x3x4x5x6050x4x3x615620 33/52-14/510 13 1 0 0-11/500010-30 0 -10050x4x3x615623 3/5 4/5-14/5-7/5 0 1 0 1 00 -11/5 -3/5 0 0 1 0 -3 00-1 0對原問題的最優解無影響，對對偶問題的最優解也無影響

4、。二、 考慮下列線性規劃MaxZ=2X1+3X22X1+ 2X2+X3=12X1+2X2 +X4=84X1 +X5=164X2 +X6=12Xj0（j=1,2,6）其最優單純形表如下：基變量X1X2X3X4X5X6X30001-1-1/40X1410001/40X64000-21/21X220101/2-1/80j000-3/2-1/801） 當C2=5時，求新的最優解2） 當b3=4時，求新的最優解3） 當增加一個約束條件2X1+X212，問最優解是否發生變化，如果發生變化求新解？解當C2=5時4=5/25=1/80所以最優解發生變化基變量X1X2X3X4X5X60X30001-1-1/40

5、2X1410001/400X64000-21/215X220101/2-1/80j000-5/21/800X32001201/22X1210010-1/20X58000-4125X23010001/4j000-20-1/4最優解為X1=2，X2=3,Z192）當b3=4時基變量X1X2X3X4X5X60X33001-1-1/402X1110001/400X6-3000-21/213X25/20101/2-1/80j000-3/2-1/800X39/20010-1/212X1110001/400X43/20001-1/4-1/23X27/4010001/4j0000-1/2-3/4此時最優解為X

6、1=1，X2=7/4,Z29/43)增加一個約束條件基變量X1X2X3X4X5X6X7X30001-1-1/400X1410001/400X64000-21/210X220101/2-1/800X7122100001j000-3/2-1/800X30001-1-1/400X1410001/400X64000-21/210X220101/2-1/800X720001/23/801j000-3/2-1/800由于X72大于0，所以最優解不變三、用對偶單純形法求下面問題解：Cj ®4600min( zj - cj)/ai*jCBXBbx1x2x3x4ai*j<00x3-80-1(-2

7、)104,3*0x4-75-3-101OBJ=0zj ®0000zj - cj-4-600Cj ®4600CBXBbx1x2x3x46x2401/21-1/200x4-35(-5/2)0-1/212/5*,6OBJ=240zj ®36-30zj - cj-10-30Cj ®4600CBXBbx1x2x3x46x23301-3/51/54x114101/5-2/5OBJ=254zj ®46-14/5-2/5zj - cj00-14/5-2/5答：最優解為x1 =14，x2 =33，目標函數值為254。四、A、B兩個煤礦負責供應甲、乙、丙三個城市煤

8、炭。已知A、B兩礦年產量、三個城市的需求量以及從兩煤礦至各城市煤炭運價如下表。由于供不應求，經協商，甲城市必要時可少供應030萬噸，乙城市需求須全部滿足，丙城市需求不少于270萬噸。試求：將甲、乙兩礦煤炭全部分配出去，滿足上述條件又使總運費最低的調運方案。產 銷甲乙丙產量AB152118252216400450銷量（T）320250350解：(1)依題意得產銷平衡表如下：產 銷甲甲乙丙 丙產量ABC1521M152101825M2216M2216040045070銷量（T）2903025027080(2)做初始的調運方案（伏格爾法）產 銷甲甲乙丙 丙產量A1501515250182222400

9、B21212516164501403027010CM0MM07070銷量（T）2903025027080（3）用位勢法進行檢驗產 銷甲甲乙丙 丙UA01501501812221222-6B2121251616000100CM0MM0-16M-5-5M-80V2121241616 (4) 做閉回路調整調整后為：產 銷甲甲乙丙 丙產量A1501515250182222400B212125161645014027040CM0MM0703040銷量（T）2903025027080（5）進行進一步檢驗產 銷甲甲乙丙 丙UA01501501812221222-6B2121251616005100CM0MM

10、0-16M-50M-8M0V2116241616(6) 調整后的方案為最優方案最低費用150×15250×18140×21270×1640×1630×040×014650五、分配甲、乙、丙、丁四人去完成5項任務。每人完成各項任務時間如下表所示。由于任務數多于人數，故規定其中有一人可兼完成兩項任務，其余三人每人完成一項，試確定總花費時間最少的指派方案。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：假設增加一個人戊完成各項工作的時間取A、B、C、D、E最小值。得效率矩陣為：

11、各行減最小值，各列減最小值：得變換得進一步最有指派方案甲B，乙C,D，丙E，丁A最低費用2926203224131六、某廠擬建兩種不同類型的冶煉爐。甲種爐每臺投資為2個單位，乙種爐每臺投資為1個單位，總投資不能超過10個單位；又該廠被許可用電量為2個單位，乙種爐被許可用電量為2個單位，但甲種爐利用余熱發電，不僅可以滿足本身需要，而且可供出電量1個單位。已知甲種爐每臺收益為6個單位，乙種爐每臺收益為4個單位。試問：應建甲、乙兩種爐各多少臺，使之收益最大？該問題也可如下表表示。（要求用割平面法求解該整數規劃問題）甲種爐(x1) 乙種爐(x2) 限 量每臺投資/單位2110用電量/單位-122收益/

12、單位64解：設x1,x2為甲乙種爐應建臺數，則用單純形法求最優解，見下表?；兞縝X1X2X3X4X31021105X42-1201-z06400X1511/21/2010X4705/21/2114/5-z-3001-30X118/5102/5-1/5X214/5011/52/5-z-32.800-16/5-2/5最優解為確定割平面方程：從而，構造割平面，并且標準化，加入最優表中，用對偶單純形法求最優解，見下表。基變量bX1X2X3X4X5X118/5102/5-1/50X214/5011/52/50X5-4/500-1/5-2/51-z-32.800-16/5-2/50基變量bX1X2X3X

13、4X5X14101/20-1/2X2201001X42001/21-5/2-z-3200-30-1。此解為整數解，故計算停止。七、某公司打算將3千萬元資金用于改造擴建所屬的3個工廠，每個工廠的利潤增長額與所分配的投資有關。各工廠在獲得不同的投資額時所能增加的利潤如下表所示，問應如何分配資金，使公司總的利潤為最大。 利潤 投資工廠01千萬2千萬3千萬102.541020358.530269解：K為階段變量，k=1,2,3 Sk:第k階段所剩的資金數 Xk：第k階段分配給第k個工廠的資金數 gk（xk）：將xk分配給第k個工廠的效益 狀態轉移方程：Sk+1= Sk-xk 遞推關系：第三階段，k=3

14、X3=s3x3s3g3(x3)f3(s3)x*301230000122126623993第二階段：s3=s2-x2， 0£s2£3， 0£x2£s2x2s2f2(s2)x*2012300+00010+23+02120+63+25+06030+93+65+28.5+090,1第三階段S1=3S2=s1-x1, 0£x1£s1x1s1f1(s1)x*1012330+92.5+64+310+0103最優分配方案為，x1*=3,x2*=0,x3*=0最佳獲益值：10千萬。八、甲乙乒乓球隊進行團體對抗賽，每對由三名球員組成，雙方都可排成三種不同

15、的陣容，每一種陣容可以看成一種策略，雙方各選一種策略參賽。比賽共賽三局，規定每局勝者得1分，輸者得-1分，可知三賽三勝得3分，三賽二勝得1分，三賽一勝得-1分，三賽三負得-3分。甲隊的策略集為S1=1，2，3，乙隊的策略集為S1=1，2，3，根據以往比賽得分資料，可得甲隊的贏得矩陣為A，如下：A=1 1 11 -1 -33 -1 3 試問這次比賽各隊應采用哪種陣容上場最為穩妥。解：甲隊的1，2，3 三種策略可能帶來的最少贏得，即矩陣A中每行的最小元素分別為： 1，-3，-1，在這些最少贏得中最好的結果是1，即甲隊應采取策略1 ，無論對手采用什么策略，甲隊至少得1分。而對乙隊來說，策略1，2，3

16、 可能帶來的最少贏得，即矩陣A中每列的最大因素（因為兩人零和策甲隊得分越多，就使得乙隊得分越少），分別為： 3，1，3，其中乙隊最好的結果為甲隊得1分，這時乙隊采取2 策略，不管甲隊采用什么策略甲隊的得分不會超過1分（即乙隊的失分不會超過1）。這樣可知甲隊應采用1 策略，乙隊應采取2 策略。把這種最優策略1 和2 分別稱為局中人甲隊、乙隊的最優純策略。這種最優純策略只有當贏得矩陣A=（aij）中等式 max min aij = min max aij i j j i成立時，局中人才有最優純策略，并把（1 ，2）稱為對策G在純策略下的解，又稱（1 ，2）為對策G的鞍點。九、矩陣對策的混合策略5

17、9 8 6 A=解：首先設甲使用1 的概率為X1，使用2 的概率為X2，并設在最壞的情況下（即乙出對其最有利的策略情況下），甲的贏得的平均值等于V。這樣我們建立以下的數學關系：1.甲使用1 的概率X1和使用2 的概率X2的和為1，并知概率值具有非負性，即X1+ X2=1，且有X10，X20.2.當乙使用1 策略時，甲的平均贏得為：5X1+ 8X2，此平均贏得應大于等于V，即5X1+ 8X2V3.當乙使用2 策略時，甲的平均贏得為：9X1+ 6X2，此平均贏得應大于等于V，即9X1+ 6X2V第二步，我們來考慮V的值，V的值與贏得矩陣A的各因素的值是有關的，如果A的各元素的值都大于零，即不管甲采

18、用什么策略，乙采用什么策略，甲的贏得都是正的。這時的V值即在乙出對其最有利的策略時甲的平均贏得也顯然是正的。因為A的所有元素都取正值，所以可知V0.第三步，作變量替換，令Xi =(i=1，2)考慮到V0，這樣把以上5個數量關系式變為：X1+ X2 =，X10，X20，5X1+ 8X2 19X1+ 6X2 1對甲來說，他希望V值越大越好，也就是希望的值越小越好，最后，我們就建立起求甲的最優混合策略的線性規劃的模型如下：min X1+ X2約束條件： 5X1+ 8X2 19X1+ 6X2 1 X10，X20同樣求出乙最優混合策略，設y1, y2分別為乙出策略1，2 的概率，V為甲出對其最有利的策略的情況下，乙的損失的平均值。同樣我們可以得到：y1+ y2=1,5y1+ 9y2 V8y1+ 6y2 Vy10，y20.同樣作變量替換，令yi =(i=1，2)得關系式： y1+ y2 =5y1+ 9y2 18y1+ 6y2 1y10，y20.乙希望損失