1Lecture6

IntegerProgrammingSchoolofBusinessAdministrationHunanUniversityLecturer:Dr.E-mail:

2LectureOutlineIntegerProgrammingProblem&itsCharacteristicsSolutionofIntegerProgrammingZero-OneIntegerProgrammingAssignmentProblem31.ThepresentationofIPProblemInmanypracticalproblems,thedecisionvariablesactuallymakesenseonlyiftheyhaveintegervalues.變量是人數(shù)、機(jī)器設(shè)備臺數(shù)或產(chǎn)品件數(shù)等對某一個項(xiàng)目要不要投資的決策問題，可選用一個邏輯變量x,當(dāng)x=1表示投資,x=0表示不投資人員的合理安排問題，當(dāng)變量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作4MathematicalModelofIP整數(shù)規(guī)劃(IP)數(shù)學(xué)模型的一般形式:max(min)z=ΣcjxjΣaijxj

bi(i=1,2,…,m,j=1,2,…,n)

xj

0且部分或全部是整數(shù)j=1ns.t.Example15某工廠生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)這兩種產(chǎn)品需要消耗材料A和B，有關(guān)數(shù)據(jù)如下表所示。問這兩種產(chǎn)品應(yīng)各自生產(chǎn)多少才能使工廠利潤最大？ProductsMaterialsProduct1Product2RHSA(kg)5424B(kg)2513Profit(￥/Product)20001000ModelofExample16Supposex1,x2arethenumberofproduct1and2respectively.7ThreeTypesofIPProblemsIPPureIP

alldecisionvariablesarerequiredtohave integervalues.Mixed-IP

some,butnotall,ofthedecisionvariablesarerequiredtohaveintegervalues.Zero-oneIP allthedecisionvariablesmusthaveintegersolutionvaluesof0or1.82.SolutionofIP設(shè)想1：

既然只取整數(shù)，通過枚舉法是否可行呢？對60個變量只取0/1的情形，設(shè)想計(jì)算機(jī)每秒能比較1,000,000個方式，比較完260種方式，大約需要360世紀(jì)！設(shè)想2：

先按一般線性規(guī)劃問題求解，然后把求得到的最優(yōu)解取整，這可行嗎？9OneExamplemaxz=2000x1+1000x25x1+4x2

242x1+5x2

13x1,x2

0變量x1,x2表示兩種貨物的箱數(shù)

按一般的線性規(guī)劃求解，其最優(yōu)解為(4.8,0)64.82.66.5Z＝9600Z＝9000Z＝8000x1x2(5,0)?s.t.10可行域：OABD內(nèi)整數(shù)點(diǎn)放棄整數(shù)要求后，最優(yōu)解B(9.2,2.4)Z0=58.8，而原整數(shù)規(guī)劃最優(yōu)解I(2,4)Z0=58，實(shí)際上B附近四個整點(diǎn)(9,2)(10,2)(9,3)(10,3)都不是原規(guī)劃最優(yōu)解。O1234567891054321xx11xx22I(2,4)B(9.2,2.4)ADAnotherExample求下列問題：maxZ=3x1+13x22x1+9x2

4011x1-8x2

82x1,x2

0,且取整數(shù)值s.t.O1234567891054321x1x2I(2,4)B(9.2,2.4)AD設(shè)想3：求出可行域的“整點(diǎn)凸包”（包含所有整點(diǎn)的最小多邊形OEFGHIJ），則可在此凸包上求線性規(guī)劃的解，即為原問題的解。EFGHIJ求“整點(diǎn)凸包”十分困難12IP經(jīng)典求解法——分枝定界法(BBM)對整數(shù)規(guī)劃（IP），若不考慮整數(shù)要求，對應(yīng)的問題（LP）稱為（IP）的松馳問題

松弛問題的可行域包含原問題的可行域若兩者都有最優(yōu)解，則松弛問題的最優(yōu)目標(biāo)值優(yōu)于原問題的最優(yōu)目標(biāo)值若松弛問題的最優(yōu)解為整數(shù)解，則最優(yōu)解就是原問題的最優(yōu)解松弛問題13BBM求解步驟以求max為例，記原問題(IP)為A，松弛問題(LP)為B求松弛問題B的最優(yōu)解B的最優(yōu)解即為A的最優(yōu)解計(jì)算結(jié)束原問題A也無可行解計(jì)算結(jié)束若B有最優(yōu)解，且符合整數(shù)條件若B無可行解若B有最優(yōu)解，但不符合整數(shù)條件一般取xj=0(j=1,2,…,n)試探用試探法找出A的一個可行解其目標(biāo)函數(shù)值作為下界松弛問題B的最優(yōu)目標(biāo)值作為上界分枝：在B的最優(yōu)解中任選一非整數(shù)變量xj構(gòu)造兩個約束條件xj≤[bj],xj≥[bj]+1分別加入B，得到兩后繼問題B1,B2定界：求解后繼問題，以目標(biāo)函數(shù)最大者作為新的上界，從滿足整數(shù)條件的各分枝中找出目標(biāo)函數(shù)值最大者作新的下界

