物流運籌學(xué)與統(tǒng)籌規(guī)劃教材課件

復(fù)習(xí)提綱及重點內(nèi)容復(fù)習(xí)提綱及重點內(nèi)容1（一）物流運籌學(xué)（一）物流運籌學(xué)2第一章物流與運籌學(xué)概論1.2物流的概念界定、基本元素及其地位1.3物流運籌學(xué)第一章物流與運籌學(xué)概論1.2物流的概念界定、基本元素及其3第二章線性規(guī)劃2.1一般線性規(guī)劃問題及其數(shù)學(xué)模型第二章線性規(guī)劃2.1一般線性規(guī)劃問題及其數(shù)學(xué)模型4第三章整數(shù)規(guī)劃3.1整數(shù)規(guī)劃問題的提出3.2整數(shù)規(guī)劃概述3.5匈牙利法與指派問題第三章整數(shù)規(guī)劃3.1整數(shù)規(guī)劃問題的提出5例7：某物流公司現(xiàn)有四項運輸任務(wù)A、B、C、D，現(xiàn)有甲、乙、丙、丁四輛車，他們完成任務(wù)所需時間如表所示。問應(yīng)指派何人去完成何工作，使所需總時間最少？完成任務(wù)所需時間表任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119例7：某物流公司現(xiàn)有四項運輸任務(wù)A、B、C、D，現(xiàn)有甲、乙、6求解：匈牙利法

第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。

(1)從系數(shù)矩陣的每行元素減去該行的最小元素；

(2)再從所得系數(shù)矩陣的每列元素中減去該列的最小元素。

若某行(列)已有0元素，那就不必再減了。

例7的計算為

求解：匈牙利法第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行7行列都有零元素行列都有零元素8現(xiàn)用例7的(bij)矩陣，按上述步驟進(jìn)行運算。按步驟(1)，先給b22加圈，然后給b31加圈，劃掉b11，b41；按步驟(2)，給b43加圈，劃掉b44，最后給b14加圈，得到01370606905320100這表明：指定甲完成任務(wù)D，乙完成任務(wù)B，丙完成任務(wù)A，丁完成任務(wù)C。所需總時間最少minz=28ABCD甲乙丙丁現(xiàn)用例7的(bij)矩陣，按上述步驟進(jìn)行運算。按步驟(1)，9第四章物資運輸與調(diào)運問題4.2物流運輸系統(tǒng)規(guī)劃概述4.3物資調(diào)運問題及其模型4.4運輸問題的求解方法初始方案的選擇（最小元素法和西北角法）解的改進(jìn)（檢驗數(shù)計算，閉回路法）運量調(diào)整第四章物資運輸與調(diào)運問題4.2物流運輸系統(tǒng)規(guī)劃概述10例4-1調(diào)運問題建模（線性規(guī)劃模型）3個工廠向四個銷售地點銷售，如表，如何調(diào)運成本最?。坷?-1調(diào)運問題建模（線性規(guī)劃模型）3個工廠向四個銷11供應(yīng)地約束需求地約束解答供應(yīng)地約束需求地約束解答12最小元素法123467531113141842722131227155910631919022131213300000000020020最小元素法123467531113141842722131213初始基礎(chǔ)可行解—西北角法813131466000000初始基礎(chǔ)可行解—西北角法81313146600000014+5非基變量xij的檢驗數(shù)zij-cij—閉回路法(1)σ12=c12-c22+c21-c11=7-4+8-6=5+5非基變量xij的檢驗數(shù)zij-cij—閉回路法(1)σ115+5閉回路法(2)σ13=c13-c23+c21-c11=5-2+8-6=5+5+5閉回路法(2)σ13=c13-c23+c21-c11=516+5閉回路法(3)σ14=c13-c33+c32-c23+c21-c11

=3-6+10-2+8-6=7+7+5+5閉回路法(3)σ14=c13-c33+c32-c217選擇進(jìn)基變量,確定離基變量（運量調(diào)整）x31進(jìn)基,min{x21,x33}=min{8,6}=6,x33離基-3-5-5-7-9-11選擇進(jìn)基變量,確定離基變量（運量調(diào)整）x31進(jìn)基,min{18調(diào)整運量后的新運輸作業(yè)表調(diào)整運量后的新運輸作業(yè)表19第五章運輸路徑規(guī)劃5.1圖的基本概念最小生成樹的物理意義及其求解方法（破圈法、避圈法）5.2最短路問題（Dijkstra算法的步驟及求解）5.3網(wǎng)絡(luò)最大流問題

（網(wǎng)絡(luò)流、增廣鏈定義及其物理意義）第五章運輸路徑規(guī)劃5.1圖的基本概念20Dijkstra算法的步驟：1、給起始點標(biāo)記固定標(biāo)號P，標(biāo)號值記為0，2、考察與（0）相鄰的各點，修改其臨時標(biāo)號值，數(shù)值為出發(fā)點的固定標(biāo)號值+出發(fā)點到該點的權(quán)重。不相鄰的點，標(biāo)號值記為∞3、從所有的臨時標(biāo)號里面找出最小的確定為固定標(biāo)號4、從新得到的固定標(biāo)號出發(fā)，修改其相鄰點的臨時標(biāo)號。若原來已有臨時標(biāo)號，則比較原值與修改值的大小，取最小值5、重復(fù)3-4，直到所有頂點被標(biāo)記。最后，根據(jù)最小路權(quán)，逆推得到最短路徑。Dijkstra算法的步驟：1、給起始點標(biāo)記固定標(biāo)號P，標(biāo)號21思考題：下圖是某地區(qū)交通運輸示意圖，弧旁數(shù)字表示相應(yīng)兩地間的公路里程（公里）。問，從1出發(fā)，經(jīng)過哪條路線到達(dá)8，才能使總行程最短。72415366765335138425192思考題：下圖是某地區(qū)交通運輸示意圖，弧旁數(shù)字表示相應(yīng)兩地22解答：因此，可知最短路為13，逆推回去可知經(jīng)過的路徑為8←7←6←3←1或8←7←6←2←17241536676533513842519203561071116138解答：因此，可知最短路為13，逆推回去可知經(jīng)過的路徑為8←723存在增廣鏈μ：1→2→4→71243576（13，5）（5，3）（9，3）（4，1）（5，2）（5，0）（6，3）（6，2）（4，2）（4，1）（10，1）（9，5）存在增廣鏈μ：1→2→4→3→6→7存在增廣鏈μ：1→2→4→71243576（13，5）（5，24（二）物流系統(tǒng)規(guī)劃（二）物流系統(tǒng)規(guī)劃25第一章物流系統(tǒng)及其規(guī)劃概述1.2物流系統(tǒng)規(guī)劃與設(shè)計基本理論（1.2.1---1.2.3）第一章物流系統(tǒng)及其規(guī)劃概述1.2物流系統(tǒng)規(guī)劃與設(shè)計基本理26第三章物流節(jié)點規(guī)劃設(shè)計3.4區(qū)域布置方法圖形構(gòu)建法的算法——節(jié)點插入法第三章物流節(jié)點規(guī)劃設(shè)計3.4區(qū)域布置方法27練習(xí)：某物流中心作業(yè)區(qū)的定量從至圖如圖所示，用節(jié)點插入法完成下面例題的布置物流量到地區(qū)域12345起始區(qū)域15450247343987042610252402步驟：1.選取具有最大權(quán)數(shù)的關(guān)聯(lián)作業(yè)區(qū)對； 2.選取與已進(jìn)入布置的作業(yè)區(qū)具有最大權(quán)數(shù)的作業(yè)區(qū)，成三角布置； 3.再選擇，插入三角區(qū)，直至布置完所有的作業(yè)區(qū)練習(xí)：某物流中心作業(yè)區(qū)的定量從至圖如圖所示，用節(jié)點插入法完成28第四章物流節(jié)點選址4.1物流節(jié)點選址概述4.1.3規(guī)劃選擇的步驟4.1.4物流節(jié)點選址布局方法4.2單物流節(jié)點選址（重心法）第四章物流節(jié)點選址4.1物流節(jié)點選址概述29例2擬建物流中心，有四個原材料供應(yīng)地，試用重心法求該物流中心的位置求解：原料供應(yīng)地P1P2P3P4x1y1x2y2x3y3x4y4坐標(biāo)位置2070606020205020年運輸量2000120010002500

20×2000+60×1200+20×1000+50×2500x0=——————————————————————=38.42000+1200+1000+2500

70×2000+60×1200+20×1000+20×2500y0=——————————————————————=42.12000+1200+1000+2500例2擬建物流中心，有四個原材料供應(yīng)地，試用重心法求該物流中30復(fù)習(xí)提綱及重點內(nèi)容復(fù)習(xí)提綱及重點內(nèi)容31（一）物流運籌學(xué)（一）物流運籌學(xué)32第一章物流與運籌學(xué)概論1.2物流的概念界定、基本元素及其地位1.3物流運籌學(xué)第一章物流與運籌學(xué)概論1.2物流的概念界定、基本元素及其33第二章線性規(guī)劃2.1一般線性規(guī)劃問題及其數(shù)學(xué)模型第二章線性規(guī)劃2.1一般線性規(guī)劃問題及其數(shù)學(xué)模型34第三章整數(shù)規(guī)劃3.1整數(shù)規(guī)劃問題的提出3.2整數(shù)規(guī)劃概述3.5匈牙利法與指派問題第三章整數(shù)規(guī)劃3.1整數(shù)規(guī)劃問題的提出35例7：某物流公司現(xiàn)有四項運輸任務(wù)A、B、C、D，現(xiàn)有甲、乙、丙、丁四輛車，他們完成任務(wù)所需時間如表所示。問應(yīng)指派何人去完成何工作，使所需總時間最少？完成任務(wù)所需時間表任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119例7：某物流公司現(xiàn)有四項運輸任務(wù)A、B、C、D，現(xiàn)有甲、乙、36求解：匈牙利法

第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。

(1)從系數(shù)矩陣的每行元素減去該行的最小元素；

(2)再從所得系數(shù)矩陣的每列元素中減去該列的最小元素。

若某行(列)已有0元素，那就不必再減了。

例7的計算為

求解：匈牙利法第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行37行列都有零元素行列都有零元素38現(xiàn)用例7的(bij)矩陣，按上述步驟進(jìn)行運算。按步驟(1)，先給b22加圈，然后給b31加圈，劃掉b11，b41；按步驟(2)，給b43加圈，劃掉b44，最后給b14加圈，得到01370606905320100這表明：指定甲完成任務(wù)D，乙完成任務(wù)B，丙完成任務(wù)A，丁完成任務(wù)C。所需總時間最少minz=28ABCD甲乙丙丁現(xiàn)用例7的(bij)矩陣，按上述步驟進(jìn)行運算。按步驟(1)，39第四章物資運輸與調(diào)運問題4.2物流運輸系統(tǒng)規(guī)劃概述4.3物資調(diào)運問題及其模型4.4運輸問題的求解方法初始方案的選擇（最小元素法和西北角法）解的改進(jìn)（檢驗數(shù)計算，閉回路法）運量調(diào)整第四章物資運輸與調(diào)運問題4.2物流運輸系統(tǒng)規(guī)劃概述40例4-1調(diào)運問題建模（線性規(guī)劃模型）3個工廠向四個銷售地點銷售，如表，如何調(diào)運成本最??？例4-1調(diào)運問題建模（線性規(guī)劃模型）3個工廠向四個銷41供應(yīng)地約束需求地約束解答供應(yīng)地約束需求地約束解答42最小元素法123467531113141842722131227155910631919022131213300000000020020最小元素法123467531113141842722131243初始基礎(chǔ)可行解—西北角法813131466000000初始基礎(chǔ)可行解—西北角法81313146600000044+5非基變量xij的檢驗數(shù)zij-cij—閉回路法(1)σ12=c12-c22+c21-c11=7-4+8-6=5+5非基變量xij的檢驗數(shù)zij-cij—閉回路法(1)σ145+5閉回路法(2)σ13=c13-c23+c21-c11=5-2+8-6=5+5+5閉回路法(2)σ13=c13-c23+c21-c11=546+5閉回路法(3)σ14=c13-c33+c32-c23+c21-c11

=3-6+10-2+8-6=7+7+5+5閉回路法(3)σ14=c13-c33+c32-c247選擇進(jìn)基變量,確定離基變量（運量調(diào)整）x31進(jìn)基,min{x21,x33}=min{8,6}=6,x33離基-3-5-5-7-9-11選擇進(jìn)基變量,確定離基變量（運量調(diào)整）x31進(jìn)基,min{48調(diào)整運量后的新運輸作業(yè)表調(diào)整運量后的新運輸作業(yè)表49第五章運輸路徑規(guī)劃5.1圖的基本概念最小生成樹的物理意義及其求解方法（破圈法、避圈法）5.2最短路問題（Dijkstra算法的步驟及求解）5.3網(wǎng)絡(luò)最大流問題

（網(wǎng)絡(luò)流、增廣鏈定義及其物理意義）第五章運輸路徑規(guī)劃5.1圖的基本概念50Dijkstra算法的步驟：1、給起始點標(biāo)記固定標(biāo)號P，標(biāo)號值記為0，2、考察與（0）相鄰的各點，修改其臨時標(biāo)號值，數(shù)值為出發(fā)點的固定標(biāo)號值+出發(fā)點到該點的權(quán)重。不相鄰的點，標(biāo)號值記為∞3、從所有的臨時標(biāo)號里面找出最小的確定為固定標(biāo)號4、從新得到的固定標(biāo)號出發(fā)，修改其相鄰點的臨時標(biāo)號。若原來已有臨時標(biāo)號，則比較原值與修改值的大小，取最小值5、重復(fù)3-4，直到所有頂點被標(biāo)記。最后，根據(jù)最小路權(quán)，逆推得到最短路徑。Dijkstra算法的步驟：1、給起始點標(biāo)記固定標(biāo)號P，標(biāo)號51思考題：下圖是某地區(qū)交通運輸示意圖，弧旁數(shù)字表示相應(yīng)兩地間的公路里程（公里）。問，從1出發(fā)，經(jīng)過哪條路線到達(dá)8，才能使總行程最短。72415366765335138425192思考題：下圖是某地區(qū)交通運輸示意圖，弧旁數(shù)字表示相應(yīng)兩地52解答：因此，可知最短路為13，逆推回去可知經(jīng)過的路徑為8←7←6←3←1或8←7←6←2←17241536676533513842519203561071116138解答：因此，可知最短路為13，逆推回去可知經(jīng)過的路徑為8←753存在增廣鏈μ：1→2→4→71243576（13，5）（5，3）（9，3）（4，1）（5，2）（5，0）（6，3）（6，2）（4，2）（4，1）（10，1）（9，5）存在增廣鏈μ：1→2→4→3→6→7存在增廣鏈μ：1→2→4→71243576（13，5）（5，54（二）物流系統(tǒng)規(guī)劃（二）物流系統(tǒng)規(guī)劃55第一章物流系統(tǒng)及其規(guī)劃概述1.2物流系統(tǒng)規(guī)劃與設(shè)計基本理論（1.2.1---1.2.3）第一章物流系統(tǒng)及其規(guī)劃概述1.2物流系統(tǒng)規(guī)劃與設(shè)計基本理56第三章物流節(jié)點規(guī)劃設(shè)計3.4區(qū)域布置方法圖形構(gòu)建法的算法——節(jié)點插入法第三章物流節(jié)點規(guī)劃設(shè)計3.4區(qū)域布置方法57練習(xí)：某物流中心作業(yè)區(qū)的定量從至圖如圖所示，用節(jié)