运筹学与最优化方法 第8章 整形规划

《运筹学与最优化方法 第8章 整形规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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割平面法（续）x1…xr…xmym+1ym

4、+2…ynRHS0…0…0σm+1σm+2…σnf*x1..xr..xm1…0…0a’1m+1a’1m+2…a’1n…………………….0…1…0a’rm+1a’rm+2…a’rn…………………….0…0…1a’mm+1a’mm+2…a’mnb’1..b’r..b’m第八章整数规划§8.4割平面法（续）第八章整数规划§8.4割平面法（续）第八章整数规划§8.4割平面法（续）第八章整数规划x1x2x3x4RHS00-1/2-1/2-5/2x1x210-1/41/4013/41/43/47/4第八章整数规划§8.4割平面法（续）第八章整数规划得到新

5、的对偶单纯形表x1x2x3x4x5RHS00-1/2-1/20-5/2x1x2x310-1/41/40013/41/4000-3/4-1/413/47/4-3/4第八章整数规划进一步得到最优单纯形表:x1x2x3x4x5RHS000-1/3-2/3-2x1x2x31001/3-1/3010010011/3-4/3111第八章整数规划§8.50-1规划的隐枚举法第八章整数规划§8.50-1规划的隐枚举法（续）其中，目标函数系数cj≥0.以下讨论一般形式的0－1规划如何化为标准形式：第八章整数规划§8.50-1规划的隐枚举法(续)第八章整数规划§

6、8.50-1规划的隐枚举法(续)第八章整数规划§8.50-1规划的隐枚举法(续)第八章整数规划§8.50-1规划的隐枚举法(续)第八章整数规划§8.50-1规划的隐枚举法(续)第八章整数规划§8.50-1规划的隐枚举法(续)第八章整数规划§8.50-1规划的隐枚举法(续)第八章整数规划§8.50-1规划的隐枚举法(续)第八章整数规划§8.6分派问题及解法第八章整数规划§8.6分派问题及解法(续)第八章整数规划§8.6分派问题及解法（续）第八章整数规划§8.6分派问题及解法（续）第八章整数规划第八章整数规划第八章整数规划§8.6分派问题及解法（

7、续）第八章整数规划§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、）三、任务与人员数不等的情况例3：分配甲、乙、丙、丁去完成五项任务，每人完成各项任务的时间如下表。由于任务多，规定其中有一人可兼完成两项任务，试确定总花费时间最少的