運籌學(xué)第17講復(fù)習(xí)分配問題與匈牙利法.pptVIP

第四章整數(shù)規(guī)劃與分配問題 整數(shù)規(guī)劃的特點及作用分枝定界法割平面法分配問題與匈牙利法應(yīng)用舉例 IntegerProgramming 簡稱IP 有純整數(shù)規(guī)劃 混合整數(shù)規(guī)劃與0 1整數(shù)規(guī)劃等類型 我們只研究線性整數(shù)規(guī)劃 整數(shù)規(guī)劃是研究決策變量只能取正整數(shù)的一類規(guī)劃問題 整數(shù)規(guī)劃的特點 1 可行解域為離散點集 2 不能用舍入取整法 3 目標(biāo)函數(shù)值的最優(yōu)值不會優(yōu)于其松弛問題的最優(yōu)值 整數(shù)規(guī)劃的特點 整數(shù)規(guī)劃的求解 分枝定界法割平面法 共同點 通過增加附加約束 使整數(shù)最優(yōu)解最終成為線性規(guī)劃可行域的一個頂點 從而使問題可利用單純形法求出這個整數(shù)最優(yōu)解 不同點 附加約束條件的選取原則及方法不同 實質(zhì) 在保留原問題全部整數(shù)可行解的前提下 將原問題分枝為若干容易求解的子問題 并利用子問題的整數(shù)解的目標(biāo)值來判定分枝的界限 分枝定界法 解 設(shè)應(yīng)購進(jìn)甲 乙機(jī)床臺數(shù)分別為x1和x2 數(shù)學(xué)模型為 1 去掉變量為整數(shù)約束 可用圖解法求得最優(yōu)解 x1 3 25非整數(shù) 進(jìn)行分枝 3 25 2 5 T X 0 x1 x2 T 3 25 2 5 TZ 0 14 75 例 某廠擬購進(jìn)甲 乙兩類機(jī)床生產(chǎn)新產(chǎn)品 已知兩類機(jī)床進(jìn)價分別為2萬元和3萬元 安裝占地面積分別為4m2和2m2 投產(chǎn)后的收益分別為3百元 日和2百元 日 廠方僅有資金14萬元 安裝面積18m2 為使收益最大 廠方應(yīng)購進(jìn)甲 乙機(jī)床各多少臺 x1 3 25非整數(shù) 進(jìn)行分枝 2 得兩個子問題的數(shù)學(xué)模型 子問題 1 子問題 2 分別用圖解法求得最優(yōu)解X 1 3 2 67 T Z 1 14 33X 2 4 1 T Z 2 14 Z 1 Z 2 14 子問題2停止分枝 其整數(shù)解作為界 子問題1對x2 2 67進(jìn)行分枝 子問題 3 子問題 4 子問題 1 Z 1 Z 2 14 子問題2停止分枝 其整數(shù)解作為界 子問題1對x2 2 67進(jìn)行分枝 分別用圖解法求得最優(yōu)解X 3 3 2 T Z 3 13X 4 2 5 3 T Z 4 13 5 Z 3 Z 2 Z 4 Z 2 子問題 3 子問題 4 子問題 1 Z 1 Z 2 14 子問題2停止分枝 其整數(shù)解作為界 子問題1對x2 2 67進(jìn)行分枝 分別用圖解法求得最優(yōu)解X 3 3 2 T Z 3 13X 4 2 5 3 T Z 4 13 5 Z 3 Z 2 Z 4 Z 2 最優(yōu)解 X X 2 4 1 T最優(yōu)值 Z 14 添加x2 3 添加x1 3 添加x2 2 添加x1 4 分枝問題解可能出現(xiàn)的情況表 情況2 4 5找到最優(yōu)解情況3在縮減的域上繼續(xù)分枝定界法情況6中問題1的整數(shù)解作為界被保留 用于以后與問題2的后續(xù)分枝所得到的解進(jìn)行比較 結(jié)論如情況4或5 割平面法 割平面法的基礎(chǔ)仍然是用解線性規(guī)劃的方法去解整數(shù)規(guī)劃問題 首先不考慮變量為整數(shù)這一條件 但增加線性約束條件 Gomory約束 稱為割平面 使得原可行解域中切掉一部分 這部分只包含非整數(shù)解 但沒切割掉任何整數(shù)可行解 切除的結(jié)果使整數(shù)解可能成為頂點 分枝定解法是對原問題可行解域進(jìn)行了切割 切割方法是對取非整數(shù)解相鄰的整數(shù)作附加約束 約束方程簡單 但子問題由于分枝的增多而成指數(shù)增長 割平面法 割平面法的基礎(chǔ)仍然是用解線性規(guī)劃的方法去解整數(shù)規(guī)劃問題 首先不考慮變量為整數(shù)這一條件 但增加線性約束條件 Gomory約束 稱為割平面 使得原可行解域中切掉一部分 這部分只包含非整數(shù)解 但沒切割掉任何整數(shù)可行解 切除的結(jié)果使整數(shù)解可能成為頂點 關(guān)鍵 如何找到割平面約束方程 使切割后最終得到這樣的可行域 它的一個整數(shù)坐標(biāo)的頂點恰好是問題的最優(yōu)解 割平面法的步驟 求松弛問題的最優(yōu)基可行解 例題 用割平面法求解下列整數(shù)規(guī)劃 x1 0 5x2 4 5 2x1 3x2 14 x1 x2 0 且均取整數(shù)值 第1步 去掉整數(shù)約束找出松弛問題 若約束條件系數(shù)和右邊常數(shù)不是整數(shù) 則必須化為整數(shù) 保證所添加的松弛變量均為整數(shù) 2x1 x2 9 2x1 3x2 14 x1 x2 0 G0 單純形法求解松弛問題G0 得到最終單純形表 因最優(yōu)解不是整數(shù)解需引入附加約束條件 找出非整數(shù)解變量中分?jǐn)?shù)部分最大的一個基變量 并寫出該行在最終表中的約束方程 將上式所有常數(shù)分寫成整數(shù)與正分?jǐn)?shù)之和 分?jǐn)?shù)移項到右端 整數(shù)項到左端 根據(jù)右端為整數(shù)且變量非負(fù)的要求 得到 即 加上松弛變量之后得到 第2步 尋找割平面方程 第3步 在最優(yōu)單純形表中求解增加約束條件后的LP問題的最優(yōu)解 應(yīng)用對偶單純形法迭代計算最優(yōu)解 出基 入基 第3步 在最優(yōu)單純形表中求解增加約束條件后的LP問題的最優(yōu)解 最優(yōu)解仍為非整數(shù)解繼續(xù)尋找Gomory約束 寫出該行在最終表中的約束方程 將上式所有常數(shù)分寫成整數(shù)與正分?jǐn)?shù)之和 分?jǐn)?shù)移項到右端 整數(shù)項到左端 根據(jù)右端為整數(shù)且變量非負(fù)的要求 得到 加上松弛變量之后得到 最優(yōu)解仍為非整數(shù)解繼續(xù)尋找Gomory約束 上述過程找到的兩個割平面方程用決策變量表示分別為 切割過程如圖 使切割后的可行域的一個整數(shù)坐標(biāo)的頂點恰好是問題的最優(yōu)解 確定割平面方程的練習(xí) 第四章整數(shù)規(guī)劃與分配問題 整數(shù)規(guī)劃的特點及作用分枝定界法割平面法分配問題與匈牙利法應(yīng)用舉例 IntegerProgramming 簡稱IP 分配問題的提出 指派問題 若干項工作或任務(wù)需要若干個人去完成 由于每人的知識 能力 經(jīng)驗的不同 故各人完成不同任務(wù)所需要的時間不同 或其他資源 問應(yīng)指派哪個人完成何項工作 可使完成所有工作所消耗的總資源最少 設(shè)某公司準(zhǔn)備派n個工人x1 x2 xn 去作n件工作y1 y2 yn 已知工人xi完成工作yj所需時間為cij i j 1 2 n 現(xiàn)問 如何確定一個分派工人去工作的方案 使得工人們完成工作的總時間為最少 標(biāo)準(zhǔn)形式的分配問題 分派方案滿足下述兩個條件 任一個工人都不能去做兩件或兩件以上的工作任一件工作都不能同時接受兩個及以上的工人去做 設(shè)某公司準(zhǔn)備派n個工人x1 x2 xn 去作n件工作y1 y2 yn 已知工人xi完成工作yj所需時間為cij i j 1 2 n 現(xiàn)問 如何確定一個分派工人去工作的方案 使得工人們完成工作的總時間為最少 標(biāo)準(zhǔn)形式的分配問題 n個人n件事 每件事必有且只有一個人去做 每個人必做且只做一件事 數(shù)學(xué)模型 n個人n件事 cij 第i人做第j事的費用 總費用 i j 1 n j 1 n i 1 n 每件事必有且只有一個人去做 每個人必做且只做一件事 時間 原料 金錢等資源 數(shù)學(xué)模型 線性規(guī)劃問題 運輸問題 0 1型整數(shù)規(guī)劃問題 匈牙利法 1955年由美國數(shù)學(xué)家W W kuhn 庫恩 提出 利用了匈牙利數(shù)學(xué)家D Konig 康尼格 證明的2個定理 系數(shù)矩陣 效率矩陣 解矩陣 決策變量矩陣 n個人n件事 定義 在系數(shù)矩陣C中 處在不同行不同列的一組零元素 稱為獨立零元素組 其中每個元素稱為獨立零元素 最優(yōu)解 定理 若將分配問題系數(shù)矩陣的每一行及每一列分別減去各行及各列的最小元素 則新分配問題與原分配問題有相同的最優(yōu)解 只有最優(yōu)值差一常數(shù) 相關(guān)定理 使每行每列都出現(xiàn)零元素 步驟1 變換系數(shù)矩陣 使其每行每列都出現(xiàn)0元素把各行元素分別減去本行元素的最小值 然后在此基礎(chǔ)上再把每列元素減去本列中的最小值 此時每行及每列中肯定都有0元素 步驟2 進(jìn)行試分配 判斷是否存在n個獨立零元素嘗試對所有零元素做標(biāo)記 確定獨立零元素 1 逐行檢驗 對只有一個未標(biāo)記的零元素的行 用記號O將該零元素圈起 然后將被圈起的零元素所在列的其他未標(biāo)記的零元素用記號 劃去 重復(fù)行檢驗 直到每一行都沒有未被標(biāo)記的零元素或至少有兩個未被標(biāo)記的零元素為止 表示此人只能做該事 此事只能由該人做 表示此事已不能由其他人來做 此人已不能做其他事 步驟2 進(jìn)行試分配 判斷是否存在n個獨立零元素嘗試對所有零元素做標(biāo)記 確定獨立零元素 1 逐行檢驗 對只有一個未標(biāo)記的零元素的行 用記號O將該零元素圈起 然后將被圈起的零元素所在列的其他未標(biāo)記的零元素用記號 劃去 重復(fù)行檢驗 直到每一行都沒有未被標(biāo)記的零元素或至少有兩個未被標(biāo)記的零元素為止 2 逐列檢驗 與行檢驗類似 對只有一個未標(biāo)記的零元素的列 用記號O將該零元素圈起 然后將被圈起的零元素所在行的其他未標(biāo)記的零元素用記號 劃去 重復(fù)列檢驗 直到?jīng)]有未被標(biāo)記的零元素或至少有兩個未被標(biāo)記的零元素為止 圈0即獨立零元素 步驟2 進(jìn)行試分配 判斷是否存在n個獨立零元素嘗試對所有零元素做標(biāo)記 確定獨立零元素 可能出現(xiàn)三種情況 1 每一行均有圈0出現(xiàn) 圈0的個數(shù)恰好等于n2 存在未標(biāo)記過的零元素 但它們所在的行和列中 未被標(biāo)記過的零元素的個數(shù)均至少有兩個 3 不存在未被標(biāo)記過的零元素 但圈0的個數(shù) n 3 判斷獨立零元素的個數(shù) 可能出現(xiàn)三種情況 2 存在未標(biāo)記過的零元素 但它們所在的行和列中 未被標(biāo)記過的零元素的個數(shù)均至少有兩個 3 不存在未被標(biāo)記過的零元素 但圈0的個數(shù) n 3 判斷獨立零元素的個數(shù) 圈0個數(shù)等于n 5 多重最優(yōu)解 可能出現(xiàn)三種情況 3 不存在未被標(biāo)記過的零元素 但圈0的個數(shù) n 3 判斷獨立零元素的個數(shù) 圈0個數(shù)4 n 5 定理 系數(shù)矩陣C中獨立零元素的最多個數(shù)等于能覆蓋所有零元素的最少線數(shù) 例 分別求下列矩陣中的獨立零元素的最多個數(shù) 獨立零元素的個數(shù)最多 對不含圈0的行打 在打 的