《数学实验 第4版》课件 第三章 最优化方法

第三章最优化方法实验3.1线性规划实验3.2非线性规划实验3.1线性规划一、线性规划的概念二、线性规划的图解法三、用MATLAB优化工具箱解线性规划四、应用举例：投资的收益和风险实验3.1线性规划需占用机床产品机床甲乙机床可利用时间（百台时）A2212B128C4016D0412利润（千元）23例1

资源的最佳利用问题：一、线性规划的概念

某工厂有A、B、C、D四种机床，可生产甲、乙两种产品．一件产品需经各台机床加工的时间和利润情况如表所示，问如何安排生产才能使得到的利润最高？实验3.1线性规划解设计划生产甲产品件，乙产品件,且使达到最大值求的值，使其满足条件实验3.1线性规划例2

运输问题：

实验3.1线性规划设有两个砖厂、，生产砖产量分别为23万块与27万块，、、三个工地，其需要量分别为17万块，将砖供应18万块和15万块．自产地到工地的运价如表所示．解且使具有最小值设由砖厂运往工地的砖的运量为（单位：万块）求的值，使其满足条件实验3.1线性规划①需要确定一组变量的值，这些变量通常称为决策变量，简称变量，它们通常是非负的.②对于决策变量，存在着可用一组线性等式或不等式来表达的限制条件，这些条件称为约束条件.③有一个可以表示为决策变量的线性函数的目标要求，这一函数称为目标函数．按问题的不同要求，可要求目标函数达到最大值或最小值．

在线性约束条件下，要求一组决策变量的值，使线性目标函数达到最大值或最小值的问题，就叫做线性规划问题，常用符号LP(LinearProgramming)表示。以上两个例子具有三个共同的特征：实验3.1线性规划，也称非负条件；称为价值系数．满足约束条件的决策变量的一组值，称为线性规划的可行解使目标函数达到所要求的最大值或最小值的可行解，称为线性规划的最优解，也就是线性规划的解．

求线性规划的解的过程叫做解线性规划．实验3.1线性规划,达到所要求的最大值或最小值s.t.(subjectedto)标准形式矩阵形式s.t.实验3.1线性规划只含两个决策变量的线性规划问题，可以用图解法求解．二、线性规划的图解法约束条件目标函数达到最大值，当直线移动到点时，于是最优解是最优值为例1实验3.1线性规划约束条件目标函数例3

解线性规划：问题无最优解线性规划有唯一解、无穷多解或无解三种情况．

对于决策变量两个以上的线性规划就不能用图解法，最常用、最有效的算法之一是单纯形方法。实验3.1线性规划minz=cX

1、模型：命令：x=linprog（c，A，b）

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注：若没有不等式约束条件存在，则令A=[]，b=[].三、解线性规划的MATLAB实现实验3.1线性规划3、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]

x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：[1]若没有等式约束

,则令Aeq=[],beq=[].

[2]其中X0表示初始点

4、命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.实验3.1线性规划x=

4

2A=[11;12;10;01];b=[6,8,4,3];c=-[2,3];A1=[];b1=[];v1=[0,0];x=linprog(c,A,b,A1,b1,v1)↙例1

资源的最佳利用问题：实验3.1线性规划A=[11;12;10;01];b=[6,8,4,3];c=-[2,3];A1=[];b1=[];v1=[0,0];x=linprog(c,A,b,A1,b1,v1)z=-c*x↙x=

4

2z=

14A=[11;12;10;01];b=[6,8,4,3];c=-[2,3];A1=[];b1=[];v1=[0,0];[x,fval]=linprog(c,A,b,A1,b1,v1)↙x=

4

2fval=-14实验3.1线性规划a=[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];b=[23,27,17,18,15];c=[50,60,70,60,110,160];v1=zeros(1,6);[x,fval]=linprog(c,[],[],a,b,v1)↙例2运输问题：

实验3.1线性规划具有最小值．x=

0

8

15

17

10

0fval=

3650即以下运输方案是最优的运量（万块）工地砖厂081517100实验3.1线性规划约束条件目标函数例3解线性规划：a=[-2,1;1,-1];b=[4,2];c=-[1,1];v1=[0,0];x=linprog(c,a,b,[],[],v1)↙实验3.1线性规划问题无界。x=[]表明此线性规划无最优解.四、应用举例：投资的收益和风险1、问题提出实验3.1线性规划市场上有n种资产（i=1,2……n）可以选择，

