整数规划(运筹学)

第

3

章Integer

ProgrammingI

P整数规划3.1整数规划问题及其建模3.2分支定界法3.3割平面法3.40-1型整数线性规划的解法3.5指派问题第3章整数规划第3章整数规划2基本概念整数规划：变量取整数的线性规划；纯整数规划：所有变量都取整数的线性规划；混合整数规划：部分变量取整数的线性规划；0-1规划：所有变量都取0、1两个值的规划；0-1混合规划：部分变量取0、1两个值的规划。1、0-1变量的应用

例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制3.1

整数规划问题及其建模

例2：上述例题中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：∑djxjf采用自备柴油机发电：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正数例3：若在开采时还需满足下述条件：（a）若开采8号，则必须同时开采6号；（b）若开采5号，则不许开采3号；（c）2号和4号至少开采一个；（d）8号与7号必须同时开采；（e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。（a）当x8=1x6=1，x6≠0当x8=0x6=1，x6=0∴x8

x6

（b）当x5=1x3=0，x3≠1当x5=0x3=0，x3=1∴

x5+x3

1（c）x2+x4

1（d）x8=x7（e）x1+x4+x6+x9

2例4：两组条件满足其中一组若x14，则x21，否则(x14)，则x23。设yi=10第i组条件起作用第i组条件不起作用则i=1,2x14＋(1-y1)Mx21－(1-y1)MM——充分大正数x14－(1-y2)Mx23＋(1-y2)My1＋y2=1y1，y2=0或1例3-1考虑固定成本的最小生产费用问题

在最小成本问题中，设第j种设备的固定成本为

，运行的变动成本为

，则生产成本与设备运行时间的关系为：设第j种设备运行每小时可以生产第i种产品

件，而第i种产品的定货为

件。要满足定货同时使设备运行的总成本最小的问题为：9混合0-1规划线性规划与整数规划的关系10线性规划整数规划X*=（13/5，19/5）Z*=89/5=17.8X*=（5，3）Z*=17一、引例

某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙2 2 33 1 214 米3 9吨托运限制3.2分支定界法建模：解：设托运甲货物x1箱，乙货物x2箱Maxz=3x1+2x2 2x1+3x214 2x1+x29 x10，x20，且为整数24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=624624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)24624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)分枝定界法:L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥4基本思想分支（Branch）定界（Bound）3.2分支定界法（B&B）第3章整数规划xr≤Irxr≥Ir+1例3-2

用分枝定界法求解以下整数规划先求得相应的线性规划的最优解，为3.2分支定界法（B&B）第3章整数规划1819Sub-6无可行解原问题Sub-2Sub-1Sub-3Sub-4Sub-5Sub-7Sub-9Sub-8Sub-10无可行解x2≤2x2≥3x1≤5x1≥5x2≤1x2≥2x1≤4x1≥6x2≤0x2≥1图3-3.探索过程示意图×√√3.3.1割平面法基本思想3.3

割平面法第3章整数规划20设放弃变量整数要求得到的线性规划的最优单纯形表如下：设其中基变量Xr的值br不是整数，以I表示整数，以F表示正的真分数，令yrj=Irj+

Frj(0≤

Frj<1)

br=Ir+Fr

(0<

Fi

<1)将上面两式代入约束r中，得3.3

割平面法第6章整数规划21改写成因此对于整数可行解，约束（3-2）可以写成更严格的不等式这就是源于第r行的割平面。

⑴线性规划的任何整数可行解都满足这个约束；未切割掉任何一个整数解。

⑵线性规划的非整数最优解不满足这个约束。切割掉了非整的LP解X；(3-4)3.3

割平面法第3章整数规划22

2°

若Xk的分量全为整数，则Xk即为原问题的最优解，停止计算；

否则根据Xk的一个非整分量所在单纯形表的那一行，譬如第i行，构造源于第

i行的割平面(3-4)

，并给它引入一个弛变量xn+k+1，得Frjxj+

xn+k+1

=-Frj=m+1

-

3°

把这个新约束添到最优单纯形表的倒第2行，并增加一列(即

xn+k+1列)，用对偶单纯形法继续迭代，求得一个新解Xk+1，令k:=k+1，返2°。

3.3.2割平面法基本步骤

1°

用单纯形法求解IP的伴随LP问题，得到其解X0，令k=0；n3.3

割平面法第6章整数规划23

minz=3x1+4x23x1+x2≥4x1+2x2≥4

x1,

x2≥0

x1,

x2为整数s.t.例3-3

