哈爾濱工業(yè)大學運籌學大作業(yè)-對偶單純形法對比

1、運籌學課程運籌學對偶單純形法與單純形法 對比分析大作業(yè)XX 工業(yè)高校工業(yè)工程系同學 XX: 學號 ： 11208401 指導(dǎo)老師 ：成果：評語：運籌學對偶單純形法與單純形法對比分析摘 要 ： 這 篇 論 文 主 要 介 紹 了 對 偶 單 純 形 法 的 實 質(zhì) 、 原 理 、 流 程 和 適 用 條 件 等 ； 將 對 偶 單 純 形 法 與 單 純 形 法 的 基 本 思 想 進 行 對 比 分 析 , 從 而 說 明 對 偶 單 純 形 法 的 優(yōu) 點 和 適 用 X 圍 ；關(guān) 鍵 詞 ： 對 偶 單 純 形 法 ； 對 偶 理 論 ； 單 純 形 法 ； 基 本 思 想在 線 性 規(guī)

2、劃 早 期 發(fā) 展 階 段 的 眾 多 重 要 發(fā) 現(xiàn) 中 , 對 偶 的 概 念 與 其 分 支 是 其 中 最 重 要 的 內(nèi) 容 之 一 ； 這 個 發(fā) 現(xiàn) 指 出 , 對 于 任 何 一 個 線 性 規(guī) 劃 問 題 都 具 有 對 應(yīng) 的 稱 為 對 偶 問 題 的 線 性 規(guī) 劃 問 題 ； 對 偶 問 題 與 原 問 題 的 關(guān) 系 在 眾 多 領(lǐng) 域 都 非 常 有 用 ；（ 一 ） 教 學 目 標 ：通 過 對 偶 單 純 形 法 的 學 習 , 加 深 對 對 偶 問 題 的 理 解 ； 掌 握 對 偶 單 純 形 法 的 解 題 過 程 , 理 解 對 偶 理 論 的 其

3、原 理 , 了 解 對 偶 單 純 形 法 的 作 用 和 應(yīng) 用 X 圍（ 二 ） 教 學 內(nèi) 容 ：1 ） 對 偶 單 純 形 法 的 思 想 來 源 2 ） 對 偶 單 純 形 法 原 理 3 ） 對 偶 理 論 的 實 質(zhì) 4 ） 單 純 形 法 和 對 偶 單 純 形 法 的 比 較（ 三 ） 教 學 進 程 ：一 、 對 偶 單 純 形 法 的 思 想 來 源 所 謂 對 偶 單 純 形 法 , 就 是 將 單 純 形 法 應(yīng) 用 于 對 偶 問 題 的 計 算 , 該 方 法 是由 美 國 數(shù) 學 家 C. 萊 姆 基 于 1954年 提 出 的 ,它 并 不 是 求 解 對 偶

4、 問 題 解 的 方 法 ,而 是 利 用 對 偶 理 論 求 解 原 問 題 的 解 的 方 法 ；1 / 9 二 、 對 偶 問 題 的 實 質(zhì) 下 面 是 原 問 題 的 標 準 形 式 以 與 其 對 應(yīng) 的 對 偶 問 題 ：原 問 題nMax Z = cj xjj= 1n對 偶 問 題mMinW = b iyij =1 ns.t. aij xj b ii = 1,2 ,. , ms.t . a ijy i cjj = 1 ,2,. ,nj= 1j =1x j 0j = 1 ,2 ,. , nyi 0i = 1 ,2 ,. , m從 而 可 以 發(fā) 現(xiàn) 如 下 規(guī) 律 ：1. 原 問

5、 題 目 標 函 數(shù) 系 數(shù) 是 對 偶 問 題 約 束 方 程 的 右 端 項 ；2. 原 問 題 約 束 方 程 的 右 端 項 是 對 偶 問 題 目 標 函 數(shù) 的 系 數(shù) ；3. 原 問 題 一 個 變 量 在 所 有 約 束 方 程 中 的 系 數(shù) 是 對 偶 問 題 一 個 約 束 方 程 中 的 所 有 系 數(shù) ；三 、 對 偶 單 純 形 法 原 理 對 偶 單 純 形 法 是 通 過 尋 找 原 問 題 的 對 偶 問 題 的 可 行 解 來 求 解 原 問 題 的 最 優(yōu) 解 的 方 法 , 它 的 應(yīng) 用 包 括 影 子 價 格 和 靈 敏 度 分 析 等 ； 為 了

6、理 解 對 偶 單 純 形 法 為 什 么 能 夠 解 出 原 方 程 的 最 優(yōu) 解 , 我 們 需 要 對 對 偶 理 論 的 幾 個 基 本 原 理 有 所 了 解 ；1. 弱 對 偶 性 如 果 . .j = 1 ,. ,n 是 原 問 題 的 可 行 解 ,. .i = 1 ,. ,m 是 其 對 偶 問 題 的 可 行 解 , 就 恒 有n cjx.j j= 1m b iy.i i= 1證 明 ： 由 于 對 偶 方 程 中 原 問 題 的 約 束 條 件 是 各 行 的 a i j x j 之 和 小 于 等 于 y i 的 系 數(shù) b i, 而 對 偶 問 題 的 約 束 條

