供應(yīng)與選址問題

1、實(shí)驗(yàn)九供應(yīng)與選址問題【實(shí)驗(yàn)?zāi)康摹?了解非線性規(guī)劃問題的基本概念和求解方法。2通過對(duì)應(yīng)用問題的分析、建模、求解，加深對(duì)非線性規(guī)劃理論的理解。3學(xué)習(xí)掌握MATLAB有關(guān)非線性規(guī)劃求解的命令?！緦?shí)驗(yàn)內(nèi)容】某建筑公司有6個(gè)建筑工地要開工，每個(gè)工地的位置（用平面坐標(biāo)，表示，距離單位：千米）及水泥日用量（噸）由表1給出。目前有兩個(gè)廢舊的料場(chǎng)位于（5,1），（2,7）處，現(xiàn)需要重新建設(shè)、兩個(gè)料場(chǎng)，日儲(chǔ)存量各為20噸。試問料場(chǎng)、各設(shè)在何處，并且如何制定每天的原料供應(yīng)計(jì)劃，使得從、兩料場(chǎng)分別向各工地運(yùn)送水泥總的噸千米數(shù)最小。表1工地的位置（，）及各工地水泥日用量位置及用量123456橫坐標(biāo)1.258.750.5

2、5.7537.25縱坐標(biāo)1.250.754.7556.57.75（噸）3547611【實(shí)驗(yàn)準(zhǔn)備】很多實(shí)際問題所歸結(jié)的優(yōu)化數(shù)學(xué)模型中，目標(biāo)函數(shù)或約束條件很難用線性來表達(dá)。如果目標(biāo)函數(shù)或約束條件中包含有非線性函數(shù)，就稱這種優(yōu)化模型為非線性規(guī)劃問題。1非線性規(guī)劃問題數(shù)學(xué)模型的一般表示01，2， （1） 0 1，2，其中，為目標(biāo)函數(shù)，為約束函數(shù)，在這些函數(shù)中至少有一個(gè)是非線性函數(shù)。令01，2，；0 1，2， （2）稱為可行集或可行域，中的點(diǎn)稱為可行點(diǎn)。這樣（1）可用集約束的形式來表示，（3）設(shè)為目標(biāo)函數(shù)，為可行域，若對(duì)每一個(gè)均有，則稱為極小化問題（1）的最優(yōu)解（整體最優(yōu)解）；若存在的某鄰域，使得對(duì)該鄰

3、域中每個(gè)成立，則稱為極小化問題的局部最優(yōu)解。至于求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過取其相反數(shù)，化為（1）所示的一般形式。庫恩塔克（KuhnTucker）條件：若為問題（1）的可行點(diǎn)，=0，和在處可微，（）在點(diǎn)處連續(xù)，在連續(xù)可微，且有向量集，1，2，線性無關(guān)，則存在非負(fù)數(shù)，和，使得0；0；0上式簡稱為KT條件，它也是最優(yōu)解的必要條件。2非線性規(guī)劃問題的求解方法求解非線性規(guī)劃問題要比求解線性規(guī)劃問題困難得多。非線性規(guī)劃有著眾多的算法，而且仍有新算法不斷地被提出來，但它卻不像線性規(guī)劃有單純形法這一通用解法，各個(gè)算法都有特定的適用范圍，帶有一定的局限性。通常，求解帶約束條件的非線

4、性規(guī)劃問題的常見方法是：將約束問題化為無約束問題，將非線性規(guī)劃問題化為線性規(guī)劃問題，以及將復(fù)雜問題轉(zhuǎn)化為簡單的問題。非線性規(guī)劃的線性逼近法代數(shù)方法、如迭代，對(duì)于線性等式或不等式非常有效，以致很多非線性規(guī)劃問題的，可以用與之近似的線性問題來代替，使問題簡化。下面介紹的近似規(guī)劃法就是一種線性化方法。近似規(guī)劃法的基本思想：將問題（1）中的目標(biāo)函數(shù)和約束條件0（1，2，）；0（1，2，）近似為線性函數(shù)，并對(duì)變量的取值范圍加以限制，從而得到一個(gè)近似線性規(guī)劃問題，再用單純形法求解之，把符合原始條件的最優(yōu)解作為（1）的解的近似。每得到一個(gè)近似解之后，都從這點(diǎn)出發(fā)，重復(fù)以上步驟。這樣，通過求解一系列線性規(guī)劃問

