所有分类05整数规划2

第五章整数规划整数规划分类：全整数规划（纯整数规划）—所有变量均取整部分整数规划（混合整数规划）—部分变量取整0—1整数规划—变量的取值为0或1例1：集装箱运货：货物体积m3/箱重量百公斤/箱利润千元/箱甲5220乙4510货运限制2413一、整数规划数学模型：数学模型：Maxz=20X1+10X25X1+4X2≤242X1+5X2≤13X1，X2≥0X1，X2为整数二、整数规划的解法：LP问题可行域为四边形OABC，是凸集ILP问题可行域为四边形OABC中整数解常用方法：分枝定界法、割平面法、隐枚举法例1数学模型：Maxz=20X1+10X25X1+4X2≤242X1+5X2≤13X1，X2≥0X1，X2为整数例1：线性规划问题最优解X=（4.8，0）；Z=96，该解为非整数最优解若X=（4，0），Z=80；若X=（5，0），Z=100为非可行解其整数规划问题最优解X=（4，1）；Z=90X2﹢﹢﹢﹢﹢﹢﹢X1OABC﹢﹢﹢﹢123412第二节分枝定界法设整数规划问题（记为A）该整数规划相应的线性规划（松弛问题记为B）：其最优解为：分枝定界法步骤：1.先不考虑整数约束条件，求相应的线性规划最优解，若最优解的所有分量都为整数，则已经得到原整数规划问题的最优解,停止。否则，进行分枝、定界2.进行分枝、定界分枝:增加约束条件，将LP问题B的可行域分成若干子区域（子问题）定界：松弛问题最优解一定是整数规划问题最优解目标函数值的上限；已得到的整数解的目标函数是整数规划最优解目标函数值的下限。

上界：下界：分枝方法：在相应线性规划非整数最优解中取某一非整数分量Xj，构造两个约束条件，形成两个子线性规划问题。设令[bj]表示小于bj的最大整数，则可构造两个新的约束条件为：将这两个约束条件分别加入到相应线性规划问题B中，得到两个子问题B1，B2。B1为：

B2为：例一：用分枝定界法求解

Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0

X1，X2为整数问题(1)Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0步骤：1、先解松弛问题x*=

4.8091.817Z*=355.89(A点)2、分枝定界①定界：0≤Z≤355.89②选X1分枝

问题（2）(1)

X1≤4问题（3）(1)

X1≥5（3）45ABC（2）注：4<

X1<

5的中间区域不包含X1为整数的解,去掉,保留两边的子区域,构成两个子问题B1，B23.对B1及B2仍不考虑整数约束条件，分别进行求解，进一步修正上下界。为B1，B2最优解中较大的目标函数值为符合整数条件的整数解中最大目标函数值，否则为零4.剪枝对于子问题的最优目标函数值小于下界的，可剪去。对于子问题最优目标函数值大于下界的，而又没有得到整数解，可继续分枝，直到得到整数规划问题的最优解或者判定原问题无最优解。问题(1)

Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0步骤：1、解松弛问题(1)x*=

4.8091.817Z*=355.89(A点)2、分枝定界①定界：0≤Z≤355.89②选X1分枝

问题（2）

(1)

X1≤4问题（3）(1)

X1≥5最优解为x*=(4,2.1)Z*=349（B点）最优解为x*=(5,1.57)Z*=341.39（C点）3、选（2）继续分枝定界：0≤Z≤349问题（5）(2)

X2≥3问题（4）(2)

X2≤2上例:A（4.81，1.82）Z=355.89B（4，2.1)，Z=349C（5，1.57），Z=341.3945ABC问题(1)

Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0(1)

Z=0

4.809355.89

1.817

X1≤4X1≥5

(2)

Z=0

4349

2.1

(3)

Z=0

5

341.39

1.571

X2≤2X2≥3

(4)

Z=0

4340

2

(5)

Z=340

1.428

327.12

3

X2≤1X2≥2×剪枝

(6)

Z=340

