工程碩士運(yùn)籌學(xué)及重點(diǎn)方案

1工程碩士運(yùn)籌學(xué)

內(nèi)蒙古工業(yè)大學(xué)管理學(xué)院

1工程碩士運(yùn)籌學(xué)

內(nèi)蒙古工業(yè)大學(xué)管理學(xué)院

課程內(nèi)容緒論線性規(guī)劃基礎(chǔ)線性規(guī)劃的圖解法、用Excel解LP問題整數(shù)規(guī)劃運(yùn)輸問題目標(biāo)規(guī)劃圖論動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)計(jì)劃技術(shù)2課程內(nèi)容緒論23第0章緒論

IntroductionstoOperationsResearch

3第0章緒論

IntroductionstoOperat運(yùn)籌學(xué)的實(shí)用價(jià)值公司應(yīng)用問題收益/效果惠普公司預(yù)測消費(fèi)者的購買行為，從而優(yōu)化庫存2009至2011年，創(chuàng)造了1.17億美元的收益中國工商銀行銀行網(wǎng)點(diǎn)的城市布局問題2006至2011年，蘇州因此增加了10.4億美元的存款I(lǐng)HG洲際酒店集團(tuán)解決酒店房間的定價(jià)問題2011年增加1.45億美元的收益，并預(yù)計(jì)推廣后未來每年將帶來4億美元的收益HubGroup哈勃貨運(yùn)集團(tuán)提高場地管理和集裝箱分配2008年收益增加了3%，獲得了1,100萬美元的凈匯報(bào)Petrobras優(yōu)化直升飛機(jī)在海上石油平臺(tái)之間的飛行路線每年節(jié)省超過2千萬美元4

ZARA（全球1500家門店）、P&G（15億）運(yùn)籌學(xué)的實(shí)用價(jià)值公司應(yīng)用問題收益/效果惠普公司預(yù)測消費(fèi)者的購5運(yùn)籌學(xué)學(xué)科特點(diǎn)1-

科學(xué)性它是在科學(xué)方法論的指導(dǎo)下通過一系列規(guī)范化步驟。5運(yùn)籌學(xué)學(xué)科特點(diǎn)1-科學(xué)性6運(yùn)籌學(xué)學(xué)科特點(diǎn)2-實(shí)踐性運(yùn)籌學(xué)以實(shí)際問題為分析對(duì)象；分析結(jié)果必須用于指導(dǎo)實(shí)際系統(tǒng)的運(yùn)行。適應(yīng)性和魯棒性Robustness，原是統(tǒng)計(jì)學(xué)中的一個(gè)專門術(shù)語，20世紀(jì)70年代初開始在控制理論的研究中流行起來，用以表征控制系統(tǒng)對(duì)特性或參數(shù)擾動(dòng)的不敏感性。即當(dāng)應(yīng)用問題的背景受到一定程度的干擾時(shí)，最優(yōu)解能夠繼續(xù)正常運(yùn)行的程度。6運(yùn)籌學(xué)學(xué)科特點(diǎn)2-實(shí)踐性7運(yùn)籌學(xué)學(xué)科特點(diǎn)3-系統(tǒng)性用系統(tǒng)的觀點(diǎn)來分析研究對(duì)象，通過協(xié)調(diào)各組成部分之間的關(guān)系和利害沖突，使整個(gè)系統(tǒng)達(dá)到最優(yōu)狀態(tài)。實(shí)際問題的多目標(biāo)“天性”，各目標(biāo)沒有統(tǒng)一的度量標(biāo)準(zhǔn)。7運(yùn)籌學(xué)學(xué)科特點(diǎn)3-系統(tǒng)性8運(yùn)籌學(xué)學(xué)科特點(diǎn)4-優(yōu)化方案強(qiáng)調(diào)是最優(yōu)的解決方案，而不是任意的一個(gè)可行方案，或者只是對(duì)現(xiàn)狀的“改進(jìn)”方案；當(dāng)研究問題從數(shù)學(xué)分析上存在多個(gè)或無窮最優(yōu)解時(shí)，不刻意去搜索出所有最優(yōu)解，而是只需找出其中一個(gè)最優(yōu)解；當(dāng)研究問題過于復(fù)雜時(shí)，運(yùn)籌學(xué)更傾向于搜索出一個(gè)“效率解”。8運(yùn)籌學(xué)學(xué)科特點(diǎn)4-優(yōu)化方案9運(yùn)籌學(xué)學(xué)科特點(diǎn)5-

綜合性運(yùn)籌學(xué)研究是一種綜合性的研究，它涉及問題的方方面面，應(yīng)用多學(xué)科的知識(shí)，因此，要由一個(gè)各方面的專家組成的小組來完成。9運(yùn)籌學(xué)學(xué)科特點(diǎn)5-綜合性運(yùn)籌學(xué)求解問題的一般思路1.明確問題，收集數(shù)據(jù)邊界、目標(biāo)量化、變量、參數(shù)、約束2.建立模型，數(shù)學(xué)模型：模型檢驗(yàn)3.選取方法，進(jìn)行求解：遺傳算法等4.驗(yàn)證方案，實(shí)施方案5.方案程序化，模塊化6.方案實(shí)施，效果分析10運(yùn)籌學(xué)求解問題的一般思路1.明確問題，收集數(shù)據(jù)10運(yùn)籌學(xué)求解問題的一般思路11運(yùn)籌學(xué)求解問題的一般思路1112第1章線性規(guī)劃基礎(chǔ)(IntroductiontoLinearProgramming)12第1章線性規(guī)劃基礎(chǔ)目標(biāo)1.常見線性規(guī)劃問題的數(shù)學(xué)建模思路2.建模的適用范圍3.“解”的概念4.圖解法5.EXCEL求解一般線性規(guī)劃問題（練習(xí)）13目標(biāo)1.常見線性規(guī)劃問題的數(shù)學(xué)建模思路1314線性規(guī)劃的定義在滿足一組線性約束條件（等式或不等式）的前提下，使得某一個(gè)線性目標(biāo)函數(shù)取得極值（最大值或最小值）。這類問題的模型及其優(yōu)化求解技術(shù)，被統(tǒng)稱為線性規(guī)劃(LinearProgramming,LP)。Inmathematics,LPproblemsareoptimizationproblemsinwhichtheobjectivefunction

andtheconstraints

arealllinear.14線性規(guī)劃的定義在滿足一組線性約束條件（等式或不等式）的前線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃問題的一般模型15線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃問題的一般模型15線性規(guī)劃數(shù)學(xué)模型模型特點(diǎn)1-所有表達(dá)式均為線性表達(dá)式2-目標(biāo)為求目標(biāo)函數(shù)Z的最大值(max)或最小值(min)3-約束條件為”≥/≤/=”，沒有”>/<”！4-通常要求決策變量取值非負(fù)16線性規(guī)劃數(shù)學(xué)模型模型特點(diǎn)1617應(yīng)用問題示例(1)-生產(chǎn)計(jì)劃

