整數(shù)線(xiàn)性規(guī)劃

整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)重要分支,可分為:純整數(shù)規(guī)劃(所有變量都限制為整數(shù))、混合整數(shù)規(guī)劃(一部分變量限制為整數(shù))、0-1規(guī)劃(所有變量都限制取0或1).

本章討論純整數(shù)線(xiàn)性規(guī)劃(ILP)及解此規(guī)劃的割平面法和分枝定界法；分配問(wèn)題(0-1規(guī)劃)與匈牙利算法.4.1整數(shù)規(guī)劃的特點(diǎn)及作用4.2分配問(wèn)題與匈牙利算法4.3割平面法4.4分枝定界法第4章整數(shù)規(guī)劃與分配問(wèn)題1§4.1整數(shù)規(guī)劃的特點(diǎn)及作用4.1.1整數(shù)規(guī)劃的模型分類(lèi)

純整數(shù)規(guī)劃模型

0-1整數(shù)規(guī)劃模型

混合整數(shù)規(guī)劃模型4.1.2邏輯變量在建模中的作用4.1.3實(shí)例

投資決策問(wèn)題

背包問(wèn)題4.1.4解整數(shù)線(xiàn)性規(guī)劃的困難性2純整數(shù)規(guī)劃模型0-1整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型4.1.1整數(shù)規(guī)劃的模型分類(lèi)34.1.2邏輯變量在建模中的作用1.m個(gè)約束條件中只有k個(gè)起作用

m個(gè)約束條件可表為

定義又M為任意大的正數(shù)，則在約束條件≤的右端+M(即yi=1),此條件不起作用42.約束條件的右端項(xiàng)可能是r個(gè)值(b1,b2,…,br)中的某一個(gè),

定義上述約束條件(*)可表示為即53.兩組條件中滿(mǎn)足其中一組

定義又M為任意大的正數(shù)，則問(wèn)題可表述為在約束條件≤的右端+M(即yi

=1),此條件不起作用在約束條件≥的右端-M(即yi

=1)，此條件不起作用64.用以表示含有固定費(fèi)用的函數(shù)若將(1)(2)表達(dá)為7【例1】試引入0－1變量將下列各題分別表達(dá)為一般線(xiàn)性約束條件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，則x2≥0，否則x2≤8（3）x2取值0，1，3，5，7【解】（1）3個(gè)約束只有1個(gè)起作用或yi=1此條件不起作用yi=0此條件不起作用8（3）右端常數(shù)是5個(gè)值中的1個(gè)（2）兩組約束只有一組起作用或或9

(1)投資組合問(wèn)題1.問(wèn)題某財(cái)團(tuán)有B萬(wàn)元的資金,經(jīng)出其考察有n個(gè)項(xiàng)目可供投資,其中第j個(gè)項(xiàng)目需投資金額為bj萬(wàn)元,預(yù)計(jì)5年后獲利cj萬(wàn)元,問(wèn)應(yīng)如何選擇項(xiàng)目使得5年后總收益最大？變量約束目標(biāo)2.分析3.數(shù)學(xué)模型4.1.3實(shí)例0-1整數(shù)線(xiàn)性規(guī)劃—總金額不超過(guò)限制—總收益最大101.背景旅行背包容量一定的背包里裝盡可能多的物品(2)背包問(wèn)題某人出國(guó)留學(xué)打點(diǎn)行李,現(xiàn)有三個(gè)旅行包,容積大小分別為1000毫升、1500毫升和2000毫升,根據(jù)需要列出需帶物品清單,其中一些物品是必帶物品共有7件,其體積大小分別為400、300、150、250、450、760、190、(單位毫升).尚有10件可帶可不帶物品,如果不帶將在目的地購(gòu)買(mǎi),通過(guò)網(wǎng)絡(luò)查詢(xún)可以得知其在目的地的價(jià)格(單位美元).這些物品的容量及價(jià)格分別見(jiàn)下表,試給出一個(gè)合理的安排方案把物品放在三個(gè)旅行包里.

