運(yùn)籌學(xué)胡運(yùn)權(quán)第五版課件

第4章整數(shù)規(guī)劃與分配問(wèn)題IntegerProgrammingandAssignmentProblem§4.1整數(shù)規(guī)劃的特點(diǎn)與作用例

某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)及托運(yùn)時(shí)所受的限制如下表所示，問(wèn)如何托運(yùn)能使總收益最大？貨物體積(米3/箱)重量(噸/箱)利潤(rùn)(千元/箱)甲乙2 2 33 1 214（米3）9（噸）托運(yùn)限制解：建模如下設(shè)托運(yùn)甲貨物x1箱，乙貨物x2箱2、整數(shù)規(guī)劃的一般形式1、整數(shù)規(guī)劃（IntegerProgramming）決策變量部分或全部取值為整數(shù)的線性規(guī)劃問(wèn)題，稱為整數(shù)線性規(guī)劃或簡(jiǎn)稱整數(shù)規(guī)劃，常記為IP。純整數(shù)規(guī)劃

所有決策變量要求取非負(fù)整數(shù)。混合整數(shù)規(guī)劃

只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。3、整數(shù)規(guī)劃的分類例如該問(wèn)題是純整數(shù)規(guī)劃.在整數(shù)規(guī)劃IP中去掉變量取整限制得到的線性規(guī)劃問(wèn)題稱為松弛問(wèn)題，常用L0表示。4、整數(shù)規(guī)劃的松弛問(wèn)題例求解下列整數(shù)線性規(guī)劃。解：其松弛問(wèn)題為先求松弛問(wèn)題的最優(yōu)解；再用四舍五入的方法求整數(shù)規(guī)劃的最優(yōu)解24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=6松弛問(wèn)題的最優(yōu)解ABCD取整得到4個(gè)整數(shù)解：A(3,2)B(4,2)C(4,3)D(3,3)不可行可行解,此時(shí)z=13但A不是該整數(shù)規(guī)劃的最優(yōu)解！P該問(wèn)題共有19個(gè)整數(shù)可行解,注意：可行域不是凸集！其中P(4,1)是最優(yōu)解

zmax=145、整數(shù)規(guī)劃IP與其松弛問(wèn)題L0的關(guān)系若L0無(wú)可行解，則IP無(wú)可行解；若L0有整數(shù)最優(yōu)解，則IP有相同的最優(yōu)解；若L0有非整數(shù)最優(yōu)解，則IP的最優(yōu)解不能確定。注意：求解IP時(shí)，不能通過(guò)先解L0再通過(guò)湊整的方法進(jìn)行；

IP的可行域不再是凸集。6、0-1變量（邏輯變量）取值只能為0或者1的決策變量。注意：0-1變量通常用來(lái)表示只有兩種結(jié)果的選擇性決策。7、0-1變量在實(shí)際問(wèn)題中的應(yīng)用管理問(wèn)題整數(shù)線性規(guī)劃引入0-1變量

0－1規(guī)劃所有決策變量只能取0-1變量。（1）表示選擇性約束例用0-1變量將表示成一般線性約束條件。8、0-1變量在表示線性約束條件中的應(yīng)用一般的，已知m個(gè)約束條件若只有k個(gè)起作用，則（2）表示選擇性取值例用0-1變量將表示成一般線性約束條件。一般的，若約束條件的右端項(xiàng)（或變量x）只能取r個(gè)值b1,b2,…,br中的一個(gè)值（3）表示兩組條件中僅有一組滿足例用0-1變量將表示成一般線性約束條件?！?.2分配問(wèn)題及匈牙利法2-1問(wèn)題的提出與數(shù)學(xué)模型例有一份說(shuō)明書(shū)，要分別翻譯成英、日、德、俄四種文字，交給甲、乙、丙、丁四個(gè)人去完成，因各人專長(zhǎng)不同，他們完成翻譯不同文字所需要的時(shí)間（小時(shí)）如表所示。規(guī)定每項(xiàng)工作只能交給其中一個(gè)人完成，每個(gè)人只能完成其中一項(xiàng)工作。問(wèn)：如何分配，能使所需的總時(shí)間最少？譯英譯日譯德譯俄甲215134乙1041415丙9141613丁78119人工作解:建立如下模型設(shè)

