第八講 網(wǎng)絡(luò)最優(yōu)化模型.ppt

1、第八屆網(wǎng)絡(luò)優(yōu)化模型，實(shí)用管理運(yùn)營(yíng)學(xué)-基于excel求解器和求解模板，第八屆網(wǎng)絡(luò)優(yōu)化模型，本文主要討論的問(wèn)題，1，網(wǎng)絡(luò)優(yōu)化模型的基本概念，2，最小支撐樹(shù)模型，3，最大流模型，4，最小1 趙(v1)、金(v2)、孫(v3)、李(v4)、王(v7)、趙(v1)、金(v2)、孫(v3)、李(v4)、周(v5)、吳(v5)在人群中互相認(rèn)識(shí)的關(guān)系圖-無(wú)向權(quán)利圖、王(v7)、王(v7)。 在第八屆網(wǎng)絡(luò)優(yōu)化模型、基本概念、圖、圖、5、循環(huán)、無(wú)向圖中，起點(diǎn)和終點(diǎn)重疊的鏈?zhǔn)且粋€(gè)循環(huán)。 上圖中(v1、v2、v3、v1)為一圈。在第八屆網(wǎng)絡(luò)優(yōu)化模型、基本概念、圖、6、道路、有向圖(或無(wú)向圖)中，點(diǎn)和弧(或邊)的交替排

2、列，但點(diǎn)和邊不能重疊。 在上圖中，(v1、v2、v3、v4)是道路。第八屆網(wǎng)絡(luò)優(yōu)化模型、基本概念、圖、圖、7、電路、起點(diǎn)和終點(diǎn)重疊的道路稱為電路。 上圖中的(v3、v5、v6、v7、v4、v3)是電路。 另外，對(duì)于第八網(wǎng)絡(luò)優(yōu)化模型、基本概念、圖、8、連通圖，只要是一個(gè)圖，在任意2點(diǎn)之間存在至少一條鏈，并且將這種圖稱為連通圖。 下圖為非連通圖。 第八次網(wǎng)絡(luò)優(yōu)化模型，基本概念，圖，9，樹(shù)，樹(shù)是無(wú)旋轉(zhuǎn)的連通圖，、王(v7)、趙(v1)、金錢。 另一點(diǎn)稱為收集點(diǎn)(或宿，記為vt )，其馀的點(diǎn)稱為中間點(diǎn)，圖中各弧的加權(quán)數(shù)cij稱為弧(vi，vj )的容量，這樣的加權(quán)有向圖稱為網(wǎng)絡(luò)。 網(wǎng)絡(luò)優(yōu)化問(wèn)題基本上是

3、基于這種網(wǎng)絡(luò)構(gòu)建對(duì)應(yīng)的網(wǎng)絡(luò)模型，并且獲得最大值或最小值。 第八屆網(wǎng)絡(luò)優(yōu)化模型、基本概念、網(wǎng)絡(luò)優(yōu)化問(wèn)題的主要特征、1、最短模型、2、最小費(fèi)用流模型、3、最小支撐樹(shù)模型、4、最大流模型、5、最小費(fèi)用最大流模型、可研究模型： 目標(biāo)是通過(guò)網(wǎng)絡(luò)找到一條路，使兩點(diǎn)之間的總距離最短。第八屆網(wǎng)絡(luò)優(yōu)化模型，最短路模型，例8.1如下圖所示，有的人每天從家s開(kāi)車上班到工作單位t，圖中各弧旁的數(shù)字表示道路的長(zhǎng)度(公里)，詢問(wèn)從家到工作單位應(yīng)該選擇哪條路線。第八屆網(wǎng)絡(luò)優(yōu)化模型、最短路模型、最短路模型的基本特征、1、從網(wǎng)絡(luò)中選擇一條路，將起點(diǎn)(源點(diǎn))、終點(diǎn)(目的地)、2、連接兩個(gè)節(jié)點(diǎn)的鏈路稱為邊(允許向任一方向行進(jìn))或3

