化工系统工程：第3章 化工过程系统的优化-整数规划

1、1第二篇化工过程系统的优化 NO.4 整数规划2写出其对偶问题画约束条件；标明可行域；目标函数等值线；说明如何得到最优解，算出相应的目标函数最优值。 用图解法求解下面的线性规划的对偶问题 课堂习题-2原问题3课堂习题-2对偶问题红色区域为可行域，灰色虚线为目标函数等值线。根据其梯度4，2，向右平移等值线，在点A(3,1)处达到可行域最远点，则该点为最优解。Min W=4*3+2*1=14 目标函数最优值为14。A梯度4，2方法1：二次型特征矩阵A的正定性4第二篇课程(3)非线性规划重点回顾(1) 二次函数凸凹性判定规则一般形式:Convex/concaveConvex?方法2： Hessian

2、矩阵H的正定性二次型:Hessian矩阵:0，正定，严格凸函数 0，半正定：凸函数=9X1=4X2=4X2=7X1 Z(5) F如对 Z(6) 继续分解，其最小值也不会低于15.5 ，问题探明，剪枝。44最优解为： x1=2， x2 =3, Z* = Z(5) =17以上的求解过程可以用一个树形图表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4无可行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6)

3、15.5x11x12x23x24x12x1345分支定界法求解原问题(IP) （1）先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一： 若( LP )没有可行解，则( IP )也没有可行解，停止计算。 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 为讨论方便，设( LP )的最优解为： 目标函数最优值为不全为整数46分枝定界法解法步骤记( IP )的目标函数最优值为 ,以 作为 的下界，记为 。令 ，则有 （2）定界： 在( LP

4、 )的最优解 X(0)中，任选一个不符合整数条件的变量，例如 xr= br （不为整数），以br表示不超过br的最大整数。构造两个约束条件 xr br 和 xr br1 将这两个约束条件分别加入问题( IP ) ，形成两个子问题( IP1)和( IP2 ) ，再解这两个子问题的松弛问题( LP1)和( LP2) 。 （3）分枝：47如此反复进行，直到得到 为止，即得最优解 X* 。 （4）修改上、下界：按照以下两点规则进行。 在各分枝问题中，找出目标函数值最小者作为新的下界； 从已符合整数条件的分枝中，找出目标函数值最小者作为 新的上界。 （5）比较与剪枝 ： 各分枝的目标函数值中，若有大于

5、者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。 （1）先不考虑整数约束，解(IP)的松弛问题(LP)：（2）定界：（3）分枝：48整数规划的应用第三部分生产计划优化人力资源问题城市应急系统选址问题炼油厂1#原油24$/桶2#原油15$/桶汽油36$/桶燃料油21$/桶煤油24$/桶残油10$/桶例1：生产计划优化产品名称收率 / %最大生产能量或市场需求/(桶/天)1#原油2#原油汽油804424000煤油5102000燃料油10366000残油510加工费用/$0.51.0生产计划模型 1#原油用量 2#原油用量 汽油产量 煤油产量 燃料油产量 残油产量生产计划模型实际生

6、产过程（0-1规划）：在短周期内，装置生产不可能频繁切换。假定在一天内，炼油厂只能加工一种原油。 加工1#原油 加工2#原油生产计划模型54例1：人力资源分配问题某个中型百货商场对售货人员（周工资200元）的需求经统计如下表，为了保证销售人员充分休息，销售人员每周工作5天，休息2天，每天需要的售货人员数如下表。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？星期一二三四五六七人数12151214161819例2：人力资源分配问题55人员安排限制每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量例2：人力资源分配问题

7、56问题分析确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量：每天开始休息的人数 57问题分析约束条件 ：1.每人休息时间2天，自然满足；2.每天工作人数不低于需求量；3.某天休息的人数就是从某天往前数5天内开始工作的人数 58 3.变量非负约束：59目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于60模型61例3：应急选址问题 某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区

8、到各备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。62问题分析 该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区的路程要最小化。 变量：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是中心的位置。设 63问题分析 为了便于说明问题引入间接变量，第i小区是否由第j个中心服务 以及最远的距离约束条件，小区服务约束64问题分析最远距离约束 中心个数约束目标函数：最远距离 最小 65模型66混合整数线性规划求解器 MILP SolversCPL

9、EXGUROBIXPRESS其他: CBC, CGL, GLPK67凸/非凸-混合整数非线性规划求解器Convex/non-Convex MINLP SolversMINLP codes:SBB Bussieck, Drud (2003) (B&B)Bonmin (COIN-OR) Bonami et al (2006) (B&B, OA, Hybrid)DICOPT (GAMS) Viswanathan and Grossman (1990) (OA)AOA (AIMMS) (OA)-ECP Westerlund and Peterssson (1996) (ECP)MINOPT Schwe

10、iger and Floudas (1998)(GBD, OA)Global MINLP code:BARON Sahinidis et al. (1998) (Deterministic Global Optimization)MIQP codes:CPLEX-MIQP ILOG (Branch and bound, cuts)68Academic Tree of Ignacio E. Grossmann作业1(只列数学模型，不要求计算结果)：现有资金总额为B。可供选择购买的化工产品有n个，产品j的价格和预期利润分别为aj和cj，此外，因供货商对产品的采购约束，有3个附加条件：第一，若选择产品1必须同时选择项目2，反之，不一定；第二