運籌學(xué)所有內(nèi)容.ppt

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