现用数额为M的相当大的资金作一个时期的投资。

这n种资产在这一时期内购买的平均收益率为风险损失率为，投资越分散，总的风险越小，总体风险可用投资的

中最大的一个风险来度量。

购买时要付交易费，(费率)，

当购买额不超过给定值时，交易费按购买计算。

另外，假定同期银行存款利率是，既无交易费又无风险。

（=5%）

已知n=4时相关数据如下：

试给该公司设计一种投资组合方案，即用给定达到资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。实验3.1线性规划符号规定基本假设实验3.1线性规划2、模型的建立(1)

总体风险用所投资的中最大的一个风险来衡量，即(3)

要使净收益尽可能大,总体风险尽可能小,这是一个多目标规划。实验3.1线性规划(2)

购买

所付交易费是一个分段函数，即交易费=可以忽略不计，这样购买的净收益为而题目所给定的定值(单位:元)相对总投资M很小,

更小，目标函数

约束条件模型1

固定风险水平，优化收益约束条件：目标函数：实验3.1线性规划3、模型简化(1)在实际投资中，投资者承受风险程度不一样，若给定风险一个界限a，使最大的一个风险

可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。

(2)若投资者希望总盈利至少达到水平以上，在风险最小的情况下寻找相应的投资组合。模型2

固定盈利水平，极小化风险目标函数：约束条件：实验3.1线性规划目标函数：

模型3

约束条件：实验3.1线性规划(3)投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。

因此对风险、收益赋予权重

称为投资偏好系数。4、模型求解

模型1实验3.1线性规划

由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长△a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)>1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.'),axis([00.100.5])holdona=a+0.001;endxlabel('a'),ylabel('Q')↙实验3.1线性规划部分计算结果如下：a=0.0030x=0.49490.12000.20000.05450.1154Q=0.1266a=0.0060x=0.00000.24000.40000.10910.2212Q=0.2019a=0.0080x=0.00000.32000.53330.12710.0000Q=0.2112a=0.0100x=0.00000.40000.58430.00000.0000Q=0.2190a=0.0200x=0.00000.80000.18820.00000.0000Q=0.2518a=0.0400x=0.00000.99010.00000.00000.0000Q=0.2673生成图实验3.1线性规划5、结果分析(3)

曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。(2)

当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。(1)

风险越大，收益也越大。实验3.1线性规划(4)在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢。所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合。类似地,可解模型2和3.大约是a*=0.6%，Q*=20%，所对应投资方案为:

风险度收益

x0x1x2x3x40.00600.201900.24000.40000.10910.2212实验3.1线性规划模型2目标函数：约束条件：模型2’目标函数：约束条件：实验3.1线性规划目标函数：

模型3

约束条件：目标函数：

模型3’

约束条件：实验3.1线性规划第三章最优化方法实验3.1线性规划实验3.2非线性规划实验3.2非线性规划一、非线性规划的概念二、二次规划三、无约束非线性规划四、带约束非线性规划五、应用举例一、非线性规划的概念

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题.

一般说来，解非线性规划要比解线性规划问题困难得多.而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围.

下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念.实验3.2非线性规划故有限制条件元.试选择最佳投资方案.元，并预计可收益个项目可供选择投资，并且至少要对（投资决策问题）某企业有元，投资于第个项目需花资金例4其中一个项目投资.已知该企业拥有总资金解设投资决策变量为则投资总额为，投资总收益为因为公司至少要对一个项目投资，并且总的投资金额不能超过总资金A，实验3.2非线性规划另外，由于只取值0或1，所以还有最佳投资方案应是投资额最小而总收益最大的方案.s.t.所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比.因此，其数学模型为：实验3.2非线性规划

上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP）.其中称为决策变量，称为目标函数，和称为约束函数.称为等式约束，称为不等式约束.实验3.2非线性规划可概括为一般形式

对于一个实际问题，在把它归结成非线性规划问题时，一般要注意以下几点：(1)确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们.(2)提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标.并且，运用各种科学和技术原理，把它表示成数学关系式.(3)给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它.实验3.2非线性规划(4)寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示.

