管理運籌學(xué)6整數(shù)規(guī)劃

1、精選ppt 例 用分枝定界法求解 且且均均取取整整數(shù)數(shù),0,255.22108.02.134max21212121xxxxxxxxZ解解: 先求對應(yīng)的松弛問題（記為先求對應(yīng)的松弛問題（記為LP0）)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 用圖解法得到最優(yōu)解用圖解法得到最優(yōu)解X(3.57,7.14),Z0=35.7,如下圖所示。如下圖所示。精選ppt1010108 . 02 . 121 xx255 . 2221 xx松弛問題松弛問題LP0的最優(yōu)解的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC精選ppt得得到到兩兩個

2、個線線性性規(guī)規(guī)劃劃及及增增加加約約束束4311 xx10 x2oABC 0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.5精選ppt10 x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.33 0,64255 . 22108 . 02 . 1:2134max2121212121xxxxxxxxLPxxZ，不不可可

3、行行，得得到到線線性性規(guī)規(guī)劃劃，顯顯然然及及進進行行分分枝枝，增增加加約約束束選選擇擇目目標標值值最最大大的的分分枝枝7762222 xxxLP6不可行72x 0,74255 . 22108 . 02 . 1:2234max2121212121xxxxxxxxLPxxZ，精選ppt10 x1x2oACLP134可可行行域域是是一一條條線線段段即即，, 40,464255 . 22108 . 02 . 1:21134max121121212121 xxxxxxxxxxLPxxZ：及及，得得線線性性規(guī)規(guī)劃劃及及進進行行分分枝枝，增增加加約約束束，選選擇擇由由于于212211542111121LPL

4、PxxLPZZ 6 0,65255 . 22108 . 02 . 1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212精選pptLP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22無可行解無可行解x27精選ppt小結(jié)學(xué)習(xí)要點：學(xué)習(xí)要點

5、： 掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu)掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu) 掌握分支定界法原理掌握分支定界法原理 能夠用分支定界法求解一般整數(shù)規(guī)劃問題能夠用分支定界法求解一般整數(shù)規(guī)劃問題精選ppt精選ppt精選ppt精選ppt循環(huán)循環(huán)(X1,X2,X3)s.t.0s.t.1s.t.2s.t.3s.t.4滿滿足足Z值值1(0,0,0)0no2(0,0,1)5-1101yes53(0,1,0)-2no4(0,1,1)315no5(1,0,0)31110yes36(1,0,1)80211yes87(1,1,0)1no8(1,1,1)626no精選ppt精選ppt精選ppt循循環(huán)環(huán)(X2,X1,X3)s

6、.t.0s.t.1s.t.2s.t.3s.t.4滿滿足足Z值值1(0,0,0)0no2(0,0,1)5-1101yes5循循環(huán)環(huán)(X2,X1,X3)s.t.0s.t.1s.t.2s.t.3s.t.4滿滿足足Z值值3(0,1,0)3no4(0,1,1)80211yes8精選ppt循循環(huán)環(huán)(X2,X1,X3)s.t.0s.t.1s.t.2s.t.3s.t.4滿滿足足Z值值5(1,0,0)-2no6(1,0,1)3no7(1,1,0)1no8(1,1,1)6no精選ppt分配問題與匈牙利法設(shè)設(shè)n 個人被分配去做個人被分配去做n 件工作，規(guī)定每個人只做一件工作，件工作，規(guī)定每個人只做一件工作，每件工作

