數(shù)學建模數(shù)學規(guī)劃模型課件

數(shù)學規(guī)劃模型的一般表達式：

為目標函數(shù),為約束函數(shù)，為約束函數(shù)，為可控變量，為已知參數(shù)，為隨機參數(shù)。數(shù)學規(guī)劃分為線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、隨機規(guī)劃、整數(shù)規(guī)劃、分式規(guī)劃、幾何規(guī)劃、目標規(guī)劃、平衡規(guī)劃、參數(shù)規(guī)劃、多目標規(guī)劃等十幾種。當然這么多規(guī)劃其中亦有交叉。又可經(jīng)過組產(chǎn)生新的規(guī)劃，每一種規(guī)劃有專著問世。

數(shù)學規(guī)劃模型的一般表達式：1第一節(jié)線性規(guī)劃模型

（1）目標函數(shù)是決策變量的線性函數(shù)。（2）約束條件都是決策變量的線性等式或不等式。第一節(jié)線性規(guī)劃模型

（1）目標函數(shù)是決策變量的線性函2MATLAB命令

命令輸入格式及線性規(guī)劃模型如下：其中：x0是算法迭代的初始點；nEq表示等式約束的個數(shù)。MATLAB命令

命令輸入格式及線性規(guī)劃模型如下：3三、建模舉例

營養(yǎng)配餐問題每種蔬菜含有的營養(yǎng)素成份是不同的，從醫(yī)學上知道，每人每周對每種營養(yǎng)成分的最低需求量。某醫(yī)院營養(yǎng)室在制定下一周菜單時，需要確定表6-1中所列六種蔬菜的供應量，以便使費用最小而又能滿足營養(yǎng)素等其它方面的要求。規(guī)定白菜的供應一周內(nèi)不多于20千克，其它蔬菜的供應在一周內(nèi)不多于40千克，每周共需供應140千克蔬菜，為了使費用最小又滿足營養(yǎng)素等其它方面的要求，問在下一周內(nèi)應當供應每種蔬菜各多少千克？三、建模舉例

營養(yǎng)配餐問題每種蔬菜含有的營養(yǎng)素成份是不同的，4表2-3表2-35問題分析與模型建立設分別表示下一周內(nèi)應當供應的青豆、胡蘿卜、菜花、白菜、甜菜及土豆的量，費用目標函數(shù)為：

約束條件：鐵的需求量至少6個單位數(shù)：磷的需求量至少25個單位數(shù)：問題分析與模型建立設6維生素A的需求量至少17500個單位：維生素C的需求量至少245個單位：煙酸的需求量至少5個單位數(shù)：

每周需供應140千克蔬菜，即維生素A的需求量至少17500個單位：7

0≤x1≤400≤x2≤400≤x3≤400≤x4≤200≤x5≤400≤x6≤40數(shù)學建模數(shù)學規(guī)劃模型課件8問題是滿足營養(yǎng)素要求的條件下，所需費用最小，是一個線性規(guī)劃模型。利用Matlab軟件編程序：%營養(yǎng)配餐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;問題是滿足營養(yǎng)素要求的條件下，所需費用最小，是一個線性規(guī)劃模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('青豆需要的份數(shù)')

x(1)8,3,53,27,5,8;10disp('胡羅卜需要的份數(shù)')

x(2)disp('菜花需要的份數(shù)')x(3)disp('白菜需要的份數(shù)')x(4)disp('甜菜需要的份數(shù)')x(5)disp('土豆需要的份數(shù)')x(6)disp('胡羅卜需要的份數(shù)')11執(zhí)行后輸出青豆需要的份數(shù)ans=

40胡羅卜需要的份數(shù)ans=

40.0000菜花需要的份數(shù)

ans=

0執(zhí)行后輸出12白菜需要的份數(shù)

ans=

20.0000甜菜需要的份數(shù)

ans=

0土豆需要的份數(shù)ans=

40最小費用

ans=

560.0000白菜需要的份數(shù)13背景：0-1規(guī)劃是數(shù)學規(guī)劃的組成部分，起始20世紀30年代末，七八十年代是數(shù)學規(guī)劃飛速發(fā)展時期，無論是從理論上還是算法方面都得到了進一步完善。時至今日數(shù)學規(guī)劃仍然是運籌學領域中熱點研究問題，從國內(nèi)外的數(shù)學建模競賽的試題中看，有近1/2的問題可用數(shù)學規(guī)劃進行求解。其中利用0-1規(guī)劃及0-1型變量的數(shù)學建模問題也為數(shù)不少，如98年的《投資的收益和風險

》，2004年的《DVD在線租賃》等問題，下面我們就來學習0-1規(guī)劃,0-1型變量在數(shù)學建模中的應用。數(shù)學建模數(shù)學規(guī)劃模型課件14

