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

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