4、 .邊(允許向任一方向行進(jìn)) 所表示的路徑長(zhǎng)度，第八次網(wǎng)絡(luò)優(yōu)化模型、最短路徑模型、最短路徑模型的求解，在例8.1的圖中，兩個(gè)節(jié)點(diǎn)的路徑可以被認(rèn)為是有向的，可以變更為如下模式圖的第八次網(wǎng)絡(luò)優(yōu)化模型、最短路徑模型、最短路徑模型的求解建立了專業(yè)的最短求解模型，可以用修正機(jī)求解：將圖中各邊和各邊的權(quán)重直接輸入求解模型，可以得到直接結(jié)果。 因此，下圖可以說(shuō)是最短路問(wèn)題的數(shù)學(xué)表現(xiàn)模型。 創(chuàng)建第八網(wǎng)絡(luò)優(yōu)化模型、最短路模型、最短路模型的關(guān)鍵是創(chuàng)建系統(tǒng)的網(wǎng)絡(luò)圖、第八網(wǎng)絡(luò)優(yōu)化模型、最短路模型、例8.2設(shè)備更新問(wèn)題。 有一家工廠的機(jī)器可以連續(xù)工作五年，決策者必須決定每年年初是否需要更新機(jī)器。 如果購(gòu)買新機(jī)器，必須支

5、付購(gòu)買費(fèi)用；如果繼續(xù)使用，必須支付維護(hù)和運(yùn)行成本，并且隨著機(jī)器使用年限的增加，費(fèi)用逐年增加。 修訂期(5年)的年購(gòu)買價(jià)格、修理和運(yùn)行成本如下表所示。 制定今后5年的機(jī)器更新修訂計(jì)劃，試著使總支付費(fèi)用達(dá)到最小。 購(gòu)買價(jià)格和維修和運(yùn)行成本，第八次網(wǎng)絡(luò)優(yōu)化模型，最短路模型，設(shè)備使用年限總費(fèi)用分布情況表單位：萬(wàn)元，第八次網(wǎng)絡(luò)優(yōu)化模型，最短路模型，網(wǎng)絡(luò)圖，第八次網(wǎng)絡(luò)優(yōu)化模型，最短路模型第四年初購(gòu)買新機(jī)器支付的費(fèi)用是最低的。 最短路線(支付的最低費(fèi)用)為53 (萬(wàn)元)。第八次網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用流模型、最小費(fèi)用流模型需要解決的問(wèn)題：對(duì)有向授權(quán)圖指定多個(gè)發(fā)行點(diǎn)和多個(gè)接收點(diǎn)。 我們的目標(biāo)是通過(guò)網(wǎng)絡(luò)確定每個(gè)網(wǎng)

6、絡(luò)上的通信量，并最大限度地減少?gòu)乃谐霭l(fā)點(diǎn)到所有接收點(diǎn)的總通信量費(fèi)用。第八屆網(wǎng)絡(luò)優(yōu)化模型，最小費(fèi)用流模型，例8.3某公司有兩個(gè)工廠生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運(yùn)輸?shù)絻蓚€(gè)倉(cāng)庫(kù)，其配送網(wǎng)絡(luò)如下圖所示(產(chǎn)品數(shù)量單位：件； 費(fèi)用單位：元)。 目標(biāo)是確定一個(gè)運(yùn)輸方案(即通過(guò)每條路線運(yùn)輸多少個(gè)產(chǎn)品)，以最大限度地減少通過(guò)運(yùn)輸網(wǎng)絡(luò)的運(yùn)輸成本。第八次網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用流模型、最小費(fèi)用流模型的基本特征、最小費(fèi)用流問(wèn)題的配置(網(wǎng)絡(luò)表示)、節(jié)點(diǎn)：供應(yīng)點(diǎn)、需求點(diǎn)和運(yùn)輸點(diǎn)、最小費(fèi)用流問(wèn)題的假設(shè)、至少一個(gè)供應(yīng)點(diǎn)、至少一個(gè)需求點(diǎn)目標(biāo)包括總成本最小(或總利潤(rùn)最大)、最小費(fèi)用流問(wèn)題解的特征、可行解的特征、整數(shù)解的特征、弧：可行線

