運(yùn)籌學(xué)第九章 網(wǎng)絡(luò)計(jì)劃課件

運(yùn)籌學(xué)趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)趙明霞第九章網(wǎng)絡(luò)計(jì)劃

網(wǎng)絡(luò)計(jì)劃圖時(shí)間參數(shù)的計(jì)算

網(wǎng)絡(luò)計(jì)劃優(yōu)化2第九章網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃圖2通過重組,打亂,優(yōu)化等手段改變?cè)镜墓逃修k事格式,優(yōu)化辦事效率的一種辦事方法。一種安排工作進(jìn)程的數(shù)學(xué)方法。它的實(shí)用范圍極廣泛，在企業(yè)管理和基本建設(shè)中，以及關(guān)系復(fù)雜的科研項(xiàng)目的組織與管理中，都可以應(yīng)用。我國，是從20世紀(jì)60年代開始運(yùn)用網(wǎng)絡(luò)計(jì)劃的，著名數(shù)學(xué)家華羅庚教授結(jié)合我國實(shí)際，在吸收國外網(wǎng)絡(luò)計(jì)劃技術(shù)理論的基礎(chǔ)上，將CPM、PERT等方法統(tǒng)一定名為統(tǒng)籌法。統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。統(tǒng)籌方法3通過重組,打亂,優(yōu)化等手段改變?cè)镜墓逃修k事格式,優(yōu)化辦事效統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例9.1某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表所示，請(qǐng)畫出其網(wǎng)絡(luò)計(jì)劃圖。工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d第一節(jié)網(wǎng)絡(luò)圖4統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開始或結(jié)束,是相鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號(hào)?；”硎疽粋€(gè)工序（或活動(dòng)），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即為對(duì)此弧所賦的權(quán)數(shù)．2022/11/175.--線性規(guī)劃--線性規(guī)劃解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表2022/11/125.--１２４５３abcde601383815圖16１２４５３abcde601383815圖16

例9.2

把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請(qǐng)畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ7例9.2把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請(qǐng)畫出其統(tǒng)解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時(shí)間。152643a60b158e1013dc38f圖28解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此增加了一個(gè)點(diǎn)和虛工序如圖4。b1256734a6015ec13d388h510fg16圖39在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。b1256734a601在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。161257834a6015bec13d388h510f6g圖4避免交叉節(jié)點(diǎn)標(biāo)號(hào)：j>iij10在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。161第二節(jié)時(shí)間參數(shù)的計(jì)算在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以推遲多久。11第二節(jié)時(shí)間參數(shù)的計(jì)算11一、工作時(shí)間t(i,j)確定型概率型缺乏統(tǒng)計(jì)來確定完成每個(gè)活動(dòng)所需時(shí)間，但對(duì)所需時(shí)間做了三種估計(jì)：1.樂觀時(shí)間。指所需最少時(shí)間，用a表示。2.最可能時(shí)間。指正常時(shí)間，用m表示。3.悲觀時(shí)間。指不順利情況下，最多時(shí)間，用b表示。2022/11/1712一、工作時(shí)間t(i,j)確定型2022/11/121活動(dòng)樂觀時(shí)間最可能時(shí)間悲觀時(shí)間abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5例9.3

2022/11/1713活動(dòng)樂觀時(shí)間最可能時(shí)間悲觀時(shí)間a1.

顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我們可以可以假定這些時(shí)間的概率分布近似服從分布。我們可以用如下公式計(jì)算出完成活動(dòng)所需的：方差平均時(shí)間例如：完成工作g所需平均時(shí)間：同時(shí)求出方差為14顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我

