線規(guī)劃建模與求解PPT課件

1、 線性規(guī)劃線性規(guī)劃 建模與求建模與求解解目錄線性規(guī)劃問(wèn)題對(duì)偶規(guī)劃問(wèn)題運(yùn)輸問(wèn)題指派問(wèn)題線性規(guī)劃運(yùn)用之一：DEA分析線性規(guī)劃運(yùn)用值二：零和對(duì)策混合戰(zhàn)略附錄一、線性規(guī)劃問(wèn)題一、線性規(guī)劃問(wèn)題問(wèn)題提出問(wèn)題提出 某食品公司雇傭了一家廣告公司來(lái)協(xié)助設(shè)某食品公司雇傭了一家廣告公司來(lái)協(xié)助設(shè)計(jì)計(jì) 全國(guó)性的促銷活動(dòng)，方案最多支付廣告公全國(guó)性的促銷活動(dòng)，方案最多支付廣告公司司 效力酬金效力酬金100萬(wàn)元，廣告費(fèi)用萬(wàn)元，廣告費(fèi)用400萬(wàn)元。根萬(wàn)元。根 據(jù)該食品公司產(chǎn)品情況，廣告公司確定了據(jù)該食品公司產(chǎn)品情況，廣告公司確定了最最 有效的三種廣告媒體。有效的三種廣告媒體。媒體媒體1：星期六上午兒童節(jié)目的電視廣告：星期六上午

2、兒童節(jié)目的電視廣告媒體媒體2：食品與家庭導(dǎo)向的雜志廣告：食品與家庭導(dǎo)向的雜志廣告媒體媒體3：主要報(bào)紙星期天增刊上的廣告：主要報(bào)紙星期天增刊上的廣告資源每種活動(dòng)的單位資源運(yùn)用量可獲得的資源數(shù)電視廣告雜志廣告星期天增刊廣告廣告預(yù)算300,000150,000100,000400萬(wàn)方案預(yù)算90,00030,00040,000100萬(wàn)電視時(shí)段1005單位奉獻(xiàn)1306050 如今要處理的問(wèn)題是如何確定各種廣告活動(dòng)的程度levels以獲得最有效的廣告組合advertising mix。相關(guān)數(shù)據(jù)如下： 問(wèn)題分析與建模問(wèn)題分析與建模 本問(wèn)題是一個(gè)典型的線性規(guī)劃問(wèn)題。本問(wèn)題是一個(gè)典型的線性規(guī)劃問(wèn)題。食品公司的最

3、終目的是利潤(rùn)最大化，在食品公司的最終目的是利潤(rùn)最大化，在此題中用單位奉獻(xiàn)表示單位利潤(rùn)。此題中用單位奉獻(xiàn)表示單位利潤(rùn)。 有目的函數(shù)為：有目的函數(shù)為：Max z=130TV+60M+50SSMax z=130TV+60M+50SS 其中，其中，TVTV、M M、SSSS分別表示電視上的分別表示電視上的廣告時(shí)段數(shù)、雜志上的廣告數(shù)目和星期廣告時(shí)段數(shù)、雜志上的廣告數(shù)目和星期天增刊上的廣告數(shù)目。天增刊上的廣告數(shù)目。v約束條件有三個(gè)：v1廣告總費(fèi)用400萬(wàn)；v2方案總本錢100萬(wàn)；v3總的電視廣告時(shí)段數(shù)目5。v表示為：v300TV+150M+100SS4000v90TV+30M+40SS1000vTV5 數(shù)

4、學(xué)模型為： Max z=130TV+60M+50SS s.t. 300TV +150M +100SS 4000 90 TV +30 M +40 SS1000 TV 5義務(wù)：義務(wù)：1EXCEL求解；求解；2錄制一個(gè)規(guī)劃求解的宏；錄制一個(gè)規(guī)劃求解的宏； 3制造一個(gè)用于規(guī)劃求解的命令按鈕；制造一個(gè)用于規(guī)劃求解的命令按鈕； 4參與一個(gè)用于規(guī)劃求解的新菜單。參與一個(gè)用于規(guī)劃求解的新菜單。 二、對(duì)偶規(guī)劃問(wèn)題二、對(duì)偶規(guī)劃問(wèn)題問(wèn)題提出問(wèn)題提出 某玻璃制品公司消費(fèi)高質(zhì)量的玻璃制某玻璃制品公司消費(fèi)高質(zhì)量的玻璃制 品，包括具有手藝和最精細(xì)工藝特性品，包括具有手藝和最精細(xì)工藝特性 的床和玻璃門。公司有三個(gè)工廠共同的床

