实例3:饮料的生产批量问题 生产批量问题的一般提法 饮料厂使用同一条生产线轮流生产多种饮料。 c;时段生产费用(元/件);假设初始库存为 若某周开工生产某种饮料,需支出生产准备费3千元 h一时段(末)库存费(元/件);制订生产计划,满 某种饮料4周的需求量 s1时段生产准备费G元);足需求并使T个时 周次箭求量千箱 生产成本(可变成本) d时段t市场需求(件); 段的总费用最小 50元箱(50千元千箱) 决策变量 标mn==∑(sy+cx+h 存贮费 x-时段生产量; 每周每千箱饮料1千元 时段(末)库存量;约来11+x-1=d x>0, y2=1~时段开工生产 安排生产计划,满足每周的需求,使4周总费用最小。 y-10,x=0 (;=0~不开工)。 大学学实编) 生产批量问题的一般提法 网 整数规划问题一般形式 min f(x) mn二= s.h2(x)=0,i=1,…,m +x-l=d 分类 8,(x)≤0,j=1,…, 1,x>0, M是一个充分大的正数 y=0,1 (这里可取M=11) 整数线性规划(LP)目标和约束均为线性函数 l=lr=0.x,1≥0 整数非线性规划INLP目标或约束中存在非线性函数 混合非线性0-1规划? 混合线性0-1规划 纯(全整数规划(PP)决策变量均为整数 混合整数规划(MIP)决策变量有整数,也有实数 0-1规划决策变量只取0或1 (学学奖 整数规划问题对应的松弛问题 整数规划问题对应的松弛问题 取消整数规划中决策变量为整数的限制〔松弛),对 应的连续优化问题称为原问题的松弛问题 对松弛问题的最优解(分量)舍入为整数,得到的往 往不是原整数规划问题的最优解(甚至不是可行解) 整数规划问题 最优解 松弛 非最优解 最 整数 目标函数下降方向 松弛问题 优 →非整教舍入一→整数 原问题 下界(对Min问题) IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点 松弛 上界(对Ma问题) 但IP松弛的最优解为c(35,2.5)3 实例3： 饮料的生产批量问题 • 安排生产计划, 满足每周的需求, 使4周总费用最小。 生产成本（可变成本）: 50元/箱 (50千元/千箱) 存 贮 费: 每周每千箱饮料1千元 饮料厂使用同一条生产线轮流生产多种饮料。 若某周开工生产某种饮料, 需支出生产准备费3千元。 某种饮料4周的需求量 周次 需求量(千箱) 1 2 2 3 3 2 4 4 合计 11 生产批量问题的一般提法 ct ~时段t 生产费用(元/件)； ht ~时段t (末)库存费(元/件)； st ~时段t 生产准备费(元)； dt ~时段t 市场需求(件)； 假设初始库存为0 制订生产计划, 满 足需求,并使T个时 段的总费用最小。 t t t t I + x − I = d −1 min ( ) 1 t t t t t T t t z =∑ s y + c x + h I = 0, , 0 I0 = IT = xt It ≥ ⎩ ⎨ ⎧ = > = 0, 0, 1, 0, t t t x x y 决策变量 xt ~时段t 生产量； It ~时段t (末)库存量； yt =1 ~时段t 开工生产 (yt =0 ~不开工)。 目标 约束 混合线性0-1规划 0,1. 0 = − ≤ t t t y x My 生产批量问题的一般提法 t t t t I + x − I = d −1 0, , 0 I0 = IT = xt It ≥ ⎩ ⎨ ⎧ = > = 0, 0, 1, 0, t t t x x y min ( ) 1 t t t t t T t t z =∑ s y + c x + h I = M是一个充分大的正数 （这里可取M= 11） 混合非线性0-1规划？ 整数规划问题一般形式 g x j l s t h x i m f x j i x Z n ( ) 0, 1,..., . . ( ) 0, 1,..., min ( ) ≤ = = = ∈ • 整数线性规划(ILP) 目标和约束均为线性函数 • 整数非线性规划(INLP) 目标或约束中存在非线性函数 • 纯(全)整数规划(PIP) 决策变量均为整数 • 混合整数规划(MIP) 决策变量有整数，也有实数 • 0-1规划 决策变量只取0或1 分 类 取消整数规划中决策变量为整数的限制（松弛），对 应的连续优化问题称为原问题的松弛问题 整数规划问题对应的松弛问题 松弛问题 松 弛 整数规划问题 最优解 最 优 解 整数 非整数 舍入 整数 下界（对Min问题） 上界（对Max问题） 非最优解 原问题 松弛 对松弛问题的最优解（分量）舍入为整数，得到的往 往不是原整数规划问题的最优解（甚至不是可行解） IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点. 但LP松弛的最优解为C(3.5,2.5) 目标函数下降方向 x1 x2 C A B O 整数规划问题对应的松弛问题