專題五-圖與網(wǎng)絡(luò)分析

1專題五圖論與網(wǎng)絡(luò)計(jì)劃模型最小生成樹(shù)模型最短路模型最大流模型最小費(fèi)用流模型網(wǎng)絡(luò)計(jì)劃與優(yōu)化模型2第一節(jié)圖與網(wǎng)絡(luò)基礎(chǔ)概念圖子圖和生成子圖網(wǎng)絡(luò)圖鏈、路、圈和回路連通圖簡(jiǎn)單圖3一、圖

由有限個(gè)代表事物的點(diǎn)和表示事物間聯(lián)系線構(gòu)成，這些點(diǎn)稱為頂點(diǎn)。為了反映7家企業(yè)的業(yè)務(wù)來(lái)往聯(lián)系，用7個(gè)點(diǎn)表示7家企業(yè)，若某兩家企業(yè)之間存在業(yè)務(wù)來(lái)往，則兩點(diǎn)間聯(lián)線。數(shù)學(xué)表達(dá)：頂點(diǎn)用V={v1,v2,…,vn}表示；頂點(diǎn)間的連線稱為邊，用E={e1,e2,…}表示，則圖的表示方法為：G={V,E}4無(wú)向圖：對(duì)象之間具有對(duì)稱性，（甲對(duì)乙，乙對(duì)甲）。有向圖：不具有對(duì)稱性的事物。A認(rèn)識(shí)B，B一定認(rèn)識(shí)A?A到B的距離，一定等于B到A的距離？為了反映球隊(duì)之間比賽勝負(fù)關(guān)系，則球隊(duì)之間單純用一條聯(lián)線就難以表達(dá)。對(duì)策：帶箭頭的線，有向線－－－有向圖。5邊：兩點(diǎn)間不帶箭頭聯(lián)線稱為邊，若兩點(diǎn)為vi,vj,則邊記為：[vi,vj]；?。簝牲c(diǎn)間帶箭頭聯(lián)線稱弧,若有vi指向vj的弧，則弧記為：（vi,vj）。無(wú)向圖定義：由點(diǎn)和邊組成，表示G={V,E}；有向圖定義：由點(diǎn)和弧組成，表示D={V,A}。6二、子圖與生成子圖子圖：圖G1中的點(diǎn)是圖G2中點(diǎn)的一部分，圖G1中的邊是圖G2中的一部分。生成圖：圖G1的點(diǎn)與圖G2相同，邊是其中的一部分。7三、網(wǎng)絡(luò)圖各邊賦予一定的物理量，例如距離，則叫做網(wǎng)絡(luò)圖。所賦予的物理量叫做權(quán)。權(quán)可以是：距離、時(shí)間、成本、容量等。e11表示上海到北京的鐵路長(zhǎng)度。或，旅客從上海到北京的車(chē)票費(fèi)用8四、鏈、路、圈、回路鏈：點(diǎn)和邊的交錯(cuò)序列（vi1,ei1,vi2,…,eik-1,vik）,若有eit=[vit,vit+1]。初等鏈：頂點(diǎn)和邊相互交替出現(xiàn)的點(diǎn)不重復(fù)序列。路：在有向圖中，鏈中每條邊的方向和鏈的走向一致的鏈。圈：起點(diǎn)和終點(diǎn)相同的鏈叫做圈。回路：起點(diǎn)和終點(diǎn)相同的路叫做回路。v4v1v2v5v3e1e2e3e4e5e6★任意舉出一條鏈，初等鏈，路，圈和回路。9五、連通圖和簡(jiǎn)單圖連通圖：在圖中，任意兩點(diǎn)之間都有一條鏈相連，叫做連通圖。否則是非連通圖。非連通圖可以由幾個(gè)連通圖構(gòu)成。環(huán)：某邊的兩個(gè)頂點(diǎn)相同；多重邊：兩個(gè)頂點(diǎn)之間多于一條邊。簡(jiǎn)單圖：沒(méi)有環(huán)和多重邊的圖是簡(jiǎn)單圖。10第二節(jié)樹(shù)及最小生成樹(shù)算法什么是樹(shù)？構(gòu)造生成樹(shù)的方法最小生成樹(shù)尋找最小生成樹(shù)的方法11樹(shù)：不含圈的連通圖五個(gè)城市連通電話線問(wèn)題什么是連通圖：任意兩點(diǎn)之間都有一條鏈相連。什么是圈：起點(diǎn)和終點(diǎn)相同的鏈叫做圈。已知有五個(gè)城市，要在它們之間架設(shè)電話線，要求任何兩個(gè)城市都可以互相通話（允許通過(guò)其它城市），并且電話線的根數(shù)最少。一、樹(shù)的基本概念12樹(shù)的基本性質(zhì)任意兩點(diǎn)之間有且只有一條鏈；圖是樹(shù)的充要條件：任意兩個(gè)頂點(diǎn)之間只有一條鏈；若樹(shù)有p個(gè)頂點(diǎn)，則共有q=p-1條邊；圖是樹(shù)的充要條件：連通圖，邊數(shù)=頂點(diǎn)數(shù)－1。五個(gè)城市連通電話線問(wèn)題13生成樹(shù)的概念生成圖：圖G1的點(diǎn)與圖G2相同，邊是其中的一部分。如果G1是樹(shù)，則稱為生成樹(shù)。五個(gè)城市連通電話線問(wèn)題14二、構(gòu)造生成樹(shù)的方法法1：破圈法：無(wú)圈的連通圖，圖中無(wú)圈。起點(diǎn)和終點(diǎn)相同的鏈叫做圈。從圖中取圈，從圈中去掉一邊，重復(fù)直到無(wú)圈。15避圈法：從圖中某一點(diǎn)開(kāi)始生長(zhǎng)邊，選取與入樹(shù)邊不構(gòu)成圈的邊。16三、最小生成樹(shù)生成樹(shù)不唯一架設(shè)電話線鋪設(shè)水管連接邊長(zhǎng)度最短？17設(shè)有一個(gè)連通圖，每一邊都有一個(gè)非負(fù)權(quán)，w(e)=wij.樹(shù)的權(quán)：樹(shù)中所有邊的權(quán)之和。最小生成樹(shù)：圖中，權(quán)最小的生成樹(shù)。18將圖中求最小生成樹(shù)的問(wèn)題歸結(jié)為整數(shù)規(guī)劃問(wèn)題，列出數(shù)學(xué)模型。3568a12a13a24a34a36a67a47a45a78a5812471920四、尋找最小生成樹(shù)的方法（1）避圈法：開(kāi)始選一條最小權(quán)的邊，以后總從與已選邊不構(gòu)成圈的那些未選邊中，選一條權(quán)最小的（相同最小權(quán)的邊，任選一條）。（2）破圈法：任取一圈，從圈中去掉一條權(quán)最大的邊（相同權(quán)的邊，任去一條），在余下圖中，重復(fù)此步驟，直到得到一個(gè)不含圈的圖，即得最小樹(shù)。21分別用破圈法和避圈法