7、路、流量限制、費(fèi)用。、第八次網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用流模型、最小費(fèi)用流模型的求解、解決最小費(fèi)用流問(wèn)題，實(shí)際確定網(wǎng)絡(luò)圖的各路徑上的通信量，使總通信量花費(fèi)最小。 因此，可以創(chuàng)建純整數(shù)修正圖數(shù)學(xué)模型的解，如下圖所示。 總費(fèi)用流： 104000 (元)、第八次網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用流模型、最小費(fèi)用流模型的求解與最短路模型一樣，建立最小費(fèi)用流求解模型，將圖中各邊和各邊的權(quán)重直接輸入到求解模型中，實(shí)現(xiàn)修正計(jì)算機(jī)求解。 因此，下圖可以說(shuō)是最小費(fèi)用流問(wèn)題的數(shù)學(xué)表示模型。第八屆網(wǎng)絡(luò)優(yōu)化模型、最大流模型、最大流模型需要解決的問(wèn)題：在有向授權(quán)地圖中指定發(fā)起點(diǎn)和接收點(diǎn)。 我們的目標(biāo)是通過(guò)網(wǎng)絡(luò)確定每個(gè)網(wǎng)絡(luò)上的通信量，使從

8、出發(fā)點(diǎn)到接收點(diǎn)的總通信量最大化。第八屆網(wǎng)絡(luò)優(yōu)化模型、最大流量模型，例8.4某石油公司擁有管線網(wǎng)絡(luò)，可以使用該管線網(wǎng)絡(luò)將石油從采油廠運(yùn)到幾個(gè)銷售點(diǎn)，該網(wǎng)絡(luò)的一部分如下圖所示。 根據(jù)配管的直徑，各段配管的流量也不同。 圖中各圓弧(各段配管)顯示的數(shù)字是該段配管的最大流量(噸/小時(shí))。 使用該網(wǎng)絡(luò)系統(tǒng)從采油廠VS向銷售地VT輸送石油，每小時(shí)最多可以輸送多少噸石油，第八次網(wǎng)絡(luò)優(yōu)化模型，最大流量模型，最大流量模型的基本特征是，1，網(wǎng)絡(luò)中的所有流量都是起點(diǎn)(來(lái)源2、其馀的節(jié)點(diǎn)稱為運(yùn)輸點(diǎn)，3、通過(guò)各弧的流僅沿弧的箭頭方向流動(dòng)，因此，如下圖所示，也可建立純整數(shù)修正圖數(shù)學(xué)模型進(jìn)行解決。 最佳值maxz=150，

9、30，20，20，30，10，30，0，30，50，40，30，30，40，第八次網(wǎng)絡(luò)優(yōu)化模型，最大流，因此下面的視圖可以說(shuō)是最大流問(wèn)題的數(shù)學(xué)表示模型。 求解最大流模型，第八次網(wǎng)絡(luò)優(yōu)化模型，最小費(fèi)用流模型，例8.5修訂編制問(wèn)題。 一家市政工程公司需要在5月8日完成4項(xiàng)工程：地下通道建設(shè)、人行橫道建設(shè)、道路和道路建設(shè)。 工期和所需勞動(dòng)力如下表所示。 該公司勞動(dòng)力120人，任何工程一個(gè)月內(nèi)的勞動(dòng)力投入不得超過(guò)80人。 公司如何分配勞動(dòng)力完成所有工程，能否按時(shí)完成？ 工期和必要?jiǎng)趧?dòng)力、第八次網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用流模型、可按需繪制的網(wǎng)絡(luò)圖如下： 圖中33:s表示工程結(jié)束5、月6、月7、月8、月a、工

10、程b、工程d、工程d，求出第八次網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用流模型，結(jié)果如下表3360每月的勞動(dòng)力分配結(jié)果、最佳值3360 最小費(fèi)用最大流模型、最小費(fèi)用最大流模型需要解決的問(wèn)題：在有向權(quán)限圖中指定發(fā)行點(diǎn)和接收點(diǎn)。 目標(biāo)是在網(wǎng)絡(luò)內(nèi)的系統(tǒng)中不僅運(yùn)輸量最大，而且總費(fèi)用最小。 第八屆網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用最大流模型，例8.6某石油公司擁有管線網(wǎng)絡(luò)，可以使用該管線網(wǎng)絡(luò)將石油從采油廠Vs輸送到幾個(gè)銷售點(diǎn)Vt，該網(wǎng)絡(luò)的一部分如下圖所示。 由于管徑不同，管線的長(zhǎng)度也不同，所以各段的管線除了流量不同外，每單位流量的費(fèi)用也不同。在圖中各圓弧(各管)旁邊的括弧中，前面的數(shù)字是該段管的最大流量(噸/小時(shí))，下面的數(shù)字是該段

