運籌學第二章ppt課件(已修改)

　

【正文】 主講教師： 聯系電話： 短 號： Email: 清華大學出版社 《運籌學教程》（第三版） 運籌學基礎 胡運權 主編 教材 運 籌 帷 幄 之 中 決 勝 千 里 之 外 運 籌 學 課 件 第二章 Linear progranming 對偶理論 與 靈敏度分析 例一 美佳公司計劃制造 Ⅰ 、 Ⅱ 兩種家電產品 。 已知各制造一件時分別占用的設備 A、 B的臺時 、 調試時間及 A、 B設備和調試工序每天可用于這兩種家電的能力 、各售出一件時的獲利情況如下表所示 。 問該公司應制造 Ⅰ 、 Ⅱ 兩種家電備多少件 ,使獲取的利潤為最大 。 設： x1—— A產品的生產量 x2—— B產品的生產量 利潤 max z= 2 x1 + x2 約束條件 5x2 ≤ 15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1， x2 ≥ 0 st . 第一節 線性規劃的對偶問題 一、對偶問題的提出 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 = 5 x1， x2 ， x3 ， x4 ， x5 ≥ 0 約束條件 st . 利潤 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5 1）標準化 ２）寫出初始單純形表（ 假設存在有單位矩陣 ） C 2 1 0 0 0 θ CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 15 24 5 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 σ 2 1 0 0 0 ３）最優解檢驗（ 唯一解、無限多解、無界解和無解 ） X*=(7/2,3/2,15/2,0,0) Z*= 17/2 θb x3 x4 x5 2 1x3 x1 x2 15/27/23/2 0 5/4 15/2 1 0 1/4 1/2 0 1/4 3/2 σ 0 0 0 1/4 1/2 一個問題？ 市場上設備 A、 設備 B和 調試工序每小時值多少錢 ？ 在什么價位時 ， 可以出租或 去租借適當數量的資源來擴大生產規模 ？ 6y2 + y3 分 析 設： y1 — 設備 A值的價值 y2 — 設備 B值的價值 y3 — 調試工序值的價值 ≥ 2 5y1 + 2y2 + y3 1 ≥ z= 15 y1 + 24y2 + 5y3 總價值 min y1 , y2 , y3 ≥ 0 st . 6y2 + y3 ≥ 2 5y1 + 2y2 + y3 1 ≥ z= 15 y1 + 24y2 + 5y3 min y1 , y2 , y3 ≥ 0 st . z39。= 15 y1 24y2 5y3 max st . 6y2 + y3 – y4 = 2 5y1 + 2y2 + y3 – y5 1 = y1, y2, y3, y4, y5 = 0 C 15 24 5 0 0 M M θ CB YB b y1 y2 y3 y4 y5 y6 y7 M M y6 y7 2 1 0 6 1 1 0 1 0 5 2 1 0 1 0 1 σ 5M15 8M24 2M5 M M 0 0 問題求解 6y2 + y3 ≥ 2 5y1 + 2y2 + y3 1 ≥ z= 15 y1 + 24y2 + 5y3 min y1 , y2 , y3 ≥ 0 st . z39。= 15 y1 24y2 5y3 max st . 6y2 + y3 – y4 = 2 5y1 + 2y2 + y3 – y5 1 = y1, y2, y3, y4, y5 = 0 C 15 24 5 0 0 θ CB YB b y1 y2 y3 y4 y5 24 5 y2 y3 1/4 1/2 5/4 1 0 1/4 1/4 15/2 0 1 1/2 3/2 σ 15/2 0 0 7/2 3/2 Y=(0, 188。, 189。 , 0, 0) z39。=17/2 z = 17/2 問題求解 Y*=(0, 188。, 189。 , 0, 0 ) 問題分析 問題 的解 6y2 + y3 ≥ 2 5y1 + 2y2 + y3 1 ≥ z= 15y1 + 24y2 + 5y3 min y1 , y2 , y3 ≥ 0 st . 問題： ？ 原問題： 利潤 max z= 2 x1 + x2 約束條件 5x2 ≤ 15 y1 6x1 + 2x2 ≤ 24 y2 x1 + x2 ≤ 5 y3 x1， x2 ≥ 0 st . 問題 的解 X*=(7/2,3/2,15/2,0,0) Z*= 17/2 Z*= 17/2 5*3/2 = 15/2 15 ＜ 6*7/2+2*3/2 = 24 24 = 7/2+3/2 = 5 5 = 結 論 ?兩個問題的最優解的值一致 ?最大值問題的最優解是最小值問題的可行解 ?一個問題的剩余變量（松弛變量） 不為 0（即有資源剩余），則對應問題的解為 0 ?一個決策變量不為 0，則對應的問題的約束條件的剩余變量 (松弛變量 ) 為