§2.20-1規(guī)劃,0-1型變量在數(shù)學建模中的應用

1、0-1規(guī)劃數(shù)學規(guī)劃模型的一般表達式：

整數(shù)規(guī)劃中決策變量只取0或1的特殊情況是0-1規(guī)劃。下面通過幾個例子說明0-1規(guī)劃在實際問題中的應用。例2.1背包問題有幾件物品，編號為1，2，…，n。第件重為kg，價值為元。今有一位裝包者欲將這些物品裝入一包，其質量不能超過kg，問應裝入哪幾件價值最大？§2.20-1規(guī)劃,0-1型變量15

解引入變量

，將物品裝包

，不將物品裝包于是得問題的模型為

取0或1，i=1，2，…，n背包問題看似簡單，但應用很廣，例如某些投資問題即可歸入背包問題模型。此類問題可以描述為：解引入變量16

投資問題：設有總額為元的資金，投資幾項事業(yè)，第項事業(yè)需投資元，利潤為元，問應選擇哪些項投資總利潤為最大？例2.2某鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油，使總的鉆探費用為最小。若10個井位的代號為，相應的鉆探費用為，并且井位選擇要滿足下列限制條件：

（1）或選和，或選；（2）選擇了或就不能選，反之亦然；（3）在中最多只能選兩個。試建立其數(shù)學模型：投資問題：設有總額為元的資金，投資幾項事17解引入變量

選擇不選擇于是以上問題的數(shù)學模型為：解引入變量18

投資的收益和風險

這是1998年全國大學生數(shù)學建模競賽的A題問題如下：市場上有n種資產(chǎn)（股票、債券、…）Si（i=1，…，n）供投資者選擇，某公司有數(shù)額為M的一筆相當大的資金可用作一個時間的投資。公司財務分析人員對這n種資產(chǎn)進行了評估，估算出在這一時期內(nèi)購買Si有平均收益率為ri，并預測出購買Si的風險損失率為qi?？紤]到投資越分散總的風險越小，公司確定，當用這筆資金購買若投資的收益和風險

這是1998年全國大19干種資產(chǎn)時，總體風險可用所投資的Si中最大的一個風險來度量。購買Si要付交易費，費率為pi，并且當購買額不超過給定值ui時，交易費按購買ui計算（不買當然無須付費）。另外，假定同期銀行存款利率是r0，且既無交易費又無風險（r0=5%）。

（1）已知n=4時的相關數(shù)據(jù)如下：

干種資產(chǎn)時，總體風險可用所投資的Si中最大的一20試給該公司設計一種投資組合方案即用給定的資金M，有選擇地購買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，而總體風險盡可能小。（2）試就一般情況對以上問題進行討論，利用以下數(shù)據(jù)進行計算。

試給該公司設計一種投資組合方案即用給定的資金21在AD邊等距地設置7個波源Ri（i=1，…，7），BC邊對等地安放7個接收器Sj（j=1，…，7），記錄由Ri發(fā)出的彈性波到達Sj的時間τij秒），見表2-3。在AD邊等距地設置7個波源Ri（i=1，…，7），BC邊對等22

2、0-1型變量在數(shù)學建模中的應用

1、空洞探測問題

1.1問題的提出

這是2000年全國大學生數(shù)學建模競賽的D題。

山體、隧洞、壩體等的某些內(nèi)部結構可用彈性波測量來確定。一個簡化問題可描述為，一塊均勻介質構成的矩形平板內(nèi)有一些充滿空氣的空洞，在平板的兩個鄰邊分別等距地設置若干波源，在它們的對邊對等地安放同樣多的接收器，記錄彈性波由每個波源到達對邊上每個接收器的時間，根據(jù)彈性波在介質中和空氣中不同的傳播速度，來確定板內(nèi)空洞的位置?，F(xiàn)考察如下的具體問題：

2、0-1型變量在數(shù)學建模中的應用

1、空洞23

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

（如圖2—1）在AB邊等距地設置7個波源Pi（i=1，…，7），CD邊對等地安放7個接收器Qj（j=1，…，7），記錄由Pi發(fā)出的彈性波到達Qj的時間tij（秒），

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

24見表2-2；見表2-2；25在AD邊等距地設置7個波源Ri（i=1，…，7），BC邊對等地安放7個接收器Sj（j=1，…，7），記錄由Ri發(fā)出的彈性波到達Sj的時間τij秒），見表2-3。在AD邊等距地設置7個波源Ri（i=1，…，7），BC邊對等26

已知彈性波在介質和空氣中的傳播速度分別為2880（米/秒）和320（米/秒），且彈性波沿板邊緣的傳播速度與在介質中的傳播速度相同。