求圖中的最小生成樹(shù)3926331447392633144722(3)矩陣求解算法步驟1：構(gòu)造一個(gè)矩陣，651572344v1v2v3v4v5v623T651572344v1v2v3v4v5v624步驟2：從矩陣中任一行開(kāi)始，用T表明節(jié)點(diǎn)入樹(shù)，劃去該節(jié)點(diǎn)所在的列。T25步驟3：在標(biāo)T的行中選取最小元素，用方框表示，將對(duì)應(yīng)的邊入樹(shù)，將新得到節(jié)點(diǎn)標(biāo)T，劃去所在列。TT26步驟4：重復(fù)步驟3。TTT27矩陣計(jì)算方法TTTT28矩陣計(jì)算方法TTTTT29矩陣計(jì)算方法TTTTTT30矩陣計(jì)算結(jié)果3168357234832第三節(jié)最短路問(wèn)題及算法什么是最短路問(wèn)題？求解最短路問(wèn)題的基本思路Dijstra算法：標(biāo)號(hào)法33一、什么是最短路問(wèn)題？91344372858始點(diǎn)終點(diǎn)v1v2v3v42v5v6v734二、求解最短路問(wèn)題的基本思路

對(duì)于在始點(diǎn)到終點(diǎn)的總體最短路徑上的任意一點(diǎn)，從始點(diǎn)到該點(diǎn)的最短路在總體最短路徑上。動(dòng)態(tài)規(guī)劃的思路35三、Dijkstra算法對(duì)每個(gè)節(jié)點(diǎn)，用兩種標(biāo)號(hào)：T和P，表示從始點(diǎn)到該節(jié)點(diǎn)的距離，P是最短距離，T是目前路徑的距離。通過(guò)不斷改進(jìn)T值，當(dāng)其最小時(shí)，將其改為P標(biāo)號(hào)。開(kāi)始時(shí)，令始點(diǎn)有P=0，P標(biāo)號(hào)，其它節(jié)點(diǎn)T=M（無(wú)窮大）。36P(V1)=0,T(V2)=M,…第一步：T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6T(V4)=min(T(V4),P(V1)+W14)=0+2=2Min(T(V2),T(V3),T(V4))=2★斷言：V1到V4的最短距離為2?P(V4)=237第二步：T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5T(V6)=min(T(V6),P(V4)+W46)=min(M,2+2)=4T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6Min(T(V2),T(V3),T(V6))=4斷言：V1到V6的距離最短：4。P(V6)=438第一步：假定vi是新產(chǎn)生的P標(biāo)號(hào)點(diǎn)，考查以vi為開(kāi)始點(diǎn)的所有弧段vivj。如果vj是P標(biāo)號(hào)點(diǎn)，則對(duì)vj點(diǎn)不再進(jìn)行標(biāo)號(hào)；如果vj是T標(biāo)號(hào)點(diǎn)，則計(jì)算第二步：產(chǎn)生新的P標(biāo)號(hào)點(diǎn)，在現(xiàn)有所有的T標(biāo)號(hào)中將值最小的T標(biāo)號(hào)改為P標(biāo)號(hào)。重復(fù)上述步驟,直到?jīng)]有點(diǎn)可標(biāo)號(hào)。39第三步：T(V5)=min(T(V5),P(V6)+W65)=min(M,4+3)=7T(V7)=min(T(V7),P(V6)+W67)=min(M,4+9)=13T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5Min(T(V2),T(V3),T(V5),T(V7))=5斷言：V1到V3的距離最短：5。P(V3)=5404142問(wèn)：從V1到V6的最短距離為多少？從V1到V3的距離為多少？從V3到V5的最短距離為多少？43練習(xí)：求V1到V9點(diǎn)的最短距離。v1v2v3v4v5v6v7v8v92349135115651246344無(wú)向圖（取消箭頭）計(jì)算方法?8623415192123456745v1v2v3v4v5v6v7v8v92349135115651246346四、Ford算法Dijkstra算法不適用于負(fù)權(quán)網(wǎng)絡(luò)具有負(fù)權(quán)的網(wǎng)絡(luò)，應(yīng)當(dāng)用Ford算法（修正標(biāo)號(hào)法）修正標(biāo)號(hào)法特點(diǎn)是：不但最小T標(biāo)號(hào)應(yīng)改為P標(biāo)號(hào)，P標(biāo)號(hào)也可修改，修改后P標(biāo)號(hào)再次改為T(mén)標(biāo)號(hào)。25-464472v1v3v4v98-588545St748五、尋找最短路徑的方法使用雙標(biāo)號(hào)49已知有6個(gè)村莊，相互間道路距離如下圖，擬建一所小學(xué)。A處有學(xué)生50人，B處有40人，C處有60人，D處有20人，E處有70人，F(xiàn)處有90人。問(wèn)小學(xué)應(yīng)建在哪個(gè)村莊，使學(xué)生上學(xué)走的路程最短？ABDCFE266418313750第四節(jié)最大流問(wèn)題網(wǎng)絡(luò)流的基本概念求解網(wǎng)絡(luò)最大流的基本原理尋找網(wǎng)絡(luò)最大流的標(biāo)號(hào)法確定網(wǎng)絡(luò)中最大流的方法51