7、件 是 各 行 的 a i jy i 之 和 小 于 等 于 x j 的 系 數(shù) c j,故 將 nj= 1c jx.j和 mi =1b iy.i分 別 和 mi= 1nj= 1x.jaij y.i比 較 , 可 得 上 述 結(jié) 論 ；2 / 9 2. 最 優(yōu) 性 如 果 x.j j = 1 ,. ,n 是 原 問 題 的 可 行 解 , y.i i = 1 ,. , m 是 其 對 偶 問 題 的 可 行 解 , 且 有n cj x.j j= 1m = b iy.i i= 1就 x.jj = 1, . ,n 是 原 問 題 的 最 優(yōu) 解 ,y.i i = 1 ,. , m 是 其 對 偶

8、問 題 的 最 優(yōu) 解 ；證 明 ： 由n cjx.j j= 1m b iy.i i= 1可 得nmn cj x.j b iy.i= cjx.jj= 1i =1j= 1mnm b iy.i c jx.j= b iy.ii= 1j =1i =1故 可 知 x.j j = 1 , . ,n 是 原 問 題 的 最 優(yōu) 解 , y.ii = 1,. ,m 是 其 對 偶 問 題 的 最 優(yōu) 解 ；3. 強 對 偶 性 如 果 原 問 題 有 最 優(yōu) 解 , 那 么 其 對 偶 問 題 也 有 最 優(yōu) 解 , 且 有 maxz=minw. C證 明 ： 設(shè)B為 原 問 題 式 1 的 最 優(yōu) 基 ,

9、那 么 當 基 為B時 的 檢 驗 數(shù) 為C B1A, 其 中C 為 由 基 變 量 的 價 值 系 數(shù) 組 成 的 價 值 向 量 ；既 然 B 為 原 問 題 式 1 的 最 優(yōu) 基 , 那 么 有CC B1A0；令YC B1, 那 么 有CYA0YAC , 從 而YC B1是 對 偶 問 題 式 2 的可 行 解 ；這 樣 一 來 ,YC B1是 對 偶 問 題 的 可 行 解 ,XB1 B b 是 原 問 題 的 最 優(yōu) 基 可行 解 ；由 于CXC XBCNXN1 C B b , 而Yb1 C B b , 從 而 有 CXYb ； 根 據(jù) 最 優(yōu)性 , 命 題 得 證 ；3 / 9

10、4. 線 性 規(guī) 劃 的 問 題 原 問 題 與 對 偶 問 題 之 間 存 在 一 對 互 補 的 基 解 , 其 中 原 問 題 的 松 弛 變 量 對 應(yīng) 對 偶 問 題 的 變 量 , 對 偶 問 題 的 剩 余 變 量 對 應(yīng) 原 問 題 的 變 量 ； 這 些 相 互 對 應(yīng) 的 變 量 如 果 在 一 個 問 題 中 是 基 變 量 , 就 在 另 一 問 題 中 是 非 基 變 量 ； 將 這 對 互 補 的 基 解 分 別 代 入 原 問 題 和 對 偶 問 題 的 目 標 函 數(shù) 有 z=w ；四 、 對 偶 單 純 形 算 法 流 程 在 上 述 的 理 論 基 礎(chǔ) 上

11、, 可 知 用 單 純 形 法 求 解 線 性 規(guī) 劃 問 題 時 , 在 得 到 原 問 題 的 一 個 基 可 行 解 問 題 同 時 , 在 檢 驗 數(shù) 行 得 到 對 偶 問 題 的 一 個 基 解 ； 單 純 形 法 的 基 本 思 想 是 保 持 原 問 題 為 可 行 解 的 基 礎(chǔ) 上 , 通 過 迭 代 增 大 目 標 函 數(shù) ,當 其 對 偶 問 題 也 為 可 行 解 時 , 就 達 到 了 目 標 函 數(shù) 的 最 優(yōu) 值 ；而 對 偶 單 純 形 法 的 基 本 思 想 就 是 保 持 對 偶 問 題 為 可 行 解 的 前 提 下 （ 即 單 純 性 表 最 后 一

12、行 檢 驗 數(shù) 都 小 于 零 ）,通 過 迭 代 減 小 目 標 函 數(shù) ,當 原 問 題 也 是 可 行 解 時 , 就 得 到 了 目 標 函 數(shù) 的 最 優(yōu) 解 ；故 我 們 可 以 得 到 對 偶 單 純 形 法 求 解 過 程 如 下 ：1. 將 原 問 題 化 為 標 準 型 , 找 到 一 個 檢 驗 數(shù) 都 小 于 等 于 零 的 對 偶 問 題 的 初 始 可 行 基 ；2. 確 定 換 出 基 的 變 量 對 于 小 于 零 的 b i , 找 到 最 小 的 一 個 b r , 其 對 應(yīng) 的 x r 為 換 出 基 的 變 量 3. 確 定 換 入 基 的 變 量（

