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

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

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

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

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

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

投資決策問題

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

m個約束條件可表為

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

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

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

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

=1)，此條件不起作用64.用以表示含有固定費用的函數(shù)若將(1)(2)表達(dá)為7【例1】試引入0－1變量將下列各題分別表達(dá)為一般線性約束條件（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個約束只有1個起作用或yi=1此條件不起作用yi=0此條件不起作用8（3）右端常數(shù)是5個值中的1個（2）兩組約束只有一組起作用或或9

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

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

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

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

xi2

xij

xim-1

xim

x1jxij

x2jxm-1jxmj

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

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

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

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

(1)從第一行開始,若該行只有一個零元素,就對這個零元素打上()號,對打()號零元素所在列畫一條直線.

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

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

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

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

(2)對矩陣的每行,當(dāng)該行有直線覆蓋時令ui=0,無直線覆蓋的令ui=k

(3)對矩陣的每列,當(dāng)該列有直線覆蓋時令vj=-k,無直線覆蓋的令vj=0.

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

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

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

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

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

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

-zj

00-1/4-5/4

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

將上式中所有常數(shù)分寫成整數(shù)與一個正分?jǐn)?shù)之和得，31將整數(shù)、分?jǐn)?shù)進(jìn)行分離,得因左端為整數(shù),故右端也需取整數(shù)，故又,故加上松弛變量后得(I)或(II)就是要尋找的Gomory約束因?qū)?III)代入(I)并化簡得(I)和(IV)等價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ī)劃問題的可行解的思想來設(shè)計算法的，其關(guān)鍵步驟是分枝和定界。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。上世紀(jì)六十年代初由LandDoig

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

如果除保留下來的可行解外，其余分枝均被剪去，則該可行解就是原問題的最優(yōu)解.(1)分枝后出現(xiàn)一個可行解時，將邊界值與可行解的目標(biāo)值進(jìn)行比較，把邊界值劣于可行解的分枝剪去。(2)分枝后出現(xiàn)兩個以上的可行解，選取其中目標(biāo)值最大的一個可行解保留，其余分枝剪去。然后將各子問題邊界值與保留的可行解的值進(jìn)行比較，把邊界值劣于可行解的分枝剪去.第四步：判斷是否最優(yōu)解否則，返回第二步，選取邊界值最優(yōu)的一個繼續(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