線性規(guī)劃-建模與求解

1、 線性規(guī)劃 建模與求解1目錄線性規(guī)劃問(wèn)題對(duì)偶規(guī)劃問(wèn)題運(yùn)輸問(wèn)題指派問(wèn)題線性規(guī)劃應(yīng)用之一：DEA分析線性規(guī)劃應(yīng)用值二：零和對(duì)策混合策略附錄2一、線性規(guī)劃問(wèn)題問(wèn)題提出 某食品公司雇傭了一家廣告公司來(lái)幫助設(shè)計(jì) 全國(guó)性的促銷活動(dòng)，計(jì)劃最多支付廣告公司 服務(wù)酬金100萬(wàn)元，廣告費(fèi)用400萬(wàn)元。根 據(jù)該食品公司產(chǎn)品狀況，廣告公司確定了最 有效的三種廣告媒體。媒體1：星期六上午兒童節(jié)目的電視廣告媒體2：食品與家庭導(dǎo)向的雜志廣告媒體3：主要報(bào)紙星期天增刊上的廣告3資源每種活動(dòng)的單位資源使用量可獲得的資源數(shù)電視廣告雜志廣告星期天增刊廣告廣告預(yù)算300,000150,000100,000400萬(wàn)計(jì)劃預(yù)算90,000

2、30,00040,000100萬(wàn)電視時(shí)段1005單位貢獻(xiàn)1306050 現(xiàn)在要解決的問(wèn)題是如何確定各種廣告活動(dòng)的水平（levels）以取得最有效的廣告組合（advertising mix）。相關(guān)數(shù)據(jù)如下： 4問(wèn)題分析與建模 本問(wèn)題是一個(gè)典型的線性規(guī)劃問(wèn)題。食品公司的最終目標(biāo)是利潤(rùn)最大化，在本題中用單位貢獻(xiàn)表示單位利潤(rùn)。 有目標(biāo)函數(shù)為：Max z=130TV+60M+50SS 其中，TV、M、SS分別表示電視上的廣告時(shí)段數(shù)、雜志上的廣告數(shù)目和星期天增刊上的廣告數(shù)目。5約束條件有三個(gè)： （1）廣告總費(fèi)用400萬(wàn)； （2）計(jì)劃總成本100萬(wàn)； （3）總的電視廣告時(shí)段數(shù)目5。 表示為： 300TV +

3、150M +100SS 4000 90 TV +30 M +40 SS1000 TV 56 數(shù)學(xué)模型為： Max z=130TV+60M+50SS s.t. 300TV +150M +100SS 4000 90 TV +30 M +40 SS1000 TV 5任務(wù)：（1）EXCEL求解；（2）錄制一個(gè)規(guī)劃求解的宏； （3）制作一個(gè)用于規(guī)劃求解的命令按鈕； （4）加入一個(gè)用于規(guī)劃求解的新菜單。 7 二、對(duì)偶規(guī)劃問(wèn)題問(wèn)題提出 某玻璃制品公司生產(chǎn)高質(zhì)量的玻璃制 品，包括具有手藝和最精細(xì)工藝特性 的床和玻璃門。公司有三個(gè)工廠共同 生產(chǎn)窗和玻璃門，其中 工廠1：生產(chǎn)鋁框和硬制件 工廠2：生產(chǎn)木框 工廠3