13、1 ） 為 了 使 迭 代 后 表 中 的 第 r 行 基 變 量 為 正 值 , 因 而 只 有 對 應(yīng) a i j 小 于 零 的 非 基 變 量 才 可 以 作 為 換 入 基 的 變 量 ；（ 2 ） 為 了 使 迭 代 后 表 中 對 偶 問 題 仍 為 可 行 解 , 令 = min jcj -zj|ari 0 =cs - zsa ija rs稱 a r s 為 主 元 素 , x s 為 換 入 基 的 變 量 ；4. 用 換 入 變 量 替 換 換 出 變 量 , 得 到 一 個 新 的 基 ； 再 次 檢 查 是 否 所 有 的 b i大 于 等 于 零 ； 如 果 是 ,

14、就 找 到 了 最 優(yōu) 解 , 如 果 否 , 就 再 次 進 行 變 換 ；4 / 9 對 偶 單 純 形 法 的 算 法 流 程 圖開頭化原問題為標準型找出一個對偶問題的初始可行基 B0,運算 非基變量檢驗數(shù)（全部檢驗數(shù) j 0）并 列出初始單純形表bi 都0？是否確定換出和換入的基變量：換出最小的“ 右端項”bi 所對應(yīng)的基變量；按公 式 =min j/a ij,aij 0= s/a ij 運算最小比值 ,所對應(yīng)的基變量為換入運算檢驗數(shù), 列出新的單純形表已找到最優(yōu)解終止5 / 9 五 、 對 偶 單 純 形 法 例 題 下 面 用 一 個 例 子 來 說 明 對 偶 單 純 形 法 的

15、 解 題 過 程 ；Min z=5x1+2x2+4x3 s.t. 3x1 + x2 + 2x3 4 6x1 + 3x2 + 5x3 10 x1 ,x2 ,x3 01. 化 為 標 準 型Max z =-5x1-2x2-4x3+0 x4+0 x5 - 3x1 - x2 - 2x3 + x4 = - 4s.t. - 6x1 - 3x2 - 5x3 + x5 = - 10 x1 , x2 , x3 , x4 , x5 02. 列 出 原 始 單 純 形 表-4 c j -5 -2 -4 0 0 C B 基bx 1x 2x 3x 4x 50 0 x 4-3 -1 -2 1 -6 -3 -5 0 1 0

16、 x 5 -10 0 c j-z j-5 -2 -4 0 3. 找 出 最 小 的 bi , 即 b5=-10.選 擇 x5作 為 換 出 變 量 ； = min jcj -zj|ari n, 那 么 對 偶 問 題 有 n 個 約 束 方 程 , 而 原 問 題 有 m 個 約 束 方 程 , 所 以 對 偶 問 題 有 更 少 的 約 束 方 程 數(shù) 量 , 那 么 通 過 對 偶 單 純 形 法 的 運 用 比 起 直 接 只 用 單 純 形 法 將 會 顯 著 的 減 少 計 算 量 ；3. 弱 對 偶 性 和 強 對 偶 性 是 對 偶 理 論 的 關(guān) 鍵 原 理 ； 對 偶 問 題

17、 可 以 用 來 對 原 問 題 的 計 劃 方 案 進 行 評 價 ； 我 們 可 以 用 一 個 對 偶 問 題 的 可 行 解 和 目 前 原 問 題7 / 9 的 計 劃 方 案 進 行 比 較 , 如 果 兩 個 目 標 函 數(shù) 值 相 等 或 比 較 接 近 , 就 可 以 說 明 原 問 題 的 計 劃 方 案 已 經(jīng) 是 可 以 看 做 最 優(yōu) 了 ；4. 對 偶 理 論 在 靈 敏 度 分 析 和 影 子 價 格 計 算 中 有 著 重 要 的 作 用 ；七 、 單 純 形 法 和 對 偶 單 純 形 法 的 基 本 思 想 比 較 通 過 以 上 的 分 析 可 知 , 對

18、 偶 單 純 形 法 其 實 相 當 于 單 純 形 法 的 一 種 變 形 ,只 不 過 在 運 用 對 偶 單 純 形 法 解 線 性 規(guī) 劃 時 需 要 將 單 純 形 表 旋 轉(zhuǎn) 一 下 ； 單 純 形 表 中 的 b 列 實 際 上 是 對 偶 問 題 的 非 基 變 量 的 檢 驗 數(shù) , 而 原 單 純 形 表 的 檢 驗 數(shù) 為 對 偶 問 題 的 基 解 , 這 樣 可 以 理 解 為 通 過 旋 轉(zhuǎn) 90 運 用 單 純 形 法 求 解 線 性 規(guī) 劃 ；從 求 解 思 路 上 來 說 , 單 純 形 法 是 首 先 保 證 基 解 是 原 問 題 的 基 可 行 解 （