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

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

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

3、總的電視廣告時段數(shù)目5。 表示為： 300tv +150m +100ss 4000 90 tv +30 m +40 ss1000 tv 5 數(shù)學模型為：數(shù)學模型為： max z=130tv+60m+50ss s.t. 300tv +150m +100ss 4000 90 tv +30 m +40 ss1000 tv 5任務：任務：（1）excel求解；（2）錄制一個規(guī)劃求解的宏； （3）制作一個用于規(guī)劃求解的命令按鈕； （4）加入一個用于規(guī)劃求解的新菜單。 二、對偶規(guī)劃問題二、對偶規(guī)劃問題問題提出問題提出 某玻璃制品公司生產(chǎn)高質(zhì)量的玻璃制 品，包括具有手藝和最精細工藝特性 的床和玻璃門。公司有

4、三個工廠共同 生產(chǎn)窗和玻璃門，其中 工廠1：生產(chǎn)鋁框和硬制件 工廠2：生產(chǎn)木框 工廠3：生產(chǎn)玻璃和組裝窗和門已知相關數(shù)據(jù)如下：工廠 生產(chǎn)每個單位所需時間（小時） 每周可用時間（小時） 門窗11042021233218單位利潤（元） 300500任務：任務：（1）列出問題數(shù)學模型，求取總利潤最大時的兩種產(chǎn)品產(chǎn)量，并練習制作命令按鈕；（2）當門和窗的單位利潤分別在什么范圍內(nèi)變動時，公司的最優(yōu)生產(chǎn)計劃不變？（3）如果改變一個工廠可用于生產(chǎn)新產(chǎn)品的生產(chǎn)時間，結(jié)果將如何？（4）學會看靈敏度分析報告。 數(shù)學模型為：max z=300d+500w 2w 12s.t. 3d+2w 18其中，d、w分別表示生產(chǎn)

5、的門和窗的個數(shù)。運算結(jié)果報告解釋運算結(jié)果報告解釋 列出目標單元格和可變單元格以及它們的初始值、最終結(jié)果、約束條件和有關約束條件的信息。 其中，目標單元格和可變單元格是用其行和列命名的，約束單元格是用其列命名的。初值和終值分別指單元格在本次求解前的數(shù)值和求解后的數(shù)值。敏感性報告解釋敏感性報告解釋 提供關于求解結(jié)果對“目標單元格”編輯框中所指定的公式的微小變化，以及約束條件的微小變化的敏感性信息。含有整數(shù)約束條件的模型不能生成本報告。對于非線性模型，此報告提供縮減梯度和拉格朗日乘數(shù)；對于線性模型，此報告中將包含遞減成本、影子價格（機會成本）、目標系數(shù)(允許有小量增減額)以及右側(cè)約束區(qū)域。1）可變單

6、元格一欄：當門和窗的單位利潤分別在(300-300，300+450)和(500-300，+)之間變動時，最優(yōu)解保持不變。 注意：注意：最優(yōu)解不變，但最優(yōu)目標函數(shù)值可能發(fā)生變化；分別變動而不是同時變動，即固定其中一個，另一個可在適當范圍內(nèi)變動。 2）約束單元格一欄：陰影價格即運籌學中的影子價格，它是指資源每增加一個單位時目標函數(shù)的增量，即： 工廠1每周可用時間在4-2，+之間發(fā)生變化時，影子價格恒為0，對目標函數(shù)值無影響； 工廠2每周可用時間在12-6，12+6之間發(fā)生變化時，影子價格恒為150，即每增加一個單位可用時間，目標函數(shù)值就增加150， 工廠3每周可用時間在18-6，18+6之間發(fā)生變

