數(shù)學(xué)規(guī)劃建模

《數(shù)學(xué)規(guī)劃建?！酚蓵T分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)規(guī)劃建模（154頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,,,*,,,,,1,,最優(yōu)化問題的,數(shù)學(xué)模型的一般形式,為：,（,1,）,（,2,）,三個要素：決策變量,decision bariable,，目標(biāo)函數(shù),objective function,，約束條件,constraints,。,,2,,,（,2,）所確定的,x,的范圍稱為,可行域,feasible region,，滿足（,2,）的解,x,稱為,可行解

2、,feasible solution,，同時滿足（,1,）（,2,）的解,x,稱為,最優(yōu)解,Optimal solution,，整個可行域上的最優(yōu)解稱為,全局最優(yōu)解,global optimal solution,，可行域中某個領(lǐng)域上的最優(yōu)解稱為,局部最優(yōu)解,local optimal solution,。最優(yōu)解所對應(yīng)的目標(biāo)函數(shù)值稱為,最優(yōu)值,optimum,。,,3,,,優(yōu)化模型的分類,（一）按有無約束條件,（,2,）可分為：,,,1.,無約束優(yōu)化,unconstrained optimization,。,,,2.,約束優(yōu)化,constrained optimization,。,,大部分實際

3、問題都是約束優(yōu)化問題。,,4,,,（二）,按決策變量取值是否連續(xù),可分為：,,1.,數(shù)學(xué)規(guī)劃或連續(xù)優(yōu)化,。,,可繼續(xù)劃分為,線性規(guī)劃,(,LP)Linear programming,和,非線性規(guī)劃,(,NLP) Nonlinear programming,。在非線性規(guī)劃中有一種規(guī)劃叫做,二次規(guī)劃,(QP)Quadratic programming,，目標(biāo)為二次函數(shù)，約束為線性函數(shù)。,,2.,離散優(yōu)化或組合優(yōu)化,。,,包含：,整數(shù)規(guī)劃,(IP)Integer programming,，整數(shù)規(guī)劃中又包含很重要的一類規(guī)劃：,0-1,（整數(shù)）規(guī)劃,Zero-one programming,，這類規(guī)劃問

4、題的決策變量只取,0,或者,1,。,,5,,,（三）,按目標(biāo)的多少,可分為：,,1.,單目標(biāo)規(guī)劃。,,2.,多目標(biāo)規(guī)劃。,,（四）,按模型中參數(shù)和變量是否具有不確定性,可分為：,,1.,確定性規(guī)劃。,,2.,不確定性規(guī)劃。,,（五）,按問題求解的特性,可分為：,,1.,目標(biāo)規(guī)劃。,,2.,動態(tài)規(guī)劃。,,3.,多層規(guī)劃。,,4.,網(wǎng)絡(luò)優(yōu)化。,,5.……,等等。,,6,,,優(yōu)化問題求解常用的軟件,,LINGO,軟件和,MATLAB,軟件。,,對于,LINGO,軟件，線性優(yōu)化求解程序通常使用,單純形法,simplex method,，單純形法雖然在實際應(yīng)用中是最好最有效的方法，但對某些問題具有指數(shù)階

5、的復(fù)雜性，為了能解大規(guī)模問題，也提供了,內(nèi)點算法,interior point method,備選（,LINGO,中一般稱為障礙法，即,barrier,），非線性優(yōu)化求解程序采用的是,順序線性規(guī)劃法,，也可用,順序二次規(guī)劃法,，廣義既約梯度法，另外可以使用多初始點（,LINGO,中稱,multistart,）找多個局部最優(yōu)解增加找全局最優(yōu)解的可能，還具有全局求解程序,—,分解原問題成一系列的,凸規(guī)劃,。,,7,,,軟件介紹,,例,1,,帆船生產(chǎn)計劃,,SAILCO,公司需要決定下四個季度的帆船生產(chǎn)量。下四個季度的帆船需求量分別是,40,條，,60,條，,75,條，,25,條，這些需求必須按時滿

6、足。每個季度正常的生產(chǎn)能力是,40,條帆船，每條船的生產(chǎn)費用為,400,美元。如果加班生產(chǎn)，每條船的生產(chǎn)費用為,450,美元。每個季度末，每條船的庫存費用為,20,美元。假定生產(chǎn)提前期為,0,，初始庫存為,10,條船。如何安排生產(chǎn)可使總費用最?。?,分析,:,,DEM,－需求量，,RP,－正常生產(chǎn)的產(chǎn)量，,,OP,－加班生產(chǎn)的產(chǎn)量，,INV,－庫存量，,,則,DEM,RP,OP,INV,對每個季度都應(yīng)該有一個對應(yīng)的值，也就說他們都應(yīng)該是一個由,4,個元素組成的,數(shù)組,，其中,DEM,是已知的，而,RP,OP,INV,是未知數(shù)。,,8,,,目標(biāo)函數(shù)：正常生產(chǎn)費＋加班生產(chǎn)費＋儲存費 最小,約束