F公司每周根據(jù)原材料M1和M2的采購數(shù)量來安排其產(chǎn)品A、B和C的生產(chǎn)計(jì)劃。問：這3種產(chǎn)品各應(yīng)生產(chǎn)多少，能使F公司獲得最大的利潤？單位消耗產(chǎn)品A產(chǎn)品B產(chǎn)品C可用資源原材料M1845320原材料M2221100單位產(chǎn)品利潤54217應(yīng)用問題示例(1)-生產(chǎn)計(jì)劃F公司每周根據(jù)原材料M1和應(yīng)用問題示例(2)-生產(chǎn)計(jì)劃A公司用M1,M2,M3和M4四種原材料，生產(chǎn)產(chǎn)品P1,P2和P3。這三種產(chǎn)品由這四種原材料混合而成（產(chǎn)品重量為四種原材料重量之和）。18產(chǎn)品原材料配方加工成本市場售價(jià)P1M1：不超過產(chǎn)品重量的35%301200M2：不少于產(chǎn)品重量的45%M3：不超過產(chǎn)品重量的50%M4：產(chǎn)品重量的20%P2M1：不超過產(chǎn)品重量的60%40850M2：不少于產(chǎn)品重量的20%M4：產(chǎn)品重量的10%P3M1：不超過產(chǎn)品重量的75%50900應(yīng)用問題示例(2)-生產(chǎn)計(jì)劃A公司用M1,M2,M3和M4四應(yīng)用問題示例(2)原材料M3和M4采購量超過市場供應(yīng)總量的一半。采購預(yù)算費(fèi)用為25萬元人民幣。問：根據(jù)產(chǎn)品的市場價(jià)格以及原材料價(jià)格，公司應(yīng)如何采購以獲得最多的利潤？19原材料M1M2M3M4市場供給300200400300市場價(jià)格300600400500應(yīng)用問題示例(2)原材料M3和M4采購量超過市場供應(yīng)總量的一應(yīng)用問題示例(2)建模思路1--20應(yīng)用問題示例(2)建模思路1--20應(yīng)用問題示例(2)正確的建模方法--21應(yīng)用問題示例(2)正確的建模方法--21應(yīng)用問題示例(2)22應(yīng)用問題示例(2)22應(yīng)用問題示例(3)-財(cái)務(wù)計(jì)劃某集團(tuán)公司未來6年年初的現(xiàn)金需求（萬元）如下所示。為此，公司決定在今年年底一次性劃撥一筆資金，未來6年不再劃撥。23年份123456現(xiàn)金350405355260215230應(yīng)用問題示例(3)-財(cái)務(wù)計(jì)劃某集團(tuán)公司未來6年年初的現(xiàn)金需求應(yīng)用問題示例(3)公司可以通過多種投資形式減少資金的需求：1-銀行一年期的定期存款，年利率為3%；2-國債（只能在第1年年初購買；國債的實(shí)際購買價(jià)格要高于其票面價(jià)格，且只能在到期日按票面價(jià)格收回本金）問：集團(tuán)公司最少需要?jiǎng)潛芏嗌儋Y金，并如何投資，才能滿足未來6年的現(xiàn)金需求？24債券類型票面價(jià)格實(shí)際購買價(jià)格年利率到期年限110,00012,0007.84210,00014,30010.75應(yīng)用問題示例(3)公司可以通過多種投資形式減少資金的需求：2應(yīng)用問題示例(3)由于6年內(nèi)不再追加投資，因此6年內(nèi)的投資（銀行定期存款方式）必然不能超過當(dāng)年現(xiàn)金需求的余額。并且，由于投資總能夠獲得更多的回報(bào)（103%），所以投資等于當(dāng)年現(xiàn)金需求的余額！25應(yīng)用問題示例(3)由于6年內(nèi)不再追加投資，因此6年內(nèi)的投資（應(yīng)用問題示例(3)采用表格形式更加直觀展示出投資與回報(bào)。年末的收益可以作為下一年年初的投資?；貓?bào)第1年年末第2年年末第3年年末第4年年末第5年年末第6年年末存款1.031.031.031.031.031.03債券10.0780.0780.0781.078債券20.1070.1070.1070.1071.10726應(yīng)用問題示例(3)采用表格形式更加直觀展示出投資與回報(bào)?；貓?bào)應(yīng)用問題示例(3)27回報(bào)第1年年末第2年年末第3年年末第4年年末第5年年末第6年年末存款1.031.031.031.031.031.03債券10.0780.0780.0781.078債券20.1070.1070.1070.1071.107應(yīng)用問題示例(3)27回報(bào)第1年第2年第3年第4年第5年第6應(yīng)用問題示例(3)完整問題模型如下：28應(yīng)用問題示例(3)完整問題模型如下：28應(yīng)用問題示例(4)-生產(chǎn)計(jì)劃N公司生產(chǎn)兩種產(chǎn)品P1和P2，這2種產(chǎn)品都是由組件C1,C2和C3各1件裝配而成。需求為1600件P1和1000件P2。共有100個(gè)正常工時(shí)和最多60個(gè)加班工時(shí)，每個(gè)加班工時(shí)將額外增加12元的運(yùn)營成本。問：如何安排生產(chǎn)和外購，才是最經(jīng)濟(jì)？29組件生產(chǎn)工時(shí)生產(chǎn)成本外購成本C11.51.01.2C2產(chǎn)品P14.08.08.5產(chǎn)品P23.06.07.0C3產(chǎn)品P12.01.52.0產(chǎn)品P23.01.82.1應(yīng)用問題示例(4)-生產(chǎn)計(jì)劃N公司生產(chǎn)兩種產(chǎn)品P1和P2，這應(yīng)用問題示例(4)根據(jù)問題描述，可以定義自行生產(chǎn)和外購的組件數(shù)量為決策變量。并且，外購組件的數(shù)量與生產(chǎn)能力也有關(guān)，因此需要定義實(shí)際加班工時(shí)為決策變量，即：30應(yīng)用問題示例(4)根據(jù)問題描述，可以定義自行生產(chǎn)和外購的組件應(yīng)用問題示例(4)31應(yīng)用問題示例(4)31應(yīng)用問題示例(5)-運(yùn)輸與分銷運(yùn)輸與分銷問題問：如何安排物流路線，實(shí)現(xiàn)總運(yùn)輸成本最小。32應(yīng)用問題示例(5)-運(yùn)輸與分銷運(yùn)輸與分銷問題32應(yīng)用問題示例(5)定義決策變量為各條路線上的運(yùn)輸量，各變量對(duì)應(yīng)的路線如下所示。33應(yīng)用問題示例(5)定義決策變量為各條路線上的運(yùn)輸量，各變量對(duì)應(yīng)用問題示例(5)對(duì)于此類以圖形方式給出的物流問題，存在以下函數(shù)關(guān)系，即圖中每個(gè)節(jié)點(diǎn)，都必須滿足“輸入=輸出”。34應(yīng)用問題示例(5)對(duì)于此類以圖形方式給出的物流問題，存在以下應(yīng)用問題示例(5)源頭節(jié)點(diǎn)“工廠1～3”，關(guān)系為“產(chǎn)量+運(yùn)入量=運(yùn)出量”。35應(yīng)用問題示例(5)源頭節(jié)點(diǎn)“工廠1～3”，關(guān)系為“產(chǎn)量+應(yīng)用問題示例(5)中間節(jié)點(diǎn)“分銷中心”，關(guān)系為“運(yùn)入量=運(yùn)出量”。36應(yīng)用問題示例(5)中間節(jié)點(diǎn)“分銷中心”，關(guān)系為“運(yùn)入量=運(yùn)出應(yīng)用問題示例(5)終止節(jié)點(diǎn)“倉庫1～2”，關(guān)系為“運(yùn)入量=運(yùn)出量+需求量”。37應(yīng)用問題示例(5)終止節(jié)點(diǎn)“倉庫1～2”，關(guān)系為“運(yùn)入量應(yīng)用問題示例(6)-套裁下料問題某建筑公司需要鋼管規(guī)格和數(shù)量分別為：3m的600根、4m的300根、5m的200根。如果只能選擇購入長度為11m的鋼管自行切割，M公司至少應(yīng)采購多少根11m的鋼管？38應(yīng)用問題示例(6)-套裁下料問題某建筑公司需要鋼管規(guī)格和數(shù)量應(yīng)用問題示例(6)某建筑公司需要鋼管規(guī)格和數(shù)量分別為：3m的600根、4m的300根、5m的200根。如果只能選擇購入長度為11m的鋼管自行切割，M公司至少應(yīng)采購多少根11m的鋼管？39應(yīng)用問題示例(6)某建筑公司需要鋼管規(guī)格和數(shù)量分別為：3m的應(yīng)用問題示例(6)40應(yīng)用問題示例(6)40應(yīng)用問題示例(6)思考題：如果目標(biāo)函數(shù)改為“如果購入這些長度為11m的鋼管自行切割，RE公司應(yīng)如何切割廢料最少？”41應(yīng)用問題示例(6)思考題：如果目標(biāo)函數(shù)改為“如果購入這些長度42線性規(guī)劃模型的假設(shè)條件比例性假定：要求目標(biāo)函數(shù)值、約束條件左端取值與決策變量的取值呈嚴(yán)格的比例關(guān)系。42線性規(guī)劃模型的假設(shè)條件比例性假定：要求目標(biāo)函數(shù)值、約束條線性規(guī)劃模型的假設(shè)條件43線性規(guī)劃模型的假設(shè)條件4344線性規(guī)劃問題的標(biāo)準(zhǔn)圖解法對(duì)于只包含2個(gè)變量的線性規(guī)劃問題，可以通過標(biāo)準(zhǔn)圖解法來求解。其解題步驟為：44線性規(guī)劃問題的標(biāo)準(zhǔn)圖解法對(duì)于只包含2個(gè)變量的線性規(guī)劃問題45標(biāo)準(zhǔn)圖解法示例1用標(biāo)準(zhǔn)圖解法求下面的線性規(guī)劃問題（例1-8）45標(biāo)準(zhǔn)圖解法示例1用標(biāo)準(zhǔn)圖解法求下面的線性規(guī)劃問題（例1-標(biāo)準(zhǔn)圖解法示例146標(biāo)準(zhǔn)圖解法示例146標(biāo)準(zhǔn)圖解法示例2應(yīng)用標(biāo)準(zhǔn)圖解法求解線性規(guī)劃問題（例1-9）47標(biāo)準(zhǔn)圖解法示例2應(yīng)用標(biāo)準(zhǔn)圖解法求解線性規(guī)劃問題（例1-9）4標(biāo)準(zhǔn)圖解法示例248標(biāo)準(zhǔn)圖解法示例24849線性規(guī)劃問題的重要推論1-如果線性規(guī)劃問題的可行域非空且有界，那么線性規(guī)劃問題一定有最優(yōu)解；2-如果線性規(guī)劃問題的可行域無界，那么該問題可能有無界解；3-如果線性規(guī)劃問題的最優(yōu)解在可行域的兩個(gè)頂點(diǎn)上同時(shí)得到，那么這兩個(gè)頂點(diǎn)連線上的所有點(diǎn)都是最優(yōu)解（有無窮多最優(yōu)解）；4-如果線性規(guī)劃問題的可行域?yàn)榭眨馕吨摼€性規(guī)劃問題無可行解。49線性規(guī)劃問題的重要推論1-如果線性規(guī)劃問題的可行域非空50簡化的圖解法對(duì)于可行域?yàn)榉忾]凸多邊形的兩變量線性規(guī)劃問題，可以采用簡化的圖解法求解：只需要窮舉出可行域的所有頂點(diǎn)，計(jì)算每一個(gè)頂點(diǎn)的目標(biāo)函數(shù)值，就可以找出最優(yōu)解。50簡化的圖解法對(duì)于可行域?yàn)榉忾]凸多邊形的兩變量線性規(guī)劃問題簡化的圖解法示例1線性規(guī)劃問題（例1-8）51頂點(diǎn)坐標(biāo)目標(biāo)函數(shù)值X1X2A000B4012C4327D2636E0630簡化的圖解法示例1線性規(guī)劃問題（例1-8）51頂點(diǎn)坐標(biāo)目標(biāo)X52Excel求解線性規(guī)劃問題“規(guī)劃求解”工具主界面52Excel求解線性規(guī)劃問題“規(guī)劃求解”工具主界面Excel求解LP問題示例1線性規(guī)劃問題（例1-8）53Excel求解LP問題示例1線性規(guī)劃問題（例1-8）53練習(xí)題-圖解以下線性規(guī)劃問題54練習(xí)題-圖解以下線性規(guī)劃問題545555某手工作坊生產(chǎn)的竹制座椅中需要用到3種規(guī)格楠竹片，每張椅子需要長度為60cm、40cm

和30cm的楠竹片2、6和2片?？梢栽谑袌錾喜少忂@些規(guī)格的現(xiàn)貨，也可以將作坊倉庫中長度

為110cm的楠竹片切割成所需的規(guī)格，但每切割1次會(huì)發(fā)生1cm的長度損耗。

問：如果要制作100張竹制座椅，該作坊的倉庫中至少要有多少條長度為110cm的楠竹片，

才不用去市場上采購？試建立本問題的線性規(guī)劃模型。

