利用Matlab求解线性规划问题

§15. 利用Matlab求解线性规划问题

线性规划是一种优化方法，Matlab优化工具箱中有现成函数linprog对如下式描述的LP问题求解：

% min f'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) 作有等式约束的问题。若没有不等式约束，则令

111

《计量地理学》（徐建华，高等教育出版社，2005）配套实习指导

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 最大允许迭代次数 TolX x处的终止容限

[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的线性等式。

112

《计量地理学》（徐建华，高等教育出版社，2005）配套实习指导

下面通过具体的例子来说明：

例如：某农场I、II、III等耕地的面积分别为100 hm2、300 hm2和200 hm2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为190000kg、130000kg和350000kg。I、II、III等耕地种植三种作物的单产如表5.1.4所示。若三种作物的售价分别为水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg。那么，（1）如何制订种植计划，才能使总产量最大？（2）如何制订种植计划，才能使总产值最大？

表1不同等级耕地种植不同作物的单产(单位:kg / hm2) 水稻 大豆 玉米

I等耕地 11 000 8 000 14 000

II等耕地 9 500 6 800 12 000

III等耕地 9 000 6 000 10 000

首先根据题意建立线性规划模型（决策变量设置如表2所示，表中xij表示第i种作物在第j等级的耕地上的种植面积。）：

表2 作物计划种植面积（单位:hm2) 水稻 大豆 玉米 I等耕地 II等耕地 III等耕地 x11 x21 x31 x12 x22 x32 x13 x23 x33 约束方程如下：

x11x21x31100x12x22x32300xxx2002333耕地面积约束： 13

-11000x119500x129000x13-190000-8000x216800x226000x23-130000-14000x12000x10000x-350000313233最低收获量约束： 

113

《计量地理学》（徐建华，高等教育出版社，2005）配套实习指导

非负约束：

xij0(i1,2,3j;1,2,3)

(1)追求总产量最大，目标函数为：

minZ=-11000x119500x129000x13 -8000x216800x226000x23- 14000x3112000x3210000x33(2)追求总产值最大，目标函数为：

maxZ=-1.20×(11000x119500x129000x13 )-1.50×(8000x216800x226000x23 )-0.80×( 14000x3112000x3210000x33)-13200x1111400x1210800x1312000x2110200x229000x2311200x319600x328000x33

根据求解函数linprog中的参数含义，列出系数矩阵，目标函数系数矩阵，以及约束条件等。

这些参数中没有的设为空。譬如， （1）当追求总产量最大时，只要将参数

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.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 -130000 -350000];

lb=[0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 ];

代入求解函数xoptfxoptlinprog(f,A,b,[],[],lb,[])，即可求得结果。

（2）当追求总产值最大时，将参数

f=[-13200 –11400 –10800 –12000 –10200 –9000 –11200 –9600 -8000];

114

《计量地理学》（徐建华，高等教育出版社，2005）配套实习指导

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.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 -130000 -350000];

lb=[0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 ];

代入求解函数xoptfxoptlinprog(f,A,b,[],[],lb,[])，即可得到求解结果。

线性规划，还有其他的几种调用函数形式，可在Matlab帮助中查找LP或者LINPROG的帮助说明。

115