数学建模数学规划模型课件

数学规划模型的一般表达式：

为目标函数,为约束函数，为约束函数，为可控变量，为已知参数，为随机参数。数学规划分为线性规划、非线性规划、动态规划、随机规划、整数规划、分式规划、几何规划、目标规划、平衡规划、参数规划、多目标规划等十几种。当然这么多规划其中亦有交叉。又可经过组产生新的规划，每一种规划有专著问世。

数学规划模型的一般表达式：1第一节线性规划模型

（1）目标函数是决策变量的线性函数。（2）约束条件都是决策变量的线性等式或不等式。第一节线性规划模型

（1）目标函数是决策变量的线性函2MATLAB命令

命令输入格式及线性规划模型如下：其中：x0是算法迭代的初始点；nEq表示等式约束的个数。MATLAB命令

命令输入格式及线性规划模型如下：3三、建模举例

营养配餐问题每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表6-1中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20千克，其它蔬菜的供应在一周内不多于40千克，每周共需供应140千克蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少千克？三、建模举例

营养配餐问题每种蔬菜含有的营养素成份是不同的，4表2-3表2-35问题分析与模型建立设分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：

约束条件：铁的需求量至少6个单位数：磷的需求量至少25个单位数：问题分析与模型建立设6维生素A的需求量至少17500个单位：维生素C的需求量至少245个单位：烟酸的需求量至少5个单位数：

每周需供应140千克蔬菜，即维生素A的需求量至少17500个单位：7

0≤x1≤400≤x2≤400≤x3≤400≤x4≤200≤x5≤400≤x6≤40数学建模数学规划模型课件8问题是满足营养素要求的条件下，所需费用最小，是一个线性规划模型。利用Matlab软件编程序：%营养配餐ch21

%文件名：ch21m

c=[5;5;8;2;6;3];

A=(-1)*[1,1,1,1,1,1;0.45,0.45,1.05,0.40,0.50,0.50;10,28,59,25,22,75;415,9065,2550,75,15,235;问题是满足营养素要求的条件下，所需费用最小，是一个线性规划模98,3,53,27,5,8;0.30,0.35,0.60,0.15,0.25,0.80];

b=(-1)*[140;6;25;17500;245;5];

xLB=zeros(6,1);

xUB=[40;40;40;20;40;40];

nEq=1;

x0=0*ones(6,1);

x=lp(c,A,b,xLB,xUB,x0,nEq);

disp('青豆需要的份数')

x(1)8,3,53,27,5,8;10disp('胡罗卜需要的份数')

x(2)disp('菜花需要的份数')x(3)disp('白菜需要的份数')x(4)disp('甜菜需要的份数')x(5)disp('土豆需要的份数')x(6)disp('胡罗卜需要的份数')11执行后输出青豆需要的份数ans=

40胡罗卜需要的份数ans=

40.0000菜花需要的份数

ans=

0执行后输出12白菜需要的份数

ans=

20.0000甜菜需要的份数

ans=

0土豆需要的份数ans=

40最小费用

ans=

560.0000白菜需要的份数13背景：0-1规划是数学规划的组成部分，起始20世纪30年代末，七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题，从国内外的数学建模竞赛的试题中看，有近1/2的问题可用数学规划进行求解。其中利用0-1规划及0-1型变量的数学建模问题也为数不少，如98年的《投资的收益和风险

》，2004年的《DVD在线租赁》等问题，下面我们就来学习0-1规划,0-1型变量在数学建模中的应用。数学建模数学规划模型课件14

§2.20-1规划,0-1型变量在数学建模中的应用

1、0-1规划数学规划模型的一般表达式：

整数规划中决策变量只取0或1的特殊情况是0-1规划。下面通过几个例子说明0-1规划在实际问题中的应用。例2.1背包问题有几件物品，编号为1，2，…，n。第件重为kg，价值为元。今有一位装包者欲将这些物品装入一包，其质量不能超过kg，问应装入哪几件价值最大？§2.20-1规划,0-1型变量15

解引入变量

，将物品装包

，不将物品装包于是得问题的模型为

取0或1，i=1，2，…，n背包问题看似简单，但应用很广，例如某些投资问题即可归入背包问题模型。此类问题可以描述为：解引入变量16

投资问题：设有总额为元的资金，投资几项事业，第项事业需投资元，利润为元，问应选择哪些项投资总利润为最大？例2.2某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为，相应的钻探费用为，并且井位选择要满足下列限制条件：

（1）或选和，或选；（2）选择了或就不能选，反之亦然；（3）在中最多只能选两个。试建立其数学模型：投资问题：设有总额为元的资金，投资几项事17解引入变量

