整數(shù)線性規(guī)劃ppt課件(參考版)
2025-01-24 23:17本頁面
【正文】 回到 b 重新標(biāo)記；(2) 少于 m條直線，到 第三步 ；78 清華算法的步驟：例 第三步： 進一步變換；? 在未劃線的元素中找 最小者 ，設(shè)為 ?? 對未被直線覆蓋的各元素減去 ?? 對兩條直線交叉點覆蓋的元素加上 ?? 只有一條直線覆蓋的元素保持不變以上步驟實際上仍是利用 定理 1第四步： 抹除所有標(biāo)記，回到 第二步 ，重新標(biāo)記；79 清華算法的步驟：例 答：最優(yōu)分配方案為 x13= x21= x34 = x42 =1，其余為 0， 即甲 ?C，乙 ?A，丙 ?D，丁 ?B， OBJ=2080 關(guān)于清華算法的適用條件n 要求所有 aij ?0q 若某些 aij 0 ，則利用定理 1 進行變換，使所有 bij ? 0n 目標(biāo)函數(shù)為 min型q 對于 max型目標(biāo)函數(shù)，將效率矩陣中所有 aij 反號，則等效于求 min型問題；再利用定理 1 進行變換，使所有 bij ? 0，則可采用清華算法 打破僵局時選擇不當(dāng)?shù)慕Y(jié)果：?? ??????結(jié)果僅出現(xiàn) 3 個標(biāo)記( )，但卻劃出 4 條線， 說明什么？！81線性規(guī)劃有關(guān)的英文詞匯n Operational/operations research 運籌學(xué)n Linear programming 線性規(guī)劃 Feasible domain 可行域n Convex set 凸集 Basic feasible solutions 基礎(chǔ)可行解n Simplex algorithm 單純型法 Pivot 主元 Pivoting 主元變換n Revised, dual simplex algorithm 修正、對偶單純型法n Relative cost 相對成本 (機會成本 ) Shadow price 影子價格n Slack, Surplus, Artificial variable 松弛，剩余，人工變量n Unbounded, Infeasible, Degenerate solution 無界解 , 無可行解 , 退化解n Duality 對偶性 Primal, dual problem 原問題，對偶問題n Complementary slackness 互補松弛 Sensitivity analysis 靈敏度分析n Ttransportation problem 運輸問題n Assignment problem 任務(wù)分配 (指派 ) 問題n Bipartite matching 兩部圖匹配 Hungarian method 匈牙利算法82。令未標(biāo)記零對應(yīng)的同行同列上其它未標(biāo)記零的個數(shù)為該零的 指數(shù) ，選 指數(shù)最小 的先標(biāo)記 ( )；采用
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1