线性规划模型目标函数ppt课件

.,1,线性规划,.,2,线性规划内容,一、线性规划模型二、线性规划模型的标准形式三、用matlab解线性规划,.,3,线性规划所解决的问题具有以下共同的特征：,2.存在一定的限制条件（即约束条件），这些限制条件是关于未知数的一组线性等式或线性不等式来表示。,1.每一个问题都用一组未知数（x1，x2，xn）表示某一方案；这些未知数的一组定值就代表一个具体方案。由于实际问题的要求，通常这些未知数取值是非负的。,3.有一个目标要求，称为目标函数。目标函数可表示为一组未知数的线性函数。根据问题的需要，需求目标函数实现最大化或最小化。,一、线性规划模型,.,4,一般的线性规划问题的数学模型：目标函数(线性函数）：Min(max)z=c1x1+c2x2+cnxn,约束条件(s.t.)：a11x1+a12x2+a1nxn()b1a21x1+a22x2+a2nxn()b2.am1x1+am2x2+amnxn()bmx1，x2，xn0式中()可以是关系符号：,=,中的任意一个。,二、线性规划模型的标准形式,.,16,实际问题中的优化模型,x是决策变量,f(x)是目标函数,gi(x)0是约束条件,数学规划,线性规划(LP)二次规划(QP)非线性规划(NLP),纯整数规划(PIP)混合整数规划(MIP),整数规划(IP),0-1整数规划一般整数规划,连续规划,优化模型的分类,.,17,线性规划标准型的特点：,1、目标函数是Min（最小化）；2、约束条件为等式；3、决策变量为非负数；4、右端常数要求为非负数。,.,18,三、用matlab解线性规划基本用法,用MATLAB优化工具箱求解线性规划时不要求一定化为标准形，而是要求化为如下形式：,下一页,.,19,线性规划的矩阵表示,.,20,用MATLAB解线性规划,命令：x=linprog（c,A,b）x,fval=linprog()返回最优解及处的目标函数值fval,2.模型：minz=cX,命令：x=linprog（c，A，b，A1,b1）,注意：若没有不等式：存在，则令A=，b=.,.,21,命令：1x=linprog（c，A，b，A1,b1,V1，V2）2x=linprog（c，A，b，A1,b1,V1，V2,X0）,注意：1若没有等式约束:,则令A1=,b1=。若v1=zeros(2,1),表示2行1列的零矩阵。2其中X0表示初始点,.,22,解编写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.03,0,0,0.08;b=850;700;100;900;A1=;b1=;v1=0;0;0;0;0;0;v2=;x,fval=linprog(c,A,b,A1,b1,v1,v2),.,23,Optimizationterminatedsuccessfully.x=1.0e+004*3.50000.50003.00000.00000.00000.0000fval=-2.5000e+004,.,24,.,25,解Matlab程序如下:c=-2,-1,1;A=1,4,-1;2,-2,1;b=4;12;A1=1,1,2;b1=6;v1=0,0,-inf;v2=inf,inf,5;x,z=linprog(c,A,b,A1,b1,v1,v2)运行后得到输出Optimizationterminatedsuccessfully.x=4.66670.00000.6667z=-8.6667,.,26,例3用MATLAB求解线性规划问题,解首先转化为求最小值问题,.,27,Matlab程序如下c=-2,-3,5;A=-2,5,-1;b=-10;A1=1,1,1;b2=7;v1=0,0,0;x,z=linprog(c,A,b,A1,b1,v1),运行后得到输出x=6.42860.57140.0000z=-14.5714键入s=-z运行后得到原问题的目标函数最大值s=14.5714,.,28,解:编写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),.,29,Optimizationterminatedsuccessfully.x=30.000050.000040.0000fval=490.0000,.,30,例5：任务分配问题：某车间有甲、乙两台车床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,.,31,解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：目标函数：约束条件：,解答,.,32,问题,.,33,编写如下:c=13,9,10,11,12,8;A=0.4,1.1,1,0,0,0;0,0,0,0.5,1.2,1.3;b=800;900;A1=1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1;b1=400,600,500;vl=zeros(6,1);v2=;x,fval=linprog(c,A,b,A1,b1,v1,v2),.,34,结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.,.,35,例6：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：,因检验员错检而造成的损失为：,.,36,线性规划模型：目标函数：,.,37,编写如下：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),.,38,结果为：x=9.00000.0000fval=360即只需聘用9个一级检验员.,注：本问题应还有一个约束条件：x1、x2取整数.故它是一个整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.,返回,.,39,习题1.建立下列线性规划问题的数学模型（1）某工厂生产A、B、C三种产品，三种产品对于材料费用、劳动力和电力的单位消耗系数，资源限量和单位产品价格如表1.1所示。问应如何确定生产计划可使得总产值达到最大？建立线性规划问题的数学模型。,表1.1生产计划问题的数据,.,40,（2）某疗养院营养师要为某类病人拟订一周的菜单。可供选择的蔬菜及其费用