MATLAB课件第十一章线性极值

第十一章线性极值MATLAB提供了很多求极值（或最优值）的命令函数，既可以求无条件的极值，也可求有条件的极值，其中，条件可以是不等式，也可以是等式的，可以是线性的，也可以是非线性的，甚至可以是多个条件，目标函数可以是线性的，也可以是非线性的，总之，MATLAB针对不同的类型，采用不同的函数命令去求解，以下将分类型来做些简单的介绍。1线性极值（又称线性规划）1.1线性规划模型规划问题研究的对象大体可以分为两大类：一类是在现有的人、财、物等资源的条件下，研究如何合理的计划、安排，可使得某一目标达到最大，如产量、利润目标等；另一类是在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使成本、费用最小等。这两类问题从本质上说是相同的，即都在一组约束条件下，去实现某一个目标的最优（最大或最小）。线性规划研究的问题要求目标与约束条件函数都是线性的，而目标函数只能是一个。在经济管理问题中，大量问题是线性的，有的也可以转化为线性的，从而使线性规划有极大的应用价值。线性规划模型包含3个要素：（1）决策变量.问题中需要求解的那些未知量，一般用n维向量Tnxxxx),,,(21表示。（2）目标函数.通常是问题需要优化的那个目标的数学表达式，它是决策变量x的线性函数。（3）约束条件.对决策变量的限制条件，即x的允许取值范围，它通常是x的一组线性不等式或线性等式。线性规划问题的数学模型一般可表示为：min（max）fTXs.tAX≤bAeqX=beqlb≤X≤ub其中X为n维未知向量，fT=[f1,f2,…fn]为目标函数系数向量，小于等于约束系数矩阵A为m×n矩阵，b为其右端m维列向量，Aeq为等式约束系数矩阵，beq为等式约束右端常数列向量。lb,ub为自变量取值上界与下界约束的n维常数向量。特别注意：当我们用MATLAB软件作优化问题时，所有求maxf的问题化为求min(-f)来作。约束gi(x)≥0，化为–gi≤0来做。1.2．线性规划问题求最优解函数：调用格式：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为指定优化参数进行最小化。[x,fval]=linprog(…)左端fval返回解x处的目标函数值。[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub,x0)的输出部分：exitflag描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。Output为关于优化的一些信息。Lambda为解x的Lagrange乘子。【例1】求解线性规划问题：maxf=2x1+5x2s.t008234212121xxxxxx先将目标函数转化成最小值问题：min(-f)=-2x1-5x2具体程序如下：f=[-2-5];A=[10;01;12];b=[4;3;8];lb=[00];[x,fval]=linprog(f,A,b,[],[],lb)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】：假设某厂计划生产甲、乙两种产品，现库存主要材料有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将其转换为标准形式：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];[x,fval,exitflag]=linprog(f,A,b,[],[],lb);x,exitflag,maxf=-fval运行结果：x=200.0000240.0000exitflag=1maxf=4.2800e+004【例4】：某公司有一批资金用于4个工程项目的投资，其投资各项目时所得的净收益(投入资金百分比)如下表：工程项目收益表工程项目ABCD收益(%)1510812由于某种原因，决定用于项目A的投资不大于其他各项投资之和而用于项目B和C的投资要大于项目D的投资。试确定该公司收益最大的投资分配方案。建立数学模型：设x1、x2、x3、x4分别代表用于项目A、B、C、D的投资百分数。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-1;0-1-11];b=[0;0];Aeq=[1111];beq=[1];lb=zeros(4,1);[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb)fmax=-fval运行结果：x=0.50000.25000.00000.2500fval=-0.1300exitflag=1fmax=0.1300即4个项目的投资百分数分别为50%，25%，0,25%时可使该公司获得最大的收益，其最大收益可到达13%。过程正常收敛。【例5】：有A、B、C三个食品加工厂，负责供给甲、乙、丙、丁四个市场。三个厂每天生产食品箱数上限如下表：工厂ABC生产数604050四个市场每天的需求量如下表：市场甲乙丙丁需求量20353334从各厂运到各市场的运输费(元/每箱)由下表给出：市场甲乙丙丁工厂A2132B1321C3411求在基本满足供需平衡的约束条件下使总运输费用最小。建立数学模型：设aij为由工厂i运到市场j的费用，xij是由工厂i运到市场j的箱数。bi是工厂i的产收点发点量，dj是市场j的需求量。114312312312A343332312423222114131211xxxxxxxxxxxxXb=(604050)d=(20353334)3141minijijijxafs.t3,2,141ibxijij4,3,2,131jdxijijxij≥0编写程序：AA=[2132;1321;3411];f=AA(:);A=[100100100100010010010010001001001001];Aeq=[111000000000000111000000000000111000000000000111];b=[60;40;50];beq=[20;35;33;34];lb=zeros(12,1);[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb)运行结果：x=0.000020.00000.000035.00000.00000.00000.00000.000033.00000.000018.468215.5318fval=122.0000exitflag=1即运输方案为：甲市场的货由B厂送20箱；乙市场的货由A厂送35箱；丙商场的货由C厂送33箱；丁市场的货由B厂送18箱，再由C厂送16箱。最低总运费为：122元。20-1整数规划求极值形如：minfTXs.tAX≤bAeqX=beqxi为0或1其中X为n维未知向量，fT=[f1,f2,…fn]为目标函数系数向量，小于等于约束系数矩阵A为m×n矩阵，b为其右端m维列向量，Aeq为等式约束系数矩阵，beq为等式约束右端常数列向量。lb,ub为自变量取值上界与下界约束的n维常数向量。2.1分支定界法在Matlab中提供了bintprog函数实现0-1型线性规划，采用的是分支定界法原理，其调用格式如下：x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)[x,fval]=bintprog(…)[x,fval,exitflag]=bintprog(…)[x,fval,exitflag,output]=bintprog(…)[x,fval,exitflag,output,lambda]=bintprog(…)说明：x=bintprog(f,A,b)返回值x为最优解向量。x=bintprog(f,A,b,Aeq,beq)作有等式约束的问题。若没有不等式约束，则令A=[]、b=[]。[x,fval]=bintprog(…)左端fval返回解x处的目标函数值。【例6】求解以下问题：maxz=x1+1.2x2+0.8x3st2.1x1+2x2+1.3x3=50.8x1+x2=5x1+2.5x2+2x3=82x2=8x1,x2,x3为0或1解答:首先，将其改变成0-1整数规划函数bintprog要求的标准形式：minz=-x1-1.2x2-0.8x3st2.1x1+2x2+1.3x3=50.8x1+x2=5x1+2.5x2+2x3=82x2=8x1,x2,x3为0或1Matlab求解：c=[-1,-1.2,-0.8];A=[2.1,2,1.3;0.8,1,0;1,2.5,2;0,2,0];b=[5;5;8;8];[x,fval]=bintprog(c,A,b);xfmax=-fval运行结果可得：x=110fmax=2.2000【例7】某快餐连锁经营公司有7个地点（A1，A2，---，A7）可以设立快餐店，由于地理位置因素，设立快餐店时必须满足以下要求：A1，A2，A3三个地点最多可选两个，A1和A5至少选取一个，A6和A7至少选取一个。已知各个地点设立快餐店的投入和预计收益如表所示。已知目前公司有650万元可以投资。问怎样投资才能使公司预计收益最高？地点A1A2A3A4A5A6A7利润/万元101181215125投资/万元1031409515019316080解：这是一个选址问题。首先引入0-1变量