运筹学第三版第8章.ppt

1、第 8 章,整 数 规 划,第8章 整数规划,8.1整数规划问题的提出 1.整数规划问题的特征 变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。 2.建模中常用的处理方法 （1）资本预算问题 设有n个投资方案，cj为第j个投资方案的收益。投资过程共分为m个阶段，bi为第i个阶段的投资总量，aij为第i个阶段第j项投资方案所需要的资金。目标是在各阶段资金限制下使,8.1整数规划问题的提出,整个投资的总收益最大。,8.1整数规划问题的提出,8.1整数规划问题的提出,（2）指示变量：指示不同情况的出现 例1 有m个仓库，要决定动用哪些仓库，满足n个顾客对货物的需要，

2、并决定从各仓库分别向不同顾客运送多少货物？,8.1整数规划问题的提出,费用 fi :动用i仓库的固定运营费（租金等）； cij :从仓库i到顾客j运送单位货物的运费。 约束条件 （1）每个顾客的需要量dj必须得到满足； （2）只能从动用的仓库运出货物。,8.1整数规划问题的提出,8.1整数规划问题的提出,3.线性规划模型的附加约束 (1)控制约束条件是否需要：,8.1整数规划问题的提出,8.2 整数规划解法概述,8.2 整数规划解法概述,8.2 整数规划解法概述,8.3 整数规划的分枝定界法,8.3 整数规划的分枝定界法,8.3 整数规划的分枝定界法,8.3 整数规划的分枝定界法,8.3 整数

3、规划的分枝定界法,8.3 整数规划的分枝定界法,8.3 整数规划的分枝定界法,8.3 整数规划的分枝定界法,8.4 割平面法,8.4 割平面法,8.4 割平面法,8.4 割平面法,8.4 割平面法,8.4 割平面法,8.4 割平面法,8.4 割平面法,8.4 割平面法,得到新的对偶单纯形表,8.4 割平面法,进一步得到最优单纯形表,8.5 0-1规划的隐枚举法,8.5 0-1规划的隐枚举法,其中，目标函数系数 cj 0。 以下讨论一般形式的0 - 1规划如何化为标准形式,8.5 0-1规划的隐枚举法,8.5 0-1规划的隐枚举法,8.5 0-1规划的隐枚举法,8.5 0-1规划的隐枚举法,8.

4、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 分派问题及解法,8.6 分派问题及解法,8.6 分派问题及解法,8.6 分派问题及解法,8.6 分派问题及解法,8.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 分派问题及解法,解 增加一人，其完成各项任务的时间为该任务完成的最少时间：,8.6 分派问题及解法,例4 从甲、乙、丙、丁、戊五人中选四人去完成四项任务，每人完成各项任务的时间如下表。规定每人只能完成一项任务。由于某种原因，甲必须被分配一项任务，丁不承担第4项任务，试确定总花费时间最少的分派方案。,8.6