4、：生產(chǎn)玻璃和組裝窗和門8已知相關(guān)數(shù)據(jù)如下：9任務(wù)：（1）列出問(wèn)題數(shù)學(xué)模型，求取總利潤(rùn)最大時(shí)的兩種產(chǎn)品產(chǎn)量，并練習(xí)制作命令按鈕；（2）當(dāng)門和窗的單位利潤(rùn)分別在什么范圍內(nèi)變動(dòng)時(shí)，公司的最優(yōu)生產(chǎn)計(jì)劃不變？（3）如果改變一個(gè)工廠可用于生產(chǎn)新產(chǎn)品的生產(chǎn)時(shí)間，結(jié)果將如何？（4）學(xué)會(huì)看靈敏度分析報(bào)告。 10 數(shù)學(xué)模型為：Max z=300D+500W 2W 12s.t. 3D+2W 18其中，D、W分別表示生產(chǎn)的門和窗的個(gè)數(shù)。11運(yùn)算結(jié)果報(bào)告解釋12 列出目標(biāo)單元格和可變單元格以及它們的初始值、最終結(jié)果、約束條件和有關(guān)約束條件的信息。 其中，目標(biāo)單元格和可變單元格是用其行和列命名的，約束單元格是用其列命名的

5、。初值和終值分別指單元格在本次求解前的數(shù)值和求解后的數(shù)值。13敏感性報(bào)告解釋14 提供關(guān)于求解結(jié)果對(duì)“目標(biāo)單元格”編輯框中所指定的公式的微小變化，以及約束條件的微小變化的敏感性信息。含有整數(shù)約束條件的模型不能生成本報(bào)告。對(duì)于非線性模型，此報(bào)告提供縮減梯度和拉格朗日乘數(shù)；對(duì)于線性模型，此報(bào)告中將包含遞減成本、影子價(jià)格（機(jī)會(huì)成本）、目標(biāo)系數(shù)(允許有小量增減額)以及右側(cè)約束區(qū)域。151）可變單元格一欄：當(dāng)門和窗的單位利潤(rùn)分別在(300-300，300+450)和(500-300，+)之間變動(dòng)時(shí)，最優(yōu)解保持不變。 注意：最優(yōu)解不變，但最優(yōu)目標(biāo)函數(shù)值可能發(fā)生變化；分別變動(dòng)而不是同時(shí)變動(dòng)，即固定其中一個(gè)，

6、另一個(gè)可在適當(dāng)范圍內(nèi)變動(dòng)。 16 2）約束單元格一欄：陰影價(jià)格即運(yùn)籌學(xué)中的影子價(jià)格，它是指資源每增加一個(gè)單位時(shí)目標(biāo)函數(shù)的增量，即： 工廠1每周可用時(shí)間在4-2，+之間發(fā)生變化時(shí)，影子價(jià)格恒為0，對(duì)目標(biāo)函數(shù)值無(wú)影響； 工廠2每周可用時(shí)間在12-6，12+6之間發(fā)生變化時(shí)，影子價(jià)格恒為150，即每增加一個(gè)單位可用時(shí)間，目標(biāo)函數(shù)值就增加150， 工廠3每周可用時(shí)間在18-6，18+6之間發(fā)生變化時(shí)，影子價(jià)格恒為100，即每增加一個(gè)單位可用時(shí)間，目標(biāo)函數(shù)值就增加100。 注意：此處也是分別變動(dòng)，而不是同時(shí)變動(dòng)。 17極限值報(bào)告解釋列出目標(biāo)單元格和可變單元格以及它們的數(shù)值、上下限和目標(biāo)值。含有整數(shù)約束條

7、件的模型不能生成本報(bào)告。其中，下限是在滿足約束條件和保持其它可變單元格數(shù)值不變的情況下，某個(gè)可變單元格可以取到的最小值。上限是在這種情況下可以取到的最大值。 18延伸下面對(duì)目標(biāo)式系數(shù)同時(shí)變動(dòng)以及約束限制值同時(shí)變動(dòng)的情況分別作以延伸。（1）目標(biāo)式系數(shù)同時(shí)變動(dòng)的百分之百法則（The 100 percent rule of simultaneous changes in objective function coefficients）： 如果目標(biāo)函數(shù)系數(shù)同時(shí)變動(dòng)，計(jì)算出每一系 數(shù)變動(dòng)量占該系數(shù)同方向可容許變動(dòng)范圍的 百分比，而后將各個(gè)系數(shù)的變動(dòng)百分比相加 ，如果所得的和不超過(guò)百分之一百，最優(yōu)解 不會(huì)