物品12345678910體積200350500430320120700420250100價(jià)格15451007050752009020302.問(wèn)題113.問(wèn)題分析變量—對(duì)每個(gè)物品要確定是否帶,同時(shí)還要確定放在哪個(gè)包裹里，設(shè)變量xij為第i個(gè)物品是否放在第j個(gè)包裹中約束包裹容量限制必帶物品限制選帶物品限制目標(biāo)函數(shù)未帶物品購(gòu)買(mǎi)費(fèi)用最小12模型13特征—變量為整數(shù)來(lái)源—問(wèn)題本身的要求;引入的邏輯變量的需要性質(zhì)—可行域是離散集合4.1.4解整數(shù)線(xiàn)性規(guī)劃的困難性與線(xiàn)性規(guī)劃的關(guān)系：整數(shù)規(guī)劃前者的可行解是松弛問(wèn)題的可行解前者的最優(yōu)值小于等于松弛問(wèn)題的最優(yōu)值松弛的線(xiàn)性規(guī)劃問(wèn)題對(duì)于min問(wèn)題,前者的最優(yōu)值大于等于松弛問(wèn)題的最優(yōu)值14最優(yōu)解不一定在頂點(diǎn)上達(dá)到.最優(yōu)解不一定是松弛問(wèn)題最優(yōu)解的鄰近整數(shù)解.整數(shù)可行解的個(gè)數(shù)遠(yuǎn)多于松弛問(wèn)題的頂點(diǎn),枚舉法不可取.解ILP問(wèn)題要遠(yuǎn)難于解松弛的LP問(wèn)題.若松弛的LP問(wèn)題無(wú)解,則原ILP問(wèn)題無(wú)解.反之,不一定成立.結(jié)論15§4.2分配問(wèn)題與匈牙利算法4.2.1分配問(wèn)題的數(shù)學(xué)模型4.2.2匈牙利算法164.2.1分配問(wèn)題的數(shù)學(xué)模型分配問(wèn)題(指派問(wèn)題)

假定有m項(xiàng)任務(wù)分配給m個(gè)人去完成,并指定每人完成其中一項(xiàng),每項(xiàng)只交給其中一個(gè)人去完成,應(yīng)如何分配使總的效率最高.效率矩陣：利用不同資源完成不同計(jì)劃活動(dòng)的效率通常用表格形式表示，表格中的數(shù)字組成效率矩陣.舉例有一份說(shuō)明書(shū),要分別譯成英、日、德、俄四種文字,交甲乙丙丁四個(gè)人去完成.因各人專(zhuān)長(zhǎng)不同,他們完成翻譯不同文字所需的時(shí)間如表所示.應(yīng)如何分配,使這四人分別完成這四項(xiàng)任務(wù)總的時(shí)間最小.效率矩陣

譯成英文譯成日文譯成德文譯城俄文甲21097乙154148丙13141611丁415139工作人一一對(duì)應(yīng)17人工作a1a2aiamb1b2bjbmxi1

xi2

xij

xim-1

xim

x1jxij

x2jxm-1jxmj

分配問(wèn)題的數(shù)學(xué)模型:第i人完成一項(xiàng)任務(wù)第j項(xiàng)任務(wù)由一人完成184.2.2匈牙利算法事實(shí)：若效率矩陣的所有元素,而其中存在一組位于不同行其余的邏輯變量xij=0,

得到的就是問(wèn)題的最優(yōu)解(最優(yōu)分配方案).例效率矩陣為令問(wèn)題：如何產(chǎn)生并尋找這組位于不同行不同列的零元素？不同列的零元素，則只要令對(duì)應(yīng)于這些零元素位置的邏輯變量xij=1,

，其余的xij=019匈牙利數(shù)學(xué)家克尼格(Konig)基礎(chǔ)：兩個(gè)基本定理定理1如果從分配問(wèn)題效率矩陣[aij]的每一行元素中分別減去(或加上)一個(gè)常數(shù)ui(被稱(chēng)為該行的位勢(shì)),從每一列分別減去(或加上)一個(gè)常數(shù)vj(被稱(chēng)為該列的位勢(shì)),得到一個(gè)新的效率矩陣[bij],其中bij=aij-ui-vj