如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到.我们先来讨论最简单的非线性规划——二次规划．实验3.2非线性规划二、二次规划

二次规划（QuadraticProgramming，记作QP）指目标函数是二次函数，约束条件为线性的.其一般形式为：s.t.为阶对称矩阵，特别地，当正定时，目标函数为凸函数，线性约束下可行域是凸集，称为凸二次规划．实验3.2非线性规划式中的意义与线性规划相同，、、、、MATLAB解二次规划的程序：

1. x=quadprog(H,c,A,b);2. x=quadprog(H,c,A,b,Aeq,beq);3. x=quadprog(H,c,A,b,Aeq,beq,VLB,VUB);4. x=quadprog(H,c,A,b,Aeq,beq,VLB,VUB,X0);5. x=quadprog(H,c,A,b,Aeq,beq,VLB,VUB,X0,options);6. [x,fval]=quaprog(...);7. [x,fval,exitflag]=quaprog(...);8. [x,fval,exitflag,output]=quaprog(...);实验3.2非线性规划例5

求解

s.t.解输入命令：H=[2-2;-24];c=[-4;-12];A=[-12;21];b=[2;3];

Aeq=[1,1];beq=[2];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)↙

实验3.2非线性规划x=0.66671.3333z=

-16.4444三、无约束非线性规划无约束非线性规划的一般形式是可以是非线性的．其中[x,fval]=fminbnd(fun,x1,x2,options)，这里fun是用M文件定义的函数或Matlab中的单变量数学函数.这实际上就是多元函数极值问题．1．求单变量有界非线性函数在区间上的极小值:Matlab的命令为它的返回值是极小值点和函数的极小值.实验3.2非线性规划例6

求函数

的最小值.

解编写M文件fun1.mfunctionf=fun1(x);f=(x-3)^2-1;在Matlab的命令行窗口输入[x,y]=fminbnd('fun1',0,5)↙

即可求得极小值点和极小值.x=3y=-1实验3.2非线性规划例7

求在中的最小值与最大值

解：命令如下f=@(x)2*exp(-x).*sin(x)';[xmin,ymin]=fminbnd(f,0,8)f1=@(x)-2*exp(-x).*sin(x)';%f的最大值点即-f的最小值点[xmax,ymax]=fminbnd(f1,0,8)↙运行结果：xmin=3.9270ymin=-0.0279xmax=0.7854ymax=-0.6448实验3.2非线性规划

所以函数在x=3.9270处取得最小值-0.0279，在x=0.7854处取得最大值0.6448.，则水槽的容积为：例8有一张边长为3m的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪可使水槽的容积最大？解设剪去的正方形的边长为建立无约束优化模型为：先编写M文件fun2.m如下:functionf=fun2(x)f=-(3-2*x).^2*x;主程序为:[x,fval]=fminbnd('fun2',0,1.5);xmax=xfmax=-fval↙实验3.2非线性规划运算结果为:xmax=0.5000fmax=2.0000即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.实验3.2非线性规划2．求多变量函数的极小值其中是一个向量，是一个标量函数.Matlab中求解多变量函数极小值的基本命令有两个：[x,fval]=fminunc(fun,x0,options,p1,p2,...)[x,fval]=fminsearch(fun,x0,options,p1,p2,...).实验3.2非线性规划例9

求解

解：编写M-文件fun3.m:functionf=fun3(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

x0=[-1,1];

[x,y]=fminunc('fun3',x0)↙x=0.5000-1.0000y=

3.6609e-15实验3.2非线性规划[x,y]=fminsearch('fun3',x0)↙x=0.5000-1.0000y=5.1425e-10四、带约束非线性规划

带有约束条件的极值问题称为约束极值问题，也叫约束规划问题.求解约束极值问题要比求解无约束极值问题困难得多.为了简化其优化工作，可采用以下方法：带约束非线性规划的一般形式为:其中是定义在上的实值函数．实验3.2非线性规划将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法.标准型为：用Matlab解非线性规划的一般步骤是：（1）首先建立M文件fun.m，定义目标函数F(ｘ):functionf=fun(ｘ);f=F(ｘ);（2）若约束条件中有非线性约束:C(x)<=0或Ceq(x)=0，则建立M文件nonlcon.m定义函数C(x)与Ceq(x):Function[C,Ceq]=nonlcon(x)C=...Ceq=...实验3.2非线性规划（3）建立主程序．非线性规划求解的函数是fmincon，命令的基本格式如下：①x=fmincon(‘fun’,X0,A,b)②x=fmincon(‘fun’,X0,A,b,Aeq,beq)③x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB)④x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)⑤x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)⑥[x,fval]=fmincon(...)其中x为返回的自变量的值，fval为返回的函数的值，X0为迭代的初值，VLB,VUB变量上下限，options参数说明．实验3.2非线性规划例10