?結(jié)束Yes剪枝：各分枝若其無可行解或其目標(biāo)函數(shù)值小于下界，則剪去該枝No對剩余的各分枝15解：不考慮整數(shù)條件，求解對應(yīng)松弛問題的最優(yōu)解得x1=4.81,x2=1.82,最優(yōu)值z＝355.88于是，LP0:maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0分枝定界法舉例maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0,且為整數(shù)用試探法尋找原整數(shù)規(guī)劃問題一可行解，顯然,x1=0,x2=0，為一可行解，對應(yīng)目標(biāo)值z=0,于是，任取松弛問題一非整數(shù)變量，這里取x1,將兩約束條件x1≤4,x1≥5,分別加入原松弛問題，構(gòu)造兩個新的問題（分枝）LP1:maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1≤4x1,x2≥0LP1':maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1≥5x1,x2≥016求解兩個分枝，結(jié)果分別為：X1=4,x2=2.1,z=349X1=5,x2=1.57,z=341分枝定界法舉例maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0,且為整數(shù)修改上下界，這里上界下界仍然為由于上下界不相等，繼續(xù)下面步驟。。。判斷是否需要剪枝，這里兩個分枝都有可行解，且各分枝的最優(yōu)目標(biāo)值在上下界之間，因而不需要剪枝繼續(xù)對剩余的各分枝進(jìn)行再分枝，如此反復(fù)Z=349X2=2.1X1=4LP1Z=341X2=1.57X1=5LP1'Z=340X2=2X1=4LP2Z=327X2=3X1=1.42LP2‘Z=356X2=1.82X1=4.81LP0無可行解LP2’‘’Z=308X2=1X1=5.44LP2’‘x1≤4x1≥5x2≤2x2≤1x2≥2x2≥318整數(shù)規(guī)劃OR求解Module→IntegerProgramming193.0-1IntegerProgramming

許多實(shí)際決策問題中要求回答“是/否”、“有/無”,這類問題可借助0-1整數(shù)變量，將復(fù)雜的問題變得簡單。

0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，其變量xj只能取0或1

該條件可用如下約束來描述：

xj≤1，

xj≥0，

xj∈Z200-1規(guī)劃的經(jīng)典求解法－隱枚舉法求解0-1整數(shù)規(guī)劃6(1,1,1)1(1,1,0)z≥8√√√√8(1,0,1)3(1,0,0)3(0,1,1)-2(0,1,0)z≥5√√√√5(0,0,1)z≥0√√√√0(0,0,0)過濾條件約束條件abcdZ值(x1,x2,x3)依次檢驗(yàn)過濾條件和約束條件220-1規(guī)劃建模案例例1(相互排斥的計(jì)劃)：某公司有5個項(xiàng)目被列入投資計(jì)劃，各項(xiàng)目的投資額和期望投資收益如下表所示：項(xiàng)目投資額（萬元）投資收益121016023002103150604130805260180該公司只有600萬元資金可用于投資，由于各種原因有以下約束：(1)項(xiàng)目1、2、3中必須且只能投資一項(xiàng)(2)項(xiàng)目3、4中必須且只能投資一項(xiàng)(3)項(xiàng)目5被選中的前提是項(xiàng)目1必須選中設(shè)xi=1項(xiàng)目i被選中0項(xiàng)目i未被選中i=1,2,3,4,5210x1+300x2+150x3+130x4+260x5≤600（1）確定決策變量（2）確定目標(biāo)函數(shù)（3）確定約束條件maxz=160x1+210x2+60x3+80x4+180x5公司只有600萬元資金可用于投資項(xiàng)目1、2、3中必須且只能投資一項(xiàng)x1+x2+x3=1項(xiàng)目3、4中必須且只能投資一項(xiàng)x3+x4=1項(xiàng)目5被選中的前提是項(xiàng)目1必須選中x5≤x1maxz=160x1+210x2+60x3+80x4+180x5s.t.210x1+300x2+150x3+130x4+260x5≤600x1+x2+x3=1x3+x4=1x5≤x1

xi=0或1,i=1,2,3,4,5求解(OR)數(shù)學(xué)模型25ABC利潤(元/件)C1C2Ⅰ0.30.20.30.225Ⅱ0.70.10.50.440每周工時(shí)250100150120

