管理運(yùn)籌學(xué)-教案ppt課件

1、管理運(yùn)籌學(xué)教案教 學(xué) 內(nèi) 容n緒緒 論論 運(yùn)籌學(xué)概況運(yùn)籌學(xué)概況n第一章第一章 線性規(guī)劃線性規(guī)劃 n第二章第二章 運(yùn)輸問題運(yùn)輸問題n第三章第三章 整數(shù)規(guī)劃整數(shù)規(guī)劃n綜合建模練習(xí)綜合建模練習(xí)1）-（10）緒 論 ： 運(yùn) 籌 學(xué) 概 況n運(yùn)籌學(xué)名稱運(yùn)籌學(xué)名稱n運(yùn)籌學(xué)的研究對象運(yùn)籌學(xué)的研究對象n運(yùn)籌學(xué)的發(fā)展運(yùn)籌學(xué)的發(fā)展n運(yùn)籌學(xué)在航空運(yùn)輸中的應(yīng)用運(yùn)籌學(xué)在航空運(yùn)輸中的應(yīng)用n課程設(shè)置情況課程設(shè)置情況運(yùn)籌學(xué)的名稱nBK：Operational ResearchORnUS：Operations ResearchORn臺灣：作業(yè)研究臺灣：作業(yè)研究n大陸：運(yùn)籌學(xué)大陸：運(yùn)籌學(xué)運(yùn)籌帷幄之中，決運(yùn)籌帷幄之中，決勝千里之外

2、勝千里之外運(yùn) 籌 學(xué) 的 研 究 對 象n資源運(yùn)用資源運(yùn)用運(yùn)用分析理論運(yùn)用分析理論n競爭現(xiàn)象競爭現(xiàn)象競爭理論競爭理論n擁擠現(xiàn)象擁擠現(xiàn)象隨機(jī)服務(wù)理論隨機(jī)服務(wù)理論運(yùn) 籌 學(xué) 的 發(fā) 展n IFORS.ORG 國際運(yùn)籌學(xué)聯(lián)盟國際運(yùn)籌學(xué)聯(lián)盟International Federation of Operational Research Societies-IFORS ,于于1959年建立）。年建立）。/index.jsp國際運(yùn)籌學(xué)聯(lián)盟航空運(yùn)輸組國際運(yùn)籌學(xué)聯(lián)盟航空運(yùn)輸組(The Airline Group of the International Federation of Op

3、erational Research Societies -AGIFORS) / 歐洲運(yùn)籌學(xué)協(xié)會歐洲運(yùn)籌學(xué)協(xié)會(Association of European Operational Research Societies-EURO). nm a t h p r o g . o r g / % E 6 % 9 5 % B 0 數(shù) 學(xué) 規(guī) 劃 學(xué) 會數(shù) 學(xué) 規(guī) 劃 學(xué) 會Mathematical Programming Society） 是一個國際是一個國際性的組織，致力于計算數(shù)學(xué)、應(yīng)用學(xué)、數(shù)學(xué)規(guī)劃的理論性的組織，致力于計算數(shù)學(xué)、應(yīng)用學(xué)、數(shù)學(xué)規(guī)劃的理論研究。研究。

4、運(yùn) 籌 學(xué) 的 發(fā) 展/home/page美國數(shù)學(xué)會American Mathematical Society - AMS ） .uk/orshop/(cojjpu553n0cnealhpkk4jzl)/orhomepage2.aspx運(yùn)籌學(xué)研究社團(tuán) （Operational Research Society ） nEconomics, Operations Research, Programming, Games - Dave Rusin; The Mathematical Atlas 提供一些簡短的文章，介紹運(yùn)籌學(xué)方面的文章，其用象征性的語言描述優(yōu)化資源

5、方面的研究。 nGlobal Optimization 這個站點(diǎn)鏈接了全球的很多關(guān)于優(yōu)化的站點(diǎn)nOR/MS Books 該站點(diǎn)收集了大量的運(yùn)籌學(xué)和管理科學(xué)方面的書。運(yùn) 籌 學(xué) 的 發(fā) 展/中國運(yùn)籌學(xué)會n7/orgs/tdyc/index.php天津運(yùn)籌學(xué)會/tddg/index.php天津大學(xué)全國精品課程運(yùn)籌學(xué)2019njpkctr/index01_detail.asp?id=2987蘭州交通大學(xué)全國精品課程運(yùn)籌學(xué)2019/res2019/data/bit/7/index.html北京理工大學(xué)全國精

6、品課程管理運(yùn)籌學(xué)2019/skyclass/C60/Asp/Root/Index.asp?Mode=1&Url=江西財經(jīng)大學(xué)全國精品課程運(yùn)籌學(xué)2019運(yùn) 籌 學(xué) 的 發(fā) 展n28/or/山東大學(xué)全國精品課程運(yùn)籌學(xué)2019/0701/東北電力大學(xué)全國精品課程運(yùn)籌學(xué)2019/四川大學(xué) 運(yùn)籌學(xué)在航空運(yùn)輸中的應(yīng)用n航班計劃問題n機(jī)隊(duì)規(guī)劃問題n飛機(jī)選型問題n機(jī)場選址問題n引進(jìn)飛機(jī)決策問題n緊缺資源排班問題機(jī)組、地面服務(wù)人員、裝卸工、操縱設(shè)備者n飛機(jī)維修計劃問題n航線網(wǎng)絡(luò)布局問題n停機(jī)位分配問

7、題n機(jī)坪作業(yè)優(yōu)化問題n收益管理問題n空中流量控制問題n航材優(yōu)化問題課程設(shè)置情況2019培養(yǎng)方案之管理運(yùn)籌學(xué)課程設(shè)置情況使用教材課程設(shè)置情況考核方式第一章 線性規(guī)劃n線性規(guī)劃(Linear programmingLP)n線性規(guī)劃的應(yīng)用案例n線性規(guī)劃的計算機(jī)求解n線性規(guī)劃解的認(rèn)識n影子價格n靈敏度分析n課程實(shí)驗(yàn)LP應(yīng)用案例生產(chǎn)計劃的安排n某企業(yè)利用四種設(shè)備生產(chǎn)兩種產(chǎn)品，單位產(chǎn)品占用各種設(shè)備的時間及有關(guān)數(shù)據(jù)如下表所示。該企業(yè)應(yīng)如何安排生產(chǎn)，可使總利潤最大？0,12416482142232max2121212121xxxxxxxxxxz目標(biāo)函數(shù)(objective function)、約束條件(con

8、straints)、非負(fù)約束(nonnegativity constraints)、決策變量(decision variables)LP應(yīng)用案例鐵皮的利用n用一塊邊長為a（=100cm)的正方形鐵皮折成盒子。如何折，可使盒子的容積最大？（x=16.67cm,V=74074cm3.)xa02)2(max2xaxxxaVLP應(yīng)用案例下料方式n用500cm長的條材截出長度為98cm和78cm的兩種毛坯分別為10000根和20000根。如何截，所用條材根數(shù)最少？(x1=1200,x5=4000,z=5200).6,5,4,3,2,1,0200006532100002345min654325432165

9、4321jxxxxxxxxxxxxxxxxxzj某機(jī)場候機(jī)樓內(nèi)每天各時段所需工作人員數(shù)如下：時段所需人數(shù)6：0010：006010： 0014： 007014： 0018： 006018： 0022： 005022： 00 2： 00202：00 6：0030設(shè)工作人員于各時段一開始時上班，連續(xù)工作 8 小時。問該侯機(jī)樓至少應(yīng)配備多少工作人員？LP應(yīng)用案例人力資源分配問題答案：時段1-60人、2-10人、3-50人、5-30人，總共150人。LP應(yīng)用案例人力資源分配問題n每周工作每周工作5 5天，連續(xù)休息天，連續(xù)休息2 2天。至少應(yīng)該配備多少人員天。至少應(yīng)該配備多少人員？（答案：星期一？（答案

10、：星期一-8-8人、三人、三-12-12人、五人、五-11-11人、六人、六-5-5人人；總共；總共3636人）人）時間所需人數(shù)時間所需人數(shù)星期一15星期五31星期二24星期六28星期三25星期七28星期四19LP應(yīng)用案例物資配運(yùn)問題有三個化肥廠為四個產(chǎn)糧區(qū)供應(yīng)化肥，供、需量及每噸化肥的運(yùn)價如下表所示。如何安排運(yùn)輸，可使總運(yùn)費(fèi)最??？建立該問題的線性規(guī)劃數(shù)學(xué)模型。 產(chǎn)糧區(qū)化肥廠B1B2B3B4供量A1587370000A24910780000A3842930000需量60000600003000030000答案：A1-B240000、-B430000，A2-B160000、-B220000，A3

11、-B330000；總運(yùn)費(fèi)890000。LP應(yīng)用案例生產(chǎn)計劃問題n甲、乙、丙三種產(chǎn)品皆需經(jīng)鑄造、機(jī)械加工和裝配三道工序，甲、乙、丙三種產(chǎn)品皆需經(jīng)鑄造、機(jī)械加工和裝配三道工序，其中甲、乙兩種產(chǎn)品的鑄造工序可以選擇自行生產(chǎn)或者外包協(xié)其中甲、乙兩種產(chǎn)品的鑄造工序可以選擇自行生產(chǎn)或者外包協(xié)作。如何安排生產(chǎn)能夠獲得最大利潤？（答案：甲作。如何安排生產(chǎn)能夠獲得最大利潤？（答案：甲- -自自16001600件件，甲，甲- -外外400400件；最大利潤件；最大利潤3320033200）甲乙丙可用工時每件鑄造工時51078000每件機(jī)械工時64812000每件裝配工時32210000自行生產(chǎn)鑄件每件成本354外

12、包協(xié)作鑄件每件成本56機(jī)械加工每件成本213裝配每件成本322每件產(chǎn)品售價231816LP應(yīng)用案例配料問題n使用三種原料使用三種原料1 1，2 2，3 3混合調(diào)配處三種不同產(chǎn)品甲、乙、丙混合調(diào)配處三種不同產(chǎn)品甲、乙、丙，情況如下表所示。如何安排生產(chǎn)能夠獲得最大利潤？（答，情況如下表所示。如何安排生產(chǎn)能夠獲得最大利潤？（答案：原料案：原料1-1-甲：甲：100100公斤，原料公斤，原料2-2-甲：甲：5050公斤，原料公斤，原料2-2-丙：丙：5050公斤，原料公斤，原料3-3-甲：甲：5050公斤；利潤公斤；利潤=500=500元）元）產(chǎn)品要求單價（元/公斤）原料可用量（公斤）單價（元/公斤）

13、甲原料1不少于50%原料2不超過25%50110065乙原料1不少于25%原料2不超過50%35210025丙不限2536035LP應(yīng)用案例投資問題n現(xiàn)有資金現(xiàn)有資金200200萬元，今后萬元，今后5 5年內(nèi)可投資項(xiàng)目如下。如何確定各項(xiàng)年內(nèi)可投資項(xiàng)目如下。如何確定各項(xiàng)目每年的投資額，使得第目每年的投資額，使得第5 5年末的資金總額最大？（答案：年末的資金總額最大？（答案：A A項(xiàng)項(xiàng)目目1-1701-170、2-62.22-62.2、5-31.45-31.4，B B項(xiàng)目項(xiàng)目1-301-30、2-24.82-24.8、3-25.923-25.92、4-304-30，C C項(xiàng)目項(xiàng)目3-803-80，

14、D D項(xiàng)目項(xiàng)目2-1002-100；第；第5 5年末資金總額年末資金總額339.04339.04萬元萬元）項(xiàng)目特點(diǎn)A第15年初都可投資，當(dāng)年末收回本利110%B第14年初都可投資，次年末收回本利125%，但每年投資額不能超過30萬元C第3年初需要投資，第5年末收回本利140%，但投資額不能超過80萬元D第2年初需要投資，第5年末收回本利155%，但投資額不能超過100萬元LP應(yīng)用案例訂貨與庫存問題n一糧庫經(jīng)營糧食批發(fā)業(yè)務(wù)。糧庫的容量為5000擔(dān)。1月1日，糧庫內(nèi)有糧食1000擔(dān)，現(xiàn)金20000元。第一季度糧食的價格如下表。每月初賣出糧食,每月末買入糧食。希望季度末糧庫余糧為2000擔(dān)。如何安排

15、可使該季度總的獲利最大？（答案：1月賣1000擔(dān)、買5000擔(dān)， 2月賣5000擔(dān)、買0擔(dān)， 3月賣0擔(dān)、買2000擔(dān)，總差價-700元）月份進(jìn)貨價（元）出貨價（元）1232.853.052.905線 性 規(guī) 劃 的 計 算 機(jī) 求 解n求解規(guī)劃問題常用的計算機(jī)軟件nMicrosoft ExcelnLindo & LingolindonMatlabnILOGnnExcel的“規(guī)劃求解簡介Excel規(guī)劃求解目標(biāo)函數(shù)設(shè)置 Excel規(guī)劃求解目標(biāo)函數(shù)設(shè)置Excel規(guī)劃求解約束條件設(shè)置E xc e l 規(guī) 劃 求 解 參 數(shù) 設(shè) 置E xc e l 規(guī) 劃 求 解 最 優(yōu)

16、 解線性規(guī)劃解的認(rèn)識n唯一最優(yōu)解的認(rèn)識唯一最優(yōu)解的認(rèn)識n無窮多最優(yōu)解的認(rèn)識無窮多最優(yōu)解的認(rèn)識n無界解的認(rèn)識無界解的認(rèn)識n無可行解的認(rèn)識無可行解的認(rèn)識n線性規(guī)劃解的認(rèn)識線性規(guī)劃解的認(rèn)識唯一最優(yōu)解的認(rèn)識0,12416482142232max2121212121xxxxxxxxxxzx124682468x20唯一最優(yōu)解的認(rèn)識0,41501053min212212121xxxxxxxxxzx124682468x2010無窮多解(Multiple optimal solutions)的認(rèn)識0,22222max21212121xxxxxxxxzx1-112-112x20-2無界解(Unbounded So

17、lution)的認(rèn)識0,18362334max21212121xxxxxxxxzx1-12-4268x20-164-8-18E xc e l 規(guī) 劃 求 解 無 界 解無可行解(Infeasibility)的認(rèn)識0,62223max21212121xxxxxxxxzx14268x2042E xc e l 規(guī) 劃 求 解 無 可 行 解前往前往線性規(guī)劃解的基本性質(zhì)n如果線性規(guī)劃問題的可行域有界，則一定有最優(yōu)解，且目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)n線性規(guī)劃問題的最優(yōu)解只可能在頂點(diǎn)或邊界上得到，而不會在可行域內(nèi)部得到。線性規(guī)劃的求解方法單純形法(Simplex Method)該解為最優(yōu)解？確