5、題，產(chǎn)生一個(gè)由線性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗(yàn)表明，這樣的序列往往收斂于非線性規(guī)劃問題的解。罰函數(shù)法罰函數(shù)的基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解。這類方法稱為序列無約束最小化方法。簡稱為SUMT（其一為SUMT外點(diǎn)法，其二為SUMT內(nèi)點(diǎn)法）。3求解非線性規(guī)劃的MATLAB命令（1）MATLAB5.2及以下版本使用的命令x = constr( fun , x0 ) 求解非線性規(guī)劃模型（1）；x = constr( fun , x0, options ) 參數(shù)options的定義由實(shí)驗(yàn)一中的表1給出x = constr( fun , x0, o

6、ptions , vlb , vub ) 指定決策變量的上下界vlbxvub； x , options = constr( fun , x0 , . ) 同上，同時(shí)返回參數(shù)options的值必須先用M文件定義函數(shù)fun，其格式如下function f , g = fun( x ) f = f( x ) ; g = g1( x ) ; g2( x ) ; ; gm( x )可調(diào)用help文件來了解constr的更多用法。二次規(guī)劃的標(biāo)準(zhǔn)型為 （4） x = qp( H , c , A , b )求解二次規(guī)劃模型（4）；x = qp( H , c , A , b , vlb , vub )指定決策變

7、量的上下界vlbxvub；x = qp( H , c , A , b , vlb , vub , x0 )指定迭代的初始值x0；x = qp( H , c , A , b , vlb , vub , x0 , n )n表示中前n個(gè)約束條件等式約束；程序qp其使用格式和線性規(guī)劃中所講的lp命令相似，可以用help qp來查閱有關(guān)該命令的詳細(xì)信息（2）MATLAB5.3以上版本使用命令求解的非線性規(guī)劃模型： ，0 （5）x = fmincon( fun , x0 , A , b )求解非線性規(guī)劃模型（5），目標(biāo)函數(shù)非線性；x = fmincon( fun , x0 , A , b , Aeq ,

8、beq ) 求解模型（5），有等式約束條件；x = fmincon( fun , x0 , A , b , Aeq , beq , lb , ub ) 求解線性規(guī)劃模型（5），指定了決策變量的上下界；x = fmincon( fun , x0 , A , b , Aeq , beq , lb , ub , nonlcon ) 非線性約束條件寫成M函數(shù)形式（nonlcon.m）；function c , ceq = nonlconc = c( x )； ceq=ceq( x )；用x , Fval代替上述各命令行中左邊的x，則可得到在最優(yōu)解x處的函數(shù)值Fval；可以在MATLAB幫助文件中查閱有

9、關(guān)該命令的更多用法?！緦?shí)驗(yàn)方法與步驟】1引例問題的分析記工地的位置為（，），水泥日用量為，1，6；料場(chǎng)位置為（，），日儲(chǔ)量為，1，2；從料場(chǎng)向工地的運(yùn)送量為。這個(gè)優(yōu)化問題的目標(biāo)函數(shù)（總噸千米數(shù)）可表為（6）各工地的日用量必須滿足，所以有，1，6（7）各料場(chǎng)的運(yùn)送量不能超過日儲(chǔ)量，所以，1，2（8）則該問題的決策變量為料場(chǎng)位置，和、兩料場(chǎng)往各工地的運(yùn)送量，問題歸結(jié)為在約束條件（7）、（8）及決策變量為非負(fù)的情況下求料場(chǎng)位置（，）和運(yùn)送量使（6）的總噸千米數(shù)最小。由于目標(biāo)函數(shù)對(duì)，是非線性的，所以在求新建料場(chǎng)位置和用料時(shí)是非線性規(guī)劃模型。2MATLAB計(jì)算機(jī)求解首先定義非線性規(guī)劃的M文件函數(shù)：fun

