整数规划
第 八 章 整 数 规 划
第八章整数规划 §81整数规划向题的出 整数规划问题的特征 变量取值范围是离散的,经典连绫数学中的 理论和方法一般无法直接用来求解整数规划问 题 二、建模中常用的处理方法 1、资本预算问题 设有m个投资方案,c为第於个投资方案的收益。 投资过程共分为m个阶段,b为第价阶段的 投资总量,2为第阶段第投资方案所需要 的资金。目标是在各阶段资金限制下使
第八章 整数规划 §8.1 整数规划问题的提出 一、整数规划问题的特征： 变量取值范围是离散的，经典连续数学中的 理论和方法一般无法直接用来求解整数规划问 题。 二、建模中常用的处理方法： 1、资本预算问题： 设有n个投资方案，cj为第j个投资方案的收益。 投资过程共分为m个阶段，bi为第i个阶段的 投资总量，aij为第i阶段第j项投资方案所需要 的资金。目标是在各阶段资金限制下使
第八章整数规划 §8.1二、建模中常用的处理方法:(续) 整个投资的总收益最大。 设决策变量 ∫1对第项投资 0,否则 得到模型: max Z= st <6 i=1,2,…,m 0或1
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） 整个投资的总收益最大。 = = = = = = = x j n st a x b i m z c x j x j n j i j j i n j j j j 0 1 1,2, , . . 1,2, , max 0 1, 1 1 或 得到模型： ，否则 对第 项投资 设决策变量
第八章整数规划 §8.1二、建模中常用的处理方法:(续) 约束∑anx≤b反映第阶段资金增长量的平衡。 an代表在第时期内第项投资的净资金流量 a1>0表示需附加资金; a0表示有附加资金 b<0表示要抽回资金
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） 表示要抽回资金 表示有附加资金 表示第 阶段外源资金流量的增长量： 表示产生资金 表示需附加资金； 代表在第 时期内第 项投资的净资金流量： 约束 反映第 阶段资金增长量的平衡。 0 0 0 0 1 = i i i i j i j i j n j i j j i b b b i a a a i j a x b i
第八章整数规划 §8.1二、建模中常用的处理方法:(续) 2、指示变量:指示不同情况的出现 例有m个仓库,要决定动用哪些仓库,满足 个顾客对货物的需要,并决定从各仓库分别向 不同顾客运送多少货物? 动用仓库 772 0否则 (y为指示变量) x:从仓库顾客运送的货物量
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） 2、指示变量：指示不同情况的出现 例.有m个仓库，要决定动用哪些仓库，满足n 个顾客对货物的需要，并决定从各仓库分别向 不同顾客运送多少货物？ 从仓库 到 顾客运送的货物量 为指示变量 否则 动用 仓库 令 x i j y i m i y i j i i : ( ) 1,2, , 0 1 = =
第八章整数规划 §8.1二、建模中常用的处理方法:(续) 费用: f动用库的固定运营费(租金等) 从仓库到顾客运送单位货物的运费 约束条件: 每个顾客的需要量d必须得到满足 i)只能从动用的仓库运出货物
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） 费用： fi :动用i仓库的固定运营费（租金等） cij :从仓库i到j顾客运送单位货物的运费 约束条件： i)每个顾客的需要量dj必须得到满足； ii)只能从动用的仓库运出货物
第八章整数规划 §8.1二、建模中常用的处理方法:(续) minf=∑∑cnx+∑/ st ∑ ∑x-y∑d≤0i=1 (当y,=0时,xn=0,j=1,2,…,n) y1=0或1i=1,2,…,m;j=1,…,n
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） = = = = = = − = = = = + = = = = = = x y i m j n y x j n x y d i m st x d j n f c x f y i j i i i j n j n j i j i j m i i j j m i n j m i i j i j i i 0, 0 1 1,2, , ; 1, , ( 0 0, 1,2, , ) 0 1, , . . 1,2, , min 1 1 1 1 1 1 或 当 时
第八章整数规划 3线性规划模型的附 (控制约束条件分 ∑anx1+yM,≤b+M 是否需要: y取0或,M为∑anx的上界 1,即原约束需要 0,则原约束失效(永远成立 2)x,=0或 ∑x1≥k(至少个变量取1) ∑x,≤k(至多个变量取1)
第八章 整数规划 3.线性规划模型的附加约束 (1)控制约束条件 是否需要： ( 1) ( 1) 2 0 1 0 1, 0 1 1 1 1 1 至多 个变量取 至少 个变量取 （ ） 或 ，则原约束失效（永远成立） 即原约束需要 取 或 ， 为 的上界 x k k x k k x y y M a x a x y M b M n j j n j j j i n j i i i j j n j i j j i i i i = = + + = = = =
第八章整数规划 (3)离散的资源变化: 约束∑ax≤b,=01,…k 其中:b<b<b2<…<b 1取b约束 处理:引入v1= 0否则 于是,把约束变为: ∑bv≤0 在目标函数中加入一项∑by(求最小)
第八章 整数规划 在目标函数中加入一项 （求最小） 于是，把约束变为： 否则 取 约束 处理：引入 其中： 约束 离散的资源变化： = = = = = = − = = k i i i k i i n j k i j j i i i i k j j i n j b y y a x b y b y b b b b a x b i k 1 1 1 1 0 1 2 1 1 0 0 1 , 0,1, , (3)
§82整数规划解法概述 常用的主要技术 分解: 设规划问题(P),可行解集S(P),有m个子问题 P2…,Pn,满足 1S(1)∪S(P2)…S(Pn)=S(P) 2S()∩S(P)=①,Vi,j=1,2,…,m2≠j 称(P)分解为m个子问题(P)(j=1,2,…,m)之和, 分解又常称为分枝。较常用的m=2
§8.2整数规划解法概述 2. ( ) ( )( 1,2, , ) 2 ( ) ( ) , , 1,2, , , 1 ( ) ( ) ( ) ( ); , , , , : , ( ), 1 2 1 2 = = = = = m P m P j m S P S P i j m i j S P S P S P S P P P P P S P m j i j m m 分解又常称为分枝。较常用的 称 分解为 个子问题 之和， 满足 设规划问题（ ）可行解集 有 个子问题 一、分解： 常用的主要技术：