《运筹学与最优化MATLAB编程 教学课件 ppt 作者 吴祈宗 郑志勇 第5章》由会员分享，可在线阅读，更多相关《运筹学与最优化MATLAB编程 教学课件 ppt 作者 吴祈宗 郑志勇 第5章（35页珍藏版）》请在金锄头文库上搜索。
1、第5章 线性规划,5.1 线性规划的模型结构 5.2 线性规划的单纯形法 5.3 linprog函数,5.1 线性规划的模型结构,max(min) f=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn(=,)b1 a21x1+a22x2+a2nxn(=,)b2,线性规划的标准形式为： max f=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2,5.1 线性规划的模型结构,am1x1+am2x2+amnxn=bm x1,x2,xn0 转化成矩阵的表示形式为： max f(x)=cTx s.t.
2、Ax=b x0,5.1 线性规划的模型结构,标准形式的可行域是凸集合(凸集合概念可以参看相关章节)。 各种形式的线性规划都可以化为标准形式。 (1)若给出的线性规划是极大化目标函数，则有 min f(x)=max-f(x) (2)若第i个约束为不等式，则可增加松弛变量，把原约束化为等式约束。,5.1 线性规划的模型结构,5.1 线性规划的模型结构,例如： minf=-x1-x2-x3 s.t. 7x1+3x2+9x31 8x1+5x2+4x31 6x1+9x2+5x31 x1,x2,x30,5.1 线性规划的模型结构,引入松弛变量x4,x5,x60，原式变为线性规划的标准形式为： max f=
3、x1+x2+x3+0x4+0x5+0x6 s.t. 7x1+3x2+9x3+x4+0x5+0x6=1 8x1+5x2+4x3+0x4+1x5+0x6=1 6x1+9x2+5x3+0x4+0x5+x6=1 x1,x2,x3,x4,x5,x60,5.1 线性规划的模型结构,(1)若给出的线性规划是极大化目标函数，则有 (2)若第i个约束为不等式，则可增加松弛变量，把原约束化为等式约束。 (3)若第i个等式约束中bi0，则用-1乘该等式两端。 (4)若第j个变量xj没有非负限制，此时称xj为自由变量，则引入两非负变量，即xj,xj0,令xj=xj-xj，将其代入目标函数以及约束中去。,5.2 线性规
4、划的单纯形法,5.2.1 单纯形算法 5.2.2 单纯形表格法的MATLAB程序：simplexTab,5.2.1 单纯形算法,单纯形法(Simplex Method)是求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在，必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。,max f(x)=cTx s.
5、t. Ax=b x0min g(x)=-cTx s.t Ax=b x0 设矩阵A的秩为m。,5.2.1 单纯形算法,算法说明： 本书以线性函数最大化(即max)给出，但是由于MATLAB的内置函数都是以最小化形式进行编程的，为了编写的程序与MATLAB的风格一致，本书程序是以最小化的标准形式进行编程实现的。两种形式在算法步骤上只有目标函数系数向量c的正负号相反。请读者在阅读时注意两者的区别。,5.2.1 单纯形算法,步骤1：取得一个初始可行基B,写出初始基可行解，以及当前的目标函数值，计算所有检验数。 步骤2：考察所有检验数，若所有检验数0，则当前基为最优解，停。否则转步骤3。 步骤3：若0，
6、则无最优解，停。否则转步骤4。,5.2.1 单纯形算法,5.2.2 单纯形表格法的MATLAB程序：simplexTab,1.初始输入表 2.迭代过程表,1.初始输入表,表格,2.迭代过程表,表格,MATLAB优化库函数都是以最小化为标准，所以simplexTab(mat,numFreeVar)程序也以最优化为标准。 simplexTab的使用方法为： 先将一般的线性规划变为线性规划的标准形式，再构建初始单纯形表格，输入程序。,5.2.2 单纯形表格法的MATLAB程序：simplexTab,在MATLAB的command window输出: 初始结果： the best Pivot is 2
7、 row and 1 col the simplex table is 7.00003.00009.00001.0000001.00000.14298.00005.00004.000001.000001.00000.1250(6.0000)9.00005.0000001.00001.00000.1667-1.0000-1.0000-1.000000000,5.2.2 单纯形表格法的MATLAB程序：simplexTab,第一次转换结果： the best Pivot is 1 row and 3 col the simplex table is 0-1.3750(5.5000)1-0.8750
8、00.12500.022710.62500.50000 0.125000.12500.250005.25002.00000-0.750010.25000.12500-0.3750-0.50000 0.125000.12500,5.2.2 单纯形表格法的MATLAB程序：simplexTab,第二次转换结果： the best Pivot is 1 row and 2 col the simplex table is 0(-0.2500)1.00000.1818-0.159100.0227-0.09091.00000.75000-0.09090.204500.11360.151505.75000
9、-0.3636-0.43181.00000.20450.03560-0.500000.09090.045500.13640,5.2.2 单纯形表格法的MATLAB程序：simplexTab,第三次转换结果： 001.00000.1660-0.17790.04350.0316-0.09091.000000-0.04350.2609-0.13040.08700.151501.00000-0.0632-0.07510.17390.03560.03560000.05930.00790.08700.15420It is the end!(表示程序运行完毕),5.2.2 单纯形表格法的MATLAB程序：s
10、implexTab,最后的单纯形表为： x1x2x3x4x5x6btheta0010.1660-0.17790.04350.0316-0.0909A100-0.04350.2609-0.13040.08700.1515010-0.0632-0.07510.17390.03560.0356判别数0000.05930.00790.08700.15420x=(0.0316,0.0870,0.0356),g=0.1542, f=-x1-x2-x3=-0.1542,5.2.2 单纯形表格法的MATLAB程序：simplexTab,simplexTab(mat,numFreeVar) 输入单纯形表mat
11、自由变量个数numFreeVar 子程序：由主函数调用,5.2.2 单纯形表格法的MATLAB程序：simplexTab,1. function newMat=interChange(mat,row1,row2) 单纯形表的两行对调 2. function newMat=multiFromRowToRow(mat,fromRow,toRow,multiplier) 行数据非主元素消去处理 3. function newMat=multMat(mat,row,mult) 行乘以mult得新行数据,5.2.2 单纯形表格法的MATLAB程序：simplexTab,5.3 linprog函数,lin
12、prog函数在MATLAB优化工具箱Optimization-Toolbox中。 linprog针对的线性函数模型为 min f Tx s.t. Axb Aeq x=beq lbxub 这里f,x,b,beq,lb,ub是向量，A,Aeq是矩阵。,5.3 linprog函数,Linprog计算算法为： 1.约束优化问题的拉格朗日乘法(即：内点法) 有关该算法的介绍本章不讲，可以参看约束规划问题的相关章节。 2.单纯形法Simplex,linprog函数格式为： 1. x=linprog(f,A,b)s 求解目标min f*x约束A*x=b. 输入：f：目标函数系数向量 A：不等式约束系数矩阵
13、b：不等式约束常数向量 输出：x:最优解,5.3 linprog函数,2. x=linprog(f,A,b,Aeq,beq) 输入：Aeq：等式约束系数矩阵 Beq：等式约束常数向量 3. x=linprog(f,A,b,Aeq,beq,lb,ub) 输入：lb：x的可行域下界 ub：x的可行域上界 4. x=linprog(f,A,b,Aeq,beq,lb,ub,x0) 输入：x0:初始迭代点(这个与linprog使用的算法有关),5.3 linprog函数,5. x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 输入：options优化参数设置 6. x,
14、fval=linprog(.) 输出：fval：最优目标函数值 7. x,lambda,exitflag=linprog(.) 输出：lambda,exitflag:算法停止原因 8. x,lambda,exitflag,output=linprog(.) 输出：output：优化结果的约束信息,5.3 linprog函数,输出参数说明： Exitflag：返回算法迭代停止原因 返回值：1 算法收敛于解x，即x是线性规划的最优解 0 算法达到最大迭代次数停止迭代，即x不一定是线性规划的最优解 -2 算法没有找到可行解，即算法求解失败，问题的可行解集合为空,5.3 linprog函数,-3 原问
15、题无解，即最优解可能为正(负)无穷大 -4 在算法中出现除零问题或其他问题，导致变量中出现非数值情况 -5 线性规划的原问题与对偶问题都不可解 -7 可行搜索方向向量过小，无法再提高最优解质量,5.3 linprog函数,Lambda：返回解的拉格朗日乘子与约束符合情况 Lower：求得解越下界 Upper：求得解越上界 Neqlin：求得解不满足不等式约束 Eqlin：求得解不满足等式约束,5.3 linprog函数,min f=-x1-x2-x3 s.t. 7x1+3x2+9x31 8x1+5x2+4x31 6x1+9x2+5x31 x1,x2,x30 使用x,fval,exitflag,
16、output,lambda=linprog(f,A,b,Aeq,beq,lb,ub),5.3.1 实例演示1(对应程序test2),Command window输入 f= %目标函数系数 A=:%不等式约束的系数矩阵 b= %不等式约束的b Aeq= %等式约束的系数矩阵(该问题无等式约束Aeq为空) beq= %等式约束的beq(该问题无等式约束beq为空) lb= %变量的下界,5.3.1 实例演示1(对应程序test2),Command window输出 Optimization terminated.(优化算法计算结束) x=(最优解) fval=-0.1542(最优解对应的函数值) exitflag=1(算法收敛于解x，即x是线性规划的最优解) output= iterations:7(算法迭代7次),5.3.1 实例演示1(对应程序test2),
