运筹学与最优化方法第8章.ppt

1、第 八 章,整 数 规 划,第八章 整数规划,8.1 整数规划问题的提出 一、整数规划问题的特征： 变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。 二、建模中常用的处理方法： 1、资本预算问题： 设有n个投资方案，cj为第j个投资方案的收益。投资过程共分为m个阶段，bi为第i个阶段的投资总量，aij为第i阶段第j项投资方案所需要的资金。目标是在各阶段资金限制下使,第八章 整数规划,8.1二、建模中常用的处理方法： （续） 整个投资的总收益最大。,第八章 整数规划,8.1二、建模中常用的处理方法： （续）,第八章 整数规划,8.1二、建模中常用的处理方法： （

2、续） 2、指示变量：指示不同情况的出现 例.有m个仓库，要决定动用哪些仓库，满足n个顾客对货物的需要，并决定从各仓库分别向不同顾客运送多少货物？,第八章 整数规划,8.1二、建模中常用的处理方法： （续） 费用： fi:动用i仓库的固定运营费（租金等） cij:从仓库i到j顾客运送单位货物的运费 约束条件： i)每个顾客的需要量dj必须得到满足； ii)只能从动用的仓库运出货物。,第八章 整数规划,8.1二、建模中常用的处理方法： （续）,第八章 整数规划,3.线性规划模型的附加约束 (1)控制约束条件是否需要：,第八章 整数规划,8.2整数规划解法概述,第八章 整数规划,8.2整数规划解法概

3、述(续）,第八章 整数规划,8.2整数规划解法概述(续）,第八章 整数规划,8.2整数规划解法概述(续）,第八章 整数规划,8.3整数规划的分枝定界法,第八章 整数规划,8.3整数规划的分枝定界法 （续）,第八章 整数规划,8.3整数规划的分枝定界法 （续）,第八章 整数规划,8.3整数规划的分枝定界法 （续）,第八章 整数规划,8.3整数规划的分枝定界法 （续）,第八章 整数规划,8.3整数规划的分枝定界法 （续）,第八章 整数规划,第八章 整数规划,第八章 整数规划,8.4割平面法,第八章 整数规划,8.4割平面法 （ 续）,第八章 整数规划,8.4割平面法 （ 续）,第八章 整数规划,8

4、.4割平面法 （ 续）,第八章 整数规划,8.4割平面法 （ 续）,第八章 整数规划,8.4割平面法 （ 续）,第八章 整数规划,第八章 整数规划,8.4割平面法 （ 续）,第八章 整数规划,得到新的对偶单纯形表,第八章 整数规划,进一步得到最优单纯形表:,第八章 整数规划,8.5 0-1规划的隐枚举法,第八章 整数规划,8.5 0-1规划的隐枚举法 （续）,其中，目标函数系数 cj 0. 以下讨论一般形式的01规划如何化为标准形式：,第八章 整数规划,8.5 0-1规划的隐枚举法 (续),第八章 整数规划,8.5 0-1规划的隐枚举法 (续),第八章 整数规划,8.5 0-1规划的隐枚举法

5、(续),第八章 整数规划,8.5 0-1规划的隐枚举法 (续),第八章 整数规划,8.5 0-1规划的隐枚举法 (续),第八章 整数规划,8.5 0-1规划的隐枚举法 (续),第八章 整数规划,8.5 0-1规划的隐枚举法 (续),第八章 整数规划,8.5 0-1规划的隐枚举法 (续),第八章 整数规划,8.6分派问题及解法,第八章 整数规划,8.6分派问题及解法(续),第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,第八章 整数规划,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章

6、 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,第八章 整数规划,第八章 整数规划,第八章 整数规划,8.6分派问题及解法（续） 三、任务与人员数不等的情况,例3：分配甲、乙、丙、丁去完成五项任务，每人完成各项任务的时间如下表。由于任务多，规定其中有一人可兼完成两项任务，试确定总花费时间最少的分派方案。,第八章 整数规划,8.6分派问题及解法（续）,第八章 整数规划,解：增加一人，其完成各项任务时间为该任务完成的最少时间：,第八章 整数规划,8.6分派问题及解法（续） 例4：从甲、乙、丙、丁、戊五人中选四人去完成四项任务，每人完成各项任务的时间如下表。规定每人只能完成一项任务。由于某种原因，甲必须被分配一项任务，丁不承担第4项任务，试确定总花费时间最少的分派方案。,第八章 整数规