MATLAB课件第十一章线性极值精品文档16页.docx

MATLAB课件第十一章线性极值精品文档16页.docx

《MATLAB课件第十一章线性极值精品文档16页.docx》由会员分享，可在线阅读，更多相关《MATLAB课件第十一章线性极值精品文档16页.docx（22页珍藏版）》请在冰点文库上搜索。

MATLAB课件第十一章线性极值精品文档16页

第十一章线性极值

教师范读的是阅读教学中不可缺少的部分，我常采用范读，让幼儿学习、模仿。

如领读，我读一句，让幼儿读一句，边读边记；第二通读，我大声读，我大声读，幼儿小声读，边学边仿；第三赏读，我借用录好配朗读磁带，一边放录音，一边幼儿反复倾听，在反复倾听中体验、品味。

MATLAB提供了很多求极值（或最优值）的命令函数，既可以求无条件的极值，也可求有条件的极值，其中，条件可以是不等式，也可以是等式的，可以是线性的，也可以是非线性的，甚至可以是多个条件，目标函数可以是线性的，也可以是非线性的，总之，MATLAB针对不同的类型，采用不同的函数命令去求解，以下将分类型来做些简单的介绍。

其实,任何一门学科都离不开死记硬背,关键是记忆有技巧,“死记”之后会“活用”。

不记住那些基础知识,怎么会向高层次进军?

尤其是语文学科涉猎的范围很广,要真正提高学生的写作水平,单靠分析文章的写作技巧是远远不够的,必须从基础知识抓起,每天挤一点时间让学生“死记”名篇佳句、名言警句,以及丰富的词语、新颖的材料等。

这样,就会在有限的时间、空间里给学生的脑海里注入无限的内容。

日积月累,积少成多,从而收到水滴石穿,绳锯木断的功效。

1线性极值（又称线性规划）

“师”之概念，大体是从先秦时期的“师长、师傅、先生”而来。

其中“师傅”更早则意指春秋时国君的老师。

《说文解字》中有注曰：

“师教人以道者之称也”。

“师”之含义，现在泛指从事教育工作或是传授知识技术也或是某方面有特长值得学习者。

“老师”的原意并非由“老”而形容“师”。

“老”在旧语义中也是一种尊称，隐喻年长且学识渊博者。

“老”“师”连用最初见于《史记》，有“荀卿最为老师”之说法。

慢慢“老师”之说也不再有年龄的限制，老少皆可适用。

只是司马迁笔下的“老师”当然不是今日意义上的“教师”，其只是“老”和“师”的复合构词，所表达的含义多指对知识渊博者的一种尊称，虽能从其身上学以“道”，但其不一定是知识的传播者。

今天看来，“教师”的必要条件不光是拥有知识，更重于传播知识。

1.1线性规划模型

规划问题研究的对象大体可以分为两大类：

一类是在现有的人、财、物等资源的条件下，研究如何合理的计划、安排，可使得某一目标达到最大，如产量、利润目标等；另一类是在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使成本、费用最小等。

这两类问题从本质上说是相同的，即都在一组约束条件下，去实现某一个目标的最优（最大或最小）。

线性规划研究的问题要求目标与约束条件函数都是线性的，而目标函数只能是一个。

在经济管理问题中，大量问题是线性的，有的也可以转化为线性的，从而使线性规划有极大的应用价值。

线性规划模型包含3个要素：

（1）决策变量.问题中需要求解的那些未知量，一般用n维向量

表示。

（2）目标函数.通常是问题需要优化的那个目标的数学表达式，它是决策变量x的线性函数。

（3）约束条件.对决策变量的限制条件，即x的允许取值范围，它通常是x的一组线性不等式或线性等式。

线性规划问题的数学模型一般可表示为：

min（max）fTX

s.tAX≤b

AeqX=beq

lb≤X≤ub

其中X为n维未知向量，fT=[f1,f2,…fn]为目标函数系数向量，小于等于约束系数矩阵A为m×n矩阵，b为其右端m维列向量，Aeq为等式约束系数矩阵，beq为等式约束右端常数列向量。

lb,ub为自变量取值上界与下界约束的n维常数向量。

特别注意：

当我们用MATLAB软件作优化问题时，所有求maxf的问题化为求min（-f）来作。

约束gi（x）≥0，化为–gi≤0来做。

1.2．线性规划问题求最优解函数：

调用格式：

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为指定优化参数进行最小化。

[x,fval]=linprog（…）左端fval返回解x处的目标函数值。

[x,fval,exitflag,output,lambda]=linprog（f,A,b,Aeq,beq,lb,ub,x0）的输出部分：

