數(shù)學(xué)建模講座優(yōu)化建模與lingo優(yōu)化軟件

1、數(shù)學(xué)建模講座優(yōu)化建模與LINGO優(yōu)化軟件,,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x2≤2 -x1+2x2≤2 x1≥0, x2≥0,Lingo 基 礎(chǔ),Lingo 程序MIN=-2*X1-6*X2+X1*X1-2*X1*X2+2*X1*X1;X1+X2<=2;-X1

2、+2*X2<=2;,Lingo 基 礎(chǔ),計(jì)算結(jié)果Objective value: -9.777778X1 = 0.6666667 X2 = 1.333333,Lingo 基 礎(chǔ),例2,x1+x2=0 s.t. 1.5+x1

3、x2 - x1 - x2 0 -x1x2 –10 0,Lingo 基 礎(chǔ),Lingo程序min=@exp(x1)*(4*x1*x1+2*x2*x2+4*x1*x2+2*x2+1);x1+x2=0;1.5+x1*x2-x1-x2<=0;-x1*x2-10<=0;@free(x1);@free(x2);,Lingo 基 礎(chǔ),計(jì)算結(jié)果Obj

4、ective value: 5.276848X1 = 1.224745 X2 = -1.224745這是局部最優(yōu)值,Lingo 基 礎(chǔ),Lingo菜單中Options，選Global Solver ，在Use Global Solver 中打鉤，再次計(jì)算。,Objective value:

5、 1.156627X1=-3.162278 X2=3.162278,Lingo 基 礎(chǔ),例三,Lingo 基 礎(chǔ),例三中,x,y ,e是一維數(shù)組，長(zhǎng)度為2，a,b,d 也是一維數(shù)組，長(zhǎng)度為6，c是二維數(shù)組（6×2矩陣）Lingo中如何定義它們？,Lingo 基 礎(chǔ),Lingo 程序 example3_2sets:demand

6、/1..6/:a,b,d;supply/1..2/:x,y,e;link(demand,supply):c;endsetsdata: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;enddata,Lingo 基 礎(chǔ),init:x,y=5,1,2,7;endinit min=@sum(link(i,

7、j):c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2) );@for(demand(i): @sum(supply(j):c(i,j)) =d(i););@for(supply(i): @sum(demand(j):c(j,i)) <=e(i); );@for(supply:@bnd(0.5,X,8.75); @bnd(0.75,Y,7.75); );END,Lingo 基 礎(chǔ),

8、計(jì)算結(jié)果為 Objective value:89.88349,模型的集部分,LINGO有兩種類型的集：原始集(primitive　set)和派生集(derived set)。一個(gè)原始集是由一些最基本的對(duì)象組成的。一個(gè)派生集是用一個(gè)或多個(gè)其它集來(lái)定義的，也就是說(shuō)，它的成員來(lái)自于其它已存在的集。,,定義一個(gè)原始集，用下面的語(yǔ)法：setname[/member_list/][:attribute_list];注意：用“[]”表示該部

9、分內(nèi)容可選。,,Member_list是集成員列表。如果集成員放在集定義中，那么對(duì)它們可采取顯式羅列和隱式羅列兩種方式。如果集成員不放在集定義中，那么可以在隨后的數(shù)據(jù)部分定義它們,模型的數(shù)據(jù)部分,數(shù)據(jù)部分以關(guān)鍵字“data:”開(kāi)始，以關(guān)鍵字“enddata”結(jié)束。在這里，可以指定集成員、集的屬性。,數(shù)據(jù)部分的未知數(shù)值,有時(shí)只想為一個(gè)集的部分成員的某個(gè)屬性指定值，而讓其余成員的該屬性保持未知，以便讓LINGO去求出它們的最優(yōu)值。在數(shù)據(jù)聲明

10、中輸入兩個(gè)相連的逗號(hào)表示該位置對(duì)應(yīng)的集成員的屬性值未知。兩個(gè)逗號(hào)間可以有空格,數(shù)據(jù)部分的未知數(shù)值,sets: years/1..5/: capacity;endsetsdata: capacity = ,34,20,,;enddata屬性capacity的第2個(gè)和第3個(gè)值分別為34和20，其余的未知,模型的初始部分,一個(gè)初始部分以“init:”開(kāi)始，以“endinit”結(jié)束。初始部分的初始聲明規(guī)則和數(shù)據(jù)部分的數(shù)據(jù)聲明規(guī)則