7、條件：,1,）能力限制：,2,）產(chǎn)品數(shù)量的平衡方程：,4,）變量非負(fù),3,）初始庫存：,－引例－ 模型建立,,9,,,記四個季度組成的集合,QUARTERS={1,，,2,，,3,，,4},，它們就是上面數(shù)組的,下標(biāo)集合,，而數(shù)組,DEM,RP,OP, INV,對集合,QUARTERS,中的每個元素,1,，,2,，,3,，,4,分別對應(yīng)于一個值。,LINGO,正是充分利用了這種,數(shù)組及其下標(biāo),的關(guān)系，引入了“集合”及其“屬性”的概念，把,QUARTERS={1,，,2,，,3,，,4},稱為,集合,，把,DEM,RP,OP, INV,稱為該集合的,屬性,(,即定義在該集合上的屬性,),。,－集

8、合與屬性－,,10,,,QUARTERS,集合的屬性,DEM,,,RP,OP,,INV,,,QUARTERS,集合,2,3,4,1,－集合與屬性－,,11,,,集合元素及集合的屬性確定的所有,變量,集合,QUARTERS,的元素,,1,2,3,4,定義在集合,,QUARTERS,,上的屬性,DEM,DEM(1),DEM(2),DEM(3),DEM(4),,RP,RP(1),RP(2),RP(3),RP(4),,OP,OP(1),OP(2),OP(3),OP(4),,INV,INV(1),INV(2),INV(3),INV(4),,－集合與屬性－,,12,,,－程序編寫－,,MODEL:,,!,