例2(相互排斥的約束):某產(chǎn)品有Ⅰ和Ⅱ兩種型號，需要經(jīng)過ABC三道工序，單位工時(shí)、利潤、各工序每周工時(shí)限制如表所示。問：工廠如何安排生產(chǎn)，才能使總利潤最大(C工序有兩種工作方式C1和C2供選擇，產(chǎn)品為整數(shù)）0-1規(guī)劃案例（1）確定決策變量

設(shè)Ⅰ和Ⅱ兩種型號的產(chǎn)量分別為x1和x2（2）確定目標(biāo)函數(shù)

maxz=25x1+40x2（3）確定約束條件A、B兩道工序每周工時(shí)約束

0.3x1+0.7x2≤2500.2x1+0.1x2≤100工序C有兩種加工方式，其每周工時(shí)約束

0.3x1+0.5x2≤1500.2x1+0.4x2≤120這兩個約束是互斥的，只能選一個！為了將兩個約束條件統(tǒng)一到一個問題中，引入0-1變量：于是，前述互斥約束條件可統(tǒng)一為：

0.3x1+0.5x2≤150＋My10.2x1+0.4x2≤120+My2

y1+y2=1其中M是充分大的正數(shù)數(shù)學(xué)模型maxz=25x1+40x20.3x1+0.7x2≤2500.2x1+0.1x2≤1000.3x1+0.5x2≤150＋My10.2x1+0.4x2≤120+My2y1+y2=1x1,x2≥0,x1,x2∈Zy1,y2

∈{0,1}s.t.

一般的，在建立數(shù)學(xué)模型時(shí)，若需要從p個約束條件中選擇q個約束，則可引入P個0－1變量再構(gòu)造約束條件組，即可達(dá)到目的300-1規(guī)劃案例例3(固定成本問題):

某公司須購買50,000個燈泡。三個供應(yīng)單位：A公司,每個3元，至少訂購量為20,000個,至多30,000個B公司,每個5元,至少10,000個C公司,每個1元，另加固定費(fèi)20000元,訂購量0～30,000內(nèi)任選公司決定從一家或兩家購買，采取怎樣的訂購方案可使所花費(fèi)用最少？解：設(shè)xA表示從A公司購買的燈泡數(shù)

xB表示從B公司購買的燈泡數(shù)

xC表示從C公司購買的燈泡數(shù)1從A公司購買0不從A公司購買YA=1從B公司購買0不從B公司購買YB=1從C公司購買0不從C公司購買YC=數(shù)學(xué)模型Minz=3xA+5xB+xC+20000YCxA+xB+xC≥50000xA≥20000YAxA≤30000YA

xB≥10000YBxB≤MYBxC≤30000YCYA+YB+YC≤2xA,xB,xC≥0,xA,xB,xC

∈Z

YA,YB,YC

∈{0,1}求解(OR)s.t.0-1背包問題33有一個背包容積為v，現(xiàn)有n種物品可裝入，物品i的重量為wi，體積為vi(i=1,2,…,n)。試問應(yīng)該如何裝包，使得在不超過容積的前提下，總重量最大。xi=1物品i裝入背包0物品i不裝入背包344.什么是指派問題？

設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的的效率（時(shí)間或費(fèi)用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（收益）最高，或總時(shí)間最少？35指派問題的數(shù)學(xué)模型1個人做1件事1件事1個人做設(shè)決策變量xij=1分配第i個人去做第j件工作0相反(i,j=1,2,…,n)36求解指派問題的方法——匈牙利法

指派問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純型法求解運(yùn)輸問題一樣是不合算的。利用指派問題的特點(diǎn)可有更簡便的解法——匈牙利法(HungarianMethodorHungarianAlgorithm)

37匈牙利解法原理——性質(zhì)1設(shè)一個指派模型的效益矩陣為[Cij].若[Cij]的第i行元素均減去一個常數(shù)ui(稱為該行的行位勢)，第j列元素均減去一個常數(shù)vj(稱為該列的列位勢)，得到一個新的效益矩陣[C’ij=Cij-ui-vj]，則以[C’ij]為效益矩陣的指派問題的最優(yōu)解與原[Cij]的最優(yōu)解相同。（同解變換）示例(-4)39匈牙利解法原理——性質(zhì)2若矩陣C的元素可分為“0”與非“0”兩部分，則覆蓋0元素的最少直線數(shù)恰好等于位于不同行不同列的0元素(獨(dú)立0元素)的最大個數(shù)。i1i2irj1j2jr40匈牙利解法步驟

第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即

(1)從（cij）的每行元素都減去該行的最小元素；

(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。

第二步：進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個獨(dú)立0元素，就以這n個獨(dú)立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為：

(1)給只有一個0元素的行中的0元素加圈，記作◎；然后劃去◎所在列的其它0元素，記作?；表示該列所代表的任務(wù)已指派完，不必再考慮別人了。

(2)給只有一個0元素的列中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?，表示該人已被占用，不必再考慮其他工作了。

(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。

（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。

第三步：作最少的直線覆蓋所有0元素。

(1)對沒有◎的行打√號；

(2)對已打√號的行中所有含?元素的列打√號；

(3)再對打有√號的列中含◎元素的行打√號；(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為止；

(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若l＝m<n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個獨(dú)立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。

例一：

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119249742◎?◎??◎◎分配方案

有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例二：求解過程如下：第一步，變換系數(shù)矩陣：－5第二步，試指派：◎◎◎??

找到3個獨(dú)立零元素但m=3<n=

4

第三步，作最少的直線覆蓋所有0元素：

◎◎◎??√√√獨(dú)立零元素的個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；

第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：000000得到4個獨(dú)立零元素，所以最優(yōu)解矩