7、只有一個人去做。已知第每件工作只有一個人去做。已知第i個人去做第個人去做第j 件工作的效率件工作的效率（ 時間或費用）為時間或費用）為Cij(i=1.2n;j=1.2n)并假設(shè)并假設(shè)Cij 0。問應(yīng)。問應(yīng)如何分配才能使總效率（如何分配才能使總效率（ 時間或費用）最高？時間或費用）最高？設(shè)決策變量設(shè)決策變量 ),.,2 , 1,(ji0ji1njixij 件事件事個人做第個人做第不指派第不指派第件事件事個人做第個人做第指派第指派第精選ppt分配問題與匈牙利法 指派問題的數(shù)學(xué)模型為： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijni

8、njijij或或取取精選ppt分配問題與匈牙利法如果從分配問題效率矩陣aij的每一行元素中分別減去(或加上)一個常數(shù)ui，從每一列中分別減去(或加上)一個常數(shù)vj，得到一個新的效率矩陣bij，則以bij為效率矩陣的分配問題與以aij為效率矩陣的分配問題具有相同的最優(yōu)解。精選ppt分配問題與匈牙利法設(shè)設(shè)n 個人被分配去做個人被分配去做n 件工作，規(guī)定每個人只做一件工作，件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第每件工作只有一個人去做。已知第i個人去做第個人去做第j 件工作的效率件工作的效率（ 時間或費用）為時間或費用）為Cij(i=1.2n;j=1.2n)并假設(shè)并假設(shè)Cij

9、0。問應(yīng)。問應(yīng)如何分配才能使總效率（如何分配才能使總效率（ 時間或費用）最高？時間或費用）最高？設(shè)決策變量設(shè)決策變量 ),.,2 , 1,(ji0ji1njixij 件事件事個人做第個人做第不指派第不指派第件事件事個人做第個人做第指派第指派第精選ppt分配問題與匈牙利法 指派問題的數(shù)學(xué)模型為： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或取取精選ppt分配問題與匈牙利法如果從分配問題效率矩陣aij的每一行元素中分別減去(或加上)一個常數(shù)ui，從每一列中分別減去(或加上)一個常數(shù)vj，得到一個新的效率矩陣bij

10、，則以bij為效率矩陣的分配問題與以aij為效率矩陣的分配問題具有相同的最優(yōu)解。精選ppt分配問題與匈牙利法1) 變換指派問題的系數(shù)矩陣變換指派問題的系數(shù)矩陣(cij)為為(bij)，使在，使在(bij)的各行各列的各行各列中都出現(xiàn)中都出現(xiàn)0元素，即元素，即 從從(cij)的每行元素都減去該行的最小元素；的每行元素都減去該行的最小元素； 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2) 進行試指派，以尋求最優(yōu)解。進行試指派，以尋求最優(yōu)解。 在在(bij)中找盡可能多的獨立中找盡可能多的獨立0元素，若能找出元素，若能找出n個獨立個獨立0元元

11、素，就以這素，就以這n個獨立個獨立0元素對應(yīng)解矩陣元素對應(yīng)解矩陣(xij)中的元素為中的元素為1，其余，其余為為0，這就得到最優(yōu)解。，這就得到最優(yōu)解。精選ppt分配問題與匈牙利法 找獨立0元素，常用的步驟為： 從只有一個從只有一個0元素的行開始，給該行中的元素的行開始，給該行中的0元素加圈，記作元素加圈，記作 。然后劃去然后劃去 所在列的其它所在列的其它0元素，記作元素，記作 ；這表示該列所代表的；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進行到最后一行。任務(wù)已指派完，不必再考慮別人了。依次進行到最后一行。 從只有一個從只有一個0元素的列開始（畫元素的列開始（畫的不計在內(nèi)），給該列

12、中的的不計在內(nèi)），給該列中的0元素加圈，記作元素加圈，記作；然后劃去；然后劃去 所在行的所在行的0元素，記作元素，記作 ，表示，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。 若仍有沒有劃圈的若仍有沒有劃圈的0元素，且同行元素，且同行(列列)的的0元素至少有兩個，比元素至少有兩個，比較這行各較這行各0元素所在列中元素所在列中0元素的數(shù)目，選擇元素的數(shù)目，選擇0元素少這個元素少這個0元素加元素加圈圈(表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇性少的選擇性少的)。然后劃掉同行同列。然后劃掉同行同列的其它的其它0元素?？?/p>