9、集合段：定義集合,SET,，元素,member,及其屬性,attribute,；,,,SETS:,,QUARTERS/1,2,3,4/:DEM,RP,OP,INV;,,ENDSETS,,!,目標(biāo)與約束段：沒有開始和結(jié)束標(biāo)記，順序無關(guān)；,,,MIN=@SUM(QUARTERS(I):400*RP(I)+450*OP(I)+20*INV(I));,,,@FOR(QUARTERS(I):RP(I)<40);,,@FOR(QUARTERS(I),|I#GT#1,:,,INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););,,INV(1)=10+RP(1)+OP(1)-DEM(1);

10、,,!,數(shù)據(jù)段：對集合的屬性輸入必要的常數(shù)數(shù)據(jù)；,,,DATA:,,DEM=40,60,75,25;,,ENDDATA,,,END,或,1..4,或用空格或回車隔開，“屬性＝常數(shù)列表”,對“：”前的每個元素求和或循環(huán),,遍歷下標(biāo)元素，可省略下標(biāo),“,︱,”,后是過濾條件，邏輯關(guān),,系式,I>1,（,greater than,）,,13,,,－展開式－,LINGO︱Generate︱Disply Model(Ctrl+G),MIN=@SUM(QUARTERS(I):400*RP(I)+450*OP(I)+20*INV(I));,,,@FOR(QUARTERS(I):RP(I)<40);,,@FO

11、R(QUARTERS(I),|I#GT#1,:,,INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););,,INV(1)=10+RP(1)+OP(1)-DEM(1);,,14,,,全局最優(yōu)解,,RP=(40,40,40,25),,OP=(0,10,35,0),最小成本,=78450,自動生成行號,－結(jié)果報告－,,15,,,例,2,運輸問題,,16,,,解：設(shè),A,1,,A,2,調(diào)運到三個糧站的大米分別為,x,11,，,,x,12,，,,x,13,，,,x,21,，,,x,22,，,,x,23,噸。,題設(shè)量可總到下表：,8,4,庫,存,量,x,23,x,22,x,21,A,2

12、,5,4,2,需要量,x,13,x,12,x,11,A,1,B,3,B,2,B,1,糧庫,糧站,距離及運量,12,12,24,30,8,24,,17,,,結(jié)合存量限制和需量限制得數(shù)學(xué)模型,：,,18,,,程序編寫 推薦,,,MODEL,:,,TITLE,,調(diào)運大米的運輸問題程序４,;,,!,定義集合段,;,,SETS,:,,LIANGKU/1..2/:A;,!,定義糧庫的集合,;,,LIANGZHAN/1..3/:B;,!,定義糧站的集合,;,,YULIANG(LIANGKU,LIANGZHAN):X,C;,!,定義運量和距離,;,,ENDSETS,,DATA,:,,!,糧庫到糧站的距離,;

13、,,C= 12 24 8,,,,30 12 24;,,19,,,!,糧庫的限量,;,,A=4 8 ;,,!,糧站的限量,;,,B=2 4 5;,,ENDDATA,,[OBJ],MIN,=,@SUM,(YULIANG:C*X);,,!,糧庫上限的約束,;,,@FOR,(LIANGKU(I):[LK],,,@SUM,(LIANGZHAN(J):X(I,J))B(J));,,END,,,20,,,程序的調(diào)試,,,1.,直接點擊運行，如果出錯會彈出錯誤提示

14、，根據(jù)提示做相應(yīng)的修改；,,,2.,可以用“！”把約束變成說明語句，而把這條語句屏蔽掉，縮小尋找出錯的范圍；,,,3.,可以邊寫程序邊運行，保證每行書寫都是正確的程序；,,21,,,料場的建立與運輸,建筑工地的位置,(,用平面坐標(biāo),a,,,b,表示，距離單位：公里,),及水泥日用量,d,(,噸,),下表給出。有兩個臨時料場位于,P (5,1), Q (2, 7),,日儲量各有,20,噸。,(1),從,A, B,兩料場分別向各工地運送多少噸水泥，使總的噸公里數(shù)最小。,(2),兩個新的料場應(yīng)建在何處，節(jié)省的噸公里數(shù)有多大？,,１,２,３,４,５,６,a,1.25,8.75,0.5,5.75,3,7

15、.25,b,1.25,0.75,4.75,5,6.5,7.75,d,3,5,4,7,6,11,非線性規(guī)劃－引例,－,,22,,,已知為,LP,模型，未知為,NLP,模型,－引例－ 模型建立,料場向工地的運送量為：,工地：位置,水泥日用量：,料場：位置,日儲量：,,23,,,利用集合的概念，可以定義需求點,DEMAND,和供應(yīng)點,SUPPLY,兩個集合，分別有,6,個和,2,個元素,(,下標(biāo),),。但決策變量,(,運送量,),c,ij,與集合,DEMAND,和集合,SUPPLY,都有關(guān)系的。該如何定義這樣的屬性？,集合的屬性相當(dāng)于以集合的元素為下標(biāo)的數(shù)組。這里的,c,ij,相當(dāng)于二維數(shù)組。它的兩

16、個下標(biāo)分別來自集合,DEMAND,和,SUPPLY,，因此可以定義一個由二元對組成的新的集合，然后將,c,ij,定義成這個新集合的屬性，這個集合稱為,派生集合,。,－派生集合－,,24,,,－程序編寫－,MODEL:,,Title Location Problem;,,sets:,,demand/1..6/:a,b,d;,,supply/1..2/:x,y,e;,,link(demand,supply):c;,,endsets,,data:,,!locations for the demand(,需求點的位置,);,,a=1.25,8.75,0.5,5.75,3,7.25;,,b=1.25,0

17、.75,4.75,5,6.5,7.75;,,!quantities of the demand and supply,（供需量）,;,,d=3,5,4,7,6,11; e=20,20;,,enddata,,……,基本集合,primary set,與,,派生集合,derived set,（定義多維數(shù)組）,,25,,,－程序編寫－,……,,!,初始段：對集合屬性定義初值（迭代算法的迭代初值）,;,,init:,,!initial locations for the supply,（初始點）,;,,x,y=5,1,2,7;,,endinit,,!Objective function,（目標(biāo)）,;,,

18、[OBJ] min=@sum(link(i,j): c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2) );,,!demand constraints,（需求約束）,;,,@for(demand(i):,[DEMAND_CON],@sum(supply(j):c(i,j)) =d(i););,,!supply constraints,（供應(yīng)約束）,;,,@for(supply(i):[SUPPLY_CON] @sum(demand(j):c(j,i)) <=e(i); );,,@for(supply: @bnd(0.5,X,8.75); @bnd(0.75,Y

19、,7.75); );,,END,LINGO,對數(shù)值順序按列賦值，即：,x=5,2;y=1,7;,標(biāo)號自動在后加下標(biāo) *,_1 , _2…,比,@free(x);@free(y);,要好，可減少計算工作量,,26,,,－求解觀察－,激活全局最優(yōu)解：,,LINGO︱Options→Global Solver︱Use Global Solver,,27,,,－結(jié)果報告－,工地與料場運輸示意圖,: “,*,”,表示料場，“,+,”,表示工地,,,28,,,－認(rèn)識“初始段”－,……,,data:,,!(,需求點的位置,);,,a=1.25,8.75,0.5,5.75,3,7.25;,,b=1.25,0.

20、75,4.75,5,6.5,7.75;,,!,（供需量）,;,,d=3,5,4,7,6,11; e=20,20;,,Enddata,,init:,,!,（初始點）,;,,x,y=5,1,2,7;,,Endinit,,……,……,,data:,,!(,需求點的位置,);,,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;,,x,y=5,1,2,7;,,Enddata,,init:,,!,（初始點）,;,,Endinit,,……,求解,NLP,問題,求解,L

21、P,問題,只對非線性模型起作用,,29,,,－知識重整－,LINGO,建模語言也稱為矩陣生成器（,MATRIX GENERATOR,）。類似,DEMAND,和,SUPPLY,直接把元素列舉出來的集合，稱為,基本集合,(primary set),,,而把,LINK,這種基于其它集合而派生出來的二維或多維集合稱為,派生集合,(derived set),。由于是,DEMAND,和,SUPPLY,生成了派生集合,LINK,，所以,DEMAND,和,SUPPLY,稱為,LINK,的,父集合,。,,表示集合,LINK,中的元素就是集合,DEMAND,和,SUPPLY,的元素組合成的有序二元組，從數(shù)學(xué)上看,

22、LINK,是,DEMAND,和,SUPPLY,的笛卡兒積，也就是說,,LINK={,（,S,，,T,）,|S,∈,DEMAND,，,T,∈,SUPPLY},,因此，其屬性,C,也就是一個,6*2,的矩陣（或者說是含有,12,個元素的,二維數(shù)組,）。,,30,,,－模型構(gòu)成－,一般來說，,LINGO,中建立的優(yōu)化模型可以由五個部分組成，或稱為五“段”（,SECTION,）：,（,1,）,集合段,（,SETS,）：以“,SETS:”,開始， “,ENDSETS”,結(jié)束，定義必要的集合變量（,SET,）及其元素（,MEMBER,，含義類似于數(shù)組的下標(biāo)）和屬性（,ATTRIBUTE,，含義類似于數(shù)組）

23、。,（,2,）,目標(biāo)與約束段,：目標(biāo)函數(shù)、約束條件等，沒有段的開始和結(jié)束標(biāo)記，因此實際上就是除其它四個段,(,都有明確的段標(biāo)記,),外的,LINGO,模型。,（,3,）,數(shù)據(jù)段,(DATA),：以 “,DATA:”,開始,, “ENDDATA”,結(jié)束，,,對集合的屬性,(,數(shù)組,),輸入必要的常數(shù)數(shù)據(jù)。,,格式為：“,attribute(,屬性,) = value_list(,常數(shù)列表,);,”,,31,,,－模型構(gòu)成－,(5),計算段,:,在數(shù)據(jù)段輸入完成之后在正式求解模型之前對,,原始數(shù)據(jù)進行處理，語句是,順序,執(zhí)行的，不能更換順序，只能,,直接使用,賦值語句,，不能包含需要經(jīng)過解方程或經(jīng)

24、過求解優(yōu)化,,問題以后才能決定的變量。,CALC,:,,T_DEM=@,SUM,(QUARTERS:DEM);,!,總需求；,,A_DEM=T_DEM/@,SIZE,(QUARTERS);,!,平均需求；,,ENDCALC,（,4,）,初始段,(INIT),：以“,INIT: ”,開始， “,ENDINIT”,結(jié)束，,,對集合的屬性,(,數(shù)組,),定義初值,(,因為求解算法一般是迭代算法，,,所以用戶如果能給出一個比較好的迭代初值，對提高算法的計,,算效果是有益的,),。,,格式為：“,attribute,（屬性）,= value_list,（常數(shù)列表）；,”,,32,,,－試一試－,使用集合

25、改寫下面程序：,,min=-5*x1-2*x2,；,,2*x1+x2+x3=8,；,,x1+x4=3,；,,x2+x5=4;,?,請動手試一下,MODEL,:,,TITLE,,露一小手,;,,SETS,:!,集合段,;,,HANG/1..3/:B;,,LIE/1..5/:C,X;,,XISHU(HANG,LIE):A;,,ENDSETS,,DATA,:,,A= 2 1 1 0 0,,1 0 0 1 0,,0 1 0 0 1;,,C=-5 -2 0 0 0;,,B=8 3 4;,,ENDDATA,,[OBJ],MIN=@SUM,(LIE:C*X);,,@FOR,(HANG(I):[YUESHU]

26、,,,@SUM,(LIE(J):A(I,J)*X(J))=B(I));,,END,SETS,:,,HANG:B;,,……,,ENDSETS,,DATA,:,,HANG=1..3;,,……,,ENDDATA,,……,教你一招,,33,,,線性規(guī)劃,怎樣建立優(yōu)化模型與,LINGO,軟件的使用,,34,,,線性規(guī)劃模型的一般形式：,,35,,,一般線性規(guī)劃問題都可以通過引入非負(fù)的松弛變量,slack variable,與非負(fù)的剩余變量,surplus v-ariable,的方法化為標(biāo)準(zhǔn)形式（約束全是等約束）。,線性規(guī)劃問題的可行域,feasible region,是一個凸集,convex set,（

27、任意兩點的連線上的點都在區(qū)域內(nèi)部，可以看作是沒有凹坑的凸多面體），所以最優(yōu)解,Optimal solution/point,在凸多面體的某個頂點上達到,求解方法：單純形算法,simplex method,。,,36,,,連續(xù)性線性規(guī)劃,,1.,比例性,：每個決策變量對目標(biāo)函數(shù)以及右端項的貢獻與該決策變量的取值成正比。,,2.,可加性,：每個決策變量對目標(biāo)函數(shù)以及右端項的貢獻與其他決策變量的取值無關(guān)。,,3.,連續(xù)性,：每個決策變量的取值都是連續(xù)的。,線性規(guī)劃問題的性質(zhì),,37,,,例,3,階段生產(chǎn)問題,某公司生產(chǎn)某產(chǎn)品,,,最大生產(chǎn)能力為,10000,單位,,,每單位,,存儲費,2,元,,,預(yù)

28、定的銷售量與單位成本如下,:,月份,單位成本,(,元,),銷售量,1,,2,,3,,4,,70 6000,,72 7000,,80 12000,,76 6000,求一生產(chǎn)計劃,,,使,1),滿足需求,; 2),不超過生產(chǎn)能力,;,,3),成本,(,生產(chǎn)成本與存儲費之和,),最低,.,,38,,,解,:,假定,1,月初無庫存,,4,月底買完,,,當(dāng)月生產(chǎn)的不庫,

