運(yùn)籌學(xué)第四章整數(shù)規(guī)劃與分配問題ppt課件

1、作業(yè)：作業(yè)：P126 4.1 4.2 4.3(a) 4.4第四章第四章 整數(shù)規(guī)劃與分配問題整數(shù)規(guī)劃與分配問題第一節(jié)第一節(jié) 整數(shù)規(guī)劃的特點(diǎn)及運(yùn)用整數(shù)規(guī)劃的特點(diǎn)及運(yùn)用一、整數(shù)規(guī)劃的普通方式一、整數(shù)規(guī)劃的普通方式定義：一部分或全部決策變量必需取整數(shù)定義：一部分或全部決策變量必需取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不思索整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不思索整數(shù)條件，由余下的目的函數(shù)和約束條件構(gòu)成條件，由余下的目的函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃的松弛問題。的規(guī)劃問題稱為該整數(shù)規(guī)劃的松弛問題。假設(shè)松弛問題是線性規(guī)劃，那么該整數(shù)規(guī)假設(shè)松弛問題是線性規(guī)劃，那么該整數(shù)規(guī)劃稱為整數(shù)線性規(guī)劃。劃稱為整數(shù)線性

2、規(guī)劃。且部分或全部取整數(shù)）或或),.2 , 1(0),.2 , 1(min)max(11njxmibxaxczjijnjijjnjj且均取整數(shù)值最優(yōu)解求下述整數(shù)規(guī)劃問題的例, 0,5 . 45 . 0143223max. 121212121xxxxxxxxz整數(shù)線性規(guī)劃的普通方式:不思索整數(shù)要求時(shí)，不思索整數(shù)要求時(shí)，最優(yōu)解為：最優(yōu)解為： X=(3.25 ,2.5)T X=(3.25 ,2.5)T Z=13 Z=13 見下頁圖解法見下頁圖解法思索整數(shù)要求時(shí)，最優(yōu)解為：思索整數(shù)要求時(shí)，最優(yōu)解為：X=(4 ,1)T Z=14X=(4 ,1)T Z=14湊整湊整 3 3，2 2可行，非最優(yōu)，可行，非最

3、優(yōu)，Z=13Z=13。 4 4，3 3，4 4，2 2，3 3，3 3 不可行不可行二、整數(shù)規(guī)劃的分類二、整數(shù)規(guī)劃的分類1. 1. 全整數(shù)線性規(guī)劃全整數(shù)線性規(guī)劃 決策變量全部取整數(shù)，約束系數(shù)和約束常數(shù)項(xiàng)決策變量全部取整數(shù)，約束系數(shù)和約束常數(shù)項(xiàng)也取整數(shù)的整數(shù)線性規(guī)劃。也取整數(shù)的整數(shù)線性規(guī)劃。2. 2. 純整數(shù)線性規(guī)劃純整數(shù)線性規(guī)劃 決策變量全部取整數(shù)，約束系數(shù)和約束常數(shù)項(xiàng)決策變量全部取整數(shù)，約束系數(shù)和約束常數(shù)項(xiàng)可取非整數(shù)的整數(shù)線性規(guī)劃?？扇》钦麛?shù)的整數(shù)線性規(guī)劃。 純整數(shù)線性規(guī)劃可化為全整數(shù)線性規(guī)劃。純整數(shù)線性規(guī)劃可化為全整數(shù)線性規(guī)劃。3. 3. 混合整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃 決策變量中有一部