选择不选择于是以上问题的数学模型为：解引入变量18

投资的收益和风险

这是1998年全国大学生数学建模竞赛的A题问题如下：市场上有n种资产（股票、债券、…）Si（i=1，…，n）供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时间的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买Si有平均收益率为ri，并预测出购买Si的风险损失率为qi。考虑到投资越分散总的风险越小，公司确定，当用这笔资金购买若投资的收益和风险

这是1998年全国大19干种资产时，总体风险可用所投资的Si中最大的一个风险来度量。购买Si要付交易费，费率为pi，并且当购买额不超过给定值ui时，交易费按购买ui计算（不买当然无须付费）。另外，假定同期银行存款利率是r0，且既无交易费又无风险（r0=5%）。

（1）已知n=4时的相关数据如下：

干种资产时，总体风险可用所投资的Si中最大的一20试给该公司设计一种投资组合方案即用给定的资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。（2）试就一般情况对以上问题进行讨论，利用以下数据进行计算。

试给该公司设计一种投资组合方案即用给定的资金21在AD边等距地设置7个波源Ri（i=1，…，7），BC边对等地安放7个接收器Sj（j=1，…，7），记录由Ri发出的弹性波到达Sj的时间τij秒），见表2-3。在AD边等距地设置7个波源Ri（i=1，…，7），BC边对等22

2、0-1型变量在数学建模中的应用

1、空洞探测问题

1.1问题的提出

这是2000年全国大学生数学建模竞赛的D题。

山体、隧洞、坝体等的某些内部结构可用弹性波测量来确定。一个简化问题可描述为，一块均匀介质构成的矩形平板内有一些充满空气的空洞，在平板的两个邻边分别等距地设置若干波源，在它们的对边对等地安放同样多的接收器，记录弹性波由每个波源到达对边上每个接收器的时间，根据弹性波在介质中和空气中不同的传播速度，来确定板内空洞的位置。现考察如下的具体问题：

2、0-1型变量在数学建模中的应用

1、空洞23

一块240（米）×240（米）的平板

（如图2—1）在AB边等距地设置7个波源Pi（i=1，…，7），CD边对等地安放7个接收器Qj（j=1，…，7），记录由Pi发出的弹性波到达Qj的时间tij（秒），

一块240（米）×240（米）的平板

24见表2-2；见表2-2；25在AD边等距地设置7个波源Ri（i=1，…，7），BC边对等地安放7个接收器Sj（j=1，…，7），记录由Ri发出的弹性波到达Sj的时间τij秒），见表2-3。在AD边等距地设置7个波源Ri（i=1，…，7），BC边对等26

已知弹性波在介质和空气中的传播速度分别为2880（米/秒）和320（米/秒），且弹性波沿板边缘的传播速度与在介质中的传播速度相同。

1）确定该平板内空洞的位置。

2）只根据由Pi发出的弹性波到达Qj的时间tij

（i，j=1，…，7），能确定空洞的位置吗？

讨论在同样能够确定空洞位置的前提下，减少波源和接受器的方法。

1.2模型的假设及符号说明

（1）模型的假设

①波源和接收器的设置仅按图中的设置来考虑，不考虑其它情况。

②在图中的一个小方格要么全是空气，要么全。

已知弹性波在介质和空气中的传播速度分别为227

是介质。

（2）符号说明

n+1：x轴方向等距地放置波源Pi（i=1~7）的个

数，相应地n是x轴方向的方格数（已知

的n=6）；

m+1：y轴方向等距地放置波源Ri（i=1~7）的个

数，相应地m是y轴方向的方格数（已知的

m=6）；

d1：x轴方向方格的边长（已知的，d1=40米）；

d2：y轴方向方格的边长（已知的，d2=40米）；

tij（i=0~6；j=0~6）：由波源Pi发生的弹性波到达

接收器Qj的时间；

是介质。

（2）符号说明

n+1：x轴方向等距地放置波源28

pij（i=0~6；j=0~6）：波线PiQj经历的介质的

总长度；

qij（i=0~6；j=0~6）：波线PiQj经历的空洞的

总长度；

v1：弹性波在介质中的传播速度（已知的

v1=2880米/秒）；

v2：弹性波在空气中的传播速度（已知的

v2=320米/秒）；

pij（i=0~6；j=0~6）：波线PiQj经29

1.3问题的分析及数学模型

（1）问题的分析

这是一个反问题，不妨先看它正问题。

