《數(shù)學實驗 第4版》課件 第三章 最優(yōu)化方法

第三章最優(yōu)化方法實驗3.1線性規(guī)劃實驗3.2非線性規(guī)劃實驗3.1線性規(guī)劃一、線性規(guī)劃的概念二、線性規(guī)劃的圖解法三、用MATLAB優(yōu)化工具箱解線性規(guī)劃四、應用舉例：投資的收益和風險實驗3.1線性規(guī)劃需占用機床產(chǎn)品機床甲乙機床可利用時間（百臺時）A2212B128C4016D0412利潤（千元）23例1

資源的最佳利用問題：一、線性規(guī)劃的概念

某工廠有A、B、C、D四種機床，可生產(chǎn)甲、乙兩種產(chǎn)品．一件產(chǎn)品需經(jīng)各臺機床加工的時間和利潤情況如表所示，問如何安排生產(chǎn)才能使得到的利潤最高？實驗3.1線性規(guī)劃解設計劃生產(chǎn)甲產(chǎn)品件，乙產(chǎn)品件,且使達到最大值求的值，使其滿足條件實驗3.1線性規(guī)劃例2

運輸問題：

實驗3.1線性規(guī)劃設有兩個磚廠、，生產(chǎn)磚產(chǎn)量分別為23萬塊與27萬塊，、、三個工地，其需要量分別為17萬塊，將磚供應18萬塊和15萬塊．自產(chǎn)地到工地的運價如表所示．解且使具有最小值設由磚廠運往工地的磚的運量為（單位：萬塊）求的值，使其滿足條件實驗3.1線性規(guī)劃①需要確定一組變量的值，這些變量通常稱為決策變量，簡稱變量，它們通常是非負的.②對于決策變量，存在著可用一組線性等式或不等式來表達的限制條件，這些條件稱為約束條件.③有一個可以表示為決策變量的線性函數(shù)的目標要求，這一函數(shù)稱為目標函數(shù)．按問題的不同要求，可要求目標函數(shù)達到最大值或最小值．

在線性約束條件下，要求一組決策變量的值，使線性目標函數(shù)達到最大值或最小值的問題，就叫做線性規(guī)劃問題，常用符號LP(LinearProgramming)表示。以上兩個例子具有三個共同的特征：實驗3.1線性規(guī)劃，也稱非負條件；稱為價值系數(shù)．滿足約束條件的決策變量的一組值，稱為線性規(guī)劃的可行解使目標函數(shù)達到所要求的最大值或最小值的可行解，稱為線性規(guī)劃的最優(yōu)解，也就是線性規(guī)劃的解．

求線性規(guī)劃的解的過程叫做解線性規(guī)劃．實驗3.1線性規(guī)劃,達到所要求的最大值或最小值s.t.(subjectedto)標準形式矩陣形式s.t.實驗3.1線性規(guī)劃只含兩個決策變量的線性規(guī)劃問題，可以用圖解法求解．二、線性規(guī)劃的圖解法約束條件目標函數(shù)達到最大值，當直線移動到點時，于是最優(yōu)解是最優(yōu)值為例1實驗3.1線性規(guī)劃約束條件目標函數(shù)例3

解線性規(guī)劃：問題無最優(yōu)解線性規(guī)劃有唯一解、無窮多解或無解三種情況．

對于決策變量兩個以上的線性規(guī)劃就不能用圖解法，最常用、最有效的算法之一是單純形方法。實驗3.1線性規(guī)劃minz=cX

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

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注：若沒有不等式約束條件存在，則令A=[]，b=[].三、解線性規(guī)劃的MATLAB實現(xiàn)實驗3.1線性規(guī)劃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(…)返回最優(yōu)解ｘ及ｘ處的目標函數(shù)值fval.實驗3.1線性規(guī)劃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線性規(guī)劃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線性規(guī)劃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線性規(guī)劃具有最小值．x=

0

8

15

17

10

0fval=

3650即以下運輸方案是最優(yōu)的運量（萬塊）工地磚廠081517100實驗3.1線性規(guī)劃約束條件目標函數(shù)例3解線性規(guī)劃：a=[-2,1;1,-1];b=[4,2];c=-[1,1];v1=[0,0];x=linprog(c,a,b,[],[],v1)↙實驗3.1線性規(guī)劃問題無界。x=[]表明此線性規(guī)劃無最優(yōu)解.四、應用舉例：投資的收益和風險1、問題提出實驗3.1線性規(guī)劃市場上有n種資產(chǎn)（i=1,2……n）可以選擇，

現(xiàn)用數(shù)額為M的相當大的資金作一個時期的投資。

這n種資產(chǎn)在這一時期內(nèi)購買的平均收益率為風險損失率為，投資越分散，總的風險越小，總體風險可用投資的

中最大的一個風險來度量。

購買時要付交易費，(費率)，

當購買額不超過給定值時，交易費按購買計算。

另外，假定同期銀行存款利率是，既無交易費又無風險。

（=5%）

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

試給該公司設計一種投資組合方案，即用給定達到資金M，有選擇地購買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，使總體風險盡可能小。實驗3.1線性規(guī)劃符號規(guī)定基本假設實驗3.1線性規(guī)劃2、模型的建立(1)

總體風險用所投資的中最大的一個風險來衡量，即(3)

要使凈收益盡可能大,總體風險盡可能小,這是一個多目標規(guī)劃。實驗3.1線性規(guī)劃(2)

購買

所付交易費是一個分段函數(shù)，即交易費=可以忽略不計，這樣購買的凈收益為而題目所給定的定值(單位:元)相對總投資M很小,

更小，目標函數(shù)

約束條件模型1

固定風險水平，優(yōu)化收益約束條件：目標函數(shù)：實驗3.1線性規(guī)劃3、模型簡化(1)在實際投資中，投資者承受風險程度不一樣，若給定風險一個界限a，使最大的一個風險

可找到相應的投資方案。這樣把多目標規(guī)劃變成一個目標的線性規(guī)劃。

(2)若投資者希望總盈利至少達到水平以上，在風險最小的情況下尋找相應的投資組合。模型2

固定盈利水平，極小化風險目標函數(shù)：約束條件：實驗3.1線性規(guī)劃目標函數(shù)：

模型3

約束條件：實驗3.1線性規(guī)劃(3)投資者在權衡資產(chǎn)風險和預期收益兩方面時，希望選擇一個令自己滿意的投資組合。

因此對風險、收益賦予權重

稱為投資偏好系數(shù)。4、模型求解

模型1實驗3.1線性規(guī)劃

由于a是任意給定的風險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風險度。我們從a=0開始，以步長△a=0.001進行循環(huán)搜索，編制程序如下：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線性規(guī)劃部分計算結果如下：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線性規(guī)劃5、結果分析(3)

曲線上的任一點都表示該風險水平的最大可能收益和該收益要求的最小風險。對于不同風險的承受能力，選擇該風險水平下的最優(yōu)投資組合。(2)

當投資越分散時，投資者承擔的風險越小，這與題意一致。即:冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。(1)

風險越大，收益也越大。實驗3.1線性規(guī)劃(4)在a=0.006附近有一個轉(zhuǎn)折點，在這一點左邊，風險增加很少時，利潤增長很快。在這一點右邊，風險增加很大時，利潤增長很緩慢。所以對于風險和收益沒有特殊偏好的投資者來說，應該選擇曲線的拐點作為最優(yōu)投資組合。類似地,可解模型2和3.大約是a*=0.6%，Q*=20%，所對應投資方案為:

風險度收益

x0x1x2x3x40.00600.201900.24000.40000.10910.2212實驗3.1線性規(guī)劃模型2目標函數(shù)：約束條件：模型2’目標函數(shù)：約束條件：實驗3.1線性規(guī)劃目標函數(shù)：

模型3

約束條件：目標函數(shù)：

模型3’

約束條件：實驗3.1線性規(guī)劃第三章最優(yōu)化方法實驗3.1線性規(guī)劃實驗3.2非線性規(guī)劃實驗3.2非線性規(guī)劃一、非線性規(guī)劃的概念二、二次規(guī)劃三、無約束非線性規(guī)劃四、帶約束非線性規(guī)劃五、應用舉例一、非線性規(guī)劃的概念