13、反復(fù)進行，直到所有元素?？煞磸?fù)進行，直到所有0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。精選ppt分配問題與匈牙利法 若若 元素的數(shù)目元素的數(shù)目m 等于矩陣的階數(shù)等于矩陣的階數(shù)n（即：（即：mn），那么這指，那么這指派問題的最優(yōu)解已得到。若派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。3) 用最少的直線通過所有用最少的直線通過所有0元素。其方法：元素。其方法： 對沒有對沒有的行打的行打“”； 對已打?qū)σ汛颉啊?的行中所有含的行中所有含元素的列打元素的列打“” ； 再對打有再對打有“”的列中含的列中含 元素的行打元素的行打“” ； 重復(fù)重復(fù)、直到得不出新的打直到得不出新的打

14、號的行、列為止；號的行、列為止； 對沒有打?qū)]有打號的行畫橫線，有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋號的列畫縱線，這就得到覆蓋所有所有0元素的最少直線數(shù)元素的最少直線數(shù) l 。注：注：l 應(yīng)等于應(yīng)等于m，若不相等，說明試指派過程有誤，回到第，若不相等，說明試指派過程有誤，回到第2步，另行試步，另行試指派；若指派；若 lm n，表示還不能確定最優(yōu)指派方案，須再變換當前的系，表示還不能確定最優(yōu)指派方案，須再變換當前的系數(shù)矩陣，以找到數(shù)矩陣，以找到n個獨立的個獨立的0元素，為此轉(zhuǎn)第元素，為此轉(zhuǎn)第4步。步。精選ppt分配問題與匈牙利法4) 變換矩陣(bij)以增加0元素 在沒有被直線通過的

15、所有元素中找出最小值，沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。精選ppt分配問題與匈牙利法 例 已知四人分別完成四項工作所需時間如下表，求最優(yōu)分配方案。 任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119精選ppt 解：1）變換系數(shù)矩陣，增加0元素。79429118713161491514410413152 2424104750111006211130 00102350960607130 00102350960607130 2）試指派（找獨立）試指派（找獨立0元素）元素） 獨立獨立0元素的個

16、數(shù)為元素的個數(shù)為4 , 指派問題的最優(yōu)指指派問題的最優(yōu)指派方案即為甲負責派方案即為甲負責D工作，乙負責工作，乙負責B工作，工作，丙負責丙負責A工作，丁負責工作，丁負責C工作。這樣安排工作。這樣安排能使總的工作時間最少，為能使總的工作時間最少，為4491128。精選ppt 例 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？ 任務(wù)人員ABCD甲67112乙4598丙31104丁5982精選ppt分配問題與匈牙利法 解：1）變換系數(shù)矩陣，增加0元素。2142 28

17、9541013895421176)( ijc 06733902451009545 01733402401004542）試指派（找獨立）試指派（找獨立0元素）元素）找到找到 3 個獨立零元素個獨立零元素 但但 m = 3 n = 4精選ppt分配問題與匈牙利法 3）作最少的直線覆蓋所有0元素獨立零元素的個數(shù)獨立零元素的個數(shù)m等于最少等于最少直線數(shù)直線數(shù)l，即，即lm=3n=4；4）沒有被直線通過的元素中選擇最小值為）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個最小元素；直陣，將沒有被直線通過

18、的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。得到新的矩陣，重復(fù)線交點處的元素加上這個最小值。得到新的矩陣，重復(fù)2）步進行試指派步進行試指派精選ppt分配問題與匈牙利法 6244251343000 0 00試指派試指派 6244251343 得到得到4個獨立零元素，個獨立零元素， 所以最優(yōu)解矩陣為：所以最優(yōu)解矩陣為： 0100001000011000即完成即完成4個任務(wù)的總時間最少個任務(wù)的總時間最少為：為：241+8=15精選ppt分配問題與匈牙利法 例 已知五人分別完成五項工作耗費如下表，求最優(yōu)分配方案。 任務(wù)人員ABCDE甲759811乙9127119丙85468丁73696

19、戊467511精選ppt分配問題與匈牙利法4347511576469637964589117129118957 7132036304520142405263402-1 -2 解：1）變換系數(shù)矩陣，增加0元素。精選ppt分配問題與匈牙利法 5032015304310140305242402 5032015304310140305242402 2）試指派（找獨立）試指派（找獨立0元素）元素） 獨立獨立0元素的個數(shù)元素的個數(shù)l45，故畫直線調(diào)整矩陣。，故畫直線調(diào)整矩陣。精選ppt分配問題與匈牙利法 5032015304310140305242402 選擇直線外的最小元素選擇直線外的最小元素為為1；直

20、線外元素減；直線外元素減1，直線交點元素加直線交點元素加1，其，其他保持不變。他保持不變。精選ppt分配問題與匈牙利法 5033004203310240306231301 l =m=4 n=5選擇直線外最小元素為選擇直線外最小元素為1，直線外元素減直線外元素減1，直線交，直線交點元素加點元素加1，其他保持不，其他保持不變，得到新的系數(shù)矩陣。變，得到新的系數(shù)矩陣。精選ppt分配問題與匈牙利法 6044003202300230206130300 總費用為總費用為=5+7+6+6+4=28=5+7+6+6+4=28注：此問題有多個最優(yōu)解注：此問題有多個最優(yōu)解精選ppt分配問題與匈牙利法 604400

21、3202300230206130300 總費用為總費用為=7+9+4+3+5=28=7+9+4+3+5=28精選ppt分配問題與匈牙利法 6044003202300230206130300 總費用為總費用為=8+9+4+3+4=28=8+9+4+3+4=28精選ppt分配問題與匈牙利法 課堂練習(xí)：用匈牙利法求解下列指派問題。79 10 1213 12 16 1715 16 14 1511 12 15 163821038729764275842359106910練習(xí)練習(xí)1：練習(xí)練習(xí)2：精選ppt分配問題與匈牙利法79 10 1213 12 16 1715 16 14 1511 12 15 163

22、8210387297642758423591069104848 21 21答案：答案：精選ppt分配問題與匈牙利法匈牙利法的條件是：模型求最小值、效率匈牙利法的條件是：模型求最小值、效率cij0。當遇到各種非標準形式的指派問題時，處理方法是先將當遇到各種非標準形式的指派問題時，處理方法是先將其轉(zhuǎn)化為標準形式，然后用匈牙利法來求解。其轉(zhuǎn)化為標準形式，然后用匈牙利法來求解。精選ppt處理方法：設(shè)處理方法：設(shè)m為最大化指派問題系數(shù)矩陣為最大化指派問題系數(shù)矩陣C中最大元素。中最大元素。令矩陣令矩陣B（m-cij）nn則以則以B為系數(shù)矩陣的最小化指派問題和為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解

23、。原問題有相同的最優(yōu)解。例例 某人事部門擬招聘某人事部門擬招聘4人任職人任職4項工作，對他們綜合考評的項工作，對他們綜合考評的 得得分如下表（滿分分如下表（滿分100分），如何安排工作使總分最多。分），如何安排工作使總分最多。 88809086907983829578879590739285丁丁丙丙乙乙甲甲C精選ppt分配問題與匈牙利法 解: M95，令)95(ijcC 71559516121301780522310C用匈牙利法求解用匈牙利法求解C，最優(yōu)解為：，最優(yōu)解為： 0100100000010010X即甲安排做第二項工作、乙做第三項、丙做第四項、丁做即甲安排做第二項工作、乙做第三項、丙做第四項、丁做第三項第三項, 最高總分最高總分Z92959080357精選ppt分配問題與匈牙利法 當人數(shù)當人數(shù)m大于工作數(shù)大于工作數(shù)n時，加上時，加上mn項虛擬工作，例如：項虛擬工作，例如： 1235461714836111095 00000000001235461714836111095 當人數(shù)當人數(shù)m小于工作數(shù)小于工作數(shù)n時，加上時，加上nm個人，例如個人，例如 1716131074569102015 00001716131074569102015精選ppt分配問題