同樣可以求出每個(gè)活動(dòng)的完成所需平均時(shí)間及方差活動(dòng)T（平均時(shí)間）方差活動(dòng)T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02815同樣可以求出每個(gè)活動(dòng)的完成所需平均時(shí)間及方差活動(dòng)T（平均時(shí)1、最早時(shí)間從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個(gè)工序的最早開始時(shí)間（ES)和最早結(jié)束時(shí)間（EF)工序a的最早開始時(shí)間工序a的最早完成時(shí)間ija[0，60]60二、時(shí)間參數(shù)161、最早時(shí)間工序a的最早工序a的最早ija[0，60]60二1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015例9.42022/11[0,60]60b[60,105]45e[62、最晚時(shí)間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個(gè)工程最早結(jié)束時(shí)間的情況下，各個(gè)工序的最晚結(jié)束時(shí)間（LF)和最晚開始時(shí)間(LS)工序a的最晚開始時(shí)間工序a的最晚完成時(shí)間ij[0，60]a2022/11/17182、最晚時(shí)間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個(gè)工程最早結(jié)束時(shí)

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135191236785a[0,60]60[0,60]b[60,101、總時(shí)差在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的總時(shí)差R三、時(shí)差2022/11/17201、總時(shí)差三、時(shí)差2022/11/12202、單時(shí)差在不影響緊后工序最早開始時(shí)間的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的單時(shí)差r2022/11/17212、單時(shí)差2022/11/1221四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線稱為關(guān)鍵路線?？倳r(shí)差為0的工序?yàn)殛P(guān)鍵工序。2022/11/1722.--線性規(guī)劃--線性規(guī)劃四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個(gè)工程所例9-12022/11/1723例9-12022/11/12232022/11/1724.--線性規(guī)劃--線性規(guī)劃2022/11/1224.--線性規(guī)劃--線性規(guī)劃2022/11/1725.--線性規(guī)劃--線性規(guī)劃2022/11/1225.--線性規(guī)劃--線性規(guī)劃例9.4

某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完成此工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以推遲多久？26例9.4某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h27工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序a生產(chǎn)線設(shè)計(jì)60/2712346785a60b45echj35ig1030d204025f18152812346785a60b45echj35ig1030d204

1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015291236785a[0,60]60b[60,105]45e[

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135301236785a[0,60]60[0,60]b[60,10

最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表所示。這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線。31最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表所示完成工序所需時(shí)間不確定例9-22022/11/1732完成工序所需時(shí)間不確定例9-22022/11/12322022/11/17332022/11/12332022/11/1734.--線性規(guī)劃--線性規(guī)劃2022/11/1234.--線性規(guī)劃--線性規(guī)劃關(guān)鍵線路2022/11/1735關(guān)鍵線路2022/11/1235第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2022/11/1736第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2利用時(shí)差

總時(shí)差不影響最短工期，但影響后續(xù)工序的自由時(shí)間。

單時(shí)差不影響后續(xù)工序。2022/11/1737利用時(shí)差2022/11/12373.時(shí)間-資源優(yōu)化做法：

1）優(yōu)先安排關(guān)鍵工序所需的資源。

2）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開各工序的開始時(shí)間。

3）適當(dāng)延長時(shí)差大的工序時(shí)間，或切斷非關(guān)鍵工序進(jìn)程。2022/11/17383.時(shí)間-資源優(yōu)化做法：2022/11/12382022/11/17392022/11/12392022/11/17402022/11/12402022/11/17412022/11/12414.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。2022/11/1742.--線性規(guī)劃--線性規(guī)劃4.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、

工序的最快完成時(shí)間：指完成時(shí)間的最高限度。我們?cè)O(shè)完成工序j的正常所需時(shí)間為Tj;直接費(fèi)用為cj;完成工序j的最快完成時(shí)間為T`j,直接費(fèi)用為c`j。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動(dòng)率（成本斜率）。有43工序的最快完成時(shí)間：指完成時(shí)間的最高限度。43模型一，在既定的時(shí)間T完工的前提下，問各工序的完成時(shí)間為多少才使因縮短工期而增加的直接費(fèi)用最少。設(shè)工序（i,j)的提前完工時(shí)間為yij,我們用Tij,T`ij分別表示正常完工時(shí)間與最快完工的時(shí)間，則有工序（i,j)的實(shí)際完工時(shí)間為：Tij-yij

。我們用Cij,C`ij表示用正常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用，kij為工序（i,j)的直接費(fèi)用變動(dòng)率（成本斜率）。44模型一，在既定的時(shí)間T完工的前提下，問各工序的完成時(shí)間為多少方法一：線性規(guī)劃法S.t.xj-xiTij-yij,對(duì)一切?。╥,j)yijTij-T`ij,對(duì)一切?。╥,j)xn-x1T,

xi0，yij0。45方法一：線性規(guī)劃法45例9.5例4所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時(shí)間與最快完工時(shí)間，以及對(duì)應(yīng)正常完工時(shí)間與最快完工時(shí)間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表所示。46例9.5例4所提供的信息都作為本例的信息，另外還給出了在工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接費(fèi)用直接費(fèi)用變動(dòng)率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-2022/11/1747.--線性規(guī)劃--線性規(guī)劃工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接該工程要求在150天內(nèi)完工，問每個(gè)工序應(yīng)比正常完工時(shí)間提前多少天完成，才能使整個(gè)工程因縮短工期而增加的直接費(fèi)用為最少。如果工期要求在140天完工呢？b12345678afechgijd48該工程要求在150天內(nèi)完工，問每個(gè)工序應(yīng)比正常完工時(shí)間提前多解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時(shí)間為xi，工序提前完工的時(shí)間為yij。minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40

x7-x515-y57x7-x625-y67

x1=0

x8150

y120y2715y235y2410y255y378y4610y575y780xi0，yij0.（對(duì)一切可能的ij)運(yùn)算得到結(jié)果：f=6400。49解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時(shí)間為xi，工序提前完工的時(shí)間為方法二：統(tǒng)籌法從關(guān)鍵工序中找成本斜率最小的工序，壓縮工期；重新計(jì)算關(guān)鍵路線和關(guān)鍵工序；再重復(fù)循環(huán)1和2，直至達(dá)到壓縮工期要求；計(jì)算增加的總直接費(fèi)用50方法二：統(tǒng)籌法50模型二，我們知道直接費(fèi)用是隨著完成時(shí)間的縮短而增加，而間接費(fèi)用卻會(huì)隨著完成時(shí)間的縮短而減少，設(shè)單位時(shí)間的間接費(fèi)用為d,計(jì)劃期的間接費(fèi)用與總工期成正比，即為d(xn-x1)。那么求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間T和各個(gè)工序最優(yōu)完成時(shí)間的模型為：

s.t.xj-xiTij-yij，對(duì)一切弧（i,j)yijTij-T`ij，對(duì)一切?。╥,j)xi