如果目標函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題.

一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多.而且，也不象線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個方法都有自己特定的適用范圍.

下面通過實例歸納出非線性規(guī)劃數(shù)學模型的一般形式，介紹有關非線性規(guī)劃的基本概念.實驗3.2非線性規(guī)劃故有限制條件元.試選擇最佳投資方案.元，并預計可收益?zhèn)€項目可供選擇投資，并且至少要對（投資決策問題）某企業(yè)有元，投資于第個項目需花資金例4其中一個項目投資.已知該企業(yè)擁有總資金解設投資決策變量為則投資總額為，投資總收益為因為公司至少要對一個項目投資，并且總的投資金額不能超過總資金A，實驗3.2非線性規(guī)劃另外，由于只取值0或1，所以還有最佳投資方案應是投資額最小而總收益最大的方案.s.t.所以這個最佳投資決策問題歸結為總資金以及決策變量（取0或1）的限制條件下，極大化總收益和總投資之比.因此，其數(shù)學模型為：實驗3.2非線性規(guī)劃

上面例題是在一組等式或不等式的約束下，求一個函數(shù)的最大值（或最小值）問題，其中目標函數(shù)或約束條件中至少有一個非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題，簡記為（NP）.其中稱為決策變量，稱為目標函數(shù)，和稱為約束函數(shù).稱為等式約束，稱為不等式約束.實驗3.2非線性規(guī)劃可概括為一般形式

對于一個實際問題，在把它歸結成非線性規(guī)劃問題時，一般要注意以下幾點：(1)確定供選方案：首先要收集同問題有關的資料和數(shù)據(jù)，在全面熟悉問題的基礎上，確認什么是問題的可供選擇的方案，并用一組變量來表示它們.(2)提出追求目標：經(jīng)過資料分析，根據(jù)實際需要和可能，提出要追求極小化或極大化的目標.并且，運用各種科學和技術原理，把它表示成數(shù)學關系式.(3)給出價值標準：在提出要追求的目標之后，要確立所考慮目標的“好”或“壞”的價值標準，并用某種數(shù)量形式來描述它.實驗3.2非線性規(guī)劃(4)尋求限制條件：由于所追求的目標一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示.

如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達到（特別是可行域的頂點上達到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點達到.我們先來討論最簡單的非線性規(guī)劃——二次規(guī)劃．實驗3.2非線性規(guī)劃二、二次規(guī)劃

二次規(guī)劃（QuadraticProgramming，記作QP）指目標函數(shù)是二次函數(shù)，約束條件為線性的.其一般形式為：s.t.為階對稱矩陣，特別地，當正定時，目標函數(shù)為凸函數(shù)，線性約束下可行域是凸集，稱為凸二次規(guī)劃．實驗3.2非線性規(guī)劃式中的意義與線性規(guī)劃相同，、、、、MATLAB解二次規(guī)劃的程序：

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非線性規(guī)劃例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非線性規(guī)劃x=0.66671.3333z=

-16.4444三、無約束非線性規(guī)劃無約束非線性規(guī)劃的一般形式是可以是非線性的．其中[x,fval]=fminbnd(fun,x1,x2,options)，這里fun是用M文件定義的函數(shù)或Matlab中的單變量數(shù)學函數(shù).這實際上就是多元函數(shù)極值問題．1．求單變量有界非線性函數(shù)在區(qū)間上的極小值:Matlab的命令為它的返回值是極小值點和函數(shù)的極小值.實驗3.2非線性規(guī)劃例6

求函數(shù)

的最小值.

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

即可求得極小值點和極小值.x=3y=-1實驗3.2非線性規(guī)劃例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非線性規(guī)劃