8、改變；如果超過(guò)百分之一百，則不能確 定最優(yōu)解是否改變。19（2）約束限制值同時(shí)變動(dòng)的百分之百法則（The 100 percent rule of simultaneous changes in right-hand sides）： 同時(shí)改變幾個(gè)或所有函數(shù)約束的約束右端值 ，如果這些變動(dòng)的幅度不大，那么可以用影 子價(jià)格預(yù)測(cè)變動(dòng)產(chǎn)生的影響。為了判別這些 變動(dòng)的幅度是否允許，計(jì)算每一變動(dòng)占同方 向可容許變動(dòng)范圍的百分比，如果所有的百 分比之和不超過(guò)百分之一百，那么影子價(jià)格 還是有效的；如果所有的百分比之和超過(guò)百 分之一百，那就無(wú)法確定影子價(jià)格是否有效。20三、運(yùn)輸問(wèn)題（一）供需平衡 某食品公司有三個(gè)

9、罐頭加工廠A1、A2、A3，四個(gè)倉(cāng)庫(kù)B1、B2、B3、B4。已知相關(guān)數(shù)據(jù)如下： 21任務(wù)：求總的運(yùn)輸費(fèi)用最小的運(yùn)輸策略。建模求解。 22 數(shù)學(xué)模型為：x11+x12+x13+x14 =75 x21+x22+x23+x24 =125 x31+x32+x33+x34 =100 x11 +x21 +x31 =80 x12 +x22 +x32 =65 x13 +x23 +x33 =70 x14 +x24 +x34 =85xij0 i=1，2，3；j=1，2，3，4Min z= 464x11+513x12+654x13+867x14 + 352x21+416x22+690 x23+791x24 + 99

10、5x31+416x32+690 x33+791x3423（二）供大于需 某水管站主管著廣闊地域的水資源分配機(jī)構(gòu)。由于該地域十分干燥，需要從外地引水。已知引入的水來(lái)自R1、R2、R3三條河流，主要供應(yīng)客戶為D1、D2、D3、D4四個(gè)城市的供水部門。除了R3的水不能供應(yīng)D4之外，所有的河流均可供應(yīng)這四個(gè)城市。運(yùn)輸表格如下：2425x11+x12+x13+x14 5 x21+x22+x23+x24 6 x31+x32+x33+x34 1.5 x11 +x21 +x31 =2 x12 +x22 +x32 =5 x13 +x23 +x33 =4 x14 +x24 +x34=1.5xij0 i=1，2，3

11、；j=1，2，3，4 數(shù)學(xué)模型為：Min z= 160 x11+130 x12+220 x13+170 x14 + 140 x21+130 x22+190 x23+150 x24 + 190 x31+200 x32+230 x33+Mx34無(wú)窮大26（三）轉(zhuǎn)運(yùn)或轉(zhuǎn)載問(wèn)題41243876523312636463工廠倉(cāng)庫(kù)零售商60040020015035030027數(shù)學(xué)模型格式2841243876523312636463工廠倉(cāng)庫(kù)零售商41243876523312636463工廠倉(cāng)庫(kù)零售商6004002001503503004129四、指派問(wèn)題某公司營(yíng)銷經(jīng)理將要主持召開一年一度的由營(yíng)銷區(qū)域經(jīng)理以及銷

