数学建模-第五章整数规划.ppt

第五章 整数规划,运 筹 学,Operations Research,第五章 整数规划,在 LP 问题的讨论中，有些最优解是小数 . 但对 于某些具体问题常有要求最优解是整数( 即整数解) . 如决策变量为机器的台数、人数、车辆数 etc.,如果在问题中所有决策变量有整数限制，称为 纯 整数规划( Pure IP ) 或 全整数规划 ( All IP )；,如果在问题中仅部分决策变量有整数限制，称为 混合整数规划( Mixed IP ) ；,如果在问题中决策变量仅取 0 、1，称为 0-1 (整 数) 规划 .,Integer Programming,第五章 整数规划,1 整数规划问题及其数学模型,2 整数规划的解法,3 整数规划的应用举例,1 整数规划问题及其数学模型,1 整数规划问题及其数学模型,Example 1 （装载问题）,某厂拟用集装箱托运甲、乙 两种货物，每箱的体积、重量、可获利润及托运限制 如表，问两种货物各托 运几箱，可获利润最大？,Solution:,设 x1、x2 分 别为甲、乙两种货物托 运箱数.,则,这是一个 Pure IP 问题.,第五章 整数规划,Example 2 （工厂选址问题）,现准备从 A1、A2、A3 三个地点中选择两个开设工厂，工厂建成后它每月的 产量 ai (i =1,2,3)、三个客户 B1、B2、B3 每月的需求量 bj (j =1,2,3) 及 Ai 至客户 Bj 的单位运价 cij 见表.,已知三工厂每月的经营费用 di (与 产量无关)分别为 100、90、120 .问如 何选址使每月经营和运输费用最低 .,Solution:,因为只有三个厂址选两个， ，所以简单的方法 是任取两个厂用运输问题求解，再加上每月的经营 费用比较即可.,设,选地点 Ai 开设工厂,否则 i = 1,2,3 ；,xij 为Ai 开设工厂时，从 Ai 至 Bj 的运量,显然,如果 Ai 处开设工厂， 则运量满足：,不开设呢？,客户端需求满足：,目标（每月的费用）：,这是一个 Mixed IP 问题. 可用于设计分配系统、新生活小区的设置 etc.,1 整数规划问题及其数学模型,在 Ex.2 中，引进 01 变量给出了在 n 件任务中, 选择 j 项的约束,又用 来刻画不设,第 i 项任务，则 xij j = 1n 都不起作用，为零.,可应用于选择性约束条件中,某工厂生产第 j 种产品的数量为 xj ( j =1,2,3) 其使 用的材料在甲、乙中选择一种，其消耗约束分别为：,其他资源约束条件未列出,引进 01 变量 y,M 为充分大的正数,一般地，假定要在 p个约束条件 中,至少要选择 q 个约束条件得到满足，可引进0-1变量 y,第五章 整数规划,Example 3 （背包问题）,假设有人要出发旅行，考虑带七 种物品，每件物品的重量与价值如表. 现在假设他最多带 35kg 物品，问该带 哪几件物品使总价值最大？,Solution:,这是一个 0-1 规划问题.,一般整数规划中的变量 x , 也可用 0-1 变量替代，如 0 x15 ，x=x020+x121+x222+x323 其中 x0,x1,x2,x3 为0-1 变量 .,1 整数规划问题及其数学模型,参见 Ex.1, 去掉整数约束，得,舍入化整,o 1 2 3 4 5 x1,4 3 2 1,x2,由图解法得最优解为：,x1= 4.8, x2= 0,Zmax = 96,显然，x1 不是整数. 是否可以根据化整的原问题的解？,x1=5、x2=0 不是可行解，,x1=4、x2=0 Z=80 . 但是 x1=4、x2=1 也可行 且 Z=90 .,所以，“舍入化整”的结果：,1、化整后未必可行；,2、即使是可行解，也未必是最优解；,3、用这个方法即使能得到最优解，但如果有n 个变 量，则取舍方案有 2n 种，计算量也是很大的.,Go back,第五章 整数规划,o 1 2 3 4 5 x1,4 3 2 1,x2,2 整数规划的解法,有人在研究在建立模型中，什么条件下 LP 问题的 解一定是整数解？,如： 运输问题,从 Ex.1 的讨论，可得到一些启迪,1、是否能在 LP 的约束区域中, 切 去 n 块不含整数解的可行域使整数 解作为顶点，则 LP 的最优解即为 整数解 ；,如增加约束 x14,则 LP 问题的解即为整数解;,2、在 LP 的可行域中，整数点不多，,（12个）,是否可以用穷举法.,2 整数规划的解法,一、割平面法,1959年由 R.E.Gomory 首先提出，从此使 IP 逐渐 形成为一个独立的运筹学分支. 割平面法的实质是用解 LP 问题的方法求解 IP 问题；,割平面法的基本思想是通过对 LP 问题的求解，如果最 优解是整数解，则就是 IP 的解；否则设法对 LP 问题 增加约束(割平面)，把 LP 问题的可行域中去掉一部分 不含整数解的，再求 LP 问题，反复进行 .,割平面法的关键在于如何寻找适当的切割约束条件.,用割平面法求解 IP 问题常常会计算量大、收敛速度 慢的情况，但在理论上是重要的，被认为是 IP 的核心.,第五章 整数规划,二、分支定界法,分支与定界法的基本思想是对有约束条件的最优化问 题的所有可行解（其数目为有限集）空间适当地进行 搜索 .,具体执行时，把可行解空间不断分割为越来越小 的子集（称为分支），并确定每个分支内的解值的下 界或上界（称为定界）. 在每次分支后，对凡是界超 出已知可行解值的子集被剪去，从而不断缩小搜索范 围.,这个过程一直进行到找出最优解为止，该可行解 的值不大于或不小于任何子集的界 .,优点：1、适用面广 2、可检查较少的解（运 气好）3、可获得最优解,缺点：本质是穷 举，复杂性大于穷举法,2 整数规划的解法,设,如果 则称问题（2）是问题（1）的松弛问题.,Note :,1、松弛问题未必比原问题难解；,如：整数规划与线性规划；TSP 与指派问题 etc.,如： A：寻找全国18 岁百米最快的运动员.,B：寻找全国所有百米最快的运动员.,显然，B 问题是 A 问题的松弛问题，且B 问题更易解 .,2、如果松弛问题易解，则先解松弛问题是有益的 .,1）设 x0 是松弛问题的最优解，且 则原问题已解,2）即使 给出了原问题最优值的界 f(x0) .,x0,B,A,B,A,x0,第五章 整数规划,分枝与定界法为什么能少检查一些解？,B,10s,B1,B2,10.2s,*,10s,B3,B4,10.3s,*,几点注意：, 确定问题（子问题）的最优值的界,通常是通过求解松弛问题， 用松弛问题的解作为界，也可 以用启发式算法得到 .,Note : 松弛问题选择的原则,1、松弛问题要与原问题的 最优值尽量接近；,2、松弛问题要尽量容易解 .,这两个原则不易统一，所以可选择不同的松弛问题,2 整数规划的解法, 划分方法的选择,原则是希望分出来的子问题容易被查清，可加快计算., 选哪个活问题先检查,1、先检查最大上界（极大化问题）的活问题,优点：检查子问题较其他规则为少；,缺点：计算机储存量较大 .,2、先检查最新产生的最大上界的活问题,优点：计算机储存量较少 ；,缺点：需要更多的分支运算 .,选择的不同，提供了发挥的余地,分枝与定界法的重要在于它提出了一类新的思 路（隐枚举法），使得许多原来不好解决的问题有 了解决的可能性. （具有普适性）,第五章 整数规划,Example 4,用分支定界法求解如右 IP 问题,Solution:,解松弛问题 P0,得：x1=2.25、x2=3.75 Zmax=41.25,去掉整数约束为原 问题的松弛问题,41.25是原问题最优值的上界,进行分支，任选一个不是整数的变量,如取 x2 则可认为 最优解 x24 或 x23 . 原问题分为两个子问题 .,3x24 之间无整数解,0 1 2 3 4 5 6 7 8 9 x1,x2 5 4 3 2 1,P1,P2,再分别求解两个松弛问题 P1、P2,P0,x1=2.25 x2=3.75 Z0=41.25,P1(x23),P2（x24）,x1=3、x2=3 Z1=39,*,x1=1.8、x2=4 Z2=41,P3（x12）,P4 (x11),不可行,*,x1=1、x2=40/9 Z4=365/9,P5（x24）,P6 (x25),x1=1、x2=4 Z5=37,*,x1=0、x2=5 Z6=40,*,此时已没有活问题，所以最 优解为 x1=0、x2=5 Zmax=40 .,2 整数规划的解法,Example 5 （投资方案的最优选择）,背包问题可以看成为一个一次性的投资问题，简 单的扩展：1、分几次投资；2、虽然一次性投资，但 不同的项目有一些政策上的限制 etc.,某公司欲对三个项目进行投资， 根据预算四年内的投资额、三个项目 每年所需投资额以及所创利润如表. 问应对哪几个项目进行投资，可获利最大？,Solution:,设,对于0-1 规划的求解，首先会 想到枚举法，但变量取0、1的所 有组合有 2n . 是否能设计一些方 法，只检查所有组合的一部分就 求得最优解，即隐枚举法.,分支定界法是 一种隐枚举.,给出一个重要思想: 设门槛 (1、可行性 2、目标函数值),第五章 整数规划, ,0,16,8,20,28,增加一个判别 A , 目标函 数值小于已知可行解的值， 则不必继续计算 .,A,0,16,20,28,可以改进吗？,A,0,20,28,还有想法吗？,Go back,第五章 整数规划,3 整数规划的应用举例,Example 6 （人员时间安排问题）,为了尽可能有效地利用劳动力，有必要对一天各 个不同时刻需要人员的情况作一分析，特别是在一些 大型服务性机构中，顾客的需要是重复性的，但不同 时刻之间需要的服务量是有显著差别的. 如：电话接 线员、公交乘务员、护士等较长时间的服务机构，因 而合理安排可提高效率，减少雇员. 如下是某航空公 司的售票员人数问题，假设每日工作 8 小时且连续工 作，由统计资料得各时段需要的最少人数 . 问该公司 最少需雇佣多少售票员？,3 整数规划的应用举例,Solution:,由表中情况可知，只 需考虑时段15的上班人数即可. 因为1、9点、11点等上班人数不 影响需要人数；2、时段 5 以后 上班的人员工作时间不到8小时.,设 xj 表示第 j 个时段开始工作的人数，j =15 .,可用0-1规划表示,进一步讨论, 售 票员的吃饭时间、 工资等.,第五章 整数规划,各班工作时间及工资：,设 xj (j=19)为第 j 班次的上班人数.,min Z = 800(x1+x2+x3)+850(x4+x5 +x6)+900(x7+x8+x9),s.t.,x1+x2+x310,x2+x36,共18个约束条件 .,3 整数规划的应用举例,Example 7 （装配线平衡问题）,若某工厂的产品装配 线由 6 道工序组成，各工序的加工时间及紧前工序见表:,若这条装配线设若干个工作站， 被装配的产品在这些编了号的工作站 上流水移动时，每个工作站都要完成 一道或几道工序，假设每个工作站加 工被装配的产品时至多耗时 10分钟 .,问最少应设几个工作站，每个工作站完成哪些工序?,流水节拍,Solution:,显然，需要的工作站不会多于 4 个.,设,第五章 整数规划,目标：,min Z = w1 + w2 + w3 + w4,对工序 i , 它应恰在某一工作站上完成，即,xi1 + xi2 + xi3 + xi4 = 1 i = 16,对工作站 j ，如果设立则在该工作站上完成的各道工 序所需的时间总和不超过 10 分钟，即,3x1j + 5x2j + 2x3j + 6x4j + 8x5j + 3x6j 10 j = 14,3x1j + 5x2j + 2x3j + 6x4j + 8x5j + 3x6j 10wj,如果不设立，则不能将任何工序分配给该工作站，即 wj = 0 则 xij = 0 i = 16 所以，上式改为,3 整数规划的应用举例,对于紧前约束，如工序 2 必须在 工序 3 之前完成，如果工序 3 在最后 一个工作站 4 上完成，显然，工序 2 必在它之前完成 .,如果工序 3 在工作站 3 上完成 (x33 = 1)，则工序 2 必须在工作站 1、2、3 上完成，即,x21 + x22 + x23 x33,类似 x21 + x22 x32 ，x21 x31,其他,x11 + x12 + x13 x43 ，x11 + x12 x42 ，x11 x41,x31 + x32 + x33 x43 ，x31 + x32 x42 ，x31 x41,以上是 6 道工序、4个工作站、5个工序顺序约束的装配线 平衡问题，共有28个变量、29个约束条件 .,Zmin = 3 x11=x21=x31=x42=x62=x53=1 其余为 0,紧前约束也可以用一个不等式描述： x31 + 2x32 + 3x33 + 4x34 x21 + 2x22 + 3x23 + 4x24,第五章 整数规划,Example 8 （排序问题）,用编号为 1#、2#、3#、4# 的4种机床生产3种产品 1#、2#、3#，产品的工艺路线及 工序加工时间见表.,一台机床一次只能加工一个产品, 现要求 2# 产品从开始加工到完成经历时间不超过 29 小 时. 问如何确定各产品在机床上的加工顺序，使在最短 时间内制成全部产品.,Solution:,设 xij 为 i # 产品在机床 j # 上开始加工时间.,第一组约束为每一产品应按工艺路线进行：,3 整数规划的应用举例,第二组约束为一族选择性 的约束条件，以保证每一机床 同一时间只能加工一个产品：,如对 1#,有：,或,引进 0-1 变量 y1 , 上述选择性约束条件为：,类似 y2, y3, y4 为 0-1 变量，对机床 2#、3#、4# 有,M 为充分大的正数,第五章 整数规划,三个产品都完工的时间为：,将它化为线性约束,目标函数为,2#产品从 1# 机床开始加工 到 4# 机床加工完成其经历时间 要求为：,3 整数规划的应用举例,Example 9 (利润分段线性问题),某厂生产甲、乙两种产品，需经 过金工和装配两个车间加工，相关数据如表所示：,产品乙无论生产批量大小，每件产品生产成本总 为 400元，试根据产品甲生产成本的下列两种情况分别 建立数学模型求利润最大 .,1、产品甲的生产成本分段线性：第 1 30 件，每件 成本为 200 元；第 31 70 件，每件成本为 190 元; 从第 71 件开始，每件成本为 195 元.,2、产品甲的产量不超过 40 件时，每件成本 200 元，但 超过 40 件，则甲的全部产品每件成本都为 195 元.,第五章 整数规划,Solution :,设 甲、乙产品的生产数量 分别为 x1，x2 件 .,由条件知产品甲 至多生产 120 件.,1、令 x1 = x3 + x4 + x5 其中 x3、x4、x5 满足下列条件：,当 0 x1 30 时， 有 0 x3 30，x4 = x5 = 0,当 30 x1 70 时， 有 x3 = 30，0 x4 40，x5 = 0,当 70 x1 120 时，有 x3 = 30，x4 = 40，0 x5 50,此时，产品甲所获利润为 100 x3 + 110 x4 + 105x5 ， 产品乙所获利润为 120 x2 .,引进 0-1 变量 y1，y2，将上述条件化为如下约束条件： 30y1 x3 30，40y2 x4 40y1， 0 x5 50y2,讨论 y1、y2的取值，如果 y1 = 0，则必有 y2 = 0，情 形1 成立；y1 = 1，y2 = 0 ，情形2 成立；y1 = 1，y2 = 1, 情形3 成立；y1 = 0，y2 = 1 是不可行的 .,max Z = 100 x3 + 110 x4 + 105x5 + 120 x2 s.t. 4x3 + 4x4 + 4x5 + 3x2 480 2x3 + 2x4 + 2x5 + 5x2 500 30y1 x3 30 40y2 x4 40y1 0 x5 50y2 xj I+0 j = 2, 3, 4, 5 yi = 0 or 1 i = 1, 2 .,3 整数规划的应用举例,2、令 x1 = x3 + x4 其中 x3、x4 满足下列条件：,当 0 x1 40 时， 有 0 x3 40，x4 = 0 ;,当 40 x1 120 时， 有 x3 = 40，0 x4 80 ;,引进 0-1 变量 y，将上述条件化为如下约束条件： 40y x3 40，0 x4 80y .,如果 y = 0，产品甲的利润为 （300-200）x1 = 100 x3,如果 y = 1，产品甲的利润为 105x3 + 105x4 = 100 x3 +105x4 + 5x3 = 100 x3 +105x4 + 200,综上产品甲的利润为 100 x3 +105x4 + 200y,max Z = 100 x3 + 105x4 + 200y + 120 x2 s.t. 4x3 + 4x4 + 3x2 480 2x3 + 2x4 + 5x2 500 40y x3 40 0 x4 80y xj I+0 j = 2, 3, 4 y = 0 or 1.,第五章 整数规划 完,