運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題求解

主講教師：孫君楊葉勇宋曉明無(wú)錫商業(yè)職業(yè)技術(shù)學(xué)院供應(yīng)鏈數(shù)據(jù)分析運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模與求解圖與網(wǎng)絡(luò)網(wǎng)絡(luò)流量、網(wǎng)絡(luò)最大流線性規(guī)劃法建立網(wǎng)絡(luò)最大流問(wèn)題模型010203EXCEL工具求解網(wǎng)絡(luò)最大流問(wèn)題模型04學(xué)習(xí)目標(biāo)

●了解圖與網(wǎng)絡(luò)的基本概念●理解網(wǎng)絡(luò)流量、網(wǎng)絡(luò)最大流問(wèn)題●掌握線性規(guī)劃法建立網(wǎng)絡(luò)最大流問(wèn)題模型●掌握EXCEL工具求解網(wǎng)絡(luò)最大流問(wèn)題模型項(xiàng)目任務(wù)學(xué)習(xí)目標(biāo)

《供應(yīng)鏈數(shù)據(jù)分析》商學(xué)院物流管理教研室●線性規(guī)劃法建立網(wǎng)絡(luò)最大流問(wèn)題模型●EXCEL工具求解網(wǎng)絡(luò)最大流問(wèn)題模型學(xué)習(xí)目標(biāo)

●了解圖與網(wǎng)絡(luò)的基本概念●理解網(wǎng)絡(luò)流量、網(wǎng)絡(luò)最大流問(wèn)題●掌握線性規(guī)劃法建立網(wǎng)絡(luò)最大流問(wèn)題模型●掌握EXCEL工具求解網(wǎng)絡(luò)最大流問(wèn)題模型學(xué)習(xí)任務(wù)●線性規(guī)劃法建立網(wǎng)絡(luò)最大流問(wèn)題模型●EXCEL工具求解網(wǎng)絡(luò)最大流問(wèn)題模型圖與網(wǎng)絡(luò)的基本概念

網(wǎng)絡(luò)最大流問(wèn)題網(wǎng)絡(luò)流量(flowproblem)是指在選定時(shí)間段內(nèi)通過(guò)道路某一地點(diǎn)、某一斷面或某一車道的實(shí)體數(shù)，也叫交通流量。最大流問(wèn)題(maximumflowproblem)，一種組合最優(yōu)化問(wèn)題，就是要討論如何充分利用裝置的能力，使得運(yùn)輸?shù)牧髁孔畲?，以取得最好的效果。求最大流的?biāo)號(hào)算法最早由福特和?？诉d與與1956年提出，20世紀(jì)50年代福特(Ford)、(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成成分。運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解以“實(shí)訓(xùn)任務(wù)南洋東郊運(yùn)輸網(wǎng)絡(luò)最大流”為例：Step1

建立運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題模型

Step2

EXCEL工具求解運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題模型

運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

實(shí)訓(xùn)任務(wù)南洋東郊運(yùn)輸網(wǎng)絡(luò)最大流南洋市東郊交通網(wǎng)絡(luò)如圖所示，試求出該地區(qū)網(wǎng)絡(luò)最大流（從V1入口流入東效運(yùn)輸網(wǎng)絡(luò)的車流量）。括號(hào)里第一個(gè)數(shù)字代表該公路最大允許的車流量，第二個(gè)數(shù)字表示當(dāng)下的車流量。參考解決辦法：Step1建立線性規(guī)劃模型Step1.1分析確定目標(biāo)函數(shù)，確定決策變量*網(wǎng)絡(luò)流入量和、或流出量和最大，用表示*各路段邊的最大流量為決策變量，用表示則目標(biāo)函數(shù)為：這里，選擇流入量和的最大化為問(wèn)題目標(biāo)。運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step1.2確定約束條件-第一類約束條件為：每個(gè)路段要求的最大流量不大于路段容量，12個(gè)路段就得有12個(gè)約束條件，即：運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step1.2確定約束條件-第二類約束條件是流量守恒約束：-整個(gè)網(wǎng)絡(luò)流入量的和要與流出量的和相等，也是遵循流量守恒定律，即：運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step1.2確定約束條件-每個(gè)路段上的流量非負(fù)約束，即運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

-完整的運(yùn)輸網(wǎng)絡(luò)最大流模型為：Step2EXCEL工具求解規(guī)劃模型Step2.1向EXCEL表導(dǎo)入各邊的容量數(shù)據(jù)Step2.2構(gòu)建模型框架Step2.2.1目標(biāo)函數(shù)單元格中輸入：流入量和，或者流出量和Step2.2.2設(shè)計(jì)節(jié)點(diǎn)約束條件Step2.2.3設(shè)計(jì)流量約束條件Step2.2.4增加基礎(chǔ)約束條件Step2.3運(yùn)用規(guī)劃求解工具求解Step2.3.1工具-加載宏：選擇規(guī)劃求解Step2.3.2輸入目標(biāo)函數(shù)單元格Step2.3.3選擇最大值/最小值Step2.3.4輸入可變（決策）單元格區(qū)域Step2.3.5添加輸入約束條件Step2.3.6確定，保存規(guī)劃求解結(jié)果運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step2.1向EXCEL表導(dǎo)入各邊的容量數(shù)據(jù)運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step2.2構(gòu)建模型框架設(shè)置決策變量區(qū)域：B34：M34黃色區(qū)域，運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step2.2構(gòu)建模型框架Step2.2.1目標(biāo)函數(shù)單元格中輸入：流入量和，或者流出量和設(shè)置目標(biāo)函數(shù)：在單元格B32中輸入目標(biāo)函數(shù)“=B34+C34”，即f12、f13的流入量和。運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step2.2構(gòu)建模型框架Step2.2.3設(shè)計(jì)流量約束條件根據(jù)模型，流量守恒的6個(gè)約束條件有計(jì)算要求，即每個(gè)節(jié)點(diǎn)的流入量、流出量要求和。運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

以V2節(jié)點(diǎn)為例，流入量和=f12+f32;流出量和=f24+f25規(guī)劃求解工具中沒(méi)有計(jì)算功能，只能直接調(diào)用單元格，因此相關(guān)中間計(jì)算工作或數(shù)據(jù)之間的關(guān)系就要先在EXCEL表中完成。Step2EXCEL工具求解規(guī)劃模型Step2.3運(yùn)用規(guī)劃求解工具求解Step2.3.1工具-加載宏：選擇規(guī)劃求解單擊“數(shù)據(jù)”工具欄，選擇“規(guī)劃求解”。運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step2EXCEL工具求解規(guī)劃模型Step2.3運(yùn)用規(guī)劃求解工具求解Step2.3.1工具-加載宏：選擇規(guī)劃求解運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

Step2.3運(yùn)用規(guī)劃求解工具求解Step2.3.2輸入目標(biāo)函數(shù)單元格Step2.3.3選擇最大值/最小值Step2.3.4輸入可變（決策）單元格區(qū)域Step2.3.5添加輸入約束條件Step2.3.6確定，保存規(guī)劃求解結(jié)果運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

求解完成。決策區(qū)域求出的解和目標(biāo)值都已產(chǎn)生，約束條件都成立。運(yùn)輸網(wǎng)絡(luò)最大流問(wèn)題建模求解

小結(jié)：南洋市東郊網(wǎng)