【正文】 G C A E F D H 到期時(shí)間 2 8 13 14 20 30 36 開始加工時(shí)間 0 2 5 7 11 18 26 加工時(shí)間 2 3 2 4 7 8 3 完成加工時(shí)間 2 5 7 11 18 26 29 第 5步： 現(xiàn)在已經(jīng)沒有工作被延誤了，所以我們將工作 B加到時(shí)序的最后。 Cij 第 i個(gè)操作員完成第 j項(xiàng)任務(wù)的成本 Xij min ΣΣCijXij ΣXij=1 ΣXij=1 Xij=0,1 i=1,?,n, j=1,?,m =1 (分派操作員 i完成任務(wù) j) =0 (不分派操作員 i完成任務(wù) j) j i 最短路問題 最短路問題 G(V,E) 為 連通圖，邊（ vi,vj)的權(quán)為 lij，求一條道路，使它從 vs到 vt的總權(quán)最少？ 方法： 1 動(dòng)態(tài)規(guī)劃法 2 Dijkstra算法 引例：某一配送中心要給一個(gè)快餐店送快餐原料，應(yīng)按什么路線送貨才能使送貨時(shí)間最短？ V2 16 v4 7 v6 4 6 V1 12 2 8 v7 18 5 V3 6 v5 （配送中心） （快餐店） 最大流問題 最大流問題 引例： 某石油公司擁有一個(gè)管道網(wǎng)絡(luò)（如圖），使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售地。 為此我們采用上述五個(gè)步驟。 規(guī)劃與決策 一 般線性規(guī)劃建模過程 Step 1. 理解及分析實(shí)際問題，資源狀況，解決問題實(shí)現(xiàn)的目標(biāo)； Step 2. 確定決策變量（ x1, … ， xn） — 解決問題的具體方案（量化方案）； Step 3. 確定目標(biāo)函數(shù)及約束條件； Step 4. 應(yīng)用線性規(guī)劃軟件求解； Step 5. 檢驗(yàn)所求得的解決方案是否可行：如可行，則開始具體實(shí)施；否則，轉(zhuǎn) Step 1 或 Step2 修改模型。如果已經(jīng)沒有工作被延誤，這便是最優(yōu)解，否則，則進(jìn)行第 2步。在重復(fù)做這些的時(shí)候，總是從時(shí)序的兩端向內(nèi)進(jìn)行，新安排的工作離時(shí)序的中間更近。如果再找不到這樣的任務(wù)，這就是最優(yōu)解。 第 3步： 找出第 2步所找工作之前（包括這一工作本身）加工時(shí)間最長(zhǎng)的工作。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A、B兩種原材料的消耗，資源限制及市場(chǎng)價(jià)格如下表： Ⅰ Ⅱ 資源限制 設(shè)備 1 1 300臺(tái)時(shí) 原材料 A 2 1 400千克 原材料 B 0 1 250千克 市場(chǎng)價(jià)格 50 100 ? 問題：如何安排生產(chǎn)，才能使工廠獲利最多？ 規(guī)劃與決策 分析： （ 1）設(shè) x1 — 生產(chǎn)產(chǎn)品 Ⅰ 的數(shù)量； x2 — 生產(chǎn)產(chǎn)品 Ⅱ 的數(shù)量。 第 5步： 將第 4步抽出的工作放到時(shí)序的末尾。 工作 A