MATLAB在线性规划中的应用

1、MATLAB课程论文 MATLAB在线性规划中的应用姓名：马福蕊 专业：通信工程 指导老师：汤全武 学院：物理电气信息学院 完成日期：2011.12.7 MATLAB在线性规划中的应用【摘要】在各类经济活动中，经常遇到这样的问题：在生产条件不变的情下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”（Linear Programming，简记为LP）问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划

2、我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益（产量最多、利润最大、效用最高）。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成任务。常规的手工解法复杂且运算量大，而MATLAB语言可以很好的处理线性规划问题，既能进行数值的求解，又能绘制有关线性图形，非常方便实用，利用其可以减少工作量，节约时间，加深理解，同样可以培养应用能力。【关键词】线性规划 优化求解 MATLAB语言1、 线性规划问题的在实际中的应用 1、 线性规划问题的在实际应用中的作用

3、任何资源都是有限的，如何通过分配有限的资源获得人们所期望的效果，在工农业生产、交通运输、资本增值等各项经济活动中，如何提高经济效益，做到耗费较少的人力物力财力，创造出较多的经济价值，这些问题涉及分配，而线性规划为最优分配提供了工具。2、 线性规划主要研究的两类问题一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用它们，使得完成任务最多。 常见的线性规划问题如：运输问题，生产的组织与计划问题，合力下料问题，配料问题、布局问题、分派问题等。2、 MATLAB在线性规划中的应 1.MATLAB在线性规划中的指令线性规划是一种优化

4、方法，Matlab优化工具箱中有现成函数linprog对如下式描述的LP问题求解：% min f'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,

5、 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显示水平。 选

6、择off 不显示输出；选择Iter显示每一 步迭代过程的输出；选择final 显示最终结果。MaxFunEvals 函数评价的最大允许次数。Maxiter 最大允许迭代次数。TolX x处的终止容限。x,fval=linprog() 左端 fval 返回解x处的目标函数值。x,fval,exitflag,output,lambda=linprog(f,A,b, Aeq,beq,lb,ub,x0) 的输出部分： exitflag 描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。output 返回优化信息：o

7、utput.iterations表示迭代次数；output.algorithm表示所采用的算法；outprt.funcCount表示函数评价次数。lambda 返回x处的拉格朗日乘子。它有以下属性：lambda.lower-lambda的下界；lambda.upper-lambda的上界；lambda.ineqlin-lambda的线性不等式；lambda.eqlin-lambda的线性等式。 三、运用MATLAB解决线性规划问题的实例 对于给定的实际问题，首先是要建立线性规划问题的数学模型， 其次是求问题的最优解。1、直接运用MATLAB编程计算求解线性规划问题 线性规划的目标函数可以是求最

8、大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为 （1）极小值模型 （2） 极大值模型 利用矩阵与向量记为 （3） 其中C 和x为n 维列向量，b为m 维列向量，b0，A为m×n矩阵,m<n且rank(A)=m。如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式： （1）若目标函数为，可将它化为 (2）若第i个约束为，可增加一个松驰变量，将不等式化为 ，且0。若第i个约束为ai1x1+ainxnbi，可引入剩余量，将

9、不等式化为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种饲料单位，

10、用C种饲料单位，用D种饲料单位，用E种饲料单位，则配合饲料的原料成本函数，即决策的目标函数为Z。考虑三种营养含量限制条件后，得这一问题的线性规划模型如下目标函数： （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

11、,1); %生成一个五行一列的零矩阵x,fval,eval = linprog(c,A,b,Aeq,beq，vlb) %调用linprog函数 可得到如下结果：Optimization terminated.x = 224.7115 0.0000 0.0000 0.0000 2.1555fval = 93.3333 从以上结果可以看出，买224.7115千克的A饲料，2.1555千克的E饲料，能满足动物生能满足动物生长营养需求又最经济，所用价钱为93.3333元。 问题二、某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时

12、，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？ 解：设需要一级和二级检验员的人数分别为、人,则应付检验员的工资为： （6）因检验员错检而造成的损失为： （7） 故目标函数为： （8）约束条件为： （9）编写M文件如下：c = 40;36; %产生有两个元素的列向量cA=-5 -3; %约束条件中的变量系数构成的矩阵Ab=-45; %约束条件中的上下界构成的列向量Aeq=; %没有等式约束beq=; %没有等式约束 vlb = zeros(2,1)

13、; %生成一个两行一列的零矩阵（含两个零的列向量）下界 vub=9;15; %上界 x,fval = linprog(c,A,b,Aeq,beq,vlb,vub) %调用linprog函数x = 9.0000 0.0000fval =360即只需聘用9个一级检验员。问题三、某农场I、II、III等耕地的面积分别为100 hm2、300 hm2和200 hm2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为190000kg、130000kg和350000kg。I、II、III等耕地种植三种作物的单产如表所示。若三种作物的售价分别为水稻1.20元/kg，大豆1.50元/kg，玉米0.80