11、相同。,模型的初始部分,init:x,y=5,1,2,7;endinit,LINGO函數(shù),基本運(yùn)算符數(shù)學(xué)函數(shù)金融函數(shù)概率函數(shù)變量界定函數(shù)集操作函數(shù)集循環(huán)函數(shù)數(shù)據(jù)輸入輸出函數(shù)輔助函數(shù),算術(shù)運(yùn)算符,＾　乘方﹡　乘／　除﹢　加﹣　減,邏輯運(yùn)算符,#not#　#eq##ne##gt##ge#　#lt# #le#　 #and#　 #or#,關(guān)系運(yùn)算符,LINGO有三種關(guān)系運(yùn)算符：“=”、“=”。 LIN

12、GO并不支持嚴(yán)格小于和嚴(yán)格大于關(guān)系運(yùn)算符。然而，如果需要嚴(yán)格小于和嚴(yán)格大于關(guān)系，比如讓A嚴(yán)格小于B：A<B，那么可以把它變成如下的小于等于表達(dá)式：A+ε<=B，,數(shù)學(xué)函數(shù),@abs(x) @sin(x) @cos(x) @tan(x) @exp(x)@log(x) @lgm(x) 返回x的gamma函數(shù)的自然對(duì)數(shù)@sign(x) 如果x<0返回-1；否則，返回1@floor(x)

13、返回x的整數(shù)部分。@smax(x1,x2,…,xn) @smin(x1,x2,…,xn),變量界定函數(shù),@bin(x) 限制x為0或1@bnd(L,x,U) 限制L≤x≤U@free(x) 取消對(duì)變量x的默認(rèn)下界為0的限制，即x可以取任意實(shí)數(shù)@gin(x) 限制x為整數(shù),集操作函數(shù),@index([set_name,]primitive_set_element)該函數(shù)返回在集set

14、_name中原始集成員primitive_set_element的索引。,集操作函數(shù),@wrap(index,limit) 該函數(shù)為index模limit再加1 @size(set_name)該函數(shù)返回集set_name的成員個(gè)數(shù),集合循環(huán)函數(shù),四個(gè)集合循環(huán)函數(shù)：FOR、SUM 、 MAX、MIN@function( setname [ ( set_index_list)[ | condition]] : expression_

15、list);,,例:,@SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J));,,例:,@FOR(STUDENTS( I): @SUM( pair( j, k) | j #EQ#i #OR# k #EQ# i: match( j, k)) =1);,,@FILE和@TEXT：文本文件輸入輸出,data:a=@file(example3_3.ldt);b=@file(exam

16、ple3_3.ldt);d=@file(example3_3.ldt);e=@file(example3_3.ldt);enddatainit:x,y=@file(example3_3.ldt);endinit,1.25,8.75,0.5,5.75,3,7.25~1.25,0.75,4.75,5,6.5,7.75~3,5,4,7,6,11~20,20~5,1,2,7,Example3_3.ldt的格式,@FILE和@

17、TEXT：文本文件輸入輸出,比較,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;,@OLE ：與EXCEL連接,使用格式@OLE(“filename” [，range_name_list]) filename 為電子表 文件名 , range_name_list 為數(shù)據(jù)的單元范圍。,@

18、OLE 的使用例子Excel文件example3_4.xls 的內(nèi)容,注意 要將表格中的數(shù)據(jù)進(jìn)行命名 :選中數(shù)據(jù),選菜單“插入|名稱|定義” 在這里分別命名為 a,b,d,e,x,y,result,@OLE 的使用例子Lingo文件example3_4.lg4 的內(nèi)容,data:a,b,d,e=@OLE("d:\數(shù)學(xué)建模\EXAMPLE3_4.XLS");enddatainit:x,y=@Ole(&

19、quot;d:\數(shù)學(xué)建模\Example3_4.xls");endinit,@OLE 的使用例子如果在Lingo文件example3_4.lg4 加上以下內(nèi)容其他不變,data:@ole("d:\數(shù)學(xué)建模\EXAMPLE3_4.XLS","result")=c;@ole("d:\數(shù)學(xué)建模\EXAMPLE3_4.XLS","x")=x;

20、@ole("d:\數(shù)學(xué)建模\EXAMPLE3_4.XLS","y")=y;enddata,@OLE 的使用例子,則example3_4.xls 變?yōu)?注意其中x,y ,result 的變化,例 加工奶制品的生產(chǎn)計(jì)劃,50桶牛奶,時(shí)間480小時(shí),至多加工100公斤A1,制訂生產(chǎn)計(jì)劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少?,可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?

21、,A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？,每天：,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 24×3x1,獲利 16×4 x2,原料供應(yīng),勞動(dòng)時(shí)間,加工能力,決策變量,目標(biāo)函數(shù),每天獲利,約束條件,非負(fù)約束,線性規(guī)劃模型(LP),時(shí)間480小時(shí),至多加工100公斤A1,模型求解,max =72*x1+64*x2;x1+x2<50;12*x1+8*x2<480;3*x1<100

22、;,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW

23、 SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS=

24、 2,20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤(rùn)3360元。,模型求解,reduced cost值表示當(dāng)該非基變量增加一個(gè)單位時(shí)（其他非基變量保持不變）目標(biāo)函數(shù)減少的量(對(duì)max型問(wèn)題),OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1

25、 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000

26、 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,也可理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE

27、 REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 4

28、8.000000 3) 0.000000 2.000000 4) 40.000000 0.000000,原料無(wú)剩余,時(shí)間無(wú)剩余,加工能力剩余40,max 72x1+64x2stx1+x2<5012x1+8x2<4803x1<100,三種資源,“資源” 剩余為零的約束為緊

