《圖與網(wǎng)絡(luò)的探析和優(yōu)化理論基礎(chǔ)綜述》1800字

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