《[理学]运筹学第8章》由会员分享，可在线阅读，更多相关《[理学]运筹学第8章（71页珍藏版）》请在金锄头文库上搜索。
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整数规划解法概述(续）第八章 整数规划8.2整数规划
3、解法概述(续）第八章 整数规划 8.2整数规划解法概述(续）第八章 整数规划8.3整数规划的分枝定界法第八章 整数规划8.3整数规划的分枝定界法 （续）第八章 整数规划8.3整数规划的分枝定界法 （续）第八章 整数规划8.3整数规划的分枝定界法 （续）第八章 整数规划 8.3整数规划的分枝定界法 （续）第八章 整数规划8.3整数规划的分枝定界法 （续）第八章 整数规划第八章 整数规划第八章 整数规划 8.4割平面法第八章 整数规划 8.4割平面法 （ 续）第八章 整数规划8.4割平面法 （ 续）x1 xr xm ym+1 ym+2 yn RHS0 0 0 m+1 m+2 nf*x1 . . x
4、r . . xm1 0 0 a1m+1 a1m+2 a1n .0 1 0 ar m+1 ar m+2 ar n .0 0 1 am m+1 a m m+2 am nb1 . . br . . bm第八章 整数规划 8.4割平面法 （ 续）第八章 整数规划 8.4割平面法 （ 续）第八章 整数规划8.4割平面法 （ 续）第八章 整数规划x1 x2 x3 x4RHS0 0 -1/2 -1/2-5/2x1x21 0 -1/4 1/40 1 3/4 1/43/47/4第八章 整数规划8.4割平面法 （ 续）第八章 整数规划 得到新的对偶单纯形表x1 x2 x3 x4 x5 RHS0 0 -1/2 -1
5、/2 0-5/2x1x2x31 0 -1/4 1/4 0 0 1 3/4 1/4 0 0 0 -3/4 -1/4 1 3/4 7/4 -3/4 第八章第八章 整数规划整数规划 进一步得到最优单纯形表:x1 x2 x3 x4 x5 RHS0 0 0 -1/3 -2/3-2x1x2x31 0 0 1/3 -1/30 1 0 0 10 0 1 1/3 -4/3111第八章 整数规划8.5 0-1规划的隐枚举法第八章 整数规划 8.5 0-1规划的隐枚举法 （续）其中，目标函数系数 cj 0.以下讨论一般形式的01规划如何化为标准 形式：第八章 整数规划 8.5 0-1规划的隐枚举法 (续)第八章 整
6、数规划8.5 0-1规划的隐枚举法 (续)第八章 整数规划8.5 0-1规划的隐枚举法 (续)第八章 整数规划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分派问题及解法（
7、续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划8.6分派问题及解法（续）第八章 整数规划8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章 整数规划l8.6分派问题及解法（续）第八章第八章 整数规划整数规划第八章 整数规划第八章第八章 整数规划整数规划第八章 整数规划l8.6分派问题及解法（
8、续）l三、任务与人员数不等的情况例3：分配甲、乙、丙、丁去完成五项任务 ，每人完成各项任务的时间如下表。由于任 务多，规定其中有一人可兼完成两项任务， 试确定总花费时间最少的分派方案。 第八章 整数规划l8.6分派问题及解法（续）任务 人ABC DE甲59112217乙242311518丙14782012丁42216325第八章 整数规划 解：增加一人，其完成各项任务时间为该任务完 成的最少时间： 任务 人ABC DE甲59112217乙242311518丙14782012丁42216325戊4甲7丙8丙3丁12丙第八章 整数规划l8.6分派问题及解法（续）例4：从甲、乙、丙、丁、戊五人中选四人 去完成四项任务，每人完成各项任务的 时间如下表。规定每人只能完成一项任 务。由于某种原因，甲必须被分配一项 任务，丁不承担第4项任务，试确定总花 费时间最少的分派方案。 第八章 整数规划l8.6分派问题及解法（续）人 工作甲乙丙 丁戊1102315925101524315514715420151368第八章 整数规划l8.6分派问题及解法（续）解：增加虚设任务5，各人该项任务时间为0 ，某人不完成某任务时，取时间M（充 分大的时间）： 第八章 整数规划l8.6分派问题及解法（续）人 工作甲乙丙 丁戊11023159251015243155147154201513M85M0000