29、約束（有效約束）,結(jié)果解釋,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000

30、ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000,結(jié)果解釋,最優(yōu)解下“資

31、源”增加1單位時(shí)“效益”的增量,原料增1單位, 利潤(rùn)增48,時(shí)間加1單位, 利潤(rùn)增2,能力增減不影響利潤(rùn),影子價(jià)格,35元可買到1桶牛奶，要買嗎？,35 <48, 應(yīng)該買！,聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURREN

32、T ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.0

33、00000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000

34、 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最優(yōu)解不變時(shí)目標(biāo)系數(shù)允許變化范圍,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系數(shù)范圍(64,96)

35、,x2系數(shù)范圍(48,72),A1獲利增加到 30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃,x1系數(shù)由24?3= 72 增加為30?3= 90，在允許范圍內(nèi),不變！,(約束條件不變),結(jié)果解釋,結(jié)果解釋,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOW

36、ABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000

37、 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.66

38、6667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子價(jià)格有意義時(shí)約束右端的允許變化范圍,原料最多增加10,時(shí)間最多增加53,35元可買到1桶牛奶，每天最多買多少？,最多買10桶？,(目標(biāo)函數(shù)不變),注意: 充

39、分但可能不必要,LINGO模型例：選址問(wèn)題,某公司有6個(gè)建筑工地，位置坐標(biāo)為(ai, bi) (單位：公里),水泥日用量di (單位：噸）,假設(shè)：料場(chǎng)和工地之間有直線道路,用例中數(shù)據(jù)計(jì)算，最優(yōu)解為,總噸公里數(shù)為136.2,線性規(guī)劃模型,決策變量：ci j (料場(chǎng)j到工地i的運(yùn)量）~12維,選址問(wèn)題：NLP,2）改建兩個(gè)新料場(chǎng)，需要確定新料場(chǎng)位置(xj,yj)和運(yùn)量cij ，在其它條件不變下使總噸公里數(shù)最小。,決策變量：ci j，(xj

40、,yj)~16維,非線性規(guī)劃模型,LINGO模型的構(gòu)成：4個(gè)段,集合段（SETS ENDSETS）,數(shù)據(jù)段（DATA ENDDATA）,初始段（INIT ENDINIT）,目標(biāo)與約束段,局部最優(yōu)：89.8835(噸公里 ),,,LP：移到數(shù)據(jù)段,問(wèn)題1. 如何下料最節(jié)省 ?,例 鋼管下料,問(wèn)題2. 客戶增加需求：,節(jié)省的標(biāo)準(zhǔn)是什么？,由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(guò)3種。如何下料最節(jié)

41、?。?按照客戶需要在一根原料鋼管上安排切割的一種組合。,切割模式,合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸,鋼管下料,為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。?合理切割模式,2. 所用原料鋼管總根數(shù)最少,鋼管下料問(wèn)題1,兩種標(biāo)準(zhǔn),1. 原料鋼管剩余總余量最小,xi ~按第i 種模式切割的原料鋼管根數(shù)(i=1,2,…7),約束,滿足需求,決策變量,目標(biāo)1（總余量）,按模式2切割12根,按模式5切割1

42、5根，余料27米,最優(yōu)解：x2=12, x5=15, 其余為0；最優(yōu)值：27,整數(shù)約束： xi 為整數(shù),當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo),目標(biāo)2（總根數(shù)）,鋼管下料問(wèn)題1,約束條件不變,最優(yōu)解：x2=15, x5=5, x7=5, 其余為0；最優(yōu)值：25。,xi 為整數(shù),按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,雖余料增加8米，但減少了2根,與目標(biāo)

43、1的結(jié)果“共切割27根，余料27米” 相比,鋼管下料問(wèn)題2,對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式,增加一種需求：5米10根；切割模式不超過(guò)3種。,現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。,決策變量,xi ~按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3),r1i, r2i, r3i, r4i ~ 第i 種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量,滿