求s.t.解

（1）先建立M文件fun4.m,定义目标函数:functionf=fun4(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);（2）再建立M文件mycon.m定义非线性约束：function[g,ceq]=mycon(x)g=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];ceq=0;实验3.2非线性规划（3）求解非线性规划:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')↙（4）运算结果为：

x=-3.16233.1623fval=1.1566实验3.2非线性规划例11

抛物面被平面截成一椭圆，求原点到这椭圆的最短距离．解（1）先建立M文件fun5.m,定义目标函数:functionf=fun5(x)f=sqrt(x(1)^2+x(2)^2+x(3)^2);（2）再建立M文件mycon1.m定义非线性约束：function[g,ceq]=mycon1(x)g=0;ceq=x(1)^2+x(2)^2-x(3);实验3.2非线性规划（4）运算结果为：x=0.36600.36600.2679fval=0.5829实验3.2非线性规划（3）求解非线性规划:x0=[0;0;0];A=[];b=[];Aeq=[111];beq=[1];vlb=[];vub=[];[x,fval]=fmincon('fun5',x0,A,b,Aeq,beq,vlb,vub,'mycon1')

↙例12资金使用问题：设有400万元资金,要求4年内使用完,若在一年内使用资金x万元,则可得效益年利率为10%.试制定出资金的使用计划,以使4年效益之和为最大.万元(效益不能再使用),当年不用的资金可存入银行,解设变量表示第i年所使用的资金数,则有

实验3.2非线性规划（1）先建立M文件fun6.m,定义目标函数:functionf=fun6(x)f=-(sqrt(x(1))+sqrt(x(2))+sqrt(x(3))+sqrt(x(4)));（2）由于没有非线性约束条件，可直接求解非线性规划:

x0=[1;1;1;1];vlb=[0;0;0;0];vub=[];A=[1,0,0,0;1.1,1,0,0;1.21,1.1,1,0;1.331,1.21,1.1,1];b=[400,440,484,532.4];Aeq=[];beq=[];[x,fval]=fmincon('fun6',x0,A,b,Aeq,beq,vlb,vub)↙实验3.2非线性规划（3）结果为:实验3.2非线性规划x=86.1883104.2878126.1883152.6879fval=-43.0860五、应用举例:供应与选址总的吨千米数最小．

某公司有6个建筑工地，每个工地的位置（用平面坐标a，b表示，单位：km）及水泥日用量d（单位：t）由表给出．目前有两个临时料场位于，日储量各有20t．（1）假设从料场到工地之间均有直线道路相连，试制订每天的供应计划，即从A、B两料场分别向各工地运送多少吨水泥，使工地1234561.258.750.55.7537.251.250.754.7556.57.753547611（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量仍各为20t，问应建在何处，节省的吨千米数有多大．实验3.2非线性规划62，因此目标函数为：解向工地从料场的运送量为记工地的位置为，水泥日用量，，料场位置为，日储量为约束条件实验3.2非线性规划，这是一个线性规划问题，（1）当用临时料场时，决策变量为计算程序如下：a=[1.258.750.55.7537.25];b=[1.250.754.7556.57.75];d=[3547611]';e=[2020]';g=[51];h=[27];c=zeros(1,12);fori=1:6c(i)=sqrt((g(1)-a(i))^2+(g(2)-b(i))^2);c(i+6)=sqrt((h(1)-a(i))^2+(h(2)-b(i))^2);endA=[ones(1,6),zeros(1,6);zeros(1,6),one