,則[bij]的最優(yōu)解等價(jià)于[aij]的最優(yōu)解。作用：構(gòu)造含有零元素的等價(jià)效率矩陣。定理2若矩陣A的元素分成“0”與非“0”兩部分，則覆蓋“0”元素的最少直線(xiàn)數(shù)等于位于不同行不同列的“0”元素的最大個(gè)數(shù).作用：判別效率矩陣中有多少個(gè)不同行不同列的零元素。20匈牙利算法的步驟：第一步：找出效率矩陣每行的最小元素,并分別從每行中減去最小元素.minmin產(chǎn)生含零的等價(jià)效率矩陣每行至少一個(gè)0元素每列也至少一個(gè)0元素第二步：再找出矩陣每列的最小元素,再分別從各列中減去.21第三步：判定由前兩步得到的效率矩陣中有多少個(gè)不同行不同列的零元素.按照以下準(zhǔn)則進(jìn)行：

(1)從第一行開(kāi)始,若該行只有一個(gè)零元素,就對(duì)這個(gè)零元素打上()號(hào),對(duì)打()號(hào)零元素所在列畫(huà)一條直線(xiàn).

(2)從第一列開(kāi)始,若該列只有一個(gè)零元素就對(duì)這個(gè)零元素打上()號(hào)(同樣不考慮已劃去的零元素),對(duì)打()號(hào)零元素所在行畫(huà)一條直線(xiàn).若該行沒(méi)有零元素或有兩個(gè)以上零元素(已劃去的不計(jì)在內(nèi)),則轉(zhuǎn)下一行,依次進(jìn)行到最后一行.若該列沒(méi)有零元素或有兩個(gè)以上零元素(已劃去的不計(jì)在內(nèi)),,則轉(zhuǎn)下一列,依次進(jìn)行到最后一行.

(3)重復(fù)(1)、(2)兩個(gè)步驟,直至不能進(jìn)行為止，()()()22231效率矩陣每行(或每列)都有一個(gè)打()號(hào)的零元素,令對(duì)應(yīng)打()號(hào)零元素的xij=1,就找到了問(wèn)題的最優(yōu)解.打()號(hào)的零元素個(gè)數(shù)小于m,但未被劃去的零元素之間存在閉回路,打()號(hào)的零元素個(gè)數(shù)小于m,但矩陣中所有零元素被劃去或打上()號(hào).()()()

(3)重復(fù)(1)、(2)兩個(gè)步驟,直至不能進(jìn)行為止，可能出現(xiàn)三種情況:然后對(duì)所有打()號(hào)的零元素,或所在行,或所在列，畫(huà)一條直線(xiàn).重復(fù)(1)、(2)兩個(gè)步驟，直至不能進(jìn)行為止。這時(shí)可順著閉回路的走向,對(duì)每個(gè)間隔的零元素打()號(hào),此時(shí)轉(zhuǎn)第四步。23第四步：為設(shè)法使每一行都有一個(gè)打()號(hào)的零元素，需要繼續(xù)按定理1對(duì)矩陣進(jìn)行變換：

(1)從矩陣未被直線(xiàn)覆蓋的數(shù)字中找出一個(gè)最小的數(shù)字k;

(2)對(duì)矩陣的每行,當(dāng)該行有直線(xiàn)覆蓋時(shí)令ui=0,無(wú)直線(xiàn)覆蓋的令ui=k

(3)對(duì)矩陣的每列,當(dāng)該列有直線(xiàn)覆蓋時(shí)令vj=-k,無(wú)直線(xiàn)覆蓋的令vj=0.