44、足需求,模式合理：每根余料不超過(guò)3米,整數(shù)非線性規(guī)劃模型,鋼管下料問(wèn)題2,目標(biāo)函數(shù)（總根數(shù)）,約束條件,整數(shù)約束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)為整數(shù),增加約束，縮小可行域，便于求解,原料鋼管總根數(shù)下界：,特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：31,模式排列順序可

45、任定,鋼管下料問(wèn)題2,需求：4米50根，5米10根，6米20根，8米15根,每根原料鋼管長(zhǎng)19米,LINGO求解整數(shù)非線性規(guī)劃模型,Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000

46、 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000

47、R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000

48、 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000

49、 R42 0.000000 0.000000 R43 2.000000 0.000000,模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。,露天礦里鏟位已

50、分成礦石和巖石: 平均鐵含量不低于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個(gè)鏟位至多安置一臺(tái)電鏟，電鏟平均裝車時(shí)間5分鐘,卡車在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)不應(yīng)發(fā)生卡車等待的情況。,露天礦生產(chǎn)的車輛安排(CUMCM-2003B),礦石卸點(diǎn)需要的鐵含量要求都為29.5%?1%(品位限制），搭配量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變。卡車

51、載重量為154噸，平均時(shí)速28km,平均卸車時(shí)間為3分鐘。,問(wèn)題：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，分別在哪些路線上各運(yùn)輸多少次 ?,平面示意圖,問(wèn)題數(shù)據(jù),問(wèn)題分析,與典型的運(yùn)輸問(wèn)題明顯有以下不同：這是運(yùn)輸?shù)V石與巖石兩種物資的問(wèn)題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問(wèn)題；為了完成品位約束，礦石要搭配運(yùn)輸；產(chǎn)地、銷地均有單位時(shí)間的流量限制；運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇

52、不多于7個(gè)產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。,近似處理：先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排,模型假設(shè),卡車在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)的情況；在鏟位或卸點(diǎn)處由兩條路線以上造成的沖突問(wèn)題面前，我們認(rèn)為只要平均時(shí)間能完成任務(wù)，就認(rèn)為不沖突。我們不排時(shí)地進(jìn)行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)，等等。,如理

53、解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來(lái)解 個(gè)別參數(shù)隊(duì)找到了可行解 （略）,符號(hào),xij ：從i鏟位到j(luò)號(hào)卸點(diǎn)的石料運(yùn)量 （車） 單位： 噸；cij ：從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的距離 公里；Tij :從i號(hào)鏟位到號(hào)j卸點(diǎn)路線上運(yùn)行一個(gè)周期平均時(shí)間 分；Aij ：從號(hào)鏟位到號(hào)卸點(diǎn)最多能同時(shí)運(yùn)行的卡車數(shù)

54、 輛；Bij ：從號(hào)鏟位到號(hào)卸點(diǎn)路線上一輛車最多可運(yùn)行的次數(shù) 次；pi：i號(hào)鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) %qj : j號(hào)卸點(diǎn)任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸cki ：i號(hào)鏟位的鐵礦石儲(chǔ)量 萬(wàn)噸cyi ：i號(hào)鏟位的