4、分取整數(shù)值，另一部分可取決策變量中有一部分取整數(shù)值，另一部分可取非整數(shù)值的整數(shù)線性規(guī)劃。非整數(shù)值的整數(shù)線性規(guī)劃。4. 0-14. 0-1整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃 決策變量只能取決策變量只能取0 0或或1 1的整數(shù)線性規(guī)劃。的整數(shù)線性規(guī)劃。三、三、0-1變量或稱邏輯變量在模型中變量或稱邏輯變量在模型中的運(yùn)用的運(yùn)用 整數(shù)規(guī)劃模型對(duì)研討管理問題有重整數(shù)規(guī)劃模型對(duì)研討管理問題有重要意義。很多不能歸結(jié)為線性規(guī)劃數(shù)學(xué)要意義。很多不能歸結(jié)為線性規(guī)劃數(shù)學(xué)模型的管理問題，卻可以經(jīng)過設(shè)置邏輯模型的管理問題，卻可以經(jīng)過設(shè)置邏輯變量建立起整數(shù)規(guī)劃數(shù)學(xué)模型。變量建立起整數(shù)規(guī)劃數(shù)學(xué)模型。第二節(jié)第二節(jié) 分配問題分配問題(

5、(指派問題與匈牙利法指派問題與匈牙利法 2-1 2-1 問題的提出及數(shù)學(xué)模型問題的提出及數(shù)學(xué)模型 假設(shè)有假設(shè)有m m項(xiàng)義務(wù)分配給項(xiàng)義務(wù)分配給m m個(gè)人去完成，并個(gè)人去完成，并指定每個(gè)人完成其中一項(xiàng)，每項(xiàng)義務(wù)也只由指定每個(gè)人完成其中一項(xiàng)，每項(xiàng)義務(wù)也只由一個(gè)人完成，問應(yīng)如何分配義務(wù)，才干使總一個(gè)人完成，問應(yīng)如何分配義務(wù)，才干使總效率最高？或總費(fèi)用最少，破費(fèi)的總時(shí)間效率最高？或總費(fèi)用最少，破費(fèi)的總時(shí)間最少等等。最少等等。 設(shè)每個(gè)人完成不同義務(wù)的耗費(fèi)見下面的設(shè)每個(gè)人完成不同義務(wù)的耗費(fèi)見下面的效率矩陣，通常要求效率矩陣，通常要求aij0aij0。 mmmmmmmmijaaaaaaaaaaA.212222

6、111211),.,2 , 1,(j0, 1mjiijixij項(xiàng)任務(wù)。人去完成第不分配第，項(xiàng)任務(wù)；人去完成第分配第又設(shè)那么分配問題的數(shù)學(xué)模型為那么分配問題的數(shù)學(xué)模型為),.,2 , 1,(10),.,2 , 1( 1),.,2 , 1( 1min1111mjixmjxmixxazijmiijmjijmimjijij，或2-2 2-2 匈牙利法匈牙利法定理定理1.1.假設(shè)從分配問題效率矩陣假設(shè)從分配問題效率矩陣(aij)(aij)的每一的每一行元素中分別減去或加上一個(gè)常數(shù)行元素中分別減去或加上一個(gè)常數(shù)ui ui 稱為該行的位勢(shì)；從每一列中分別減去稱為該行的位勢(shì)；從每一列中分別減去或加上一個(gè)常數(shù)或

7、加上一個(gè)常數(shù) vj vj 稱為該列的位稱為該列的位勢(shì)；得到一個(gè)新的效率矩陣勢(shì)；得到一個(gè)新的效率矩陣bijbij，其中，其中bij= bij= aij - ui - vj aij - ui - vj ，那么，那么aijaij的最優(yōu)解等價(jià)于的最優(yōu)解等價(jià)于bijbij的最優(yōu)解。的最優(yōu)解。定理定理2. 2. 假設(shè)效率矩陣假設(shè)效率矩陣A A的元素可分成的元素可分成0 0與非與非0 0兩部分，那么覆蓋一切兩部分，那么覆蓋一切0 0元素的最少直線數(shù)等元素的最少直線數(shù)等于位于不同行不同列的于位于不同行不同列的0 0元素的最大個(gè)數(shù)。元素的最大個(gè)數(shù)。匈牙利法的步驟：匈牙利法的步驟：第一步第一步 效率矩陣每行都減去

8、該行的最小元素；效率矩陣每行都減去該行的最小元素；第二步第二步 效率矩陣每列都減去該列的最小元素；效率矩陣每列都減去該列的最小元素； 此時(shí)，效率矩陣的每行每列都有此時(shí)，效率矩陣的每行每列都有0 0元素。元素。第三步第三步 尋覓位于不同行不同列的尋覓位于不同行不同列的0 0元素，也就是元素，也就是尋覓能覆蓋一切尋覓能覆蓋一切0 0元素的最少直線數(shù)。元素的最少直線數(shù)。 方法：方法：1. 1. 從只需一個(gè)從只需一個(gè)0 0元素的行開場(chǎng)，對(duì)元素的行開場(chǎng)，對(duì)0 0元素打上元素打上 號(hào)，然后對(duì)打號(hào)，然后對(duì)打 的的0 0元素所在列畫一條直線，元素所在列畫一條直線，依次進(jìn)展到最后一行；依次進(jìn)展到最后一行；2.

9、2. 從只需一個(gè)從只需一個(gè)0 0元素的列開場(chǎng)，對(duì)元素的列開場(chǎng)，對(duì)0 0元素打上元素打上 號(hào)，號(hào)， 然后對(duì)打然后對(duì)打 的的0 0元素所在行畫一條直線，元素所在行畫一條直線，依次進(jìn)展到最后一列；依次進(jìn)展到最后一列；3. 3. 反復(fù)反復(fù)1.1.、2.2.兩個(gè)步驟，能夠出現(xiàn)三種情況：兩個(gè)步驟，能夠出現(xiàn)三種情況： 1 1假設(shè)能找到假設(shè)能找到m m個(gè)位于不同行不同列的個(gè)位于不同行不同列的0 0元素元素即帶即帶 的的0 0元素，那么令元素，那么令0 0處的處的xij=1,xij=1,求解終了；求解終了；2 2假設(shè)有構(gòu)成閉回路的假設(shè)有構(gòu)成閉回路的0 0元素，那么任選一個(gè)元素，那么任選一個(gè)打打 ，然后對(duì)每個(gè)間隔

10、的，然后對(duì)每個(gè)間隔的0 0元素打元素打 ，同，同時(shí)對(duì)打時(shí)對(duì)打 的的0 0元素所在行或列畫一條直線。元素所在行或列畫一條直線。 3 3假設(shè)位于不同行不同列的假設(shè)位于不同行不同列的0 0元素元素 即帶即帶 的的0 0元素元素 少于少于m m，轉(zhuǎn)第四步。，轉(zhuǎn)第四步。 第四步第四步 為產(chǎn)生為產(chǎn)生m m個(gè)位于不同行不同列的個(gè)位于不同行不同列的0 0元素，元素，用定理一對(duì)效率矩陣進(jìn)展調(diào)整，使之生成新的用定理一對(duì)效率矩陣進(jìn)展調(diào)整，使之生成新的0 0元素。方法：元素。方法：1. 1. 在效率矩陣未被直線覆蓋的元素中找出最小在效率矩陣未被直線覆蓋的元素中找出最小元素元素k k；2. 2. 效率矩陣未被直線覆蓋的

11、行都減效率矩陣未被直線覆蓋的行都減k;k;3. 3. 效率矩陣被直線覆蓋的列都加效率矩陣被直線覆蓋的列都加k;k;4. 4. 轉(zhuǎn)回第三步。轉(zhuǎn)回第三步。2-3 特殊情況的處置特殊情況的處置1. 人數(shù)多于義務(wù)數(shù)，加虛擬義務(wù)。人數(shù)多于義務(wù)數(shù)，加虛擬義務(wù)。設(shè)有設(shè)有n人，人，m項(xiàng)義務(wù)，項(xiàng)義務(wù)，nm,那么添加那么添加n-m項(xiàng)義務(wù)。項(xiàng)義務(wù)。2. 人數(shù)少于義務(wù)數(shù)，加虛擬人員。人數(shù)少于義務(wù)數(shù)，加虛擬人員。設(shè)有設(shè)有n人，人，m項(xiàng)義務(wù)，項(xiàng)義務(wù)，nm,那么添加那么添加m-n項(xiàng)義務(wù)。項(xiàng)義務(wù)。此時(shí)，效率矩陣的元素全成為負(fù)值，不符合要此時(shí)，效率矩陣的元素全成為負(fù)值，不符合要求，根據(jù)定理求，根據(jù)定理1 1，令，令變換后的效率

12、矩陣每行都加變換后的效率矩陣每行都加M M即可。即可。mimjijijxaz11)(min ijaMmax3. 對(duì)求最大值問題的處置對(duì)求最大值問題的處置設(shè)目的函數(shù)為設(shè)目的函數(shù)為可將其變換為可將其變換為mimjijijxaz11max作業(yè)：作業(yè)：P127 4.8(a)P127 4.8(a)第三節(jié)第三節(jié) 分枝定界法分枝定界法一、分枝定界法的根本思想一、分枝定界法的根本思想 先不思索整數(shù)解的限制，用單純形法求先不思索整數(shù)解的限制，用單純形法求解其松弛問題，假設(shè)求得的解恰好是整數(shù)解，解其松弛問題，假設(shè)求得的解恰好是整數(shù)解，那么得整數(shù)規(guī)劃最優(yōu)解，停頓計(jì)算。否那么，那么得整數(shù)規(guī)劃最優(yōu)解，停頓計(jì)算。否那么，

13、將松弛問題分解為兩個(gè)子問題也稱后繼問將松弛問題分解為兩個(gè)子問題也稱后繼問題，每個(gè)子問題都是在原松弛問題的根底題，每個(gè)子問題都是在原松弛問題的根底上添加一個(gè)變量取整數(shù)的約束條件，這樣就上添加一個(gè)變量取整數(shù)的約束條件，這樣就減少了原來的可行域，然后用單純形法求解，減少了原來的可行域，然后用單純形法求解，直至得到最終結(jié)果。直至得到最終結(jié)果。二、分枝定界法的步驟最大值問題二、分枝定界法的步驟最大值問題第一步第一步 尋覓替代問題并求解尋覓替代問題并求解 設(shè)原整數(shù)規(guī)劃問題為設(shè)原整數(shù)規(guī)劃問題為IPIP，其松弛問題為，其松弛問題為L0L0。用單純形法求用單純形法求L0L0，假設(shè)，假設(shè)L0L0無可行解，那么無可

14、行解，那么IPIP也也無可行解，計(jì)算停頓。假設(shè)求得無可行解，計(jì)算停頓。假設(shè)求得L0L0為整數(shù)解，為整數(shù)解，那么得那么得IPIP的最優(yōu)解，停頓。否那么，轉(zhuǎn)下一步；的最優(yōu)解，停頓。否那么，轉(zhuǎn)下一步；第二步第二步 分枝與定界分枝與定界 在在L0L0的解中，任選一個(gè)不滿足整數(shù)條件的的解中，任選一個(gè)不滿足整數(shù)條件的變量變量xixi，設(shè)，設(shè)xi = bi xi = bi ，那么做兩個(gè)子問題，那么做兩個(gè)子問題 iibxL,1 1,2iibxL 不思索整數(shù)條件，用單純形法求解兩個(gè)不思索整數(shù)條件，用單純形法求解兩個(gè)子問題，假設(shè)得整數(shù)解或子問題的最優(yōu)值小子問題，假設(shè)得整數(shù)解或子問題的最優(yōu)值小于前面分支中已計(jì)算得到

15、的一切整數(shù)解的目于前面分支中已計(jì)算得到的一切整數(shù)解的目的函數(shù)最大值，那么停頓分枝；否那么，選的函數(shù)最大值，那么停頓分枝；否那么，選取一切子問題中目的函數(shù)值最大的問題作為取一切子問題中目的函數(shù)值最大的問題作為L0L0繼續(xù)分枝，直至得到整數(shù)規(guī)劃的最優(yōu)解。繼續(xù)分枝，直至得到整數(shù)規(guī)劃的最優(yōu)解。 第三步第三步 剪枝剪枝 在一切整數(shù)解中選取獲得最大值的解為在一切整數(shù)解中選取獲得最大值的解為最優(yōu)解。最優(yōu)解。且均取整數(shù)值數(shù)規(guī)劃問題的最優(yōu)解用分枝定界法求下述整例, 0,5 . 45 . 0143223max.21212121xxxxxxxxz第四節(jié)第四節(jié) 割平面法割平面法一、割平面法的根本思想一、割平面法的根本

16、思想 先不思索整數(shù)條件，用單純形法求解其先不思索整數(shù)條件，用單純形法求解其松弛問題，假設(shè)得整數(shù)解，即得整數(shù)規(guī)劃最松弛問題，假設(shè)得整數(shù)解，即得整數(shù)規(guī)劃最優(yōu)解。否那么，添加線性約束條件稱為割優(yōu)解。否那么，添加線性約束條件稱為割平面方程，將原問題的可行域切割掉一部平面方程，將原問題的可行域切割掉一部分，被切割掉的都是非整數(shù)解，再用單純形分，被切割掉的都是非整數(shù)解，再用單純形法求解新的線性規(guī)劃問題，依次進(jìn)展下去，法求解新的線性規(guī)劃問題，依次進(jìn)展下去，直到使問題的最優(yōu)解恰好在可行域的某個(gè)具直到使問題的最優(yōu)解恰好在可行域的某個(gè)具有整數(shù)坐標(biāo)的頂點(diǎn)上得到。有整數(shù)坐標(biāo)的頂點(diǎn)上得到。二、割平面法的步驟二、割平面法

17、的步驟第一步第一步 將問題化為全整數(shù)規(guī)劃問題；將問題化為全整數(shù)規(guī)劃問題； 第二步第二步 加非負(fù)松弛變量，將約束條件化為等加非負(fù)松弛變量，將約束條件化為等式約束；式約束； 第三步第三步 解相應(yīng)的線性規(guī)劃問題解相應(yīng)的線性規(guī)劃問題1. 1. 假設(shè)線性規(guī)劃的最優(yōu)解是整數(shù)解，那么得假設(shè)線性規(guī)劃的最優(yōu)解是整數(shù)解，那么得整數(shù)規(guī)劃的最優(yōu)解，停頓計(jì)算，否那么轉(zhuǎn)整數(shù)規(guī)劃的最優(yōu)解，停頓計(jì)算，否那么轉(zhuǎn)2;2;2. 2. 求解割平面方程作為附加約束條件，構(gòu)成求解割平面方程作為附加約束條件，構(gòu)成新的線性規(guī)劃問題，繼續(xù)第三步。新的線性規(guī)劃問題，繼續(xù)第三步。三、割平面方程的求法三、割平面方程的求法 1.1.求解線性方程組法求

18、解線性方程組法 設(shè)設(shè)xi=bi xi=bi 是整數(shù)規(guī)劃的松弛問題是整數(shù)規(guī)劃的松弛問題LPLP問題問題最優(yōu)解中取分?jǐn)?shù)值分?jǐn)?shù)部分最大的基變量，最優(yōu)解中取分?jǐn)?shù)值分?jǐn)?shù)部分最大的基變量，將將xi=bixi=bi用非基變量表示用非基變量表示 將將bibi，aikaik分解成整數(shù)部分和非負(fù)真分?jǐn)?shù)部分分解成整數(shù)部分和非負(fù)真分?jǐn)?shù)部分之和：之和：kkikiixabxkkikikkikiikkikikkikikkikikiiiikikikikiiiixffxNNxxffxNNxfNfNxffNaffNb)() 10() 10(得kkikiixabx 要使一切變量都取非負(fù)整數(shù)值，上式左要使一切變量都取非負(fù)整數(shù)值，上式

19、左端必為整數(shù)，從而右端也必為整數(shù)，由于端必為整數(shù)，從而右端也必為整數(shù)，由于fi fi 0 0 ， fik 0 fik 0 ，故應(yīng)有，故應(yīng)有 這就是所求的割平面方程這就是所求的割平面方程GomoryGomory方程方程 。1kkikixff例例 設(shè)某整數(shù)規(guī)劃的松弛問題最優(yōu)解中有設(shè)某整數(shù)規(guī)劃的松弛問題最優(yōu)解中有x1 = x1 = 3.5 3.5 ， x1 x1的非基變量表達(dá)式為的非基變量表達(dá)式為x1=3.5 + 2.4 x4 3.6 x5 + 4 x6 x1=3.5 + 2.4 x4 3.6 x5 + 4 x6 =3+0.5+2 x4 +0.4 x4 - 4 x5 +0.4 x5 +4 =3+0.

20、5+2 x4 +0.4 x4 - 4 x5 +0.4 x5 +4 x6x6或或: : x1-3- 2x4+4x5-4 x6 = 0.5+0.4x4+0.4x5 x1-3- 2x4+4x5-4 x6 = 0.5+0.4x4+0.4x5 由此可得割平面方程為由此可得割平面方程為 0.5 + 0.4 x4 + 0.4 x5 1 0.5 + 0.4 x4 + 0.4 x5 1 2. 2. 借助單純形表法借助單純形表法 對(duì)求解整數(shù)規(guī)劃問題的松弛問題對(duì)求解整數(shù)規(guī)劃問題的松弛問題LPLP問題得到問題得到最優(yōu)單純形表，設(shè)最優(yōu)單純形表，設(shè)xi=bi xi=bi 是最優(yōu)解中取分?jǐn)?shù)值分?jǐn)?shù)是最優(yōu)解中取分?jǐn)?shù)值分?jǐn)?shù)部分最