5、和玻璃門。公司有三個(gè)工廠共同 消費(fèi)窗和玻璃門，其中消費(fèi)窗和玻璃門，其中 工廠工廠1：消費(fèi)鋁框和硬制件：消費(fèi)鋁框和硬制件 工廠工廠2：消費(fèi)木框：消費(fèi)木框 工廠工廠3：消費(fèi)玻璃和組裝窗和門：消費(fèi)玻璃和組裝窗和門知相關(guān)數(shù)據(jù)如下：工廠生產(chǎn)每個(gè)單位所需時(shí)間（小時(shí)）每周可用時(shí)間（小時(shí)）門窗11042021233218單位利潤(rùn)（元）300500義務(wù)：義務(wù)：1列出問(wèn)題數(shù)學(xué)模型，求取總利潤(rùn)最列出問(wèn)題數(shù)學(xué)模型，求取總利潤(rùn)最大時(shí)的兩種產(chǎn)品產(chǎn)量，并練習(xí)制造命令大時(shí)的兩種產(chǎn)品產(chǎn)量，并練習(xí)制造命令按鈕；按鈕；2當(dāng)門和窗的單位利潤(rùn)分別在什么范當(dāng)門和窗的單位利潤(rùn)分別在什么范圍內(nèi)變動(dòng)時(shí)，公司的最優(yōu)消費(fèi)方案不變？圍內(nèi)變動(dòng)時(shí)，公司

6、的最優(yōu)消費(fèi)方案不變？3假設(shè)改動(dòng)一個(gè)工廠可用于消費(fèi)新產(chǎn)假設(shè)改動(dòng)一個(gè)工廠可用于消費(fèi)新產(chǎn)品的消費(fèi)時(shí)間，結(jié)果將如何？品的消費(fèi)時(shí)間，結(jié)果將如何？4學(xué)會(huì)看靈敏度分析報(bào)告。學(xué)會(huì)看靈敏度分析報(bào)告。 數(shù)學(xué)模型為：Max z=300D+500W 2W 12s.t. 3D+2W 18其中，D、W分別表示消費(fèi)的門和窗的個(gè)數(shù)。運(yùn)算結(jié)果報(bào)告解釋運(yùn)算結(jié)果報(bào)告解釋列出目的單元格和可變單元格以及它們的初始值、最終結(jié)果、約束條件和有關(guān)約束條件的信息。其中，目的單元格和可變單元格是用其行和列命名的，約束單元格是用其列命名的。初值和終值分別指單元格在本次求解前的數(shù)值和求解后的數(shù)值。敏感性報(bào)告解釋敏感性報(bào)告解釋提供關(guān)于求解結(jié)果對(duì)“目的

7、單元格編輯框中所指定的公式的微小變化，以及約束條件的微小變化的敏感性信息。含有整數(shù)約束條件的模型不能生本錢報(bào)告。對(duì)于非線性模型，此報(bào)告提供縮減梯度和拉格朗日乘數(shù)；對(duì)于線性模型，此報(bào)告中將包含遞減本錢、影子價(jià)錢時(shí)機(jī)本錢、目的系數(shù)(允許有小量增減額)以及右側(cè)約束區(qū)域。1可變單元格一欄：當(dāng)門和窗的單位利潤(rùn)分別在(300-300，300+450)和(500-300，+)之間變動(dòng)時(shí)，最優(yōu)解堅(jiān)持不變。 留意：最優(yōu)解不變，但最優(yōu)目的函數(shù)值能夠發(fā)生變化；分別變動(dòng)而不是同時(shí)變動(dòng)，即固定其中一個(gè)，另一個(gè)可在適當(dāng)范圍內(nèi)變動(dòng)。 2約束單元格一欄：陰影價(jià)錢即運(yùn)籌學(xué)中的影子價(jià)錢，它是指資源每添加一個(gè)單位時(shí)目的函數(shù)的增量，

8、即： 工廠1每周可用時(shí)間在4-2，+之間發(fā)生變化時(shí)，影子價(jià)錢恒為0，對(duì)目的函數(shù)值無(wú)影響； 工廠2每周可用時(shí)間在12-6，12+6之間發(fā)生變化時(shí)，影子價(jià)錢恒為150，即每添加一個(gè)單位可用時(shí)間，目的函數(shù)值就添加150， 工廠3每周可用時(shí)間在18-6，18+6之間發(fā)生變化時(shí)，影子價(jià)錢恒為100，即每添加一個(gè)單位可用時(shí)間，目的函數(shù)值就添加100。 留意：此處也是分別變動(dòng)，而不是同時(shí)變動(dòng)。 極限值報(bào)告解釋極限值報(bào)告解釋列出目的單元格和可變單元格以及它們的數(shù)值、上下限和目的值。含有整數(shù)約束條件的模型不能生本錢報(bào)告。其中，下限是在滿足約束條件和堅(jiān)持其它可變單元格數(shù)值不變的情況下，某個(gè)可變單元格可以取到的最小