29、,存,,,庫存量無限制,.,第,j+1,個月的庫存量,第,j+1,個月的庫存費,共,3,個月的庫存費,到本月總生產(chǎn)量大于等于銷售量,4,個月總生產(chǎn)量等于總銷售量,4,個月總生產(chǎn)成本,,39,,,,model,:,,title,,生產(chǎn)計劃程序,1;,,Sets,:,,yuefen/1..4/:c,x,e,d;,,endsets,,data,:,,c=70 71 80 76;,,d=6000 7000 12000 6000;,,e=2 2 2 2 ;,,a=10000;,,enddata,,min,=,@sum,(yuefen:c*x)+,,,@sum,(yuefen(j)|j#lt#4:,,,@

30、sum,(yuefen(i)|i#le#j:x-d)*e(j+1));,,@for,(yuefen(j)|j#lt#4:,,,@sum,(yuefen(i)|i#le#j:x)>,@sum,(yuefen(i)|i#le#j:d));,,@sum,(yuefen:x)=,@sum,(yuefen:d);,,@for,(yuefen:x

31、0 6000;,,e=2 2 2 2 ;,,a=10000;,,enddata,,min,=,@sum,(yuefen:c*x+e*s);,,@for,(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i));,,s(4)+x(4)-d(4)=0;,,s(1)=0,;,,@for,(yuefen:x

32、 6000,,43,,,76,82,76,76,-,-,-,80,-,-,74,72,-,74,72,70,生產(chǎn)月,,10000,10000,10000,10000,產(chǎn)量,6000,4,12000,7000,6000,銷量,4,3,2,1,3,2,1,,需求月,費用,c,ij,,44,,,,45,,,model,:,,title,,生產(chǎn)計劃程序,3;,,sets,:,,yuefen/1..4/:a,d,xx;,,!,定義上三角矩陣,;,,link(yuefen,yuefen)|,,endsets,,data,:,,c=70 72 74 76,,71 73 75,,80 82,,

33、76;,,d=6000 7000 12000 6000;,,a=10000 10000 10000 10000;,,enddata,,min,=,@sum,(link:c*x);,,@for,(yuefen(i):,@sum,(yuefen(j)|j#ge#i:x(i,j))d(j););,,!,得到每個月的生產(chǎn)量,;,,@for,(yuefen(i):xx=,@sum,(yuefen(j):x(i,j)));,,End,,46,,,Model Title: :,生產(chǎn)計劃程序,1

34、,,Variable Value Reduced Cost,,A 10000.00 0.000000,,C( 1) 70.00000 0.000000,,C( 2) 71.00000 0.000000,,C( 3) 80.00000 0.000000,,C( 4) 76.00000 0.000000,,X( 1) 10000.00 0.000000

35、,,X( 2) 10000.00 0.000000,,X( 3) 5000.000 0.000000,,X( 4) 6000.000 0.000000,,E( 1) 2.000000 0.000000,,E( 2) 2.000000 0.000000,,E( 3) 2.000000 0.000000,,E( 4) 2.000000 0.00000

36、0,,D( 1) 6000.000 0.000000,,D( 2) 7000.000 0.000000,,D( 3) 12000.00 0.000000,,D( 4) 6000.000 0.000000,,,,47,,,課堂練習(xí),1:,轉(zhuǎn)運問題,設(shè)有兩個工廠,A,、,B,，產(chǎn)量都是,10,萬個，工廠有三個倉庫,x,，,y,，,z,，產(chǎn)品都先送到倉庫?，F(xiàn)有四個顧客分別為甲，乙，丙，丁，需求量分別為,3,，,5,，,4,，,5,萬個。工廠到倉庫、倉庫到顧客

37、的運費單價（元,/,個）見下表所示。試求總運費最少的運輸方案以及總運費。,,A,B,甲,乙,丙,丁,x,4,3,5,7,10,20,y,2,1,9,6,7,15,z,5,2,20,6,7,4,,48,,,連續(xù)投資,10,萬元,A,：從第,1,年 到第,4,年每年初要投資，次年末回收本利,1.15,B,：,第3年初投資，到第5年末回收1.25,，最大投資,4,萬元,C,：,第2年初投資，到第5年末回收1.40,，最大投資,3,萬元,D,：,每年初投資，每年末回收1.11,。,求：,5,年末總資本最大。,課堂練習(xí),2:,連續(xù)投資,,49,,,靈敏度分析與影子價格,,50,,,,例,4,生產(chǎn)計劃問題

38、,某工廠計劃安排生產(chǎn),Ⅰ,，,Ⅱ,兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤，生產(chǎn)單位產(chǎn)品所需設(shè)備臺時及,A,B,兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺時的定額如表所示，問：,,１）怎么安排生產(chǎn)使得工廠獲利最大？,,２）產(chǎn)品,Ⅰ,的單位利潤降低到,1.8,萬元，要不要改變生產(chǎn)計劃，如果降低到,1,萬元呢？,,３）產(chǎn)品,Ⅱ,的單位利潤增大到,5,萬元，要不要改變生產(chǎn)計劃？,,４）如果產(chǎn)品,Ⅰ,，,Ⅱ,的單位利潤同時降低了,1,萬元，要不要改變生產(chǎn)計劃？,,產(chǎn)品,Ⅰ,產(chǎn)品,Ⅱ,最大資源量,設(shè)備,1,2,8,臺時,原材料,A,4,0,16kg,原材料,B,0,4,12kg,單位產(chǎn)品利潤,2,3,,,51,,,,

39、,52,,,程序編寫,,,model,:,,title,,生產(chǎn)計劃問題,;,,[maxf],max,=2*x1+3*x2;,,[A]x1+2*x2<8;,,[B]4*x1<16;,,[TIME]4*x2<12;,,END,,,53,,,運行結(jié)果,,,,Model Title:,生產(chǎn)計劃問題,,,Variable Value Reduced Cost,,X1 4.000000 0.000000,,X2 2.000000 0.000000,,Row Slack or Surplus

40、 Dual Price,,MAXF 14.00000 1.000000,,A 0.000000 1.500000,,B 0.000000 0.1250000,,TIME 4.000000 0.000000,,對問題,1,，安排是生產(chǎn)產(chǎn)品,Ⅰ4,單位，產(chǎn)品,Ⅱ2,單位，最大盈,,利為,14,萬元,。,,,54,,,－線性模型－敏感性理論,1,目標(biāo)函數(shù)的系數(shù)變化的敏感性分析,如果目標(biāo)函數(shù)的系數(shù)發(fā)生變化，將會影響目標(biāo)函數(shù),f,斜率的變化，但是只要,f,的斜

41、率小于等于,-1/2,（也就是直線,l,夾在,l,1,與,l,2,之間時），最優(yōu)解都在,(4,2),上取到，最優(yōu)解不變，從而生產(chǎn)計劃不會變,.,,,55,,,－線性模型－,敏感性分析,1,要使用敏感性分析,,必須要在這里選擇,Prices & Ranges,,然后,保存,退出,路徑：,,LINGO︱Options︱General Solver,,(,通用求解程序,),選項卡,,56,,,要調(diào)出敏感性分析的結(jié)果，必須,先求解,后再,在程序窗口下,點擊,,LINGO,｜,Range,，,,,57,,,Ranges in which the basis is unchanged:,,Objectiv

42、e Coefficient Ranges,,,Current Allowable Allowable,,Variable Coefficient Increase Decrease,,X1 2.000000 INFINITY 0.5000000,,X2 3.000000 1.000000 3.000000,,Righthand Side Ranges,,Row Current Allowable

43、 Allowable,,RHS Increase Decrease,,A 8.000000 2.000000 4.000000,,B 16.00000 16.00000 8.000000,,TIME 12.00000 INFINITY 4.000000,,當(dāng)前變量系數(shù),允許增加量,允許減少量,對問題,2,，產(chǎn)品,Ⅰ,的單位利潤降低到,1.8,萬元，在（,1.5,，∞）之間，所以不改變生產(chǎn)計劃。如果降低到,1,萬元

44、，不在（,1.5,，∞）內(nèi)，要改變生產(chǎn)計劃。在程序中將目標(biāo)函數(shù)的系數(shù)“,2”,改為“,1”,，可得新的計劃為,安排是生產(chǎn)產(chǎn)品,Ⅰ2,單位，產(chǎn)品,Ⅱ3,單位，最大盈利為,11,萬元,.,,對問題,3,，要改變生產(chǎn)計劃，更改程序得新計劃為生產(chǎn)產(chǎn)品,Ⅰ2,單位，產(chǎn)品,Ⅱ3,單位，最大盈利為,19,萬元,.,,對問題,4,，因為兩個系數(shù)同時改變了，所以只有更改程序的數(shù)據(jù)，重新運行得：不改變生產(chǎn)計劃，但是最大利潤降低到,8,萬元,.,,,,58,,,,,59,,,把,y,1,,,y,2,,,y,3,作為三種原料的定價，,定價的目標(biāo)是在比生產(chǎn)產(chǎn)品獲得更多利潤的前提下的最小利潤,.,在最優(yōu)情況下，,y,的值

45、就是資源的,影子價格，,影子價格有意義是有范圍的,。,影子價格經(jīng)濟含義是：在資源得到最優(yōu)配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量．,,,60,,,Ranges in which the basis is unchanged:,,Objective Coefficient Ranges,,,Current Allowable Allowable,,Variable Coefficient Increase Decrease,,X1 2.000000 INFINITY

46、 0.5000000,,X2 3.000000 1.000000 3.000000,,,Righthand Side Ranges,,Row Current Allowable Allowable,,RHS Increase Decrease,,A 8.000000 2.000000 4.000000,,B 16.00000 16.00000 8.000000,,

47、TIME 12.00000 INFINITY 4.000000,,運行結(jié)果,,,,Model Title:,生產(chǎn)計劃問題,,,Variable Value Reduced Cost,,X1 4.000000 0.000000,,X2 2.000000 0.000000,,Row Slack or Surplus,Dual Price,,MAXF 14.00000,1.000000,,A 0.000000,1.

48、500000,,B 0.000000,0.1250000,,TIME 4.000000,0.000000,,,,61,,,1,桶牛奶,3,公斤,A,1,,12,小時,8,小時,4,公斤,A,2,,或,獲利,24,元,/,公斤,獲利,16,元,/,公斤,50,桶牛奶,時間,480,小時,至多加工,100,公斤,A,1,,制訂生產(chǎn)計劃，使每天獲利最大,,35,元可買到,1,桶牛奶，買嗎？若買，每天最多買多少,?,可聘用臨時工人，付出的工資最多是每小時幾元,?,,A,1,的獲利增加到,30,元,/,公斤，應(yīng)否改變生產(chǎn)計劃？,每天：,例,5,加工奶制品的生產(chǎn)計劃,,62,,

49、,x,1,桶牛奶生產(chǎn),A,1,,x,2,桶牛奶生產(chǎn),A,2,,獲利,24×3,x,1,,獲利,16×4,x,2,,原料供應(yīng),,勞動時間,,加工能力,,決策變量,,目標(biāo)函數(shù),,每天獲利,約束條件,非負(fù)約束,,線性規(guī)劃模型,(LP),,,63,,,Max=72*x1+64*x2;,,x1+x2<50,;,,12*x1+8*x2<480;,,3*x1<100;,,OBJECTIVE FUNCTION VALUE,,,1) 3360.000,,,VARIABLE VALUE,REDUCED COST,,,X1 20.000000,0.000000

50、,,,X2 30.000000,0.000000,,ROW SLACK OR SURPLUS DUAL PRICES,,2) 0.000000 48.000000,,3) 0.000000 2.000000,,4) 40.000000 0.000000,,NO. ITERATIONS= 2,20,桶牛奶生產(chǎn),A,1,, 30,桶生產(chǎn),A,2,，利潤,3360,元。,,,64,,,,OBJECT