已知空洞的位置及弹性波在介质和空气中的传播速度，求由波源Pi发出的弹性波到达接收器Qj的时间tij，为了求出tij，可先算出波线PiQj经历的每个小方格的长度，根据该方格是介质还是空洞，分别除以波在介质和空气中的传播速度，对经历的所有方格求和，即得tij。

上述的正问题等价于：算出波线PiQj经历的各个小方格的长度，根据该方格是介质还是空洞，分别乘以0和1，对经历的所有方格求和，即可得到波线PiQj经历的空洞的长度。

1.3问题的分析及数学模型

（1）问题的30

反问题可以这样求解：先由波源Pi发出的弹性波到达接收器Qj的时间tij及弹性波在介质和空气中的传播速度，算出波线PiQj经历的空洞的总长度，再由PiQj经历的每个方格的长度，即可解出每个方格是介质还是空洞（即是0还是1）。

（2）数学建模

建立坐标系如图2-2，X、Y轴上分别等距地放置n+1，m+1个波源（本题n=m=6），将平板划分为个方格，则

1）波线PiQj经历的介质的总长度pij和空洞的总长度qij满足下面两个式子：

反问题可以这样求解：先由波源Pi发出的弹性波到达31126781231323634513（如图2—2）126781231323634513（如图2—2）32

2）波线PiQj的方程为