55、巖石儲(chǔ)量 萬(wàn)噸fi :描述第i號(hào)鏟位是否使用的0-1變量，取1為使用；0為關(guān)閉。,,,,(近似),優(yōu)化模型,,（1）道路能力(卡車數(shù))約束（2）電鏟能力約束（3）卸點(diǎn)能力約束（4）鏟位儲(chǔ)量約束（5）產(chǎn)量任務(wù)約束（6）鐵含量約束（7）電鏟數(shù)量約束（8）整數(shù)約束,.,xij為非負(fù)整數(shù)fi 為0-1整數(shù),計(jì)算結(jié)果（LINGO軟件）,,計(jì)算結(jié)

56、果（派車）,結(jié)論：鏟位1、2、3、4、8、9、10處各放置一臺(tái)電鏟。一共使用了13輛卡車；總運(yùn)量為85628.62噸公里；巖石產(chǎn)量為32186噸；礦石產(chǎn)量為38192噸。,此外：6輛聯(lián)合派車（方案略）,2005年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題 DVD在線租賃,隨著信息時(shí)代的到來(lái)，網(wǎng)絡(luò)成為人們生活中越來(lái)越不可或缺的元素之一。許多網(wǎng)站利用其強(qiáng)大的資源和知名度，面向其會(huì)員群提供日益專業(yè)化和便捷化的服務(wù)。例如，音像制品的在線租賃就是一種可行

57、的服務(wù)。這項(xiàng)服務(wù)充分發(fā)揮了網(wǎng)絡(luò)的諸多優(yōu)勢(shì)，包括傳播范圍廣泛、直達(dá)核心消費(fèi)群、強(qiáng)烈的互動(dòng)性、感官性強(qiáng)、成本相對(duì)低廉等，為顧客提供更為周到的服務(wù)。 。,,考慮如下的在線DVD租賃問(wèn)題。顧客繳納一定數(shù)量的月費(fèi)成為會(huì)員，訂購(gòu)DVD租賃服務(wù)。會(huì)員對(duì)哪些DVD有興趣，只要在線提交訂單，網(wǎng)站就會(huì)通過(guò)快遞的方式盡可能滿足要求。會(huì)員提交的訂單包括多張DVD，這些DVD是基于其偏愛(ài)程度排序的。網(wǎng)站會(huì)根據(jù)手頭現(xiàn)有的DVD數(shù)量和會(huì)員的訂單進(jìn)行分發(fā)。每個(gè)會(huì)員每個(gè)

58、月租賃次數(shù)不得超過(guò)2次，每次獲得3張DVD。會(huì)員看完3張DVD之后，只需要將DVD放進(jìn)網(wǎng)站提供的信封里寄回（郵費(fèi)由網(wǎng)站承擔(dān)），就可以繼續(xù)下次租賃,,請(qǐng)考慮以下問(wèn)題：1、…2、表2中列出了網(wǎng)站手上100種DVD的現(xiàn)有張數(shù)和當(dāng)前需要處理的1000位會(huì)員的在線訂單（表2的數(shù)據(jù)格式示例如下表），如何對(duì)這些DVD進(jìn)行分配，才能使會(huì)員獲得最大的滿意度？請(qǐng)具體列出前30位會(huì)員（即C0001~C0030）分別獲得哪些DVD。,,,注：D001~D1

59、00表示100種DVD, C0001~C1000表示1000個(gè)會(huì)員, 會(huì)員的在線訂單用數(shù)字1,2,…表示，數(shù)字越小表示會(huì)員的偏愛(ài)程度越高，數(shù)字0表示對(duì)應(yīng)的DVD當(dāng)前不在會(huì)員的在線訂單中。,,問(wèn)題二的解答1、如何定義滿意度？滿意度是在線訂單表格數(shù)字的減函數(shù),,,滿意度的幾種定義方式,,2、0-1規(guī)劃模型對(duì)于問(wèn)題中的分配問(wèn)題,我們可以設(shè)0-1 決策變量 , =1 表示將j 號(hào)DVD分配給i 號(hào)會(huì)員, =0 表示不分配.,2005