xij=10甲：x11+x12+x13+x14=1乙：x21+x22+x23+x24=1丙：x31+x32+x33+x34=1?。簒41+x42+x43+x44=1譯英：x11+x21+x31+x41=1譯日：x12+x22+x32+x42=1譯德：x13+x23+x33+x43=1譯俄：x14+x24+x34+x44=1xij

=0或1(i=1,2,3,4;j=1,2,3,4)minz=aijxij i=1j=144第i個(gè)人完成第j項(xiàng)工作第i個(gè)人不完成第j項(xiàng)工作用aij表示第

i個(gè)人完成第j項(xiàng)任務(wù)的時(shí)間

有m項(xiàng)工作要交給m個(gè)人完成，規(guī)定每項(xiàng)工作只能交給其中一個(gè)人完成，而每個(gè)人只能完成其中一項(xiàng)工作。問(wèn)：如何分配，可使所需的總時(shí)間最少？（或總效率最高？）1、分配問(wèn)題或指派問(wèn)題（AssignmentProblem）2、分配問(wèn)題的已知條件m個(gè)人，用i=1,2,…,m表示；

m項(xiàng)工作，用j=1,2,…,m表示；

aij為第i個(gè)人完成第j項(xiàng)工作所需花費(fèi)的資源（即時(shí)間或效率）將m階矩陣（aij）稱為該分配問(wèn)題的效率矩陣（此處效率也包括時(shí)間），此時(shí)該問(wèn)題稱為m階分配問(wèn)題。3、分配問(wèn)題的表格形式

工作人12…m1a11a12…a1m2a21a22…a2m......mam1am2…amm4、標(biāo)準(zhǔn)分配問(wèn)題求目標(biāo)函數(shù)的極小值效率矩陣的元素全非負(fù)aij≥05、標(biāo)準(zhǔn)分配問(wèn)題的數(shù)學(xué)模型第i個(gè)人完成一項(xiàng)工作第j項(xiàng)工作由一個(gè)人完成分配問(wèn)題是0-1整數(shù)規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例。分配問(wèn)題一定有最優(yōu)解。2-2匈牙利法4(0)5654(0)5763(0)(0)562例已知某分配問(wèn)題的效率矩陣如右：1、特殊情況在標(biāo)準(zhǔn)形式的分配問(wèn)題中，若m階效率矩陣中存在m個(gè)不同行不同列的0元素（稱之為獨(dú)立的0元素），則令這些0元素對(duì)應(yīng)位置上的變量的值為1，其他變量的值為0，得到該問(wèn)題的最優(yōu)解。2、基本原理（1）如果從效率矩陣[aij]的每一行元素中分別減去(或加上)一個(gè)常數(shù)（稱之為行位勢(shì)，記做ui

）,或者從每一列中分別減去(或加上)一個(gè)常數(shù)（稱之為列位勢(shì)，記做vj）,得到一個(gè)新的效率矩陣[bij],其中bij=aij-ui-vj,則以[bij]為效率矩陣的最優(yōu)解等價(jià)于以[aij]為效率矩陣的最優(yōu)解.（2）系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)=能夠覆蓋所有0元素的最少直線數(shù)。定理（1）的證明以[aij]為效率矩陣的目標(biāo)函數(shù)值：z0=aijxij以[bij]為效率矩陣的目標(biāo)函數(shù)值：

z=bijxijmmi=1j=1i=1j=1mm∵

bij=aij-ui-vj∴z=(aij-ui-vj)xij=aijxij-uixij

-vjxij

=z0-uixij-

vjxijmmmmmmmmmm=z0-ui-vj=z0-常數(shù)mmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1mm故以[bij]為效率矩陣的分配問(wèn)題的最優(yōu)解等價(jià)于以[aij]為效率矩陣的分配問(wèn)題的最優(yōu)解.3、匈牙利法由匈牙利數(shù)學(xué)家克尼格（Konig）建立的用于求解分配問(wèn)題的計(jì)算方法。4、匈牙利法的步驟第一步造0：變換效率矩陣，使每行每列至少有一個(gè)0找出每行最小元素（即該行的行位勢(shì)ui），從該行各元素中減去ui找出每列最小元素（即該列的列位勢(shì)vj），從該列各元素中減去vj

