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

《數(shù)學(xué)規(guī)劃建?！酚蓵?huì)員分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)規(guī)劃建模（154頁珍藏版）》請(qǐng)?jiān)谘b配圖網(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,）,三個(gè)要素：決策變量,decision bariable,，目標(biāo)函數(shù),objective function,，約束條件,constraints,。,,2,,,（,2,）所確定的,x,的范圍稱為,可行域,feasible region,，滿足（,2,）的解,x,稱為,可行解

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

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.,動(dòng)態(tài)規(guī)劃。,,3.,多層規(guī)劃。,,4.,網(wǎng)絡(luò)優(yōu)化。,,5.……,等等。,,6,,,優(yōu)化問題求解常用的軟件,,LINGO,軟件和,MATLAB,軟件。,,對(duì)于,LINGO,軟件，線性優(yōu)化求解程序通常使用,單純形法,simplex method,，單純形法雖然在實(shí)際應(yīng)用中是最好最有效的方法，但對(duì)某些問題具有指數(shù)階

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

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

7、條件：,1,）能力限制：,2,）產(chǎn)品數(shù)量的平衡方程：,4,）變量非負(fù),3,）初始庫存：,－引例－ 模型建立,,9,,,記四個(gè)季度組成的集合,QUARTERS={1,，,2,，,3,，,4},，它們就是上面數(shù)組的,下標(biāo)集合,，而數(shù)組,DEM,RP,OP, INV,對(duì)集合,QUARTERS,中的每個(gè)元素,1,，,2,，,3,，,4,分別對(duì)應(yīng)于一個(gè)值。,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ù)段：對(duì)集合的屬性輸入必要的常數(shù)數(shù)據(jù)；,,,DATA:,,DEM=40,60,75,25;,,ENDDATA,,,END,或,1..4,或用空格或回車隔開，“屬性＝常數(shù)列表”,對(duì)“：”前的每個(gè)元素求和或循環(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,自動(dòng)生成行號(hào),－結(jié)果報(bào)告－,,15,,,例,2,運(yùn)輸問題,,16,,,解：設(shè),A,1,,A,2,調(diào)運(yùn)到三個(gè)糧站的大米分別為,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,糧庫,糧站,距離及運(yùn)量,12,12,24,30,8,24,,17,,,結(jié)合存量限制和需量限制得數(shù)學(xué)模型,：,,18,,,程序編寫 推薦,,,MODEL,:,,TITLE,,調(diào)運(yùn)大米的運(yùn)輸問題程序４,;,,!,定義集合段,;,,SETS,:,,LIANGKU/1..2/:A;,!,定義糧庫的集合,;,,LIANGZHAN/1..3/:B;,!,定義糧站的集合,;,,YULIANG(LIANGKU,LIANGZHAN):X,C;,!,定義運(yùn)量和距離,;,,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.,直接點(diǎn)擊運(yùn)行，如果出錯(cuò)會(huì)彈出錯(cuò)誤提示

14、，根據(jù)提示做相應(yīng)的修改；,,,2.,可以用“！”把約束變成說明語句，而把這條語句屏蔽掉，縮小尋找出錯(cuò)的范圍；,,,3.,可以邊寫程序邊運(yùn)行，保證每行書寫都是正確的程序；,,21,,,料場的建立與運(yùn)輸,建筑工地的位置,(,用平面坐標(biāo),a,,,b,表示，距離單位：公里,),及水泥日用量,d,(,噸,),下表給出。有兩個(gè)臨時(shí)料場位于,P (5,1), Q (2, 7),,日儲(chǔ)量各有,20,噸。,(1),從,A, B,兩料場分別向各工地運(yùn)送多少噸水泥，使總的噸公里數(shù)最小。,(2),兩個(gè)新的料場應(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,模型,－引例－ 模型建立,料場向工地的運(yùn)送量為：,工地：位置,水泥日用量：,料場：位置,日儲(chǔ)量：,,23,,,利用集合的概念，可以定義需求點(diǎn),DEMAND,和供應(yīng)點(diǎn),SUPPLY,兩個(gè)集合，分別有,6,個(gè)和,2,個(gè)元素,(,下標(biāo),),。但決策變量,(,運(yùn)送量,),c,ij,與集合,DEMAND,和集合,SUPPLY,都有關(guān)系的。該如何定義這樣的屬性？,集合的屬性相當(dāng)于以集合的元素為下標(biāo)的數(shù)組。這里的,c,ij,相當(dāng)于二維數(shù)組。它的兩

16、個(gè)下標(biāo)分別來自集合,DEMAND,和,SUPPLY,，因此可以定義一個(gè)由二元對(duì)組成的新的集合，然后將,c,ij,定義成這個(gè)新集合的屬性，這個(gè)集合稱為,派生集合,。,－派生集合－,,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(,需求點(diǎn)的位置,);,,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,,,－程序編寫－,……,,!,初始段：對(duì)集合屬性定義初值（迭代算法的迭代初值）,;,,init:,,!initial locations for the supply,（初始點(diǎn)）,;,,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,對(duì)數(shù)值順序按列賦值，即：,x=5,2;y=1,7;,標(biāo)號(hào)自動(dòng)在后加下標(biāo) *,_1 , _2…,比,@free(x);@free(y);,要好，可減少計(jì)算工作量,,26,,,－求解觀察－,激活全局最優(yōu)解：,,LINGO︱Options→Global Solver︱Use Global Solver,,27,,,－結(jié)果報(bào)告－,工地與料場運(yùn)輸示意圖,: “,*,”,表示料場，“,+,”,表示工地,,,28,,,－認(rèn)識(shí)“初始段”－,……,,data:,,!(,需求點(diǎn)的位置,);,,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:,,!,（初始點(diǎn)）,;,,x,y=5,1,2,7;,,Endinit,,……,……,,data:,,!(,需求點(diǎn)的位置,);,,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:,,!,（初始點(diǎn)）,;,,Endinit,,……,求解,NLP,問題,求解,L

21、P,問題,只對(duì)非線性模型起作用,,29,,,－知識(shí)重整－,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,也就是一個(gè),6*2,的矩陣（或者說是含有,12,個(gè)元素的,二維數(shù)組,）。,,30,,,－模型構(gòu)成－,一般來說，,LINGO,中建立的優(yōu)化模型可以由五個(gè)部分組成，或稱為五“段”（,SECTION,）：,（,1,）,集合段,（,SETS,）：以“,SETS:”,開始， “,ENDSETS”,結(jié)束，定義必要的集合變量（,SET,）及其元素（,MEMBER,，含義類似于數(shù)組的下標(biāo)）和屬性（,ATTRIBUTE,，含義類似于數(shù)組）

23、。,（,2,）,目標(biāo)與約束段,：目標(biāo)函數(shù)、約束條件等，沒有段的開始和結(jié)束標(biāo)記，因此實(shí)際上就是除其它四個(gè)段,(,都有明確的段標(biāo)記,),外的,LINGO,模型。,（,3,）,數(shù)據(jù)段,(DATA),：以 “,DATA:”,開始,, “ENDDATA”,結(jié)束，,,對(duì)集合的屬性,(,數(shù)組,),輸入必要的常數(shù)數(shù)據(jù)。,,格式為：“,attribute(,屬性,) = value_list(,常數(shù)列表,);,”,,31,,,－模型構(gòu)成－,(5),計(jì)算段,:,在數(shù)據(jù)段輸入完成之后在正式求解模型之前對(duì),,原始數(shù)據(jù)進(jìn)行處理，語句是,順序,執(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é)束，,,對(duì)集合的屬性,(,數(shù)組,),定義初值,(,因?yàn)榍蠼馑惴ㄒ话闶堑惴ǎ?,所以用戶如果能給出一個(gè)比較好的迭代初值，對(duì)提高算法的計(jì),,算效果是有益的,),。,,格式為：“,attribute,（屬性）,= value_list,（常數(shù)列表）；,”,,32,,,－試一試－,使用集合

25、改寫下面程序：,,min=-5*x1-2*x2,；,,2*x1+x2+x3=8,；,,x1+x4=3,；,,x2+x5=4;,?,請(qǐng)動(dòng)手試一下,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,是一個(gè)凸集,convex set,（

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

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

29、,存,,,庫存量無限制,.,第,j+1,個(gè)月的庫存量,第,j+1,個(gè)月的庫存費(fèi),共,3,個(gè)月的庫存費(fèi),到本月總生產(chǎn)量大于等于銷售量,4,個(gè)月總生產(chǎn)量等于總銷售量,4,個(gè)月總生產(chǎn)成本,,39,,,,model,:,,title,,生產(chǎn)計(jì)劃程序,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,,需求月,費(fèi)用,c,ij,,44,,,,45,,,model,:,,title,,生產(chǎn)計(jì)劃程序,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););,,!,得到每個(gè)月的生產(chǎn)量,;,,@for,(yuefen(i):xx=,@sum,(yuefen(j):x(i,j)));,,End,,46,,,Model Title: :,生產(chǎn)計(jì)劃程序,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)運(yùn)問題,設(shè)有兩個(gè)工廠,A,、,B,，產(chǎn)量都是,10,萬個(gè)，工廠有三個(gè)倉庫,x,，,y,，,z,，產(chǎn)品都先送到倉庫。現(xiàn)有四個(gè)顧客分別為甲，乙，丙，丁，需求量分別為,3,，,5,，,4,，,5,萬個(gè)。工廠到倉庫、倉庫到顧客