7、化時，影子價格恒為100，即每增加一個單位可用時間，目標函數(shù)值就增加100。 注意：注意：此處也是分別變動，而不是同時變動。 極限值報告解釋極限值報告解釋列出目標單元格和可變單元格以及它們的數(shù)值、上下限和目標值。含有整數(shù)約束條件的模型不能生成本報告。其中，下限是在滿足約束條件和保持其它可變單元格數(shù)值不變的情況下，某個可變單元格可以取到的最小值。上限是在這種情況下可以取到的最大值。 延伸延伸下面對目標式系數(shù)同時變動以及約束限制值同時變動的情況分別作以延伸。（1）目標式系數(shù)同時變動的百分之百法則（the 100 percent rule of simultaneous changes in obj

8、ective function coefficients）： 如果目標函數(shù)系數(shù)同時變動，計算出每一系 數(shù)變動量占該系數(shù)同方向可容許變動范圍的 百分比，而后將各個系數(shù)的變動百分比相加 ，如果所得的和不超過百分之一百，最優(yōu)解 不會改變；如果超過百分之一百，則不能確 定最優(yōu)解是否改變。（2）約束限制值同時變動的百分之百法則（the 100 percent rule of simultaneous changes in right-hand sides）： 同時改變幾個或所有函數(shù)約束的約束右端值 ，如果這些變動的幅度不大，那么可以用影 子價格預測變動產(chǎn)生的影響。為了判別這些 變動的幅度是否允許，計算每

9、一變動占同方 向可容許變動范圍的百分比，如果所有的百 分比之和不超過百分之一百，那么影子價格 還是有效的；如果所有的百分比之和超過百 分之一百，那就無法確定影子價格是否有效。三、運輸問題三、運輸問題（一）供需平衡（一）供需平衡 某食品公司有三個罐頭加工廠a1、a2、a3，四個倉庫b1、b2、b3、b4。已知相關數(shù)據(jù)如下： 倉庫加工廠b1b2b3b4產(chǎn)量a146451365486775a2352416690791125a3995682388685100分配量80657085任務：任務：求總的運輸費用最小的運輸策略。建模求解。 數(shù)學模型為：x11+x12+x13+x14 =75 x21+x22+x

10、23+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 + 995x31+416x32+690 x33+791x34（二）供大于需（二）供大于需 某水管站主管著廣闊地域的水資源分配機構。由于該地域十分干燥，需要從外地引水。已知引入的水來自r1、r2、r3三條河流，主要供應

11、客戶為d1、d2、d3、d4四個城市的供水部門。除了r3的水不能供應d4之外，所有的河流均可供應這四個城市。運輸表格如下： 城市河流d1d2d3d4供量r11601302201705r21401301901506r3190200230-5需求2541.5x11+x12+x13+x14 5 x21+x22+x23+x24 6 x31+x32+x33+x34 1.5 x11 +x2 1 +x3 1 =2 x12 +x22 +x32 =5 x13 +x23 +x33 =4 x14 +x24 +x34=1.5xij0 i=1，2，3；j=1，2，3，4 數(shù)學模型為：min z= 160 x11+130

12、 x12+220 x13+170 x14 + 140 x21+130 x22+190 x23+150 x24 + 190 x31+200 x32+230 x33+mx34無窮大（三）轉(zhuǎn)運或轉(zhuǎn)載問題（三）轉(zhuǎn)運或轉(zhuǎn)載問題41243876523312636463工廠工廠倉庫倉庫零售商零售商600400200150350300數(shù)學模型格式所有弧線ijijxcminisxxiijij起始點運入弧線運出弧線轉(zhuǎn)運點運入弧線運出弧線0ijijxxjdxxjijij終點運出弧線運入弧線0ijx41243876523312636463工廠工廠倉庫倉庫零售商零售商41243876523312636463工廠工廠倉庫

