离散变量优化问题..pptVIP

离散变量问题优化算法 (Algorithms for Discrete Variable Problem)  §9.1引言 一般的优化方法只能求得连续变量的最优解。 工程实际中存在大量混合设计变量问题 混合设计变量包含:连续设计变量、整型设计变量和离散设 计变量。 例如:齿轮传动装置的优化设计 齿数是一个整型量,模数是一系列 离散量,变位系数可以看做连续量 齿宽若按长度1mm单位计算,则也可 以看做整型量。  传统方法的局限性 求离散问题的最优解,传统的方法是先用连续变量优化 设计方法求连续变量的最优解,然后圆整到离散值上。 弊病:可能得不到可行最优解,或所得的解不是离散最 优解。 为连续变量最优解 x①是圆整后最近的离散点,但不可 X(2 x(2)是最近的可行离散点,但不是离 散最优点; x③3是离散最优点。  离散变量优化方法 离散变量优化难点:不存在指导有哪些信誉好的足球投注网站过程的最优性条件。 直接方法:枚举法( enumeration)。可行点过多时,计算量大。 减少计算量:随机思想( stochastic ideas)、启发式原则( heuristic rules)。 两种基本方法 (隐式)枚举法:如,分枝定界法( the branch and bound algorithm); 随机或进化方法:如,模拟退火算法、遗传算法等。  §9.3分枝定界法( the branch and bound algorithm) 引入概念:松弛问题 以整型优化问题为例: maxZ=x+5x 5x1+6x2≤30 ≤4 x,x2≥0且全为整数 松弛问题: maxZ=x+5x, 5x+6x,≤30 ≥0  分枝定界法基本思想: 设有最大化的整型优化问题A,相应有松弛问题B,从解松弛问题 B开始,若其最优解不符合A的整数条件,那么B的最优目标函数 必是A的最优目标函数x米的上界,记作;而A的任意可行解 的目标函数值将是x的一个下界,记作又。 分枝定界法就是将B的可行域分成子区域(称为分枝)的方法 逐步减小了,增大又,最终求到x ≤冰≤  个基本操作: (1)分枝 在松弛问题B的最优解中任选一个不符合整数条件的变量x,其 值为b,以b表示小于b的最大整数。构造两个约束条件 x≤[b,和x≥[b1+1 将这两个约束条件,分别加入问题B,求两个后继规划问题B1和B2, 不考虑整数条件求解这两个后继问题  (2)定界 以每个后继问题为一分枝标明求解结果,在解的结果中,找岀最优 目标函数值最大者作为新的上界.从已符合整数条件的各分支中 找出目标函数值为最大者作为新的下界,若无,则下界为0 3)比较与剪枝 各分支的最优目标函数中若有小于,则剪掉这枝;若大于互 且不符合整数条件,则重复前两步,直到找到最优解  分枝定界法计算过程: 上界 讨论松弛问题L: 1、L无最优解,则IP)无最优解结束 2、最优解X*=(x*0,x*,…,x*m),最优值z (1)X*为整数解,则X*为P的最优解结束 (2)X米中至少有一个是分数,设x*是分数:分枝 ,sXo 子问题L1 子问题L2 1、L1无最优解,剪枝 2、最优解X*=(x*,x*12…,x米 最优值x1 (1)X*1为整数解,x为下界关闭 (2)X*中至少有一个是分数 继续分枝  设已找到下界Z: 讨论子问题L: 若k的最优值zk≤20,剪枝 若1的最优值zkZo (1)最优解X*是整数解 将下界改为z,关闭L (2)最优解X*不是整数解 继续对L分枝 当所有的子问题均被关闭或剪枝后 目标函数值最大的整数解既为所求的最优解