物流運(yùn)籌學(xué)與統(tǒng)籌規(guī)劃

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

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

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

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

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

例7的計(jì)算為

行列都有零元素現(xiàn)用例7的(bij)矩陣，按上述步驟進(jìn)行運(yùn)算。按步驟(1)，先給b22加圈，然后給b31加圈，劃掉b11，b41；按步驟(2)，給b43加圈，劃掉b44，最后給b14加圈，得到01370606905320100這表明：指定甲完成任務(wù)D，乙完成任務(wù)B，丙完成任務(wù)A，丁完成任務(wù)C。所需總時(shí)間最少minz=28ABCD甲乙丙丁第四章物資運(yùn)輸與調(diào)運(yùn)問題4.2物流運(yùn)輸系統(tǒng)規(guī)劃概述4.3物資調(diào)運(yùn)問題及其模型4.4運(yùn)輸問題的求解方法初始方案的選擇（最小元素法和西北角法）解的改進(jìn)（檢驗(yàn)數(shù)計(jì)算，閉回路法）運(yùn)量調(diào)整例4-1調(diào)運(yùn)運(yùn)問題建建模（線線性規(guī)劃劃模型））3個(gè)工廠廠向四個(gè)個(gè)銷售地地點(diǎn)銷售售，如表表，如何何調(diào)運(yùn)成成本最小??？供應(yīng)地約約束需求地約約束解答最小元素素法123467531113141842722131227155910631919022131213300000000020020初始基礎(chǔ)礎(chǔ)可行解解—西北北角法813131466000000+5非基變量量xij的檢驗(yàn)數(shù)數(shù)zij-cij—閉回路路法(1)σ12=c12-c22+c21-c11=7-4+8-6=5+5閉回路法法(2)σ13=c13-c23+c21-c11=5-2+8-6=5+5+5閉回路法法(3)σ14=c13-c33+c32-c23+c21-c11=3-6+10-2+8-6=7+7+5選擇進(jìn)基基變量,確定離離基變量量（運(yùn)量量調(diào)整））x31進(jìn)基,min{x21,x33}=min{8,6}=6,x33離基-3-5-5-7-9-11調(diào)整運(yùn)量量后的新新運(yùn)輸作作業(yè)表第五章運(yùn)運(yùn)輸路路徑規(guī)劃劃5.1圖圖的基基本概念念最小生成成樹的物物理意義義及其求求解方法法（破圈圈法、避避圈法））5.2最最短路路問題（（Dijkstra算算法的步步驟及求求解）5.3網(wǎng)網(wǎng)絡(luò)最最大流問問題（網(wǎng)絡(luò)流流、增廣廣鏈定義義及其物物理意義義）Dijkstra算法法的步驟驟：1、給起起始點(diǎn)標(biāo)標(biāo)記固定定標(biāo)號(hào)P，標(biāo)號(hào)號(hào)值記為為0，2、考察察與（0）相鄰鄰的各點(diǎn)點(diǎn)，修改改其臨時(shí)時(shí)標(biāo)號(hào)值值，數(shù)值值為出發(fā)發(fā)點(diǎn)的固固定標(biāo)號(hào)號(hào)值+出出發(fā)點(diǎn)到到該點(diǎn)的的權(quán)重。。不相鄰鄰的點(diǎn)，，標(biāo)號(hào)值值記為∞∞3、從所所有的臨臨時(shí)標(biāo)號(hào)號(hào)里面找找出最小小的確定定為固定定標(biāo)號(hào)4、從新新得到的的固定標(biāo)標(biāo)號(hào)出發(fā)發(fā)，修改改其相鄰鄰點(diǎn)的臨臨時(shí)標(biāo)號(hào)號(hào)。若原原來已有有臨時(shí)標(biāo)標(biāo)號(hào)，則則比較原原值與修修改值的的大小，，取最小小值5、重復(fù)復(fù)3-4，直到到所有頂頂點(diǎn)被標(biāo)標(biāo)記。最后，根根據(jù)最小小路權(quán)，，逆推得得到最短短路徑。。思考題：：下圖是某某地區(qū)交交通運(yùn)輸輸示意圖圖，弧旁旁數(shù)字表表示相應(yīng)應(yīng)兩地間間的公路路里程（（公里））。問，，從1出出發(fā)，經(jīng)經(jīng)過哪條條路線到到達(dá)8，，才能使使總行程程最短。。72415366765335138425192解答：因此，可可知最短短路為13，逆逆推回去去可知經(jīng)經(jīng)過的路路徑為8←7←←6←3←1或或8←7←6←←2←17241536676533513842519203561071116138存在增廣廣鏈μ：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（二）物物流系統(tǒng)統(tǒng)規(guī)劃第一章物物流系系統(tǒng)及其其規(guī)劃概概述1.2物物流系系統(tǒng)規(guī)劃劃與設(shè)計(jì)計(jì)基本理理論（1.2.1---1.2.3）第三章物物流節(jié)節(jié)點(diǎn)規(guī)劃劃設(shè)計(jì)3.4區(qū)區(qū)域布布置方法法圖形構(gòu)建建法的算算法———節(jié)點(diǎn)插插入法練習(xí)：某物流中中心作業(yè)業(yè)區(qū)的定定量從至至圖如圖圖所示，，用節(jié)點(diǎn)點(diǎn)插入法法完成下下面例題題的布置置物流量到地區(qū)域12345起始區(qū)域15450247343987042610252402步驟：1.選取具具有最大大權(quán)數(shù)的的關(guān)聯(lián)作作業(yè)區(qū)對(duì)對(duì)；2.選取取與已進(jìn)進(jìn)入布置置的作業(yè)業(yè)區(qū)具有有最大權(quán)權(quán)數(shù)的作作業(yè)區(qū)，，成三角角布置；；3.再選選擇，插插入三角角區(qū)，直直至布置置完所有有的作業(yè)業(yè)區(qū)第四章物物流節(jié)節(jié)點(diǎn)選址址4.1物物流節(jié)節(jié)點(diǎn)選址址概述4.1.3規(guī)規(guī)劃選擇擇的步驟驟4.1.4物物流節(jié)點(diǎn)點(diǎn)選址布布局方法法4.2單單物流流節(jié)點(diǎn)選選址（重重心法））例2擬擬建物流流中心，，有四個(gè)個(gè)原材料料供應(yīng)地地，試用用重心法法求該物物流中心心的位置置求解：原料供應(yīng)地P1P2P3P4x1y1x2y2x3y3x4y4坐標(biāo)位置2070606020205020年運(yùn)輸量200012001000250020×2000+60×1200+20××1000+50×2500x0=———————