11、管的單位流量的費(fèi)用(meta /噸)。 網(wǎng)絡(luò)系統(tǒng)中運(yùn)輸石油最多，總運(yùn)輸費(fèi)用最低，如何安排網(wǎng)絡(luò)各段的通信量第八次網(wǎng)絡(luò)優(yōu)化模型，最低費(fèi)用最大流模型，最低費(fèi)用最大流模型的基本特征是1，1個(gè)接收點(diǎn)2、給一個(gè)弧施加容量，3、給一個(gè)弧同時(shí)施加單位流量的費(fèi)用，4、在確定網(wǎng)絡(luò)最大流量的同時(shí)，使總費(fèi)用最小化的第二步：在最大流量f的所有方案中，選擇最小費(fèi)用的方案，第八次網(wǎng)絡(luò)優(yōu)化模型，最小費(fèi)用最大流模型，最小費(fèi)用最大流模型解決最小費(fèi)用最大流問(wèn)題，其實(shí)是多目標(biāo)修訂畫問(wèn)題，各級(jí)目標(biāo)建立各自的網(wǎng)圖形式的數(shù)學(xué)表現(xiàn)模型，用修正計(jì)算機(jī)解決。 以與目標(biāo)修正像素的求解方法類似的方式，Excel求解器模塊也可以一次求解兩個(gè)目標(biāo)模型(

12、如下圖)。 系統(tǒng)最大流程： 10、第一級(jí)(最大流程)、第二級(jí)(最小費(fèi)用流程)、系統(tǒng)最小費(fèi)用流程： 145、第八次網(wǎng)絡(luò)優(yōu)化模型、最小費(fèi)用最大流程模型以表格形式表示，第八次網(wǎng)絡(luò)優(yōu)化模型、最小支撐樹(shù)模型、第八次網(wǎng)絡(luò)最大公司管理層已經(jīng)決定建設(shè)最先進(jìn)的光纖網(wǎng)絡(luò)，在公司主要部門之間提供高速通信(數(shù)據(jù)、語(yǔ)音、圖像)。 下圖中的節(jié)點(diǎn)顯示了該公司主要部門(包括總部、巨型計(jì)算機(jī)、科研區(qū)、生產(chǎn)和配送中心等)的分布圖。 虛線是可能鋪設(shè)纖維光纜的位置。 每條虛線旁邊的數(shù)字表示選擇在此位置敷設(shè)光纜所需的成本(單位：萬(wàn)美元)。 第八屆網(wǎng)絡(luò)優(yōu)化模型、最小支撐樹(shù)模型、應(yīng)確定的公司光纖最小支撐樹(shù)如下圖所示。 樹(shù)中各邊的權(quán)重之和(該光纖網(wǎng)絡(luò)所需的成本):112222=11 (萬(wàn)元)，第八次網(wǎng)絡(luò)優(yōu)化模型，最小支撐樹(shù)模型，最小支撐樹(shù)模型的基本特征2 .構(gòu)成連通圖的邊都加權(quán)相應(yīng)的權(quán)重，而且邊的數(shù)量是總節(jié)點(diǎn)的數(shù)量除去任何一條邊必定是不連通的，4、鄰接頂點(diǎn)如果不連接一條邊，正好回路(環(huán))，5、在滿足上述四個(gè)要求的所有構(gòu)成方案中，構(gòu)成樹(shù)的破圈法求解(手動(dòng))、修正機(jī)程序模塊求解(基于貪婪法)、第八回網(wǎng)最小支撐樹(shù)模型的求解-貪婪法，選擇1，第一條邊：選擇成本最低的候補(bǔ)邊，選擇2，不構(gòu)成下一個(gè)(b )輪