21、大的基變量，那么有部分最大的基變量，那么有kkikiikkikiikikikikiikikikikiiiiikiikkikixffNxNxfNxfNxffNaffNbabbxax即得令真分?jǐn)?shù)部分之和，分解成整數(shù)部分和非負(fù)將)() 10() 10(, 上式中，要使等式左端為整數(shù)，那么右上式中，要使等式左端為整數(shù)，那么右端也必為整數(shù)，由端也必為整數(shù)，由0 0fifi1,1,故應(yīng)有故應(yīng)有 這就是所求的割平面方程這就是所求的割平面方程GomoryGomory方程。方程。0kkikixff例例 設(shè)某整數(shù)規(guī)劃的松弛問題最優(yōu)解中有設(shè)某整數(shù)規(guī)劃的松弛問題最優(yōu)解中有x1=3.5 x1=3.5 ， x1x1在單純

22、形表中的約束條件為：在單純形表中的約束條件為： x1-2.4x4 +3.6x5 -4x6=3.5 x1-2.4x4 +3.6x5 -4x6=3.5 x1-3x4+0.6x4+3x5+0.6x5-4 x6=3+0.5 x1-3x4+0.6x4+3x5+0.6x5-4 x6=3+0.5 或或: x1-3-3x4+3x5-4x6=0.5-0.6x4-0.6x5 : x1-3-3x4+3x5-4x6=0.5-0.6x4-0.6x5 由此可得割平面方程為由此可得割平面方程為 0.5 -0.6x4 -0.6x50 0.5 -0.6x4 -0.6x50 且均取整數(shù)值規(guī)劃問題的最優(yōu)解用割平面法求下述整數(shù)例,

23、0,5 . 45 . 0143223max.21212121xxxxxxxxz解：解：1.1.將問題化為全整數(shù)規(guī)劃問題；去掉變量的將問題化為全整數(shù)規(guī)劃問題；去掉變量的整數(shù)要求，可得其松弛問題整數(shù)要求，可得其松弛問題G0G02. 2. 加松弛變量，將約束化為等式約束；并加松弛變量，將約束化為等式約束；并用單純形法求解得到最優(yōu)表；表用單純形法求解得到最優(yōu)表；表4-44-40,92143223max21212121xxxxxxxxz0,92143223max432142132121xxxxxxxxxxxxz3. 找出非整數(shù)解變量中非整數(shù)部分最大的找出非整數(shù)解變量中非整數(shù)部分最大的一個(gè)基變量這里是一個(gè)

24、基變量這里是x2，并寫出這一行，并寫出這一行的約束；的約束；:02121212121212)212()211()210(2122121434342432432加松弛變量化為等式所以，割平面方程為或即xxxxxxxxxxxx。形表，見表的單純法繼續(xù)求解得到中，然后用對(duì)偶單純形的單純形表解，可將該式直接加入求問題的約束中，得一新的將上式加入松弛問題54LP2121211010543GGGGxxx 4.由于表中還有非整數(shù)解，找出非整數(shù)解變量由于表中還有非整數(shù)解，找出非整數(shù)解變量中非整數(shù)部分最大的一個(gè)基變量這里是中非整數(shù)部分最大的一個(gè)基變量這里是x1，并寫出這一行的約束；并寫出這一行的約束；:0212

25、1212132132121321555415541541加松弛變量化為等式得割平面方程為或即xxxxxxxxxxxx。單純形表，見表的續(xù)求解得到然后用對(duì)偶單純形法繼的單純形表中，可將該式直接加入求解，問題中得一新的將上式加入到64LP2121212165GGGGxx該表已得到整數(shù)解，故原整數(shù)規(guī)劃問題的最優(yōu)解該表已得到整數(shù)解，故原整數(shù)規(guī)劃問題的最優(yōu)解為為: x1 = 4: x1 = 4， x2 = 1x2 = 1， 最優(yōu)值為最優(yōu)值為max z=14max z=14作業(yè)：作業(yè)：P128130 4.13 4.14 4.16 4.18 P128130 4.13 4.14 4.16 4.18 第五節(jié)第五

26、節(jié) 解解0-10-1規(guī)劃問題的隱枚舉法規(guī)劃問題的隱枚舉法一、隱枚舉法的根本思想一、隱枚舉法的根本思想 首先令一切整數(shù)變量都取首先令一切整數(shù)變量都取0 0值，然后使某值，然后使某些變量取值為些變量取值為1 1，直到獲得一個(gè)可行解，將第，直到獲得一個(gè)可行解，將第一個(gè)可行解作為暫時(shí)最優(yōu)解稱為過濾條一個(gè)可行解作為暫時(shí)最優(yōu)解稱為過濾條件，再繼續(xù)試探某些變量的取值，假設(shè)可件，再繼續(xù)試探某些變量的取值，假設(shè)可找到另一個(gè)可行解優(yōu)于暫時(shí)最優(yōu)解，那么將找到另一個(gè)可行解優(yōu)于暫時(shí)最優(yōu)解，那么將新的可行解作為暫時(shí)最優(yōu)解新的過濾條新的可行解作為暫時(shí)最優(yōu)解新的過濾條件，依此類推，檢查整數(shù)變量等于件，依此類推，檢查整數(shù)變量等于0 0或或1 1的的各種組合，不斷尋求新的暫時(shí)