51、IVE FUNCTION VALUE,,1) 3360.000,,VARIABLE VALUE REDUCED COST,,X1 20.000000 0.000000,,X2 30.000000 0.000000,,ROW SLACK OR SURPLUS,DUAL PRICES,,,2),0.000000,48.000000,,,3),0.000000,2.000000,,,4),40.000000,0.000000,,35,元可買到,1,桶牛奶，

52、要買嗎？,35 <48,,應(yīng)該買！,聘用臨時工人付出的工資最多每小時幾元？,2,元！,,,65,,,RANGES IN WHICH THE BASIS IS UNCHANGED:,,OBJ COEFFICIENT RANGES,,VARIABLE CURRENT ALLOWABLE ALLOWABLE,,COEF INCREASE DECREASE,,,X1 72.000000 24.000000 8.000000,,X2 64.000000 8.000000

53、 16.000000,,RIGHTHAND SIDE RANGES,,ROW CURRENT ALLOWABLE ALLOWABLE,,RHS INCREASE DECREASE,,,2 50.000000 10.000000 6.666667,,3 480.000000 53.333332 80.000000,,4 100.000000 INFINITY

54、 40.000000,,A,1,獲利增加到,30,元,/,千克，應(yīng)否改變生產(chǎn)計劃？,不變！,,35,元可買到,1,桶牛奶，每天最多買多少？,最多買,10,桶！,,,66,,,整數(shù)規(guī)劃,,67,,,問題： 如何下料最節(jié)省,?,原料鋼管,:,每根,19,米,4,米,50,根,6,米,20,根,8,米,15,根,客戶需求,,例,6,下料問題,,68,,,按照客戶需要在一根原料鋼管上安排切割的一種組合。,,余料,1,米,4,米,1,根,6,米,1,根,8,米,1,根,余料,3,米,4,米,1,根,6,米,1,根,6,米,1,根,合理切割模式,的余料應(yīng)小于客戶需要鋼管的最小尺寸,余料,3,米,8