exitflag描述函数计算的退出条件：

若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。

Output为关于优化的一些信息。

Lambda为解x的Lagrange乘子。

【例1】求解线性规划问题：

maxf=2x1+5x2

s.t

先将目标函数转化成最小值问题：

min（-f）=-2x1-5x2

具体程序如下：

f=[-2-5];

A=[10;01;12];

b=[4;3;8];

lb=[00];

[x,fval]=linprog（f,A,b,[],[],lb）

f=fval*（-1）

运行结果：

x=23

fval=-19.0000

maxf=19

【例2】：

minf=5x1-x2+2x3+3x4-8x5

s.t–2x1+x2-x3+x4-3x5≤6

2x1+x2-x3+4x4+x5≤7

0≤xj≤15j=1,2,3,4,5

编写以下程序：

f=[5-123-8];

A=[-21-11-3;21-141];

b=[6;7];

lb=[00000];

ub=[1515151515];

[x,fval]=linprog（f,A,b,[],[],lb,ub）

运行结果：

x=

0.0000

0.0000

8.0000

0.0000

15.0000

minf=

-104

【例3】：

假设某厂计划生产甲、乙两种产品，现库存主要材料有A类3600公斤，B类2000公斤，C类3000公斤。

每件甲产品需用材料A类9公斤，B类4公斤，C类3公斤。

每件乙产品，需用材料A类4公斤，B类5公斤，C类10公斤。

甲单位产品的利润70元，乙单位产品的利润120元。

问如何安排生产，才能使该厂所获的利润最大。

建立数学模型：

设x1、x2分别为生产甲、乙产品的件数。

f为该厂所获总润。

maxf=70x1+120x2

s.t9x1+4x2≤3600

4x1+5x2≤2000

3x1+10x2≤3000

x1,x2≥0

将其转换为标准形式：

minf=-70x1-120x2

s.t9x1+4x2≤3600

4x1+5x2≤2000

3x1+10x2≤3000

x1,x2≥0

编写以下程序：

f=[-70-120];

A=[94;45;310];

b=[3600;2000;3000];

lb=[00];

[x,fval,exitflag]=linprog（f,A,b,[],[],lb）;

x,exitflag,maxf=-fval

运行结果：

x=

200.0000

240.0000

exitflag=

1

maxf=

4.2800e+004

【例4】：

某公司有一批资金用于4个工程项目的投资，其投资各项目时所得的净收益（投入资金百分比）如下表：

工程项目收益表

工程项目

A

B

C

D

收益（%）

15

10

8

12

由于某种原因，决定用于项目A的投资不大于其他各项投资之和而用于项目B和C的投资要大于项目D的投资。

试确定该公司收益最大的投资分配方案。

建立数学模型：

设x1、x2、x3、x4分别代表用于项目A、B、C、D的投资百分数。

maxf=0.15x1+0.1x2+0.08x3+0.12x4

s.tx1-x2-x3-x4≤0

x2+x3-x4≥0

x1+x2+x3+x4=1

xj≥0j=1,2,3,4

将其转换为标准形式：

minz=-0.15x1-0.1x2-0.08x3-0.12x4

s.tx1-x2-x3-x4≤0

-x2-x3+x4≤0

x1+x2+x3+x4=1

xj≥0j=1,2,3,4

编写程序：

f=[-0.15;-0.1;-0.08;-0.12];

A=[1-1-1-1;0-1-11];

b=[0;0];

Aeq=[1111];

beq=[1];

lb=zeros（4,1）;

[x,fval,exitflag]=linprog（f,A,b,Aeq,beq,lb）

fmax=-fval

运行结果：

x=

0.5000

0.2500

0.0000

0.2500

fval=

-0.1300

exitflag=

1

fmax=

0.1300

即4个项目的投资百分数分别为50%，25%，0,25%时可使该公司获得最大的收益，其最大收益可到达13%。

过程正常收敛。

【例5】：

有A、B、C三个食品加工厂，负责供给甲、乙、丙、丁四个市场。

三个厂每天生产食品箱数上限如下表：

工厂

A

B

C

生产数

60

40

50

四个市场每天的需求量如下表：

市场

甲

乙

丙

丁

需求量

20

35

33

34

从各厂运到各市场的运输费（元/每箱）由下表给出：

市场

甲

乙

丙

丁

工

厂

A

2

1

3

2

B

1

3

2

1

C

3

4

1

1

求在基本满足供需平衡的约束条件下使总运输费用最小。

建立数学模型：

设aij为由工厂i运到市场j的费用，xij是由工厂i运到市场j的箱数。

bi是工厂i的产量，dj是市场j的需求量。