0，yij0。51模型二，我們知道直接費(fèi)用是隨著完成時(shí)間的縮短而增加，而間接費(fèi)

例9.6如果在例5中，每天的間接費(fèi)用為330元，求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間T和各個(gè)工序最優(yōu)完成時(shí)間。解：minf=330(x8-x1)+120y27+300y23+400y24+500y25+230y37+350y46+290y67

s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40

x7-x515-y57x7-x625-y67

x1=0y120y2715y235y2410y255y378y4610y575y780xi0，yij0.（對(duì)一切可能的ij)52例9.6如果在例5中，每天的間接費(fèi)用為330元，求使包

f=55700.x1=0,y12=0,y67=10,

x2=60,y27=0,y78=0.x3=125,y23=0,

x4=107,y24=0,

x5=110,y25=0,

x6=110,y37=0,

x7=125,y46=0,

x8=160,y57=0,

也就是說整個(gè)工程工期為160天時(shí)總費(fèi)用最少為124600元，各個(gè)工序開始時(shí)間如解所示，工序i要提前10天完工，其余的工序按正常時(shí)間完工。53f=55700.53例9-354例9-35455552022/11/17562022/11/12562022/11/1757.--線性規(guī)劃--線性規(guī)劃2022/11/1257.--線性規(guī)劃--線性規(guī)劃習(xí)題9.4（1）9.59.79.858習(xí)題9.4（1）58運(yùn)籌學(xué)趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)趙明霞第九章網(wǎng)絡(luò)計(jì)劃

網(wǎng)絡(luò)計(jì)劃圖時(shí)間參數(shù)的計(jì)算

網(wǎng)絡(luò)計(jì)劃優(yōu)化60第九章網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃圖2通過重組,打亂,優(yōu)化等手段改變?cè)镜墓逃修k事格式,優(yōu)化辦事效率的一種辦事方法。一種安排工作進(jìn)程的數(shù)學(xué)方法。它的實(shí)用范圍極廣泛，在企業(yè)管理和基本建設(shè)中，以及關(guān)系復(fù)雜的科研項(xiàng)目的組織與管理中，都可以應(yīng)用。我國，是從20世紀(jì)60年代開始運(yùn)用網(wǎng)絡(luò)計(jì)劃的，著名數(shù)學(xué)家華羅庚教授結(jié)合我國實(shí)際，在吸收國外網(wǎng)絡(luò)計(jì)劃技術(shù)理論的基礎(chǔ)上，將CPM、PERT等方法統(tǒng)一定名為統(tǒng)籌法。統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。統(tǒng)籌方法61通過重組,打亂,優(yōu)化等手段改變?cè)镜墓逃修k事格式,優(yōu)化辦事效統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例9.1某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表所示，請(qǐng)畫出其網(wǎng)絡(luò)計(jì)劃圖。工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d第一節(jié)網(wǎng)絡(luò)圖62統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開始或結(jié)束,是相鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號(hào)?；”硎疽粋€(gè)工序（或活動(dòng)），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即為對(duì)此弧所賦的權(quán)數(shù)．2022/11/1763.--線性規(guī)劃--線性規(guī)劃解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表2022/11/125.--１２４５３abcde601383815圖164１２４５３abcde601383815圖16