37、的運(yùn)費(fèi)單價(jià)（元,/,個(gè)）見下表所示。試求總運(yùn)費(fèi)最少的運(yùn)輸方案以及總運(yùn)費(fèi)。,,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,,,靈敏度分析與影子價(jià)格,,50,,,,例,4,生產(chǎn)計(jì)劃問題

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

39、,52,,,程序編寫,,,model,:,,title,,生產(chǎn)計(jì)劃問題,;,,[maxf],max,=2*x1+3*x2;,,[A]x1+2*x2<8;,,[B]4*x1<16;,,[TIME]4*x2<12;,,END,,,53,,,運(yùn)行結(jié)果,,,,Model Title:,生產(chǎn)計(jì)劃問題,,,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,,對(duì)問題,1,，安排是生產(chǎn)產(chǎn)品,Ⅰ4,單位，產(chǎn)品,Ⅱ2,單位，最大盈,,利為,14,萬元,。,,,54,,,－線性模型－敏感性理論,1,目標(biāo)函數(shù)的系數(shù)變化的敏感性分析,如果目標(biāo)函數(shù)的系數(shù)發(fā)生變化，將會(huì)影響目標(biāo)函數(shù),f,斜率的變化，但是只要,f,的斜

41、率小于等于,-1/2,（也就是直線,l,夾在,l,1,與,l,2,之間時(shí)），最優(yōu)解都在,(4,2),上取到，最優(yōu)解不變，從而生產(chǎn)計(jì)劃不會(huì)變,.,,,55,,,－線性模型－,敏感性分析,1,要使用敏感性分析,,必須要在這里選擇,Prices & Ranges,,然后,保存,退出,路徑：,,LINGO︱Options︱General Solver,,(,通用求解程序,),選項(xiàng)卡,,56,,,要調(diào)出敏感性分析的結(jié)果，必須,先求解,后再,在程序窗口下,點(diǎn)擊,,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ù),允許增加量,允許減少量,對(duì)問題,2,，產(chǎn)品,Ⅰ,的單位利潤降低到,1.8,萬元，在（,1.5,，∞）之間，所以不改變生產(chǎn)計(jì)劃。如果降低到,1,萬元

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