b=（604050）d=（20353334）

s.t

xij≥0

编写程序：

AA=[2132;1321;3411];

f=AA（:

）;

A=[100100100100

010010010010

001001001001];

Aeq=[111000000000

000111000000

000000111000

000000000111];

b=[60;40;50];

beq=[20;35;33;34];

lb=zeros（12,1）;

[x,fval,exitflag]=linprog（f,A,b,Aeq,beq,lb）

运行结果：

x=

0.0000

20.0000

0.0000

35.0000

0.0000

0.0000

0.0000

0.0000

33.0000

0.0000

18.4682

15.5318

fval=

122.0000

exitflag=

1

即运输方案为：

甲市场的货由B厂送20箱；乙市场的货由A厂送35箱；丙商场的货由C厂送33箱；丁市场的货由B厂送18箱，再由C厂送16箱。

最低总运费为：

122元。

20-1整数规划求极值

形如：

minfTX

s.tAX≤b

AeqX=beq

xi为0或1

其中X为n维未知向量，fT=[f1,f2,…fn]为目标函数系数向量，小于等于约束系数矩阵A为m×n矩阵，b为其右端m维列向量，Aeq为等式约束系数矩阵，beq为等式约束右端常数列向量。

lb,ub为自变量取值上界与下界约束的n维常数向量。

2.1分支定界法

在Matlab中提供了bintprog函数实现0-1型线性规划，采用的是分支定界法原理，其调用格式如下：

x=bintprog（f,A,b）

x=bintprog（f,A,b,Aeq,beq）

[x,fval]=bintprog（…）

[x,fval,exitflag]=bintprog（…）

[x,fval,exitflag,output]=bintprog（…）

[x,fval,exitflag,output,lambda]=bintprog（…）

说明：

x=bintprog（f,A,b）返回值x为最优解向量。

x=bintprog（f,A,b,Aeq,beq）作有等式约束的问题。

若没有不等式约束，则令A=[]、b=[]。

[x,fval]=bintprog（…）左端fval返回解x处的目标函数值。

【例6】求解以下问题：

maxz=x1+1.2x2+0.8x3

st

2.1x1+2x2+1.3x3<=5

0.8x1+x2<=5

x1+2.5x2+2x3<=8

2x2<=8

x1,x2,x3为0或1

解答:

首先，将其改变成0-1整数规划函数bintprog要求的标准形式：

minz=-x1-1.2x2-0.8x3

st

2.1x1+2x2+1.3x3<=5

0.8x1+x2<=5

x1+2.5x2+2x3<=8

2x2<=8

x1,x2,x3为0或1

Matlab求解：

c=[-1,-1.2,-0.8];

A=[2.1,2,1.3;0.8,1,0;1,2.5,2;0,2,0];

b=[5;5;8;8];

[x,fval]=bintprog（c,A,b）;

x

fmax=-fval

运行结果可得：

x=

1

1

0

fmax=

2.2000

【例7】某快餐连锁经营公司有7个地点（A1，A2，---，A7）可以设立快餐店，由于地理位置因素，设立快餐店时必须满足以下要求：

A1，A2，A3三个地点最多可选两个，A1和A5至少选取一个，A6和A7至少选取一个。

已知各个地点设立快餐店的投入和预计收益如表所示。

已知目前公司有650万元可以投资。

问怎样投资才能使公司预计收益最高？

地点

A1

A2

A3

A4

A5

A6

A7

利润/万元

10

11

8

12

15

12

5

投资/万元

103

140

95

150

193

160

80

解：

这是一个选址问题。

首先引入0-1变量xi;

xi=1,选择Ai地址；xi=0,不选择Ai地址。

则该问题的数学模型可以表示如下：

maxz=10x1+11x2+8x3+12x4+15x5+12x6+5x7

st

（1）103x1+140x2+95x3+150x4+193x5+160x6+80x7<=650

（2）x1+x2+x3<=2

（3）x4+x5>=1

（4）x6+x7>=1

（5）xi=0,1

matlab求解程序如下：

c=[-10-11-8-12-15-12-5];

A=[1031409515019316080;1110000;

000-1-100;00000-1-1];

b=[650;2;-1;-1];

[x,fval]=bintprog（c,A,b）;

x

f=fval*（-1）

运行程序得：

x=[1;1;0;1;0;1;1],fval=50

2.2枚举法

除了采用分支定界法原理计算0-1整数规划外，还可以采用枚举法

枚举法程序bintLp_E.m

function[x,f]=bintLp_E（c,A,b,N）

%[x,f]=bintLp_E（c,A,b,N）:

用枚举法求解下列0-1线性规划

