运筹学12-整数规划II-11.pptVIP

第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元，如何投资获利最大？ “或”约束 两种货物甲和乙，可以选择用车运或者用船运 运货有车运和船运两种方式，用车运时的体积限制条件： 5x1+4x2?24 [1] 如用船运时关于体积的限制条件为 7x1+3x2?45 [2] 这两条件是互相排斥的。车运时只需满足[1]，而船运时只需满足[2] 为了统一在一个问题中，引入0-1变量y，令 于是[1]和[2]可由下述条件[3]和[4]来代替： 5x1+4x2?24+yM [3] 7x1+3x2?45+(1-y)M [4] 其中M是充分大的数。 可以验证，当y=0时，[3]就是[1]，而[4]自然成立，因而是多余的。当y=1时，[4]就是[2]，而[3]是多余的。引入的变量y不必出现在目标函数内，即认为在目标函数式内y的系数为0。 运用0-1变量表示下列四个约束至少满足两个 固定费用问题 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式，固定成本高（选购自动化程度高的设备），但由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，则由于产量小，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令 xj 表示采用第j种方式时的产量； cj 表示采用第j种方式时每件产品的变动成本； kj 表示采用第j种方式时的固定成本。 添加约束条件 解：总收益等于销售收入减去生产产品的固定费用和可变费用之和。建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。借助0-1变量解决这个困难。 设xj是第j种产品的产量，j=1,2,3； 再引入0-1变量 12.2 求解0-1规划的隐枚举法 隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。 过滤条件：目标函数值优于计算过的可行解目标函数值。 12.3 指派问题 指派问题的数学模型 指派问题：设有n项工作，交给n个人去完成。每个人只能完成其中的一项，又每个人完成其中任何一项工作的代价为已知，求这样的任务分配方案，使完成这些工作的总代价为最小。 以cij表示第i个人完成第j项工作所付出的代价，由此得到矩阵： 引入决策变量xij： 由此得到指派矩阵X = (xij)。注意到：由于每项工作只能由一人完成并且每人只能做一项工作，故在指派矩阵中每行和每列有且只有一个1，其余均为0。 例：已知指派问题中的代价矩阵为 则下列矩阵 均为指派矩阵，其代价分别为50，28。而矩阵 X3不是指派矩阵。 所谓求指派问题的最小值解，就是求这样的指派矩阵，其对应的代价为最小。 数学模型的表达： 指派矩阵(解矩阵)应满足的条件是，该矩阵中每行和每列的元素中只有一个是1，其余均为0，即 指派问题的数学模型可以表示为： 指派问题的求解——匈牙利法 设代价矩阵为C=(cij)nxn，我们用下面的方法求其最小值解： (1) 每行减去该行的最小数(行缩减)； (2) 每列减去该列的最小数(列缩减)； (3) 判断是否有n个独立的零，若有，则在指派矩阵中，对应于独立的零的位置元素取1，其余取0，则得到该指派问题的最小值解。 是否存在n个独立的零的判断方法：用最少的横线或竖线将经过行缩减和列缩减后的代价矩阵中的所有的零划去，若最少的线数为n