18、定初始基本可行解已得到最優(yōu)解，停頓求出更佳的基本可行解是是否否影子價格n影子價格的含義n影子價格的意義n 不同于市場價格，由資源的使用情況確定；n 反映資源在生產(chǎn)中的使用情況；n 為零時，說明該資源還有剩余或者剛好用盡；n 為正值時，說明該資源已消耗完畢；n 決定了對該種資源的處理方式；n 可作為對緊缺資源的分配依據(jù)。n影子價格的應(yīng)用影子價格的含義0,12416482142232max2121212121xxxxxxxxxxzx124682468x20 x124682468x20n增加單位資源能使總利潤增加的數(shù)量。影子價格的意義n不同于市場價格，由資源的使用情況確定；n反映資源在生產(chǎn)中的使用情

19、況；n為零時，說明該資源還有剩余或者剛好用盡；n為正值時，說明該資源已消耗完畢；n決定了對該種資源的處理方式；n可作為對緊缺資源的分配依據(jù)。影子價格的應(yīng)用x124682468x200,12416482142232max2121212121xxxxxxxxxxzn設(shè)B設(shè)備的市場價格為1(元/臺時)，應(yīng)否增加該設(shè)備的使用時間？增加多少？Excel規(guī)劃求解運(yùn)算結(jié)果報告Excel規(guī)劃求解敏感性報告Excel規(guī)劃求解極限值報告靈敏度分析線性規(guī)劃的基本假設(shè)n確定性cj、aij、bi不隨時間變化n等比性資源需要量與產(chǎn)品數(shù)量等比n可加性兩種產(chǎn)品總利潤等于各自利潤之和(兩種產(chǎn)品之間無替代性）n可分性決策變量可取

20、小數(shù)值靈敏度分析的內(nèi)容和形式n靈敏度分析的內(nèi)容n某參數(shù)的允許變化范圍，使原最優(yōu)方案不變；n某參數(shù)的變化超出允許范圍時，如何求得新的最優(yōu)方案。n靈敏度分析的形式n 價值系數(shù)cj發(fā)生變化n 右端常數(shù)bi發(fā)生變化n 增加一個變量的情況n Pj發(fā)生變化n 增加一個約束條件的情況價值系數(shù)cj發(fā)生變化0124164821422522121212121x ,xxxxxxxxxzmaxn確定產(chǎn)品的單位利潤c2 的允許變動范圍，使原最優(yōu)生產(chǎn)方案不變。當(dāng)c2變?yōu)?時，求新的最優(yōu)生產(chǎn)方案。x124682468x20 x124682468x200124164821422322121212121x ,xxxxxxxxx

