《運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用》胡運(yùn)權(quán)主編,哈工大出版社,完整版ppt課件

運(yùn)籌學(xué) OperationsResearch 經(jīng)濟(jì)學(xué)核心課程 緒論 1 運(yùn)籌學(xué)簡(jiǎn)述 2 運(yùn)籌學(xué)的主要內(nèi)容 3 本課程的教材及參考書(shū) 4 本課程的特點(diǎn)和要求 5 本課程授課方式與考核 6 運(yùn)籌學(xué)在工商管理中的應(yīng)用 本章主要內(nèi)容 運(yùn)籌學(xué)簡(jiǎn)述 運(yùn)籌學(xué) OperationsResearch 系統(tǒng)工程的最重要的理論基礎(chǔ)之一 在美國(guó)有人把運(yùn)籌學(xué)稱(chēng)之為管理科學(xué) ManagementScience 運(yùn)籌學(xué)所研究的問(wèn)題 可簡(jiǎn)單地歸結(jié)為一句話(huà) 依照給定條件和目標(biāo) 從眾多方案中選擇最佳方案 故有人稱(chēng)之為最優(yōu)化技術(shù) 運(yùn)籌學(xué)簡(jiǎn)述 運(yùn)籌學(xué)的歷史 運(yùn)作研究 OperationalResearch 小組 解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題 例如 如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍德空襲對(duì)商船如何進(jìn)行編隊(duì)護(hù)航 使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度 才能增加對(duì)德國(guó)潛艇的殺傷力等 運(yùn)籌學(xué)的主要內(nèi)容 數(shù)學(xué)規(guī)劃 線(xiàn)性規(guī)劃 整數(shù)規(guī)劃 目標(biāo)規(guī)劃 動(dòng)態(tài)規(guī)劃等 圖論存儲(chǔ)論排隊(duì)論對(duì)策論排序與統(tǒng)籌方法決策分析 本課程的教材及參考書(shū) 選用教材 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用 胡運(yùn)權(quán)主編哈工大出版社參考教材 運(yùn)籌學(xué)教程 胡運(yùn)權(quán)主編 第2版 清華出版社 管理運(yùn)籌學(xué) 韓伯棠主編 第2版 高等教育出版社 運(yùn)籌學(xué) 修訂版 錢(qián)頌迪主編清華出版社 本課程的特點(diǎn)和要求 先修課 高等數(shù)學(xué) 基礎(chǔ)概率 線(xiàn)性代數(shù)特點(diǎn) 系統(tǒng)整體優(yōu)化 多學(xué)科的配合 模型方法的應(yīng)用運(yùn)籌學(xué)的研究的主要步驟 本課程授課方式與考核 講授為主 結(jié)合習(xí)題作業(yè) 運(yùn)籌學(xué)在工商管理中的應(yīng)用 運(yùn)籌學(xué)在工商管理中的應(yīng)用涉及幾個(gè)方面 生產(chǎn)計(jì)劃運(yùn)輸問(wèn)題人事管理庫(kù)存管理市場(chǎng)營(yíng)銷(xiāo)財(cái)務(wù)和會(huì)計(jì)另外 還應(yīng)用于設(shè)備維修 更新和可靠性分析 項(xiàng)目的選擇與評(píng)價(jià) 工程優(yōu)化設(shè)計(jì)等 運(yùn)籌學(xué)在工商管理中的應(yīng)用 Interface上發(fā)表的部分獲獎(jiǎng)項(xiàng)目 管理運(yùn)籌學(xué) 軟件介紹 管理運(yùn)籌學(xué) 2 0版包括 線(xiàn)性規(guī)劃 運(yùn)輸問(wèn)題 整數(shù)規(guī)劃 0 1整數(shù)規(guī)劃 純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃 目標(biāo)規(guī)劃 對(duì)策論 最短路徑 最小生成樹(shù) 最大流量 最小費(fèi)用最大流 關(guān)鍵路徑 存儲(chǔ)論 排隊(duì)論 決策分析 預(yù)測(cè)問(wèn)題和層次分析法 共15個(gè)子模塊 Chapter1線(xiàn)性規(guī)劃 LinearProgramming LP的數(shù)學(xué)模型圖解法單純形法單純形法的進(jìn)一步討論 人工變量法LP模型的應(yīng)用 本章主要內(nèi)容 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 1 規(guī)劃問(wèn)題 生產(chǎn)和經(jīng)營(yíng)管理中經(jīng)常提出如何合理安排 使人力 物力等各種資源得到充分利用 獲得最大的效益 這就是規(guī)劃問(wèn)題 線(xiàn)性規(guī)劃通常解決下列兩類(lèi)問(wèn)題 1 當(dāng)任務(wù)或目標(biāo)確定后 如何統(tǒng)籌兼顧 合理安排 用最少的資源 如資金 設(shè)備 原標(biāo)材料 人工 時(shí)間等 去完成確定的任務(wù)或目標(biāo) 2 在一定的資源條件限制下 如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益 如產(chǎn)品量最多 利潤(rùn)最大 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 例1 1如圖所示 如何截取x使鐵皮所圍成的容積最大 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 例1 2某企業(yè)計(jì)劃生產(chǎn)甲 乙兩種產(chǎn)品 這些產(chǎn)品分別要在A B C D 四種不同的設(shè)備上加工 按工藝資料規(guī)定 單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示 企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃 使企業(yè)總的利潤(rùn)最大 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 解 設(shè)x1 x2分別為甲 乙兩種產(chǎn)品的產(chǎn)量 則數(shù)學(xué)模型為 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 2 線(xiàn)性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成 決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints 其特征是 1 問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線(xiàn)性函數(shù) 通常是求最大值或最小值 2 問(wèn)題的約束條件是一組多個(gè)決策變量的線(xiàn)性不等式或等式 怎樣辨別一個(gè)模型是線(xiàn)性規(guī)劃模型 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 目標(biāo)函數(shù) 約束條件 3 線(xiàn)性規(guī)劃數(shù)學(xué)模型的一般形式 簡(jiǎn)寫(xiě)為 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 向量形式 其中 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 矩陣形式 其中 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 3 線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 特點(diǎn) 1 目標(biāo)函數(shù)求最大值 有時(shí)求最小值 2 約束條件都為等式方程 且右端常數(shù)項(xiàng)bi都大于或等于零 3 決策變量xj為非負(fù) 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 2 如何化標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)的轉(zhuǎn)換 如果是求極小值即 則可將目標(biāo)函數(shù)乘以 1 可化為求極大值問(wèn)題 也就是 令 可得到上式 即 若存在取值無(wú)約束的變量 可令其中 變量的變換 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 約束方程的轉(zhuǎn)換 由不等式轉(zhuǎn)換為等式 稱(chēng)為松弛變量 稱(chēng)為剩余變量 變量的變換 可令 顯然 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 例1 3將下列線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式 用替換 且 解 因?yàn)閤3無(wú)符號(hào)要求 即x3取正值也可取負(fù)值 標(biāo)準(zhǔn)型中要求變量非負(fù) 所以 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 2 第一個(gè)約束條件是 號(hào) 在 左端加入松馳變量x4 x4 0 化為等式 3 第二個(gè)約束條件是 號(hào) 在 左端減去剩余變量x5 x5 0 4 第3個(gè)約束方程右端常數(shù)項(xiàng)為 5 方程兩邊同乘以 1 將右端常數(shù)項(xiàng)化為正數(shù) 5 目標(biāo)函數(shù)是最小值 為了化為求最大值 令z z 得到maxz z 即當(dāng)z達(dá)到最小值時(shí)z 達(dá)到最大值 反之亦然 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 標(biāo)準(zhǔn)形式如下 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 4 線(xiàn)性規(guī)劃問(wèn)題的解 線(xiàn)性規(guī)劃問(wèn)題 求解線(xiàn)性規(guī)劃問(wèn)題 就是從滿(mǎn)足約束條件 2 3 的方程組中找出一個(gè)解 使目標(biāo)函數(shù) 1 達(dá)到最大值 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 可行解 滿(mǎn)足約束條件 的解為可行解 所有可行解的集合為可行域 最優(yōu)解 使目標(biāo)函數(shù)達(dá)到最大值的可行解 基 設(shè)A為約束條件 的m n階系數(shù)矩陣 m n 其秩為m B是矩陣A中m階滿(mǎn)秩子矩陣 B 0 稱(chēng)B是規(guī)劃問(wèn)題的一個(gè)基 設(shè) 稱(chēng)B中每個(gè)列向量Pj j 12 m 為基向量 與基向量Pj對(duì)應(yīng)的變量xj為基變量 除基變量以外的變量為非基變量 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 基解 某一確定的基B 令非基變量等于零 由約束條件方程 解出基變量 稱(chēng)這組解為基解 在基解中變量取非0值的個(gè)數(shù)不大于方程數(shù)m 基解的總數(shù)不超過(guò)基可行解 滿(mǎn)足變量非負(fù)約束條件的基本解 簡(jiǎn)稱(chēng)基可行解 可行基 對(duì)應(yīng)于基可行解的基稱(chēng)為可行基 線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型 例1 4求線(xiàn)性規(guī)劃問(wèn)題的所有基矩陣 解 約束方程的系數(shù)矩陣為2 5矩陣 r A 2 2階子矩陣有10個(gè) 其中基矩陣只有9個(gè) 即 圖解法 線(xiàn)性規(guī)劃問(wèn)題的求解方法 一般有兩種方法 圖解法單純形法 兩個(gè)變量 直角坐標(biāo)三個(gè)變量 立體坐標(biāo) 適用于任意變量 但必需將一般形式變成標(biāo)準(zhǔn)形式 下面我們分析一下簡(jiǎn)單的情況 只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題 這時(shí)可以通過(guò)圖解的方法來(lái)求解 圖解法具有簡(jiǎn)單 直觀(guān) 便于初學(xué)者窺探線(xiàn)性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn) 圖解法 maxZ 2X1 X2X1 1 9X2 3 8X1 1 9X2 3 8s t X1 1 9X2 10 2X1 1 9X2 3 8X1 X2 0 例1 5用圖解法求解線(xiàn)性規(guī)劃問(wèn)題 圖解法 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 4 2X1 X2 20 2X1 X2 17 2 2X1 X2 11 2X1 X2 Lo 0 2X1 X2 7 6 2 D maxZ minZ 此點(diǎn)是唯一最優(yōu)解 且最優(yōu)目標(biāo)函數(shù)值maxZ 17 2 可行域 maxZ 2X1 X2 圖解法 maxZ 3X1 5 7X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 7 6 2 D L0 0 3X1 5 7X2 maxZ 3 8 4 34 2 3X1 5 7X2 藍(lán)色線(xiàn)段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解 但是最優(yōu)目標(biāo)函數(shù)值maxZ 34 2是唯一的 可行域 圖解法 minZ 5X1 4X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 D L0 0 5X1 4X2 maxZ minZ 8 5X1 4X2 43 5X1 4X2 0 2 可行域 此點(diǎn)是唯一最優(yōu)解 圖解法 2 4 6 x1 x2 2 4 6 無(wú)界解 無(wú)最優(yōu)解 maxZ x1 2x2 例1 6 x1 x2 4 x1 3x2 6 3x1 x2 6 maxZ minZ x1 x2 O 10 20 30 40 10 20 30 40 50 50 無(wú)可行解 即無(wú)最優(yōu)解 maxZ 3x1 4x2 例1 7 圖解法 學(xué)習(xí)要點(diǎn) 1 通過(guò)圖解法了解線(xiàn)性規(guī)劃有幾種解的形式 唯一最優(yōu)解 無(wú)窮多最優(yōu)解 無(wú)界解 無(wú)可行解 2 作圖的關(guān)鍵有三點(diǎn) 1 可行解區(qū)域要畫(huà)正確 2 目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò) 3 目標(biāo)函數(shù)的直線(xiàn)怎樣平行移動(dòng) 單純形法基本原理 凸集 如果集合C中任意兩個(gè)點(diǎn)X1 X2 其連線(xiàn)上的所有點(diǎn)也都是集合C中的點(diǎn) 稱(chēng)C為凸集 單純形法基本原理 定理1 若線(xiàn)性規(guī)劃問(wèn)題存在可行解 則該問(wèn)題的可行域是凸集 定理2 線(xiàn)性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)可行域 凸集 的頂點(diǎn) 定理3 若問(wèn)題存在最優(yōu)解 一定存在一個(gè)基可行解是最優(yōu)解 或在某個(gè)頂點(diǎn)取得 單純形法的計(jì)算步驟 單純形法的思路 找出一個(gè)初始可行解 是否最優(yōu) 轉(zhuǎn)移到另一個(gè)基本可行解 找出更大的目標(biāo)函數(shù)值 最優(yōu)解 是 否 循環(huán) 核心是 變量迭代 結(jié)束 單純形法的計(jì)算步驟 單純形表 單純形法的計(jì)算步驟 例1 8用單純形法求下列線(xiàn)性規(guī)劃的最優(yōu)解 解 1 將問(wèn)題化為標(biāo)準(zhǔn)型 加入松馳變量x3 x4則標(biāo)準(zhǔn)型為 單純形法的計(jì)算步驟 2 求出線(xiàn)性規(guī)劃的初始基可行解 列出初始單純形表 檢驗(yàn)數(shù) 單純形法的計(jì)算步驟 3 進(jìn)行最優(yōu)性檢驗(yàn) 如果表中所有檢驗(yàn)數(shù) 則表中的基可行解就是問(wèn)題的最優(yōu)解 計(jì)算停止 否則繼續(xù)下一步 4 從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解 列出新的單純形表 確定換入基的變量 選擇 對(duì)應(yīng)的變量xj作為換入變量 當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于0時(shí) 一般選擇最大的一個(gè)檢驗(yàn)數(shù) 即 其對(duì)應(yīng)的xk作為換入變量 確定換出變量 根據(jù)下式計(jì)算并選擇 選最小的 對(duì)應(yīng)基變量作為換出變量 單純形法的計(jì)算步驟 用換入變量xk替換基變量中的換出變量 得到一個(gè)新的基 對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解 并相應(yīng)地可以畫(huà)出一個(gè)新的單純形表 5 重復(fù)3 4 步直到計(jì)算結(jié)束為止 單純形法的計(jì)算步驟 換入列 bi ai2 ai2 0 40 10 換出行 將3化為1 5 3 1 18 0 1 3 0 1 3 10 1 1 3 30 30 0 5 3 0 4 3 乘以1 3后得到 1 0 3 5 1 5 18 0 1 1 5 2 5 4 0 0 1 1 單純形法的計(jì)算步驟 例1 9用單純形法求解 解 將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 不難看出x4 x5可作為初始基變量 列單純形表計(jì)算 單純形法的計(jì)算步驟 20 x2 2 1 3 1 5 0 1 20 75 3 0 17 1 3 1 3 0 9 0 2 25 60 x1 1 1 0 17 3 1 3 1 25 0 1 28 9 1 9 2 3 35 3 0 0 98 9 1 9 7 3 單純形法的計(jì)算步驟 學(xué)習(xí)要點(diǎn) 1 線(xiàn)性規(guī)劃解的概念以及3個(gè)基本定理2 熟練掌握單純形法的解題思路及求解步驟 單純形法的進(jìn)一步討論 人工變量法 人工變量法 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣 很容易確定一組基可行解 在實(shí)際問(wèn)題中有些模型并不含有單位矩陣 為了得到一組基向量和初基可行解 在約束條件的等式左端加一組虛擬變量 得到一組基變量 這種人為加的變量稱(chēng)為人工變量 構(gòu)成的可行基稱(chēng)為人工基 用大M法或兩階段法求解 這種用人工變量作橋梁的求解方法稱(chēng)為人工變量法 單純形法的進(jìn)一步討論 人工變量法 例1 10用大M法解下列線(xiàn)性規(guī)劃 解 首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式 系數(shù)矩陣中不存在單位矩陣 無(wú)法建立初始單純形表 單純形法的進(jìn)一步討論 人工變量法 故人為添加兩個(gè)單位向量 得到人工變量單純形法數(shù)學(xué)模型 其中 M是一個(gè)很大的抽象的數(shù) 不需要給出具體的數(shù)值 可以理解為它能大于給定的任何一個(gè)確定數(shù)值 再用前面介紹的單純形法求解該模型 計(jì)算結(jié)果見(jiàn)下表 單純形法的進(jìn)一步討論 人工變量法 單純形法的進(jìn)一步討論 人工變量法 解的判別 1 唯一最優(yōu)解判別 最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零 則線(xiàn)規(guī)劃具有唯一最優(yōu)解 2 多重最優(yōu)解判別 最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零 則線(xiàn)則性規(guī)劃具有多重最優(yōu)解 或無(wú)窮多最優(yōu)解 3 無(wú)界解判別 某個(gè) k 0且aik i 1 2 m 則線(xiàn)性規(guī)劃具有無(wú)界解 4 無(wú)可行解的判斷 當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存在Ri 0時(shí) 則表明原線(xiàn)性規(guī)劃無(wú)可行解 5 退化解的判別 存在某個(gè)基變量為零的基本可行解 單純形法的進(jìn)一步討論 人工變量法 單純性法小結(jié) A 線(xiàn)性規(guī)劃模型的應(yīng)用 一般而言 一個(gè)經(jīng)濟(jì) 管理問(wèn)題凡是滿(mǎn)足以下條件時(shí) 才能建立線(xiàn)性規(guī)劃模型 要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映 且為線(xiàn)性函數(shù)存在著多種方案要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的 這些約束可用線(xiàn)性等式或不等式描述 線(xiàn)性規(guī)劃在管理中的應(yīng)用 人力資源分配問(wèn)題 例1 11某晝夜服務(wù)的公交線(xiàn)路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段開(kāi)始時(shí)上班 并連續(xù)工作8小時(shí) 問(wèn)該公交線(xiàn)路應(yīng)怎樣安排司機(jī)和乘務(wù)人員 即能滿(mǎn)足工作需要 又使配備司機(jī)和乘務(wù)人員的人數(shù)減少 線(xiàn)性規(guī)劃在管理中的應(yīng)用 解 設(shè)xi表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員人數(shù) 此問(wèn)題最優(yōu)解 x1 50 x2 20 x3 50 x4 0 x5 20 x6 10 一共需要司機(jī)和乘務(wù)員150人 線(xiàn)性規(guī)劃在管理中的應(yīng)用 2 生產(chǎn)計(jì)劃問(wèn)題 某廠(chǎng)生產(chǎn) 三種產(chǎn)品 都分別經(jīng)A B兩道工序加工 設(shè)A工序可分別在設(shè)備A1和A2上完成 有B1 B2 B3三種設(shè)備可用于完成B工序 已知產(chǎn)品 可在A B任何一種設(shè)備上加工 產(chǎn)品 可在任何規(guī)格的A設(shè)備上加工 但完成B工序時(shí) 只能在B1設(shè)備上加工 產(chǎn)品 只能在A2與B2設(shè)備上加工 加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)如下表 試安排最優(yōu)生產(chǎn)計(jì)劃 使該廠(chǎng)獲利最大 線(xiàn)性規(guī)劃在管理中的應(yīng)用 線(xiàn)性規(guī)劃在管理中的應(yīng)用 解 設(shè)xijk表示產(chǎn)品i在工序j的設(shè)備k上加工的數(shù)量 約束條件有 線(xiàn)性規(guī)劃在管理中的應(yīng)用 目標(biāo)是利潤(rùn)最大化 即利潤(rùn)的計(jì)算公式如下 帶入數(shù)據(jù)整理得到 線(xiàn)性規(guī)劃在管理中的應(yīng)用 因此該規(guī)劃問(wèn)題的模型為 線(xiàn)性規(guī)劃在管理中的應(yīng)用 3 套裁下料問(wèn)題 例 現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米 需要截取2 5米長(zhǎng)的毛坯100根 長(zhǎng)1 3米的毛坯200根 問(wèn)如何才能既滿(mǎn)足需要 又能使總的用料最少 解 為了找到一個(gè)省料的套裁方案 必須先設(shè)計(jì)出較好的幾個(gè)下料方案 其次要求這些方案的總體能裁下所有各種規(guī)格的圓鋼 以滿(mǎn)足對(duì)各種不同規(guī)格圓鋼的需要并達(dá)到省料的目的 為此可以設(shè)計(jì)出4種下料方案以供套裁用 線(xiàn)性規(guī)劃在管理中的應(yīng)用 設(shè)按方案 下料的原材料根數(shù)分別為xj j 1 2 3 4 可列出下面的數(shù)學(xué)模型 線(xiàn)性規(guī)劃在管理中的應(yīng)用 4 配料問(wèn)題 例 某人每天食用甲 乙兩種食物 如豬肉 雞蛋 其資料如下 問(wèn)兩種食物各食用多少 才能既滿(mǎn)足需要 又使總費(fèi)用最省 線(xiàn)性規(guī)劃在管理中的應(yīng)用 解 設(shè)Xj表示Bj種食物用量 Chapter2對(duì)偶理論 DualityTheory 線(xiàn)性規(guī)劃的對(duì)偶模型對(duì)偶性質(zhì)對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 影子價(jià)格對(duì)偶單純形法 本章主要內(nèi)容 線(xiàn)性規(guī)劃的對(duì)偶模型 設(shè)某工廠(chǎng)生產(chǎn)兩種產(chǎn)品甲和乙 生產(chǎn)中需4種設(shè)備按A B C D順序加工 每件產(chǎn)品加工所需的機(jī)時(shí)數(shù) 每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用機(jī)時(shí)數(shù)列于下表 產(chǎn)品數(shù)據(jù)表 問(wèn) 充分利用設(shè)備機(jī)時(shí) 工廠(chǎng)應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤(rùn) 1 對(duì)偶問(wèn)題的現(xiàn)實(shí)來(lái)源 線(xiàn)性規(guī)劃的對(duì)偶模型 解 設(shè)甲 乙型產(chǎn)品各生產(chǎn)x1及x2件 則數(shù)學(xué)模型為 反過(guò)來(lái)問(wèn) 若廠(chǎng)長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品 決定出租機(jī)器用于接受外加工 只收加工費(fèi) 那么 種機(jī)器的機(jī)時(shí)如何定價(jià)才是最佳決策 線(xiàn)性規(guī)劃的對(duì)偶模型 在市場(chǎng)競(jìng)爭(zhēng)的時(shí)代 廠(chǎng)長(zhǎng)的最佳決策顯然應(yīng)符合兩條 1 不吃虧原則 即機(jī)時(shí)定價(jià)所賺利潤(rùn)不能低于加工甲 乙型產(chǎn)品所獲利潤(rùn) 由此原則 便構(gòu)成了新規(guī)劃的不等式約束條件 2 競(jìng)爭(zhēng)性原則 即在上述不吃虧原則下 盡量降低機(jī)時(shí)總收費(fèi) 以便爭(zhēng)取更多用戶(hù) 設(shè)A B C D設(shè)備的機(jī)時(shí)價(jià)分別為y1 y2 y3 y4 則新的線(xiàn)性規(guī)劃數(shù)學(xué)模型為 線(xiàn)性規(guī)劃的對(duì)偶模型 把同種問(wèn)題的兩種提法所獲得的數(shù)學(xué)模型用表2表示 將會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象 原問(wèn)題與對(duì)偶問(wèn)題對(duì)比表 線(xiàn)性規(guī)劃的對(duì)偶模型 2 原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系 原問(wèn)題 對(duì)偶問(wèn)題 對(duì)偶問(wèn)題 原問(wèn)題 線(xiàn)性規(guī)劃的對(duì)偶模型 1 對(duì)稱(chēng)形式 特點(diǎn) 目標(biāo)函數(shù)求極大值時(shí) 所有約束條件為 號(hào) 變量非負(fù) 目標(biāo)函數(shù)求極小值時(shí) 所有約束條件為 號(hào) 變量非負(fù) 已知P 寫(xiě)出D 線(xiàn)性規(guī)劃的對(duì)偶模型 例2 1寫(xiě)出線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 解 首先將原問(wèn)題變形為對(duì)稱(chēng)形式 線(xiàn)性規(guī)劃的對(duì)偶模型 線(xiàn)性規(guī)劃的對(duì)偶模型 2 非對(duì)稱(chēng)型對(duì)偶問(wèn)題 若給出的線(xiàn)性規(guī)劃不是對(duì)稱(chēng)形式 可以先化成對(duì)稱(chēng)形式再寫(xiě)對(duì)偶問(wèn)題 也可直接按教材表2 2中的對(duì)應(yīng)關(guān)系寫(xiě)出非對(duì)稱(chēng)形式的對(duì)偶問(wèn)題 線(xiàn)性規(guī)劃的對(duì)偶模型 線(xiàn)性規(guī)劃的對(duì)偶模型 例2 2寫(xiě)出下列線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題 解 原問(wèn)題的對(duì)偶問(wèn)題為 對(duì)偶性質(zhì) 例2 3分別求解下列2個(gè)互為對(duì)偶關(guān)系的線(xiàn)性規(guī)劃問(wèn)題 分別用單純形法求解上述2個(gè)規(guī)劃問(wèn)題 得到最終單純形表如下表 對(duì)偶性質(zhì) 原問(wèn)題最優(yōu)表 對(duì)偶問(wèn)題最優(yōu)表 對(duì)偶性質(zhì) 原問(wèn)題與其對(duì)偶問(wèn)題的變量與解的對(duì)應(yīng)關(guān)系 在單純形表中 原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)原問(wèn)題的變量 對(duì)偶性質(zhì) 性質(zhì)1對(duì)稱(chēng)性定理 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題 對(duì)偶性質(zhì) 性質(zhì)2弱對(duì)偶原理 弱對(duì)偶性 設(shè)和分別是問(wèn)題 P 和 D 的可行解 則必有 推論1 原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下屆 反之 對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界 推論2 在一對(duì)對(duì)偶問(wèn)題 P 和 D 中 若其中一個(gè)問(wèn)題可行但目標(biāo)函數(shù)無(wú)界 則另一個(gè)問(wèn)題無(wú)可行解 反之不成立 這也是對(duì)偶問(wèn)題的無(wú)界性 對(duì)偶性質(zhì) 推論3 在一對(duì)對(duì)偶問(wèn)題 P 和 D 中 若一個(gè)可行 如P 而另一個(gè)不可行 如D 則該可行的問(wèn)題目標(biāo)函數(shù)值無(wú)界 性質(zhì)3最優(yōu)性定理 如果是原問(wèn)題的可行解 是其對(duì)偶問(wèn)題的可行解 并且 則是原問(wèn)題的最優(yōu)解 是其對(duì)偶問(wèn)題的最優(yōu)解 對(duì)偶性質(zhì) 性質(zhì)4強(qiáng)對(duì)偶性 若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解 則兩者均具有最優(yōu)解 且它們最優(yōu)解的目標(biāo)函數(shù)值相等 還可推出另一結(jié)論 若 LP 與 DP 都有可行解 則兩者都有最優(yōu)解 若一個(gè)問(wèn)題無(wú)最優(yōu)解 則另一問(wèn)題也無(wú)最優(yōu)解 性質(zhì)5互補(bǔ)松弛性 設(shè)X0和Y0分別是P問(wèn)題和D問(wèn)題的可行解 則它們分別是最優(yōu)解的充要條件是 其中 Xs Ys為松弛變量 對(duì)偶性質(zhì) 性質(zhì)5的應(yīng)用 該性質(zhì)給出了已知一個(gè)問(wèn)題最優(yōu)解求另一個(gè)問(wèn)題最優(yōu)解的方法 即已知Y 求X 或已知X 求Y 互補(bǔ)松弛條件 由于變量都非負(fù) 要使求和式等于零 則必定每一分量為零 因而有下列關(guān)系 若Y 0 則Xs必為0 若X 0 則Ys必為0利用上述關(guān)系 建立對(duì)偶問(wèn)題 或原問(wèn)題 的約束線(xiàn)性方程組 方程組的解即為最優(yōu)解 對(duì)偶性質(zhì) 例2 4已知線(xiàn)性規(guī)劃 的最優(yōu)解是X 6 2 0 T 求其對(duì)偶問(wèn)題的最優(yōu)解Y 解 寫(xiě)出原問(wèn)題的對(duì)偶問(wèn)題 即 標(biāo)準(zhǔn)化 對(duì)偶性質(zhì) 設(shè)對(duì)偶問(wèn)題最優(yōu)解為Y y1 y2 由互補(bǔ)松弛性定理可知 X 和Y 滿(mǎn)足 即 因?yàn)閄1 0 X2 0 所以對(duì)偶問(wèn)題的第一 二個(gè)約束的松弛變量等于零 即y3 0 y4 0 帶入方程中 解此線(xiàn)性方程組得y1 1 y2 1 從而對(duì)偶問(wèn)題的最優(yōu)解為 Y 1 1 最優(yōu)值w 26 對(duì)偶性質(zhì) 例2 5已知線(xiàn)性規(guī)劃 的對(duì)偶問(wèn)題的最優(yōu)解為Y 0 2 求原問(wèn)題的最優(yōu)解 解 對(duì)偶問(wèn)題是 標(biāo)準(zhǔn)化 對(duì)偶性質(zhì) 設(shè)對(duì)偶問(wèn)題最優(yōu)解為X x1 x2 x3 T 由互補(bǔ)松弛性定理可知 X 和Y 滿(mǎn)足 將Y 帶入由方程可知 y3 y5 0 y4 1 y2 2 0 x5 0又 y4 1 0 x2 0 將x2 x5分別帶入原問(wèn)題約束方程中 得 解方程組得 x1 5 x3 1 所以原問(wèn)題的最優(yōu)解為 X 5 0 1 最優(yōu)值z(mì) 12 對(duì)偶性質(zhì) 原問(wèn)題與對(duì)偶問(wèn)題解的對(duì)應(yīng)關(guān)系小結(jié) 思考題 判斷下列結(jié)論是否正確 如果不正確 應(yīng)該怎樣改正 1 任何線(xiàn)性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線(xiàn)性規(guī)劃 2 原問(wèn)題第i個(gè)約束是 約束 則對(duì)偶變量yi 0 3 互為對(duì)偶問(wèn)題 或者同時(shí)都有最優(yōu)解 或者同時(shí)都無(wú)最優(yōu)解 4 對(duì)偶問(wèn)題有可行解 則原問(wèn)題也有可行解 5 原問(wèn)題有多重解 對(duì)偶問(wèn)題也有多重解 6 對(duì)偶問(wèn)題有可行解 原問(wèn)題無(wú)可行解 則對(duì)偶問(wèn)題具有無(wú)界解 7 原問(wèn)題無(wú)最優(yōu)解 則對(duì)偶問(wèn)題無(wú)可行解 8 對(duì)偶問(wèn)題不可行 原問(wèn)題可能無(wú)界解 9 原問(wèn)題與對(duì)偶問(wèn)題都可行 則都有最優(yōu)解 10 原問(wèn)題具有無(wú)界解 則對(duì)偶問(wèn)題不可行 11 對(duì)偶問(wèn)題具有無(wú)界解 則原問(wèn)題無(wú)最優(yōu)解 12 若X Y 是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解 則X Y 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 影子價(jià)格 1 影子價(jià)格的數(shù)學(xué)分析 定義 在一對(duì)P和D中 若P的某個(gè)約束條件的右端項(xiàng)常數(shù)bi 第i種資源的擁有量 增加一個(gè)單位時(shí) 所引起目標(biāo)函數(shù)最優(yōu)值z(mì) 的改變量稱(chēng)為第i種資源的影子價(jià)格 其值等于D問(wèn)題中對(duì)偶變量yi 由對(duì)偶問(wèn)題得基本性質(zhì)可得 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 影子價(jià)格 2 影子價(jià)格的經(jīng)濟(jì)意義1 影子價(jià)格是一種邊際價(jià)格在其它條件不變的情況下 單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化 即對(duì)偶變量yi就是第i種資源的影子價(jià)格 即 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 影子價(jià)格 2 影子價(jià)格是一種機(jī)會(huì)成本影子價(jià)格是在資源最優(yōu)利用條件下對(duì)單位資源的估價(jià) 這種估價(jià)不是資源實(shí)際的市場(chǎng)價(jià)格 因此 從另一個(gè)角度說(shuō) 它是一種機(jī)會(huì)成本 若第i種資源的單位市場(chǎng)價(jià)格為mi 則有當(dāng)yi mi時(shí) 企業(yè)愿意購(gòu)進(jìn)這種資源 單位純利為yi mi 則有利可圖 如果yi mi 則企業(yè)有償轉(zhuǎn)讓這種資源 可獲單位純利mi yi 否則 企業(yè)無(wú)利可圖 甚至虧損 結(jié)論 若yi mi則購(gòu)進(jìn)資源i 可獲單位純利yi mi若yi mi則轉(zhuǎn)讓資源i 可獲單位純利mi yi 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 影子價(jià)格 3 影子價(jià)格在資源利用中的應(yīng)用根據(jù)對(duì)偶理論的互補(bǔ)松弛性定理 Y Xs 0 YsX 0表明生產(chǎn)過(guò)程中如果某種資源bi未得到充分利用時(shí) 該種資源的影子價(jià)格為0 若當(dāng)資源資源的影子價(jià)格不為0時(shí) 表明該種資源在生產(chǎn)中已耗費(fèi)完 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 影子價(jià)格 4 影子價(jià)格對(duì)單純形表計(jì)算的解釋 單純形表中的檢驗(yàn)數(shù) 其中cj表示第j種產(chǎn)品的價(jià)格 表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和 即產(chǎn)品的隱含成本 當(dāng)產(chǎn)值大于隱含成本時(shí) 即 表明生產(chǎn)該項(xiàng)產(chǎn)品有利 可在計(jì)劃中安排 否則 用這些資源生產(chǎn)別的產(chǎn)品更有利 不在生產(chǎn)中安排該產(chǎn)品 對(duì)偶單純形法 對(duì)偶單純形法是求解線(xiàn)性規(guī)劃的另一個(gè)基本方法 它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)計(jì)出來(lái)的 因此稱(chēng)為對(duì)偶單純形法 不要簡(jiǎn)單理解為是求解對(duì)偶問(wèn)題的單純形法 對(duì)偶單純形法原理 對(duì)偶單純形法基本思路 找出一個(gè)對(duì)偶問(wèn)題的可行基 保持對(duì)偶問(wèn)題為可行解的條件下 判斷XB是否可行 XB為非負(fù) 若否 通過(guò)變換基解 直到找到原問(wèn)題基可行解 即XB為非負(fù) 這時(shí)原問(wèn)題與對(duì)偶問(wèn)題同時(shí)達(dá)到可行解 由定理4可得最優(yōu)解 對(duì)偶單純形法 找出一個(gè)DP的可行基 LP是否可行 XB 0 保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解 最優(yōu)解 是 否 循環(huán) 結(jié)束 對(duì)偶單純形法 例2 9用對(duì)偶單純形法求解 解 1 將模型轉(zhuǎn)化為求最大化問(wèn)題 約束方程化為等式求出一組基本解 因?yàn)閷?duì)偶問(wèn)題可行 即全部檢驗(yàn)數(shù) 0 求max問(wèn)題 對(duì)偶單純形法 對(duì)偶單純形法 對(duì)偶單純形法 原問(wèn)題的最優(yōu)解為 X 2 2 2 0 0 0 Z 72其對(duì)偶問(wèn)題的最優(yōu)解為 Y 1 3 3 7 3 W 72 對(duì)偶單純形法 對(duì)偶單純形法應(yīng)注意的問(wèn)題 用對(duì)偶單純形法求解線(xiàn)性規(guī)劃是一種求解方法 而不是去求對(duì)偶問(wèn)題的最優(yōu)解 初始表中一定要滿(mǎn)足對(duì)偶問(wèn)題可行 也就是說(shuō)檢驗(yàn)數(shù)滿(mǎn)足最優(yōu)判別準(zhǔn)則 最小比值中的絕對(duì)值是使得比值非負(fù) 在極小化問(wèn)題 j 0 分母aij 0這時(shí)必須取絕對(duì)值 在極大化問(wèn)題中 j 0 分母aij 0 總滿(mǎn)足非負(fù) 這時(shí)絕對(duì)值符號(hào)不起作用 可以去掉 如在本例中將目標(biāo)函數(shù)寫(xiě)成 這里 j 0在求 k時(shí)就可以不帶絕對(duì)值符號(hào) 對(duì)偶單純形法 對(duì)偶單純形法與普通單純形法的換基順序不一樣 普通單純形法是先確定進(jìn)基變量后確定出基變量 對(duì)偶單純形法是先確定出基變量后確定進(jìn)基變量 普通單純形法的最小比值是其目的是保證下一個(gè)原問(wèn)題的基本解可行 對(duì)偶單純形法的最小比值是 其目的是保證下一個(gè)對(duì)偶問(wèn)題的基本解可行 對(duì)偶單純形法在確定出基變量時(shí) 若不遵循規(guī)則 任選一個(gè)小于零的bi對(duì)應(yīng)的基變量出基 不影響計(jì)算結(jié)果 只是迭代次數(shù)可能不一樣 本章小結(jié) 學(xué)習(xí)要點(diǎn) 1 線(xiàn)性規(guī)劃解的概念以及3個(gè)基本定理2 熟練掌握單純形法的解題思路及求解步驟 Chapter3運(yùn)輸規(guī)劃 TransportationProblem 運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型表上作業(yè)法運(yùn)輸問(wèn)題的應(yīng)用 本章主要內(nèi)容 運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型 例3 1某公司從兩個(gè)產(chǎn)地A1 A2將物品運(yùn)往三個(gè)銷(xiāo)地B1 B2 B3 各產(chǎn)地的產(chǎn)量 各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)費(fèi)如下表所示 問(wèn) 應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小 運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型 解 產(chǎn)銷(xiāo)平衡問(wèn)題 總產(chǎn)量 總銷(xiāo)量 500設(shè)xij為從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的運(yùn)輸量 得到下列運(yùn)輸量表 MinC 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型 運(yùn)輸問(wèn)題的一般形式 產(chǎn)銷(xiāo)平衡 A1 A2 Am表示某物資的m個(gè)產(chǎn)地 B1 B2 Bn表示某物質(zhì)的n個(gè)銷(xiāo)地 ai表示產(chǎn)地Ai的產(chǎn)量 bj表示銷(xiāo)地Bj的銷(xiāo)量 cij表示把物資從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的單位運(yùn)價(jià) 設(shè)xij為從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的運(yùn)輸量 得到下列一般運(yùn)輸量問(wèn)題的模型 運(yùn)輸規(guī)劃問(wèn)題的數(shù)學(xué)模型 變化 1 有時(shí)目標(biāo)函數(shù)求最大 如求利潤(rùn)最大或營(yíng)業(yè)額最大等 2 當(dāng)某些運(yùn)輸線(xiàn)路上的能力有限制時(shí) 在模型中直接加入約束條件 等式或不等式約束 3 產(chǎn)銷(xiāo)不平衡時(shí) 可加入假想的產(chǎn)地 銷(xiāo)大于產(chǎn)時(shí) 或銷(xiāo)地 產(chǎn)大于銷(xiāo)時(shí) 定理 設(shè)有m個(gè)產(chǎn)地n個(gè)銷(xiāo)地且產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題 則基變量數(shù)為m n 1 表上作業(yè)法 表上作業(yè)法是一種求解運(yùn)輸問(wèn)題的特殊方法 其實(shí)質(zhì)是單純形法 表上作業(yè)法 例3 2某運(yùn)輸資料如下表所示 問(wèn) 應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小 表上作業(yè)法 解 第1步求初始方案 方法1 最小元素法基本思想是就近供應(yīng) 即從運(yùn)價(jià)最小的地方開(kāi)始供應(yīng) 調(diào)運(yùn) 然后次小 直到最后供完為止 3 11 3 10 1 9 2 7 4 10 5 8 3 4 1 6 3 3 表上作業(yè)法 總的運(yùn)輸費(fèi) 3 1 6 4 4 3 1 2 3 10 3 5 86元 元素差額法對(duì)最小元素法進(jìn)行了改進(jìn) 考慮到產(chǎn)地到銷(xiāo)地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額 如果差額很大 就選最小運(yùn)價(jià)先調(diào)運(yùn) 否則會(huì)增加總運(yùn)費(fèi) 例如下面兩種運(yùn)輸方案 15 5 10 總運(yùn)費(fèi)是z 10 8 5 2 15 1 105 最小元素法 表上作業(yè)法 5 15 10 總運(yùn)費(fèi)z 10 5 15 2 5 1 85 后一種方案考慮到C11與C21之間的差額是8 2 6 如果不先調(diào)運(yùn)x21 到后來(lái)就有可能x11 0 這樣會(huì)使總運(yùn)費(fèi)增加較大 從而先調(diào)運(yùn)x21 再是x22 其次是x12 用元素差額法求得的基本可行解更接近最優(yōu)解 所以也稱(chēng)為近似方案 表上作業(yè)法 方法2 Vogel法 1 從運(yùn)價(jià)表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額 并填入該表的最右列和最下行 3 11 3 10 1 9 2 7 4 10 5 8 表上作業(yè)法 2 再?gòu)牟钪底畲蟮男谢蛄兄姓页鲎钚∵\(yùn)價(jià)確定供需關(guān)系和供需數(shù)量 當(dāng)產(chǎn)地或銷(xiāo)地中有一方數(shù)量供應(yīng)完畢或得到滿(mǎn)足時(shí) 劃去運(yùn)價(jià)表中對(duì)應(yīng)的行或列 重復(fù)1 和2 直到找出初始解為至 3 11 3 10 1 9 2 7 4 10 5 8 5 表上作業(yè)法 7 1 1 3 5 2 1 5 表上作業(yè)法 7 1 3 5 2 7 5 3 表上作業(yè)法 1 1 3 5 1 5 3 6 3 1 2 該方案的總運(yùn)費(fèi) 1 3 4 6 3 5 2 10 1 8 3 5 85元 表上作業(yè)法 第2步最優(yōu)解的判別 檢驗(yàn)數(shù)的求法 求出一組基可行解后 判斷是否為最優(yōu)解 仍然是用檢驗(yàn)數(shù)來(lái)判斷 記xij的檢驗(yàn)數(shù)為 ij由第一章知 求最小值的運(yùn)輸問(wèn)題的最優(yōu)判別準(zhǔn)則是 所有非基變量的檢驗(yàn)數(shù)都非負(fù) 則運(yùn)輸方案最優(yōu) 求檢驗(yàn)數(shù)的方法有兩種 閉回路法位勢(shì)法 表上作業(yè)法 閉回路的概念 為一個(gè)閉回路 集合中的變量稱(chēng)為回路的頂點(diǎn) 相鄰兩個(gè)變量的連線(xiàn)為閉回路的邊 如下表 表上作業(yè)法 例下表中閉回路的變量集合是 x11 x12 x42 x43 x23 x25 x35 x31 共有8個(gè)頂點(diǎn) 這8個(gè)頂點(diǎn)間用水平或垂直線(xiàn)段連接起來(lái) 組成一條封閉的回路 一條回路中的頂點(diǎn)數(shù)一定是偶數(shù) 回路遇到頂點(diǎn)必須轉(zhuǎn)90度與另一頂點(diǎn)連接 表3 3中的變量x32及x33不是閉回路的頂點(diǎn) 只是連線(xiàn)的交點(diǎn) 表上作業(yè)法 閉回路 例如變量組不能構(gòu)成一條閉回路 但A中包含有閉回路 變量組變量數(shù)是奇數(shù) 顯然不是閉回路 也不含有閉回路 表上作業(yè)法 用位勢(shì)法對(duì)初始方案進(jìn)行最優(yōu)性檢驗(yàn) 1 由 ij Cij Ui Vj 計(jì)算位勢(shì)Ui Vj 因?qū)兞慷杂?ij 0 即Cij Ui Vj 0 令U1 0 2 再由 ij Cij Ui Vj 計(jì)算非基變量的檢驗(yàn)數(shù) ij 3 11 3 10 1 9 2 7 4 10 5 8 4 3 6 3 1 3 0 1 5 3 10 2 9 1 2 1 1 10 12 當(dāng)存在非基變量的檢驗(yàn)數(shù) kl 0 說(shuō)明現(xiàn)行方案為最優(yōu)方案 否則目標(biāo)成本還可以進(jìn)一步減小 表上作業(yè)法 當(dāng)存在非基變量的檢驗(yàn)數(shù) kl 0且 kl min ij 時(shí) 令Xkl進(jìn)基 從表中知可選X24進(jìn)基 第3步確定換入基的變量 第4步確定換出基的變量 以進(jìn)基變量xik為起點(diǎn)的閉回路中 標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量 對(duì)應(yīng)的基變量為出基變量 并打上 以示換出作為非基變量 表上作業(yè)法 3 11 3 10 1 9 2 7 4 10 5 8 4 3 6 3 1 3 調(diào)整步驟為 在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量 標(biāo)有負(fù)號(hào)的變量減去調(diào)整量 其余變量不變 得到一組新的基可行解 然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn) 1 2 5 表上作業(yè)法 當(dāng)所有非基變量的檢驗(yàn)數(shù)均非負(fù)時(shí) 則當(dāng)前調(diào)運(yùn)方案即為最優(yōu)方案 如表此時(shí)最小總運(yùn)費(fèi) Z 1 3 4 6 3 5 2 10 1 8 3 5 85元 3 11 3 10 1 9 2 7 4 10 5 8 5 3 6 3 1 2 0 2 5 3 10 3 9 0 2 2 1 12 9 表上作業(yè)法 表上作業(yè)法的計(jì)算步驟 表上作業(yè)法 表上作業(yè)法計(jì)算中的問(wèn)題 1 若運(yùn)輸問(wèn)題的某一基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為負(fù) 在繼續(xù)迭代時(shí) 取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善 但通常取 ij 0中最小者對(duì)應(yīng)的變量為換入變量 2 無(wú)窮多最優(yōu)解產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解 如果非基變量的 ij 0 則該問(wèn)題有無(wú)窮多最優(yōu)解 表上作業(yè)法 退化解 表格中一般要有 m n 1 個(gè)數(shù)字格 但有時(shí)在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列 這時(shí)需要補(bǔ)一個(gè)0 以保證有 m n 1 個(gè)數(shù)字格作為基變量 一般可在劃去的行和列的任意空格處加一個(gè)0即可 利用進(jìn)基變量的閉回路對(duì)解進(jìn)行調(diào)整時(shí) 標(biāo)有負(fù)號(hào)的最小運(yùn)量 超過(guò)2個(gè)最小值 作為調(diào)整量 選擇任意一個(gè)最小運(yùn)量對(duì)應(yīng)的基變量作為出基變量 并打上 以示作為非基變量 表上作業(yè)法 12 4 11 4 8 3 10 2 9 5 11 6 0 2 9 2 1 12 8 12 4 2 8 14 如下例中 11檢驗(yàn)數(shù)是0 經(jīng)過(guò)調(diào)整 可得到另一個(gè)最優(yōu)解 表上作業(yè)法 11 4 4 3 1 3 7 7 8 2 10 6 3 4 1 6 0 6 在x12 x22 x33 x34中任選一個(gè)變量作為基變量 例如選x34 例 用最小元素法求初始可行解 運(yùn)輸問(wèn)題的應(yīng)用 求極大值問(wèn)題目標(biāo)函數(shù)求利潤(rùn)最大或營(yíng)業(yè)額最大等問(wèn)題 運(yùn)輸問(wèn)題的應(yīng)用 求解方法 將極大化問(wèn)題轉(zhuǎn)化為極小化問(wèn)題 設(shè)極大化問(wèn)題的運(yùn)價(jià)表為C 用一個(gè)較大的數(shù)M M max cij 去減每一個(gè)cij得到矩陣C 其中C M cij 0 將C 作為極小化問(wèn)題的運(yùn)價(jià)表 用表上用業(yè)法求出最優(yōu)解 運(yùn)輸問(wèn)題的應(yīng)用 例3 3下列矩陣C是Ai I 1 2 3 到Bj的噸公里利潤(rùn) 運(yùn)輸部門(mén)如何安排運(yùn)輸方案使總利潤(rùn)最大 運(yùn)輸問(wèn)題的應(yīng)用 得到新的最小化運(yùn)輸問(wèn)題 用表上作業(yè)法求解即可 運(yùn)輸問(wèn)題的應(yīng)用 產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題當(dāng)總產(chǎn)量與總銷(xiāo)量不相等時(shí) 稱(chēng)為不平衡運(yùn)輸問(wèn)題 這類(lèi)運(yùn)輸問(wèn)題在實(shí)際中常常碰到 它的求解方法是將不平衡問(wèn)題化為平衡問(wèn)題再按平衡問(wèn)題求解 當(dāng)產(chǎn)大于銷(xiāo)時(shí) 即 數(shù)學(xué)模型為 運(yùn)輸問(wèn)題的應(yīng)用 由于總產(chǎn)量大于總銷(xiāo)量 必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完 必須就地庫(kù)存 即每個(gè)產(chǎn)地設(shè)一個(gè)倉(cāng)庫(kù) 假設(shè)該倉(cāng)庫(kù)為一個(gè)虛擬銷(xiāo)地Bn 1 bn 1作為一個(gè)虛設(shè)銷(xiāo)地Bn 1的銷(xiāo)量 即庫(kù)存量 各產(chǎn)地Ai到Bn 1的運(yùn)價(jià)為零 即Ci n 1 0 i 1 m 則平衡問(wèn)題的數(shù)學(xué)模型為 具體求解時(shí) 只在運(yùn)價(jià)表右端增加一列Bn 1 運(yùn)價(jià)為零 銷(xiāo)量為bn 1即可 運(yùn)輸問(wèn)題的應(yīng)用 當(dāng)銷(xiāo)大于產(chǎn)時(shí) 即 數(shù)學(xué)模型為 由于總銷(xiāo)量大于總產(chǎn)量 故一定有些需求地不完全滿(mǎn)足 這時(shí)虛設(shè)一個(gè)產(chǎn)地Am 1 產(chǎn)量為 運(yùn)輸問(wèn)題的應(yīng)用 銷(xiāo)大于產(chǎn)化為平衡問(wèn)題的數(shù)學(xué)模型為 具體計(jì)算時(shí) 在運(yùn)價(jià)表的下方增加一行Am 1 運(yùn)價(jià)為零 產(chǎn)量為am 1即可 運(yùn)輸問(wèn)題的應(yīng)用 例3 4求下列表中極小化運(yùn)輸問(wèn)題的最優(yōu)解 因?yàn)橛?運(yùn)輸問(wèn)題的應(yīng)用 所以是一個(gè)產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題 表中A2不可達(dá)B1 用一個(gè)很大的正數(shù)M表示運(yùn)價(jià)C21 虛設(shè)一個(gè)銷(xiāo)量為b5 180 160 20 Ci5 0 i 1 2 3 4 表的右邊增添一列 得到新的運(yùn)價(jià)表 運(yùn)輸問(wèn)題的應(yīng)用 下表為計(jì)算結(jié)果 可看出 產(chǎn)地A4還有20個(gè)單位沒(méi)有運(yùn)出 運(yùn)輸問(wèn)題的應(yīng)用 3 生產(chǎn)與儲(chǔ)存問(wèn)題 例3 5某廠(chǎng)按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10 15 25 20臺(tái)同一規(guī)格的柴油機(jī) 已知該廠(chǎng)各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表 如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨 每臺(tái)每積壓一個(gè)季度需儲(chǔ)存 維護(hù)等費(fèi)用0 15萬(wàn)元 試求在完成合同的情況下 使該廠(chǎng)全年生產(chǎn)總費(fèi)用為最小的決策方案 運(yùn)輸問(wèn)題的應(yīng)用 解 設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目 那么應(yīng)滿(mǎn)足 交貨 x11 10生產(chǎn) x11 x12 x13 x14 25x12 x22 15x22 x23 x24 35x13 x23 x33 25x33 x34 30 x14 x24 x34 x44 20 x44 10 把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠(chǎng)的產(chǎn)量 把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量 設(shè)cij是第i季度生產(chǎn)的第j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本 應(yīng)該等于該季度單位成本加上儲(chǔ)存 維護(hù)等費(fèi)用 可構(gòu)造下列產(chǎn)銷(xiāo)平衡問(wèn)題 運(yùn)輸問(wèn)題的應(yīng)用 由于產(chǎn)大于銷(xiāo) 加上一個(gè)虛擬的銷(xiāo)地D 化為平衡問(wèn)題 即可應(yīng)用表上作業(yè)法求解 運(yùn)輸問(wèn)題的應(yīng)用 該問(wèn)題的數(shù)學(xué)模型 Minf 10 8x11 10 95x12 11 1x13 11 25x14 11 1x22 11 25x23 11 4x24 11 0 x33 11 15x34 11 3x44 運(yùn)輸問(wèn)題的應(yīng)用 最優(yōu)生產(chǎn)決策如下表 最小費(fèi)用z 773萬(wàn)元 Chapter4整數(shù)規(guī)劃 IntegerProgramming 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用分支定界法分配問(wèn)題與匈牙利法 本章主要內(nèi)容 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃 簡(jiǎn)稱(chēng) IP 要求一部分或全部決策變量取整數(shù)值的規(guī)劃問(wèn)題稱(chēng)為整數(shù)規(guī)劃 不考慮整數(shù)條件 由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問(wèn)題稱(chēng)為該整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題 若該松弛問(wèn)題是一個(gè)線(xiàn)性規(guī)劃 則稱(chēng)該整數(shù)規(guī)劃為整數(shù)線(xiàn)性規(guī)劃 整數(shù)線(xiàn)性規(guī)劃數(shù)學(xué)模型的一般形式 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)線(xiàn)性規(guī)劃問(wèn)題的種類(lèi) 純整數(shù)線(xiàn)性規(guī)劃 指全部決策變量都必須取整數(shù)值的整數(shù)線(xiàn)性規(guī)劃 混合整數(shù)線(xiàn)性規(guī)劃 決策變量中有一部分必須取整數(shù)值 另一部分可以不取整數(shù)值的整數(shù)線(xiàn)性規(guī)劃 0 1型整數(shù)線(xiàn)性規(guī)劃 決策變量只能取值0或1的整數(shù)線(xiàn)性規(guī)劃 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃的典型例子 例4 1工廠(chǎng)A1和A2生產(chǎn)某種物資 由于該種物資供不應(yīng)求 故需要再建一家工廠(chǎng) 相應(yīng)的建廠(chǎng)方案有A3和A4兩個(gè) 這種物資的需求地有B1 B2 B3 B4四個(gè) 各工廠(chǎng)年生產(chǎn)能力 各地年需求量 各廠(chǎng)至各需求地的單位物資運(yùn)費(fèi)cij 見(jiàn)下表 工廠(chǎng)A3或A4開(kāi)工后 每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬(wàn)或1500萬(wàn)元 現(xiàn)要決定應(yīng)該建設(shè)工廠(chǎng)A3還是A4 才能使今后每年的總費(fèi)用最少 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 解 這是一個(gè)物資運(yùn)輸問(wèn)題 特點(diǎn)是事先不能確定應(yīng)該建A3還是A4中哪一個(gè) 因而不知道新廠(chǎng)投產(chǎn)后的實(shí)際生產(chǎn)物資 為此 引入0 1變量 再設(shè)xij為由Ai運(yùn)往Bj的物資數(shù)量 單位為千噸 z表示總費(fèi)用 單位萬(wàn)元 則該規(guī)劃問(wèn)題的數(shù)學(xué)模型可以表示為 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 混合整數(shù)規(guī)劃問(wèn)題 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 例4 2現(xiàn)有資金總額為B 可供選擇的投資項(xiàng)目有n個(gè) 項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj j 1 2 n 此外由于種種原因 有三個(gè)附加條件 若選擇項(xiàng)目1 就必須同時(shí)選擇項(xiàng)目2 反之不一定項(xiàng)目3和4中至少選擇一個(gè) 項(xiàng)目5 6 7中恰好選擇2個(gè) 應(yīng)該怎樣選擇投資項(xiàng)目 才能使總預(yù)期收益最大 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 解 對(duì)每個(gè)投資項(xiàng)目都有被選擇和不被選擇兩種可能 因此分別用0和1表示 令xj表示第j個(gè)項(xiàng)目的決策選擇 記為 投資問(wèn)題可以表示為 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 例4 3指派問(wèn)題或分配問(wèn)題 人事部門(mén)欲安排四人到四個(gè)不同崗位工作 每個(gè)崗位一個(gè)人 經(jīng)考核四人在不同崗位的成績(jī) 百分制 如表所示 如何安排他們的工作使總成績(jī)最好 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 設(shè) 數(shù)學(xué)模型如下 要求每人做一項(xiàng)工作 約束條件為 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 每項(xiàng)工作只能安排一人 約束條件為 變量約束 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃問(wèn)題解的特征 整數(shù)規(guī)劃問(wèn)題的可行解集合是它松弛問(wèn)題可行解集合的一個(gè)子集 任意兩個(gè)可行解的凸組合不一定滿(mǎn)足整數(shù)約束條件 因而不一定仍為可行解 整數(shù)規(guī)劃問(wèn)題的可行解一定是它的松弛問(wèn)題的可行解 反之不一定 但其最優(yōu)解的目標(biāo)函數(shù)值不會(huì)優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 例4 3設(shè)整數(shù)規(guī)劃問(wèn)題如下 首先不考慮整數(shù)約束 得到線(xiàn)性規(guī)劃問(wèn)題 一般稱(chēng)為松弛問(wèn)題 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 用圖解法求出最優(yōu)解為 x1 3 2 x2 10 3 且有Z 29 6 現(xiàn)求整數(shù)解 最優(yōu)解 如用舍入取整法可得到4個(gè)點(diǎn)即 1 3 2 3 1 4 2 4 顯然 它們都不可能是整數(shù)規(guī)劃的最優(yōu)解 x1 x2 3 3 3 2 10 3 按整數(shù)規(guī)劃約束條件 其可行解肯定在線(xiàn)性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn) 故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集 如右圖所示 其中 2 2 3 1 點(diǎn)的目標(biāo)函數(shù)值最大 即為Z 4 整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用 整數(shù)規(guī)劃問(wèn)題的求解方法 分支定界法和割平面法匈牙利法 指派問(wèn)題 分支定界法 1 求整數(shù)規(guī)劃的松弛問(wèn)題最優(yōu)解 若松弛問(wèn)題的最優(yōu)解滿(mǎn)足整數(shù)要求 得到整數(shù)規(guī)劃的最優(yōu)解 否則轉(zhuǎn)下一步 2 分支與定界 任意選一個(gè)非整數(shù)解的變量xi 在松弛問(wèn)題中加上約束 xi xi 和xi xi 1組成兩個(gè)新的松弛問(wèn)題 稱(chēng)為分枝 新的松弛問(wèn)題具有特征 當(dāng)原問(wèn)題是求最大值時(shí) 目標(biāo)值是分枝問(wèn)題的上界 當(dāng)原問(wèn)題是求最小值時(shí) 目標(biāo)值是分枝問(wèn)題的下界 檢查所有分枝的解及目標(biāo)函數(shù)值 若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于 max 等于其它分枝的目標(biāo)值 則將其它分枝剪去不再計(jì)算 若還存在非整數(shù)解并且目標(biāo)值大于 max 整數(shù)解的目標(biāo)值 需要繼續(xù)分枝 再檢查 直到得到最優(yōu)解 分支定界法的解題步驟 分支定界法 例4 4用分枝定界法求解整數(shù)規(guī)劃問(wèn)題 解 首先去掉整數(shù)約束 變成一般線(xiàn)性規(guī)劃問(wèn)題 原整數(shù)規(guī)劃問(wèn)題的松馳問(wèn)題 LP IP 分支定界法 用圖解法求松弛問(wèn)題的最優(yōu)解 如圖所示 x1 x2 3 18 11 40 11 2 1 1 2 3 x1 18 11 x2 40 11Z 218 11 19 8 即Z也是IP最小值的下限 對(duì)于x1 18 11 1 64 取值x1 1 x1 2對(duì)于x2 40 11 3 64 取值x2 3 x2 4先將 LP 劃分為 LP1 和 LP2 取x1 1 x1 2 分支定界法 分支 分別求出 LP1 和 LP2 的最優(yōu)解 分支定界法 先求LP1 如圖所示 此時(shí)在B點(diǎn)取得最優(yōu)解 x1 1 x2 3 Z 1 16找到整數(shù)解 問(wèn)題已探明 此枝停止計(jì)算 x1 x2 3 3 18 11 40 11 1 1 B A C 同理求LP2 如圖所示 在C點(diǎn)取得最優(yōu)解 即 x1 2 x2 10 3 Z 2 56 3 18 7 Z 2 Z 1 16 原問(wèn)題有比 16更小的最優(yōu)解 但x2不是整數(shù) 故繼續(xù)分支 分支定界法 在IP2中分別再加入條件 x2 3 x2 4得下式兩支 分別求出LP21和LP22的最優(yōu)解 分支定界法 x1 x2 3 3 18 11 40 11 1 1 B A C D 先求LP21 如圖所示 此時(shí)D在點(diǎn)取得最優(yōu)解 即x1 12 5 2 4 x2 3 Z 21 87 5 17 4 Z 1 16但x1 12 5不是整數(shù) 可繼續(xù)分枝 即3 x1 2 求LP22 如圖所示 無(wú)可行解 故不再分枝 分支定界法 在 LP21 的基礎(chǔ)上繼續(xù)分枝 加入條件3 x1 2有下式 分別求出 LP211 和 LP212 的最優(yōu)解 分支定界法 x1 x2 3 3 18 11 40 11 1 1 B A C D E F 先求 LP211 如圖所示 此時(shí)在E點(diǎn)取得最優(yōu)解 即x1 2 x2 3 Z 211 17找到整數(shù)解 問(wèn)題已探明 此枝停止計(jì)算 求 LP212 如圖所示 此時(shí)F在點(diǎn)取得最優(yōu)解 即x1 3 x2 2 5 Z 212 31 2 15 5 Z 211 如對(duì)LP212繼續(xù)分解 其最小值也不會(huì)低于 15 5 問(wèn)題探明 剪枝 分支定界法 原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為 x1 2 x2 3 Z 17以上的求解過(guò)程可以用一個(gè)樹(shù)形圖表示如右 LP1x1 1 x2 3Z 1 16 LPx1 18 11 x2 40 11Z 0 19 8 LP2x1 2 x2 10 3Z 2 18 5 LP21x1 12 5 x2 3Z 21 17 4 LP22無(wú)可行解 LP211x1 2 x2 3Z 211 17 LP212x1 3 x2 5 2Z 212 15 5 x1 1 x1 2 x2 3 x2 4 x1 2 x1 3 分支定界法 例4 5用分枝定界法求解 解 先求對(duì)應(yīng)的松弛問(wèn)題 記為L(zhǎng)P0 用圖解法得到最優(yōu)解X 3 57 7 14 Z0 35 7 如下圖所示 分支定界法 10 10 松弛問(wèn)題LP0的最優(yōu)解X 3 57 7 14 Z0 35 7 x1 x2 o A B C 分支定界法 10 x2 o A B C LP1 LP2 3 4 LP1 X 3 7 6 Z1 34 8 LP2 X 4 6 5 Z2 35 5 分支定界法 10 x1 x2 o A B C LP1 LP21 3 4 LP21 X 4 33 6 Z21 35 33 6 分支定界法 10 x1 x2 o A C LP1 3 4 6 LP211 X 4 6 Z211 34 LP212 X 5 5