%minf=c'*x,s.t.A*x<=b,x的分量全为0或1

%其中N表示约束条件A*x<=b中的前N个是等式，N=0时可以省略

%返回结果x是最优解，f是最优解处的函数值

ifnargin<4

N=0;

end

c=c（:

）;b=b（:

）;

[m,n]=size（A）;

x=[];f=abs（c'）*ones（n,1）;

i=1;

whilei<=2^n

B=de2bi（i-1,n）';

t=A*B-b;

t11=find（t（1:

N,:

）~=0）;

t12=find（t（N+1:

m,:

）>0）;

t1=[t11;t12];

ifisempty（t1）

f=min（[f,c'*B]）;

ifc'*B==f

x=B;

end

end

i=i+1;

end

注意：

以上程序需保存至搜索路径之下才可以调用。

【例8】求解下列0-1型整数线性规划。

解：

分别采用二种算法计算如下：

c=[3-25];

a=[12-1;14-1;110;041];

b=[2;4;3;6];

[x,fval]=bintprog（c,a,b）

[xx,ffval]=bintLp_E（c,a,b）

计算结果如下：

x=

0

1

0

fval=

-2

xx=

0

1

0

ffval=

-2

【例9】A1加工B1,A2加工B3,A3加工B2配件时所需总时间最少,只需10小时.

练习2:

某公司有A1,A2,A3三项业务需要B1,B2,B3三位业务员处理,每个业务员处理业务的费用如表所示,其中业务员B2不能处理业务A1,问应指派何人去完成何项业务,使所需总费用最少?

B1

B2

B3

A1

1500

不能处理

800

A2

1200

900

750

A3

900

800

900

解:

设xij表示第i项业务被第j位业务员处理，其中不能处理时可以认为费用非常高，比如999999元，则依题意可得如下模型：

minz=1500x11+999999x12+800x13+1200x21

+900x22+750x23+900x31+800x32+900x33

st

x11+x12+x13=1

x21+x22+x23=1

x31+x32+x33=1

x11+x21+x31=1

x12+x22+x32=1

x13+x23+x33=1

xij=0,1

编写matlab程序：

c=[15009999998001200900750900800900];

Aeq=[111000000;

000111000;

000000111;

100100100;

010010010;

001001001];

beq=ones（6,1）;

[x,fval]=bintprog（c,[],[],Aeq,beq）

[xx,ffval]=bintLp_E（c,Aeq,beq,6）

运行程序可得：

x=xx=[001010100];fval=ffval2600

答案:

A1被B3处理，A2被B2处理，A3被B1处理时总费用最少,只需2600元.

3整数规划求极值

MATLAB关于整数规划没有内带的函数，目前关于整数规划的自编程序已编好，以下是其中之一：

function[x,val,status]=ip（f,A,b,Aeq,beq,lb,ub,M,e）

options=optimset（'display','off'）;bound=inf;

[x0,val0]=linprog（f,A,b,Aeq,beq,lb,ub,[],options）;

[x,val,status,b]=rec（f,A,b,Aeq,beq,lb,ub,x0,val0,M,e,bound）;function[xx,val,status,bb]=rec（f,A,b,Aeq,beq,lb,ub,x,v,M,e,bound）

options=optimset（'display','off'）;

[x0,val0,status0]=linprog（f,A,b,Aeq,beq,lb,ub,[],options）;

ifstatus0<=0|val0>bound

xx=x;val=v;status=status0;bb=bound;

return;

end

ind=find（abs（x0（M）-round（x0（M）））>e）;

ifisempty（ind）

status=1;

ifval0

x0（M）=round（x0（M））;

xx=x0;

val=val0;

bb=val0;

else

xx=x;

val=v;

bb=bound;

end

return

end

[rowcol]=size（ind）;

br_var=M（ind

（1））;

br_value=x（br_var）;

fori=2:

col

tempbr_var=M（ind（i））;

tempbr_value=x（br_var）;

iftempbr_value>br_value

br_var=tempbr_var;

br_value=tempbr_value;

end

end

ifisempty（A）

[rc]=size（Aeq）;

else

[rc]=size（A）;

end

A1=[A;zeros（1,c）];

A1（end,br_var）=1;

b1=[b;floor（br_value）];

A2=[A;zeros（1,c）];

A2（end,br_var）=-1;

b2=[b;-ceil（br_value）];

[x1,val1,status1,bound1]=rec（f,A1,b1,Aeq,beq,lb,ub,x0,val0,M,e,bound）;

status=status1;

ifstatus1>0&bound1

xx=x1;

val=val1;

bound=bound1;

bb=bound1