上海交通大學(xué)管理科學(xué)-運籌學(xué)課件(存儲版)
【正文】 210解：把這個問題化為最短路問題用表示第年初購進一臺新設(shè)備，虛設(shè)一個點，表示第5年底；用弧表示第初購的設(shè)備一直使用到第年年底；弧上的數(shù)字表示第年初購進設(shè)備，一直使用到第年底所需支付的購買、維修的全部費用。對于每一個弧，對應(yīng)有一個（簡寫為），稱為弧的容量。定義 設(shè)是一個可行流，是從到的一條鏈，若滿足下列條件，是可行流的一條增廣鏈。最大流量最小截量定理：任一個網(wǎng)絡(luò)中，從到的最大流的流量等于分離，的最小截集的容量。定理1為我們提供了尋求網(wǎng)絡(luò)最大流的一個方法。⑵調(diào)整過程令調(diào)整量，去掉所有標(biāo)號，對新的可行流重新進行標(biāo)號過程。檢查，在弧上，則給標(biāo)號。開始給標(biāo)號，檢查，給標(biāo)以，檢查，弧上，弧上，均不符合條件，標(biāo)號過程無法繼續(xù)下去，算法結(jié)束。 網(wǎng)絡(luò)計劃20世紀(jì)50年代以來，國外陸續(xù)出現(xiàn)一些計劃管理的新方法，如關(guān)鍵路線法（Critical Path Method，縮寫為CPM），計劃評審方法（Program Evaluation Review Technique，縮寫為PETR）等。工序是在工藝技術(shù)和組織管理上相對獨立的工作或活動，需要一定的時間與資源，而事項則表示一個或若干工序的開始或結(jié)束，是相繼工序的分界點。⑶兩節(jié)點之間只能有一條弧。虛工序還可以用于正確表示平行與交叉作業(yè)。避免弧的交叉，盡可能將關(guān)鍵路線布置在中心位置，將聯(lián)系緊密的工序布置在相近的位置。一、 工序時間的確定工序的所需時間可記為，有以下兩種情況：⑴完成工序所需時間確定，只給出一個時間值。⑵事項的最遲時間事項的最遲時間用表示，它表明在不影響任務(wù)總工期條件下，以它為始點的工序的最遲必須開始時間，或以它為終點的各工作的最遲必須完成時間?？倳r差為零的工序，開始和結(jié)束的時間沒有一點機動的余地，由這些工序所組成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線，這些工序就是關(guān)鍵工序。⑶時差根據(jù)圖522中的結(jié)果，可以求出各工序的總時差。 時間資源優(yōu)化在編制網(wǎng)絡(luò)計劃安排工程進度時，考慮時間優(yōu)化的同時，盡量合理地利用有限的資源。顯然，在網(wǎng)絡(luò)計劃中，最低成本日程具有重要意義。重復(fù)以上三個步驟，直到工期不能再縮短為止。由于一條關(guān)鍵路線①→③→④→⑥上各工序工時不能縮短，計算結(jié)束。（1） 確定所有的截集；（2） 求最小截集的容量；（3） 證明指出的流是最大流。表57工作工時（d）緊前工序工作工時（d）緊前工序A5F4B，CB8A，CG8CC3AH2F，GD6CI4E，HE10B，CJ5F，G511 已知下列資料表58活動作業(yè)時間（d）緊前活動正常完成進度的直接費用（百元）趕進度1天所需費用（百元）A4205B8304C6B153D3A52E5A184F7A407G4B，D103H3E，F(xiàn)，G156工程的間接費5（百元/天），求出該項工程的最低成本日程。某單位今年購進一臺，問如何確定更新方案可使5年里總支出最小（不管設(shè)備使用了多少年，其殘值為0）。增加直接費用2（100+200）=600元，減少間接費用2330=660元。解：按下列步驟進行計算。⑵間接費用是指管理費、辦工費等，常按施工時間長短分?jǐn)偂?時間優(yōu)化根據(jù)對計劃進度的要求，縮短工程完工時間。再從后面開始計算各事項最遲時間，如總完工事項⑩的，事項⑦的將結(jié)果填入編號上方空格 右邊。工序最遲必須完工時間等于事項的最遲時間四、時差。事項最早時間可用下列遞推公式，按照事項編號從小到大順序逐個計算。要想使任務(wù)按期完或提前完工，就要在關(guān)鍵路線的關(guān)鍵工序上想辦法。根據(jù)上述規(guī)則繪制網(wǎng)絡(luò)圖，是為了保證網(wǎng)絡(luò)圖的正確性。也就是說，是的緊前工序，而只有是的緊前工序。在繪制網(wǎng)絡(luò)圖時，還要注意以下規(guī)則：⑴網(wǎng)絡(luò)圖只能有一個總起點事項，一個總終點事項。 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖是由節(jié)點、弧及權(quán)所構(gòu)成的有向圖，即有向的賦權(quán)圖。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。上：上：其余的不變。檢查，在弧上，不滿足標(biāo)號條件。③ 重復(fù)上述步驟，直到被標(biāo)上號或不再有頂點可標(biāo)號為止。記，于是得到一個截集，顯然必有所以。定義 給一截集，把截集中所有弧的容量之和稱為這個截集的容量，記作不難證明，任何一個可行流的流量都不會超過任一截量的容量，即。其實最大流問題是一個特殊的線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系求解，更為直觀簡便。20世紀(jì)50年代Ford ，F(xiàn)ulkerson建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分。試制定一個5年更新計劃，使總支出最少。如已知，因故記下。顯然，從到的最短路總是從出發(fā)，沿著一條路到某點，再沿到的，所以，從到的這條路必定是從到的最短路。⑸考察，在所有標(biāo)號中，最小，令。⑵若點為剛得到標(biāo)號的點，考慮，且為標(biāo)號。算法的基本思路基于以下原理：若是從到的最短路，是中的一個點，那么從沿到的路是從到的最短路。定義1 網(wǎng)絡(luò)，其邊是有權(quán)，構(gòu)造矩陣其中，稱矩陣為網(wǎng)絡(luò)的權(quán)矩陣。圖可分為無向圖和有向圖。“有限圖與無限圖的理論”，發(fā)表于1936年。第5章 圖與網(wǎng)絡(luò)分析 圖論的基本概念 引言瑞士數(shù)學(xué)歐拉（Euler）在1736年發(fā)表了圖論方面的第一篇論文，題為
公司管理相關(guān)推薦
鄂ICP備17016276號-1