56某手工作坊生產(chǎn)的竹制座椅中需要用到3種規(guī)格楠竹片，每張椅子需5757585859第2章整數(shù)規(guī)劃(IntegerLinearProgramming)59第2章整數(shù)規(guī)劃基本概念線性規(guī)劃模型中增加了決策變量的整數(shù)約束，這類數(shù)學(xué)規(guī)劃問題被稱為整數(shù)規(guī)劃(IntegerLinearProgramming,ILP)問題。整數(shù)規(guī)劃模型雖然只是在線性規(guī)劃模型中增加了決策變量的整數(shù)約束，但是其求解過程卻變得非常復(fù)雜。（簡單的四舍五入？？？）車輛調(diào)度、人員安排、產(chǎn)品產(chǎn)量60基本概念線性規(guī)劃模型中增加了決策變量的整數(shù)約束，這類數(shù)學(xué)規(guī)劃基本概念根據(jù)全部還是部分決策變量必須滿足整數(shù)約束，整數(shù)規(guī)劃問題可分為兩類：純整數(shù)規(guī)劃（PureIntegerProgramming,PIP）混合整數(shù)規(guī)劃（MixedIntegerProgramming,MIP）根據(jù)整數(shù)變量取值的范圍，整數(shù)規(guī)劃問題還可分為：一般整數(shù)規(guī)劃-整數(shù)變量的取值可以是任意非負(fù)整數(shù)0-1整數(shù)規(guī)劃（BinaryIntegerProgramming,BIP）-要求決策變量只能取值0或者161基本概念根據(jù)全部還是部分決策變量必須滿足整數(shù)約束，整數(shù)規(guī)劃問基本概念62一般整數(shù)規(guī)劃問題的數(shù)學(xué)模型基本概念62一般整數(shù)規(guī)劃問題的數(shù)學(xué)模型基本概念630-1整數(shù)規(guī)劃問題的數(shù)學(xué)模型基本概念630-1整數(shù)規(guī)劃問題的數(shù)學(xué)模型應(yīng)用問題建模設(shè)施布點(diǎn)問題某市在其5個(gè)規(guī)劃片區(qū)規(guī)劃消防站設(shè)點(diǎn)，要求任意一個(gè)片區(qū)發(fā)生火警時(shí)，本片區(qū)或來自其它片區(qū)的消防車可以在15分鐘內(nèi)趕到。雖然在各片區(qū)各設(shè)一個(gè)消防站可以解決此問題，但為提高資源利用率，市政府提出消防站數(shù)量應(yīng)盡可能少。64應(yīng)用問題建模設(shè)施布點(diǎn)問題64應(yīng)用問題建模背包問題（0-1）某家庭計(jì)劃自駕野外露營，出發(fā)前需考慮攜帶的物品，各物品的壓縮體積及重要程度如表所示。由于其自駕車最大容納的物品體積為650升，不可能所有物品都能裝入車中。問：應(yīng)選擇哪些物品出行？65應(yīng)用問題建模背包問題（0-1）65應(yīng)用問題建模指派問題有5項(xiàng)任務(wù)需要5個(gè)員工獨(dú)立完成，由于能力差異，不同員工完成同一任務(wù)的執(zhí)行成本不同。下表給出了員工i完成任務(wù)j的執(zhí)行成本cij。問：如何指派任務(wù)可以最經(jīng)濟(jì)地完成各項(xiàng)任務(wù)。66應(yīng)用問題建模指派問題66應(yīng)用問題建模將n項(xiàng)任務(wù)分配給n個(gè)人，約定每人只能完成一項(xiàng)工作，每項(xiàng)工作也只能由一個(gè)人來完成，但由于每個(gè)人能力各不相同，完成各項(xiàng)工作的收益和成本不同。根據(jù)不同的問題背景，可要求得到總利潤最大或總成本最小的指派方案。這類問題在運(yùn)籌學(xué)中被稱為一種專門的問題：指派問題(AssignmentProblem)。67應(yīng)用問題建模將n項(xiàng)任務(wù)分配給n個(gè)人，約定每人只能完成一項(xiàng)工作應(yīng)用問題建模68定義0-1變量xij(i,j=1,…,n)表示第i個(gè)人是否被指派完成第j項(xiàng)任務(wù)（0代表不指派，1代表指派），則指派問題的數(shù)學(xué)模型為：應(yīng)用問題建模68定義0-1變量xij(i,j=1,…,n)表應(yīng)用問題建模含有互斥項(xiàng)目的計(jì)劃1.如果攜帶食物，就必須同時(shí)攜帶野外廚具和洗漱用品；2.通信設(shè)備和應(yīng)急醫(yī)療用品至少要攜帶1件；3.帳篷和防曬防雨最多只能選擇1項(xiàng)；4.野外廚具、攝影器材和通信設(shè)備最多選2項(xiàng)。69應(yīng)用問題建模含有互斥項(xiàng)目的計(jì)劃69應(yīng)用問題建模含有互斥約束條件的計(jì)劃某公司用兩種原料E1和E2生產(chǎn)A、B兩種產(chǎn)品，生產(chǎn)過程均需經(jīng)過甲、乙兩道工序。甲、乙兩道工序又各可以采取2種生產(chǎn)工藝。甲工序可以混合使用甲1和甲2兩種工藝，而乙工序只能在乙1和乙2中選擇其中一種工藝。問：該公司應(yīng)如何安排生產(chǎn)可使利潤最大？70應(yīng)用問題建模含有互斥約束條件的計(jì)劃70在建模中對(duì)互斥的約束處理時(shí)，可以引入Mi來實(shí)現(xiàn)使某個(gè)約束條件有效或者冗余，其中Mi為任意大的正數(shù)。71在建模中對(duì)互斥的約束處理時(shí)，可以引入Mi來實(shí)現(xiàn)使某個(gè)約束條件固定成本問題某工廠用兩條生產(chǎn)線??1和??2生產(chǎn)兩種產(chǎn)品A和B。這兩條生產(chǎn)線每個(gè)月的額定工時(shí)分別為600和800小時(shí)，生產(chǎn)線??1的生產(chǎn)率為產(chǎn)品A60件/小時(shí)或產(chǎn)品B45件/小時(shí)，生產(chǎn)線??2的生產(chǎn)率為產(chǎn)品A35件/小時(shí)或產(chǎn)品B40件/小時(shí)；產(chǎn)品A和B的單位售價(jià)分別為12元/件和16元/件，生產(chǎn)產(chǎn)品A和B的固定成本分別為60000元和80000元。

問：應(yīng)如何安排生產(chǎn)可實(shí)現(xiàn)利潤最大化？試建立本問題的混合整數(shù)規(guī)劃模72固定成本問題某工廠用兩條生產(chǎn)線??1和??2生產(chǎn)兩種產(chǎn)品A和1）決策變量的定義：因?yàn)楹泄潭ǔ杀镜膯栴}，所以某產(chǎn)品的產(chǎn)量X和是否生產(chǎn)該產(chǎn)品的決策Y必須分別定義，而且它們必須是聯(lián)動(dòng)的，即如果某產(chǎn)品的產(chǎn)量X大于0，那么Y必須為1；而產(chǎn)品的產(chǎn)量X為0時(shí)，Y必須為0.否則，就有可能出現(xiàn)未生產(chǎn)產(chǎn)品X卻減去了固定成本的問題，或者生產(chǎn)了卻未減去固定成本的問題。這類問題必須引入任意大的正數(shù)M。731）決策變量的定義：因?yàn)楹泄潭ǔ杀镜膯栴}，所以某產(chǎn)品的產(chǎn)量2）正數(shù)M的引入X≤M?Y其中M為任意大的正數(shù)，即，只要Y=0，則X必須為0，Y=1時(shí)，X可以取任意正整數(shù)。742）正數(shù)M的引入74所以，上題的決策變量定義如下：75所以，上題的決策變量定義如下：757676分枝定界法分枝定界技術(shù)是一種求解優(yōu)化問題的通用思想，其邏輯思路是：把原始問題分解成若干個(gè)足夠小的可以直接求解的子問題，此為分枝過程(Branching)；對(duì)于每個(gè)子集及其對(duì)應(yīng)的子問題，考察其最優(yōu)解是否足夠好―是否可能包含原始問題的最優(yōu)解，此為定界過程(Bounding)；結(jié)束某些子問題的分枝過程，并根據(jù)定界過程的結(jié)果，放棄那些不可能包含原始問題最優(yōu)解的子集及子問題，此為剪枝過程(Fathoming)。77分枝定界法分枝定界技術(shù)是一種求解優(yōu)化問題的通用思想，其邏輯思割平面法78割平面法78習(xí)題1某大型社區(qū)臨街的中式快餐店每天的營業(yè)時(shí)間為8:00到24:00，根據(jù)社區(qū)居民對(duì)早餐、中餐、晚餐和夜宵的需求不同，一天中不同時(shí)段對(duì)服務(wù)員的需求如圖所示。

79習(xí)題1某大型社區(qū)臨街的中式快餐店每天的營業(yè)時(shí)間為8:00到2該店的員工分為兩類。第一類是正式員工，分別在3個(gè)8小時(shí)時(shí)段上班：8:00-16:00、12:00-

20:00，以及16:00-

24:00，其工作時(shí)薪為14元/小時(shí)，且規(guī)定各時(shí)段正式員工數(shù)量不能少于3人；第二類是鐘點(diǎn)工，可在8:00到24:00的任意時(shí)間工作，其工作時(shí)薪為12元/小時(shí)。

問：應(yīng)如何雇用正式員工和鐘點(diǎn)工，可在人力資源成本最小的基礎(chǔ)上滿足需求？試建立本問題的整數(shù)規(guī)劃模型。

80該店的員工分為兩類。第一類是正81818282習(xí)題2某公司計(jì)劃在東、西、南三個(gè)地區(qū)建立銷售網(wǎng)點(diǎn)，總共有7個(gè)備選地點(diǎn)????(??=1,···,7)可供選擇?，F(xiàn)要求所設(shè)立的銷售網(wǎng)點(diǎn)必須滿足以下條件：

?在東部地區(qū)，??1,??2,??3三個(gè)備選地點(diǎn)中至多選擇兩個(gè)地點(diǎn)設(shè)立銷售網(wǎng)點(diǎn)；

?在西部地區(qū)，??4,??5兩個(gè)備選地點(diǎn)中至少選擇一個(gè)地點(diǎn)設(shè)立銷售網(wǎng)點(diǎn)；

?在南部地區(qū)，??6,??7兩個(gè)備選地點(diǎn)只能選一個(gè)設(shè)立銷售網(wǎng)點(diǎn)；

?出于市場環(huán)境的考慮，如果方案中選擇了??2地點(diǎn)，必須選擇在??5同時(shí)設(shè)立銷售網(wǎng)點(diǎn)。若在備選地點(diǎn)????設(shè)立銷售網(wǎng)點(diǎn)需要投資????萬元，每年可獲得利潤????萬元。問：如果總投資預(yù)算為B萬元，在哪些備選地點(diǎn)設(shè)立網(wǎng)點(diǎn)可獲得最多的利潤？試建立本問題的數(shù)學(xué)模型。

83習(xí)題2某公司計(jì)劃在東、西、南三個(gè)地區(qū)建立銷售網(wǎng)點(diǎn)，總共有7個(gè)8484習(xí)題3某短途航空公司有10條聯(lián)飛路線，可經(jīng)停9個(gè)城市，下表給出了這10條飛行路線經(jīng)停的城市和飛行總小時(shí)數(shù)（單位：小時(shí)）。

試從這10條路線中選擇3條路線，既能夠滿足飛行總時(shí)間最少的要求，又能夠經(jīng)停9個(gè)城市

至少1次。給出本問題的0-1整數(shù)規(guī)劃模型。

85習(xí)題3某短途航空公司有10條聯(lián)飛路線，可經(jīng)停9個(gè)城市，下表給8686則其目標(biāo)函數(shù)為：Min（Z）=？87878888習(xí)題4某小提琴手作坊根據(jù)顧客提出的定制需求生產(chǎn)小提琴，價(jià)格和固定成本因定制需求而異。由于作坊的熟練技師有限(12人)，該手工作坊只能挑選部分訂單，甚至只能部分完成訂單所要求的數(shù)量。目前，作坊收到來自3家交響樂隊(duì)的小提琴訂單，下表給出了與此訂單相關(guān)的制作成本和價(jià)格（單位：元）。問：各訂單各應(yīng)接受多少臺(tái)，可獲得最多的利潤？試建立本問題的整數(shù)規(guī)劃模型。

