第八章 整数规划

第八章

整数规划1整数规划问题线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(IntegerProgramming)。全部决策变量的取值都为整数，则称为全整数规划(AllIP)；仅要求部分决策变量的取值为整数，则称为混合整数规划(MixedIP)；要求决策变量只能取0或1值，则称为0-1规划(0-1rogramming)。

2整数规划问题为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。“舍入化整”一般是不可行的：化整后的解有可能成为非可行解；虽是可行解，却不是最优解。例如一、问题的提出

产品资源甲乙现有量A219B5735单台利润63

问如何安排甲、乙两产品的产量，使利润为最大。3整数规划问题解：设x1为甲产品的台数，x2为乙产品的台数。maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。不考虑整数约束的最优解：x1

*=28/9=3.111，

x2

*

=25/9=2.778，Z

*

=293/9=32.556舍入化整x1=3，x2=3，Z=33，不满足约束条件5x1+7x2≤35，非可行解；x1=3，x2=2，Z=28，满足约束条件，是可行解，但不是最优解；x1=4，x2=1，Z=29，满足约束条件，才是最优解。45x1+7x2=352x1+x2=9•(3,3)••••••••••第一节、整数规划的图解法

x1x21231253445步骤：在线性规划的可行域内列出所有决策变量可能取的整数值，求出这些变量所有可行的整数解，比较它们相应的目标函数值，最优的目标函数值所对应的解就是整数规划的最优解。实用性：只有两个决策变量，可行的整数解较少。

第一节、整数规划的图解法

二、整数规划的图解法

6例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140

第一节、整数规划的图解法甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。解：设x1、

x2分别为甲、乙两种货物托运的件数，建立模型目标函数：Maxz=2x1+3x2

约束条件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0为整数。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，7得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目标函数值为14。性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=6第一节、整数规划的图解法••••••••••8例2：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3x1,x2,x3≥0为整数例3：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3

为整数

x3

为0-1变量用《管理运筹学》软件求解得：

x1=5x2=2x3=2用《管理运筹学》软件求解得：

x1=4x2=1.25x3=1z=16.25第二节、整数规划的计算机求解9第三节、整数规划的应用

例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj

(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：

在东区由A1

，A2

，A3三个点至多选择两个；在西区由A4

，A5两个点中至少选一个；在南区由A6

，A7两个点中至少选一个；在北区由A8

，A9

，A10

三个点中至少选两个。一、投资场所的选择Aj

各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见下表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?10解：设：0--1变量xi=1(Ai点被选用）或0(Ai点没被选用）。这样我们可建立如下的数学模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

xj≥0

xj

为0--1变量，i=1,2,3,……,10第三节、整数规划的应用11Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2

xj≥0

xj

为0--1变量，i=1,2,3,……,10最优解：x1=1,x2=1,x3=0,

x4=0,x5=1,

x6=1,

x7=0,x8=0,x9=1,

x10=1最大利润245万元。即在A1,A2,A5,A6,A9,A10

等6个地点建立销售门市部。实际投资额为100+120+70+90+160+180=720第三节、整数规划的应用12例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器有100台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。二、固定成本问题第三节、整数规划的应用13解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）引入约束xi≤Myi

，i=1，2，3，M充分大，以保证当yi

=0时，xi=0。这样我们可建立如下的数学模型：

Maxz=4x1+5x2+6x3-100y1-150y2-200y3

s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi

，i=1，2，3，M充分大

xj≥0xj∈N

yj

为0--1变量，i=1,2,3第三节、整数规划的应用14例6．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如表所示，问应如何指派工作，才能使总的消耗时间为最少。三、指派问题:有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。第三节、整数规划的应用15解：引入0—1变量xij，并令xij

=1(当指派第i人去完成第j项工作时)或0（当不指派第i人去完成第j项工作时)．这可以表示为一个0--1整数规划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.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(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)

x13+x23+x33+x43=1(C工作只能一人干)

x14+x24+x34+x44=1(D工作只能一人干)

xij

∈N为0--1变量，i,j

=1,2,3,4

***求解可用《管理运筹学》软件中整数规划方法。

第三节、整数规划的应用16

对于有m

个人，n项任务的一般指派问题，设：第三节、整数规划的应用并设：cij

为第i人去完成第n项任务的成本（如时间、费用等）则一般指派问题的模型可以写为：约束条件：xij为0-1变量，对所有的i和j.17因为m不一定等于n，当m>n，即人数多于任务数时，就有人没有任务，所以前面个约束条件都是“小于等于1”，这是说每个人至多承担一项任务，而后面n个约束条件说明每项工作正好有一人承担，所以都是“等于1”.当n>m时，需要设假想的n-m个人便获得可行解.第三节、整数规划的应用18第三节、整数规划的应用还有一种指派问题叫做多重指派问题，它于一般的指派问题的区别在于：一般的指派问题中每个人至多承担一项任务，而多重指派问题中一个人可以根据自己能力的大小承担一项、两项或更多项的任务.这时约束条件中的前个条件不是而是改为其中ai是第i个人至多承担的任务的数，对于不同的i

，ai可以是不一样的.19四、分布系统设计

例7．某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。（1）

问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?

（2）

如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?第三节、整数规划的应用20解：

a)

设xij为从Ai运往Bj

的运输量(单位千箱)，yi

=1(当Ai被选中时)或0（当Ai没被选中时)．这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。

