线性规划(LP)基本概念和搜索算法 |
您所在的位置:网站首页 › 线性规划的定义是什么和形式 › 线性规划(LP)基本概念和搜索算法 |
标引
可以用一个符号描述一系列类似的数量值 线性方程一个方程,如果他是关于决策变量的常熟加权求和形式,则该方程式线性方程(liner),佛则该方程为非线性方程(non-linear) 线性规划目标函数 目标函数 一个优化模型,如果他的决策变量中存在离散变量,则该优化模型位整数规划(integer program, IP),如果整数规划的所有决策变量均为离散变量,则该整数规划为纯整数规划(pure integer program);否则为混合整数规划(mixed integer program)。 搜索算法搜索算法(improving search)通过检查邻域来寻找比当前更好地解,若有改进则替换当前解,继续迭代,直到邻域中没有更好的解为止。搜索算法又称为局部改进(local improvement),爬山算法(hillclimbing),局部搜索(local search)或邻域搜索(neighborhood search) 倘若一组可行解周围足够小的的邻域内没有优于该解的可行点,则称为局部最优解(local optimum),最小化(最大化)问题存在局部最小(最大)解。 如果在全局范围内不存在目标值优于某可行解的其他可行点,则称为全局最优解(global optimum),最小化(最大化)问题存在全局最小(最大)解 搜索算法沿 对于所有足够小的 如果优化模型的目标函数 导数(derivative),描述函数随参数的变化率,可以看做斜率。偏导数(partial derivative),是保持其他变量恒定时,关于其中一个变量的导数 改进方向的梯度条件对于最大化目标函数 对于最小化目标函数 当目标函数梯度 如果可行域内任意两点的连线都在可行域内,则称该可行域为凸集。 离散的可行集总是非凸集 若优化模型的可行集是凸集,那么对任意可行解始终存在指向另一个解的可行方向,意味着,只要存在最优解,可能性不会阻碍局部最优解发展为全局最优解。 线性约束可行集的凸性线性约束的可行集又称为多面体集。 如果优化模型的所有约束都是线性的,那么该模型的可行域是凸集 寻找初始解两阶段法 大M法 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |