1、第第6章章08級本科適用級本科適用08級本科適用級本科適用08級本科適用級本科適用08級本科適用級本科適用拖拉機用工數（人）耗油量（公斤）利潤（百元）甲5220乙4510限制量2413我們首先設我們首先設 x1 ，x2 分別為分別為運用甲、乙兩種遷延機的臺運用甲、乙兩種遷延機的臺數，那么其數學模型為：數，那么其數學模型為： ）（是整數）（）（）（）（5,40,313522244511020max2121212121xxxxxxxxxxz08級本科適用級本科適用不是可行解，也就是說0521xx）（是整數）（）（）（）（5,40,313522244511020max2121212121xxxxxx

2、xxxxz這個模型和這個模型和LP模型的區別僅在于？模型的區別僅在于？如今不思索如今不思索5，解，解1-496max, 08 . 421zxx，0521xx，即取代入方程代入方程2，就破壞了人數約數。，就破壞了人數約數。 以后我們稱這樣的問題為原問題相應的以后我們稱這樣的問題為原問題相應的LP問題問題利用單純形法很容易就可解得：利用單純形法很容易就可解得：80z0421xx，如果就滿足約束條件，因此是可行解就滿足約束條件，因此是可行解 但不是最優解但不是最優解 ，也是可行解，因為90z1421xx08級本科適用級本科適用08級本科適用級本科適用08級本科適用級本科適用08級本科適用級本科適用）

