MATLAB在线性规划中的应用

MATLAB在线性规划中的应用摘要在各类经济活动中，经常遇到这样的问题：在生产条件不变的情下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”（LinearProgramming，简记为LP）问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益（产量最多、利润最大、效用最高）。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成任务。常规的手工解法复杂且运算量大，而MATLAB语言可以很好的处理线性规划问题，既能进行数值的求解，又能绘制有关线性图形，非常方便实用，利用其可以减少工作量，节约时间，加深理解，同样可以培养应用能力。关键词:线性规划优化求解MATLAB语言一、线性规划问题的在实际中的应用线性规划问题的在实际应用中的作用任何资源都是有限的，如何通过分配有限的资源获得人们所期望的效果，在工农业生产、交通运输、资本增值等各项经济活动中，如何提高经济效益，做到耗费较少的人力物力财力，创造出较多的经济价值，这些问题涉及分配，而线性规划为最优分配提供了工具。线性规划主要研究的两类问题一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用它们，使得完成任务最多。常见的线性规划问题如：运输问题，生产的组织与计划问题，合力下料问题，配料问题、布局问题、分派问题等。MATLAB在线性规划中的应用1.MATLAB在线性规划中的指令线性规划是一种优化方法，Matlab优化工具箱中有现成函数linprog[1]对如下式描述的LP问题求解：%minf'x%s.t.(约束条件)：Ax<=b%(等式约束条件)：Aeqx=beq%lb<=x<=ub linprog函数的调用格式如下：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为指定优化参数进行最小化。Options的参数描述：Display显示水平；选择’off’不显示输出；选择’Iter’显示每一步迭代过程的输出；选择’final’显示最终结果。MaxFunEvals函数评价的最大允许次数。Maxiter最大允许迭代次数。TolXx处的终止容限。[x,fval]=linprog(…)左端fval返回解x处的目标函数值。[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beg,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解决线性规划问题的实例对于给定的实际问题，首先是要建立线性规划问题[2]的数学模型，其次是求问题的最优解。1、直接运用MATLAB编程计算求解线性规划问题线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为（1）极小值模型（2）极大值模型利用矩阵与向量记为（3）其中C和x为n维列向量，b为m维列向量，b≥0，A为m×n矩阵,m<n且rank(A)=m。如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式：（1）若目标函数为，可将它化为(2）若第i个约束为，可增加一个松驰变量，将不等式化为，且0。 若第i个约束为ai1x1+…+ainxnbi，可引入剩余量，将不等式化为ai1x1+…+ainxn－yi=bi，且yi0。（3）若xi为自变量，则可令,其中、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种饲料单位，用B种饲料单位，用C种饲料单位，用D种饲料单位，用E种饲料单位，则配合饲料的原料成本函数，即决策的目标函数为Z。考虑三种营养含量限制条件后，得这一问题的线性规划模型[3]如下目标函数：（4）约束条件为：（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元。问题二、某农场I、II、III等耕地的面积分别为100hm2、300hm2和200hm2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为190000kg、130000kg和350000kg。I、II、III等耕地种植三种作物的单产如表5.1.4所示。若三种作物的售价分别为水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg表2不同等级耕地种植不同作物的单产(单位:kg/hm2)I等耕地II等耕地III等耕地水稻1100095009000大豆800068006000玉米140001200010000首先根据题意建立线性规划模型（决策变量设置如表2所示，表中表示第种作物在第j等级的耕地上的种植面积。）：表3作物计划种植面积（单位:hm2)I等耕地II等耕地III等耕地水稻大豆玉米约束方程[4]如下：耕地面积约束：（6）最低收获量约束：（7）非负约束：追求总产量最大，目标函数为：（8）追求总产值最大，目标函数为：（9）根据求解函数linprog中的参数含义，列出系数矩阵，目标函数系数矩阵，以及约束条件等。这些参数中没有的设为空。譬如，当追求总产量最大时，只要将参数f=[-11000–9500–9000–8000–6800–6000–14000–12000-10000];A=[1.00000.00000.00001.00000.00000.00001.00000.00000.0000;0.00001.00000.00000.00001.00000.00000.00001.00000.0000;0.00000.00001.00000.00000.00001.00000.00000.00001.0000;-11000.00000.00000.0000-9500.00000.00000.0000-9000.00000.00000.0000;0.0000-8000.00000.00000.0000-6800.00000.00000.0000-6000.00000.0000;0.00000.0000-14000.00000.00000.0000-12000.00000.00000.0000-10000.0000];b=[100300200-190000-130000-350000];lb=[0.00000.00000.00000.00000.00000.00000.00000.00000.0000];代入求解函数，即可得到求解结果。运用MATLAB的图解法求解线性规划问题若一个线性规划问题有最优解，则最优解一定可以在可行域的某个极点上找到一个最优解。同时仍有可能有其他最优解存在，但它们也只可能存在于可行域的其他极点或是边界上。如果我们的目的是找出一个最优解而不是全部最优解，这一定理实际上是把寻找的范围，从可行域中的无穷多个可行点，缩小到可行域的有限几个极点上。[5]问题一、某农户有耕地20公顷，可采用甲乙两种种植方式。甲种植方式每公顷需投资280元，每公顷投工6个，可获收入1000元，乙方式每公顷需投资150元，劳动15个工日，可获收入1200元，该户共有可用资金4200元、240个劳动工日。问如何安排甲乙两种方式的生产，可使总收入最大?解：设甲方式种公顷，乙方式种公顷，总收入为Z，则有：（13）图问题一线性规划图解所以，如图所示，在B点时，甲级两种方式的总收入最大，即甲方式种6.7公顷，乙方式种13.3公顷。结论1、由于将线性规划问题化为标准形式之后的约束条件是一个非齐次线性方程组，故当考虑LP问题的解时，首先可以考虑非齐次线性方程组的解，然后再考虑目标函数的解最大、最小值问题。单纯形法是求解LP问题的一种常用方法，但单纯形法的运算量比较大，当约束条件中的约束变量比较多时，效费比就比较低，因此借助计算机软件的强大运算功能，既节约时间又提高了运算的准确性，对于一般的线性规划问题，应用excel、MATLAB都可以轻松解决，但MATLAB的整数线性规划运算功能欠缺，此时可以应用lingo、excel软件解决这类问题。2、在接触MATLAB之后,我发现MATLAB语法简单,易于绘制图形,编程也非常容易.并且有功能强大的开放式的toolbox。MATLAB是功能强大的科学及工程计算软件,它不但具有矩阵计算为基础的强大数学计算和分析功能,而且还具有丰富的可视化图形表现功能和方便的程序设计能力。3、对于MATLAB自带函数的问题,要多利用MATLAB的帮助功能,例如:对于某些不是很明确的命令,只知道大体的所属范围,譬如说某个工具箱,直接在命令窗口中敲入helptoolboxname.可以这么说任何问题都可以在MATLAB帮助里找到解决方法,问题不论大小