第七章 数规划问题.pptVIP

第七章 整数规划（IP） 及分配问题; 要求一部分或全部决策变量必须取整数值的规划问题称为整数规划（integer programming，简记IP）。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松驰问题（slack problem）。若松驰问题是一个线性规划，则称该整数规划为整数线性规划（integer linear programming）。;整数线性规划数学模型的一般形式为:;3. 0-1型整数线性规划(Zero-one integer linear programming)：指决策变量只能了取值0或1的整数线性规划。;例7-1某厂生产 和 两种产品，需要经过 三道工序。单件工时和利润以及各工序每周工时限额见表7-1。问工厂应如何安排生产，才能使总利润最大？;解 设工厂每周生产 产品 件， 产品 件。 则该问题的数学模型为 ;例7-2某服务部门各时段（每2小时为一时段）需要的服务人数见表7-2。按规定，服务员连续工作8小时（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。; ;三、解的特点 ; 在一般情况下，松驰问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。此时，若对松驰问题的这个最优解中不符合整数要求的分量简单地取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。;§7-2 分支定界法 ;表7.2.1 分枝问题解可能出现的情况;例1：求解下述问题： min z = -40x1-90x2 s.t. 9x1+7x2≤56 7x1 +20x2≤70 xj≥0,整数，j=1，2;2;2;2;2; 例2：求解下述（AIP）： max z = 3x1+2x2 s.t. 2x1+3 x2 ≤14 　　　　　x1 +0.5x2 ≤4.5 xj≥0,整数，j=1,2;葵琐枝鹅漏嗣抛搅缕瓣袭蕴橇遏仔席限担棺膀褪尊臣歹蔓屏脊犯捕价庸绪第七章 数规划问题第七章 数规划问题;作业：（试用分枝定界法求解下面整数规划问题的解）;作业点评：;分枝问题的松弛解;§7-3 0-1型整数规划;1、投资场所的选定--相互排斥的计划;例7-3现有资金总额为B，可供选择的投资项目有 个，项目 所需投资额和预期收益分别为 和 此外，由于种种原因，有三个附加条件：①若选择项目1，就必须同时选择项目2，反之，则不一定；②项目3和4中至少选择一个；③项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？; 这是一个0-1型整数线性规划问题。其中，中间三个约束条件分别对应三个附加条件。;2、相互排斥的约束条件;在p个约束条件中至少要满足k个约束条件;3、关于固定费用的问题;引例1：今有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸1辆。由于各个班组的技术特长不同，各个班组卸不同车辆所需时间如下表。问：派班员应如何分配卸车任务，可以使卸车所花费的总车辆小时最小？;引例2：一份中文说明书需要译成英、日、德、俄四种文字（E，J，G，R），现有甲、乙、丙、丁四人可以完成上述任务，他们将说明书翻译成不同语种的文字所需时间如下表，且一项任务只能由一人去完成，每人只能完成一项任务。问：指派何人完成何工作，可使总花费时间最少？ ; （1）n项工作怎样分配给n个工作人员去完成， 可以使总花费时间最省； （2）n项加工任务怎样分配给n台机床去完成， 可以使总费用最低； （3）n条航线，怎样指定n艘班轮去完成航行任 务，可以使总运输费用最低； 。。。。。。 ——该类问题是运输问题的特殊形式，称为 指派问题。;（二）指派问题的基本特征;（三）指派问题的基本模型; 运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是0?1规划 任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的 任务分配是匹配问题，有著名的匈牙利算法;二、匈牙利法;定理 1（构造等效矩阵） 如果从效率矩阵{aij}m?m中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵{b