60、 DVD問(wèn)題數(shù)學(xué)模型,,,lingo程序! Excel 表b2005table2.xls A(i,j) 為零改為 11；!Excel表b2005table3.xls 為未改動(dòng)數(shù)據(jù)model:sets:user/1..1000/:y;dvd/1..100/:C;link(user,dvd):A,S,X;endsets,2005 DVD問(wèn)題,data:S=@ole('d:\lingo8\B2005table2.

61、xls');C=@ole('d:\lingo8\B2005table2.xls','CC');A=@ole('d:\ling8\b2005table3.xls');enddata,2005 DVD問(wèn)題,max=@sum(link(i,j):(11-S(i,j))/10*X(i,j));@for(dvd(j):@sum(user(i):X(i,j))<=C(j));

62、@for(user(i):@sum(dvd(j):X(i,j))=3*y(i));@for(link(i,j):@bnd(0,X(i,j),A(i,j)));@for(link(i,j):@bin(X));,貨郎擔(dān)問(wèn)題，Traveling Salesman Problem,有一個(gè)推銷員，從城市1出發(fā)，要遍訪城市2，3，…，n各一次，最后返回城市1。已知從城市i到j(luò)的旅費(fèi)為cij，問(wèn)他應(yīng)按怎樣的次序訪問(wèn)這些城市，使得總旅費(fèi)最少？,Tr

63、aveling Salesman Problem,引入一些0-1整數(shù)變量：,目標(biāo)是使為最小,Traveling Salesman Problem,TSP問(wèn)題有兩種理解，一種是找頂點(diǎn)不重復(fù)的最小權(quán)的Hamilton圈，另外一種是找一條經(jīng)過(guò)每個(gè)頂點(diǎn)且有最小權(quán)的閉鏈(頂點(diǎn)可以重復(fù))。對(duì)于滿足三角不等式的完全圖，兩者是一致的。,Traveling Salesman Problem,兩個(gè)約束條件：訪問(wèn)城市i后必須要有一個(gè)即將訪問(wèn)的確切城

64、市；訪問(wèn)城市j前必須要有一個(gè)剛剛訪問(wèn)過(guò)的確切城市。,Traveling Salesman Problem,但以上兩個(gè)條件對(duì)于TSP來(lái)說(shuō)并不充分，僅僅是必要條件。例如：,以上兩個(gè)條件都滿足，但它顯然不是TSP的解，它存在兩個(gè)子巡回。,Traveling Salesman Problem,把額外變量 (表示城市I在巡回中的次序)附加到問(wèn)題中,附加下面形式的約束條件,Traveling Salesman P

65、roblem,可以證明：（1）任何含子巡回的路線都不滿足該約束條件；（2）全部巡回都滿足該約束條件。,Traveling Salesman Problem,TSP轉(zhuǎn)化成了一個(gè)混合整數(shù)線性規(guī)劃問(wèn)題,TSP Lingo程序,,sets: cities/1..10/:u; link(cities, cities): distance, x; endsetsdata: distance = 0 8

66、 5 9 12 14 12 16 17 22…enddata,TSP Lingo程序,enddatan=@size(cities); min=@sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j)),TSP Lingo程序,@for(cities(i) : @sum(cities(j)| j #ne# i: x(j,i))=1; @sum(cities(j)| j #ne#

67、i: x(i,j))=1; @for(cities(j)| j #gt# 1 #and# j #ne# i : u(i)-u(j) +n* x(i,j)<=n-1; ););@for(link : @bin(x));@for(cities(i) | i #gt# 1 : u(i)<=n-2;,TSP Lingo程序,但是,這個(gè)程序運(yùn)行太慢, 如果加上界for(cities(i) | i #

68、gt# 1 : u(i)=1+(n-2)*x(i,1);很快就得到結(jié)果,TSP問(wèn)題二 18個(gè)節(jié)點(diǎn),,TSP問(wèn)題二,min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));@for(cities(i) : @sum(cities(j)| j #ne# i: x(j,i))=1; @sum(cities(j)| j #ne# i: x(i,j))=1;@for(cities(j)| j

69、 #gt# 1 #and# j #ne# i :u(i)-u(j) +n* x(i,j)=1+(n-2)*x(i,1););,TSP問(wèn)題三,29個(gè)節(jié)點(diǎn)的問(wèn)題（tsp3.lg4)。Lingo 運(yùn)行時(shí)間為1分40秒 找到最優(yōu)解,TSP問(wèn)題4,Tsp4.lg4, 48個(gè)節(jié)點(diǎn) 最優(yōu)解為 5046運(yùn)行4小時(shí)，找到解為 5074利用模擬退火法（C程序simu_tsp.c，數(shù)據(jù)文件tsp4.txt) 幾分鐘后找到最優(yōu)解5046 29 7 28