5.444

307.76

1

×剪枝

(7)

Z=340

无解

分枝定界一般步骤：1.先解（A）的松弛问题（B）（B）的解有下列三种情况①（B）无可行解→（A）无可行解②（B）的最优解符合（A）的要求，停；③（B）的最优解不符合（A）的要求，其目标值作为上限ZO2.用观察法找（A）的一个整数可行解；一般取xj=0，j=1，2，3，…n，其目标函数值作为整数最优解目标值的下界，记z3.选（B）解中不符合整数要求的分量xj（xj=bj）分枝，作（B）的后续问题（C）、（D）（C）：（B）加约束xj≤[bj]

（D）：（B）加约束xj≥[bj]+1剪枝条件①（C）（D）无可行解②（C）（D）对应的目标值

≤

z

③（C）（D）对应的目标值zc

≧

z

且解为整数解，令

zc

=

z

且解为非整数解，令（C）（D）取代（B）返回（4）4.全部枝剪完3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例二、用分枝定界法求解整数规划问题（单纯形法）

x1=13/4

x2=5/2Z(0)=59/4≈14.75

选x2进行分枝，即增加两个约束，2≥x2≥3有下式：分别在(LP1)和(LP2)中引入松弛变量x5和x6

，将新加约束条件加入上表计算。即x2+x5=2,－x2+x6=－3

得下表:32000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2

-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2

Z(1)=29/2=14.5继续分枝，加入约束

3≥x1≥4LP132000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵

Z(2)<Z(1)∴先不考虑分枝接(LP1)继续分枝，加入约束4≤x1≤3，有下式：分别引入松弛变量x7和x8，然后进行计算。CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3

x1=3,x2=2

Z(3)=13找到整数解，问题已探明，停止计算。LP3CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1

x1=4,x2=1

Z(4)=14找到整数解，问题已探明，停止计算。LP4树形图如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)＝13LP4x1=4,x2=1Z(4)＝14x2≤2x2≥3x1≤3x1≥4＃＃＃割平面法◆用于解决纯整数规划问题计算步骤：1.用单纯形法求解(

IP)对应的松弛问题(LP)：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。

⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。

⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。例:Maxz=X1+X2﹣X1+X2≤13X1+X2≤4X1,X2≧0且为整数

松弛问题:

Maxz=X1+X2

﹣X1+X2≤1

3X1+X2≤4X1,X2≧0先求松弛问题最优解最终表见右表XbbX1

X2X3X4X13/410﹣1/41/4X27/4013/41/4

00﹣1/2﹣1/22.增加约束条件切割松弛问题可行域。从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数和右端常数分解为整数和非负真分数之和，建立割平面方程。若选X1，写出X1在最终表中对应的方程

X1﹣1/4X3+1/4X4=3/4XbbX1

X2

X3X4X13/410﹣1/41/4X27/4013/41/4

00﹣1/2﹣1/2

◆割平面求法:X1在最终表中对应的方程

X1﹣1/4X3+1/4X4=3/4

将所有变量系数及右端常数表示成整数和小数（或非负真分数）之和X1+（﹣1+3/4）X3+1/4X4=3/4

将整数及整数系数的变量移至左侧，其余在右侧

X1﹣X3=3/4﹣(3/4X3+1/4X4)

若所有变量均取整数，则3/4﹣(3/4X3+1/4X4)≤0﹣3/4X3﹣

1/4X4≤﹣3/4

割平面方程即：﹣3X3﹣X4≤

﹣3

化标准型﹣3X3﹣X4+X5=

﹣33、把新增约束加到原整数规划问题中，仍不考虑整数约束条件，求相应松弛问题最优解。

11000XB

bX1X2

X3

X4

X5X1X2X53/47/4﹣3

10﹣1/41/40

013/41/40

00

﹣3*﹣1100﹣1/2﹣1/20X1X2

X31

11

1001/31/1201001/4001-1-1/3000

-1/3-1/6割平面方程的几何意义：割平面方程