13、倉庫零售商零售商60040020015035030041四、指派問題四、指派問題某公司營銷經(jīng)理將要主持召開一年一度的由營銷區(qū)域經(jīng)理以及銷售人員參加的銷售協(xié)商會議。為了更好的安排這次會議，他雇傭了四個臨時人員張三、李四、王五、宋六，每一個人負責完成下面的一項任務：1.書面陳述的文字處理；2.制作口頭和書面陳述的電腦圖；3.會議材料準備，包括書面材料的抄寫和組織；4.處理與會者的提前和當場注冊報名。 現(xiàn)在他需要確定將哪一項任務指派給哪一個人。相關數(shù)據(jù)如下： 任務人員1234工資/小時張三3541274014李四4745325112王五3956364313宋六3251254615五、線性規(guī)劃應用之一

14、 dea分析 數(shù)據(jù)包絡分析是一種基于線性規(guī)劃，用于評價同類型組織績效相對有效性的工具手段。這類組織例如學校、醫(yī)院、銀行分支機構、超市的各營業(yè)部等。注意：各組織具有相同的投入、產(chǎn)出項目，對應單位也應相同。 有某個銀行的4個分理處數(shù)據(jù)如下：dmu投入產(chǎn)出職員數(shù)營業(yè)面積儲蓄存款貸款中間業(yè)務分理處115140理處220130 10003501000分理處3211208004501300分理處4201359004201500試對四個分理處進行dea有效性分析，包括規(guī)模有效分析即c2r，和技術有效分析即c2gs2。（一）規(guī)模有效性分析（一）規(guī)模有效性分析 數(shù)學模型（d）：對dmu

15、1：min 15 1 +20 2 +21 3 +20 4=15 140 1 +130 2 +120 3 +135 4=1800 200 1 +350 2 +450 3 +420 4=2001600 1+1000 2+1300 3+1500 4=1600 i=0， i=1，2，3，4； =0v=1，說明為弱dea有效（c2r）；v=1，且松弛變量或人工變量均為0，說明為dea有效（c2r）；vdea有效性分析（c2r）反映的是規(guī)模有效。練習：分理處2、3、4的規(guī)模有效性分析。借助運算結(jié)果報告。（二）技術有效性分析（二）技術有效性分析 數(shù)學模型（d），以對dmu2為例。min 15 1 +20 2

16、 +21 3 +20 4=20 140 1 +130 2 +120 3 +135 4=1000 200 1 +350 2 +450 3 +420 4=3501600 1+1000 2+1300 3+1500 4=1000 1 + 2 +3 + 4=1 i=0， i=1，2，3，4； =0v=1，說明為弱dea有效（c2gs2）；v=1，且松弛變量或人工變量均為0，說明為dea有效（c2gs2） ；vdea有效性分析（c2gs2）反映的是技術有效。練習：分理處1、2、4的技術有效性分析。借助運算結(jié)果報告。六、線性規(guī)劃應用之二六、線性規(guī)劃應用之二 零和對策混合策略均衡零和對策混合策略均衡 兩個人互

17、相獨立的各自從1、2、3三個數(shù)字中任意選寫一個數(shù)字。如果二人所寫數(shù)字之和為偶數(shù)，則局中人2付給局中人1以數(shù)量為此和數(shù)的報酬；如果二人所寫數(shù)字之和為奇數(shù)，則局中人1付給局中人2以數(shù)量為此和數(shù)的報酬，求此對策的解。 支付矩陣（贏得矩陣）為：1109092927654543432為方便求解，每項加5化為非負矩陣。原數(shù)學模型為：mixxnjwxaiiiiiij., 2 , 101, 2 , 1min vmax wnjyymivyajjjjjij, 2 , 101., 2 , 1min 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對偶規(guī)劃模型：x*=1/w*xy*=1/v*y七、網(wǎng)絡優(yōu)化七、網(wǎng)絡優(yōu)化某工程項目的網(wǎng)絡計劃如圖所示，工程),()(max)(0)1(jititjtteiee),()(min)()()(jitjtitntntljlel事項的最早開始時間：事項的最遲開始時間：工作的最早可能開始時間和最早可能完工時間：),(),(),(),(