55、,米,1,根,8,米,1,根,,69,,,model,:,,title,,搜索合理的下料方式,;,,sets,:,,ren:;,!,用一根原料可下各需求長度的最多根數(shù)定義元素個數(shù)，最多為,4,，這里要定義,5(0—4,有,5,個數(shù),);,,long(ren,ren,ren):;,!,有三種需求長度，定義三維數(shù)組,;,,endsets,,data,:,,ren=1..5;,,!,為了美觀輸出一些題頭,;,,@text,('d:renxinglong.txt')=,@write,(1*' ',',下料方式,',7*' ',',余料長度,',,@newline,(1));,,@text,('d:re

56、nxinglong.txt')=,@write,(12*'-',4*' ',8*'-',,@newline,(1));,,!,搜索所有滿足過濾條件的,i,j,k;,,@text,('d:renxinglong.txt')=,@writefor,(long(i,j,k)|,,(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0,,#and#(19-8*(i-1)-6*(j-1)-4*(k-1))#lt#a,,,!,一種下料方式下料長度和不超過總長度,,,合理模式的余料小于最短需求,;,,,!,輸出下料方式到文本文件,renxinglong.txt,，我們需要的數(shù)是,0--4;,,,

57、:i-1,4*' ',j-1,4*' ',k-1,8*' ',19-8*(i-1)-6*(j-1)-4*(k-1),,@newline,(2));,,!,輸出計算段計數(shù)過的下料方式總數(shù),;,,@text,('d:renxinglong.txt')=,@write,(',下料方式總數(shù)為：,',2*' ',n,',種,');,,Enddata,,,70,,,calc,:,,a=,@smin,(8,6,4);,,b=,@floor,(19/a)+1;,,n=0;,,@for,(long(i,j,k)|,,(19-8*(i-1)-6*(j-1)-4*(k-1))#ge#0,,#and#(19-8*(i

58、-1)-6*(j-1)-4*(k-1))#lt#a,,:n=n+1);,!,下料方式計數(shù),;,,endcalc,,end,,,71,,,為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。?模式,,4,米鋼管根數(shù),,6,米鋼管根數(shù),,8,米鋼管根數(shù),,余料,(,米,),,1,,4,,0,,0,,3,,2,,3,,1,,0,,1,,3,,2,,0,,1,,3,,4,,1,,2,,0,,3,,5,,1,,1,,1,,1,,6,,0,,3,,0,,1,,7,,0,,0,,2,,3,,x,i,~,按第,i,種模式切割的原料鋼管根數(shù),(,i,=,1,2,…7,),決策變量,,,72