s.t.x11+x12+x13≤30(A1

厂的产量限制)

x21+x22+x23≤10y2(A2

厂的产量限制)

x31+x32+x33≤20y3(A3

厂的产量限制)

x41+x42+x43≤30y4(A4

厂的产量限制)

x51+x52+x53≤40y5(A5

厂的产量限制)

x11+x21+x31+x41+x51=30(B1

销地的限制)

x12+x22+x32+x42+x52=20(B2

销地的限制)

x13+x23+x33+x43+x53=20(B3

销地的限制)

xij≥0xj∈N

，yi为0--1变量，i=1,2,3,4,5；j=1,2,3

***求解可用《管理运筹学》软件中整数规划方法。

第三节、整数规划的应用21b)

如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?

解：

设xij为从Ai运往Bj

的运输量(单位千箱)，yi=1(当Ai

被选中时)或0（当Ai

没被选中时)．这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。

s.t.x11+x12+x13≤30(A1

厂的产量限制)

x21+x22+x23≤10y2(A2

厂的产量限制)

x31+x32+x33≤20y3(A3

厂的产量限制)

x41+x42+x43≤30y4(A4

厂的产量限制)

x51+x52+x53≤40y5(A5

厂的产量限制)

x11+x21+x31+x41+x51=30(B1

销地的限制)

x12+x22+x32+x42+x52=20(B2

销地的限制)

x13+x23+x33+x43+x53=20(B3

销地的限制)

y2+y3=1(必须在A2，A3地建一个厂)

xij≥0yi为0--1变量，i=1,2,3,4,5；j=1,2,322五、投资问题例8．某公司在今后五年内考虑给以下的项目投资。已知：

项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；

项目B：第三年初需要投资，到第五年未能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；

项目C：第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。

项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?第三节、整数规划的应用23解：1)设xiA、xiB、xiC、xiD(i

＝1，2，3，4，5)分别表示第

i

年年初给项目A，B，C，D的投资额；设y1A，y3B，是0—1变量，并规定:

第三节、整数规划的应用设y2C

是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第2年投资C项目6万元时，取值为3；第2年投资C项目4万元时，取值为2；第2年投资C项目2万元时，取值为1；第2年不投资C项目时，取值为0；

24这样我们建立如下的决策变量：

第1年第2年第3年第4年第5年

Ax1A

x2A

x3A

x4A

B

x3B

C

x2C(=20000y2C)

D

x1D

x2D

x3D

x4D

x5D

第三节、整数规划的应用252）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是x1A+x1D=100000；第二年：A次年末才可收回投资,故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的资金为1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的资金为1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D；第三节、整数规划的应用26关于项目A的投资额规定:x1A≥40000y1A

，x1A≤200000y1A

，200000是足够大的数；保证当

y1A=0时，x1A=0；当y1A=1时，x1A≥40000。关于项目B的投资额规定:x3B≥30000y3B

，x3B≤50000y3B

；保证当

y3B=0时，x3B=0；当y3B=1时，50000≥

x3B≥30000。关于项目C的投资额规定:x2C=20000y2C

，y2C=0，1，2，3，4。第三节、整数规划的应用273）目标函数及模型：

Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5D

s.t.x1A+x1D=100000；

x2A+x2C+x2D=1.06x1D；

x3A+x3B+x3D=1.15x1A+1.06x2D；

x4A+x4D=1.15x2A+1.06x3D；

x5D=1.15x3A+1.06x4D；

x1A≥40000y1A

，

x1A≤200000y1A

，

x3B≥30000y3B

，

x3B≤50000y3B

；

x2C=20000y2C