89習(xí)題4某小提琴手作坊根據(jù)顧客提出的定制需求生產(chǎn)小90909191習(xí)題5某工廠生產(chǎn)A和B兩種型號(hào)的產(chǎn)品，其生產(chǎn)過程須經(jīng)過甲、乙、丙三個(gè)流水線車間加工，其中，乙車間有兩條加工效率不同的流水線乙1和乙2。已知乙車間的兩條流水線只能任選一條使用，問：如何安排生產(chǎn)可獲得最大的利潤。建立本問題的整數(shù)規(guī)劃模型。92習(xí)題5某工廠生產(chǎn)A和B兩種型號(hào)的產(chǎn)品，其生產(chǎn)過程須經(jīng)過甲、乙939394第5章運(yùn)輸問題(TransportationProblems)94第5章運(yùn)輸問題基本概念將某種物資從若干個(gè)產(chǎn)地運(yùn)輸?shù)搅硗馊舾蓚€(gè)銷地，要求總運(yùn)費(fèi)最小的問題，這一類問題及其衍生問題統(tǒng)稱為運(yùn)輸問題(TransportationProblem)。95基本概念將某種物資從若干個(gè)產(chǎn)地運(yùn)輸?shù)搅硗馊舾蓚€(gè)銷地，要求總運(yùn)引例FreshFruit公司旗下有3個(gè)蘋果種植基地，預(yù)計(jì)年產(chǎn)量分別為75、125和100噸，近期該公司與4個(gè)不同地區(qū)的客戶簽訂了今年的蘋果供應(yīng)合同，其銷量分別80、65、70和85噸。由于交通條件差異，從3個(gè)基地到4個(gè)客戶所在地的單位運(yùn)費(fèi)不同，其運(yùn)價(jià)表如表所示。96引例FreshFruit公司旗下有3個(gè)蘋果種植基地，預(yù)計(jì)年產(chǎn)運(yùn)輸問題的數(shù)學(xué)模型97運(yùn)輸問題通常為：從m個(gè)產(chǎn)地向n個(gè)銷地運(yùn)輸某種物資，產(chǎn)地i到銷地j的單位運(yùn)費(fèi)是cij（呈比例關(guān)系），產(chǎn)地i的產(chǎn)量是ai，銷地j的銷量是bj，要求找到使得總運(yùn)費(fèi)最小的運(yùn)輸方案。當(dāng)問題滿足總產(chǎn)量與總銷量相等，這類問題稱為標(biāo)準(zhǔn)運(yùn)輸問題，或者產(chǎn)銷平衡運(yùn)輸問題。運(yùn)輸問題的數(shù)學(xué)模型97運(yùn)輸問題通常為：從m個(gè)產(chǎn)地向n個(gè)銷地運(yùn)運(yùn)輸問題的數(shù)學(xué)模型標(biāo)準(zhǔn)運(yùn)輸問題的數(shù)學(xué)模型為：98運(yùn)輸問題的數(shù)學(xué)模型標(biāo)準(zhǔn)運(yùn)輸問題的數(shù)學(xué)模型為：98標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法作為一種特殊的線性規(guī)劃問題，標(biāo)準(zhǔn)運(yùn)輸問題模型并不包含天然的基變量和初始基本可行解，求解時(shí)需要在每個(gè)等式中引入人工變量，計(jì)算較為煩瑣。對(duì)于標(biāo)準(zhǔn)運(yùn)輸問題，在某種特殊形式的表格上來應(yīng)用單純形法，可使求解過程大大簡化，這種方法叫作運(yùn)輸問題的表上作業(yè)法。需特別強(qiáng)調(diào)的是，用表上作業(yè)法求解運(yùn)輸問題，產(chǎn)銷平衡是一個(gè)基本前提。99標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法作為一種特殊的線性規(guī)劃問題，標(biāo)準(zhǔn)運(yùn)輸標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法解題步驟：1-初始化給出初始基本可行方案；2-迭代第1步基本可行方案的最優(yōu)判定，判斷當(dāng)前基本可行方案是否最優(yōu)。如果不是，進(jìn)入第2步；第2步基本可行方案的改進(jìn)，然后返回第1步；100標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法解題步驟：100標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題作業(yè)表/產(chǎn)銷平衡表101標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題作業(yè)表/產(chǎn)銷平衡表101標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法102西北角法從作業(yè)表的西北角往東南角逐步填寫運(yùn)輸量。標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法102西北角法西北角法示例1103西北角法示例1103西北角法示例1104西北角法示例1104標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法105最小元素法按照單位運(yùn)費(fèi)由低到高的次序來選擇每次迭代中指派運(yùn)輸量的單元格。標(biāo)準(zhǔn)運(yùn)輸問題的表上作業(yè)法105最小元素法最小元素法示例1106最小元素法示例1106最小元素法示例1107最小元素法示例1107產(chǎn)銷不平衡的運(yùn)輸問題示例108產(chǎn)銷不平衡的運(yùn)輸問題示例108轉(zhuǎn)運(yùn)問題(1)確定標(biāo)準(zhǔn)運(yùn)輸問題中的產(chǎn)地和銷地：轉(zhuǎn)運(yùn)點(diǎn)既是產(chǎn)地，又是銷地。也就是說，標(biāo)準(zhǔn)運(yùn)輸問題中的產(chǎn)地為原始轉(zhuǎn)運(yùn)問題中的產(chǎn)地和所有的轉(zhuǎn)運(yùn)點(diǎn)，銷地為原始問題中的銷地和所有的轉(zhuǎn)運(yùn)點(diǎn)。(2)確定各產(chǎn)地的產(chǎn)量和銷地的銷量：將原始轉(zhuǎn)運(yùn)問題中產(chǎn)地的產(chǎn)量和銷地的銷量直接移植入標(biāo)準(zhǔn)運(yùn)輸問題；轉(zhuǎn)運(yùn)點(diǎn)的產(chǎn)量和銷量相同，數(shù)值都為經(jīng)過該轉(zhuǎn)運(yùn)點(diǎn)的最大可能轉(zhuǎn)運(yùn)量。109轉(zhuǎn)運(yùn)問題(1)確定標(biāo)準(zhǔn)運(yùn)輸問題中的產(chǎn)地和銷地：轉(zhuǎn)運(yùn)點(diǎn)既是產(chǎn)轉(zhuǎn)運(yùn)問題(3)確定各產(chǎn)地與銷地之間的單位運(yùn)輸費(fèi)用：將原始問題中已知的兩地之間的單位運(yùn)輸費(fèi)用移植入標(biāo)準(zhǔn)運(yùn)輸問題；各轉(zhuǎn)運(yùn)點(diǎn)到其自身的單位運(yùn)輸費(fèi)用為0；對(duì)于原始轉(zhuǎn)運(yùn)問題中不存在的運(yùn)輸路線，單位運(yùn)費(fèi)為無窮大，用任意大的正數(shù)??表示。110轉(zhuǎn)運(yùn)問題(3)確定各產(chǎn)地與銷地之間的單位運(yùn)輸費(fèi)用：將原始問轉(zhuǎn)運(yùn)問題示例1111轉(zhuǎn)運(yùn)問題示例1111其它問題一些應(yīng)用問題雖然與物資運(yùn)輸、分銷沒有任何聯(lián)系，但是由于其問題背景與運(yùn)輸問題有相似的形式，亦可將其抽象并建模為廣義的產(chǎn)銷平衡運(yùn)輸問題，從而采用運(yùn)輸問題的表上作業(yè)法進(jìn)行求解。112其它問題一些應(yīng)用問題雖然與物資運(yùn)輸、分銷沒有任何聯(lián)系，但是由習(xí)題1求解如下運(yùn)輸問題：113習(xí)題1求解如下運(yùn)輸問題：113習(xí)題2求解如下運(yùn)輸問題：114習(xí)題2求解如下運(yùn)輸問題：114習(xí)題3某水產(chǎn)品銷售公司每天從3個(gè)水產(chǎn)品養(yǎng)殖廠采購新鮮產(chǎn)品運(yùn)往4個(gè)批發(fā)市場。3個(gè)養(yǎng)殖廠每天提供的水產(chǎn)品數(shù)量為2500、3000、4500公斤，4個(gè)批發(fā)市場每日的需求量分別為2000、2500、3000、2500公斤。根據(jù)表5所示3個(gè)養(yǎng)殖廠的采購成本價(jià)和4個(gè)批發(fā)市場的價(jià)格（單位：元/千克），公司應(yīng)如何安排運(yùn)輸可使得總利潤最大？

115習(xí)題3某水產(chǎn)品銷售公司每天從3個(gè)水產(chǎn)品養(yǎng)殖廠采購新鮮產(chǎn)品運(yùn)往習(xí)題4有3個(gè)牧業(yè)基地向4個(gè)城市提供鮮奶，4個(gè)城市每日的鮮奶需求量為16、30、24和30千升，3個(gè)基地的每日鮮奶供應(yīng)量分別為30、40和50千升。已知運(yùn)送每千升鮮奶的費(fèi)用如表所示（單位：千元）。試確定最經(jīng)濟(jì)的鮮奶運(yùn)輸方案，且求出最小總運(yùn)費(fèi)。116習(xí)題4有3個(gè)牧業(yè)基地向4個(gè)城市提供鮮奶習(xí)題5假定習(xí)題3中城市A每天最低需求和總需求量分別為14和24千升，城市C每天最低需求和總需求量分別為25和40千升，其它城市需求量無變化，在最低需求必須滿足的前提下，求解該問題，且求出最小總運(yùn)費(fèi)。

117習(xí)題5假定習(xí)題3中城市A每天最低需求和總需求量分別為14和2習(xí)題6某干果公司從3個(gè)水果生產(chǎn)基地進(jìn)貨，在4個(gè)加工廠將水果加工成干果。假定3個(gè)水果基地的產(chǎn)量、4個(gè)加工廠的需求量，以及單位水果的運(yùn)價(jià)如表所示。在最低需求必須滿足的前提下，求總成本最低的運(yùn)輸方案。

118習(xí)題6某干果公司從3個(gè)水果生產(chǎn)基地進(jìn)貨，在4個(gè)加工廠將水果加習(xí)題7已知2個(gè)供應(yīng)方A1、A2以及3個(gè)需求方B1、B2、B3的運(yùn)輸問題的運(yùn)價(jià)表如表所示。由于違約成本比較低，供應(yīng)方A1、A2在運(yùn)輸成本較高的情景下可選擇違約；同樣，由于缺貨損失比較低，需求方B1、B2、B3也可以在運(yùn)輸成本較低的情景下選擇違約。問：根據(jù)表所示的缺貨成本、違約成本，以及運(yùn)輸成本，如何安排運(yùn)輸可使得總運(yùn)營成本最低？

119習(xí)題7已知2個(gè)供應(yīng)方A1、A2以及3個(gè)需求方B1、B2、B3第6章目標(biāo)規(guī)劃(GoalProgramming)120第6章目標(biāo)規(guī)劃(GoalProgramming)120目標(biāo)規(guī)劃的提出用線性規(guī)劃來解決實(shí)際問題時(shí)，除了要滿足比例性、可加性、可分性和確定性四個(gè)假設(shè)之外，通常還假設(shè)實(shí)際問題的求解目標(biāo)是單一的，而且其約束條件是可以嚴(yán)格滿足的。

線性規(guī)劃的弊端：現(xiàn)實(shí)決策問題通常都有多重的、可能相互沖突的目標(biāo)其約束條件也不一定必須全部嚴(yán)格滿足

目標(biāo)規(guī)劃(GoalProgramming)的提出，正是為了消除或至少部分填補(bǔ)這種方法與實(shí)際應(yīng)用之間的空白。121目標(biāo)規(guī)劃的提出用線性規(guī)劃來解決實(shí)際問題時(shí)，除了要滿足比例性、6.1.1引例-目標(biāo)規(guī)劃的數(shù)學(xué)模型在例1-1中，F(xiàn)公司每周需要根據(jù)下表確定產(chǎn)品A、B、C的產(chǎn)量，以獲取最大的利潤其線性規(guī)劃數(shù)學(xué)模型為：本問題的求解目標(biāo)是唯一的———利潤最大化。1226.1.1引例-目標(biāo)規(guī)劃的數(shù)學(xué)模型在例1-1中，F(xiàn)公司每周6.1.1引例但現(xiàn)實(shí)問題往往會(huì)有多個(gè)目標(biāo)，比如把上面這個(gè)例子變成：例6-1在滿足例1-1資源約束的前提下，按優(yōu)先次序滿足以下的目標(biāo)：利潤最好不少于200元；產(chǎn)品B為產(chǎn)品A的補(bǔ)充件，其產(chǎn)量最好低于產(chǎn)品A的一半；產(chǎn)品C為戰(zhàn)略性產(chǎn)品，其產(chǎn)量最好不低于5件；原材料M2最好全部使用完且不超量；原材料M1比較稀缺，最好至少有10千克的剩余。問：F公司應(yīng)如何安排生產(chǎn)計(jì)劃，能夠盡可能達(dá)成以上的經(jīng)營目標(biāo)？1236.1.1引例但現(xiàn)實(shí)問題往往會(huì)有多個(gè)目標(biāo)，比如把上面這個(gè)例6.1.1引例問題的線性規(guī)劃模型變?yōu)橐韵虏坏仁浇M符合上述不等式組的解，就是本問題的解。經(jīng)過計(jì)算，該不等式組無解。而在實(shí)際背景下，該問題顯然是有解的。124