(4)從原矩陣的每個(gè)元素aij中分別減去ui和vj,得到一個(gè)新的矩陣,轉(zhuǎn)第五步。第五步：返回到第三步,反復(fù)進(jìn)行,一直到矩陣的每一行都有一個(gè)打號(hào)的零元素為止,即找到了最優(yōu)分配方案.()()()()()()()24說(shuō)明：1)第三步中的第二種結(jié)果2打()號(hào)的零元素個(gè)數(shù)小于m,但未被劃去的零元素之間存在閉回路,這時(shí)可順著閉回路的走向,對(duì)每個(gè)間隔的零元素打一()號(hào),然后對(duì)所有打()號(hào)的零元素,或所在行,或所在列畫(huà)一條直線(xiàn).()()()()()()或()()()()()()()()或()25例()()()()()(1)(2)()()()()()()()()()()()()()()得到答案()()()()26說(shuō)明：2.分配問(wèn)題中如果人數(shù)和任務(wù)數(shù)不相等時(shí)的處理方法.(2)人數(shù)<任務(wù)數(shù)(1)人數(shù)>任務(wù)數(shù)工作人IIIIII13252746336345355652仍規(guī)定每人完成一項(xiàng)工作,每項(xiàng)工作只交給一個(gè)人去完成

增添兩項(xiàng)假想的工作任務(wù),每個(gè)人完成這兩項(xiàng)任務(wù)時(shí)間為零.IVV0000000000工作人IIIIIIIV1325227463336354000027minmin()()()()()3.目標(biāo)函數(shù)為的處理方法.minmin284.3Gomory割平面法

割平面法是求解整數(shù)規(guī)劃的一個(gè)最早提出的方法,1958年由高莫雷(Gomory)提出.

基本思想是在與整數(shù)規(guī)劃相對(duì)應(yīng)的線(xiàn)性規(guī)劃中逐步增加線(xiàn)性約束條件(稱(chēng)為割平面),使線(xiàn)性規(guī)劃的可行域縮小,同時(shí)保持整數(shù)規(guī)劃的可行解集合不變;

然后求解增加約束后的線(xiàn)性規(guī)劃,如果得到整數(shù)的最優(yōu)解則停止;如果沒(méi)有找到整數(shù)最優(yōu)解,就再增加割平面,一直到得到或證明線(xiàn)性規(guī)劃無(wú)整數(shù)最優(yōu)解為止.29割平面法的解題步驟：第一步：把問(wèn)題中所有約束條件的系數(shù)均化為整數(shù),解該問(wèn)題的松弛問(wèn)題G0.若得到的是整數(shù)解,得到了原問(wèn)題的最優(yōu)解，否則轉(zhuǎn)第二步.構(gòu)造Gomory約束.第二步：將Gomory約束加到G0中得到新的線(xiàn)性規(guī)劃問(wèn)題G1.第三步：重復(fù)第一至第三步直到找出問(wèn)題的整數(shù)最優(yōu)解為止.第四步：30例用割平面法求下述整數(shù)規(guī)劃的最優(yōu)解解：替代問(wèn)題最終單純形表cj

→3200CB基bx1x2x3x42x25/2011/2-1/23x113/410-1/43/4cj

-zj

00-1/4-5/4

找出非整數(shù)解變量中分?jǐn)?shù)部分最大的一個(gè)基變量，并寫(xiě)下這一行的約束

將上式中所有常數(shù)分寫(xiě)成整數(shù)與一個(gè)正分?jǐn)?shù)之和得，31將整數(shù)、分?jǐn)?shù)進(jìn)行分離,得因左端為整數(shù),故右端也需取整數(shù)，故又,故加上松弛變量后得(I)或(II)就是要尋找的Gomory約束因?qū)?III)代入(I)并化簡(jiǎn)得(I)和(IV)等價(jià)32cj

→3200CB基bx1x2x3x42x25/2011/2-1/23x113/410-1/43/4cj

-zj

