《第1讲 线性规划.ppt》由会员分享，可在线阅读，更多相关《第1讲 线性规划.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 线性规划线性规划数学建模数学建模谢华朝生活中的优化问题，一般都是求使问题生活中的优化问题，一般都是求使问题的某一项指标的某一项指标“最优最优”的方案，这类问的方案，这类问题统称为题统称为“最优化问题最优化问题”。解决这类问。解决这类问题的最常用方法就是线性规划方法。题的最常用方法就是线性规划方法。目的目的内容内容2、掌握用数学软件包求解线性规划问题。、掌握用数学软件包求解线性规划问题。1、了解线性规划的基本内容。、了解线性规划的基本内容。*2 2、线性规划的基本算法。、线性规划的基本算法。5 5、作业。、作业。3、用数学软件包求解线性规划问题。、用数学软件包求解线性规划问题。1、两个引例。、
2、两个引例。4、建模、建模案例：投资的收益与风险案例：投资的收益与风险问题一问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？两个引例两个引例解解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：解答问题二：问题二：某厂每日8小时的产量不低于1800件。为了进
3、行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解解 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：故目标函数为：故目标函数为：约束条件为：线性规划模型：线性规划模型：解答返回线性规划模型的一般形式：线性规划模型的一般形式：1.1.线性规划的标准形式：线性规划的标准形式：用单纯形法求解时，常将标准形式化为：2.线性规划的
4、基本算法线性规划的基本算法单纯形法单纯形法线性规划的基本算法线性规划的基本算法单纯形法单纯形法方法：方法：2、约束条件为不等式：对于不等号、约束条件为不等式：对于不等号“（）”的约束的约束 条件，则可在左端加上（减去）一个非负变量（松弛条件，则可在左端加上（减去）一个非负变量（松弛 变量），使其变为等式。变量），使其变为等式。1、目标函数为最小化问题：令、目标函数为最小化问题：令 z=-z,max z=-min z3、无约束的决策变量：如、无约束的决策变量：如 x为任意实数，令为任意实数，令x=x-x”,x,x”0.引入松弛变量x3,x4,x5,将不等式化为等式,即单纯形标准形:显然A的秩ra
5、n(A)=3,任取3个线性无关的列向量,如P3P4P5称为一组基基,记为B.其余列向量称为非基非基,记为N.于是f=cBxB+cNxN,Ax=BxB+NxN=b,则xB=B-1b-B-1NxN,f=cBB-1b+(cNcBB-1N)xN 若可行基进一步满足:cNcBB-1N0,即:cBB-1N-cN0则对一切可行解x,必有f(x)cBB-1b,此时称基可行解x=(B-1b,0)T为最优解最优解.3.最优解的存在性定最优解的存在性定理理将A的列向量重排次序成A=(B,N),相应x=(xB,xN)T,c=(cB,cN)基对应的变量xB称为基变量基变量,非基对应的变量xN称为非基变量非基变量.定理定
6、理1 1 如果线性规划(1)有可行解，那么一定有基可行解.定理定理2 2 如果线性规划(1)有最优解，那么一定存在一个基可行解 是最优解.4.4.基可行解是最优解的判定准则基可行解是最优解的判定准则因为f=cBB-1b+(cNcBB-1N)xN，即f-0 xB+(cBB-1N-cN)xN=cBB-1b5.5.基可行解的改进基可行解的改进改进方法：改进方法：返回用用MATLAB优化工具箱解线性规划优化工具箱解线性规划minz=cX 1、模型：命令：x=linprog（c，A，b）2、模型：minz=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b
7、=.3、模型：minz=cX VLBXVUB命令：1x=linprog（c，A，b，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：1若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.解解 编写编写M文件文件xxgh1.m如下：如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.0
8、3 0 0 0.08;b=850;700;100;900;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh1)解解:编写编写M文件文件xxgh2.m如下：如下：c=6 3 4;A=0 1 0;b=50;Aeq=1 1 1;beq=120;vlb=30,0,20;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh2)S.t.改写为：例例3 问题一的解答问题问题编写编写M文件文件xxgh3.m如下如下:f=1391011128
9、;A=0.41.110000000.51.21.3;b=800;900;Aeq=100100010010001001;beq=400600500;vlb=zeros(6,1);vub=;x,fval=linprog(f,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh3)结果结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。例例2 问题二的解答问题问题改写为：编写编写M文件文件
10、xxgh4.m如下：如下：c=40;36;A=-5-3;b=-45;Aeq=;beq=;vlb=zeros(2,1);vub=9;15;%调用linprog函数：x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh4)结果为：结果为：x=9.00000.0000fval=360即只需聘用9个一级检验员。注：注：本问题应还有一个约束条件：x1、x2取整数。故它是一个整数线性规划整数线性规划问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定
11、是相应整数规划的最优解，这样的整数规划应用专门的方法求解。返回 投资的收益和风险投资的收益和风险二、基本假设和符号规定二、基本假设和符号规定三、模型的建立与分析三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即maxqixi|i=1，2,n4.模型简化：四、模型四、模型1 1的求解的求解 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)1c=-0.05-0.27-0.19-0.185-0.185;Aeq=11.011.021.0451.065;
12、beq=1;A=00.025000;000.01500;0000.0550;00000.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);ax=xQ=-valplot(a,Q,.)，axis(00.100.5)，holdona=a+0.001;endxlabel(a),ylabel(Q)ToMatlab（xxgh5）计算结果：计算结果：五、五、结果分析结果分析返回4 4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风
13、险和 收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度收益x0 x1x2x3x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2 2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。格式如下:x=bintprog(f)x=bintprog(f,A,b
14、)x=bintprog(f,A,b,Aeq,beq)x=bintprog(f,A,b,Aeq,beq,x0)x=bintprog(f,A,b,Aeq,Beq,x0,options)x,fval=bintprog(.)x,fval,exitflag=bintprog(.)x,fval,exitflag,output=bintprog(.)bintprog求解0-1规划问题这里x是问题的解;向量f是由目标函数的系数构成的向量;A是一个矩阵，b是一个向量A，b和变量x=x1,x2,xn一起，表示了线性规划中不等式约束条件。A，b是系数矩阵和右端向量。Aeq和Beq表示了线性规划中等式约束条件中的系数
15、矩阵和右端向量。X0是给定的变量的初始值options为控制规划过程的参数系列。返回值中fval是优化结束后得到的目标函数值。exitflag=0表示优化结果已经超过了函数的估计值或者已声明的最大迭代次数；exitflag0表示优化过程中变量收敛于解X，exitflag=时应乘以-1化为=.实验作业实验作业某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.返回