3、（是整數）（）（）（）（5.,40,37020725679)(19040max2121212121xxxxxxxxAxxz35682.181.4B21zxx，356Bz*z08級本科適用級本科適用81.41x5411xx或）（）（）（）（40,37020725679)B(19040max21212121xxxxxxxxz）（）（）（）（40,437020725679)(19040max2112121121xxxxxxxBxxz）（是整數）（）（）（）（5.,40,37020725679)(19040max2121212121xxxxxxxxAxxz）（）（）（）（40,537020725679

4、)(19040max2112121221xxxxxxxBxxz08級本科適用級本科適用567921xx7020721xxD1D2x1x將將B中的中的X1=4.81分成分成X15或或X1 4不思索整數條件，解不思索整數條件，解B1 ，B2得最優解見表得最優解見表B1 B210.200.4349211xxz57.100.5341212xxz219040zxx 解解B1 ，B2，將可行域，將可行域D分成分成為為D1，D22D將將B1中的中的X2=2.1再分成再分成X23或或X22，即，即1分解為分解為B3 ，B4 不思索整數條件，解不思索整數條件，解B3 ，B42308級本科適用級本科適用34000

5、. 200. 4021zxx，得32700. 3428. 1021zxx，08級本科適用級本科適用2122xx和340*z00. 200. 421xx，08級本科適用級本科適用08級本科適用級本科適用）（或 jx）（或 jx08級本科適用級本科適用08級本科適用級本科適用)9 , 2 , 1(jAj321AAA、54AA 、76AA 、98AA 、) 9 , 2 , 1(jAjjbjc08級本科適用級本科適用)9 , 2 , 1(ixj點未被選用點被選用jjjAx0A1102112max9876543219191或jjjjjjjxxxxxxxxxxBxbxcz08級本科適用級本科適用. 10,

6、46433244122523max3213221321321321或）（）（）（）（xxxxxxxxxxxxxxxxz000，100，010，110，001，101，011，111，下面舉例闡明一種解下面舉例闡明一種解0-1型整數規劃的隱枚舉法型整數規劃的隱枚舉法08級本科適用級本科適用. 10,46433244122523max3213221321321321或）（）（）（）（xxxxxxxxxxxxxxxxz000，100，010，110，001，101，011，111，)0,0,1(),(321xxx3z 先經過試換的方法找出一個可行解。容易看出得得z=3。由于是求極大值問題，當然希望。

7、由于是求極大值問題，當然希望于是添加一個約束條件于是添加一個約束條件0： 是符合是符合14條件的可行解條件的可行解）（ 03523321xxx下面舉例闡明一種解下面舉例闡明一種解0-1型整數規劃的隱枚舉法型整數規劃的隱枚舉法. 10,46433244122)0.(.3523523max3213221321321321321或）（）（）（）（xxxxxxxxxxxxxxxxxxxz條件條件0稱為過濾條件稱為過濾條件Filtering Constraint。 這樣原問題的線性條件就變成了這樣原問題的線性條件就變成了5個。個。 原題假設用全部的枚舉法，原題假設用全部的枚舉法，3個變量共有個變量共有2

8、3=8個解，加上個解，加上4個約束條件，共需個約束條件，共需32次運算。次運算。 按照按照04的順序排好。對每個解，依次代入約束的順序排好。對每個解，依次代入約束方程左側，求出數值，如下表方程左側，求出數值，如下表1 。看能否符合不等式條件，。看能否符合不等式條件，假設不符合，同行以下各條件就不用檢查，因此就減少了假設不符合，同行以下各條件就不用檢查，因此就減少了運算次數。運算次數。08級本科適用級本科適用321xxx，約約 束束 條條 件件滿足條件滿足條件否否 是是Z值值（0）（1）（2）（3）（4） 000，100，010，110，001，101，011，111，321523maxxxxz

9、)0.(3523321xxx) 1.(22321xxx)2.(44321xxx) 3.(321 xx)4.(6432 xx05-11015-2如此檢查下去，結果見下個幻燈片如此檢查下去，結果見下個幻燈片 08級本科適用級本科適用321xxx，約約 束束 條條 件件滿足條件滿足條件否否 是是Z值值（0）（1）（2）（3）（4）05-233816-1110215126001 101 538000，100，010，110，001，101，011，111，1 , 0 , 1321xxx，8*z經過經過24次運算求得最優解：次運算求得最優解：，08級本科適用級本科適用321xxx，約約 束束 條條 件件

10、滿足條件滿足條件否否 是是Z值值（0）（1）（2）（3）（4） 000，100，010，110，001，101，011，111，321523maxxxxz)0.(5523321xxx) 1.(22321xxx)2.(44321xxx) 3.(321 xx)4.(6432 xx055-2在計算過程中，假設遇到在計算過程中，假設遇到z值已超越條件值已超越條件0右邊值，應改右邊值，應改動條件動條件0，使右邊為迄今為止的最大者，然后繼續運算。，使右邊為迄今為止的最大者，然后繼續運算。如當檢查點如當檢查點0，0，1時，因時，因z=53，改之為新的過濾條，改之為新的過濾條件，可減少更多的計算量。件，可減少

11、更多的計算量。 338021116268如當檢查點如當檢查點1，0，1時，因時，因z=85，改之為新的過濾條，改之為新的過濾條件，還可減少更多的計算量。此處略。件，還可減少更多的計算量。此處略。 08級本科適用級本科適用000，100，010，110，001，101，011，111，312321532523xxxxxxz312xxx， 為了使最優解比較早出現，普通重新陳列為了使最優解比較早出現，普通重新陳列X j的順序，的順序，使目的函數中使目的函數中X j的系數是遞增的。那么本例可改為：的系數是遞增的。那么本例可改為：約束方程與變量取值均按照順序：約束方程與變量取值均按照順序：、.10,46

12、43442312203532532max3213231212312312312或取）（）（）（）（）（xxxxxxxxxxxxxxxxxxxz按照前面方法求解會更快獲得最優解。合計算按照前面方法求解會更快獲得最優解。合計算16次。次。08級本科適用級本科適用08級本科適用級本科適用ABCD趙4658錢61078孫78119李9384零件零件人員人員ABCD趙4658錢61078孫78119李9384表表6-4-16-4-1： ( (單位：工時單位：工時) ) 在類似的問題中，都必需給出像表在類似的問題中，都必需給出像表6-4-1的數表稱為的數表稱為效率矩陣或系數矩陣，其元素效率矩陣或系數矩陣，

13、其元素 表示指派第表示指派第i人去完成第人去完成第j項義務的效率。項義務的效率。), 2 , 1, ( 0njicij08級本科適用級本科適用), 2 , 1, ( 0njixij.01項任務人去完成第不指派第項任務；人去完成第指派第jijixij）（或）（）（）（4013, 2 , 1, 12, 2 , 1, 11minijjijiijijijijxnixnjxxcz約束條件約束條件2闡闡明第明第j項義務只能由項義務只能由1人去完成；人去完成；約束條件約束條件3闡闡明第明第i人只能去完成一人只能去完成一項義務。項義務。極小極小問題問題08級本科適用級本科適用08級本科適用級本科適用08級本科

14、適用級本科適用08級本科適用級本科適用08級本科適用級本科適用08級本科適用級本科適用08級本科適用級本科適用 9118713161491514410413152ijcijb由于由于m=n=4，所以得最優，所以得最優這表示：安排由甲譯俄文、這表示：安排由甲譯俄文、乙譯日文、丙譯英文、丁譯乙譯日文、丙譯英文、丁譯德文，所需總時間最少為：德文，所需總時間最少為： 0100000100101000ijxijijijijijijbccccxczxbz28min0min14432231為所求為所求 每行都減去該行最小元素每行都減去該行最小元素11100621113047502410每列都減去該列最小元素

15、每列都減去該列最小元素00601501303670290試指派：給只需一個零元素試指派：給只需一個零元素的行的零元素劃圈，并給其的行的零元素劃圈，并給其同列的零元素劃同列的零元素劃試指派：給只需一個零元素試指派：給只需一個零元素的列的零元素劃圈，并給其的列的零元素劃圈，并給其同行的零元素劃同行的零元素劃劃圈的零元素所在位置指派劃圈的零元素所在位置指派為為1，其他位置為零，其他位置為零08級本科適用級本科適用ABCDE甲甲127979乙乙89666丙丙71712149丁丁15146610戊戊4107109義務義務人員人員08級本科適用級本科適用91071041066141591412177666

16、98979712ijc ，所以還沒有解完，按第三步進展：，所以還沒有解完，按第三步進展：1 1對沒有圈對沒有圈0 0的行打的行打“；2 2對已打對已打“的行中的的行中的0 0元素所在列打元素所在列打“；3 3對打對打“列中的列中的“0“0所在行打所在行打“；4 4 反復直至打不出新的反復直至打不出新的“；5 5對沒有打對沒有打“的行畫一橫線，對打的行畫一橫線，對打“的列畫垂線。的列畫垂線。)5()4(nm因為 20205解解00032275100400895636008級本科適用級本科適用在沒有被直線所覆蓋的元素中找出最小元素在沒有被直線所覆蓋的元素中找出最小元素2對沒有打對沒有打“的各行元素分別減的各行元素分別減2，“0除外除外給打給打“的列各元素分別加上的列各元素分別加上2，“0除外除外得到新陣得到新陣*后，并按照前述第二步繼續：后，并按照前述第二步繼續：56360400892751000003220205400800032020053802-23414011472-08級本科適用級本科適用34140400811053800003420207m=n=5具有具有n個獨立的個獨立的0元素，這就得到了最優元素，這就得到了最優解，畫出相應解矩陣，由解矩陣得最