資源約束五個(gè)目標(biāo)6.1.1引例問題的線性規(guī)劃模型變?yōu)橐韵虏坏仁浇M124 6.1.1引例實(shí)際上，本問題前3個(gè)優(yōu)先級(jí)的目標(biāo)是可以完全達(dá)成的，第(4)、(5)個(gè)目標(biāo)雖然無法完全達(dá)成，但是是允許妥協(xié)的———只需要在前幾個(gè)目標(biāo)達(dá)成的基礎(chǔ)上，盡可能滿足即可。問題出在建模的方式上以上模型將5個(gè)原本有優(yōu)先次序的、允許妥協(xié)的目標(biāo)變成了必須同時(shí)嚴(yán)格滿足的目標(biāo)。因此，一個(gè)在現(xiàn)實(shí)中有解的多目標(biāo)決策問題，以線性規(guī)劃的思路建?？赡芫蜔o解了。目標(biāo)規(guī)劃的提出，正是針對(duì)這類線性規(guī)劃無法解決的實(shí)際問題。1256.1.1引例實(shí)際上，本問題前3個(gè)優(yōu)先級(jí)的目標(biāo)是可以完全6.1.2目標(biāo)規(guī)劃的基本概念目標(biāo)規(guī)劃問題是這樣一類問題：在滿足剛性約束的前提下，求解一組決策變量的取值，使得不同優(yōu)先級(jí)別目標(biāo)的實(shí)現(xiàn)值與目標(biāo)值之間的偏差盡可能小的線性規(guī)劃問題。概念實(shí)現(xiàn)值與目標(biāo)值、偏差變量剛性約束與柔性約束達(dá)成函數(shù)優(yōu)先級(jí)與權(quán)重1266.1.2目標(biāo)規(guī)劃的基本概念目標(biāo)規(guī)劃問題是這樣一類問題：16.1.2目標(biāo)規(guī)劃的基本概念1、目標(biāo)值、實(shí)現(xiàn)值與偏差變量在目標(biāo)規(guī)劃中，描述各個(gè)目標(biāo)的數(shù)學(xué)表達(dá)式稱為目標(biāo)表達(dá)式。對(duì)某個(gè)目標(biāo)表達(dá)式期望的取值水平（不論是不超過、不少于還是等于），稱為該目標(biāo)的目標(biāo)值。當(dāng)決策變量xj

的取值確定以后，某個(gè)目標(biāo)表達(dá)式的實(shí)際取值稱為該目標(biāo)的實(shí)現(xiàn)值，又稱為決策值。例如，例6-1中第(1)個(gè)目標(biāo)的目標(biāo)表達(dá)式為5x1+4x2+2x3，對(duì)此目標(biāo)的期望值為200，則其目標(biāo)值為200；第(2)個(gè)目標(biāo)的目標(biāo)表達(dá)式可寫為x1

?2x2，此時(shí)目標(biāo)值為0。第(3)個(gè)目標(biāo)的表達(dá)式x3，目標(biāo)值為5。1276.1.2目標(biāo)規(guī)劃的基本概念1、目標(biāo)值、實(shí)現(xiàn)值與偏差變量16.1.2目標(biāo)規(guī)劃的基本概念實(shí)現(xiàn)值與目標(biāo)值之間可能會(huì)存在差異，這種差異的大小在決策（確定決策變量取值）前是無法預(yù)知的，是隨決策變量變化而變化的，因此稱實(shí)現(xiàn)值與目標(biāo)值之間的差異為偏差變量。因建模的需要以及適應(yīng)線性規(guī)劃中對(duì)變量的非負(fù)要求，偏差變量又分為正偏差量，代表實(shí)現(xiàn)值超過目標(biāo)值的偏差，記為d+負(fù)偏差量，代表實(shí)現(xiàn)值未達(dá)到目標(biāo)值的偏差，記為d-滿足非負(fù)：滿足互斥：1286.1.2目標(biāo)規(guī)劃的基本概念實(shí)現(xiàn)值與目標(biāo)值之間可能會(huì)存在差6.1.2目標(biāo)規(guī)劃的基本概念例如，例6-1中，如果某個(gè)滿足了約束條件式(6-1)的決策為x1=25;x2=13;x3=5;則第(1)個(gè)目標(biāo)，其實(shí)現(xiàn)值為5x1+4x2+2x3=187，未達(dá)到目標(biāo)值200，如果用

表示該目標(biāo)的正負(fù)偏差量，有對(duì)于第(2)個(gè)目標(biāo)，其實(shí)現(xiàn)值為x1

?2x2=?1，目標(biāo)值為0，有同理，對(duì)于第(3)個(gè)目標(biāo)，因?yàn)閷?shí)現(xiàn)值等于目標(biāo)值5，有1296.1.2目標(biāo)規(guī)劃的基本概念例如，例6-1中，如果某個(gè)滿足6.1.2目標(biāo)規(guī)劃的基本概念2、剛性約束、柔性約束與達(dá)成函數(shù)在目標(biāo)規(guī)劃中，必須嚴(yán)格滿足的約束條件稱為剛性約束或硬目標(biāo)。剛性約束中不含偏差變量。目標(biāo)規(guī)劃中，不滿足剛性約束的解為非可行解。與剛性約束相對(duì)，目標(biāo)規(guī)劃中允許某些目標(biāo)的決策值與目標(biāo)值存在偏差，這類目標(biāo)稱為軟目標(biāo)，其所對(duì)應(yīng)的約束條件稱為柔性約束。此即柔性約束的表達(dá)式。1306.1.2目標(biāo)規(guī)劃的基本概念2、剛性約束、柔性約束與達(dá)成6.1.2目標(biāo)規(guī)劃的基本概念例如，對(duì)例6-1中的第(1)個(gè)目標(biāo)，其柔性約束為：同理，對(duì)于第(2)、(3)個(gè)目標(biāo)，其柔性約束分別為：1316.1.2目標(biāo)規(guī)劃的基本概念例如，對(duì)例6-1中的第(1)個(gè)6.1.2目標(biāo)規(guī)劃的基本概念對(duì)每個(gè)目標(biāo)，決策者會(huì)表達(dá)出對(duì)決策值與目標(biāo)值之間關(guān)系的期望———超過、不超過或恰好等于。但僅從柔性約束本身，無法判斷決策者究竟是期望達(dá)到哪一種。在此引入一個(gè)稱為達(dá)成函數(shù)的表達(dá)式來表示決策者的期望。由目標(biāo)規(guī)劃問題的定義可知，對(duì)于任一目標(biāo)，決策者的期望是使決策值與目標(biāo)值的偏差盡可能小，因此達(dá)成函數(shù)是僅含偏差變量，且目標(biāo)是使偏差變量取最小值的目標(biāo)函數(shù)1326.1.2目標(biāo)規(guī)劃的基本概念對(duì)每個(gè)目標(biāo)，決策者會(huì)表達(dá)出對(duì)決6.1.2目標(biāo)規(guī)劃的基本概念對(duì)于單一的目標(biāo)，達(dá)成函數(shù)依決策者的期望分三種情況：超過目標(biāo)值，則達(dá)成函數(shù)為

?？衫斫鉃橄Ｍ姓?，不希望有負(fù)偏差。不超過目標(biāo)值，則達(dá)成函數(shù)為

?？衫斫鉃橄Ｍ胸?fù)偏差，不希望有正偏差。恰好等于目標(biāo)值，則有

，亦即正、負(fù)偏差量都要盡可能地小。結(jié)合柔性約束與達(dá)成函數(shù)，就可以寫出每個(gè)目標(biāo)的目標(biāo)表達(dá)式。1336.1.2目標(biāo)規(guī)劃的基本概念對(duì)于單一的目標(biāo)，達(dá)成函數(shù)依決策6.1.2目標(biāo)規(guī)劃的基本概念例如，第(1)個(gè)目標(biāo)的達(dá)成函數(shù)為利潤最好不少于200：第(2)個(gè)目標(biāo)的表達(dá)式為產(chǎn)品B產(chǎn)量最好低于產(chǎn)品A一半：第(4)個(gè)目標(biāo)的表達(dá)式為原材料M2最好全部使用完且不超量：1346.1.2目標(biāo)規(guī)劃的基本概念例如，第(1)個(gè)目標(biāo)的達(dá)成函數(shù)6.1.2目標(biāo)規(guī)劃的基本概念3、優(yōu)先級(jí)與權(quán)重以上的分析只針對(duì)單一目標(biāo)，當(dāng)問題中有多個(gè)主次不同的目標(biāo)，且各個(gè)目標(biāo)之間可能存在矛盾時(shí)，就需要以某種方式將各個(gè)目標(biāo)的達(dá)成函數(shù)合并成一個(gè)單一的達(dá)成函數(shù)。目標(biāo)規(guī)劃通過引入優(yōu)先級(jí)來為不同目標(biāo)的達(dá)成函數(shù)加權(quán)。具體為，在合并達(dá)成函數(shù)時(shí)，將目標(biāo)按重要程度進(jìn)行優(yōu)先級(jí)排序，第1優(yōu)先級(jí)目標(biāo)的達(dá)成函數(shù)乘以優(yōu)先因子P1，第2優(yōu)先級(jí)目標(biāo)的達(dá)成函數(shù)乘以P2，依次類推，第L優(yōu)先級(jí)目標(biāo)的達(dá)成函數(shù)乘以優(yōu)先因子PL，且規(guī)定由此保證優(yōu)先實(shí)現(xiàn)P1

級(jí)的目標(biāo)，在此基礎(chǔ)上再考慮P2

級(jí)目標(biāo)的實(shí)現(xiàn)，然后依次類推。1356.1.2目標(biāo)規(guī)劃的基本概念3、優(yōu)先級(jí)與權(quán)重1356.1.2目標(biāo)規(guī)劃的基本概念某些實(shí)際問題中同一優(yōu)先級(jí)下可能有多個(gè)目標(biāo)，這些目標(biāo)的重要程度還可以有差異，只不過這種差異不是數(shù)量級(jí)上的，目標(biāo)規(guī)劃用權(quán)重來區(qū)分這種差異。在建模時(shí)，可以根據(jù)決策者的需求，對(duì)該優(yōu)先級(jí)Pl

下某個(gè)目標(biāo)k的達(dá)成函數(shù)以權(quán)系數(shù)wlk

加權(quán)后再相加。注意：優(yōu)先級(jí)的劃分，以及同一優(yōu)先級(jí)下多個(gè)目標(biāo)的權(quán)重的設(shè)定，沒有普適性的規(guī)則，而應(yīng)根據(jù)決策者的需求和偏好來確定。------------主觀性在不同的問題背景或決策者偏好下，同一個(gè)目標(biāo)的優(yōu)先級(jí)或其在某個(gè)優(yōu)先級(jí)中的權(quán)系數(shù)都可能有不同的設(shè)定。1366.1.2目標(biāo)規(guī)劃的基本概念某些實(shí)際問題中同一優(yōu)先級(jí)下可能6.1.2目標(biāo)規(guī)劃的基本概念根據(jù)上述概念，可以寫出例6-1的目標(biāo)規(guī)劃模型。整個(gè)問題的達(dá)成函數(shù)可以寫為上式所示的“和”的形式，也可以寫為“集合”的形式：1376.1.2目標(biāo)規(guī)劃的基本概念根據(jù)上述概念，可以寫出例6-16.1.3目標(biāo)規(guī)劃模型及建模步驟目標(biāo)規(guī)劃問題的數(shù)學(xué)模型的一般形式為：自上而下分別是達(dá)成函數(shù)、剛性約束、柔性約束和所有變量的非負(fù)約束138

