MATLAB在线性规划中的应用

《MATLAB》课程论文MATLAB在线性规划中的应用姓名：马福蕊学号：12010245317专业：通信工程指导老师：汤全武学院：物理电气信息学院完成日期：2011.12.7MATLAB在线性规划中的应用（马福蕊12010245317通信工程（1）班）【摘要】在各类经济活动中，经常遇到这样的问题：在生产条件不变的情下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”（LinearProgramming，简记为LP）问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益（产量最多、利润最大、效用最高）。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成任务。常规的手工解法复杂且运算量大，而MATLAB语言可以很好的处理线性规划问题，既能进行数值的求解，又能绘制有关线性图形，非常方便实用，利用其可以减少工作量，节约时间，加深理解，同样可以培养应用能力。【关键词】线性规划优化求解MATLAB语言一、线性规划问题的在实际中的应用1、线性规划问题的在实际应用中的作用任何资源都是有限的，如何通过分配有限的资源获得人们所期望的效果，在工农业生产、交通运输、资本增值等各项经济活动中，如何提高经济效益，做到耗费较少的人力物力财力，创造出较多的经济价值，这些问题涉及分配，而线性规划为最优分配提供了工具。2、线性规划主要研究的两类问题一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用它们，使得完成任务最多。常见的线性规划问题如：运输问题，生产的组织与计划问题，合力下料问题，配料问题、布局问题、分派问题等。二、MATLAB在线性规划中的应1.MATLAB在线性规划中的指令线性规划是一种优化方法，Matlab优化工具箱中有现成函数linprog对如下式描述的LP问题求解：%minf'x%s.t.(约束条件)：Ax=b%(等式约束条件)：Aeqx=beq%lb=x=ublinprog函数的调用格式如下：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(…)2、相关说明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的线性等式。三、运用MATLAB解决线性规划问题的实例对于给定的实际问题，首先是要建立线性规划问题的数学模型，其次是求问题的最优解。1、直接运用MATLAB编程计算求解线性规划问题线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为112211112211211222221122,min...,,···0(1,2,,).nnnnnnmmmnnmizfxfxfxstaxaxaxbaxaxaxbaxaxaxbxin（1）极小值模型112211112211211222221122max...,,,0(1,2,,).nnnnnnmmmnnmizfxfxfxstaxaxaxbaxaxaxbaxaxaxbxin（2）极大值模型利用矩阵与向量记为min..0TzCxstAxbx（3）其中C和x为n维列向量，b为m维列向量，b≥0，A为m×n矩阵,mn且rank(A)=m。如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式：（1）若目标函数为maxTzCx，可将它化为minTzCx(2）若第i个约束为11iinniaxaxb，可增加一个松驰变量iy，将不等式化为11iinniiaxaxyb，且iy0。若第i个约束为ai1x1+…+ainxnbi，可引入剩余量iy，将不等式化为ai1x1+…+ainxn－yi=bi，且yi0。（3）若xi为自变量，则可令iiixxx,其中ix、ix0。问题一、某牧场饲养一批动物，平均每头动物至少需要700g蛋白质，30g矿物质和100g维生素。现有A,B,C,D,E五种饲料可供选用，每千克饲料的营养成分（单位：g）与价格（单位：元/kg）如下表所示：表1每千克饲料的营养成分（单位：g）与价格（单位：元/kg）蛋白质矿物质维生素价格A31.00.50.4B20.51.01.4C10.21.20.8D62.02.01.6E120.50.81.6试求能满足动物生长营养需求又最经济的选用饲料方案。设配合饲料中，用A种饲料1x单位，用B种饲料2x单位，用C种饲料3x单位，用D种饲料4x单位，用E种饲料5x单位，则配合饲料的原料成本函数，即决策的目标函数为Z。考虑三种营养含量限制条件后，得这一问题的线性规划模型如下目标函数：543216.16.18.04.14.0xxxxxMinz（4）约束条件为：12345123451234532612700..1.00.50.22.00.5300.51.01.22.00.8100xxxxxstxxxxxxxxxx（5）编写M文件如下：c=[0.4;1.4;0.8;1.6;1.6];%产生有五个元素的列向量cA=[-3,-2,-1,-6,-12;-1.0,-0.5,-0.2,-2.0,-0.5;-0.5,-1.0,-1.2,-2.0,-0.8];%约束条件中的变量系数构成的矩阵Ab=[-700;-30;-100];%约束条件中的上下界构成的列向量Aeq=[];%没有等式约束beq=[];%没有等式约束vlb=zeros(5,1);%生成一个五行一列的零矩阵[x,fval,eval]=linprog(c,A,b,Aeq,beq，vlb)%调用linprog函数可得到如下结果：Optimizationterminated.x=224.71150.00000.00000.00002.1555fval=93.3333从以上结果可以看出，买224.7115千克的A饲料，2.1555千克的E饲料，能满足动物生能满足动物生长营养需求又最经济，所用价钱为93.3333元。问题二、某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解：设需要一级和二级检验员的人数分别为1x、2x人,则应付检验员的工资为：212124323848xxxx（6）因检验员错检而造成的损失为：21211282)%5158%2258(xxxx（7）故目标函数为：213640minxxz（8）约束条件为：0,01594535..212121xxxxxxts（9）编写M文件如下：c=[40;36];%产生有两个元素的列向量cA=[-5-3];%约束条件中的变量系数构成的矩阵Ab=[-45];%约束条件中的上下界构成的列向量Aeq=[];%没有等式约束beq=[];%没有等式约束vlb=zeros(2,1);%生成一个两行一列的零矩阵（含两个零的列向量）下界vub=[9;15];%上界[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)%调用linprog函数x=9.00000.0000fval=360即只需聘用9个一级检验员。问题三、某农场I、II、III等耕地的面积分别为100hm2、300hm2和200hm2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为190000kg、130000kg和350000kg。I、II、III等耕地种植三种作物的单产如表5.1.4所示。若三种作物的售价分别为水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg。那么，（1）如何制订种植计划，才能使总产量最大？（2）如何制订种植计划，才能使总产值最大表2不同等级耕地种植不同作物的单产(单位:kg/hm2)I等耕地II等耕地III等耕地水稻1100095009000大豆800068006000玉米140001200010000首先根据题意建立线性规划模型（决策变量设置如表2所示，表中ijx表示第i种作物在第j等级的耕地上的种植面积。）：表3作物计划种植面积（单位:hm2)I等耕地II等耕地III等耕地水稻11x12x13x大豆21x22x23x玉米31x32x33x约束方程如下：耕地面积约束：200xxx300xxx100xxx332313322212312111（10）最低收获量约束：-35000010000x12000x14000x-00003-10x0066800x8000x--1900009000x9500x11000x-333231232221131211（11）非负约束：1,2,3)j1,2,3;(i0xij(1)追求总产量最大，目标函数为：33323123222113121110000x12000x14000x-0x0066800x8000x-9000x9500x-11000x=minZ