12、售人員參加的銷售協(xié)商會(huì)議。為了更好的安排這次會(huì)議，他雇傭了四個(gè)臨時(shí)人員張三、李四、王五、宋六，每一個(gè)人負(fù)責(zé)完成下面的一項(xiàng)任務(wù)：1.書面陳述的文字處理；2.制作口頭和書面陳述的電腦圖；3.會(huì)議材料準(zhǔn)備，包括書面材料的抄寫和組織；4.處理與會(huì)者的提前和當(dāng)場(chǎng)注冊(cè)報(bào)名。30 現(xiàn)在他需要確定將哪一項(xiàng)任務(wù)指派給哪一個(gè)人。相關(guān)數(shù)據(jù)如下： 任務(wù)人員1234工資/小時(shí)張三3541274014李四4745325112王五3956364313宋六325125461531五、線性規(guī)劃應(yīng)用之一 DEA分析 數(shù)據(jù)包絡(luò)分析是一種基于線性規(guī)劃，用于評(píng)價(jià)同類型組織績(jī)效相對(duì)有效性的工具手段。這類組織例如學(xué)校、醫(yī)院、銀行分支機(jī)構(gòu)、

13、超市的各營(yíng)業(yè)部等。注意：各組織具有相同的投入、產(chǎn)出項(xiàng)目，對(duì)應(yīng)單位也應(yīng)相同。 有某個(gè)銀行的4個(gè)分理處數(shù)據(jù)如下：32DMU投入產(chǎn)出職員數(shù)營(yíng)業(yè)面積儲(chǔ)蓄存款貸款中間業(yè)務(wù)分理處11514018002001600分理處22013010003501000分理處3211208004501300分理處4201359004201500試對(duì)四個(gè)分理處進(jìn)行DEA有效性分析，包括規(guī)模有效分析即C2R，和技術(shù)有效分析即C2GS2。33（一）規(guī)模有效性分析 數(shù)學(xué)模型（D）：對(duì)DMU1：Min 15 1 +20 2 +21 3 +20 4=15 140 1 +130 2 +120 3 +135 4=1800 200 1 +3

14、50 2 +450 3 +420 4=2001600 1+1000 2+1300 3+1500 4=1600 i=0， i=1，2，3，4； =034=1，說(shuō)明為弱DEA有效（C2R）；=1，且松弛變量或人工變量均為0，說(shuō)明為DEA有效（C2R）；DEA有效性分析（C2R）反映的是規(guī)模有效。練習(xí)：分理處2、3、4的規(guī)模有效性分析。借助運(yùn)算結(jié)果報(bào)告。35（二）技術(shù)有效性分析 數(shù)學(xué)模型（D），以對(duì)DMU2為例。Min 15 1 +20 2 +21 3 +20 4=20 140 1 +130 2 +120 3 +135 4=1000 200 1 +350 2 +450 3 +420 4=350160

15、0 1+1000 2+1300 3+1500 4=1000 1 + 2 +3 + 4=1 i=0， i=1，2，3，4； =036=1，說(shuō)明為弱DEA有效（C2GS2）；=1，且松弛變量或人工變量均為0，說(shuō)明為DEA有效（C2GS2） ；DEA有效性分析（C2GS2）反映的是技術(shù)有效。練習(xí)：分理處1、2、4的技術(shù)有效性分析。借助運(yùn)算結(jié)果報(bào)告。37六、線性規(guī)劃應(yīng)用之二 零和對(duì)策混合策略均衡 兩個(gè)人互相獨(dú)立的各自從1、2、3三個(gè)數(shù)字中任意選寫一個(gè)數(shù)字。如果二人所寫數(shù)字之和為偶數(shù)，則局中人2付給局中人1以數(shù)量為此和數(shù)的報(bào)酬；如果二人所寫數(shù)字之和為奇數(shù)，則局中人1付給局中人2以數(shù)量為此和數(shù)的報(bào)酬，求此對(duì)策的解。 支付矩陣（贏得矩陣）為：38為方便求解，每項(xiàng)加5化為非負(fù)矩陣。39原數(shù)學(xué)模型為：Min vMax w40Min w=x1+x2+x37x1+2x2 +9x3=12x1+9x2 =19x1 +11x3 =1x1,x2,x3 =0Max v=y1+y2+y37y1+2y2 +9y3=12y1+9y2 =19y1 +11y3 =0對(duì)偶規(guī)劃模型：X*=1/w*XY*=1/v*Y41七、網(wǎng)絡(luò)優(yōu)化某