韩伯棠管理运筹学(第三版)-第八章-整数规划课件

第八章

整数规划运筹学1第八章

整数规划运筹学1第六章整数规划

§1整数规划的图解法

§2整数规划的计算机求解

§3整数规划的应用*§4整数规划的分枝定界法2第六章整数规划§1整数规划的图整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。整数线性规划(IntegerLinearProgramming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。应用实例：●项目投资问题●工作分配问题●选址问题●背包问题第六章整数规划3整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性根据变量的取值情况，整数线性规划又可以分为纯整数规划（所有变量取整数），混合整数规划（部分变量取整数），0-1整数规划（变量只取0或1）等。求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理就能解决的。整数线性规划一些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的。整数规划是数学规划中一个较弱的分支，目前有成熟的方法解线性整数规划问题，而非线性整数规划问题，还没有好的办法。第六章整数规划4根据变量的取值情况，整数线性规划又可以分为纯整数规划（所有变§1整数规划的图解法例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。货物每件体积(立方米)每件重量(百千克)每件利润（百元）甲乙19527344023托运限制1365140

5§1整数规划的图解法例1.某公司拟用集装箱托运甲、货物每件体积(立方米)每件重量(百千克)每件利润（百元）甲乙19527344023托运限制1365140

解：设x1、

x2分别为甲、乙两种货物托运的件数，建立模型。目标函数：Maxz=2x1+3x2约束条件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4

x1，x2≥0,为整数。如果去掉最后一个约束，就是一个线性规划问题.§1整数规划的图解法6货物每件体积每件重量每件利润甲19542托运限制136514利用图解法，得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出,整数规划的最优解为x1=4,x2=2,目标函数值为14。Maxz=2x1+3x2195x1+273x2=13654x1+40x2=1404231123x2x1§1整数规划的图解法7利用图解法，得到线性规划的最优解为x1=2.对于整数规划，易知有以下性质：性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。§1整数规划的图解法8对于整数规划，易知有以下性质：§1整数规划的图解法8§2分支定界法以及计算机求解分枝定界法步骤：求解与IP相应的LP问题，可能会出现下面几种情况：若所得的最优解的各变量恰好取整数，则这个解也是原整数规划的最优解，计算结束。若无可行解，则原整数规划问题也无可行解，计算结束。若有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。9§2分支定界法以及计算机求解分枝定界法步骤：9分枝定界法步骤（续）：从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl

[xl]或xl

[xl]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（分枝）。定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。10分枝定界法步骤（续）：10例：分支定界法的求解思路图线性规划1Z1=14.66X1=2.44X2=3.26z=13,

=14.66线性规划2Z2=13.90X1=2X2=3.30X1≤2X1≥3X2≤2X2≥3z=13,

=14.58z=14,

=14线性规划4Z4=14.00X1=4X2=2线性规划5无可行解线性规划3Z3=14.58X1=3X2=2.8611例：分支定界法的求解思路图线性规划1z=13,=14.例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≤2

x1-3x2+2x3≤3

x3≤1

x1,x2,x3≥0

x1，x3

为整数，x3

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

x1=5x2=2x3=2用《管理运筹学》软件求解得:z=16.25x1=4x2=1.25x3=1§2整数规划的计算机求解12例2：例3：用《管理运筹学》软件求解得：用《管理运筹学》软件§3整数规划的应用一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j=1,2,3,…,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定:

在东区由A1

，A2

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

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

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

，A9

，A10

三个点中至少选两个。

Aj

各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?13§3整数规划的应用一、投资场所的选择13解：设：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,…,1014解：设：0--1变量xi=1(Ai点被选用)或0例5、解决某市消防站的布点问题，该城市有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市的任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间如下表所示，请帮助该市制定一个最省的计划。12345610101628272021002432171031624012272142832120152552717271501462010212514015例5、解决某市消防站的布点问题，该城市有6个区，每个区都可以设xi=1,0;1－i区建消防站，0－i区不建消防站，i=1,…6minz=x1+x2+x3+x4+x5+x6s.t.x1+x2≥1,x3+x4

≥1,x3+x4+x5

≥1x4+x5+x6

≥1,x2+x6

≥1

xi=0,1;i=1,…612345610101628272021002432171031624012272142832120152552717271501462010212514016设xi=1,0;1－i区建消防站，0－i17171818练习、背包问题背包可装入8单位重量，10单位体积物品。若背包中每件物品至多只能装一个，怎样才能使背包装的物品价值最高。物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服451519练习、背包问题背包可装入8单位重量，10单位体积物品。若解：xi为是否带第i种物品MaxZ=20x1+

30x2+10x3+18x4+15x55x1+3x2+x3+2x4+4x582x1+x2+4x3+3x4+5x510xi为0,1物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服451520解：xi为是否带第i种物品MaxZ=20x1+30一般形式：,整数

xi为i物品携带数量ai为i物品单位重量ci为i物品重要性估价b为最大负重21一般形式：,整数xi为i物品携带数量21§3整数规划的应用二、固定成本问题例6．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。22§3整数规划的应用二、固定成本问题22解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）。引入约束xi≤Myi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。§3整数规划的应用23解：这是一个整数规划的问题。§3整数规划的应用23这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大

xj≥0yj为0--1变量，i=1,2,3§3整数规划的应用24这样我们可建立如下的数学模型：§3整数规划的应用24三、指派问题有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。

§3整数规划的应用25三、指派问题§3整数规划的应用25例7．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。§3整数规划的应用26例7．有四个工人，要分别指派他们完成四项不同的工作，每人做各解：引入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+17x44§3整数规划的应用27解：引入0—1变量xij，并令§3整数规划的应用27整数规划模型为：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为0--1变量，i,j=1,2,3,4§3整数规划的应用28整数规划模型为：§3整数规划的应用28四、分布系统设计例8．某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?

b)如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?§3整数规划的应用29四、分布系统设计§3整数规划的应用29§3整数规划的应用30§3整数规划的应用30解：a)设xij为从Ai运往Bj的运输量(单位千箱)，yk=1(当Ak被选中时)或0（当Ak没被选中时),k=2,3,4,5．这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。§3整数规划的应用31解：a)设xij为从Ai运往Bj的运输量(单位千箱)，yks.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≥0,i=1,2,3,4,5;j=1,2,3,yk为0-1变量,k=2,3,4,5.32s.t.x11+x12+x13≤30(A整数规划模型为：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≥0,i=1,2,3,4,5;j=1,2,3,yk为0-1变量,k=2,3,4,5.33整数规划模型为：33五、投资问题例9.某公司在今后五年内考虑给以下的项目投资.已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?§3整数规划的应用34五、投资问题§3整数规划的应用34解：1)设xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分别表示第i年年初给项目A，B，C，D的投资额；设yiA，yiB，是0-1变量，并规定取1时分别表示第i年给A、B投资，否则取0（i=1,2,3,4,5）。设yiC是非负整数变量,并规定:第2年投资C项目8万元时,取值为4；第2年投资C项目6万元时,取值3;第2年投资C项目4万元时,取值2；第2年投资C项目2万元时,取值1;第2年不投资C时,取值0;

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

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

Ax1A

x2A

x3A

x4A

B

x3B

C

x2C=20000y2C

D

x1D

x2D

x3D

x4D

x5D

35解：1)设xiA、xiB、xiC、xiD(i＝1，22）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是x1A+x1D=100000；第二年：A的投资第二年末才可收回，故第二年年初的资金为1