例9.2

把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請(qǐng)畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ65例9.2把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請(qǐng)畫出其統(tǒng)解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時(shí)間。152643a60b158e1013dc38f圖266解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此增加了一個(gè)點(diǎn)和虛工序如圖4。b1256734a6015ec13d388h510fg16圖367在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。b1256734a601在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。161257834a6015bec13d388h510f6g圖4避免交叉節(jié)點(diǎn)標(biāo)號(hào)：j>iij68在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。161第二節(jié)時(shí)間參數(shù)的計(jì)算在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以推遲多久。69第二節(jié)時(shí)間參數(shù)的計(jì)算11一、工作時(shí)間t(i,j)確定型概率型缺乏統(tǒng)計(jì)來確定完成每個(gè)活動(dòng)所需時(shí)間，但對(duì)所需時(shí)間做了三種估計(jì)：1.樂觀時(shí)間。指所需最少時(shí)間，用a表示。2.最可能時(shí)間。指正常時(shí)間，用m表示。3.悲觀時(shí)間。指不順利情況下，最多時(shí)間，用b表示。2022/11/1770一、工作時(shí)間t(i,j)確定型2022/11/121活動(dòng)樂觀時(shí)間最可能時(shí)間悲觀時(shí)間abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5例9.3

2022/11/1771活動(dòng)樂觀時(shí)間最可能時(shí)間悲觀時(shí)間a1.

顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我們可以可以假定這些時(shí)間的概率分布近似服從分布。我們可以用如下公式計(jì)算出完成活動(dòng)所需的：方差平均時(shí)間例如：完成工作g所需平均時(shí)間：同時(shí)求出方差為72顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我

同樣可以求出每個(gè)活動(dòng)的完成所需平均時(shí)間及方差活動(dòng)T（平均時(shí)間）方差活動(dòng)T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02873同樣可以求出每個(gè)活動(dòng)的完成所需平均時(shí)間及方差活動(dòng)T（平均時(shí)1、最早時(shí)間從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個(gè)工序的最早開始時(shí)間（ES)和最早結(jié)束時(shí)間（EF)工序a的最早開始時(shí)間工序a的最早完成時(shí)間ija[0，60]60二、時(shí)間參數(shù)741、最早時(shí)間工序a的最早工序a的最早ija[0，60]60二1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015例9.42022/11[0,60]60b[60,105]45e[62、最晚時(shí)間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個(gè)工程最早結(jié)束時(shí)間的情況下，各個(gè)工序的最晚結(jié)束時(shí)間（LF)和最晚開始時(shí)間(LS)工序a的最晚開始時(shí)間工序a的最晚完成時(shí)間ij[0，60]a2022/11/17762、最晚時(shí)間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個(gè)工程最早結(jié)束時(shí)

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135771236785a[0,60]60[0,60]b[60,101、總時(shí)差在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的總時(shí)差R三、時(shí)差2022/11/17781、總時(shí)差三、時(shí)差2022/11/12202、單時(shí)差在不影響緊后工序最早開始時(shí)間的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的單時(shí)差r2022/11/17792、單時(shí)差2022/11/1221四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線稱為關(guān)鍵路線。總時(shí)差為0的工序?yàn)殛P(guān)鍵工序。2022/11/1780.--線性規(guī)劃--線性規(guī)劃四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個(gè)工程所例9-12022/11/1781例9-12022/11/12232022/11/1782.--線性規(guī)劃--線性規(guī)劃2022/11/1224.--線性規(guī)劃--線性規(guī)劃2022/11/1783.--線性規(guī)劃--線性規(guī)劃2022/11/1225.--線性規(guī)劃--線性規(guī)劃例9.4

某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完成此工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開始時(shí)間與結(jié)束時(shí)間可以推遲多久？84例9.4某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h85工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序a生產(chǎn)線設(shè)計(jì)60/2712346785a60b45echj35ig1030d204025f18158612346785a60b45echj35ig1030d204