所以函數(shù)在x=3.9270處取得最小值-0.0279，在x=0.7854處取得最大值0.6448.，則水槽的容積為：例8有一張邊長為3m的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪可使水槽的容積最大？解設剪去的正方形的邊長為建立無約束優(yōu)化模型為：先編寫M文件fun2.m如下:functionf=fun2(x)f=-(3-2*x).^2*x;主程序為:[x,fval]=fminbnd('fun2',0,1.5);xmax=xfmax=-fval↙實驗3.2非線性規(guī)劃運算結果為:xmax=0.5000fmax=2.0000即剪掉的正方形的邊長為0.5米時水槽的容積最大,最大容積為2立方米.實驗3.2非線性規(guī)劃2．求多變量函數(shù)的極小值其中是一個向量，是一個標量函數(shù).Matlab中求解多變量函數(shù)極小值的基本命令有兩個：[x,fval]=fminunc(fun,x0,options,p1,p2,...)[x,fval]=fminsearch(fun,x0,options,p1,p2,...).實驗3.2非線性規(guī)劃例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非線性規(guī)劃[x,y]=fminsearch('fun3',x0)↙x=0.5000-1.0000y=5.1425e-10四、帶約束非線性規(guī)劃

帶有約束條件的極值問題稱為約束極值問題，也叫約束規(guī)劃問題.求解約束極值問題要比求解無約束極值問題困難得多.為了簡化其優(yōu)化工作，可采用以下方法：帶約束非線性規(guī)劃的一般形式為:其中是定義在上的實值函數(shù)．實驗3.2非線性規(guī)劃將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復雜問題變換為較簡單問題的其它方法.標準型為：用Matlab解非線性規(guī)劃的一般步驟是：（1）首先建立M文件fun.m，定義目標函數(shù)F(ｘ):functionf=fun(ｘ);f=F(ｘ);（2）若約束條件中有非線性約束:C(x)<=0或Ceq(x)=0，則建立M文件nonlcon.m定義函數(shù)C(x)與Ceq(x):Function[C,Ceq]=nonlcon(x)C=...Ceq=...實驗3.2非線性規(guī)劃（3）建立主程序．非線性規(guī)劃求解的函數(shù)是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為返回的函數(shù)的值，X0為迭代的初值，VLB,VUB變量上下限，options參數(shù)說明．實驗3.2非線性規(guī)劃例10

求s.t.解

（1）先建立M文件fun4.m,定義目標函數(shù):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非線性規(guī)劃（3）求解非線性規(guī)劃: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非線性規(guī)劃例11

拋物面被平面截成一橢圓，求原點到這橢圓的最短距離．解（1）先建立M文件fun5.m,定義目標函數(shù):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非線性規(guī)劃（4）運算結果為：x=0.36600.36600.2679fval=0.5829實驗3.2非線性規(guī)劃（3）求解非線性規(guī)劃: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年內(nèi)使用完,若在一年內(nèi)使用資金x萬元,則可得效益年利率為10%.試制定出資金的使用計劃,以使4年效益之和為最大.萬元(效益不能再使用),當年不用的資金可存入銀行,解設變量表示第i年所使用的資金數(shù),則有

實驗3.2非線性規(guī)劃（1）先建立M文件fun6.m,定義目標函數(shù):functionf=fun6(x)f=-(sqrt(x(1))+sqrt(x(2))+sqrt(x(3))+sqrt(x(4)));（2）由于沒有非線性約束條件，可直接求解非線性規(guī)劃:

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非線性規(guī)劃（3）結果為:實驗3.2非線性規(guī)劃x=86.1883104.2878126.1883152.6879fval=-43.0860五、應用舉例:供應與選址總的噸千米數(shù)最?。?/p>

某公司有6個建筑工地，每個工地的位置（用平面坐標a，b表示，單位：km）及水泥日用量d（單位：t）由表給出．目前有兩個臨時料場位于，日儲量各有20t．（1）假設從料場到工地之間均有直線道路相連，試制訂每天的供應計劃，即從A、B兩料場分別向各工地運送多少噸水泥，使工地1234561.258.750.55.7537.251.250.754.7556.57.753547611（2）為了進一步減少噸千米數(shù)，打算舍棄兩個臨時料場，改建兩個新的，日儲量仍各為20t，問應建在何處，節(jié)省的噸千米數(shù)有多大．實驗3.2非線性規(guī)劃62，因此目標函數(shù)為：解向工地從料場的運送量為記工地的位置為，水泥日用量，，料場位置為，日儲量為約束條件實驗3.2非線性規(guī)劃，這是一個線性規(guī)劃問題，（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