14、元/kg。那么，（1）如何制订种植计划，才能使总产量最大？（2）如何制订种植计划，才能使总产值最大 表2 不同等级耕地种植不同作物的单产(单位:kg / hm2)I等耕地II等耕地III等耕地水稻11 0009 5009 000大豆8 0006 8006 000玉米14 00012 00010 000首先根据题意建立线性规划模型（决策变量设置如表2所示，表中表示第种作物在第j等级的耕地上的种植面积。）：表3 作物计划种植面积（单位:hm2)I等耕地II等耕地III等耕地水稻大豆玉米约束方程如下：耕地面积约束： （10）最低收获量约束： （11）非负约束： (1) 追求总产量最大，目标函数为：

15、（12）（2） 追求总产值最大，目标函数为： （13）根据求解函数linprog中的参数含义，列出系数矩阵，目标函数系数矩阵，以及约束条件等。这些参数中没有的设为空。譬如，当追求总产量最大时，只要将参数f=-11000 9500 9000 8000 6800 6000 14000 12000 -10000;A=1.0000 0.0000 0.0000 1.0000 0.0000 0.0000 1.0000 0.0000 0.0000; 0.0000 1.0000 0.0000 0.0000 1.0000 0.0000 0.0000 1.0000 0.0000; 0.0000 0.0000 1.

16、0000 0.0000 0.0000 1.0000 0.0000 0.0000 1.0000; -11000.0000 0.0000 0.0000 -9500.0000 0.0000 0.0000 -9000.0000 0.0000 0.0000; 0.0000 -8000.0000 0.0000 0.0000 -6800.0000 0.0000 0.0000 -6000.0000 0.0000; 0.0000 0.0000 -14000.0000 0.0000 0.0000 -12000.0000 0.0000 0.0000 -10000.0000;b=100 300 200 -190000

17、 -130000 -350000;lb=0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 ; 代入求解函数，即可得到求解结果。 线性规划，还有其他的几种调用函数形式，可在Matlab帮助中查找LP或者LINPROG的帮助说明。2. 运用MATLAB的图解法求解线性规划问题 若一个线性规划问题有最优解，则最优解一定可以在可行域的某个极点上找到一个最优解。同时仍有可能有其他最优解存在，但它们也只可能存在于可行域的其他极点或是边界上。如果我们的目的是找出一个最优解而不是全部最优解，这一定理实际上是把寻找的范围，从可行域中的无

18、穷多个可行点，缩小到可行域的有限几个极点上。 问题一、某农户有耕地20公顷，可采用甲乙两种种植方式。甲种植方式每公顷需投资280元，每公顷投工6个，可获收入1000元，乙方式每公顷需投资150元，劳动15个工日，可获收入1200元，该户共有可用资金4200元、240个劳动工日。问如何安排甲乙两种方式的生产，可使总收入最大?解：设甲方式种公顷，乙方式种公顷，总收入为Z，则有： （13） 图 问题一线性规划图解所以，如图所示，在B点时，甲级两种方式的总收入最大，即甲方式种6.7公顷，乙方式种13.3公顷。4、 结论 1、由于将线性规划问题化为标准形式之后的约束条件是一个非齐次线性方程组，故当考虑

19、LP 问题的解时，首先可以考虑非齐次线性方程组的解，然后再考虑目标函数的解最大、最小值问题。单纯形法是求解 LP 问题的一种常用方法，但单纯形法的运算量比较大，当约束条件中的约束变量比较多时，效费比就比较低，因此借助计算机软件的强大运算功能，既节约时间又提高了运算的准确性，对于一般的线性规划问题，应用 excel、MATLAB 都可以轻松解决，但MATLAB 的整数线性规划运算功能欠缺，此时可以应用 lingo、excel 软件解决这类问题。 2、在接触 MATLAB 之后,我发现 MATLAB语法简单,易于绘制图形,编程也非常容易.并且有功能强大的开放式的 toolbox。MATLAB是功能

20、强大的科学及工程计算软件,它不但具有矩阵计算为基础的强大数学计算 和分析功能,而且还具有丰富的可视化图形表现功能和方便的程序设计能力。3、对于 MATLAB自带函数的问题,要多利用 MATLAB 的帮助功能,例如:对于某些不是很明确的命令,只知道大体的所属范围,譬如说某个工具箱,直接在命令窗口中敲入 helptoolboxname.可以这么说任何问题都可以在 MATLAB 帮助里找到解决方法,问题不论大小,都是由更小的问题组成,到MATLAB帮助里面去找这些小问题,就可以得到解决。4、MATLAB在使用的过程中一定要仔细,整个程序中如果一个分号放错位置,都会导致程序不能运行,这样会花费大量时间去调试,往往还不能找到错误的地方. 5、MATLAB 同时