如圖是聯(lián)接某石油銷(xiāo)地和產(chǎn)地的交通網(wǎng)（管道），弧旁數(shù)字表示此運(yùn)輸管道的最大通過(guò)能力。產(chǎn)品從V1送到V7．現(xiàn)在要求制定一個(gè)運(yùn)輸方案，使從V1到V7的產(chǎn)品運(yùn)輸最多。91344372858始點(diǎn)終點(diǎn)v1v2v3v42v5v6v752一、網(wǎng)絡(luò)流的基本概念流量：某時(shí)間內(nèi)通過(guò)弧(vivj)的物質(zhì)數(shù)量fij。容量：弧的最大允許流通量。始點(diǎn)（發(fā)點(diǎn)），終點(diǎn)（收點(diǎn)），中間點(diǎn)91344372858始點(diǎn)終點(diǎn)v1v2v3v42v5v6v753可行流f：節(jié)點(diǎn)和邊的限制條件（1）容量限制條件：通過(guò)每條弧的流量不超過(guò)弧的容量。（2）平衡條件：網(wǎng)絡(luò)中的總流量等于始點(diǎn)凈輸出量；網(wǎng)絡(luò)中的總流量等于終點(diǎn)凈輸入量；流進(jìn)中間點(diǎn)的流量等于流出該點(diǎn)的流量。41341231223始點(diǎn)終點(diǎn)v1v2v3v41v5v6v7網(wǎng)絡(luò)中的總流量54如何判斷流分配是否可行？41341231223始點(diǎn)終點(diǎn)v1v2v3v41v5v6v791344372858始點(diǎn)終點(diǎn)v1v2v3v42v5v6v755飽和?。壕W(wǎng)絡(luò)中流量等于容量的??；非飽和弧：流量小于容量的?。徽蚧。憾x從始點(diǎn)到終點(diǎn)的一條鏈，與鏈方向一致的弧，為正向弧，反之為反向弧。12345691344372858始點(diǎn)終點(diǎn)v1v2v3v42v5v6v7零流?。毫髁?0的弧56增廣鏈：對(duì)于一可行流，網(wǎng)絡(luò)一條鏈滿足BDCFE10，55，211，64，15，13，26，33，317，28，3非飽和弧非零流弧57二、求解網(wǎng)絡(luò)最大流的基本原理數(shù)學(xué)模型58列出下述問(wèn)題的數(shù)學(xué)模型：從三口油井1，2，3經(jīng)管道將油輸送到脫水處理廠7，8，中間經(jīng)4，5，6三個(gè)泵站。圖中弧旁數(shù)字為各管道通過(guò)的最大能力，求從油井每小時(shí)輸送到處理廠的最大流量。2010101050203015205020123456783059定理：可行流f為最大流的充分必要條件是當(dāng)且僅當(dāng)網(wǎng)絡(luò)不存在增廣鏈。若f是最大流，則不存在增廣鏈；若不存在增廣鏈，則f是最大流。60給出一初始可行流，尋找增廣鏈，若存在，則通過(guò)該增廣鏈調(diào)整、增加網(wǎng)絡(luò)流。若不存在增廣鏈，則網(wǎng)絡(luò)流不可再增加。求得最大流。流量調(diào)整多少？61三、尋找網(wǎng)絡(luò)最大流的標(biāo)號(hào)法Ford-Fulkson標(biāo)號(hào)算法：尋增廣鏈。給每個(gè)節(jié)點(diǎn)以一對(duì)標(biāo)號(hào)，第一個(gè)標(biāo)號(hào)表示箭尾節(jié)點(diǎn)，第二個(gè)標(biāo)號(hào)表示可調(diào)整量，若終點(diǎn)有了標(biāo)號(hào)，則找到一條增廣鏈，否則不存在增廣鏈。增廣鏈判定：vivjvivj62調(diào)整過(guò)程：在增廣鏈上，正向弧加上調(diào)整量，反向弧減去調(diào)整量。經(jīng)過(guò)調(diào)整網(wǎng)絡(luò)流v(f)增加一個(gè)調(diào)整量：4，43，05，33，36，4按上述調(diào)整，得網(wǎng)絡(luò)流是否可行？流量是否增加了？4，43，15，23，36，363646566從三口油井1，2，3經(jīng)管道將油輸送到脫水處理廠7，8，中間經(jīng)4，5，6三個(gè)泵站。圖中弧旁數(shù)字為各管道通過(guò)的最大能力，求從油井每小時(shí)輸送到處理廠的最大流量。2010101050203015205020123456783067第五節(jié)最小費(fèi)用最大流問(wèn)題什么是最小費(fèi)用流問(wèn)題？求解最小費(fèi)用流的賦權(quán)圖法68一、什么是最小費(fèi)用流354123152最大流分配是否唯一？引入每條流的成本！69給定網(wǎng)絡(luò)N=(V,A,c,b)和經(jīng)過(guò)網(wǎng)絡(luò)的流量v，求流在網(wǎng)絡(luò)上的最佳分布，使總費(fèi)用最小。70二、求解最小費(fèi)用流的賦權(quán)圖法增廣鏈費(fèi)用，最小費(fèi)用增廣鏈。當(dāng)沿著一條關(guān)于可行流f的增廣鏈，以調(diào)整f，得到的可行流f’，流量增加，費(fèi)用變化：稱之為增廣鏈的費(fèi)用。多條增廣鏈,費(fèi)用不同.71對(duì)于可行流，沿最小費(fèi)用增廣鏈調(diào)整流，可使流增加，并保持流費(fèi)用最小。給定初始可行流（若該流量下費(fèi)用最?。?，求最小費(fèi)用增廣鏈，若存在，則沿該增廣鏈調(diào)整網(wǎng)絡(luò)流；再尋求最小費(fèi)用增廣鏈，直到給定的網(wǎng)絡(luò)流不存在增廣鏈為止，即為最小費(fèi)用最大流。72如何求最小費(fèi)用增廣鏈？增廣鏈的條件73賦權(quán)網(wǎng)絡(luò)：將飽和弧反向?qū)⒎秋柡?、非零流弧加一反向弧零流弧不變所有正向弧的?quán)為該弧的費(fèi)用，反向弧的權(quán)為該弧費(fèi)用的相反數(shù)如此變化后，有何特點(diǎn)？賦權(quán)圖中，從始點(diǎn)到終點(diǎn)每條通路都是當(dāng)前可行流的增廣鏈。最小費(fèi)用增廣鏈對(duì)應(yīng)賦權(quán)網(wǎng)絡(luò)的最短路。74最小費(fèi)用流的實(shí)例7576777879-28081賦權(quán)網(wǎng)絡(luò)已不存在最短路（增廣鏈）82第六節(jié)網(wǎng)絡(luò)計(jì)劃技術(shù)網(wǎng)絡(luò)圖的繪制與識(shí)別網(wǎng)絡(luò)圖的時(shí)間參數(shù)計(jì)算網(wǎng)絡(luò)優(yōu)化的基本方法83甘特圖不易表現(xiàn)工程全貌不便于對(duì)各項(xiàng)工作的安排進(jìn)行籌劃和推敲不能識(shí)別影響進(jìn)度的關(guān)鍵工作不能反映一項(xiàng)工作不能按進(jìn)度完成時(shí)對(duì)工程進(jìn)度影響項(xiàng)目有幾項(xiàng)工作?能否體現(xiàn)工作之間先后關(guān)系?能否反映工作開(kāi)工和完工的時(shí)間?84一、網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖的構(gòu)成作業(yè)（工作、工序、活動(dòng)），箭頭表示，箭頭之上表示工作名稱，之下表示工作時(shí)間。需要消耗一定的人力、物力，經(jīng)過(guò)一定的時(shí)間完成。事項(xiàng)，節(jié)點(diǎn)表示，表示某個(gè)工作的結(jié)束和另一工作的開(kāi)始。虛工作85一個(gè)基建項(xiàng)目網(wǎng)絡(luò)圖特點(diǎn)：工作數(shù)；先后時(shí)間。有了工作和事項(xiàng)，可按照作業(yè)的先后次序繪制網(wǎng)絡(luò)圖。86路線：從開(kāi)始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的一條路經(jīng)，一個(gè)網(wǎng)絡(luò)圖有多條路線，每條路線有一個(gè)總時(shí)間。關(guān)鍵路線：總時(shí)間最長(zhǎng)的路線。工期：關(guān)鍵路線的總時(shí)間87網(wǎng)絡(luò)圖的路線路線有幾條？關(guān)鍵路線是哪條？工期有多長(zhǎng)？88以上網(wǎng)絡(luò)圖共有8條路線可以計(jì)算出這8條路線的總時(shí)間，最長(zhǎng)的是16天。關(guān)鍵路線是當(dāng)某些工作的時(shí)間調(diào)整后，可能引起關(guān)鍵路線的變化和工期的變化。例如將工作E的時(shí)間縮短為4天，則工期縮短為13天，關(guān)鍵路線將變?yōu)?346BEG5651356BFH55389二、網(wǎng)絡(luò)圖的畫(huà)法作業(yè)的串聯(lián)：先行作業(yè)；緊前作業(yè)；緊后作業(yè)作業(yè)的并聯(lián)兩事項(xiàng)間只能有一項(xiàng)作業(yè)90網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號(hào)應(yīng)從小到大，且不重復(fù)。箭頭事項(xiàng)編號(hào)大于箭尾事項(xiàng)編號(hào)。網(wǎng)絡(luò)圖只能一個(gè)開(kāi)始節(jié)點(diǎn)，一個(gè)終止節(jié)點(diǎn)。不能出現(xiàn)循環(huán)路線。盡量少交叉，采用暗橋；有層次性。始工作和結(jié)束工作繪制網(wǎng)絡(luò)圖的基本原則9192一項(xiàng)工作有兩個(gè)緊后工作一項(xiàng)工作有兩個(gè)緊前工作9394修改95三、網(wǎng)絡(luò)圖時(shí)間參數(shù)計(jì)算事項(xiàng)時(shí)間參數(shù)的計(jì)算作業(yè)時(shí)間參數(shù)的計(jì)算關(guān)鍵路線的尋找方法96作業(yè)時(shí)間的確定對(duì)具有標(biāo)準(zhǔn)的作業(yè)，采用單一時(shí)間估計(jì)法對(duì)一般性作業(yè)，采用三點(diǎn)時(shí)間估計(jì)法最樂(lè)觀時(shí)間：a最可能時(shí)間：m最悲觀時(shí)間：b計(jì)算時(shí)間期望值和方差97作業(yè)時(shí)間計(jì)算方法數(shù)學(xué)期望；方差98事項(xiàng)參數(shù)計(jì)算事項(xiàng)最早時(shí)間：以節(jié)點(diǎn)j為開(kāi)始的各項(xiàng)作業(yè)最早可開(kāi)工的時(shí)間。事項(xiàng)最遲時(shí)間：以此節(jié)點(diǎn)為結(jié)束的各項(xiàng)作業(yè)最遲必須完成時(shí)間。ijiiijj99圖上計(jì)算法1）從始節(jié)點(diǎn)開(kāi)始（始節(jié)點(diǎn)最早為零），用方括號(hào)表示某節(jié)點(diǎn)的最早時(shí)間。2）從終節(jié)點(diǎn)開(kāi)始（終節(jié)點(diǎn)最遲為工期），用三角表示某節(jié)點(diǎn)最遲時(shí)間。12345ABCDEHFG67841078127540411141426313501441414263135100作業(yè)時(shí)間參數(shù)的計(jì)算作業(yè)最早開(kāi)始時(shí)間作業(yè)最早結(jié)束時(shí)間作業(yè)最遲開(kāi)始時(shí)間作業(yè)最遲結(jié)束時(shí)間總時(shí)差單時(shí)差101作業(yè)最早時(shí)間ijii最早開(kāi)始最早結(jié)束102作業(yè)最遲時(shí)間ijj最遲開(kāi)始最遲結(jié)束103作業(yè)時(shí)間參數(shù)計(jì)算12345ABCDEHFG67841078127540411141426313501441414263135作業(yè)D的時(shí)間參數(shù)作業(yè)G的時(shí)間參數(shù)104總時(shí)差：在不影響總工程完工工期情況下，作業(yè)完工期可推遲的時(shí)間。單時(shí)差：不影響下一作業(yè)最早開(kāi)工的情況下，一項(xiàng)作業(yè)完工期可推遲的時(shí)間。最早開(kāi)始，最早結(jié)束最遲開(kāi)始，最遲結(jié)束ijEF105時(shí)差12345ABCDEHFG67841078127540411141426313501441414263135106最早時(shí)間：由上到下；先定開(kāi)始作業(yè)A的最早開(kāi)始時(shí)間（0），加上作業(yè)時(shí)間得到作業(yè)的最早結(jié)束時(shí)間。凡是先行作業(yè)（B，C）只有一個(gè)為A，則，作業(yè)A的最早結(jié)束時(shí)間為該作業(yè)（B，C）的最早開(kāi)始時(shí)間。若有多項(xiàng)先行作業(yè)，則為先行作業(yè)最早結(jié)束時(shí)間最長(zhǎng)的為該作業(yè)的最早開(kāi)始時(shí)間。107最遲時(shí)間：由下到上；最后一個(gè)作業(yè)的最早結(jié)束時(shí)間為最遲結(jié)束時(shí)間，減去作業(yè)時(shí)間為最遲開(kāi)始時(shí)間；查看該作業(yè)的先行作業(yè)，先行作業(yè)的最遲結(jié)束時(shí)間為該作業(yè)的最遲開(kāi)始時(shí)間。若某作業(yè)是兩個(gè)以上作業(yè)的先行作業(yè)，取小的為該作業(yè)的最遲開(kāi)始時(shí)間。108關(guān)鍵路線的確定方法總時(shí)差為零的作業(yè)即是關(guān)鍵作業(yè)；關(guān)鍵作業(yè)構(gòu)成關(guān)鍵路線。109已知下表所列資料：要求(1)繪制網(wǎng)絡(luò)圖；(2)計(jì)算各工序的最早開(kāi)工、最早完工，最遲開(kāi)工，最遲完工時(shí)間，總時(shí)差，并指出關(guān)鍵工序；(3)若要求工程完工時(shí)間縮短2天，縮短哪些工序的時(shí)間為好。工序緊前工序工序時(shí)間工序緊前工序工序時(shí)間工序緊前工序工序時(shí)間ag,m3ec5ia,l2bh4fa,e5kf,i1c-7gb,c2lb,c7dl3h-5mc3110四、網(wǎng)絡(luò)優(yōu)化工程進(jìn)度計(jì)劃編制：工期，費(fèi)用，資源從工程進(jìn)度角度編制，考慮工作時(shí)間關(guān)系；考慮資源條件限制，包括人員和物質(zhì)條件，如設(shè)備工時(shí)，器材，工具，廠房，運(yùn)輸工具，原材料，動(dòng)力，燃料。111工期限定，資源需要平衡問(wèn)題：多項(xiàng)工作同時(shí)展開(kāi)，可能導(dǎo)致資源使用不均衡，延誤關(guān)鍵工作，不能保證工期。解決措施：工期不變，就是關(guān)鍵工作時(shí)間不能調(diào)整。調(diào)整非關(guān)鍵路線上工作的開(kāi)始時(shí)間，使資源實(shí)現(xiàn)平衡。112箭線下面的數(shù)字