应用LINGO、MATLAB软件求解线性规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.5,应用,LINGO,、,MATLAB,软件求解线性规划,1.5.1,应用,LINGO,软件求解线性规划,一、,LINGO,使用简介,LINGO,软件是美国的,LINDO,系统公司（,Lindo,System Inc,）开发的一套用于求解最优化问题的软件包。,LINGO,除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解等。,LINGO,软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快。,LINGO,内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用,LINGO,高效的求解器可快速求解并分析结果，这里简单介绍,LINGO,的使用方法。,LINGO,可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等。,一个,LINGO,程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者,LINGO,的,HELP,文件详细了解，这里就不展开介绍了。,LINGO,的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为,LINGO,模型；并且能方便地与,Excel,、数据库等其他软件交换数据。,LINGO,的语法规定：,（,1,）求目标函数的最大值或最小值分别用,MAX=,或,MIN=,来表示；,（,2,）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；,（,3,）变量名称必须以字母,(AZ),开头，由字母、数字,(09),和下划线所组成，长度不超过,32,个字符，不区分大小写；,（,4,）可以给语句加上标号，例如,OBJMAX=200*X1+300*X2,；,（,5,）以惊叹号“！”开头，以分号“；”结束的语句是注释语句,;,（,6,）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；,（,7,）,LINGO,模型以语句“,MODEL,：”开头，以“,END”,结束，对于比较简单的模型，这两个语句可以省略。,在,LINGO,的,MODEL,窗口内输入如下模型：,model:,max=2*x1+3*x2;,x1+2*x2=8;,4*x1=16;,4*x260;,0.1*x1+0.05*x2+0.02*x3+0.2*x4+0.05*x53;,0.05*x1+0.1*x2+0.02*x3+0.2*x4+0.08*x58;,X1+x2+x3+x4+x552;,例,1.5.2,用,LINGO,求解例,1.1.3,食谱问题。,解 例,1.1.3,食谱问题的数学模型为（,1.1.6,）,求解输出结果如下,:,Global optimal solution found at iteration:4,Objective value:22.40000,Variable Value Reduced Cost,X1 0.000000 0.7000000,X2 12.00000 0.000000,X3 0.000000 0.6166667,X4 30.00000 0.000000,X5 10.00000 0.000000,Row Slack or Surplus Dual Price,1 22.40000 -1.000000,2 0.000000 -0.5833333,3 4.100000 0.000000,4 0.000000 -4.166667,5 0.000000 0.8833333,因此,每周每个动物的配料为饲料,A,2,、,A,4,、,A,5,分别为,12,、,30,和,10,，合计为,52,，可使得饲养成本达到最小，最小成本为,22.4,元；不选用饲料和的原因是因为这两种饲料的价格太高了，没有竞争力。“,Reduced Cost,”,分别等于,0.7,和,0.617,，说明当这两种饲料的价格分别降低,0.7,元和,0.62,元以上时，不仅选用这两种饲料而且使得饲养成本降低。从“,Slack or Surplus”,可以看出，蛋白质和维生素刚达到最低标准，矿物质超过最低标准,4.1,；从“,Dual Price”,可以得到降低标准蛋白质,1,单位可使饲养成本降低,0.583,元，降低标准维生素,1,单位可使饲养成本降低,4.167,元，但降低矿物质的标准不会降低饲养成本，如果动物的进食量减少，就必须选取精一些的饲料但要增加成本，大约进食量降低,1,可使得饲养成本增加,0.88,元。,(1.5.1),1.5.2,应用,MATLAB,求解线性规划,MATLAB,（,MATrix,LABoratory,）的基本含义是矩阵实验室，它是由美国,MathWorks,公司研制开发的一套高性能的集数值计算、信息处理、图形显示等于一体的可视化数学工具软件。它是建立在向量、数组和矩阵基础之上的，除了基本的数值计算、数据处理、图形显示等功能之外，还包含功能强大的多个“工具箱”，如优化工具箱（,optimization toolbox,）、统计工具箱、样条函数工具箱和数据拟合工具箱等都是优化计算的有力工具。在这里仅介绍用,MATLAB6.5,优化工具箱求解线性规划问题。,一般线性规划问题的数学模型为,其中,C,是目标函数的系数行向量（常数）,X,是,n,维列向量（决策变量），,A,A,1,是常数矩阵，,b,b,1,是常数向量，,lb,ub,是,n,维列向量分别表示决策变量,X,的下界与上界。,在,Matlab,优化工具箱（,Optimization Toolbox,）中，求解,(1.5.1),的程序如下：,x,，,fval,，,exitflag,，,output,，,lambda=,linprog,(c,，,A,，,b,，,Aeq,，,beq,，,lb,，,ub,，,x0,，,options),说明：,(1)A,是不等式约束的系数矩阵，,b,是相应的常数列向量，若没有不等式约束，则均用,代替；,(2),Aeq,是等式约束的系数矩阵，,beq,是相应的常数列向量，若没有等式约束，则均用,代替；,(3),如果某个变量无下界，则用,-,inf,表示；如果某个变量无上界，则用,inf,表示，若决策变量 无下界，则,lb,用,代替；若决策变量 无上界，则,ub,用,代替；,(4)x0,是线性规划的初始解，这种设计仅对中规模算法有效，通常可以缺省。,(5),输出 是最优解，,fval,是最优值。,(6),输出,exitflag,描述了程序的运行情况，若其值大于零，表示程序收敛到最优解 ；若其值等于零，表示计算达到了最大次数；若其值小于零，表示问题无可行解，或程序运行失败。,(7),输出,output,表示程序运行的某些信息，如迭代次数,(iterations),、所用算法,(algorithm),、共轭梯度,(,cgiterations,),等。,(8)lambda,表示解处的拉格朗日乘子，其中,lower,，,upper,，,ineqlin,，,eqlin,分别对应于下界、上界、不等式约束与等式约束。,例,1.5.3,用,MATLAB,解线性规划问题,(,1.5.2,),解,Matlab,程序如下,:,c=-2,-1,1;,A=1,4,-1;2,-2,1;,b=4;12;,Aeq,=1,1,2;,beq,=6;,lb=0,0,-inf;,ub,=inf,inf,5;,x,z,=,linprog(c,A,b,Aeq,beq,lb,ub,),运行后得到输出,Optimization terminated successfully.,x=,4.6667,0.0000,0.6667,z,=,-8.6667,例,1.5.4,用,MATLAB,求解线性规划问题,（,1.5.3,）,解,首先转化为求最小值问题,Matlab,程序如下,c=-2,-3,5;,A=-2,5,-1;,b=-10;,Aeq,=1,1,1;,beq,=7;,lb=0,0,0;,x,z,=,linprog(c,A,b,Aeq,beq,lb,),运行后得到输出,x=,6.4286,0.5714,0.0000,z=,-14.5714,键入,s=-z,运行后得到原问题的目标函数最大值,s=14.5714,用,MATLAB,求解例,1.5.2,的程序与输出结果为：,c=0.2,0.7,0.4,0.3,0.5;,A=-0.3,-2,-1,-0.6,-1.8;-0.1,-0.05,-0.02,-0.2,-0.05;-0.05,-0.1,-0.02,-0.2,-0.08;1,1,1,1,1;,b=-60;-3;-8;52;,lb=0,0,0,0,0;,x,z,=,linprog(c,A,b,lb,),Optimization terminated successfully.,x=,0.0000,12.0000,0.0000,30.0000,10.0000,z=,22.4000,习题,1,1.,建立下列线性规划问题的数学模型,（,1,）某工厂生产,A,、,B,、,C,三种产品，三种产品对于材料费用、劳动力和电力的单位消耗系数，资源限量和单位产品价格如表,1.1,所示。问应如何确定生产计划可使得总产值达到最大？建立线性规划问题的数学模型。,表,1.1,生产计划问题的数据,产品,资源,A,B,C,资源限量,材料费用（元）,2,2.5,4,320,劳动力（人天）,6,1,8,640,电力（度）,5,5,10,750,单位价格（百元）,6,4,10,（,2,）某疗养院营养师要为某类病人拟订一周的菜单。可供选择的蔬菜及其费用和所含营养成分的数量以及这类病人每周所需各种营养成分的最低数量如表,1.2,所示。另外，为了口味的需要，规定一周内所用卷心菜不多于,2,份，其他蔬菜不多于,4,份。若病人每周需要,14,份蔬菜，问选用每种蔬菜各多少份，可使生活费用最小。建立线性规划问题的数学模型。,表,1.2,食谱问题的数据,蔬菜,每份蔬菜所含营养成分,费用,（元,/,份）,铁,(mg),磷,(mg),VA(,单位,),VC(mg,),烟酸,(mg),青豆,0.45,10,415,8,0.3,1.5,胡萝卜,0.45,28,9065,3,0.35,1.5,花菜,1.05,50,2550,53,0.6,2.4,卷心菜,0.4,25,75,27,0.15,0.6,甜菜,0.5,22,15,5,0.25,1.8,土豆,0.5,75,235,8,0.8,1.0,每周营养,最低需求量,6.0,325,17500,245,5.0,播种计划表,亩产量表,土地作物,作物面积,100,600,700,500,500,800,500,850,400,400,150,300,土地面积,200,300,500,（,4,）某糖果厂用原料,A,、,B,、,C,加工成三种不同牌号的糖果甲、乙、丙，已知各种牌号的糖果中,A,、,B,、,C,的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表,1.4,所示，问该厂每月应生产这三种牌号的糖果各多少千克，使该厂获利最大？试建立这个问题的线性规划数学模型。,甲,乙,丙,原料成本,(,元,/,千克,),每月限制用量,（千克）,A,8.00,2000,B,6.00,2500,C,4.00,1200,加工费,（元,/,千克）,2.0,1.6,1.2,售价（元）,13.6,11.4,9,表,1.4,糖果厂生产计划数据表,0.0,0.5,1.0,1.5,1.9,2.5,3.0,3.5,4.0,4.5,1.0,0.9,0.7,1.5,2.0,2.4,3.2,2.0,2.7,3.5,5.0,5.5,6.0,6.6,7.0,7.6,8.5,9.0,10.0,1.0,4.0,3.6,2.7,5.7,4.6,6.0,6.8,7.3,表,1.5,随 变化的数据表,求拟合以上数据的直线 ，目标为使,y,的各个观察值同按直线关系所预期的值的绝对偏差总和为最小（即：误差绝对值之和最小）。建立线性规划问题的数学模型。,（提示：对任意的 ，令：,那么，）,2.,将下列线性规划问题化成标准形,(1),(2),3.,用图解法求解下列线性规划问题,(1),(2),(3),(4),(5),4.,试将下述问题改写成线性规划问题,8.,用单纯形方法求解下列线性规划问题,(1),(2),(3),(4),9,某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗、资源的限制和每单位产品的获利如表,1.6,。问工厂应分别生产甲、乙产品多少单位才能使工厂获利最大？建立线性规划问题数学模型，并用单纯形方法求出最优解。,产品,资源,甲,乙,资源限制,设备,1,1,300,台时,原料,A,2,1,400,千克,原料,B,0,1,250,千克,单位产品获利,50,元,100,元,表,1.6,资源配置问题的数据,10.,对于线性规划问题：,（,1,）求该线性规划问题的全体基本最优解；,（,2,）确定任意最优解的表达式。,11.,用两阶段法求解线性规划问题。,(1),(2),(3),(4),12.,某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗，以及资源的限制和每单位产品的获利如下表,1.7,。问工厂应分别生产甲、乙产品多少单位才能使工厂获利最大？对应的最大利润是多少？建立线性规划问题的数学模型，并用单纯形方法求出所有的基础最优解。,产品,资源,甲,乙,资源限制,设备,1,1,300,台时,原料,A,2,1,400,千克,原料,B,0,1,250,千克,单位产品获利,50,元,50,元,表,1.7,资源配置问题的数据,13.,考虑下述线性规划问题,14,用,LINGO,和,MATLAB,求解本章习题中的线性规划问题。,