59、,,,2.,所用原料鋼管總根數(shù)最少,1.,原料鋼管剩余總余量最小,目標(biāo)函數(shù)：（,兩種標(biāo)準(zhǔn)）,,,73,,,模,,式,,4,米,,根數(shù),,6,米,,根數(shù),,8,米,,根數(shù),,余,,料,,1,,4,,0,,0,,3,,2,,3,,1,,0,,1,,3,,2,,0,,1,,3,,4,,1,,2,,0,,3,,5,,1,,1,,1,,1,,6,,0,,3,,0,,1,,7,,0,,0,,2,,3,,需,,求,,50,,20,,15,,,約束,整數(shù)約束：,x,i,為整數(shù),,,74,,,－程序編寫－,model,:,,Title,,鋼管下料,;,,,Min,=3*x1 + x2 + 3*x3 + 3*x4

60、 + x5 + x6 + 3*x7;,,4*x1 + 3*x2 + 2*x3 + x4 + x5>50;,,x2 + 2*x4 + x5 + 3*x6> 20;,,x3 + x5 + 2*x7>15;,,@gin,(x1);,@gin,(x2);,@gin,(x3);,@gin,(x4);,,@gin,(x5);,@gin,(x6);,@gin,(x7);,,end,程序編寫,,75,,,按模式,2,切割,12,根,,,按模式,5,切割,15,根，余料,27,米,,最優(yōu)解：,x,2,=12,,x,5,=15,,其余為,0,；,,最優(yōu)值：,27,最優(yōu)解：,x,