10、ction f,g=liaoch(x)a=1.25, 8.75, 0.5, 5.75, 3, 7.25;b=1.25, 0.75, 4.75, 5, 6.5, 7.75;d=3, 5, 4, 7, 6, 11;e=20, 20;f1=0;%f1是料場(chǎng)A到各工地的噸千米總數(shù)，其中x(1)至x(6)為料場(chǎng)A往各工地的運(yùn)送量, (x(13), x(14)為A的位置for i=1:6 s(i)=sqrt(x(13)-a(i)2+(x(14)-b(i)2); f1=s(i)*x(i)+f1;endf2=0;%f2是料場(chǎng)B到各工地的噸千米總數(shù)，其中x(7)至x(12)為料場(chǎng)B往各工地的運(yùn)送量, (x(15

11、), x(16)為B的位置for i=7:12 s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2); f2=s(i)*x(i)+f2; endf=f1+f2;for i=1:6 g(i)=x(i)+x(i+6)-d(i);%各工地用量必須滿足endg(7)=sum(x(1:6)-e(1);%各料場(chǎng)運(yùn)送量不超過日儲(chǔ)量g(8)=sum(x(7:12)-e(2);然后，在MATLAB命令框里輸入求解命令： x0=zeros(1,12) 5 1 2 7;%取零為往各工地運(yùn)送量的初值，取廢棄料場(chǎng)位置為新料場(chǎng)的初值 vlb=zeros(1,16);%求解下界為零 op(13)=

12、6;op(14)=2000;%確定等式約定的數(shù)目和命令求解的最大迭代次數(shù) x,op=constr(liaoch,x0,op,vl), y=op(8)將結(jié)果作成列表的形式為工地123456新料場(chǎng)位置354710（5.6959，4.9284）0000511（7.2500，7.7500）最小的總噸千米數(shù)為89.8835。【結(jié)果分析】在命令框輸入命令 text(1.25,1.25,+3); text(8.75,0.75,+5); text(0.5,4.75,+4) text(5.75,5,+7); text(3,6.5,+6); text(7.25,7.75,+11) text(5.6959,4.92

13、84,A) text(7.2500,7.7500,B)圖9.1圖9.1畫出了工地、新料場(chǎng)的位置（+為工地，旁邊的數(shù)字為用量，A、B分別表示新料場(chǎng)的位置，可以看出，新料場(chǎng)應(yīng)建在兩個(gè)用量最大的工地旁邊，這個(gè)結(jié)果預(yù)先估計(jì)到了嗎？所求得的解是全局最優(yōu)解嗎？實(shí)際上改變決策變量的初始值，那么給各工地的供應(yīng)量和新料場(chǎng)的位置都要發(fā)生變化，不妨試試。【練習(xí)與思考】1某公司經(jīng)營兩種物品，第一種物品每噸（t）售價(jià)30元，第二種物品售價(jià)450元/t，根據(jù)統(tǒng)計(jì)，售出每噸第一種物品所需要的營業(yè)時(shí)間平均是0.5h（小時(shí)），第二種物品是2+0.25（h）,其中是第二種物品售出的數(shù)量。已知該公司在這段時(shí)間內(nèi)的總營業(yè)時(shí)間為800h，試決定使其營業(yè)額最大的營業(yè)計(jì)劃。2一基金管理者的工作是，每天將現(xiàn)有的美元、英鎊、馬克、日元四種貨幣按當(dāng)天的匯率相互兌換，使在滿足需要的條件下，按美元計(jì)算的價(jià)值最高。設(shè)某天的匯率、現(xiàn)有貨幣和當(dāng)天需求如下：美元英鎊馬克日元現(xiàn)有量（）需求量（）美元1.589281.743138.386英鎊1.69712.9579234.713馬克.57372.33808179.34681日元.004260.1261010問該基金管理者應(yīng)如何操作？（“按美元計(jì)算的價(jià)值