6.1.3目標(biāo)規(guī)劃模型及建模步驟目標(biāo)規(guī)劃問題的數(shù)學(xué)模型的一6.1.3目標(biāo)規(guī)劃模型及建模步驟建模步驟：第1步設(shè)定問題的決策變量；第2步列出問題的剛性約束；第3步根據(jù)決策者的需求和偏好，設(shè)定各個(gè)目標(biāo)的優(yōu)先級(jí)，當(dāng)有多個(gè)目標(biāo)同屬于一個(gè)優(yōu)先級(jí)下時(shí)，還需根據(jù)約定設(shè)定各個(gè)目標(biāo)的權(quán)重；然后，寫出各個(gè)目標(biāo)的柔性約束和各優(yōu)先級(jí)的達(dá)成函數(shù)；第4步用優(yōu)先因子和權(quán)系數(shù)為各個(gè)目標(biāo)的達(dá)成函數(shù)加權(quán)，寫出整個(gè)問題的達(dá)成函數(shù)。第5步寫出決策變量與偏差變量的非負(fù)約束。1396.1.3目標(biāo)規(guī)劃模型及建模步驟建模步驟：139例6-2在例6-1中，假定不要求嚴(yán)格滿足資源約束，且各優(yōu)先級(jí)的目標(biāo)依次如下：利潤最好不少于180元；產(chǎn)品A的產(chǎn)量最好不多于25件、產(chǎn)品B的產(chǎn)量最好不少于15件、產(chǎn)品C的產(chǎn)量最好不少于5件，且根據(jù)單位產(chǎn)品的利潤確定權(quán)系數(shù)；原材料M2最好全部使用完，不足時(shí)可購入，原材料M1比較稀缺，最好至少有10千克的剩余。問：F公司應(yīng)如何安排生產(chǎn)計(jì)劃，能夠盡可能達(dá)成以上的經(jīng)營目標(biāo)？140例6-2在例6-1中，假定不要求嚴(yán)格滿足資源約束，且各優(yōu)解：用x1，x2

和x3

表示產(chǎn)品A，B和C的產(chǎn)量。141解：用x1，x2和x3表示產(chǎn)品A，B和C的產(chǎn)量。14例6-3電子產(chǎn)品生產(chǎn)企業(yè)HF公司通過采購半成品生產(chǎn)A、B、C三種型號(hào)的手機(jī)。這三種手機(jī)在同一流水線上生產(chǎn)，每件的生產(chǎn)工時(shí)消耗分別為5分鐘，7分鐘，12分鐘，利潤分別為每臺(tái)140元，210元，384元。生產(chǎn)線正常運(yùn)轉(zhuǎn)時(shí)間為250小時(shí)/月，加班滿負(fù)荷運(yùn)轉(zhuǎn)時(shí)最多有400小時(shí)/月。HF公司的決策者提出的月經(jīng)營目標(biāo)按優(yōu)先級(jí)排序?yàn)椋罕M可能充分利用生產(chǎn)線的正常工時(shí)，工時(shí)不夠用時(shí)可以加班；希望A、B、C的產(chǎn)量至少達(dá)到700，750，500臺(tái)，根據(jù)單位工時(shí)的利潤比例設(shè)定權(quán)系數(shù)；加班工時(shí)最好不超過40小時(shí)/月；

希望A、B、C的產(chǎn)量盡可能超過月銷售量預(yù)測的最低水平800，900，550臺(tái)，根據(jù)單位工時(shí)的利潤比例設(shè)定權(quán)系數(shù)。問：各產(chǎn)品應(yīng)生產(chǎn)多少才能達(dá)成上述經(jīng)營目標(biāo)？建立本問題的其目標(biāo)規(guī)劃模型。142例6-3電子產(chǎn)品生產(chǎn)企業(yè)HF公司通過采購半成品生產(chǎn)A、B解：設(shè)A、B、C的產(chǎn)量分別為x1,x2,x3。143解：設(shè)A、B、C的產(chǎn)量分別為x1,x2,x3。143例6-4SD公司下屬三個(gè)工廠生產(chǎn)某種產(chǎn)品來滿足四個(gè)地區(qū)的需求，各工廠的產(chǎn)量、各地的需求量以及從各工廠到四地的單位產(chǎn)品運(yùn)輸費(fèi)用如下表所示。如果僅要求運(yùn)輸費(fèi)用最小，在將該問題轉(zhuǎn)化為產(chǎn)銷平衡問題后，用運(yùn)輸問題表上作業(yè)法求解得最低總運(yùn)費(fèi)為2750元。但是考慮到各地的不同情況和運(yùn)輸中可能存在的問題，該公司在確定最后運(yùn)輸方案時(shí)還需考慮其它幾個(gè)目標(biāo)，按重要程度依次為：P1：地區(qū)3為重點(diǎn)銷售地區(qū)，其需求應(yīng)優(yōu)先全部滿足；P2：用于供應(yīng)地區(qū)2的產(chǎn)品中，工廠1的產(chǎn)品不少于80件；P3：為平衡各地需求，每個(gè)地區(qū)用戶需求的滿足率應(yīng)不低于90%；P4：由于交通條件的限制，應(yīng)盡量避免從工廠2運(yùn)輸至地區(qū)2；P5：盡可能減少總運(yùn)費(fèi)。144例6-4SD公司下屬三個(gè)工廠生產(chǎn)某種產(chǎn)品來滿足四個(gè)地區(qū)的1451456.2兩變量目標(biāo)規(guī)劃問題的圖解法

1466.2兩變量目標(biāo)規(guī)劃問題的圖解法

1466.2兩變量目標(biāo)規(guī)劃問題的圖解法目標(biāo)規(guī)劃模型中對(duì)目標(biāo)進(jìn)行了優(yōu)先級(jí)的區(qū)分，這決定了其求解過程是一個(gè)分級(jí)進(jìn)行的過程：對(duì)于有L個(gè)優(yōu)先級(jí)的目標(biāo)規(guī)劃問題，先在可行域內(nèi)尋找滿足P1級(jí)目標(biāo)的解然后在保證P1級(jí)目標(biāo)不被打破的前提下，再尋找滿足P2級(jí)目標(biāo)的解依次類推如果用解空間的概念，求解過程又可以表述為：在可行域R0

內(nèi)找到滿足P1

級(jí)目標(biāo)的解空間R1，再以R1

為可行域?qū)ふ覞M足P2

級(jí)目標(biāo)的解空間R2，依次類推，直至在RL-1

內(nèi)尋找PL

級(jí)目標(biāo)的解空間RL，其中目標(biāo)規(guī)劃的最終求解結(jié)果通常只能稱為滿意解即只能保證優(yōu)先級(jí)較高的目標(biāo)得以實(shí)現(xiàn)或部分實(shí)現(xiàn)，不保證優(yōu)先級(jí)低的目標(biāo)能實(shí)現(xiàn)。1476.2兩變量目標(biāo)規(guī)劃問題的圖解法目標(biāo)規(guī)劃模型中對(duì)目標(biāo)進(jìn)行了優(yōu)6.2兩變量目標(biāo)規(guī)劃問題的圖解法步驟第1步在坐標(biāo)平面第一象限表示出由剛性約束所確定的可行域，以此可行域?yàn)槌跏冀饪臻gR0；第2步選定P1優(yōu)先級(jí)的目標(biāo)，進(jìn)入第3步；第3步在Rl-1

中找到滿足Pl級(jí)目標(biāo)的解空間進(jìn)入第4步Rl；第4步當(dāng)所有優(yōu)先級(jí)的目標(biāo)都處理完時(shí)，求解結(jié)束，問題的滿意解就是目前得到的解空間；或者，如果Rl

為一個(gè)點(diǎn)，求解結(jié)束，問題的滿意解就是該點(diǎn)的坐標(biāo)。如果上述條件皆不滿足，則轉(zhuǎn)到下一個(gè)優(yōu)先級(jí)，返回第3步。1486.2兩變量目標(biāo)規(guī)劃問題的圖解法步驟148圖解法示例例6-5用圖解法求解

149圖解法示例例6-5用圖解法求解149150150151151152152153153154154155155156156157157158158圖解法示例例6-6

用圖解法求解159圖解法示例例6-6用圖解法求解1591601601611611621621631631641641651651661666.2兩變量目標(biāo)規(guī)劃問題的圖解法應(yīng)用圖解法求解只有兩個(gè)決策變量、且一個(gè)優(yōu)先級(jí)Pl下有多個(gè)目標(biāo)的目標(biāo)規(guī)劃模型時(shí)，確定Pl優(yōu)先級(jí)的解空間Rl的過程就會(huì)變得比較復(fù)雜，見例6-7(略)。1676.2兩變量目標(biāo)規(guī)劃問題的圖解法應(yīng)用圖解法求解只有兩個(gè)決策變6.4用Excel求解目標(biāo)規(guī)劃問題掌握了序貫解法的原理，理解將目標(biāo)規(guī)劃問題轉(zhuǎn)化為一系列線性規(guī)劃問題的方式，再進(jìn)一步用Excel規(guī)劃求解工具完成。略。1686.4用Excel求解目標(biāo)規(guī)劃問題掌握了序貫解法的原理，理169第9章網(wǎng)絡(luò)計(jì)劃技術(shù)(NetworkPlanningTechnique)169第9章網(wǎng)絡(luò)計(jì)劃技術(shù)基本概念網(wǎng)絡(luò)計(jì)劃技術(shù)（項(xiàng)目進(jìn)度管理）它利用網(wǎng)絡(luò)圖的形式直觀表現(xiàn)出工程項(xiàng)目中各項(xiàng)任務(wù)之間的相互關(guān)系，從而找出決定項(xiàng)目總工期的關(guān)鍵路線和關(guān)鍵工序。進(jìn)而，在一定工期、成本、資源等約束條件下通過各種技術(shù)手段獲得最佳的計(jì)劃安排，以達(dá)到縮短工期、提高工效、降低成本的目的。170基本概念網(wǎng)絡(luò)計(jì)劃技術(shù)（項(xiàng)目進(jìn)度管理）170引例17116分鐘引例17116分鐘引例17220分鐘引例17220分鐘發(fā)展歷程網(wǎng)絡(luò)計(jì)劃技術(shù)根據(jù)起源可以分為關(guān)鍵路徑法（CPM-CriticalPathMethod-WalkerandKelly）和計(jì)劃評(píng)審技術(shù)（PERT-ProgramEvaluationandReviewTechnic-U.S.Navy）兩個(gè)源頭。關(guān)鍵路徑法強(qiáng)調(diào)/要求所研究項(xiàng)目中每項(xiàng)任務(wù)的執(zhí)行時(shí)間必須是明確的，而計(jì)劃評(píng)審技術(shù)中每項(xiàng)任務(wù)的執(zhí)行時(shí)間可以是一個(gè)估計(jì)值/不確定值。因此，關(guān)鍵路徑法主要應(yīng)用于一些有前期經(jīng)驗(yàn)的工程項(xiàng)目，而計(jì)劃評(píng)審技術(shù)更多應(yīng)用于研究與開發(fā)項(xiàng)目的計(jì)劃管理。1962,錢學(xué)森-華羅庚-“統(tǒng)籌法”173發(fā)展歷程網(wǎng)絡(luò)計(jì)劃技術(shù)根據(jù)起源可以分為關(guān)鍵路徑法（CPM-Cr基本流程1-闡明問題，將項(xiàng)目分解為若干個(gè)可以獨(dú)立的工作單元，并明確各個(gè)工作單元的相關(guān)屬性（資源使用、時(shí)間消耗、成本計(jì)算等），以及工作單元之間的邏輯先后關(guān)系。2-根據(jù)分解后的工作單元，以及工作單元之間的邏輯先后關(guān)系，繪制網(wǎng)絡(luò)圖。174基本流程1-闡明問題，將項(xiàng)目分解為若干個(gè)可以獨(dú)立的工作單元，基本流程3-應(yīng)用關(guān)鍵路徑法計(jì)算得到整個(gè)項(xiàng)目的最短完成時(shí)間，項(xiàng)目中每項(xiàng)工序的最遲開始時(shí)間、最早可能開始時(shí)間等時(shí)間參數(shù)，整個(gè)項(xiàng)目的關(guān)鍵路徑以及關(guān)鍵路徑上的各項(xiàng)關(guān)鍵工序。4-根據(jù)具體應(yīng)用，對(duì)關(guān)鍵路徑上的關(guān)鍵工序進(jìn)行資源的合理安排和優(yōu)化。175基本流程3-應(yīng)用關(guān)鍵路徑法計(jì)算得到整個(gè)項(xiàng)目的最短完成時(shí)間，項(xiàng)雙代號(hào)網(wǎng)絡(luò)圖的繪制方法工作單元用有向箭線來表示，箭線的方向表示工序進(jìn)行的方向：箭線的箭尾表示該工序的開始，箭線的箭頭表示該工序的結(jié)束。工序的名稱或者代號(hào)標(biāo)注在箭線的上方，工序所花費(fèi)的時(shí)間標(biāo)注在箭線的下方。176雙代號(hào)網(wǎng)絡(luò)圖的繪制方法工作單元用有向箭線來表示，箭線的方向表雙代號(hào)網(wǎng)絡(luò)圖的繪制方法多條箭線指向該節(jié)點(diǎn)代表著多條箭線所指的工序都完成之后，該節(jié)點(diǎn)之后的工序才可以開始E的緊后工序F，同理，C、D、E是F工序的緊前工序。多條箭線從該節(jié)點(diǎn)引出代表著該節(jié)點(diǎn)所代表的之前的工序結(jié)束后，可以同時(shí)開始多項(xiàng)工序。177雙代號(hào)網(wǎng)絡(luò)圖的繪制方法多條箭線指向該節(jié)點(diǎn)代表著多條箭線所指的雙代號(hào)網(wǎng)絡(luò)圖的繪制方法1-