1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015871236785a[0,60]60b[60,105]45e[

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135881236785a[0,60]60[0,60]b[60,10

最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表所示。這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線。89最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表所示完成工序所需時(shí)間不確定例9-22022/11/1790完成工序所需時(shí)間不確定例9-22022/11/12322022/11/17912022/11/12332022/11/1792.--線性規(guī)劃--線性規(guī)劃2022/11/1234.--線性規(guī)劃--線性規(guī)劃關(guān)鍵線路2022/11/1793關(guān)鍵線路2022/11/1235第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2022/11/1794第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2利用時(shí)差

總時(shí)差不影響最短工期，但影響后續(xù)工序的自由時(shí)間。

單時(shí)差不影響后續(xù)工序。2022/11/1795利用時(shí)差2022/11/12373.時(shí)間-資源優(yōu)化做法：

1）優(yōu)先安排關(guān)鍵工序所需的資源。

2）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開各工序的開始時(shí)間。

3）適當(dāng)延長時(shí)差大的工序時(shí)間，或切斷非關(guān)鍵工序進(jìn)程。2022/11/17963.時(shí)間-資源優(yōu)化做法：2022/11/12382022/11/17972022/11/12392022/11/17982022/11/12402022/11/17992022/11/12414.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。2022/11/17100.--線性規(guī)劃--線性規(guī)劃4.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、

工序的最快完成時(shí)間：指完成時(shí)間的最高限度。我們?cè)O(shè)完成工序j的正常所需時(shí)間為Tj;直接費(fèi)用為cj;完成工序j的最快完成時(shí)間為T`j,直接費(fèi)用為c`j。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動(dòng)率（成本斜率）。有101工序的最快完成時(shí)間：指完成時(shí)間的最高限度。43模型一，在既定的時(shí)間T完工的前提下，問各工序的完成時(shí)間為多少才使因縮短工期而增加的直接費(fèi)用最少。設(shè)工序（i,j)的提前完工時(shí)間為yij,我們用Tij,T`ij分別表示正常完工時(shí)間與最快完工的時(shí)間，則有工序（i,j)的實(shí)際完工時(shí)間為：Tij-yij

。我們用Cij,C`ij表示用正常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用，kij為工序（i,j)的直接費(fèi)用變動(dòng)率（成本斜率）。102模型一，在既定的時(shí)間T完工的前提下，問各工序的完成時(shí)間為多少方法一：線性規(guī)劃法S.t.xj-xiTij-yij,對(duì)一切?。╥,j)yijTij-T`ij,對(duì)一切?。╥,j)xn-x1T,

xi0，yij0。103方法一：線性規(guī)劃法45例9.5例4所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時(shí)間與最快完工時(shí)間，以及對(duì)應(yīng)正常完工時(shí)間與最快完工時(shí)間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表所示。104例9.5例4所提供的信息都作為本例的信息，另外還給出了在工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接費(fèi)用直接費(fèi)用變動(dòng)率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-2022/11/17105.--線性規(guī)劃--線性規(guī)劃工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接該工程要求在150天內(nèi)完工，問每個(gè)工序應(yīng)比正常完工時(shí)間提前多少天完成，才能使整個(gè)工程因縮短工期而增加的直接費(fèi)用為最少。如果工期要求在140天完工呢？b12345678afechgijd106該工程要求在150天內(nèi)完工，問每個(gè)工序應(yīng)比正常完工時(shí)間提前多解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時(shí)間為xi，工序提前完工的時(shí)間為yij。minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40

x7-x515-y57x7-x625-y67

x1=0

x8150

y120y2715y235y2410y255y378y4610y575y780xi0，yij0.（對(duì)一切可能的ij)運(yùn)算得到結(jié)果：f=6400。107解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時(shí)間為xi，工序提前完工的時(shí)間為方法二：統(tǒng)籌法從關(guān)鍵工序中找成本斜率最小的工序，壓縮工期；重新計(jì)算關(guān)鍵路線和關(guān)鍵工序；再重復(fù)循環(huán)1和2，直至達(dá)到壓縮工期要求；計(jì)算增加的總直接費(fèi)用108方法二：統(tǒng)籌法50模型二，我們知道直接費(fèi)用是隨著完成時(shí)間的縮短而增加，而間接費(fèi)用卻會(huì)