9、值。上限是在這種情況下可以取到的最大值。 延伸延伸下面對(duì)目的式系數(shù)同時(shí)變動(dòng)以及約束限制值同時(shí)變動(dòng)的情況分別作以延伸。1目的式系數(shù)同時(shí)變動(dòng)的百分之百法那么The100percentruleofsimultaneouschangesinobjectivefunctioncoefficients：假設(shè)目的函數(shù)系數(shù)同時(shí)變動(dòng)，計(jì)算出每一系數(shù)變動(dòng)量占該系數(shù)同方向可允許變動(dòng)范圍的百分比，而后將各個(gè)系數(shù)的變動(dòng)百分比相加，假設(shè)所得的和不超越百分之一百，最優(yōu)解不會(huì)改動(dòng)；假設(shè)超越百分之一百，那么不能確定最優(yōu)解能否改動(dòng)。2約束限制值同時(shí)變動(dòng)的百分之百法那么The100percentruleofsimultaneous

10、changesinright-handsides：同時(shí)改動(dòng)幾個(gè)或一切函數(shù)約束的約束右端值，假設(shè)這些變動(dòng)的幅度不大，那么可以用影子價(jià)錢預(yù)測(cè)變動(dòng)產(chǎn)生的影響。為了判別這些變動(dòng)的幅度能否允許，計(jì)算每一變動(dòng)占同方向可允許變動(dòng)范圍的百分比，假設(shè)一切的百分比之和不超越百分之一百，那么影子價(jià)錢還是有效的；假設(shè)一切的百分比之和超越百分之一百，那就無(wú)法確定影子價(jià)錢能否有效。三、運(yùn)輸問(wèn)題三、運(yùn)輸問(wèn)題一供需平衡一供需平衡 某食品公司有三個(gè)罐頭加工廠某食品公司有三個(gè)罐頭加工廠A1、A2、A3，四個(gè)倉(cāng)庫(kù)，四個(gè)倉(cāng)庫(kù)B1、B2、B3、B4。知。知相關(guān)數(shù)據(jù)如下：相關(guān)數(shù)據(jù)如下： 倉(cāng)庫(kù)加工廠B1B2B3B4產(chǎn)量A146451365

11、486775A2352416690791125A3995682388685100分配量80657085義務(wù)：義務(wù)：求總的運(yùn)輸費(fèi)用最小的運(yùn)輸戰(zhàn)略。建模求總的運(yùn)輸費(fèi)用最小的運(yùn)輸戰(zhàn)略。建模求解。求解。 數(shù)學(xué)模型為：x11+x12+x13+x14 =75 x 2 1 + x 2 2 + x 2 3 + x 2 4 =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

12、+867x14 + 352x21+416x22+690 x23+791x24 + 995x31+416x32+690 x33+791x34二供大于需二供大于需 某水管站主管著寬廣地域的水資源分某水管站主管著寬廣地域的水資源分配機(jī)構(gòu)。由于該地域非常枯燥，需求從配機(jī)構(gòu)。由于該地域非常枯燥，需求從外地引水。知引入的水來(lái)自外地引水。知引入的水來(lái)自R1、R2、R3三條河流，主要供應(yīng)客戶為三條河流，主要供應(yīng)客戶為D1、D2、D3、D4四個(gè)城市的供水部門。除了四個(gè)城市的供水部門。除了R3的水不能供應(yīng)的水不能供應(yīng)D4之外，一切的河流均之外，一切的河流均可供應(yīng)這四個(gè)城市。運(yùn)輸表格如下：可供應(yīng)這四個(gè)城市。運(yùn)輸表格

13、如下：城市河流D1D2D3D4供量R11601302201705R21401301901506R3190200230-5需求2541.5x11+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 x 1 4 + x 2 4 +x34=1.5xij0 i=1，2，3；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 +

14、 190 x31+200 x32+230 x33+Mx34無(wú)窮大三轉(zhuǎn)運(yùn)或轉(zhuǎn)載問(wèn)題三轉(zhuǎn)運(yùn)或轉(zhuǎn)載問(wèn)題41243876523312636463工廠工廠倉(cāng)庫(kù)倉(cāng)庫(kù)零售商零售商600400200150350300數(shù)學(xué)模型格式所有弧線ijijxcMinisxxiijij起始點(diǎn)運(yùn)入弧線運(yùn)出弧線轉(zhuǎn)運(yùn)點(diǎn)運(yùn)入弧線運(yùn)出弧線0ijijxxjdxxjijij終點(diǎn)運(yùn)出弧線運(yùn)入弧線0ijx41243876523312636463工廠工廠倉(cāng)庫(kù)倉(cāng)庫(kù)零售商零售商41243876523312636463工廠工廠倉(cāng)庫(kù)倉(cāng)庫(kù)零售商零售商60040020015035030041四、指派問(wèn)題四、指派問(wèn)題某公司營(yíng)銷經(jīng)理將要主持召開一年一度的由營(yíng)

