第八章整数规划 §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 分解又常称为分枝。较常用的 称 分解为 个子问题 之和， 满足 设规划问题（ ）可行解集 有 个子问题 一、分解： 常用的主要技术：