-3/4X3-1/4X4≤-3/4

即-3X3-X4≤-3，将X3、X4用X1、X2表示-3（1+X1-X2）-（4-3X1–X2）≤-3即X2≤1∵∵∵∵∵∵∵∵∵∵∵∵。11（3/4，7/4）X2X1∷松弛问题:

Maxz=X1+X2

﹣X1+X2≤1

3X1+X2≤4X1,X2≧0例二：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6初始表最优表在松弛问题最优解中，x1,x2

均为非整数解，由上表有：将系数和常数都分解成整数和非负真分数之和以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：引入松弛变量s1后得到下式，将此约束条件加到上表中，继续求解。Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/60Cj11000CBXBbx1x2x3x4s11x10100－101x240101－20x320011－3－Z－40000－1/2﹡得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。

割平面求法：设松弛问题的最优解X*=（X1，X2，……Xn，Y1，Y2，……Yn）基变量X1，X2，……Xn；非基变量Y1，Y2，……YnXi不是整数Xi+∑aijyj

=bi（诱导方程）①——bi=bi+βibi、

aij为整数

aij

=aij

+αij0

＜

βi＜1

、0＜

αij

＜1～～～～——①式变为

Xi

+∑aijyj

–bi=βi—∑αijyj②～～且βi—∑αijyj

≤0加松弛变量Si（整数

）

βi—∑αijyj+

Si=0③——割平面方程③式满足（1）没有割去原来的整数解（2）割去了非整数最优解小结（1）适宜中小型问题，也可解混合整数规划问题（2）收敛较慢，舍入误差大（3）割平面取法不唯一LP1x1=1,x2=7/3Z(1)＝10/3LPx1=3/2,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)＝3LP6无可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)＝61/14LP4无可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤2x1≥3＃＃作业0—1整数规划问题例2：背包问题：背包可装8公斤重量、10单位体积物品物品名称重量体积价值1书52202摄象机31303饮料14104食品23185衣服4515Maxz=20X1+30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X5≤82X1+X2+4X3+3X4+5X5≤10Xi=0或1数学模型：设Xi表示是否带第I种物品，Xi=0或1i=1，2，3，4，5）Xi=0表示不带第i种物品；

Xi=1表示带第i

种物品0—1决策变量可应用于相互排斥的计划中例3：若例一运输方式为火车或船火车：5X1+4X2≦

24（体积）船：7X1+3X2≦45

（体积）

X3=0时用火车；

X3=1用船2X1+5X2≤135X1+4X2≤24+MX37X1+3X2≤45+M（1-X3）X1X2≧0且为整数；X3=0或1；M＞0例一数学模型：Maxz=20X1+10X25X1+4X2≤242X1+5X2≤13X1，X2≥0X1，X2为整数增加0——1变量

X3,当例4：选址问题：B3B4B2A3B1A2A1Ai可建仓库地点、容量为ai

，投资费bi，建2个；Bj商店，需求dj

,

j=1，2，3，4Cij

仓库i到仓库j单位运费要求选择适当地点建仓库，在满足商店需求条件下，总费用最小设Xi表示是否在Ai

建仓库，

Xi=1建，Xi=0不建Yij表示从i仓库到j商店运量Minz=∑biXi+∑∑CijYij∑Xi=2

Y11+Y21=d1

Y12+Y22+Y32=d2

Y23+Y33=d3

Y14+Y24+Y34=d4Y11+Y12+Y14≤a1X1Y21+Y22+Y23+Y24≤a2X2Y32+Y33+Y34≤a3X3Xi为0或1，Yij≥0

隐枚举法用于解决0——1规划问题步骤1）用试探法求出一可行解，其目标值作为当前最好值ZO2）增加过滤条件Z≥ZO

3）将Xj按Cj由小到大排列观察得解（X1，X2，X3）=（1，0，0）Z0=3

过滤条件3X1-2X2+5X3≥3

