运筹学08整数规划

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

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

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

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

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

6、公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲乙乙1951952732734 440402 23 3托运限制托运限制13651365140140 8.2 整数规划的图解法解：解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： s.t. 195 x1 + 273 x2 1365 4 x1 + 40

7、 x2 140 x1 4 x1，x2 0 为整数。如果去掉最后一个约束，就是一个线性规划问题。8.2 整数规划的图解法由图解法得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。12341232x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =68.2 整数规划的图解法例例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1,x2,x3 0 为整数例例3： Max z

8、 = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x3 1 x1,x2,x3 0 x1，x3 为整数 x3 为0-1变量用管理运筹学软件求解得： x1 = 5 x2 = 2 x3 = 2 用管理运筹学软件求解得： x1 = 4 x2 = 1.25 x3 = 18.3 整数规划的应用 一、投资场所的选择一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2

9、 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?8.3 整数规划的应用解：解：设：0-1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型：Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+6

10、1x10s.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 = 1,2,3,108.3 整数规划的应用二、固定成本问题二、固定成本问题 例例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500

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

12、）。 引入约束 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 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指

13、派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。 例6有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。8.3 整数规划的应用 工作工人ABCD甲15182124乙19232218丙26171619丁192123178.3 整数规划的应用解解：引入01变量 xij，并令xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为一个0-1整数规划问题：Minz=15x11+18x12+21x13+24x14+1

14、9x21+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 (

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

16、年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?8.3 整数规划的应用解：解：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年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C

17、项目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.4 分支定界法 分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。 分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解

18、这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。 . 2), 2 , 1)()(, 2 , 1,)()(2);()()()(1:,),(,2121mmjPmPjimjiPSPSPSPSPSPSPPPmPSPjjimm常用的分解又常称为分枝。较之和，个子问题分解为称满足个子问题有可行解集）设规划问题（一、分解：常用的主要技术：8.4 分支定界法.)(),(.)(3;)()(2)(),()(1min,)()()(optPxPSxoptPfffPfPPPPSPSPPP的是则的若的一个下界，即最优值是最优值无可行解；）无可行解，则特别若（那么，有下列性质：是求设问题

19、）。松弛问题（可得到删去某些约束，把约束条件放宽问题二、松弛：)(,2, 1|min)()(.1,)()(,)()( ,)(.,2, 1,),( ,),(),()(21约束得到的子问题是原问题上增加下界新，可计算：分解之后的上下界问题问题为最优目标值的上、下界及的最优值为及的最优值记）（各子问题分解为子问题设问题三、剪枝：ffmjffffffPffffPPfPPfPmiPPPPPjjjjjjjjjjjm大。再分解只能使目标值增大。再分解只能使目标值增当前的若。肯定子问题解集均为在分解是增加约束，故说明无可行解，即若式进行。用逐步分解子问题的方计算整数规划问题常采分解，即称剪枝：以下几种情况，不

20、必再上界新的可行解对应目标值。有可取各子问题,3,);(.)(2,)(,)()(1.2,min)(1jjjjjjjjjjmjjjfffffPSxoptPPSPSPfffffffPfLPXbAXtsAXCfBnjxXbAXtsXCfATjT标准问题的松弛为整数，设线性整数规划问题：0.min)(,2, 10.min)()(,)(22)()(),(,)()(,)()()(),(1xffSxAAxffASxxBiiiASxxiiABiBAA那么取任一最优值的一个下界：可找最优值的的下界，转为而有最优解若的解。得到则停（剪枝）且有最优解若无可行解；枝）说明无可行解，则停止（剪若求解骤）分枝定界法：（一

21、般步B重复上述求解过程。中得到两个子问题分别加入把构造两个约束条件：找不等于整数的分量）分枝：对于上述（分枝与定界：以下进行分枝和定界：),(),()()(),()(1)(,1. 1212121AAAcccxxcxxxSxstepiiiiiA优解。对应的解即原问题的最枝时，当前上界当全部子问题均得到剪述过程进行分枝。对于未剪枝问题重复上，”的方法考察剪枝问题按“剪枝比较与剪枝。和下界找到当前层的上界”的方法枝定界（估界）：按“剪2. 21)2(stepffz线性规划线性规划1Z1=14.66X1=2.44X2=3.26z z=13, =13, =14.66 线性规划线性规划2Z2=13.90X

22、1=2X2=3.30线性规划线性规划3Z3=14.58X1=3X2=2.86线性规划线性规划4Z4=14.00X1=4X2=2线性规划线性规划5无可行解无可行解X12X13X22X23z z=13, =13, =14.58 z z=14, =14, =14zz 分支定界法示意图艘船去航行等。条航线有项任务；台机床加工类似有：可使总效率最高。派效率不同，决定如何指各人对完成不同任务的成，个人（每人一项）去完项任务要分配给）：题一、分配问题（指派问nnnnnnproblemAssignment,8.5 8.5 指派问题与匈牙利法指派问题与匈牙利法10, 1, 1, 1, 1. .ZM)(01:0.

23、 11111或每人一项任务每项任务一人：模型否则项任务个人完成第第引入时间成本等项任务的效率个人完成第第设一般模型：ijnjijniijninjijijijijxnixnjxtsxcinPjixjicnnnnnncccccccccC212222111211效益矩阵阵数据集中在下列系数矩有相同的解。与原问题为系数矩阵的分派问题那么以得到矩阵素中加上同一个实数的一行（或一列）各元若从矩阵的最优解的性质：关于问题BbBaCPnmij,)()(. 2响最优解。目标函数的常数项不影目标函数：afxaxcxbfnkiinjkjnjijijninjijij11111kiackicbakCkjijij那么，行

24、各元素加上的第设从证：,n1 1、指派问题的形式表述、指派问题的形式表述n给定了一系列所要完成的任务（给定了一系列所要完成的任务（taskstasks）以及一系列完）以及一系列完成任务的被指派者（成任务的被指派者（assigneesassignees），所需要解决的问题），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务就是要确定出哪一个人被指派进行哪一项任务 2 2、指派问题的假设、指派问题的假设被指派者的数量和任务的数量是被指派者的数量和任务的数量是相同的相同的每一个被指派者只完成每一个被指派者只完成一项任务一项任务 每一项任务只能由每一项任务只能由一一个被指派者个被指派者来完成来

25、完成 每个被指派者和每项任务的组合有一个相关成本每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小目标是要确定怎样进行指派才能使得总成本最小 典型问题典型问题 例例1 1：有有甲、乙、丙、丁甲、乙、丙、丁四个工人，要分别派他们完成四四个工人，要分别派他们完成四乡不同的任务，分别记作乡不同的任务，分别记作A A、B B、C C、D D。他们完成各项任务。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982第第1 1步，变换系数矩阵：步，变换系数矩阵：2142 289541013895421176)( ijc 0673390245100954 0173340240100454-5第第2 2步，确定独立零元素步，确定独立零元素 找到找到 3 个独立零元素，个独立零元素， 但但 m = 3 工作数时：假想工作数，使得工作数时：假想工作数，使得与人数能够匹配与人数能够匹配, , 对应的效率设定为对应的效率设定为0 0值。值。 当工作数当工作数 人数时：假想人数，使得与人数时：假想人数，使得与工作数能够匹配工作数能够匹配, , 对应的效率设定为对应的效率设定为0 0值。值。人数和工作数不等的指派问题人数