第二步劃直線：計(jì)算獨(dú)立0元素的個(gè)數(shù)②、逐列檢查若該列只有一個(gè)未標(biāo)記的0，對(duì)其加()標(biāo)記（表明這項(xiàng)工作必須由對(duì)應(yīng)的人完成），同時(shí)劃一條直線覆蓋該行的所有元素（表明此人不能再完成其他工作）。否則輪空，轉(zhuǎn)下一列檢查，直到所有列檢查完；①、逐行檢查若該行只有一個(gè)未標(biāo)記的0，對(duì)其加()標(biāo)記（表明這個(gè)人必須對(duì)應(yīng)的工作），同時(shí)劃一條直線覆蓋該列的所有元素（表明此項(xiàng)工作不能再由其他人完成）。否則輪空，轉(zhuǎn)下一行檢查，直到所有行檢查完；③、在未被直線覆蓋的元素中重復(fù)①②，直至再劃不出這樣的直線，轉(zhuǎn)入④。④、可能出現(xiàn)三種情況： 情況1：打（0）的個(gè)數(shù)=m，即每行均有（0），則令（0）對(duì)應(yīng)的變量xij=1，其他變量=0，得到該問(wèn)題的最優(yōu)解，計(jì)算總時(shí)間，結(jié)束。 情況2：打（0）的個(gè)數(shù)<m，且未被直線覆蓋的0元素構(gòu)成閉回路，則沿該回路對(duì)每個(gè)間隔的0打（），同時(shí)劃去該0所在的一列。情況3：打（0）的個(gè)數(shù)<m，且所有0元素均被直線劃去。出現(xiàn)僵局，轉(zhuǎn)入第三步。000000第三步

打破僵局：使未劃去的元素中出現(xiàn)新的0元素①

從未被直線覆蓋的元素中找出一個(gè)最小的元素，用k表示； ②逐行檢查，若該行有直線覆蓋，則令行位勢(shì)ui=0，否則令ui=k； ③逐列檢查，若該列有直線覆蓋，則令列位勢(shì)vj=-k,否則令vj=0；④在現(xiàn)有效率矩陣中減去行位勢(shì)和列位勢(shì)，得到新的效率矩陣，轉(zhuǎn)入第二步?！皺M線為0”“豎線負(fù)k”21513410414159141613781192497ui01311260101105740142vj

004201370606905320100例用匈牙利法求解下列分配問(wèn)題。（1）最優(yōu)分配甲乙丙丁譯俄譯日譯英譯德減去ui減去vj總時(shí)間zmin=4+4+9+11=28小時(shí)210971541481314161141513924114ui0875110104235001195vj

00500825110542300011452202-2-200080311032450001123（2）減去ui減去vj出現(xiàn)僵局，取K=2減去ui減去vj最優(yōu)分配人1234工作3241總時(shí)間zmin=9+4+11+4=28例已知分配問(wèn)題的效率矩陣如下，試求總效率最高的分配方案。

工作人一二三136227143365例求解下列分配問(wèn)題。

工作人一二三四136262714433658464375524365762解：∵人數(shù)>工作數(shù)∴增加假想的工作，建立標(biāo)準(zhǔn)分配問(wèn)題如下：

工作人一二三四五六136260027144003365800464370055243006576200最優(yōu)分配人123456工作三二一四總時(shí)間zmin=2+1+3+2=8（1）任務(wù)E必須完成,其他4項(xiàng)任務(wù)可任選3項(xiàng)完成.（2）其中有1人完成2項(xiàng),其他每人完成1項(xiàng).（3）任務(wù)A由甲或丙完成，任務(wù)C由丙或丁完成，任務(wù)E由甲或乙或丁完成，且規(guī)定4人中丙或丁完成2項(xiàng)任務(wù)，其它每人完成1項(xiàng)。（1）任務(wù)E必須完成,其他4項(xiàng)任務(wù)可任選3項(xiàng)完成.其中有1人完成2項(xiàng),其他每人完成1項(xiàng).（3）任務(wù)A由甲或丙完成，任務(wù)C由丙或丁完成，任務(wù)E由甲或乙或丁完成，且規(guī)定4人中丙或丁完成2項(xiàng)任務(wù)，其它每人完成1項(xiàng)。例已知分配問(wèn)題的效率矩陣如下，試求總效率最高的分配方案。

工作人一二三1362271433652-3兩點(diǎn)說(shuō)明1．人數(shù)與工作數(shù)不等的處理

當(dāng)人數(shù)>工作數(shù)時(shí)：增加假想的工作，使得工作數(shù)與人數(shù)能夠匹配,對(duì)應(yīng)的效率設(shè)定為0。

當(dāng)工作數(shù)>人數(shù)時(shí)：增加假想的人，使得人數(shù)與工作數(shù)能夠匹配,對(duì)應(yīng)的效率設(shè)定為0或M或其它。2．若目標(biāo)函數(shù)為求max

z的處理（例如已知每個(gè)人完成各項(xiàng)工作的效率）令z=-z

等價(jià)于求解

minz

=∑∑(-aij)xiji=1j=1mm再利用第1個(gè)基本原理減去行（列）位勢(shì)，化為效率矩陣非負(fù)的情形。§4.3分枝定界法二、分枝定界法用來(lái)求解整數(shù)線性規(guī)劃的方法。一、整數(shù)線性規(guī)劃（IP）的特征

1、可行域不是凸集；

2、可行解的個(gè)數(shù)是有限的；

3、當(dāng)可行解個(gè)數(shù)不多時(shí)，可以用窮舉法求解。三、原理

在求解某問(wèn)題時(shí)，先放寬或取消其中某些約束，求解一個(gè)較簡(jiǎn)單的替代問(wèn)題，而且總是保證原問(wèn)題的可行域包含在替代問(wèn)題的可行域中。四、步驟以純整數(shù)規(guī)劃為例，已知其松弛問(wèn)題為：

第一步求解松弛問(wèn)題（L0）先不考慮整數(shù)約束，解(

IP)的松弛問(wèn)題(L0)，可能得到以下情況之一：①若(L0)無(wú)可行解，則(IP)也無(wú)可行解，結(jié)束。②若(L0)有最優(yōu)解，并符合(IP)的取整條件，則(L0)的最優(yōu)解即為(IP)的最優(yōu)解，結(jié)束。③若(L0)有最優(yōu)解，但不符合(IP)的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)(L0)的最優(yōu)解為：

第二步分枝與定界記(

IP)的目標(biāo)函數(shù)最優(yōu)值為Z*。以松弛問(wèn)題（L0）的最優(yōu)解X（0）對(duì)應(yīng)的目標(biāo)函數(shù)值Z0作為Z*

的上界。

在(L0)的最優(yōu)解X(0)中，任選一個(gè)不符合整數(shù)條件的變量，例如xr=

（不為整數(shù)），以表示不超過(guò)的最大整數(shù)。構(gòu)造兩個(gè)約束條件

xr≤和xr≥＋1

將這兩個(gè)約束條件分別加入問(wèn)題(

L0

)，形成兩個(gè)子問(wèn)題(L1)和(L2)。注意：（L1）和（L2）的可行域之并集包含（IP)的全部可行解。

依次求解兩個(gè)子問(wèn)題（L1）和（L2），將出現(xiàn)兩種情況：①某個(gè)子問(wèn)題的最優(yōu)解滿足變量取整的要求，即為原（IP）的整數(shù)可行解，進(jìn)入第三步；②兩個(gè)子問(wèn)題的最優(yōu)解均非整數(shù)可行解，則選目標(biāo)函數(shù)值較大的子問(wèn)題繼續(xù)分枝求解，直至出現(xiàn)某個(gè)子問(wèn)題的最優(yōu)解滿足變量取整要求，即為原（IP）的整數(shù)可行解，進(jìn)入第三步。

第三步比較與剪枝若出現(xiàn)兩個(gè)或更多整數(shù)可行解，則僅保留目標(biāo)函數(shù)值較大的一個(gè)。將各分枝的目標(biāo)函數(shù)值與保留的整數(shù)可行解進(jìn)行比較，并把目標(biāo)函數(shù)值小于整數(shù)可行解的目標(biāo)函數(shù)值的分枝剪去，將出現(xiàn)兩種情況：①僅保留整數(shù)可行解，其他分枝均被剪去，則該整數(shù)可行解即為原（IP）的最優(yōu)解，結(jié)束；②除保留整數(shù)可行解外，還有其他未被剪去的分枝，則取目標(biāo)函數(shù)值最大的繼續(xù)分枝，直至出現(xiàn)新的整數(shù)可行解，重復(fù)第三步。例用分枝定界法求解下列IP問(wèn)題

