72 数学规划.docx
《72 数学规划.docx》由会员分享，可在线阅读，更多相关《72 数学规划.docx（33页珍藏版）》请在冰点文库上搜索。
72数学规划
7.2数学规划模型与数学实验
7.2.1线性规划模型
1939年苏联的康托洛维奇（л.в.Канторович）和美国的希奇柯克（F.L.Hitchcock）等人就在生产组织管理和制定交通运输方案方面首先研究和应用一线性规划方法。
1947年丹齐格（Dantzig）等人提出了求解线性规划问题的单纯形方法，为线性规划的理论与计算奠定了基础，特别是电子计算机的出现和日益完善，更使规划论得到迅速的发展，可用电子计算机来处理成千上万个约束条件和变量的大规模线性规划问题，从解决技术问题的最优化，到工业、农业、商业、交通运输业以及决策分析部门都可以发挥作用。
从范围来看，小到一个班组的计划安排，大至整个部门，以至国民经济计划的最优化方案分析，它都有用武之地，具有适应性强，应用面广，计算技术比较简便的特点。
下面我们就从引例出发，介绍线性规划模型。
例1（动物饲料配置）我国一家公司以专门饲养并出售一种实验用动物而闻名。
该公司的研究表明，这种动物的生长对饲料中的三种营养成分特别敏感，即蛋白质、矿物质和维生素。
同时发现这种动物每天至少需要70克蛋白质、3克矿物质和10毫克维生素。
该公司能得到五种饲料，每一种饲料每市斤所含的营养成分及成本如表7.1。
该公司希望找出满足动物营养需要而成本又最低的混合饲料配置。
表7.1每一种饲料每市斤所含的营养成份及成本
饲料
蛋白质（g）
矿物质（g）
维生素（mg）
价格（元）
1
0.30
0.10
0.05
0.2
2
2
0.05
0.10
0.7
3
1.0
0.02
0.02
0.4
4
0.60
0.2
0.2
0.3
5
1.8
0.05
0.08
0.5
解：
确定决策变量：
令
为每天所需混合饲料中第j种饲料的市斤数．
确定约束条件：
蛋日质每天至少70克：
矿物质每天至少3克：
维生素每天至少10毫克：
每种饲料的市斤数不能为负（非负约束）：
确定目标函数：
混合饲料的成本最低：
上述模型一般写成：
这就是一个线性规划问题，可以用线性规划算法（更现成的是用各种相关的软件）求解．
例2（运输问题）有两个煤场A、B，每月分别进煤60吨，100吨。
它们担负供应三个居民区用煤任务。
这三个居民区每月需用煤分别为45吨，75吨，40吨。
A煤场离这三居民距离区分别为10公里，5公里，6公里，B煤场离这三居民距离区分别为4公里，8公里，15公里。
试建立使运输量（吨•公里）最小的运输方案的数学模型。
解：
各煤场的进煤量，居民区需求量及煤场与居民区的距离可用表7.2表示：
表7.2煤场与居民区的供需及距离表
距离居民区
煤场
1
2
3
供应量
A
10
5
6
60
B
4
8
15
100
需求量
45
75
40
设xij为煤场i运往第j个居民区的运煤量，则总的运输量为
（供销平衡的运输问题）
在本例中,由于煤场供应量正好等于居民区需求量，煤场的煤正好卖出，居民区的需求量也正好得到满足，所以各约束条件均为等式。
我们把这样的运输问题称为供销平衡问题。
如果供应量大于需求量，比如说A煤场的进煤量为70吨，B煤场的进煤量为120吨，其它条件不变，则模型应变为：
（供销不平衡的运输问题）
线性规划模型可以具有各种形式，下面给出一般形式、标准形式和两种实用形式．各种形式之间是可以相互转化的．
1线性规划模型的一般形式
求决策变量（向量）
，在满足约束条件下使目标函数达到最大或最小，这里
1）约束条件下列各种形式条件的组合：
2）目标函数
求极小或极大（min/max）
其中A为矩阵，b和c均为向量．某些常见的特殊约束条件有：
等等．
2线性规划模型的标准形式
线性规划的标准形式（SLP:
standardlinearprogramming）为：
其中
是n维列向量，
（m×n维矩阵），
是n维行向量。
3线性规划模型的实用形式
许多实际线性规划问题具有下列形式或可以容易地化为下列形式，许多的软件也十分方便地提供对这类形式的直接支持．
（1）实用形式之一
其中L和U为变量的下界（可为负无穷）和上界（可为正无穷）
（2）实用形式之二
其中
和L可为负无穷，
和U可为正无穷．
线性规划问题的求解方法包括表上作业法、图解法、单纯形法等，但在决策变量个数较多，求解过程都比较复杂时，用MATLAB软件求解线性规划问题则比较简单。
4MATLAB求解线性规划模型
用MATLAB求解线性规划问题的命令如下
命令函数：
[X,fval,exitflag,output,lambda]=linprog（c,A,b,Aeq,Beq,LB,UB,X0,options）.
函数说明：
⑴ 这里c为由目标函数的系数组成的向量。
X是由决策变量组成的列向量，A是一个矩阵，b是一个向量，A和b组成线性规划的不等式约束条件AX≤b。
返回的X值为满足目标函数取得极值的一组变量的值。
Aeq是一个矩阵，Beq是一个向量，Aeq和Beq组成线性规划的等式约束条件Aeq·X＝Beq。
LB和UB分别是变量的下界和上界约束。
X0是给出的变量的初始值。
Options为控制规划过程的参数系列。
在返回值中fval是优化结束后得到的目标函数值。
⑵ 运用linprog（）命令时，系统默认为它的各种linprog（c,A,b,Aeq,Beq,LB,UB,X0,options）都存在，且按固定顺序排列。
本例中，在存在约束LB的情况下，它后面的参数没给出，可以不声明，但是LB前面的参数即使没给出（例如等式约束条件）也要用空矩阵“[]”的方式给出声明，不能省略。
⑶ 返回值exitflag有3种情况：
exitflag=0表示优化结果已经超过函数的估计值或者已声明的最大叠代次数；exitflag=1表示优化过程中变量收敛于解X。
本例exitflag=1表示解收敛。
exitflag=－1表示优化结果不收敛。
⑷ 返回值output有3个分量，iterations表示优化过程的叠代次数，cgiterations表示PCG叠代次数，algorithm表示优化采用的运算规则。
⑸ 返回值lambda有4个分量，ineqlin是线性不等式约束条件，eqlin是线性等式约束条件，upper是变量的上界约束条件，lower是变量的下界约会条件。
它们的返回值分别表示相应的约束条件在优化过程中是否有效，本例中可以看到，三个不等式约束中的后两个是有效的。
其中，有些选项可以省略，如下所示。
（1） X=linprog（c,A,b）
求解LP问题：
minz=cX
s.t.AX≤b
（2） [X,fval]=linprog（c,A,b,Aeq,Beq）
求解LP问题
minz=cX
s.t.AX≤b
Aeq·X＝beq
若没有不等式：
AX≤b 存在，则令A＝[],b＝[].
（3）[X,fval]=linprog（c,A,b,Aeq,Beq,LB,UB）
求解LP问题
minz=cX
s.t.AX≤b
Aeq·X＝Beq
LB≤X≤UB
若没有等式约束：
Aeq·X＝beq，则令Aeq＝[],Beq＝[].
在例1中，改写模型如下：
输入matlab代码如下：
>>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];
>>b=-[70;3;10];
>>lb=[0,0,0,0,0];
>>[X,fval]=linprog（c,A,b,[],[],lb）
击回车键，显示最优解及目标函数最优值：
X=
0.0000
0.0000
0.0000
39.7436
25.6410
fval=
24.7436
结果表明，这种实验用动物每天的混合饲料中需要这五类饲料的市斤数分别为0，0，0，39.7436，25.6410市斤，混合饲料的最低成本为24.7436元。
在例2中先解答供销平衡的运输问题，然后再求解供销不平衡的运输问题。
供销平衡运输问题的MATLAB程序如下
>>clear
>>f=[10,5,6,4,8,15];
>>aeq=[1,1,1,0,0,0
0,0,0,1,1,1
1,0,0,1,0,0
0,1,0,0,1,0
0,0,1,0,0,1];
>>beq=[60,100,45,75,40];
>>lb=[0,0,0,0,0,0];
>>[X,fval]=linprog（f,[],[],aeq,beq,lb）
回车后结果显示
Optimizationterminatedsuccessfully.
X=
0.0000
20.0000
40.0000
45.0000
55.0000
0.0000
fval=
960.0000
结果表明，A煤场依次往三个居民区供煤0、20、40吨、B煤场依次往三个居民区供煤45、55、0吨时运输量最小，为960吨˙公里。
对于供销不平衡的运输问题
其MATLAB程序为
>>clear
>>f=[10,5,6,4,8,15];
>>A=[1,1,1,0,0,0
0,0,0,1,1,1];
>>b=[70,120];
>>Aeq=[1,0,0,1,0,0
0,1,0,0,1,0
0,0,1,0,0,1];
>>beq=[45,75,40];
>>lb=[0,0,0,0,0,0];
>>[X,fval]=linprog（f,A,b,Aeq,beq,lb）
回车后结果显示
Optimizationterminatedsuccessfully.
X=
0.0000
30.0000
40.0000
45.0000
45.0000
0.0000
fval=
930.0000
结果和实际意义与供销平衡时的意义是相同的，不再重述。
7.2.2非线性规划数学模型
如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。
一般说来，解非线性规划要比解线性规划问题困难得多。
如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。
1Matlab优化工具箱简介
（1）MATLAB求解优化问题的主要函数
类型
模型
基本函数名
一元函数极小
MinF（x）s.t.x1x=fminbnd（‘F’,x1,x2）
无约束极小
MinF（X）
X=fminunc（‘F’,X0）
X=fminsearch（‘F’,X0）
线性规划
Min
s.t.AX<=b
X=linprog（c,A,b）
二次规划
Min
xTHx+cTx
s.t.Ax<=b
X=quadprog（H,c,A,b）
约束极小
（非线性规划）
MinF（X）
s.t.G（X）<=0
X=fmincon（‘FG’,X0）
达到目标问题
Minr
s.t.F（x）-wr<=goal
X=fgoalattain（‘F’,x,goal,w）
极小极大问题
Minmax{Fi（x）}
X{Fi（x）}
s.t.G（x）<=0
X=fminimax（‘FG’,x0）
（2）.优化函数的输入变量
使用优化函数或优化工具箱中其它优化函数时,输入变量见下表:
变量
描述
调用函数
f
线性规划的目标函数f*X或二次规划的目标函数X’*H*X+f*X中线性项的系数向量
linprog,quadprog
fun
非线性优化的目标函数.fun必须为行命令对象或M文件、嵌入函数、或MEX文件的名称
fminbnd,fminsearch,fminunc,fmincon,lsqcurvefit,lsqnonlin,fgoalattain,fminimax
H
二次规划的目标函数X’*H*X+f*X中二次项的系数矩阵
quadprog
A,b
A矩阵和b向量分别为线性不等式约束：
中的系数矩阵和右端向量
linprog,quadprog,fgoalattain,fmincon,fminimax
Aeq,beq
Aeq矩阵和beq向量分别为线性等式约束：
中的系数矩阵和右端向量
linprog,quadprog,fgoalattain,fmincon,fminimax
vlb,vub
X的下限和上限向量：
vlb≤X≤vub
linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,
lsqnonlin
X0
迭代初始点坐标
除fminbnd外所有优化函数
x1,x2
函数最小化的区间
fminbnd
options
优化选项参数结构，定义用于优化函数的参数
所有优化函数
（3）.优化函数的输出变量下表:
变量
描述
调用函数
x
由优化函数求得的值.若exitflag>0,则x为解;否则,x不是最终解,它只是迭代制止时优化过程的值
所有优化函数
fval
解x处的目标函数值
linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,
lsqnonlin,fminbnd
exitflag
描述退出条件:
●exitflag>0,表目标函数收敛于解x处
●exitflag=0,表已达到函数评价或迭代的最大次数
●exitflag<0,表目标函数不收敛
output
包含优化结果信息的输出结构.
●Iterations:
迭代次数
●Algorithm:
所采用的算法
●FuncCount:
函数评价次数
所有优化函数
控制参数options可以通过函数optimset创建或修改。
命令的格式如下：
（i）options=optimset（‘optimfun’）
创建一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构options.
（ii）options=optimset（‘param1’,value1,’param2’,value2,...）
创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.
（iii）options=optimset（oldops,‘param1’,value1,’param2’,value2,...）
创建名称为oldops的参数的拷贝,用指定的参数值修改oldops中相应的参数.
例：
opts=optimset（‘Display’,’iter’,’TolFun’,1e-8）
该语句创建一个称为opts的优化选项结构,其中显示参数设为’iter’,TolFun参数设为1e-8.
2用Matlab解无约束优化问题
（1）.一元函数无约束优化问题:
常用格式如下：
（1）x=fminbnd（fun,x1,x2）
（2）x=fminbnd（fun,x1,x2，options）
（3）[x，fval]=fminbnd（...）
（4）[x，fval，exitflag]=fminbnd（...）
（5）[x，fval，exitflag，output]=fminbnd（...）
其中（3）、（4）、（5）的等式右边可选用
（1）或
（2）的等式右边。
函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。
例1求f=2
在0解 程序代码如下：
f='2*exp（-x）.*sin（x）';
plot（f,[0,8]）;%作图语句
[xmin,ymin]=fminbnd（f,0,8）
f1='-2*exp（-x）.*sin（x）';
[xmax,ymax]=fminbnd（f1,0,8）
例2对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？
解 设剪去的正方形的边长为x，则水槽的容积为：
建立无约束优化模型为：
miny=-
，0设剪去的正方形的边长为x，则水槽的容积为：
建立无约束优化模型为：
miny=-
，0先编写M文件fun0.m如下:
functionf=fun0（x）
f=-（3-2*x）.^2*x;
主程序为shuicao.m:
[x,fval]=fminbnd（'fun0',0,1.5）;
xmax=x
fmax=-fval
运算结果为:
xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.
（2）多元函数无约束优化问题
多元函数无约束优化问题的标准形式为：
minF（X）
命令格式为:
（i）x=fminunc（fun,X0）；
（ii）x=fminunc（fun,X0，options）；
（iii）[x，fval]=fminunc（...）；
（iv）[x，fval，exitflag]=fminunc（...）；
（v）[x，fval，exitflag，output]=fminunc（...）；
fminunc的算法说明如下：
[1]fminunc为无约束优化提供了大型优化和中型优化算法。
由options中的参数LargeScale控制：
LargeScale=’on’（默认值）,使用大型算法;
LargeScale=’off’（默认值）,使用中型算法.
[2]fminunc为中型优化算法的搜索方向提供了4种算法，由options中的参数HessUpdate控制：
HessUpdate=’bfgs’（默认值），拟牛顿法的BFGS公式；
HessUpdate=’dfp’，拟牛顿法的DFP公式；
HessUpdate=’steepdesc’，最速下降法.
[3]fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：
LineSearchType=’quadcubic’（缺省值），混合的二次和三次多项式插值；
LineSearchType=’cubicpoly’，三次多项式插值
例3求
.
1、编写M-文件fun1.m:
functionf=fun1（x）
f=exp（x
（1））*（4*x
（1）^2+2*x
（2）^2+4*x
（1）*x
（2）+2*x
（2）+1）;
2、输入M文件examp3.m如下:
x0=[-1,1];
x=fminunc（‘fun1’,x0）;
y=fun1（x）
3、运行结果:
x=0.5000-1.0000
y=1.3029e-10
例4Rosenbrock函数
的最优解（极小）为
，极小值为
.试用不同算法（搜索方向和步长搜索）求数值最优解.初值选为
=（-1.2,2）.
解：
1.为获得直观认识，先画出Rosenbrock函数的三维图形,输入以下命令：
[x,y]=meshgrid（-2:
0.1:
2,-1:
0.1:
3）;
z=100*（y-x.^2）.^2+（1-x）.^2;mesh（x,y,z）
2.画出Rosenbrock函数的等高线图,输入命令：
contour（x,y,z,20）
holdon
plot（-1.2,2,'o'）;
text（-1.2,2,'startpoint'）
plot（1,1,'o'）
text（1,1,'solution'）
（1）建立M-文件fun2.m
functionf=fun2（x）
f=100*（x
（2）-x
（1）^2）^2+（1-x
（1））^2
（2）主程序rosen1.m
oldoptions=optimset（'fminunc'）;%fminunc函数缺省选项
options=optimset（oldoptions,'LargeScale','off'）;%采用中型优化算法
options11=optimset（options,'HessUpdate','dfp'）;%DFP算法,混合二、三次插值[x11,fval11,exitflag11,output11]=fminunc（'fun2',[-1.22],options11）
pause
options12=optimset（options,'HessUpdate','dfp','LineSearchType','cubicpoly'）;%采用DFP算法,三次插值
[x12,fval12,exitflag12,output12]=fminunc（'fun2',[-1.22],options12）
pause
options21=optimset（options,'HessUpdate','bfgs'）;%BFGS算法,混合二、三次插值
[x21,fval21,exitflag21,output21]=fminunc（'fun2',[-1.22],options21）
pause
options22=optimset（options,'HessUpdate','bfgs','LineSearchType','cubicpoly'）;%BFGS算法,三次插值
[x22,fval22,exitflag22,output22]=fminunc（'fun2',[-1.22],options22）
pause
options31=optimset（options,'HessUpdate','steepdesc'）;%最速下降算法,混合二、三次插值
[x31,fval31,exitflag31,output31]=fminunc（'fun2',[-1.22],options31）
pause
options32=optimset（options,'HessUpdate','steepdesc','MaxIter',8000,'MaxFunEvals',8000）;%最速下降算法,设定最大迭代次数8000
[x32,fval32,exitflag32,output32]=fminunc（'fun2',[-1.22],options32）
pause
options33=optimset（options,'HessUpdate','steepdesc','MaxIter',9000,'MaxFunEvals',9000）;%最速下降算法,混合二、三次插值，设定最大迭代次数9000
[x33,fval33,exitflag33,output33]=fminunc（'fun2',[-1.22],options33）
Rosenbrock函数不同算法的
升级会员 