将（X1，X2，X3）→（X2，X1，X3）（X2，X1，X3）目标值

Z0①②③④当前最大值0000＜0015＞√√√√50103

＜0118＞√√√√8100-2＜1

013

＜11

01＜1116＜最优解为（1，0，1）maxz=3X1-2X2+5X3

X1+2X2-

X3≤2

X1+4

X2+

X3≤4X1+

X2≤3

4

X2+

X3

≤6X1，X2，X3等于0或1一、数学模型；例：有一份中文说明书需翻译成英、日、德、俄四种文字，有甲乙丙丁四人，他们将中文说明书翻译成不同语种需要的时间如表所示，问派何人完成何工作，使所需总时间指派问题

EJGR甲215134乙1041415丙9141613丁78119EJGR甲215134乙1041415丙9141613丁78119Minz=2X11+15X12+13X13+4X14

+10X21+4X22+14X23+15X24+9X31+14X32+…+9X44

引入变量Xij=数学模型：1表示第I人完成第j项工作0表示第I人不完成第j项工作每人只做一项工作X11+X12+X13+X14=1X21+X22+X23+X24=1X31+X32+X33+X34=1X41+X42+X43+X44=1Xij=1或0每项工作由一人来做

X11+

X21+

X31+

X41=1X12+

X22+

X32+

X42=1X13+

X23+

X33+

X43=1X14+

X24+

X34+

X44=1一般类型：Minz=∑∑CijXij

匈牙利法求解思想：◆整体最优◆相对比较选优◆系数矩阵的某行某列减去或加上一个常数，不影响分配关系◆为方便求解，选择变换系数矩阵，使每行每列都含有零元素◆位于不同行不同列零元素(独立0元素)的最多个数等于覆盖所有零元素的最小直线数Xij=0或1计算步骤：◆变换系数矩阵使每行每列都含零元素◆最优解判别若覆盖所有零元素的最小直线数等于矩阵行数，（即有n个独立0元素）则可进行最优分配。

令n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，就得到最优解。◆修正系数矩阵所有未被直线覆盖元素减去其中最小数，将此最小数加到交叉位置处◆确定最优方案从含零元素最小的行（或列）先分配①每行减去该行最小元素EJGR01311260101105740142甲乙丙丁②每列减去该列最小元素EJGR甲乙丙丁06001305176300920EJGR甲215134乙1041415丙9141613丁781197630EJGR甲乙丙丁0600130510920EJGR甲乙丙丁06001305176300920④最优分配：甲→R

乙→J

丙→E丁→G解矩阵例：求下表效率矩阵的指派问题最优解A

B

CDE甲乙丙丁戊1279798966671712149152466104107109502022300001057298004063657020243000083501180040414370202430000835011800404143所有未被直线覆盖元素减去其中最小数，将此最小数加到交叉位置处当n较小时可直接观察出覆盖所有零元素的最小直线数，当n较大时，可用标号法确定：用标号法确定覆盖所有零元素的最小直线数方法：（1）行标号有两个以上零的行中的零先不标号有一个零的行中的零先标号，记作◎，该零所在列中其他零划掉，表示此项工作已分配，不再分配给其他人（2）列标号同上（3）重复以上两步直到出现下面三种情况之一：①每行每列都有一个◎的零，则可直接进行分配②并非所有零均已标号，但按（1）、（2）标号无法进行（同行同列至少有两个零元素），则从剩有零元素最小的行或列开始标，比较该行（列）各零元素所在列中零元素的数目，选择零元素小的那列的这个零先加圈，然后划掉同行同列中其他零，反复进行直到所有零元素加圈或划去③所有零均已标号但并非①，则进行（4）（4）在未标◎行右侧标√，在标√的行中找出被化掉的零所在的列，在此列下方打√；在打√的列中找出加圈的零所在的行，在此行右侧打√，重复以上过程，直到无法打√为止50202230000105729800406365√√√（5）对所有打√的列和未打√的行画直线就是覆盖所有零元素的最小直线数。38