15、銷區(qū)域經(jīng)理以及銷售人員參與的銷售協(xié)商會(huì)議。為了更好的安排這次會(huì)議，他雇傭了四個(gè)暫時(shí)人員張三、李四、王五、宋六，每一個(gè)人擔(dān)任完成下面的一項(xiàng)義務(wù)：1.書面陳說(shuō)的文字處置；2.制造口頭和書面陳說(shuō)的電腦圖；3.會(huì)議資料預(yù)備，包括書面資料的謄寫和組織；4.處置與會(huì)者的提早和當(dāng)場(chǎng)注冊(cè)報(bào)名。如今他需求確定將哪一項(xiàng)義務(wù)指派給哪一個(gè)人。相關(guān)數(shù)據(jù)如下：任務(wù)人員1234工資/小時(shí)張三3541274014李四4745325112王五3956364313宋六3251254615五、線性規(guī)劃運(yùn)用之一 DEA分析 數(shù)據(jù)包絡(luò)分析是一種基于線性規(guī)劃，用于評(píng)價(jià)同類型組織績(jī)效相對(duì)有效性的工具手段。這類組織例如學(xué)校、醫(yī)院、銀行分支機(jī)

16、構(gòu)、超市的各營(yíng)業(yè)部等。留意：各組織具有一樣的投入、產(chǎn)出工程，對(duì)應(yīng)單位也應(yīng)一樣。 有某個(gè)銀行的4個(gè)分理處數(shù)據(jù)如下：DMU投入產(chǎn)出職員數(shù)營(yíng)業(yè)面積儲(chǔ)蓄存款貸款中間業(yè)務(wù)分理處11514018002001600分理處22013010003501000分理處3211208004501300分理處4201359004201500試對(duì)四個(gè)分理處進(jìn)展DEA有效性分析，包括規(guī)模有效分析即C2R，和技術(shù)有效分析即C2GS2。一規(guī)模有效性分析一規(guī)模有效性分析 數(shù)學(xué)模型數(shù)學(xué)模型D：對(duì)DMU1：Min151+202+213+204=151401+1302+1203+4=18002001+3502+4503+4204=20

17、016001+10002+13003+15004=1600i=0，i=1，2，3，4；=0v=1，闡明為弱DEA有效C2R；v=1，且松弛變量或人工變量均為0，闡明為DEA有效C2R；vDEA有效性分析C2R反映的是規(guī)模有效。練習(xí)：分理處2、3、4的規(guī)模有效性分析。借助運(yùn)算結(jié)果報(bào)告。二技術(shù)有效性分析二技術(shù)有效性分析 數(shù)學(xué)模型數(shù)學(xué)模型D，以對(duì)，以對(duì)DMU2為例。為例。Min151+202+213+204=201401+1302+1203+4=10002001+3502+4503+4204=35016001+10002+13003+15004=10001+2+3+4=1i=0，i=1，2，3，4；

18、=0v=1，闡明為弱DEA有效C2GS2；v=1，且松弛變量或人工變量均為0，闡明為DEA有效C2GS2 ；vDEA有效性分析C2GS2反映的是技術(shù)有效。練習(xí)：分理處1、2、4的技術(shù)有效性分析。借助運(yùn)算結(jié)果報(bào)告。六、線性規(guī)劃運(yùn)用之二六、線性規(guī)劃運(yùn)用之二 零和對(duì)策混合戰(zhàn)略平衡零和對(duì)策混合戰(zhàn)略平衡 兩個(gè)人相互獨(dú)立的各自從1、2、3三個(gè)數(shù)字中恣意選寫一個(gè)數(shù)字。假設(shè)二人所寫數(shù)字之和為偶數(shù)，那么局中人2付給局中人1以數(shù)量為此和數(shù)的報(bào)酬；假設(shè)二人所寫數(shù)字之和為奇數(shù)，那么局中人1付給局中人2以數(shù)量為此和數(shù)的報(bào)酬，求此對(duì)策的解。 支付矩陣博得矩陣為：1109092927654543432為方便求解，每項(xiàng)加5化為非負(fù)矩陣。原數(shù)學(xué)模型為：mixxnjwxaiiiiiij., 2 , 101, 2