運(yùn)籌學(xué)課件--整數(shù)規(guī)劃

1、第四章第四章 整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃與分配問題 第一節(jié)第一節(jié) 整數(shù)線性規(guī)劃問題整數(shù)線性規(guī)劃問題 第二節(jié)第二節(jié) 分枝定界法分枝定界法 第三節(jié)第三節(jié) 01 規(guī)劃規(guī)劃 第四節(jié)第四節(jié) 分配問題分配問題 第一節(jié)第一節(jié) 整數(shù)線性規(guī)劃問題整數(shù)線性規(guī)劃問題一一 、整數(shù)線性規(guī)劃問題、整數(shù)線性規(guī)劃問題二、二、 整數(shù)規(guī)劃的分類整數(shù)規(guī)劃的分類l純整數(shù)規(guī)劃純整數(shù)規(guī)劃 所有變量都取非負(fù)整數(shù)的線性規(guī)劃所有變量都取非負(fù)整數(shù)的線性規(guī)劃 特：特：0 01 1規(guī)劃規(guī)劃 變量的值只限制取變量的值只限制取0 0或或1 1的線性規(guī)劃的線性規(guī)劃l混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃 部分變量取非負(fù)整數(shù)的線性規(guī)劃部分變量取非負(fù)整數(shù)的線性規(guī)劃第三節(jié)第

2、三節(jié) 01規(guī)劃規(guī)劃 第三節(jié)第三節(jié) 01規(guī)劃規(guī)劃 第四節(jié)第四節(jié) 分配問題分配問題 一、一、分配問題分配問題 二、匈牙利方法二、匈牙利方法一、分配問題一、分配問題 分配問題分配問題 分配問題分配問題 基基 本本 概概 念念l解矩陣解矩陣l系數(shù)矩陣系數(shù)矩陣l匹配匹配l獨(dú)立獨(dú)立0元素元素系數(shù)矩陣的定義與性質(zhì)系數(shù)矩陣的定義與性質(zhì)匹匹 配配甲甲蝶泳蝶泳乙乙蛙泳蛙泳 丙丙自由泳自由泳丁丁仰泳仰泳甲甲蛙泳蛙泳乙乙自由泳自由泳 丙丙蝶泳蝶泳丁丁仰泳仰泳分配問題的匈牙利解法分配問題的匈牙利解法 第一步：給系數(shù)矩陣第一步：給系數(shù)矩陣“制造制造”0元素：元素： 1.從系數(shù)矩陣的每行元素減去該行的最小元素；從系數(shù)矩陣的

3、每行元素減去該行的最小元素； 2. 從系數(shù)矩陣的每列元素減去該列的最小元素。從系數(shù)矩陣的每列元素減去該列的最小元素。第二步：找第二步：找 n 個獨(dú)立的個獨(dú)立的“0”元素元素 ： 如果個數(shù)達(dá)到如果個數(shù)達(dá)到n個，則結(jié)束，已得最優(yōu)解；個，則結(jié)束，已得最優(yōu)解； 否則，轉(zhuǎn)第三步。否則，轉(zhuǎn)第三步。第三步第三步 增加系數(shù)矩陣中的增加系數(shù)矩陣中的0元素：元素：1. 找最少直線覆蓋效率矩陣中的所有找最少直線覆蓋效率矩陣中的所有0元素元素（1）對沒有）對沒有0*行的行打行的行打 ，（2）對打）對打 的行上所有有的行上所有有0元素的列打元素的列打 ，（3）對打）對打 的列上所有有的列上所有有0*元素的行打元素的行打

4、 ，（4）重復(fù)（）重復(fù)（2）（）（3）步，到過程結(jié)束）步，到過程結(jié)束（5）對沒有打）對沒有打 的行畫橫線，所有打的行畫橫線，所有打 的列畫垂線，的列畫垂線，找到了覆蓋所有找到了覆蓋所有0元素的最少直線。元素的最少直線。 分配問題的匈牙利解法分配問題的匈牙利解法分配問題的匈牙利解法分配問題的匈牙利解法2. 增加增加0元素元素（1）在系數(shù)矩陣中沒有被覆蓋的元素中找最?。┰谙禂?shù)矩陣中沒有被覆蓋的元素中找最小元素元素 ；（2）對沒有被直線覆蓋的行，減去最小元素）對沒有被直線覆蓋的行，減去最小元素 ，對被直線覆蓋的列，加上最小元素對被直線覆蓋的列，加上最小元素 ； 轉(zhuǎn)第二步。轉(zhuǎn)第二步。 分配問題的匈牙利

5、解法分配問題的匈牙利解法 9118713161491514410413152分配問題的匈牙利解法分配問題的匈牙利解法 794291187131614915144104131522424104750111006211130001023509606017130 0010235096*06017130001235*096*0601713*01235*096*0601713*01235*096*06*01713 分配問題的匈牙利解法分配問題的匈牙利解法 541100032450115280分配問題的匈牙利解法分配問題的匈牙利解法 最大值問題最大值問題 匈牙利法實(shí)質(zhì)上一種求最小值的方法，匈牙利法實(shí)質(zhì)上一

6、種求最小值的方法，如果給我們的是系數(shù)矩陣，如果給我們的是系數(shù)矩陣，a ij表示表示的是第的是第 i 個個人員完成第人員完成第 j 項(xiàng)任務(wù)的收益，則要求我們?nèi)绾雾?xiàng)任務(wù)的收益，則要求我們?nèi)绾畏峙淠橙送瓿赡稠?xiàng)任務(wù)，使總收益最大。這種分配某人完成某項(xiàng)任務(wù)，使總收益最大。這種求最大值的分配問題如何求解呢。求最大值的分配問題如何求解呢。分配問題的匈牙利解法分配問題的匈牙利解法系數(shù)矩陣不是方陣系數(shù)矩陣不是方陣 在實(shí)際問題中，往往遇到有些任務(wù)沒有人去在實(shí)際問題中，往往遇到有些任務(wù)沒有人去做，或某些人沒有分配到任務(wù)的情況。對系數(shù)做，或某些人沒有分配到任務(wù)的情況。對系數(shù)矩陣來說，表現(xiàn)為系數(shù)矩陣不是方陣，而用匈矩陣

7、來說，表現(xiàn)為系數(shù)矩陣不是方陣，而用匈牙利法求解時(shí)，系數(shù)矩陣為方陣是必要條件。牙利法求解時(shí)，系數(shù)矩陣為方陣是必要條件。 分配問題的匈牙利解法分配問題的匈牙利解法 某工廠訂購了三臺機(jī)器（某工廠訂購了三臺機(jī)器（A,B,C），有四），有四各位置可供機(jī)器安裝（位置一，二，三，四），各位置可供機(jī)器安裝（位置一，二，三，四），但但B機(jī)器不能安裝在第二號位置。由于這四個機(jī)器不能安裝在第二號位置。由于這四個安裝位置離工廠中心的遠(yuǎn)近不同，所需要的原安裝位置離工廠中心的遠(yuǎn)近不同，所需要的原料運(yùn)送費(fèi)用也就不同，想要求總的原料運(yùn)送費(fèi)料運(yùn)送費(fèi)用也就不同，想要求總的原料運(yùn)送費(fèi)用達(dá)到最小，問這些機(jī)器安裝在哪幾個位置最用達(dá)到最小，問這些機(jī)器安裝在哪幾個位置最適合？適合？ 分配問題的匈牙利解法分配問題的匈牙利解法分配問題的匈牙利解法分配問題的匈牙利解法00006107520131511121013M分配問題的匈牙利解法分配問題的匈牙利解法 某單位有四項(xiàng)