《Matlab学习系列线性规划》由会员分享，可在线阅读，更多相关《Matlab学习系列线性规划（5页珍藏版）》请在金锄头文库上搜索。
1、24. 线性规划一、基本原理一、基本原理一般线性规划问题的标准型为1minnjj jzc x1s. t. ,1,nijjj ja xb imL非标准型可转化为标准型，例如1maxnjj jzc x1s. t. ,1,nijjj ja xb imL可转化为1min njj jzc x1s. t. ,1,nijjj ja xb im L满足约束条件的解 x=(x1, , xn)称为线性规划问题的可行解，所有可行解构成的集合称为问题的可行域，记为 R，使得目标函数达到最小值的可行解称为最优解。基于“若线性规划问题有有限最优解，则一定有某个最优解是可行域的一个极点” ，1947 年，G.B. Dant
2、zig 提出了单纯形法：先找出可行域的一个极点，根据一定规则判断其是否最优，否则转换到与之相邻的另一个极点，并使目标函数值更优，依次做下去，直到找到某一个最优解。二、二、Matlab 实现实现Matlab 中线性规划的标准形式为：min s. t. zcx Axb Aeqxbeq LBxUB 其中，c 和 x 为 n 维列向量，b 为 m 维列向量；A 为 mn 矩阵。Matlab 实现：x, fval, exitflag, output, lambda=linprog(c, A, b, Aeq, beq, LB, UB, X0, options)其中，x 返回最优解；fval 返回目标函数值
3、；A 和 b 对应不等式约束 Axb; Aeq 和 beq 对应等式约束 Ax=b; LB 和 UB 分别是变量 x 的下界和上界；x0 为 x 的初始值；options 为控制参数；exitflag 返回算法停止的原因：1 表示成功找到最优解，0 表示达到最大迭代次数，不能继续寻找最优解，0 表示优化失败（-2未找到可行解，-3 问题没有定义边界，-4 NaN 存在导致算法退出，-5 原始对偶问题没有可行解，-7 算法搜索方向存在问题） ；output 返回 algorithm 采用的算法（大中小型） ，迭代次数等优化信息；lambda 返回最优解 x 处的拉格朗日乘子的一些参数。optio
4、ns 参数设置：（1）options=optimset(optimfun)若已有设置好的参数项设置，直接使用其名称即可；（2）opts=optimset(param1, value1, param2, value2, )创建一个名为 opts 的参数设置，分别指定参数值，未指定的保持默认。例如，要设置使用大型算法、显示每次迭代、允许误差为 10-8：opts=optimset(LargeScale, on, Display, iter, TolFun, 1e-8)例例 1 求解下列线性规划问题：123123123123123max2 s. t. 264422120, 0, 0zxxxxxxxx
5、xxxxxxx代码：代码：f=-2 1 -1; A=1 4 -1; 2 -2 1; b=4;12; Aeq=1 1 2; beq=6; lb=zeros(3,1); x0=0; 0; 0; options=optimset(LargeScale, on, Display, iter, TolFun, 1e-3); x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,b eq,lb,x0,options) lambda.lower运行结果：运行结果：The interior-point algorithm uses a built-in startin
6、g point;ignoring user-supplied X0.Residuals: Primal Dual Duality TotalInfeas Infeas Gap RelA*x-b A*y+z-f x*z Error-Iter 0: 6.61e+02 7.16e+00 1.35e+03 2.00e+02Iter 1: 4.29e+01 7.02e-16 1.28e+02 3.06e+00Iter 2: 5.10e-15 4.58e-16 2.27e+01 1.13e+00Iter 3: 3.08e-15 8.48e-15 1.10e+01 1.06e+00Iter 4: 9.89e
7、-13 4.97e-16 2.62e+00 2.42e-01Iter 5: 9.57e-15 6.84e-14 1.44e-01 1.65e-02Iter 6: 5.10e-15 9.93e-16 1.20e-05 1.38e-06Optimization terminated.x = 4.66670.00000.6667fval = -8.6667exitflag = 1output = iterations: 6algorithm: interior-pointcgiterations: 0message: Optimization terminated.constrviolation:
8、3.5527e-15firstorderopt: 4.3452e-06lambda = ineqlin: 2x1 doubleeqlin: 0.3333upper: 3x1 doublelower: 3x1 doubleans = 0.00006.00000.0000“exitflag = 1”表示优化成功，共迭代 6 次，最优解为x = 4.6667 0.0000 0.6667目标值为 8.6667.注：若在参数选项设置最大迭代次数为3次：options=optimset(LargeScale, on, Display, iter, TolFun, 1e-3, maxiter, 3);fval = -8.2110exitflag = 0 说明达到最大迭代次数，不能继续寻找最优解。