圖解法x1x2012345678910123456782x1+x2=72x1+4x2=13X（0）=(5/2,2)z0=23X（1）=(2,9/4)Z1=21X（2）=(3,1)Z2=22原IP的最優(yōu)解原IP的松弛問(wèn)題L0：

松弛問(wèn)題的最優(yōu)解為：x（0）=(5/2,2)T,Z0=23x12x13L0：z0=23x1=2.5，x2=2L1：z1=21L2：z2=22x1=2，x2=2.25x1=3，x2=1x1≤2x1≥3取原IP的最優(yōu)解為舍松弛問(wèn)題：

當(dāng)存在若干變量有取整約束時(shí)，分枝既廣且深，在最壞的情況下相當(dāng)于組合所有可能的整數(shù)解。一般整數(shù)規(guī)劃問(wèn)題屬于一類未解決的難題，稱為NP-complete，只有少數(shù)特殊問(wèn)題有好的算法，例如分配問(wèn)題。

注意：

例求解下列整數(shù)線性規(guī)劃。解：其松弛問(wèn)題為24624(3.25,2.5)x1x22x1+3x2=142x1+x2=9松弛問(wèn)題的最優(yōu)解松弛問(wèn)題：選x2=2.5分枝，引入條件x2≤2,x2≥3,得到兩個(gè)子問(wèn)題：24624(3.25,2.5)x1x22x1+3x2=142x1+x2=9松弛問(wèn)題的最優(yōu)解AB點(diǎn)A（3.5,2）為L(zhǎng)1的最優(yōu)解，此時(shí)z=14.5點(diǎn)B（2.5,3）為L(zhǎng)2的最優(yōu)解，此時(shí)z=13.5都不是原IP的可行解，取邊界值較大的z=14.5，對(duì)x1=3.5繼續(xù)分枝。選x1分枝，引入條件x1≤3,x1≥4,得到兩個(gè)子問(wèn)題：24624(3.25,2.5)x1x22x1+3x2=142x1+x2=9松弛問(wèn)題的最優(yōu)解AB點(diǎn)C（3,2）為L(zhǎng)11的最優(yōu)解，此時(shí)z=13點(diǎn)D（4,1）為L(zhǎng)12的最優(yōu)解，此時(shí)z=14都是原IP的可行解，取邊界值較大的z=14，開(kāi)始剪枝。CDL0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L11：z3=13L12：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥4舍舍取綜上，原IP的最優(yōu)解為L(zhǎng)0：z0=14.75x1=3.25，x2=2.5L1：z1=43/3L2：z2=14L11：z3=13L12：z4=38/3x1=3，x2=8/3x1=4，x2=1x1=3，x2=2x1=2，x2=10/3x1≤3x1≥4x2≤2x2≥3舍舍取綜上，原IP的最優(yōu)解為本例也可以先對(duì)x1=3.25分枝：例用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題記為（LP）用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對(duì)于x1＝18/11≈1.64，取約束條件x1≤1，x1≥2將（IP）劃分為（IP1）和（IP2）相應(yīng)的，將（LP）劃分為（LP1）和（LP2）x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。即有：

下面求（LP1）和（LP2）的最優(yōu)解。x1x2⑴⑵33(18/11,40/11)⑶

先求（LP1）,如圖所示。此時(shí)B

在點(diǎn)取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。11再求（LP2）

,如圖所示。在C

點(diǎn)取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原問(wèn)題有比（－16）更小的最優(yōu)解，但x2不是整數(shù)，故利用

3≤10/3≤4

加入條件。BAC加入條件：x2≤3,x2≥4有下式：下面求（LP3）和（LP4）的最優(yōu)解。x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所示。此時(shí)D在點(diǎn)取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即2≤x1≤3。D再求（LP4），如圖所示。無(wú)可行解，不再分枝。

在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件x1≤2，x1≥3有：再求（LP5）和（LP6）的最優(yōu)解。x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時(shí)E

在點(diǎn)取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。E求（LP6），如圖所示。此時(shí)F在點(diǎn)取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F

如對(duì)Z(6)

繼續(xù)分解，其最小值也不會(huì)低于－15.5，問(wèn)題探明,剪枝。

至此，原問(wèn)題（IP）的最優(yōu)解為：

x1=2，

x2=3,

Z*=Z(5)=－17以上的求解