1）確定該平板內(nèi)空洞的位置。

2）只根據(jù)由Pi發(fā)出的彈性波到達Qj的時間tij

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

討論在同樣能夠確定空洞位置的前提下，減少波源和接受器的方法。

1.2模型的假設及符號說明

（1）模型的假設

①波源和接收器的設置僅按圖中的設置來考慮，不考慮其它情況。

②在圖中的一個小方格要么全是空氣，要么全。

已知彈性波在介質和空氣中的傳播速度分別為227

是介質。

（2）符號說明

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

數(shù)，相應地n是x軸方向的方格數(shù)（已知

的n=6）；

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

數(shù)，相應地m是y軸方向的方格數(shù)（已知的

m=6）；

d1：x軸方向方格的邊長（已知的，d1=40米）；

d2：y軸方向方格的邊長（已知的，d2=40米）；

tij（i=0~6；j=0~6）：由波源Pi發(fā)生的彈性波到達

接收器Qj的時間；

是介質。

（2）符號說明

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

pij（i=0~6；j=0~6）：波線PiQj經(jīng)歷的介質的

總長度；

qij（i=0~6；j=0~6）：波線PiQj經(jīng)歷的空洞的

總長度；

v1：彈性波在介質中的傳播速度（已知的

v1=2880米/秒）；

v2：彈性波在空氣中的傳播速度（已知的

v2=320米/秒）；

pij（i=0~6；j=0~6）：波線PiQj經(jīng)29

1.3問題的分析及數(shù)學模型

（1）問題的分析

這是一個反問題，不妨先看它正問題。

已知空洞的位置及彈性波在介質和空氣中的傳播速度，求由波源Pi發(fā)出的彈性波到達接收器Qj的時間tij，為了求出tij，可先算出波線PiQj經(jīng)歷的每個小方格的長度，根據(jù)該方格是介質還是空洞，分別除以波在介質和空氣中的傳播速度，對經(jīng)歷的所有方格求和，即得tij。

上述的正問題等價于：算出波線PiQj經(jīng)歷的各個小方格的長度，根據(jù)該方格是介質還是空洞，分別乘以0和1，對經(jīng)歷的所有方格求和，即可得到波線PiQj經(jīng)歷的空洞的長度。

1.3問題的分析及數(shù)學模型

（1）問題的30

反問題可以這樣求解：先由波源Pi發(fā)出的彈性波到達接收器Qj的時間tij及彈性波在介質和空氣中的傳播速度，算出波線PiQj經(jīng)歷的空洞的總長度，再由PiQj經(jīng)歷的每個方格的長度，即可解出每個方格是介質還是空洞（即是0還是1）。

（2）數(shù)學建模

建立坐標系如圖2-2，X、Y軸上分別等距地放置n+1，m+1個波源（本題n=m=6），將平板劃分為個方格，則

1）波線PiQj經(jīng)歷的介質的總長度pij和空洞的總長度qij滿足下面兩個式子：

反問題可以這樣求解：先由波源Pi發(fā)出的彈性波到達31126781231323634513（如圖2—2）126781231323634513（如圖2—2）32

2）波線PiQj的方程為

(3）

直線方程(3)與

的交點可算出,從而求得PiQj經(jīng)歷的每個方格長度。

3）將個方格如圖示順序排列，第i個方格的特征量記為

(4）

全體方格的特征向量記為。

2）波線PiQj的方程為33

4）由AB至CD的波線PiQj共條，其中n+1條PiQj是無用的，去掉無用波線后n(n+1）條波線PiQj的順序按，；,

…；排列，每條波線經(jīng)歷的各個方格的長度排成一行向量，于是得到條波線經(jīng)歷mn個方格的長度矩陣

5）將1）得到的波線PiQj經(jīng)歷空洞的總長度qij，按照4）中波線的順序構成空洞長度（列）向量，則應有

（5）

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

6）完全類似地處理波線RkSl，得到m（m+1）條波線經(jīng)歷mn個方格的長度矩陣和空洞長度（列）向量，構造

,

則（6）當

Rank(A)=mn時可求出該方程最小二乘意義下的解

（7）

6）完全類似地處理波線RkSl，得到m（m+1）條波線35

7）取適當?shù)?/p>

（8）

取的小方格為介質，小方格為空洞，其余的（如果有的話）無法確定。

2.3.4模型求解

%空洞探測ch23.m

%文件名：ch23.m

%計算

PiQj在每個格子中的線段長度。

clear

n=1;

7）取適當?shù)?/p>

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

%對矩陣進行合并操作，計算系數(shù)矩陣

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

執(zhí)行后輸出

矩陣

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