运筹学08整数规划ppt课件

1、第八章 整数规划8.1 8.1 整数规划问题及其数学模型整数规划问题及其数学模型8.2 8.2 整数规划的应用整数规划的应用8.3 8.3 整数规划与线性规划的关系整数规划与线性规划的关系8.4 8.4 分支定界法分支定界法8.5 8.5 指派问题与匈牙利算法指派问题与匈牙利算法一、整数规划问题的特征：一、整数规划问题的特征： 变量取值范围是离散的，经典连续数学中的变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。理论和方法一般无法直接用来求解整数规划问题。二、整数规划问题的定义：二、整数规划问题的定义：规划中的变量部分或全部限制为整数时，称为规划中的变量部分或

2、全部限制为整数时，称为整数规划整数规划Integer ProgrammingInteger Programming）。简称）。简称IPIP。线性规划中的变量部分或全部限制为整数时，线性规划中的变量部分或全部限制为整数时，称为整数线性规划。称为整数线性规划。8.1 整数规划问题及其数学模型8.1 整数规划问题及其数学模型三、建模中常用的处理方法三、建模中常用的处理方法： 1 1、资本预算问题：、资本预算问题： 设有设有n n个投资方案，个投资方案，cjcj为第为第j j个投资方案的收益。个投资方案的收益。投资过程共分为投资过程共分为m m个阶段，个阶段，bibi为第为第i i个阶段的投资总量个阶

3、段的投资总量，aijaij为第为第i i阶段第阶段第j j项投资项投资方案所需要的资金。目标方案所需要的资金。目标是在各阶段资金限制下使是在各阶段资金限制下使整个投资的总收益最大。整个投资的总收益最大。njxmibxatsxczMaxjxjnjijijnjjjj, 2 , 110, 2 , 1. .0, 111或得到模型：，否则项投资对第设决策变量2、指示变量：指示不同情况的出现、指示变量：指示不同情况的出现 例例.有有m个仓库，要决定动用哪些仓库，满足个仓库，要决定动用哪些仓库，满足n个个顾客对货物的需要，并决定从各仓库分别向不顾客对货物的需要，并决定从各仓库分别向不同顾客运送多少货物？同顾

4、客运送多少货物？ 费用：费用： fi:动用动用i仓库的固定运营费租金等）仓库的固定运营费租金等） cij:从仓库从仓库i到到j顾客运送单位货物运费顾客运送单位货物运费顾客运送的货物量到从仓库为指示变量令jixy,m1,2,i01yijii:)(否则仓库i动用njmiyxnjxymidyxnjdxtsyfxcfiijijinjnjjiijmijijminjmiiiijij, 1;, 2 , 110, 0), 2 , 1, 00(, 10, 2 , 1. .min111111或时，当约束条件：约束条件：i)i)每个顾客的需要量每个顾客的需要量djdj必须得到满足；必须得到满足； ii) ii)只能

5、从动用的仓库运出货物。只能从动用的仓库运出货物。四、整数规划的数学模型四、整数规划的数学模型纯整数规划：所有决策变量为非负整数；纯整数规划：所有决策变量为非负整数；全整数规划：所有变量、系数和常数均为整数；全整数规划：所有变量、系数和常数均为整数；混合整数规划：只有一部分决策变量为非负整数，混合整数规划：只有一部分决策变量为非负整数，其余变量可其余变量可 为非负实数；为非负实数；0-1整数规划：所有决策变量只能取整数规划：所有决策变量只能取0获获1两个整两个整数。数。且部分或全部为整数njxmibxatsxcZMinMaxjinjjijnjjj, 2 , 1, 0, 2 , 1.)(118.2

6、 整数规划的应用 一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?8.2 整数规划的应用

7、解：设：解：设：0-1变量变量 xi = 1 (Ai 点被选用或点被选用或 0 (Ai 点没被选用）。点没被选用）。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 且且xj 为为0-1变量，变量，i

8、= 1,2,3,108.2 整数规划的应用二、固定成本问题二、固定成本问题 例例5高压容器公司制造小、中、大三种尺寸的高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别考虑固定费用，每种容器售出一只所得的利润分别为为 4万元、万元、5万元、万元、6万元，可使用的金属板有万元，可使用的金属板有500吨，劳动力有吨，劳动力有300人人/月，机器有月，机器有100台台/月，此外不月，此外不管每

9、种容器制造的数量是多少，都要支付一笔固定管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是的费用：小号是l00万元，中号为万元，中号为 150 万元，大号万元，大号为为200万元。现在要制定一个生产计划，使获得的万元。现在要制定一个生产计划，使获得的利润为最大。利润为最大。 资源小号容器 中号容器 大号容器金属板（吨）248劳动力（人月）234机器设备（台月）1238.2 整数规划的应用解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i

10、种容器, 即 xi 0 时) 或0当不生产第 i种容器即 xi = 0 时）。 引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 为0-1变量，i = 1,2,3三、指派问题三、指派问题 有有 n 项不同的任务，恰好项不同的任务，恰好

11、 n 个人可分别承担这些个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把一项任务，怎样把 n 项任务指派给项任务指派给 n 个人，使得个人，使得完成完成 n 项任务的总的效率最高，这就是指派问题项任务的总的效率最高，这就是指派问题。 例例6有四个工人，要分别指派他们完成四项不同有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为示，

12、问应如何指派工作，才能使总的消耗时间为最少。最少。8.2 整数规划的应用 工作工人ABCD甲15182124乙19232218丙26171619丁192123178.2 整数规划的应用解：引入解：引入01变量变量 xij，并令，并令xij = 1(当指派第当指派第 i人去完成第人去完成第j项工作时项工作时)或或0当不指派第当不指派第 i人去完成第人去完成第j项工作时项工作时)这可以表示为一个这可以表示为一个0-1整数规整数规划问题：划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+1

13、9x41 +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工

14、作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 为为0-1变量，变量，i,j = 1,2,3,4 8.2 整数规划的应用四、投资问题四、投资问题 例例8某公司在今后五年内考虑给以下的项目投资。某公司在今后五年内考虑给以下的项目投资。知：知：项目项目A：从第一年到第四年每年年初需要投资，并于：从第一年到第四年每年年初需要投资，并于次年末回收本利次年末回收本利115%， 但要求第一年投资最低金但要求第一年投资最低金额为额为4万元，第二、三、四年不限；万元，第二、三、四年不限；项目项目B：第三年初需要投资，到第五年末能回收本利：

15、第三年初需要投资，到第五年末能回收本利128，但规定最低投资金额为，但规定最低投资金额为3万元，最高金额万元，最高金额为为5万元；万元； 工程工程 C：第二年初需要投资，到第五年末能回收本：第二年初需要投资，到第五年末能回收本利利140%，但规定其投资额或为，但规定其投资额或为2万元或为万元或为4万元或万元或为为6万元或为万元或为8万元。万元。 工程工程 D：五年内每年初可购买公债，于当年末归还，：五年内每年初可购买公债，于当年末归还，并加利息并加利息6%，此项投资金额不限。，此项投资金额不限。 该部门现有资金该部门现有资金10万元，问它应如何确定给这万元，问它应如何确定给这些项目的每年投资额

16、，些项目的每年投资额，使到第五年末拥有的资金本利总额为最大使到第五年末拥有的资金本利总额为最大?8.2 整数规划的应用解：解：1) 设设xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分别表示第分别表示第 i 年年初给年年初给项目项目A，B，C，D的投资额；的投资额； 设设yiA， yiB，是，是01变量，并规定取变量，并规定取 1 时分别表示第时分别表示第 i 年给年给A、B投资，投资，否则取否则取 0（ i = 1, 2, 3, 4, 5）。）。设设yiC 是非负整数变量，并规定：第是非负整数变量，并规定：第2年投资年投资C项目项目8万元时，取值为万元时，取值为4；第第 2年投