45、就是資源的,影子價(jià)格，,影子價(jià)格有意義是有范圍的,。,影子價(jià)格經(jīng)濟(jì)含義是：在資源得到最優(yōu)配置，使總效益最大時(shí)，該資源投入量每增加一個(gè)單位所帶來總收益的增加量．,,,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,,運(yùn)行結(jié)果,,,,Model Title:,生產(chǎn)計(jì)劃問題,,,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,小時(shí),8,小時(shí),4,公斤,A,2,,或,獲利,24,元,/,公斤,獲利,16,元,/,公斤,50,桶牛奶,時(shí)間,480,小時(shí),至多加工,100,公斤,A,1,,制訂生產(chǎn)計(jì)劃，使每天獲利最大,,35,元可買到,1,桶牛奶，買嗎？若買，每天最多買多少,?,可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元,?,,A,1,的獲利增加到,30,元,/,公斤，應(yīng)否改變生產(chǎn)計(jì)劃？,每天：,例,5,加工奶制品的生產(chǎn)計(jì)劃,,62,,

49、,x,1,桶牛奶生產(chǎn),A,1,,x,2,桶牛奶生產(chǎn),A,2,,獲利,24×3,x,1,,獲利,16×4,x,2,,原料供應(yīng),,勞動(dòng)時(shí)間,,加工能力,,決策變量,,目標(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)該買！,聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？,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)計(jì)劃？,不變！,,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ù)定義元素個(gè)數(shù)，最多為,4,，這里要定義,5(0—4,有,5,個(gè)數(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));,,!,輸出計(jì)算段計(jì)數(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);,!,下料方式計(jì)數(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í)，,通常以總根數(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é)到一家公司參加三個(gè)階段的面試，公司要

62、求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到主管部門處復(fù)試，最后到經(jīng)理處參加免試，并且不允許插隊(duì)，由于,4,名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段的面試時(shí)間也不同，如表所示，這,4,名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司，假定現(xiàn)在時(shí)間是早上,8,：,00,，請(qǐng)問他們最早何時(shí)能離開公司？,,,秘書初試,主管復(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)為：,約束條件：,個(gè)人時(shí)間先后次序約束：,同階段不同同學(xué)時(shí)間不相容：（同階段靠前同學(xué)的完成時(shí)間小于靠后同學(xué)的開始時(shí)間）,,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é)最后面試完畢時(shí)間,;,,@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,,,運(yùn)行結(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,，面試順序?yàn)?4-1-2-3,（丁,-,甲,-,乙,-,丙）．,,87,,,課堂練習(xí),4,某班準(zhǔn)備從,5,名游泳員中選擇４人組成接力隊(duì)，藏家學(xué)校的,4×100m,混合泳接力比賽，,5,名隊(duì)員,4,種泳姿的百米平均成績?nèi)绫?，問如何選拔隊(duì)員。,隊(duì)員,甲,乙,丙,丁,戊,蝶泳,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,自由