上海交通大學(xué)管理科學(xué)-運(yùn)籌學(xué)課件(編輯修改稿)
2025-05-15 06:31 本頁面
【文章內(nèi)容簡介】 法分2步：第1步是標(biāo)號過程，通過標(biāo)號來尋找增廣鏈；第2步是調(diào)整過程，沿增廣鏈調(diào)整以增加流量。⑴標(biāo)號過程每個標(biāo)號點的標(biāo)號包含兩部分：第1個標(biāo)號明它的標(biāo)號從哪一點得到，以便找出增廣鏈；第2個標(biāo)號是為確定增廣鏈的調(diào)整量用的。① 給發(fā)點以標(biāo)號；② 選擇一個已標(biāo)號的點，對于的所有未標(biāo)號的鄰接點，如果，且，令，并給以標(biāo)號；如果，且，令，并給以標(biāo)號。③ 重復(fù)上述步驟，直到被標(biāo)上號或不再有頂點可標(biāo)號為止。如果得到標(biāo)號，說明存在增廣鏈，轉(zhuǎn)入調(diào)整過程；若未獲得標(biāo)號，標(biāo)號過程已無法進(jìn)行時，說明已是最大流。⑵調(diào)整過程令調(diào)整量，去掉所有標(biāo)號，對新的可行流重新進(jìn)行標(biāo)號過程。例54 用標(biāo)號法求圖513所示網(wǎng)絡(luò)的最大流?；∨缘臄?shù)是。解：經(jīng)檢查，網(wǎng)絡(luò)中的流是可行流，下面分析是否可以增加流量。（一） 標(biāo)號過程 首先給標(biāo)上；檢查，在弧上，則的標(biāo)號為，其中。在弧上，不滿足標(biāo)號條件。檢查，在弧上，不滿足標(biāo)號條件。在弧上，則的標(biāo)號為。檢查，在弧上，則給標(biāo)號。在弧上，給標(biāo)號。在中任選一個進(jìn)行檢查，例如，在弧 上，給標(biāo)號。因有了標(biāo)號，故轉(zhuǎn)入調(diào)整過程。（二）調(diào)整過程按點的第一個標(biāo)號找到一條增廣鏈，如圖514中雙箭線所示。則見：按，在增廣鏈上調(diào)整。上：上：其余的不變。調(diào)整后得到圖515所示的可行流，對這個可行流進(jìn)行標(biāo)號，尋找增廣鏈。開始給標(biāo)號，檢查，給標(biāo)以，檢查，弧上，弧上，均不符合條件，標(biāo)號過程無法繼續(xù)下去，算法結(jié)束。這時圖515 可行流即最大流。最大流為：。與此同時可找到最小截集，其中為標(biāo)號點集，即，為未標(biāo)號點集，截集，最小截量為5。由上述可見，用標(biāo)號法找增廣鏈找到最大流的同時，得到一個最小截集。最小截集的容量大小影響網(wǎng)絡(luò)最大流量。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。另一方面，一旦最小截集中弧的通過能力被 降低，就會使總的輸送量減少。 網(wǎng)絡(luò)計劃20世紀(jì)50年代以來，國外陸續(xù)出現(xiàn)一些計劃管理的新方法，如關(guān)鍵路線法（Critical Path Method，縮寫為CPM），計劃評審方法（Program Evaluation Review Technique，縮寫為PETR）等。這些方法都是建立在網(wǎng)絡(luò)模型基礎(chǔ)之上，稱為網(wǎng)絡(luò)計劃技術(shù)，廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、科研等計劃管理中，對縮短工期，節(jié)約人力、物力和財力，提高經(jīng)濟(jì)效益發(fā)揮了重要作用。我國數(shù)學(xué)家華羅庚先生將這些方法總結(jié)概括為統(tǒng)籌方法，引入中國并推廣應(yīng)用。統(tǒng)籌方法的基本原理是：從需要管理的任務(wù)的總進(jìn)度著眼，以任務(wù)中各工作所需要的工時為時間因素，按照工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)全貌，實現(xiàn)管理過程的模型化。然后進(jìn)行時間參數(shù)計算，找出計劃中的關(guān)鍵工作和關(guān)鍵路線，對任務(wù)的各項工作所需的人、財、物通過改善網(wǎng)絡(luò)計劃作出合理安排，得到最優(yōu)方案并付諸實施。通過對各種評價指標(biāo)進(jìn)行定量化分析，在計劃的實施過程中，進(jìn)行有效的監(jiān)督與控制，以保證任務(wù)高質(zhì)量地完成。 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖是由節(jié)點、弧及權(quán)所構(gòu)成的有向圖，即有向的賦權(quán)圖。節(jié)點表示事項，弧表示工序（活動）。工序是在工藝技術(shù)和組織管理上相對獨立的工作或活動，需要一定的時間與資源，而事項則表示一個或若干工序的開始或結(jié)束，是相繼工序的分界點。權(quán)表示為完成某個工序所需要的時間或資源等數(shù)據(jù)。例如某工序可以表示為：，為箭頭節(jié)點，表示工序開始，為箭頭尾節(jié)點，表示工序結(jié)束，5為完成本工序所需時間。網(wǎng)絡(luò)圖是有向圖，按照工藝流程的順序，規(guī)定工序從左向右排列，再給節(jié)點統(tǒng)一編號，節(jié)點由小到大編號。對任一工序來講，要求。始點編號可以從1開始。在繪制網(wǎng)絡(luò)圖時，還要注意以下規(guī)則：⑴網(wǎng)絡(luò)圖只能有一個總起點事項，一個總終點事項。⑵網(wǎng)絡(luò)圖不能有缺口和回路。⑶兩節(jié)點之間只能有一條弧。⑷正確表示工作之間的前行、后繼關(guān)系。如圖516表示兩工序結(jié)束后，兩工序才開始。為的緊前工序，為的緊后工序。⑸虛工序的應(yīng)用。如果的工序關(guān)系是：必須在均完成后才能開工，而只要在完成后即可開工。也就是說，是的緊前工序，而只有是的緊前工序。這樣必須用圖517來表示，其中③→④是一個虛工序，只表示③、④兩節(jié)點的銜接關(guān)系，不需要人力、物力等資源和時間。虛工序還可以用于正確表示平行與交叉作業(yè)。一道工序分為幾道工序同時進(jìn)行，稱為平行作業(yè)。如圖518（a）中市場調(diào)研需12天，如增加人力分為3組同時進(jìn)行，可以畫為518（b）。兩個或兩個以上的工作交叉進(jìn)行，稱為交叉作業(yè)。如工作與工作分別為挖溝和埋管子，那么它們的關(guān)系可以是挖一段，埋一段，不必等溝全部挖好再埋。這樣，我們可用圖519來表示交叉作業(yè)。根據(jù)上述規(guī)則繪制網(wǎng)絡(luò)圖，是為了保證網(wǎng)絡(luò)圖的正確性。此外，為了使圖面布局合理，層次分明，條理清楚，還要注意畫圖技巧。避免弧的交叉，盡可能將關(guān)鍵路線布置在中心位置，將聯(lián)系緊密的工序布置在相近的位置。例55 某項新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作（如表53）列示各工序與所需時間以及它們之間的相互關(guān)系。要求編制該項工程的網(wǎng)絡(luò)計劃。表53工序工序內(nèi)容緊前工序工時（周）A市場調(diào)查/4B資金籌措/10C需求分析A3D產(chǎn)品設(shè)計A6E產(chǎn)品研制D8F制定成本計劃C，E2G制定生產(chǎn)計劃F3H籌備設(shè)備B，G2I原材料準(zhǔn)備B，G8J安裝設(shè)備H5K人員準(zhǔn)備G2L準(zhǔn)備開工投產(chǎn)I，J，K1根據(jù)以上規(guī)則，繪制的網(wǎng)絡(luò)圖如520
公司管理相關(guān)推薦
鄂ICP備17016276號-1