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