21、zmax右端常數(shù)bi發(fā)生變化0124204821422322121212121x ,xxxxxxxxxzmaxn設(shè)C設(shè)備的可用臺時b3變?yōu)?0時，求新的最優(yōu)生產(chǎn)方案。x124682468x20 x124682468x200124164821422322121212121x ,xxxxxxxxxzmax增加一個變量的情況n現(xiàn)有產(chǎn)品可供選擇。生產(chǎn)每件產(chǎn)品耗用A,B,C,D設(shè)備的臺時分別為3,2,6,3，單位利潤為5元。是否應(yīng)該生產(chǎn)產(chǎn)品？生產(chǎn)多少件？0124164821422322121212121x ,xxxxxxxxxzmax01234166482214322532321323132132132

22、1x ,x ,xxxxxxxxxxxxxxzmaxPj發(fā)生變化的情況n由于工藝結(jié)構(gòu)的改進(jìn)，生產(chǎn)產(chǎn)品所耗A,B,C,D設(shè)備的時間變?yōu)?,2,5,2，單位利潤也提高到4元。應(yīng)如何安排生產(chǎn)？x124682468x20 x124682468x200124164821422322121212121x ,xxxxxxxxxzmax0124216582214233421211212121x ,xxxxxxxxxxzmax增加一個約束條件n生產(chǎn)產(chǎn)品、產(chǎn)品時增加一道工序，在E設(shè)備上進(jìn)行。產(chǎn)品、產(chǎn)品在E設(shè)備上加工的時間為2,2.4小時，E設(shè)備在計劃期內(nèi)的有效臺時為12小時。應(yīng)如何安排生產(chǎn)？x124682468x2

23、00124164821422322121212121x ,xxxxxxxxxzmax012512212416482142232212121212121x ,xxxxxxxxxxxzmax課程實(shí)驗(yàn):LP應(yīng)用案例(2)-(9)的求解n隨機(jī)抽簽確定題目；n原則上力爭每人1題，由于學(xué)生人數(shù)多而無法實(shí)現(xiàn)時，力爭使每題分配的人數(shù)均等；n每次實(shí)驗(yàn)結(jié)果皆計入平時成績。第二章 運(yùn)輸問題n產(chǎn)銷平衡運(yùn)輸問題的數(shù)學(xué)模型n產(chǎn)銷不平衡運(yùn)輸問題的數(shù)學(xué)模型n需求有界運(yùn)輸問題的數(shù)學(xué)模型n轉(zhuǎn)運(yùn)問題的數(shù)學(xué)模型n課程實(shí)驗(yàn)運(yùn)輸問題的數(shù)學(xué)模型n產(chǎn)地、銷地、運(yùn)價、運(yùn)費(fèi)n產(chǎn)銷平衡問題的數(shù)學(xué)模型 n產(chǎn)大于銷問題的數(shù)學(xué)模型n銷大于產(chǎn)問題的數(shù)學(xué)模