61、2,=15,,x,5,=5,,x,7,=5,,其余為,0,；,,最優(yōu)值：,25,。,按模式,2,切割,15,根，按模式,5,切割,5,根，按模式,7,切割,5,根，共,25,根，余料,35,米,當(dāng)余料沒有用處時，,通常以總根數(shù)最少為目標(biāo),,,76,,,課堂練習(xí),3,某服務(wù)部門一周中每天需要不同數(shù)目的雇員，周一到周四每天至少需要,50,人，周五至少需要,80,人，周六和周日至少需要,90,人，現(xiàn)規(guī)定應(yīng)聘者需連續(xù)工作,5,天，試確定聘用方案。,,77,,,0-1,規(guī)劃,,78,,,例,7,選址問題,,79,,,,80,,,,例,8,面試順序問題,,有,4,名同學(xué)到一家公司參加三個階段的面試，公司要

62、求每個同學(xué)都必須首先找公司秘書初試，然后到主管部門處復(fù)試，最后到經(jīng)理處參加免試，并且不允許插隊，由于,4,名同學(xué)的專業(yè)背景不同，所以每人在三個階段的面試時間也不同，如表所示，這,4,名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司，假定現(xiàn)在時間是早上,8,：,00,，請問他們最早何時能離開公司？,,,秘書初試,主管復(fù)試,經(jīng)理面試,同學(xué)甲,13,15,20,同學(xué)乙,10,20,18,同學(xué)丙,20,16,10,同學(xué)丁,8,10,15,,81,,,,82,,,優(yōu)化目標(biāo)為：,約束條件：,個人時間先后次序約束：,同階段不同同學(xué)時間不相容：（同階段靠前同學(xué)的完成時間小于靠后同學(xué)的開始時間）,,83,,,可將目標(biāo)改

63、為如下線性優(yōu)化目標(biāo)：,,84,,,程序編寫,,model,:,,title,:,面試問題,;,,sets,:,,student/1..4/:;,,office/1..3/:;,,link1(student,office):x,t;,,link2(student,student)|,,endsets,,data,:,,t=13 15 20,,10 20 18,,20 16 10,,8 10 15 ;,,Enddata,,min,=time;,,!time,大于每名同學(xué)最后面試完畢時間,;,,@for,(student(i):time>x(i,3)+t(i,3););,,85,,,!,面試先后次序

64、約束,;,,@for,(student(i):,@for,(office(j)|j#lt#3:x(i,j)+t(i,j)

65、:,,x(k,j)+t(k,j)-x(i,j)<1000*(1-y(i,k)))));,,!,定義,0-1,變量,,,最后通過,0-1,變量可以查看面試順序,;,,@for,(link2:,@bin,(y));,,End,,86,,,運行結(jié)果,,Model Title: :,面試問題,,,Variable Value Reduced Cost,,TIME 84.00000 0.000000,,,……………………,（省略）,,,Y( 1, 2) 0.000000 -1000.000,,Y( 1

66、, 3) 0.000000 0.000000,,Y( 1, 4) 1.000000 1000.000,,Y( 2, 3) 0.000000 -1000.000,,Y( 2, 4) 1.000000 0.000000,,Y( 3, 4) 1.000000 0.000000,,所以面試完成至少需要,84min,，面試順序為,4-1-2-3,（丁,-,甲,-,乙,-,丙）．,,87,,,課堂練習(xí),4,某班準(zhǔn)備從,5,名游泳員中選擇４人組成接力隊，藏家學(xué)校的,4×100m,混合泳接力比賽，,5,名隊員,4,種泳姿的百米平均成績?nèi)绫恚瑔柸绾芜x拔隊員。,隊員,甲,乙,丙,丁,戊,蝶泳,1’06’’8,57’’2,1’18’’,1’10’’,1’07’’4,仰泳,1’15’’6,1’06’’,1’14’’2,1’14’’2,1’11’’,蛙泳,1’27’’,1’06’’4,1’09’’6,1’09’’6,1’23’’8,自由