Matlab学习系列24.线性规划.docx

24. 线性规划一、基本原理一般线性规划问题的标准型为 1 min n j j j z c x ??? 1 s. t. , 1, , n ij j j j a x b i m ?? ???非标准型可转化为标准型,例如 1 max n j j j z c x ??? 1 s. t. , 1, , n ij j j j a x b i m ?? ???可转化为 1 min n j j j z c x ?? ??? 1 s. t. , 1, , n ij j j j a x b i m ?? ?????满足约束条件的解 x =(x 1,…,x n) 称为线性规划问题的可行解,所有可行解构成的集合称为问题的可行域, 记为 R, 使得目标函数达到最小值的可行解称为最优解。基于“若线性规划问题有有限最优解, 则一定有某个最优解是可行域的一个极点”, 1947 年, . Dantzig 提出了单纯形法:先找出可行域的一个极点, 根据一定规则判断其是否最优, 否则转换到与之相邻的另一个极点, 并使目标函数值更优, 依次做下去, 直到找到某一个最优解。二、 Matlab 实现 Matlab 中线性规划的标准形式为: min s. t. z cx Ax b Aeqx beq LB x UB ???? ?其中, c和 x为 n 维列向量, b为 m 维列向量; A为 m×n 矩阵。 Matlab 实现: [x, fval , exitflag, output, lambda ] =linprog(c, A, b, Aeq, beq, LB, UB, X0, o ptions) 其中, x 返回最优解; fval 返回目标函数值; A和 b 对应不等式约束 Ax ≤ b; Aeq 和 beq 对应等式约束 Ax=b; LB 和 UB 分别是变量 x 的下界和上界; x0为 x 的初始值; options 为控制参数; exitflag 返回算法停止的原因: 1 表示成功找到最优解, 0 表示达到最大迭代次数,不能继续寻找最优解, <0 表示优化失败( -2未找到可行解, -3 问题没有定义边界, -4 NaN 存在导致算法退出, -5 原始对偶问题没有可行解, -7 算法搜索方向存在问题); output 返回 algorithm 采用的算法( 大中小型), 迭代次数等优化信息; lambda 返回最优解 x 处的拉格朗日乘子的一些参数。 options 参数设置: ( 1) options=optimset( ‘ optimfun ’) 若已有设置好的参数项设置,直接使用其名称即可; ( 2) opts=optimset( ‘ param1 ’, value1, ‘ param2 ’, value2, …) 创建一个名为 opts 的参数设置,分别指定参数值,未指定的保持默认。例如,要设置使用大型算法、显示每次迭代、允许误差为 10 -8: opts=optimset( ‘ LargeScale ’,‘ on’,‘ Display ’,‘ iter ’,‘ TolFun ’, 1e-8