網(wǎng)絡(luò)圖中箭線盡量從左指向右，從上至下，從小到大，節(jié)點(diǎn)的編號(hào)按順序編排，不允許重復(fù)。2-

兩個(gè)節(jié)點(diǎn)之間，如果有，只能有一條箭線。3-

網(wǎng)絡(luò)圖中只能有一個(gè)起始節(jié)點(diǎn)和一個(gè)終止節(jié)點(diǎn)。4-

不能有缺口和回路。除了起始點(diǎn)和終止點(diǎn)，任何節(jié)點(diǎn)都必須有至少一條箭線指向和引出該節(jié)點(diǎn)。178雙代號(hào)網(wǎng)絡(luò)圖的繪制方法1-網(wǎng)絡(luò)圖中箭線盡量從左指向右，從上雙代號(hào)網(wǎng)絡(luò)圖的繪制方法如果節(jié)點(diǎn)之間需要包含兩個(gè)或兩個(gè)以上的箭線，即表示多個(gè)工序可以同時(shí)開始，并同時(shí)作為后續(xù)工序的緊前工序，那么需要使用虛工序（虛線的箭線）來幫助表示。179雙代號(hào)網(wǎng)絡(luò)圖的繪制方法如果節(jié)點(diǎn)之間需要包含兩個(gè)或兩個(gè)以上的箭雙代號(hào)網(wǎng)絡(luò)圖的繪制方法180雙代號(hào)網(wǎng)絡(luò)圖的繪制方法180雙代號(hào)網(wǎng)絡(luò)圖的繪制方法181雙代號(hào)網(wǎng)絡(luò)圖的繪制方法181雙代號(hào)網(wǎng)絡(luò)圖的繪制方法182雙代號(hào)網(wǎng)絡(luò)圖的繪制方法182雙代號(hào)網(wǎng)絡(luò)圖示例1例9-1183雙代號(hào)網(wǎng)絡(luò)圖示例1例9-1183雙代號(hào)網(wǎng)絡(luò)圖示例1184雙代號(hào)網(wǎng)絡(luò)圖示例1184雙代號(hào)網(wǎng)絡(luò)圖示例2185雙代號(hào)網(wǎng)絡(luò)圖示例2185單代號(hào)網(wǎng)絡(luò)圖的繪制方法節(jié)點(diǎn)表示工序，有向箭線描述工序之間的邏輯關(guān)系—緊前/緊后工序：箭尾連接的節(jié)點(diǎn)工序?yàn)榧^連接的節(jié)點(diǎn)工序的緊前工序。單代號(hào)網(wǎng)絡(luò)不需要使用類似雙代號(hào)網(wǎng)絡(luò)中的虛工序。186單代號(hào)網(wǎng)絡(luò)圖的繪制方法節(jié)點(diǎn)表示工序，有向箭線描述工序之間的邏單代號(hào)網(wǎng)絡(luò)圖的繪制方法187單代號(hào)網(wǎng)絡(luò)圖的繪制方法187單代號(hào)網(wǎng)絡(luò)圖的繪制方法188單代號(hào)網(wǎng)絡(luò)圖的繪制方法188單代號(hào)網(wǎng)絡(luò)圖的繪制方法189單代號(hào)網(wǎng)絡(luò)圖的繪制方法189單代號(hào)網(wǎng)絡(luò)圖示例1例9-3190單代號(hào)網(wǎng)絡(luò)圖示例1例9-3190單代號(hào)網(wǎng)絡(luò)圖示例1例9-3191單代號(hào)網(wǎng)絡(luò)圖示例1例9-3191單代號(hào)網(wǎng)絡(luò)圖示例2192單代號(hào)網(wǎng)絡(luò)圖示例2192習(xí)題1193習(xí)題1193194194195195習(xí)題2196習(xí)題2196

197197習(xí)題3198習(xí)題3198199199習(xí)題4200習(xí)題4200201201關(guān)鍵路徑法從開始節(jié)點(diǎn)出發(fā)，沿著不同的路徑到達(dá)終止節(jié)點(diǎn)所花費(fèi)的時(shí)間也不盡相同。其中，花費(fèi)時(shí)間最長的路經(jīng)稱為關(guān)鍵路徑，而關(guān)鍵路徑上的所有工序都被稱為關(guān)鍵工序。202關(guān)鍵路徑法從開始節(jié)點(diǎn)出發(fā)，沿著不同的路徑到達(dá)終止節(jié)點(diǎn)所花費(fèi)的關(guān)鍵路徑法基本特點(diǎn)1-關(guān)鍵路徑上的所有工序總花費(fèi)時(shí)間決定了整個(gè)項(xiàng)目的總工期，即項(xiàng)目的總工期等于關(guān)鍵路徑上的所有工序持續(xù)時(shí)間的總和。2-關(guān)鍵路徑上的任一個(gè)關(guān)鍵工序發(fā)生了時(shí)間上的延遲，那么必然導(dǎo)致整個(gè)項(xiàng)目的工期時(shí)間上的延遲。203關(guān)鍵路徑法基本特點(diǎn)203關(guān)鍵路徑法基本特點(diǎn)3-關(guān)鍵路徑上關(guān)鍵工序如果縮短了工期，那么整個(gè)項(xiàng)目的工期都會(huì)被縮短。相反，如果只是縮短非關(guān)鍵路徑上的工序—非關(guān)鍵工序的花費(fèi)時(shí)間，整個(gè)項(xiàng)目的工期不會(huì)發(fā)生變化。4-

如果一個(gè)項(xiàng)目包含多條關(guān)鍵路徑，那么它們的工期一定都相同。并且，如果只是縮短其中一條關(guān)鍵路徑的工期，整個(gè)項(xiàng)目的工期并不能被縮短。204關(guān)鍵路徑法基本特點(diǎn)204關(guān)鍵路徑法基本特點(diǎn)5-

關(guān)鍵路徑是相對(duì)的。如果關(guān)鍵路徑的工期被縮短，那么它有可能變?yōu)榉顷P(guān)鍵路徑，而非關(guān)鍵路徑則有可能變成關(guān)鍵路徑。205關(guān)鍵路徑法基本特點(diǎn)205關(guān)鍵路徑法重要參數(shù)最早開始時(shí)間。一個(gè)工序的最早開始時(shí)間TES為該工序的所有緊前工序d最早結(jié)束時(shí)間中最晚的一個(gè)，即其所有緊前工序的最早結(jié)束時(shí)間的最大值。（前一個(gè)工序結(jié)束，后一個(gè)工序才能開始）最早結(jié)束時(shí)間。一個(gè)工序的最早結(jié)束時(shí)間TEF等于該工序的最早開始時(shí)間加上該工序的花費(fèi)時(shí)間值。206關(guān)鍵路徑法重要參數(shù)206關(guān)鍵路徑法重要參數(shù)最遲結(jié)束時(shí)間。一個(gè)工序的最遲結(jié)束時(shí)間TLF是指該工序在不影響整個(gè)項(xiàng)目的時(shí)間進(jìn)度前提下能夠最遲結(jié)束的時(shí)間。它等于該工序所有緊后工序最遲開始時(shí)間最早的一個(gè)，即所有緊后工序的最遲開始時(shí)間的最小值。（取決于別的工序）最遲開始時(shí)間。一個(gè)工序的最遲開始時(shí)間TLS等于該工序的最遲結(jié)束時(shí)間減去該工序的花費(fèi)時(shí)間值。207關(guān)鍵路徑法重要參數(shù)207關(guān)鍵路徑法重要參數(shù)工序總時(shí)差。一個(gè)工序的總時(shí)差TTF是指該工序在不影響整個(gè)項(xiàng)目的時(shí)間進(jìn)度前提下，工序最早開始時(shí)間可以推遲的時(shí)間，即該工序的最遲開始時(shí)間和最早開始時(shí)間的差值。LS-ES工序自由時(shí)差。一個(gè)工序的自由時(shí)差TFF是指該工序在不影響其它工序（其緊后工序）的最早開始時(shí)間前提下，工序最早開始時(shí)間可以推遲的時(shí)間。208關(guān)鍵路徑法重要參數(shù)208技巧:工作最早時(shí)間的計(jì)算:

順著箭線，取大值

工作最遲時(shí)間的計(jì)算：

逆著箭線，取小值

總時(shí)差：

最遲減最早

自由時(shí)差：后早始減本早完209技巧:工作最早時(shí)間的計(jì)算:

209

1．工作最早時(shí)間的計(jì)算（包括工作最早開始時(shí)間和工作最早完成時(shí)間）：“順著箭線計(jì)算，依次取大”（最早開始時(shí)間--取緊前工作最早完成時(shí)間的最大值），起始結(jié)點(diǎn)工作最早開始時(shí)間為0。用最早開始時(shí)間加持續(xù)時(shí)間就是該工作的最早完成時(shí)間。2．網(wǎng)絡(luò)計(jì)劃工期的計(jì)算：終點(diǎn)節(jié)點(diǎn)的最早完成時(shí)間最大值就是該網(wǎng)絡(luò)計(jì)劃的計(jì)算工期，一般以這個(gè)計(jì)劃工期為要求工期。3．工作最遲時(shí)間的計(jì)算（包括工作最遲完成時(shí)間和最遲開始時(shí)間）：“逆著箭線計(jì)算，依次取小”（最遲完成時(shí)間--取緊后工作最遲開始時(shí)間的最小值）。與終點(diǎn)節(jié)點(diǎn)相連的最后一個(gè)工作的最早完成時(shí)間（計(jì)算工期）就是最后一個(gè)工作的最遲完成時(shí)間。用最遲完成時(shí)間減去工作的持續(xù)時(shí)間就是該工作的最遲開始時(shí)間。4．總時(shí)差：“最遲減最早”（最遲開始時(shí)間減最早開始時(shí)間或者最遲完成時(shí)間減最早完成時(shí)間）。注意這里都是“最遲減最早”。每個(gè)工作都有總時(shí)差，最小的總時(shí)差是零，我們經(jīng)常說總時(shí)差為零的工作是“沒有總時(shí)差”。5．自由時(shí)差：“后早始減本早完”(緊后工作的最早開始時(shí)間減本工作的最早完成時(shí)間)。自由時(shí)差總是小于、最多等于總時(shí)差，不會(huì)大于總時(shí)差。210

1．工作最早時(shí)間的計(jì)算（包括工作最早開始時(shí)間和工作最早完成關(guān)鍵路徑法對(duì)于一個(gè)項(xiàng)目而言，一個(gè)工序的工序總時(shí)差代表著該工序在項(xiàng)目中可以機(jī)動(dòng)的時(shí)間。如果一個(gè)工序的工序總時(shí)差為0，則代表該工序不存在機(jī)動(dòng)時(shí)間，那么該工序就是項(xiàng)目的一個(gè)關(guān)鍵工序?？梢愿鶕?jù)計(jì)算得到所有關(guān)鍵工序，確定項(xiàng)目的一條或多條關(guān)鍵路徑。211關(guān)鍵路徑法對(duì)于一個(gè)項(xiàng)目而言，一個(gè)工序的工序總時(shí)差代表著該工序雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法通過計(jì)算節(jié)點(diǎn)相關(guān)的時(shí)間參數(shù)得到工序的時(shí)間參數(shù)。節(jié)點(diǎn)的最早發(fā)生時(shí)間。一個(gè)節(jié)點(diǎn)的最早發(fā)生時(shí)間TEEO是由所有指向該節(jié)點(diǎn)的箭線（工序）中最晚的最早發(fā)生時(shí)間確定。（Tes）節(jié)點(diǎn)的最遲發(fā)生時(shí)間。一個(gè)節(jié)點(diǎn)的最遲發(fā)生時(shí)間TLEO是由該節(jié)點(diǎn)所發(fā)出所有箭線（工序）中最早的最遲發(fā)生時(shí)間確定。(Tlf)212雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法通過計(jì)算節(jié)點(diǎn)相關(guān)的時(shí)間參數(shù)得到工序的時(shí)雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法213工序A（1,2）M（j）=（緊前工序的集合），N(j)=（緊后工序的集合）雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法213工序A（1,2）雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法214雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法214雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法對(duì)于工序(i,j)來說，工序的最早開始時(shí)間就是節(jié)點(diǎn)i的最早發(fā)生時(shí)間

，最遲結(jié)束時(shí)間就是節(jié)點(diǎn)j的最遲發(fā)生時(shí)間

。215雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法對(duì)于工序(i,j)來說，工序的最早開始雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法216雙代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法216雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1例9-5217雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1例9-5217雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例11-按照網(wǎng)絡(luò)圖中各個(gè)節(jié)點(diǎn)的邏輯先后順序，計(jì)算所有節(jié)點(diǎn)的最早發(fā)生時(shí)間TEEO。218雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例11-按照網(wǎng)絡(luò)圖中各個(gè)節(jié)點(diǎn)的邏輯先后雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1219雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1219雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例12-計(jì)算完所有節(jié)點(diǎn)的最早發(fā)生時(shí)間，從終止節(jié)點(diǎn)10開始，反向計(jì)算各個(gè)節(jié)點(diǎn)的最遲發(fā)生時(shí)間TLEO。220雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例12-計(jì)算完所有節(jié)點(diǎn)的最早發(fā)生時(shí)間，雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1最遲開始時(shí)間LS最早開始時(shí)間ES221雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1最遲開始時(shí)間LS221雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1222雙代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1222單代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法與雙代號(hào)網(wǎng)絡(luò)圖的關(guān)鍵路徑法計(jì)算方法類似，單代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法也需要計(jì)算每個(gè)工序的6項(xiàng)時(shí)間參數(shù)，并根據(jù)工序的總時(shí)差為0來找出關(guān)鍵工序。223單代號(hào)網(wǎng)絡(luò)的關(guān)鍵路徑法與雙代號(hào)網(wǎng)絡(luò)圖的關(guān)鍵路徑法計(jì)算方法類似單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1例9-7224單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1例9-7224單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例11-計(jì)算所有節(jié)點(diǎn)的最早開始時(shí)間和最早結(jié)束時(shí)間。225單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例11-計(jì)算所有節(jié)點(diǎn)的最早開始時(shí)間和最單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1226單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1226單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1227單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1227單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1228單代號(hào)網(wǎng)絡(luò)關(guān)鍵路徑法示例1228計(jì)劃評(píng)審技術(shù)計(jì)劃評(píng)審技術(shù)（PERT）與關(guān)鍵路徑法（CPM）方法最大的差異在于計(jì)劃評(píng)審技術(shù)主要是針對(duì)項(xiàng)目中工序持續(xù)時(shí)間無法精確估計(jì)或者給出，而是只能得到由多個(gè)數(shù)據(jù)共同描述的估計(jì)值，計(jì)算這種情況下項(xiàng)目的總工期，以及項(xiàng)目在規(guī)定時(shí)間內(nèi)完成的可能性。229計(jì)劃評(píng)審技術(shù)計(jì)劃評(píng)審技術(shù)（PERT）與關(guān)鍵路徑法（CPM）方計(jì)劃評(píng)審技術(shù)計(jì)算步驟可以描述為：1-各個(gè)工序持續(xù)時(shí)間的估值計(jì)算，即多個(gè)時(shí)間數(shù)據(jù)的合成；2-應(yīng)用CPM方法計(jì)算得到項(xiàng)目的關(guān)鍵工序和關(guān)鍵路徑；3-計(jì)算關(guān)鍵工序以及關(guān)鍵路徑持續(xù)時(shí)間的波動(dòng)范圍；4-計(jì)算規(guī)定時(shí)間內(nèi)項(xiàng)目能夠完工的可能性概率。230計(jì)劃評(píng)審技術(shù)計(jì)算步驟可以描述為：230計(jì)劃評(píng)審技術(shù)在工程實(shí)踐中，工序持續(xù)時(shí)間的估計(jì)通常采用三點(diǎn)時(shí)間，即工序的最長持續(xù)時(shí)間b、最短持續(xù)時(shí)間a和最可能發(fā)生的持續(xù)時(shí)間m。而為了由此三個(gè)時(shí)間得到工序的單一持續(xù)時(shí)間估計(jì)值，通常的方法是取這三個(gè)值的加權(quán)平均值：231計(jì)劃評(píng)審技術(shù)在工程實(shí)踐中，工序持續(xù)時(shí)間的估計(jì)通常采用三點(diǎn)時(shí)間Excel求解關(guān)鍵路徑關(guān)鍵路徑為網(wǎng)絡(luò)計(jì)劃圖中總時(shí)間最長的一條從起點(diǎn)到終點(diǎn)的路線。因此，可以將關(guān)鍵路徑的計(jì)算看作是網(wǎng)絡(luò)中最“長”路徑選擇問題。232Excel求解關(guān)鍵路徑關(guān)鍵路徑為網(wǎng)絡(luò)計(jì)劃圖中總時(shí)間最長的一條M.S.Project軟件介紹233M.S.Project軟件介紹233人有了知識(shí)，就會(huì)具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋。”通過閱讀科技書籍，我們能豐富知識(shí)，培養(yǎng)邏輯思維能力；通過閱讀文學(xué)作品，我們能提高文學(xué)鑒賞水平，培養(yǎng)文學(xué)情趣；通過閱讀報(bào)刊，我們能增長見識(shí)，擴(kuò)大自己的知識(shí)面。有許多書籍還能培養(yǎng)我們的道德情操，給我們巨大的精神力量，鼓舞我們前進(jìn)。人有了知識(shí)，就會(huì)具備各種分析能力，工程碩士運(yùn)籌學(xué)及重點(diǎn)方案236工程碩士運(yùn)籌學(xué)

內(nèi)蒙古工業(yè)大學(xué)管理學(xué)院

1工程碩士運(yùn)籌學(xué)

內(nèi)蒙古工業(yè)大學(xué)管理學(xué)院

課程內(nèi)容緒論線性規(guī)劃基礎(chǔ)線性規(guī)劃的圖解法、用Excel解LP問題整數(shù)規(guī)劃運(yùn)輸問題目標(biāo)規(guī)劃圖論動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)計(jì)劃技術(shù)237課程內(nèi)容緒論2238第0章緒論

IntroductionstoOperationsResearch

3第0章緒論

IntroductionstoOperat運(yùn)籌學(xué)的實(shí)用價(jià)值公司應(yīng)用問題收益/效果惠普公司預(yù)測消費(fèi)者的購買行為，從而優(yōu)化庫存2009至2011年，創(chuàng)造了1.17億美元的收益中國工商銀行銀行網(wǎng)點(diǎn)的城市布局問題2006至2011年，蘇州因此增加了10.4億美元的存款I(lǐng)HG洲際酒店集團(tuán)解決酒店房間的定價(jià)問題2011年增加1.45億美元的收益，并預(yù)計(jì)推廣后未來每年將帶來4億美元的收益HubGroup哈勃貨運(yùn)集團(tuán)提高場地管理和集裝箱分配2008年收益增加了3%，獲得了1,100萬美元的凈匯報(bào)Petrobras優(yōu)化直升飛機(jī)在海上石油平臺(tái)之間的飛行路線每年節(jié)省超過2千萬美元239

ZARA（全球1500家門店）、P&G（15億）運(yùn)籌學(xué)的實(shí)用價(jià)值公司應(yīng)用問題收益/效果惠普公司預(yù)測消費(fèi)者的購240運(yùn)籌學(xué)學(xué)科特點(diǎn)1-

科學(xué)性它是在科學(xué)方法論的指導(dǎo)下通過一系列規(guī)范化步驟。5運(yùn)籌學(xué)學(xué)科特點(diǎn)1-科學(xué)性241運(yùn)籌學(xué)學(xué)科特點(diǎn)2-實(shí)踐性運(yùn)籌學(xué)以實(shí)際問題為分析對(duì)象；分析結(jié)果必須用于指導(dǎo)實(shí)際系統(tǒng)的運(yùn)行。適應(yīng)性和魯棒性Robustness，原是統(tǒng)計(jì)學(xué)中的一個(gè)專門術(shù)語，20世紀(jì)70年代初開始在控制理論的研究中流行起來，用以表征控制系統(tǒng)對(duì)特性或參數(shù)擾動(dòng)的不敏感性。即當(dāng)應(yīng)用問題的背景受到一定程度的干擾時(shí)，最優(yōu)解能夠繼續(xù)正常運(yùn)行的程度。6運(yùn)籌學(xué)學(xué)科特點(diǎn)2-實(shí)踐性242運(yùn)籌學(xué)學(xué)科特點(diǎn)3-系統(tǒng)性用系統(tǒng)的觀點(diǎn)來