17、资年投资C项目项目6万元时，取值万元时，取值3；第；第2年投资年投资C项目项目4万元时，取值万元时，取值2；第第2年投资年投资C项目项目2万元时，取值万元时，取值1；第；第2年不投资年不投资C项目时，取值项目时，取值0； 这样我们建立如下的决策变量：这样我们建立如下的决策变量： 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 A x1A x2A x3A x4A B x3B C x2C=20000y2C D x1D x2D x3D x4D x5D 8.3整数规划与线性规划的关系n从数学模型上看，整数规划似乎是线性规划的一种特殊情况，求解只需在线性规划解的基础上，通过舍入取整，寻求满足

18、整数要求的解即可。n但是实际上整数规划与线性规划之间确实有着很大的不同，通过舍入取整得到的整数解也不一定就是整数规划问题的最优解，有时甚至不能保证所得的解是整数可行解例98.1n关于整数规划问题的可行解和最优解的定义与线性规划类似，只是要加上满足整数条件一般来说，整数规划问题的可行解是相应的线性规划问题可行域内的整数格子点，因此整数规划的可行解集是一个有限集见下图）n既然整数规划的可行解是一个有限集，我们可以将这个集合内的每一个点对应的目标函数值都一一计算出来，然后从中找出最大者，就是整数规划问题的最优解这种方法称为完全枚举法n严格地说，IP问题是一个非线性问题。这是因为IP的可行域是一个整点

19、凸包，而不是一个凸集。)0 , 0()0(X)0 , 1 ()1(X)0 , 2()2(X)0 , 3()3(X) 1 , 2()6(X)2 , 2()7(X) 1 , 1 ()4(X)2 , 1 ()5(X) 1 , 3()8(X0)0(Z1)1(Z3)3(Z2)2(Z2)4(Z3)5(Z4)7(Z3)6(Z4)8(Z4) 1 , 3()2 , 2(*ZXXn完全枚举法的问题是计算量太大，特别是当变量个数很多和约束条件的个数也很多时，这个工作是很费时的，有时甚至是不可能实现的nn! 当n=20时，大于2108 n因此，如何巧妙地构造枚举过程是必须研究的问题，目前用得较多的是将完全枚举法变成部

20、分枚举法n常用的求解整数规划的方法有分枝定界法和割平面法，对于特别的0l规划问题的求解，可以采用隐枚举法和匈牙利法8.4 分枝定界法n60年代初，由 Land Doing和Dakin等人 提出n是一个部分枚举的方法n优点：灵敏，便于计算机求解，成为目前求解整数规划的重要方法之一n用途：可用于求解纯整数规划或混合整数规划问题n分枝定界法由“分枝和“定界两部分组成n其基本解题思路可大致叙述如下：n4. 修改上、下界：修改界值按照以下两点规则：n在各分枝问题中，找出目标函数值最大者作为新的上界；n从已符整数条件的分枝中，找出目标函数值最大者作为新的下界例1n用分枝定界法求解整数规划问题8.2D1D28.38.38.38.48.48.4D3D421x31xD7D8G31x21x14/6131x31x艘船去航行等。条航线有项任务；台机床加工类似有：可使总效率最高。派效率不同，决定如何指各人对完成不同任务的成，个人（每人一项）去完项任务要分配给）：题一、分配问题（指派问nnnnnnproblemAssignment,8.5 8.5 指派问题与匈牙利法指派问题与