线性规划模型及matlab程序求解

§1线性规划模型一、线性规划课题：实例1：生产计划问题假设某厂计划生产甲、乙两种产品，现库存主要材料有A类3600公斤，B类2000公斤，C类3000公斤。每件甲产品需用材料A类9公斤，B类4公斤，C类3公斤。每件乙产品，需用材料A类4公斤，B类5公斤，C类10公斤。甲单位产品的利润70元，乙单位产品的利润120元。问如何安排生产，才能使该厂所获的利润最大。建立数学模型：设x1、x2分别为生产甲、乙产品的件数。f为该厂所获总润。maxf=70x1+120x2s.t9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0归结出规划问题：目标函数和约束条件都是变量x的线性函数。形如：(1)minfTXs.tAX≤bAeqX=beqlb≤X≤ub其中X为n维未知向量，fT=[f1,f2,…fn]为目标函数系数向量，小于等于约束系数矩阵A为m×n矩阵，b为其右端m维列向量，Aeq为等式约束系数矩阵，beq为等式约束右端常数列向量。lb,ub为自变量取值上界与下界约束的n维常数向量。二．线性规划问题求最优解函数：调用格式：x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(…)[x,fval,exitflag]=linprog(…)[x,fval,exitflag,output]=linprog(…)[x,fval,exitflag,output,lambda]=linprog(…)说明：x=linprog(f,A,b)返回值x为最优解向量。x=linprog(f,A,b,Aeq,beq)作有等式约束的问题。若没有不等式约束，则令A=[]、b=[]。x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)中lb,ub为变量x的下界和上界，x0为初值点，options为指定优化参数进行最小化。Options的参数描述：Display显示水平。选择’off’不显示输出；选择’iter’显示每一步迭代过程的输出；选择’final’显示最终结果。MaxFunEvals函数评价的最大允许次数Maxiter最大允许迭代次数TolXx处的终止容限[x,fval]=linprog(…)左端fval返回解x处的目标函数值。[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub,x0)的输出部分：exitflag描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。output返回优化信息：output.iterations表示迭代次数；output.algorithm表示所采用的算法；outprt.funcCount表示函数评价次数。lambda返回x处的拉格朗日乘子。它有以下属性：lambda.lower-lambda的下界；lambda.upper-lambda的上界；lambda.ineqlin-lambda的线性不等式；lambda.eqlin-lambda的线性等式。三．举例例1：求解线性规划问题：maxf=2x1+5x2s.tx1≤4x2≤3x1+x2≤8x1,x2≥0先将目标函数转化成最小值问题：min(-f)=-2x1-5x2程序：f=[-2-5];A=[10;01;11];b=[4;3;8];[x,fval]=linprog(f,A,b)f=fval*(-1)结果：x=23fval=-19.0000maxf=19例2：minf=5x1-x2+2x3+3x4-8x5s.t–2x1+x2-x3+x4-3x5≤62x1+x2-x3+4x4+x5≤70≤xj≤15j=1,2,3,4,5程序：f=[5-123-8];A=[-21-11-3;21-141];b=[6;7];lb=[00000];ub=[1515151515];[x,fval]=linprog(f,A,b,[],[],lb,ub)结果：x=0.00000.00008.00000.000015.0000minf=-104例3：求解线性规划问题：minf=5x1+x2+2x3+3x4+x5s.t–2x1+x2-x3+x4-3x5≤12x1+3x2-x3+2x4+x5≤-20≤xj≤1j=1,2,3,4,5程序：f=[51231];A=[-21-11-3;23-121];b=[1;-2];lb=[00000];ub=[11111];[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb,ub)运行结果：Exiting:Oneormoreoftheresiduals,dualitygap,ortotalrelativeerrorhasgrown100000timesgreaterthanitsminimumvaluesofar:theprimalappearstobeinfeasible(andthedualunbounded).(ThedualresidualTolFun=1.00e-008.)x=0.00000.00001.19870.00000.0000fval=2.3975exitflag=-1output=iterations:7cgiterations:0algorithm:'lipsol'lambda=ineqlin:[2x1double]eqlin:[0x1double]upper:[5x1double]lower:[5x1double]显示的信息表明该问题无可行解。所给出的是对约束破坏最小的解。例4：求解实例1的生产计划问题建立数学模型：设x1、x2分别为生产甲、乙产品的件数。f为该厂所获总润。maxf=70x1+120x2s.t9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0将其转换为标准形式：minf=-70x1-120x2s.t9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0程序：f=[-70-120];A=[94;45;310];b=[3600;2000;3000];lb=[00];ub=[];[x,fval,exitflag]=linprog(f,A,b,[],[],lb,ub)maxf=-fval结果：x=200.0000240.0000fval=-4.2800e+004exitflag=1maxf=4.2800e+004例5：求解实例2建立数学模型：maxf=0.15x1+0.1x2+0.08x3+0.12x4s.tx1-x2-x3-x4≤0x2+x3-x4≥0x1+x2+x3+x4=1xj≥0j=1,2,3,4将其转换为标准形式：minz=-0.15x1-0.1x2-0.08x3-0.12x4s.tx1-x2-x3-x4≤0-x2-x3+x4≤0x1+x2+x3+x4=1xj≥0j=1,2,3,4程序：f=[-0.15;-0.1;-0.08;-0.12];A=[1-1-1-10-1-11];b=[0;0];Aeq=[1111];beq=[1];lb=zeros(4,1);[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb)f=-fval结果：x=0.50000.25000.00000.2500fval=-0.1300exitflag=1f=0.1300即4个项目的投资百分数分别为50%，25%，0,25%时可使该公司获得最大的收益，其最大收益可到达13%。过程正常收敛。MATLAB的语言特点一种语言之所以能如此迅速地普及，显示出如此旺盛的生命力，是由于它有着不同于其他语言的特点，正如同FORTRAN和C等高级语言使人们摆脱了需要直接对计算机硬件资源进行操作一样，被称作为第四代计算机语言的MATLAB，利用其丰富的函数资源，使编程人员从繁琐的程序代码中解放出来。MATLAB最突出的特点就是简洁。MATLAB用更直观的，符合人们思维习惯的代码，代替了C和FORTRAN语言的冗长代码。MATLAB给用户带来的是最直观，最简洁的程序开发环境。以下简单介绍一下MATLAB的主要特点。1）。语言简洁紧凑，使用方便灵活，库函数极其丰富。MATLAB程序书写形式自由，利用起丰富的库函数避开繁杂的子程序编程任务，压缩了一切不必要的编程工作。由于库函数都由本领域的专家编写，用户不必担心函数的可靠性。可以说，用MATLAB进行科技开发是站在专家的肩膀上。具有FORTRAN和C等高级语言知识的读者可能已经注意到，如果用FORTRAN或C语言去编写程序，尤其当涉及矩阵运算和画图时，编程会很麻烦。例如，如果用户想求解一个线性代数方程，就得编写一个程序块读入数据，然后再使用一种求解线性方程的算法（例如追赶法）编写一个程序块来求解方程，最后再输出计算结果。在求解过程中，最麻烦的要算第二部分。解线性方程的麻烦在于要对矩阵的元素作循环，选择稳定的算法以及代码的调试动不容易。即使有部分源代码，用户也会感到麻烦，且不能保证运算的稳定性。解线性方程的程序用FORTRAN和C这样的高级语言编写，至少需要四百多行，调试这种几百行的计算程序可以说很困难。以下用MATLAB编写以上两个小程序的具体过程。MATLAB求解下列方程，并求解矩阵A的特征值。Ax=b,其中：A=32134567237985124323546598347135b=1234解为：x=A\b;设A的特征值组成的向量e，e=eig（A）。可见，MATLAB的程序极其简短。更为难能可贵的是，MATLAB甚至具有一定的智能水平，比如上面的解方程，MATLAB会根据矩阵的特性选择方程的求解方法，所以用户根本不用怀疑MATLAB的准确性。2）运算符丰富。由于MATLAB是用C语言编写的，MATLAB提供了和C语言几乎一样多的运算符，灵活使用MATLAB的运算符将使程序变得极为简短。3）MATLAB既具有结构化的控制语句（如for循环，while循环，break语句和if语句），又有面向对象编程的特性。4）程序限制不严格，程序设计自由度大。例如，在MATLAB里，用户无需对矩阵预定义就可使用。5）程序的可移植性很好，基本上不做修改就可以在各种型号的计算机和操作系统上运行。6）MATLAB的图形功能强大。在FORTRAN和C语言里，绘图都很不容易，但在MATLAB里，数据的可视化非常简单。MATLAB还具有较强的编辑图形界面的能力。7）MATLAB的缺点是，它和其他高级程序相比，程序的执行速度较慢。由于MATLAB的程序不用编译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。8）功能强大的工具箱是MATLAB的另一特色。MATLAB包含两个部分：核心部分和各种可选的工具箱。核心部分中有数百个核心内部函数。其工具箱又分为两类：功能性工具箱和学科性工具箱。功能性工具箱主要用来扩充其符号计算功能，图示建模仿真功能，文字处理功能以及与硬件实时交互功能。功能性工具箱用于多种学科。而学科性工具箱是专业性比较强的，如control,toolbox,signlproceessingtoolbox,commumnicationtoolbox等。这些工具箱都是由该领域内学术水平很高的专家编写的，所以用户无需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究。9）源程序的开放性。开放性也许是MATLAB最受人们欢迎的特点。除内部函数以外，所有MATLAB的核心文件和工具箱文件都是可读可改的源文件，用户可通过对源文件的修改以及加入自己的文件构成新的工具箱。MATLAB入门教程1．MATLAB的基本知识1-1