24、型n有最低需求問題的數(shù)學(xué)模型n轉(zhuǎn)運(yùn)問題的數(shù)學(xué)模型產(chǎn)地、銷地、運(yùn)價、運(yùn)費(fèi)產(chǎn)銷平衡問題的數(shù)學(xué)模型njmixbxxbxxaxxaxxxcxcxcxczijnmnnmmmnmnmnmnmmnn，, 1, 1, 0min111111111111111111產(chǎn)銷平衡問題的數(shù)學(xué)模型 銷地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343853銷量3322 1010.,j;,ixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzminzBAxijjiij43213210223332558342342467334241433231332221231211134333231242

25、3222114131211343332312423222114131211，。則：總運(yùn)費(fèi)為的物資數(shù)量，運(yùn)給銷地為從產(chǎn)地設(shè)產(chǎn)大于銷問題的數(shù)學(xué)模型 銷 地產(chǎn) 地B1B2B3B4產(chǎn) 量A1211347A2103595A378127銷 量2346 1915銷大于產(chǎn)問題的數(shù)學(xué)模型 銷地產(chǎn)地B1B2B3產(chǎn)量A148856A216241682A38162477銷量8210261 215245有最低需求問題的數(shù)學(xué)模型 銷地產(chǎn)地B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023M50最低需求3070010 160110轉(zhuǎn)運(yùn)問題ABCDGEFH發(fā)量10發(fā)量2收量3收量1收量854

26、31214134DGDEDCEDDCBCABBEBCABGHFGEFEDDGDEDCBEBCABxxxxDxxCxxxBxAxxxxxxxxxxMinz2:3:10:4432345., 08:1:HAjixxHxxxGxxFxxxxEijGHGHFGDGFGEFEFEDDEBE轉(zhuǎn)運(yùn)問題續(xù)）最優(yōu)調(diào)運(yùn)方案ABCDGEFH發(fā)量10發(fā)量2收量3收量1收量8543121413410378618課程實(shí)驗(yàn)運(yùn)輸問題的計算機(jī)求解n產(chǎn)銷平衡問題的求解產(chǎn)銷平衡問題的求解 n產(chǎn)大于銷問題的求解產(chǎn)大于銷問題的求解n銷大于產(chǎn)問題的求解銷大于產(chǎn)問題的求解n有最低需求問題的求解有最低需求問題的求解n轉(zhuǎn)運(yùn)問題的求解轉(zhuǎn)運(yùn)問題的求

27、解有最低需求問題的計算機(jī)求解“=”時有最低需求問題的計算機(jī)求解“=”時有最低需求問題的計算機(jī)求解“”時有最低需求問題的計算機(jī)求解“”時第三章 整數(shù)規(guī)劃n整數(shù)規(guī)劃問題的數(shù)學(xué)模型n整數(shù)規(guī)劃問題的求解方法n0-1型整數(shù)規(guī)劃的應(yīng)用n指派問題n整數(shù)規(guī)劃應(yīng)用案例航班計劃的制定n課程實(shí)驗(yàn)整數(shù)規(guī)劃的數(shù)學(xué)模型n整數(shù)規(guī)劃的基本概念n整數(shù)線性規(guī)劃n整數(shù)非線性規(guī)劃n純整數(shù)規(guī)劃n混合整數(shù)規(guī)劃n01規(guī)劃n托運(yùn)甲、乙兩種貨物分別采用兩種不同規(guī)格的集裝箱。每箱體積及重量等數(shù)據(jù)如下表所示。問兩種貨物各托運(yùn)多少箱，可使所獲利潤最大？貨 物體 積(米3)重 量(百 斤)利 潤(百 元)甲5220乙4510托 運(yùn)限 制2413且為整

28、數(shù)013522445102021212121x ,xxxxxxxzmax整數(shù)規(guī)劃與松弛問題的關(guān)系n整數(shù)規(guī)劃問題與其松弛問題的最優(yōu)解對比n整數(shù)規(guī)劃問題的目標(biāo)函數(shù)值不超過其松弛問題的目標(biāo)函數(shù)值 n不能采用對松弛問題最優(yōu)解取整方法得到整數(shù)規(guī)劃最優(yōu)解且為整數(shù)013522445102021212121x ,xxxxxxxzmax。不是整數(shù)規(guī)劃的可行解；為可行解，但最優(yōu)解為松弛問題的最優(yōu)解),0 , 5() 1 , 4(),0 , 4()0 , 8 . 4(整數(shù)規(guī)劃問題的求解方法分支定界法X14X15 且為整數(shù)0,70207567909040max21212121xxxxxxxxz 349)1021, 4

29、(),(0,47020756799040max*2*1211212121zxxxxxxxxxxxz3.4341)711, 5(),(0,57020756799040max*2*1211212121zxxxxxxxxxxxz 88.355)131238,131630(),(. 0,7020756799040max*2*121212121zxxxxxxxxxxz整數(shù)規(guī)劃問題的求解方法分支定界法X22X23X21X22 349)1021, 4(),(0,47020756799040max*2*1211212121zxxxxxxxxxxxz3.4341)711, 5(),(0,570207567990

30、40max*2*1211212121zxxxxxxxxxxxz340)2 , 4(),(0,247020756799040max*2*12121212121zxxxxxxxxxxxxz 4.1327)3 ,710(),(0,347020756799040max*2*12121212121zxxxxxxxxxxxxz8.7307) 1 ,949(),(0,157020756799040max*2*12121212121zxxxxxxxxxxxxz無可行解。0,257020756799040max2121212121xxxxxxxxxxz0-1整數(shù)規(guī)劃的應(yīng)用案例n某公司擬在東、西、南三區(qū)建立門市部

31、。共有七個地點(diǎn)A1，A7可供選擇。規(guī)定：在東區(qū)A1,A2,A3中至多選兩個；在西區(qū)，由A4, A5中至少選一個； 在南區(qū)，由A6, A7中至少選一個。選Ai點(diǎn)時，需投資bi元，年獲利ci元?，F(xiàn)有資金總額B元。問應(yīng)選擇哪些點(diǎn)，可使年獲利潤最大？ .7 , 1A0A1112maxjj71765432171jxBxbxxxxxxxxczjjjjjjj點(diǎn)建門市部時當(dāng)不選擇，點(diǎn)建門市部時，當(dāng)選擇0-1整數(shù)規(guī)劃的應(yīng)用某實(shí)驗(yàn)衛(wèi)星擬從下列儀器裝置中選若干件攜帶升空，要求：儀器裝置體積重量實(shí)驗(yàn)價值A(chǔ)1v1w1c1A2v2w2c2A3v3w3c3A4v4w4c4A5v5w5c5A6v6w6c6 攜帶的儀器裝置總體

32、積不超過 V，總重量不超過 W； A1與 A3中最多安裝一件； A2 與 A4中至少安裝一件； A5 與 A6或者都安裝，或者都不安裝。確定使該次科學(xué)實(shí)驗(yàn)產(chǎn)生最大的實(shí)驗(yàn)價值的裝載方案。.6, 1A0A1011maxjj654231616161jxxxxxxxVxvWxwxczjjjjjjjjjj，儀器時當(dāng)不攜帶儀器時當(dāng)攜帶0-1整數(shù)規(guī)劃的應(yīng)用某鉆井隊(duì)要從以下 10 個可供選擇的井位中確定 5 個鉆井探油，使總的鉆探費(fèi)用最小。要求：井位s1s2s3s4s5s6s7s8s9s10鉆探費(fèi)用c1c2c3c4c5c6c7c8c9c10 或者選擇 s1 和 s7，或者選擇 s8； 選擇了 s3 或 s4就

33、不能選擇 s5，反之亦然； 在 s5 ，s6 ，s7 ，s8中最多只能選擇兩個。15,min.10, 1,s0s181101101jjxxxxczjxjjjjjj井位時當(dāng)不選擇井位時當(dāng)選擇.10,1,0or121108765545371jxxxxxxxxxxxj0-1整數(shù)規(guī)劃的應(yīng)用.6, 1,0or11202132132154jxxxxxxxxxj 工程工種總工時泥工655070486070240木工404530403550170普通工708060505080170鋼筋工303528302540330利潤1.5v要求：v從工程、中最多只能挑選一項(xiàng)；v如果選擇工程或，就必須

34、選擇工程，反之亦然。3304025302835301708050506080701705035403045402407060487050655 . 22 . 15 . 125 . 1max. 6 , 1,01654321654321654321654321654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzjjjxj項(xiàng)工程時當(dāng)不選擇第項(xiàng)工程時當(dāng)選擇第0-1整數(shù)規(guī)劃的應(yīng)用擬 在 以 下 新 建 的 居 民 小 區(qū) 增 設(shè) 若 干 所 小 學(xué) 。 要 求 覆 蓋 所 有 小 區(qū) ， 至 少應(yīng) 建 多 少 所小 學(xué) 。 試建 立 該 問題 的 數(shù) 學(xué)模 型 （ 不必 求 解 ）

35、。備 選 校 址ABCDEF覆 蓋 的 居 民小 區(qū)1,5,71,2,51,3,52,4,53,64,60-1整數(shù)規(guī)劃的應(yīng)用10 xn1j1,xm1ixxaxzn1jm1iijijxijm1iij0n1jijj0ij或者上加工時種零件不在機(jī)床當(dāng)?shù)谏霞庸r種零件在機(jī)床當(dāng)?shù)?min.,;,0,1均衡?；虮M可能機(jī)床的總加工任務(wù)相等。問如何分配，使各種，為工。設(shè)加工時間分別種零件在這種機(jī)床上加臺同類型的機(jī)床，有有n21a,a,anm0-1整數(shù)規(guī)劃的應(yīng)用. n, 0ji,1,01nn, 1 , 0S1,n, 1 , 01,n, 1 , 0i , 1dmin; n, 0ji,AA,0AA, 1ijijn0

36、in0jSiSjijn0iijn0jijijn0in0jijjijiij或者對任意的非空子集時后面的不是當(dāng)緊接著村莊時后面的是當(dāng)緊接著村莊xxxjxxxzx并使總的行程最短。，使能經(jīng)過每個村莊一次，順序，問如何選定行走為的距離到。設(shè)到，最后返回莊經(jīng)過預(yù)先確定的村出發(fā)一位推銷商從居住地0iii0ijji0n10A,A,A,A,AdAAAA,A,An210-1整數(shù)規(guī)劃的應(yīng)用*。滿足時，要求條件滿足時，不要求條件，其中：。必須且只需有一個滿足個條件：設(shè)。滿足時，要求條件滿足時，要求條件，其中：則上述條件可表示為：為可以任意大的正數(shù)，令。必須且只需有一個滿足：和條件：設(shè)條件i0i1y1myyyMybx