00-1/4-5/40x500100x5-1/200-1/2-1/2[]2x22010-113x17/21001-1/20x310011-2cj-zj000-1-1/2得到新的Gomory約束加上松弛變量后得33320000x1x2x3x4x5x62x22010-1103x17/21001-1/200x310011-200x6-1/20000-1/21cj-zj000-1-1/20[]2x21010-1023x1410010-10x3300110-40x5100001-2cj-zj000-10-1344.4分枝定界法分枝定界法是一種隱枚舉法，是借助于一種“巧妙”地枚舉整數(shù)規(guī)劃問(wèn)題的可行解的思想來(lái)設(shè)計(jì)算法的，其關(guān)鍵步驟是分枝和定界。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問(wèn)題。上世紀(jì)六十年代初由LandDoig

和Dakin等人提出。由于這種方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它是解整數(shù)規(guī)劃的主要方法。35分枝定界法的解題步驟：第一步：尋找替代問(wèn)題并求解.放寬或取消原問(wèn)題的某些約束若替代問(wèn)題的最優(yōu)解是原問(wèn)題的可行解,則此解就是原問(wèn)題的最優(yōu)解.尋找替代問(wèn)題的方法：替代問(wèn)題的要求：易求解;包含原問(wèn)題的解.否則,此解的目標(biāo)函數(shù)值就是原問(wèn)題最優(yōu)值的上界(求極大)或下界(求極小).例求下述整數(shù)規(guī)劃的最優(yōu)解替代問(wèn)題L0的最優(yōu)解(3.25,2.5),不是原問(wèn)題的可行解,轉(zhuǎn)第二步.原問(wèn)題對(duì)替代問(wèn)題的解進(jìn)行判定36第二步：分枝與定界若子問(wèn)題的最優(yōu)解滿(mǎn)足原問(wèn)題的約束，則該解是原問(wèn)題的可行解.(1)替代問(wèn)題的最優(yōu)解不是原問(wèn)題的可行解時(shí)，將替代問(wèn)題分成兩個(gè)子問(wèn)題(分枝)。子問(wèn)題的要求：易求解;各子問(wèn)題解的集合包含原問(wèn)題的解否則,該解對(duì)應(yīng)的目標(biāo)值為所屬分枝的邊界值(對(duì)求極大問(wèn)題為上界或?qū)η髽O小問(wèn)題為下界).(2)若所有子問(wèn)題的最優(yōu)解均非原問(wèn)題的可行解，則取邊界值最大(求極大)或最小(求極小)的子問(wèn)題進(jìn)一步細(xì)分求解,直到找到一個(gè)原問(wèn)題的可行解為止.出現(xiàn)下述三種情況時(shí)需要分枝：概念：(3)存在子問(wèn)題的邊界值大于可行解的目標(biāo)值時(shí)，需要對(duì)該子問(wèn)題進(jìn)行分枝?？尚薪獾哪繕?biāo)值確定了一個(gè)上界，即待剪去子問(wèn)題的一個(gè)上界。37(3.25,2.5),z=14.75(3.5,2),z=14.5(2.5,3),z=13.5(3,2),z=13(4,1),z=1438第三步：定界與剪枝

如果除保留下來(lái)的可行解外，其余分枝均被剪去，則該可行解就是原問(wèn)題的最優(yōu)解.(1)分枝后出現(xiàn)一個(gè)可行解時(shí)，將邊界值與可行解的目標(biāo)值進(jìn)行比較，把邊界值劣于可行解的分枝剪去。(2)分枝后出現(xiàn)兩個(gè)以上的可行解，選取其中目標(biāo)值最大的一個(gè)可行解保留，其余分枝剪去。然后將各子問(wèn)題邊界值與保留的可行解的值進(jìn)行比較，把邊界值劣于可行解的分枝剪去.第四步：判斷是否最優(yōu)解否則，返回第二步，選取邊界值最優(yōu)的一個(gè)繼續(xù)分枝，定界，剪枝，判斷。需要剪枝的兩種情況：39(3.25,2.5),z=14.75(3.5,2),z=14.5(2.5,3),z=13.5(3,2),z=13(4,1),z=1440【例1】

用分枝定界法求下述混合整數(shù)規(guī)劃的最優(yōu)解解：(3.25,2.5),z=14.75(3