运筹学12-整数规划II-11教学讲义.ppt

第12讲 整数规划II 12.1 0-1变量在建模中的运用 12.2 求解0-1规划的隐枚举法 12.3 指派问题 12.1 0-1变量在建模中的运用 投资问题 选址问题 “或” 约束 固定费用问题 选址 某公司拟在市东、西、南三区建立门市部，拟议中有7个位置Ai 可供选择，根据有关规定： 在东区，由A1， A2 ，A3三个点中至多选两个； 在西区，由A4， A5 两点中至少选择1个； 在南区，由 A6， A7 两点中至少选择1个。 若选择Ai 点，估计设备投资为bi 元，获利ci ,但投资不能超过B元，如何投资获利最大？ 解：引入0-1变量 “或”约束 两种货物甲和乙，可以选择用车运或者用船运 车运体积 船运体积 重量 利润 甲 5 7 2 20 乙 4 3 5 10 托运限制 24 45 13 问：应选择何种运输方式，两种货物各托运多少箱可以使利润最大？ Max Z=20x1+10x2 5x1+4x2≤24+yM 7x1+3x2≤45 +(1-y)M 2x1+5x2≤13 x1, x2≥0 ，y=0或1 x1, x2为整数 运用0-1变量表示下列四个约束至少满足两个 固定费用问题 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式，固定成本高（选购自动化程度高的设备），但由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，则由于产量小，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令 xj 表示采用第j种方式时的产量； cj 表示采用第j种方式时每件产品的变动成本； kj 表示采用第j种方式时的固定成本。 解：采用各种生产方式的总成本分别为 在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量yj，令 当采用第j种生产方式时(即xj 0) 当不采用第j种生产方式时(即xj = 0) 于是目标函数 Min z =(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3) 添加约束条件 x1 ≤ M1y1 x2 ≤ M2y2 x3 ≤ M3y3 其中M是个充分大的正数。 产品 资源 Ⅰ Ⅱ Ⅲ 资源量 A 2 4 8 500 B 2 3 4 300 C 1 2 3 100 单件可变费用 4 5 6 固定费用 100 150 200 单价 8 10 12 解：总收益等于销售收入减去生产产品的固定费用和可变费用之和。建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。借助0-1变量解决这个困难。 设xj是第j种产品的产量，j=1,2,3； 再引入0-1变量 若生产第j种产品(即xj 0) 若不生产第j种产品(即xj = 0) 该问题的整数规划模型为 Max Z=4x1+5x2+6x3-100y1-150y2-200y3 2x1+4x2+8x3≤500 2x1+3x2+4x3≤300 x1+2x2+3x3≤100 x1 ≤M1y1 x2 ≤M2y2 x3 ≤M3y3 xj ≥0且为整数，j=1,2,3 yj=0或1，j=1,2,3 其中Mj为充分大的正数。 如果生产第j种产品，则其产量xj0。此时，由约束条件xj=Mjyj, 知yj=1。因此，相应的固定费用在目标函数中将被考虑。如果不生产第j种产品，则其产量xj = 0，此时，由约束条件xj=Mjyj, 知yj=0或1，但yj=1不利于目标函数的最大化，因而在最优解中yj必然等于0，从而相应的固定成本在目标函数中将不被考虑。 12.2 求解0-1规划的隐枚举法 隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。 过滤条件：目标函数值优于计算过的可行解目标函数值。 (x1 , x2 , x3) Z值 约束条件 ① ② ③ ④ 过滤条件 （0，0，0） 0 √ √ √ √ Z≥0 （0，0，1） 5 √ √ √ √ Z≥5 （0，1，0） -2 （0，1，1） 3 （1，0，0） 3 （1，0，1） 8 √ √ √ √ Z≥8 （1，1，0） 1 （1，1，1） 6 12.3 指派问题 指派问题的数学模型 指派问题：设有n项工作，交给n个人去完成。每个人只能完成其中的一项，又每个人完成其中任何一项工作的代价为已知，