37、axaxam, 1i,bxaxaxam1021yMy-1bxaxayMbxaxaMbxaxa2bxaxa1im21iinin2i21i1inin2i21i122221211212111222212112121110-1整數(shù)規(guī)劃的應(yīng)用*。，或，其中：中的一個值，只能取?；颍渲校簞t上述條件可表示為：為可以任意大的正數(shù)，令或321i10y1yyy7y5y3yx7530 x210yMy-1-53x2xyM2xxM53x2x2xx1i32132121212121,)()(0-1整數(shù)規(guī)劃的應(yīng)用*?；?，其中：至少滿足兩個，四個條件。或，其中：，否則則若,41,i1,0y2yyyyM1-y6xxM1-y2x

38、My12xMy15xx6xx2x2x5xx)4(10yMy-14xM1-y2xyM-1xyM2x4x1x2x)3(i4321443332112143312111212210-1整數(shù)規(guī)劃的應(yīng)用* 某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。知：某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。知：項(xiàng)目項(xiàng)目A A：從第一年到第四年每年年初需要投資，并于次年末回：從第一年到第四年每年年初需要投資，并于次年末回收本利收本利115%115%，但要求第一年投資最低金額為，但要求第一年投資最低金額為4 4萬元，第二、萬元，第二、三、四年不限；三、四年不限；項(xiàng)目項(xiàng)目B B：第三年初需要投資，到第五年末能回收本利：第三年初需

39、要投資，到第五年末能回收本利128128，但，但規(guī)定最低投資金額為規(guī)定最低投資金額為3 3萬元，最高金額為萬元，最高金額為5 5萬元；萬元；項(xiàng)目項(xiàng)目C C：第二年初需要投資，到第五年末能回收本利：第二年初需要投資，到第五年末能回收本利140%140%，但，但規(guī)定其投資額或?yàn)橐?guī)定其投資額或?yàn)? 2萬元或?yàn)槿f元或?yàn)? 4萬元或?yàn)槿f元或?yàn)? 6萬元或?yàn)槿f元或?yàn)? 8萬元。萬元。項(xiàng)目項(xiàng)目D D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%6%，此項(xiàng)投資金額不限。，此項(xiàng)投資金額不限。 該部門現(xiàn)有資金該部門現(xiàn)有資金1010萬元，問它應(yīng)如何確定給這些項(xiàng)目

40、的萬元，問它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大每年投資額，使到第五年末擁有的資金本利總額為最大? ?指派問題n平衡指派問題的數(shù)學(xué)模型n不平衡指派問題的數(shù)學(xué)模型n 求極大的指派問題的數(shù)學(xué)模型n 人員數(shù)多于工作數(shù)的指派問題的數(shù)學(xué)模型n 工作數(shù)多于人員數(shù)的指派問題的數(shù)學(xué)模型平衡指派問題的數(shù)學(xué)模型., 1, 10, 1, 1, 1, 1min., 1, 1011111mjiorxmixmjxxcznmnjmijijixijmjijmiijmimjijijij且，項(xiàng)工作名職員承擔(dān)第不分配第項(xiàng)工作名職員承擔(dān)第分配第令平衡指派問題的數(shù)學(xué)模型 施工 隊(duì)工程甲乙丙丁戊A745

41、68B121013159C10981113D1517201411E1614131815表中數(shù)據(jù)為完成工程所需時間求極大指派問題的數(shù)學(xué)模型表中數(shù)據(jù)為操作每臺機(jī)器的產(chǎn)值 機(jī)器工人ABCD甲10987乙3456丙2112丁4356人員數(shù)多于工作數(shù)的指派問題表中數(shù)據(jù)為承擔(dān)每種工作的費(fèi)用 工 人工 作甲乙丙丁戊己A373655B618427C245346D648732人員數(shù)少于工作數(shù)的指派問題表中數(shù)據(jù)為承擔(dān)每種工作的費(fèi)用，且每人最多承擔(dān)1項(xiàng)工作。 工 作工 人ABCDEF甲373655乙618427丙275346丁648732人員數(shù)少于工作數(shù)的指派問題表中數(shù)據(jù)為承擔(dān)每種工作的費(fèi)用，且每人最多可以承擔(dān)2項(xiàng)

42、工作。 工 作工 人ABCDEF甲373655乙618427丙275346丁648732整數(shù)規(guī)劃應(yīng)用案例航班計劃編制n某航空公司經(jīng)營A,B,C三個城市之間的航線，這些航線每天航班起飛與到達(dá)時間如下表所示。設(shè)飛機(jī)在機(jī)場停留的損失費(fèi)用大致與停留時間的平方成正比，而且從降落到起飛至少需2小時的準(zhǔn)備時間。指定使停留費(fèi)用損失最小的航班計劃。航班號起飛城市起飛時間到達(dá)城市到達(dá)時間101A9:00B12:00102A10:00B13:00103A15:00B18:00104A20:00C24:00105A22:00C2:00106B4:00A7:00107B11:00A14:00108B15:00A18:0