，

y1A，y3B=0或1，y2C=0，1，2，3，4xiA

，xiB

，xiC

，xiD≥0(i=1、2、3、4、5）第三节、整数规划的应用28第四节分枝定界法分枝定界法(BranchandBoundMethod)基本思想：先求出整数规划相应的LP(即不考虑整数限制)的最优解，若求得的最优解符合整数要求，则是原IP的最优解；若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。

29第四节分枝定界法定界的含义：整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；对极小化问题来说，相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。30第四节分枝定界法例maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解：

x1=28/9，x2=25/9，Z1=293/9第二步,定界过程这个解不满足整数约束，这时目标函值Z1是整数规划的目标上界；因为x1=x2=0是整数规划问题的可行解，所以下界为0。第三步,分枝过程将不满足整数约束的变量x1进行分枝，x1称为分枝变量，构造两个新的约束条件：

x1≤[28/9]=3，x1≥[28/9]+1=4

31第四节分枝定界法这样就把相应的线性规划的可行域分成两个部分，如图所示。••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4问题2：maxZ=

6x1+5x2问题3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数32第四节分枝定界法求解相应的线性规划的最优解问题2相应的线性规划的最优解：x1=3，x2=20/7，Z2=226/7问题3相应的线性规划的最优解：x1=4，x2=1，Z3=29第四步，定界过程LP3的解满足整数约束，不必再分枝，它的目标函数值是29，大于原有下界0，则新的下界为29；现有上界为未分枝子问题中目标函数最大值，即为226/7。LP2的解仍不满足整数约束的要求，它的目标函数值226/7大于现有下界，则应继续分枝。第五步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：

x2≤[20/7]=2，x2≥[20/7]+1=3

33••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3第四节分枝定界法问题4：maxZ=

6x1+5x2问题5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=334第四节分枝定界法求解相应的线性规划的最优解问题4相应的线性规划的最优解：

x1=3，x2=2，Z4=28问题5相应的线性规划的最优解：x1=14/5，x2=3，Z5=159/5第六步，定界过程LP4的解满足整数约束，不必再分枝，它的目标函数值是28，小于原有下界29，则下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为159/5。LP5的解仍不满足整数约束的要求，它的目标函数值159/5大于现有下界29，则应继续分枝。第七步，分枝过程将不满足整数约束的变量x1进行分枝，构造两个新的约束条件：

x1≤[14/5]=2，x1≥[14/5]+1=3

35第四节分枝定界法问题6：maxZ=

6x1+5x2问题7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=3••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=236第四节分枝定界法求解相应的线性规划的最优解：问题6相应的线性规划的最优解：

x1=2，x2=25/7，Z6=209/7问题7相应的线性规划的最优解：无最优解第八步，定界过程LP7的无最优解，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为209/7。LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于现有下界29，则应继续分枝。第九步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：

x2≤3，x2≥4

37第四节分枝定界法问题8：maxZ=

6x1+5x2问题9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

x2=438第四节分枝定界法求解相应的线性规划的最优解问题8相应的线性规划的最优解：

x1=2，x2=3，Z8=27问题9相应的线性规划的最优解：x1=7/5，x2=4，Z9=142/5第十步，定界过程LP8的最优解，满足整数约束，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为29。虽然LP9的解仍不满足整数约束的要求，它的目标函数值142/5小于现有下界29，则不再继续分枝。上界=下界，得整数规划问题的最优解：x1=4，x2=1，Z=2939分枝定界过程x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥4第四节分枝定界法40

整数规划的分枝定界法步骤

从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B：

第一步：求解问题B，可得以下情况之一：

1.B没有可行解，则A也没有可行解，求解过程停止。

2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。

3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。

第二步：确定A的最优目标函数值z*的上下界，其上界即为

=z1,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。

第三步：判断

是否等于z

。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。41整数规划的分枝定界法步骤

第四步：在B的最优解中选一个最远离整数要求的变量，不妨设此变量为xj=bj，以[bj]表示小于bj的最大整数，构造以下两个约束条件，并加入问题B，得到B的两个分枝B1和B2。xj≤[bj]和xj≥[bj]+1

第五步：求解B1和B2

。修改A问题的最优目标函数值z*的上下界，

和z。

第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打Х表示），即以后不再考虑了。若大于z

，则不符合整数条件，则重复第三步至第六步，直至

，求出最优解为止。对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。42§4整数规划的分枝定界法例9用分枝定界法求解整数规划Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1,x2≥0且x1,x2为整