试用割平面法求解以下整数规划：解求解线性规划得最优单纯形表选择一个非整数的基变量，例如x2=8/5，构造约束条件(3-4）3.3割平面法第3章整数规划24用对偶单纯形法，x5离基，x3进基，已获得整数的最优解：X*=（2，1）Z*=10第6章整数规划25

maxz=

x1+x22x1+x2≤54x1-x2≥2

x1,

x2≥0

x1,

x2为整数s.t.

maxz=

x1+x2

2x1+x2+x3=5

-4x1+x2+x4

=

-2

x1,

x2,x3,

x4≥

0s.t.例:

试用割平面法求解：解

标准化并获取排列阵：第6章整数规划26

cj

基

解

x1

x2x3

x4

1

1

00序号

2

110x3x4

5-2

-

4

1

0100

0

1

1

00-

4

4

0

3/2

1

1/2x3x1

01

1/21

-1/4

0-1/4

1/2

0

5/4

0

1/43/211

x2x17/6

1

0

1/6

-1/6

8/3

0

1

2/3

1/323/60

0

-5/6

-1/6(a)(b)(c)

源于第一行构造割平面：-

(x3+

x4)≤0232313

-

x3-

x4+

x5=

-232313①等价于x2

≤2

2

00

21

-3110

3/2101/2

0-1/2x2x1x4(b)cj

基

解

x1

x2x3

x4x5

1

1

00

0序号

x2x1x5

23/6

0

0

5/6

1/6

0-2/30

0-2/3

-1/31-1/3110

7/61

0

1/6-1/6

0

8/30

1

2/3

1/3

0(a)

2

01

001

7/2

00

1/2

0

1/2第6章整数规划28源于第二行构造割平面：-

(x3+

x5)≤0121212

-

x3-

x5+

x6=

-121212X1*=

(1,2)TX2*=

(2,1)Tz*

=

3②

等价于

x1+x2

≤3cj

基

解

x1x2

x3x4x5

x63

5

00

0

0

0

1

0

0

1

0x2x1

x4

x6

23/2

2

1

01/2

0

-1/2

01100

0

0

2

1

-3

07/2

0

01/2

0

1/2

0-1/2

0

0-1/2

0-1/2

1-1/2x2x1

x4

x3

1

0

0

1

0

1-2

0

0

0

0

1

-5

4

1

1

0

0

0

-1

1

2

0

1

0

0

10

3

0

0

0

0

01110010

11

22x1x2A(7/6,8/3)①x2

≤

2B(1,2)C(3/2,2)②x1

+

x2

≤

3

11

22x1x2B(1,2)C(3/2,2)D(2,1)隐枚举法（ImplicitEumeration）例3-4用隐枚举法求解下列问题

④③①②可行解：X=(1，0，0)，Z=3

增加过滤条件（filteringconstraint）

◎3.40-1型整数规划的解法第3章整数规划303.40-1型整数规划的解法第3章整数规划313.5指派问题及匈牙利算法(AssignmentProblem)一、问题的提出和数学模型例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139建立模型：设xij=10译英文：x11+x12+x13+x14=1译日文：x21+x22+x23+x24=1译德文：x31+x32+x33+x34=1译俄文：x41+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 (aij---效率)i=1j=144若第i项工作交与第j个人完成若第i项工作不交与第j个人完成分配问题一般数学模型结构：

设有m项工作要交与m个人完成，其中第i项工作交与第j个人完成时所需花费的时间为

aij。规定每项工作只能交与其中的一个人完成，而每个人只能完成其中的一项工作。问：如何分配，可使所需的总时间最少？Minz=aijxijst.xij=1xij=1i=1j=1j=1i=1mmmmxij=0或1(i=1,2,···,m;j=1,2,···,m)(i=1,2,···,m)(j=1,2,···,m)二、匈牙利法：基本思想：(0)564(0)563(0)(0)562

克尼格定理(konig)：如果从效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui,从每列中分别减去(或加上)一个常数vj,得到一个新的效率矩阵[bij],其中bij=aij-ui-vj,则以[bij]为效率矩阵的最优解等价于以[aij]为效率矩阵的最优解.证明:以[aij]为效率矩阵的目标函数值：z0=aijxij以[bij]为效率矩阵的目标函数值：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-constantmmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1mm三、步骤⑴使每行、每列都出现0元素方法：每行减该行最小元素；2109715414813141611415139-2-4-11-4min0875110104235001195min-0-0-5-0082511054230001145-2-2 -2+2+2080311032450001123每列减该列最小元素。⑵寻找位于不同行不同列的0元素准则：A）从第一行开始，若只有一个0，则记（0），同时作直线覆盖该列的元素。否则，转下行；B）从第一列开始，若只有一个0，则记（0），同时作直线覆盖该行的元素。否则，转下列；C）重复A）、B），至再找不出这样的0元素，转D）D）可能出现三种情况： ①每行均有（0）元素，则在有（0）位置构成最优解中xij=1； ②多于两行和两列存在未被直线覆盖的0元素，即存在0元素的闭回路，则沿回路顶点每间隔一个0记（），同时作直线覆盖该列的元素；③所有0元素均有直线覆盖，但记（0）的个数<m个，转⑶。000000⑶迭代，寻找新的位于不同行不同列的0元素a）从未被直线覆盖的元素中找出一个最小的元素amin； b）对行，若无直线覆盖，则-amin；