43、0109C7:00A11:00110C15:00A19:00111B13:00C18:00112B18:00C23:00113C15:00B20:00114C7:00B12:00整數(shù)規(guī)劃應(yīng)用案例航班計劃編制 A起 飛到 達(dá)A1011021031041051064964169225107361400625366410822525644141610948452916811211101962254006259 B起 飛到 達(dá)B1061071081111121012565299625361022254844576251031002894413615761136422536128948411425652

44、9962536 C起 飛到 達(dá)C109110113114104492252254910525169169251111694414411691126425625664整數(shù)規(guī)劃應(yīng)用案例航班計劃編制106102107104110101108105113111114112109103課程實(shí)驗(yàn)(3)整數(shù)規(guī)劃的計算機(jī)求解n0-1整數(shù)規(guī)劃的應(yīng)用(4)、(5)、(11)n平衡的指派問題n不平衡的指派問題綜合建模練習(xí)1）n（參見教材P20） Par公司生產(chǎn)高爾夫袋，各道生產(chǎn)工序的可用時間、兩種規(guī)格的高爾夫袋的單位加工時間以及利潤情況如下表所示。兩種袋各生產(chǎn)多少個，可使Par公司獲得最大的利潤？工序加工時間（小時

45、）可用時間（小時）標(biāo)準(zhǔn)袋高級袋切割與印染7/101630縫合1/25/6600成型12/3708檢查與包裝1/101/4135單位利潤（美元）109綜合建模練習(xí)2）背景：現(xiàn)將背景：現(xiàn)將2020噸貨物從地點(diǎn)依次經(jīng)過地點(diǎn)、噸貨物從地點(diǎn)依次經(jīng)過地點(diǎn)、運(yùn)至地點(diǎn)，在地點(diǎn)、出發(fā)時都可以且只運(yùn)至地點(diǎn)，在地點(diǎn)、出發(fā)時都可以且只能選擇鐵路、公路和航空三種運(yùn)輸方式之一，相應(yīng)的運(yùn)能選擇鐵路、公路和航空三種運(yùn)輸方式之一，相應(yīng)的運(yùn)輸成本如表所示。并且如果在相鄰兩段改變了運(yùn)輸方式，輸成本如表所示。并且如果在相鄰兩段改變了運(yùn)輸方式，還要發(fā)生額外的費(fèi)用，具體數(shù)據(jù)亦如表所示。如何選擇還要發(fā)生額外的費(fèi)用，具體數(shù)據(jù)亦如表所示。如何

46、選擇各段的運(yùn)輸方式，使總的運(yùn)輸成本最?。扛鞫蔚倪\(yùn)輸方式，使總的運(yùn)輸成本最?。?2345第1段第2段第3段第4段綜合建模練習(xí)3）n（參見教材P200某房產(chǎn)租賃公司現(xiàn)有2000千美元用于購置新的房產(chǎn)，別墅每套售價282千美元，最多可購買5套；每幢公寓樓售價400千美元。該公司每月最多可以花140小時管理新增房產(chǎn)，其中管理每套別墅每月要花4小時，管理每幢公寓樓每月要花40小時。出租后，每套別墅的年收益為10千美元，每種公寓樓的年收益為15千美元。別墅和公寓樓各購買多少套，可使全年總收益最大？綜合建模練習(xí)4-1）的總步行距離最短？機(jī)口，使所有中轉(zhuǎn)旅客間的距離，如何分配登，以及各登機(jī)口之登機(jī)口轉(zhuǎn)機(jī)的旅客

47、人數(shù)進(jìn)港航班上需要到各個個航班進(jìn)港。已知每個分鐘內(nèi)將有個登機(jī)口空閑，某機(jī)場現(xiàn)有7157各進(jìn)港航班中到各登機(jī)口轉(zhuǎn)機(jī)的旅客人數(shù)進(jìn)港航班銜接航班出港登機(jī)口12345678910111213141516171819F155108158210820540934121F2521419942322738402172F31004913444355849117944F4485410410024191245582F541199631442103512234F6124252762472364102100F73325913112237224011229綜合建模練習(xí)4-2）各登機(jī)口之間的距離進(jìn)港航班登機(jī)口出港航班登機(jī)口

48、1234567891011121314151617181931040-301040205030604070508060907090804401030-40105020603070408050906090708010704060305020401030-4010504060307040501150804070306020501040-30104020503050401490608050704060305020401030-40105020301570100609050804070306020501040-3010302017801007090608050704060305020401030-2010綜合建模練習(xí)5）背景：某航空公司以戴高樂機(jī)場作為中轉(zhuǎn)樞紐。分別來自波爾多、背景：某航空公司以戴高樂機(jī)場作為中轉(zhuǎn)樞紐。分別來自波爾多、克萊蒙克萊蒙- -費(fèi)朗、馬賽、南特、尼斯、圖盧茲的費(fèi)朗、馬賽、南特、尼斯、圖盧茲的6 6架相同