(3）

直线方程(3)与

的交点可算出,从而求得PiQj经历的每个方格长度。

3）将个方格如图示顺序排列，第i个方格的特征量记为

(4）

全体方格的特征向量记为。

2）波线PiQj的方程为33

4）由AB至CD的波线PiQj共条，其中n+1条PiQj是无用的，去掉无用波线后n(n+1）条波线PiQj的顺序按，；,

…；排列，每条波线经历的各个方格的长度排成一行向量，于是得到条波线经历mn个方格的长度矩阵

5）将1）得到的波线PiQj经历空洞的总长度qij，按照4）中波线的顺序构成空洞长度（列）向量，则应有

（5）

4）由AB至CD的波线PiQj共34

6）完全类似地处理波线RkSl，得到m（m+1）条波线经历mn个方格的长度矩阵和空洞长度（列）向量，构造

,

则（6）当

Rank(A)=mn时可求出该方程最小二乘意义下的解

（7）

6）完全类似地处理波线RkSl，得到m（m+1）条波线35

7）取适当的

（8）

取的小方格为介质，小方格为空洞，其余的（如果有的话）无法确定。

2.3.4模型求解

%空洞探测ch23.m

%文件名：ch23.m

%计算

PiQj在每个格子中的线段长度。

clear

n=1;

7）取适当的

36

fori=0:6

forj=0:6

ai=i;aj=j;

ifi==j

aj=j+1;

ifaj==7

break;

end

end

Chudian=[ai,0];Modian=[aj,6];Dianwei=[ai,0];pp=[];

form=1:6

fori=0:6

forj=0:37

x=Chudian(1)+(Modian(1)-Chudian(1))*(m-Chudian(2))/...

(Modian(2)-Chudian(2));

Dianwei=[Dianwei;x,m];end

ifaj>ai

p=aj;aj=ai;ai=p;end

ifabs(aj-ai)>=2

fork=(aj+1):(ai-1)

y=Chudian(2)+(Modian(2)-Chudian(2))*(k-Chudian(1))/...

(Modian(1)-Chudian(1));

pp=[pp;k,y];end

end

x=Chudian(1)+(Modian(1)38

Jiaodian=[Dianwei;pp];[hang,lie]=size(Jiaodian);aa=Jiaodian(:,1);bb=unique(aa);[hang1,lie1]=size(bb);Zuobiao=[];

forii=1:hang1

forjj=1:hang

ifJiaodian(jj,1)==bb(ii)Zuobiao(ii,:)=Jiaodian(jj,:);break;end;end;end;

forpp=1:hang1-1

d=sqrt(sum((Zuobiao(pp,:)-Zuobiao(pp+1,:)).^2));

ifj<i

Jiaodian=[Dianwei;pp];[39

distance_PQ(n,ceil(Zuobiao(pp+1,1))+fix(Zuobiao(pp+1,2))*6)=d;

else

ifZuobiao(pp,2)==0

distance_PQ(n,ceil(Zuobiao(pp+1,1)))=d;

elsedistance_PQ(n,ceil(Zuobiao(pp+1,1))+fix(Zuobiao(pp,2))*6)

=d;

end

end

end

distance_PQ(n,ceil(Zuob40

ifn>=2ifdistance_PQ(n,:)==distance_PQ(n-1,:);

distance_PQ(n,:)=[];

else

n=n+1;

end

else

n=n+1;

end

end

end

ifn>=2ifdistance41

%计算矩阵

A1的秩

A1=[distance_PQ];

disp('矩阵

A1的秩')

rank(A1)

%计算RiSj在每个格子中的线段长度。

n=1;

fori=0:6

forj=0:6

ai=i;aj=j;

ifi==j

aj=j+1;

ifaj==7break;

end

%计算矩阵A1的秩

A1=[dis42

end

Chudian=[0,ai];Modian=[6,aj];Dianwei=[0,ai];pp=[];

form=1:6y=Chudian(2)+(Modian(2)-Chudian(2))*(m-Chudian(1))/...

(Modian(1)-Chudian(1));Dianwei=[Dianwei;m,y];end

ifaj>ai

p=aj;aj=ai;ai=p;end

ifabs(aj-ai)>=2

end

Chudian=[0,43

fork=(aj+1):(ai-1)x=Chudian(1)+(Modian(1)-Chudian(1))*(k-Chudian(2))/...

(Modian(2)-Chudian(2));

pp=[pp;x,k];end

end

Jiaodian=[Dianwei;pp];[hang,lie]=size(Jiaodian);aa=Jiaodian(:,2);bb=unique(aa);[hang1,lie1]=size(bb);

Zuobiao=[];

forii=1:hang1

forjj=1:hang

ifJiaodian(jj,2)==bb(ii)

fork=(aj+1):(ai-1)44

Zuobiao(ii,:)=Jiaodian(jj,:);break;end;end;end;

forpp=1:hang1-1

d=sqrt(sum((Zuobiao(pp,:)-Zuobiao(pp+1,:)).^2));

ifj<idistance_RS(n,ceil(Zuobiao(pp,1))+fix(Zuobiao(pp,2))*6)=d;

else

ifZuobiao(pp+1,1)==6

distance_RS(n,fix(Zuobiao(pp+1,2))*6)=d;

else

Zuobiao(ii,:)=Jiaodian45

distance_RS(n,ceil(Zuobiao(pp+1,1))+fix(Zuobiao(pp,2))*6)

=d;

end

end

end

ifn>=2ifdistance_RS(n,:)==distance_RS(n-1,:);

distance_RS(n,:)=[];

else

n=n+1;

end

distance_RS(n,ceil(Zuo46

else

n=n+1;

end

end

end

%对矩阵进行合并操作，计算系数矩阵

A

A=[distance_PQ;distance_RS];

disp('矩阵

A的秩')

rank(A)

%首先输入时间矩阵,并给出

b

else

n=n+1;

47

b1=[0.08950.19960.20320.41810.49230.5646;

0.09890.44130.43180.47700.52420.3805;

0.30520.41320.41530.41560.35630.1919;

0.32210.44530.40400.17890.07400.2122;

0.34900.45290.22630.19170.17680.1810;

0.38070.31770.23640.30640.22170.1031;

0.43110.33970.35660.19540.07600.0688];

b2=[0.06020.08130.35160.38670.43140.5721;

0.07530.28520.43410.34910.48000.4980;

0.34560.32050.40930.42400.45400.3112;

0.36550.32890.42470.32490.21340.1017;

0.31650.24090.32140.32560.18740.2130;

0.27490.38910.58950.30160.20580.0706;

0.44340.49190.39040.07860.07090.0914];

b1=[0.08950.1996048

lie1=[];lie2=[];

fori=1:7

m=b1(i,:)';n=b2(i,:)';

lie1=[lie1;m];lie2=[lie2;n];

end

b=[lie1;lie2];

%计算方程

Ax=b最小二乘意义下解

x=A\b;

tushi=[];

fori=0:5pp=x(i*6+1:(i+1)*6)’;tushi=[tushi;pp];

lie1=[];lie2=[];

fori=49

end

x=tushi;

disp('输出结果

X')

x

%进行空洞判断

a=0.11;b=-0.11;

fori=1:6

forj=1:6

iftushi(i,j)>b&tushi(i,j)<a

xx(i,j)=0;

else

end

x=tushi;

disp('输50

xx(i,j)=1;

end

end

end

xx

执行后输出

矩阵

A1的秩

ans=

29

矩阵

A的秩

ans=

36

输出结果

X

xx(i,j)=1;

end

51

x=

0.00980.01800.00580.0070

0.01810.0137

0.01450.12330.13250.0140

0.01370.0125

0.02030.11960.12040.0217

0.11550.0174

0.02550.01280.12730.1246

0.01730.0074

0.01270.12710.01450.0134

0.00690.0134

0.00540.01590.01340.0075

0.01850.0173

x=

0.00980.052

取ε=0.1有

xx=000000

01