圖與網(wǎng)絡(luò)的分析和優(yōu)化理論基礎(chǔ)綜述目錄TOC\o"1-2"\h\u12488圖與網(wǎng)絡(luò)的分析和優(yōu)化理論基礎(chǔ)綜述 1153811.1網(wǎng)絡(luò)計(jì)劃法 1228121.2網(wǎng)絡(luò)圖 1186711.3網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線 2229581.1.1路線與關(guān)鍵路線 2102381.1.2網(wǎng)絡(luò)時(shí)間的計(jì)算 361041.4網(wǎng)絡(luò)優(yōu)化 71.1網(wǎng)絡(luò)計(jì)劃法用于工程項(xiàng)目的計(jì)劃與控制的管理方法之一為網(wǎng)絡(luò)計(jì)劃法，在二十世紀(jì)五十年代末得到迅速的發(fā)展。按照網(wǎng)絡(luò)計(jì)劃法的起源，其主要分為計(jì)劃評(píng)審法（PERT）與關(guān)鍵路徑法(CPM)。主要原理是通過(guò)相關(guān)的邏輯分析與數(shù)學(xué)運(yùn)算，利用網(wǎng)絡(luò)圖的形式將某一工程中的工作組成和與其對(duì)應(yīng)的具體的關(guān)系表示出來(lái)，從而求出系統(tǒng)所需要的線路與關(guān)鍵的工序，并通過(guò)完善網(wǎng)絡(luò)計(jì)劃，從而對(duì)最優(yōu)方案做出選擇，來(lái)有效控制并管理相應(yīng)的項(xiàng)目。1.2網(wǎng)絡(luò)圖解決系統(tǒng)工程問(wèn)題的前提條件之一為先構(gòu)建好整個(gè)系統(tǒng)的網(wǎng)絡(luò)圖。網(wǎng)絡(luò)圖的定義為由結(jié)點(diǎn)、權(quán)和弧形成的有向圖。例：通過(guò)以下工序間的關(guān)系制作網(wǎng)絡(luò)圖：（大寫(xiě)字母表示各不同的工序）A：所需時(shí)間60天，后續(xù)工序有B,C,D,E；B：所需時(shí)間45天，后續(xù)工序?yàn)镴；C：所需時(shí)間10天，后續(xù)工序?yàn)镕；D：所需時(shí)間20天，后續(xù)工序有G,H；E：所需時(shí)間40天，后續(xù)工序?yàn)镠；F：所需時(shí)間18天，后續(xù)工序?yàn)镴；G：所需時(shí)間30天，后續(xù)工序?yàn)镴；H：所需時(shí)間15天，后續(xù)工序?yàn)镴；I：所需時(shí)間25天，后續(xù)工序?yàn)镴；J：所需時(shí)間35天，無(wú)后續(xù)工序。由題意，繪制出網(wǎng)絡(luò)圖，如圖1所示：圖1工程網(wǎng)絡(luò)圖圖3-1中，事項(xiàng)為帶圈數(shù)字，根據(jù)定義，事項(xiàng)就是前一項(xiàng)工序的開(kāi)始和后一項(xiàng)工序的結(jié)束，大寫(xiě)字母為相關(guān)工序，字母下為序號(hào)（事項(xiàng)）之間的箭頭，箭頭下標(biāo)有不盡相同的數(shù)字，該數(shù)字則為完成此項(xiàng)工序所需要的時(shí)間，即工期。繪制網(wǎng)絡(luò)圖時(shí)，先分解整體工程為若干不同的工序，并確定出工序的工期，然后通過(guò)各個(gè)工序的流程確定好工序之間的排列順序以及位置關(guān)系，然后再進(jìn)行工程網(wǎng)絡(luò)圖的繪制。1.3網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線1.1.1路線與關(guān)鍵路線在1.2的引例中，路線表如表1所示：表1線路表線路線路的組成各工序所需的時(shí)間（天）1127814021237812331246781704124578130512578150其中，所需時(shí)間最長(zhǎng)的一條路線即被稱(chēng)為關(guān)鍵路線，在對(duì)應(yīng)的網(wǎng)絡(luò)圖中用由粗實(shí)線構(gòu)成的箭線組表示。在表1中，線路3即為該工程的關(guān)鍵路線。一項(xiàng)工程中的關(guān)鍵工序就是關(guān)鍵路線上的工序。在某一項(xiàng)工程中，想要縮短該項(xiàng)工程的工期的充要條件即為縮短此工程中各個(gè)關(guān)鍵工序的工期。使資源得到充分利用，使工程完成時(shí)間得到壓縮，縮短整個(gè)工程的工期。1.1.2網(wǎng)絡(luò)時(shí)間的計(jì)算在解決一項(xiàng)工程問(wèn)題時(shí)，首先要制定該項(xiàng)工程的網(wǎng)絡(luò)計(jì)劃，而定制網(wǎng)絡(luò)計(jì)劃的前提則為確定該項(xiàng)工程的關(guān)鍵路線，所以，為了確定關(guān)鍵路線，就需要得到此項(xiàng)工程中各個(gè)工序的網(wǎng)絡(luò)時(shí)間。網(wǎng)絡(luò)時(shí)間分為作業(yè)時(shí)間、事項(xiàng)時(shí)間和作業(yè)（工序）的各種時(shí)間。(1)作業(yè)時(shí)間()：工序i到工序j所需要的工期之和；(2)事項(xiàng)時(shí)間：1)事項(xiàng)最早時(shí)間事項(xiàng)最早時(shí)間的定義為：某任一事項(xiàng)j可能最早的開(kāi)工時(shí)間。關(guān)于，有如下關(guān)系成立：（1）根據(jù)此關(guān)系式，則可以得出工程網(wǎng)絡(luò)圖1中的各事項(xiàng)的最早時(shí)間：再將所得出的各個(gè)結(jié)果匯總?cè)刖W(wǎng)絡(luò)圖中，如圖2所示：圖2調(diào)整后的工程網(wǎng)絡(luò)圖2)事項(xiàng)最遲時(shí)間事項(xiàng)最遲時(shí)間的定義為：在不誤計(jì)劃工程總工期的前提下，某事項(xiàng)j最遲必須完成的時(shí)間。關(guān)于，有如下關(guān)系式成立：=（n為終點(diǎn)事項(xiàng)）（2）根據(jù)此關(guān)系式，則可以得出工程網(wǎng)絡(luò)圖1中的各事項(xiàng)的最遲時(shí)間：再將各個(gè)工序的事項(xiàng)最遲時(shí)間匯總?cè)刖W(wǎng)絡(luò)圖的中，并結(jié)合上一步所計(jì)算出的各個(gè)工序的事項(xiàng)最小時(shí)間，最終可得出調(diào)整后的新的工程網(wǎng)絡(luò)圖。如圖2所示。(3)工序的各種時(shí)間：1)作業(yè)最早開(kāi)始時(shí)間有：（3）在圖2中，有2)作業(yè)最早結(jié)束時(shí)間有：（4）對(duì)于圖2所示的工程網(wǎng)絡(luò)圖，有：3)作業(yè)最遲開(kāi)始時(shí)間有：（5）對(duì)于圖2所示的工程網(wǎng)絡(luò)圖，有：4)作業(yè)最遲結(jié)束時(shí)間有：（6）對(duì)于圖2所示的工程網(wǎng)絡(luò)圖，有：1.4網(wǎng)絡(luò)優(yōu)化通常來(lái)說(shuō)，在制定了初始方案之后，需要根據(jù)指標(biāo)的要求，對(duì)初始方案進(jìn)行調(diào)整和優(yōu)化，因?yàn)楹茈y做到在最初的方案中得到完全合理的指標(biāo)。調(diào)整和優(yōu)化網(wǎng)絡(luò)圖的主要方法有：縮短網(wǎng)絡(luò)計(jì)劃的工期，使其符合規(guī)定工期的要求；亦或是工期不變，使需要的資源（人力、物力、資金）最小化；降低人力使用高峰，使其符合人力供應(yīng)能力，并在能夠達(dá)到最短工期地情況下連續(xù)且均衡地使用各工種人員；降低資源的需求高峰，使其在能達(dá)到的最短工期符合資源供應(yīng)情況；在費(fèi)用