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