《數(shù)學(xué)規(guī)劃及》PPT課件.ppt

數(shù)學(xué)規(guī)劃模型,實(shí)際問(wèn)題中 的優(yōu)化模型,x決策變量,f(x)目標(biāo)函數(shù),gi(x)0, hj(x)=0 約束條件,數(shù)學(xué)規(guī)劃,線性規(guī)劃:目標(biāo)函數(shù)和約束條件均為線性。,非線性規(guī)劃：目標(biāo)函數(shù)和約束條件至少一個(gè)非線性的。,整數(shù)規(guī)劃：決策變量取值為整數(shù)。,多元函數(shù)條件極值,決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)m1+m2較大；,最優(yōu)解在可行域的邊界上取得。,數(shù)學(xué)規(guī)劃模型,重點(diǎn)在模型的建立、軟件求解及結(jié)果的分析。,數(shù)學(xué)軟件求解優(yōu)化模型包括：Lingo、Matlab等。為了結(jié)合結(jié)果分析，這里我們主要介紹Lingo 11軟件。,LINGO簡(jiǎn)介,LINGO 軟件有多種版本，如LINDO，GINO 和LINGO(包括LINGO NL)軟件。,LINGO 是一種專門(mén)用于求解數(shù)學(xué)規(guī)劃問(wèn)題的優(yōu)化計(jì)算軟件包，版權(quán)現(xiàn)在由美國(guó)LINDO 系統(tǒng)公司所擁有。LINGO 軟件包的特點(diǎn)是程序執(zhí)行速度快，易于方便地輸入、修改、求解和分析一個(gè)數(shù)學(xué)規(guī)劃（優(yōu)化問(wèn)題），因此LINGO 在教學(xué)，科研和工業(yè)界得到廣泛應(yīng)用。,LINGO 11有兩種命令模式,Windows 模式, 通過(guò)下拉式菜單命令驅(qū)動(dòng)LINGO 運(yùn)行。,命令行(Command-Line) 模式,僅在命令窗口下操作。,LINGO 軟件主要具有兩大優(yōu)點(diǎn),1、可用于求解非線性規(guī)劃問(wèn)題，包括非線性整數(shù)規(guī)劃問(wèn)題。還可以進(jìn)行靈敏性分析。,2、LINGO 包含了內(nèi)置的建模語(yǔ)言，允許以簡(jiǎn)練、直觀的方式描述較大規(guī)模的優(yōu)化問(wèn)題，模型中所需的數(shù)據(jù)可以以一定格式保存在獨(dú)立的文件中,說(shuō)明：,LP問(wèn)題的數(shù)學(xué)模型及LINGO程序,s.t.,min=2*x1+3*x2;,x1+x2350; x1100; 2*x1+x2600;,（1）. 將目標(biāo)函數(shù)的表示方式從“min”變成了“min=”。,（2）.“ST”在LINGO 模型中不再需要，所以被刪除了。,（3） 每個(gè)系數(shù)與變量間增加了運(yùn)算符“*”（即乘號(hào)不能省略）,（4） 每行（目標(biāo)、約束和說(shuō)明語(yǔ)句）后面均增加了一個(gè)分號(hào)“;”,（7） 模型結(jié)束標(biāo)志“END”也被刪除了（LINGO 中只有當(dāng)模型以“MODEL：”開(kāi)始時(shí)才能以“END” 結(jié)束）。,（5） LINGO中變量不區(qū)分大小寫(xiě)；,（6） 由于LINGO中已假設(shè)所以變量都是非負(fù)的，所以非負(fù)約束不必再輸?shù)接?jì)算機(jī)中；,狀態(tài)窗口的參數(shù)解釋,變量數(shù)量（其中包括變量總數(shù)、 非線性變量數(shù)、整數(shù)變量數(shù)）,非零系數(shù)數(shù)量（總數(shù)、非線 性項(xiàng)的個(gè)數(shù)）,內(nèi)存使用量、求解花費(fèi)的時(shí)間,約束數(shù)量（約束總數(shù)、非線性約束個(gè)數(shù)）,狀態(tài)窗口的參數(shù)解釋,用LINGO 來(lái)解二次規(guī)劃問(wèn)題,s.t.,max=98*x1+277*x2-x12-0.3*x1*x2-2*x22; x1+x2100; x12*x2; gin(x1);gin(x2);,1) 變量和行名可以超過(guò)8 個(gè)字符，但不能超過(guò)32 個(gè)字符，且必須以字母開(kāi)頭;,2) LINGO 已假定各變量非負(fù)（除非用函數(shù)free或sub 或slb 另行說(shuō)明）;,3) 變量可以放在約束條件的右端（同時(shí)數(shù)字也可放在約束條件的左端）。但為了提高效率，應(yīng)盡可能采用線性表達(dá)式定義目標(biāo)和約束（如果可能).,說(shuō)明：,求解結(jié)果：,s.t.,LINGO的編程,對(duì)于復(fù)雜的優(yōu)化模型的求解時(shí)要涉及到LINGO編程，即， 定義集合、使用循環(huán)語(yǔ)句和文件輸入輸出操作等。如,LINGO程序?yàn)椋?model: !6發(fā)點(diǎn)8收點(diǎn)運(yùn)輸問(wèn)題; sets: !集合段; warehouses/wh1wh6/: capacity; vendors/v1v8/: demand; links(warehouses,vendors): cost, volume; endsets !目標(biāo)函數(shù);!模型段; min=sum(links: cost*volume); !需求約束; for(vendors(J):sum(warehouses(I): volume(I,J)=demand(J); !產(chǎn)量約束; for(warehouses(I):sum(vendors(J): volume(I,J)=capacity(I); !下面是數(shù)據(jù);!數(shù)據(jù)段; data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; !text(r.txt)=volume; !cost=file(c.txt); Enddata !初始段 Init: endinit; end,集部分是LINGO模型的一個(gè)可選部分。在LINGO模型中使用集之前，必須在集部分事先定義。集部分以關(guān)鍵字“sets:”開(kāi)始，以“endsets”結(jié)束。,模型的集部分,為了定義一個(gè)原始集，必須詳細(xì)聲明： 集的名字 可選，集的成員 可選，集成員的屬性 定義一個(gè)原始集，用下面的語(yǔ)法： setname/member_list/:attribute_list;,原始集,集可以分為兩類，即：原始集和派生集,為了定義一個(gè)派生集，必須詳細(xì)聲明： 集的名字 父集的名字 可選，集成員 可選，集成員的屬性 可用下面的語(yǔ)法定義一個(gè)派生集： setname(parent_set_list)/member_list/:attribute_list;,例如： sets: product/A B/; machine/M N/; week/12/; allowed(product,machine,week):x; endsets,派生集,LINGO中有三類運(yùn)算符：算術(shù)運(yùn)算符，邏輯運(yùn)算符和關(guān)系運(yùn)算符。運(yùn)算符的優(yōu)先級(jí)如下。,abs(x)：返回x的絕對(duì)值。 sin(x)：返回x的正弦值，x采用弧度制。 cos(x)：返回x的余弦值。 tan(x)：返回x的正切值。 exp(x)：返回常數(shù)e的x次方。 log(x)：返回x的自然對(duì)數(shù)。 lgm(x)：返回x的gamma函數(shù)的自然對(duì)數(shù)。 mod(x,y)：返回x除以y的余數(shù)。 sign(x)：如果x=0時(shí)，返回不超過(guò)x的最大整數(shù)；當(dāng)x0時(shí)，返回不低于x的最大整數(shù)。 smax(x1,x2,xn)：返回x1，x2，xn中的最大值。 smin(x1,x2,xn)：返回x1，x2，xn中的最小值。,LINGO提供了大量的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)：,變量界定函數(shù)實(shí)現(xiàn)對(duì)變量取值范圍的附加限制，共4種： bin(x)：限制x為0或1； bnd(L,x,U)：限制LxU； free(x)：取消對(duì)變量x的默認(rèn)下界為0的限制，即x可以取任意實(shí)數(shù)； gin(x)：限制x為整數(shù)。 在默認(rèn)情況下，LINGO規(guī)定變量是非負(fù)的，也就是說(shuō)下界為0，上界為+。free取消了默認(rèn)的下界為0的限制，使變量也可以取負(fù)值。bnd用于設(shè)定一個(gè)變量的上下界,它也可以取消默認(rèn)下界為0的約束。,變量界定函數(shù),集循環(huán)函數(shù),集循環(huán)函數(shù)遍歷整個(gè)集進(jìn)行操作。其語(yǔ)法為 function(setname(set_index_list)|conditional_qualifier:expression_list);,1for 該函數(shù)用來(lái)產(chǎn)生對(duì)集成員的約束?；诮ＵZ(yǔ)言的標(biāo)量需要顯式輸入每個(gè)約束，不過(guò)for函數(shù)允許只輸入一個(gè)約束，然后LINGO自動(dòng)產(chǎn)生每個(gè)集成員的約,model: sets: number/15/:x; endsets for(number(I): x(I)=I2); end,例：產(chǎn)生序列1,4,9,16,25,2sum 該函數(shù)返回遍歷指定的集成員的一個(gè)表達(dá)式的和。,例：求向量5，1，3，4，6，10前5 個(gè)數(shù)的和。,model: data: N=6; enddata sets: number/1N/:x; endsets data: x = 5 1 3 4 6 10; enddata s=sum(number(I) | I #le# 5: x); end,3min和max,例：求向量5，1，3，4，6，10前5 個(gè)數(shù)的最小值，后3 個(gè)數(shù)的最大值。,model: data: N=6; enddata sets: number/1N/:x; endsets data: x = 5 1 3 4 6 10; enddata minv=min(number(I) | I #le# 5: x); maxv=max(number(I) | I #ge# N-2: x); end,輸入和輸出函數(shù)可以把模型和外部數(shù)據(jù)比如文本文件、數(shù)據(jù)庫(kù)和電子表格等連接起來(lái)。,輸入和輸出函數(shù),1file函數(shù) 該函數(shù)用從外部文件中輸入數(shù)據(jù)，可以放在模型中任何地方。該函數(shù)的語(yǔ)法格式為file(filename)。這里filename是文件名，可以采用相對(duì)路徑和絕對(duì)路徑兩種表示方式。,2text函數(shù) 該函數(shù)被用在數(shù)據(jù)部分用來(lái)把解輸出至文本文件中。它可以輸出集成員和集屬性值。其語(yǔ)法為 text(filename)。,用該命令產(chǎn)生當(dāng)前模型的靈敏性分析報(bào)告：研究當(dāng)目標(biāo)函數(shù)的費(fèi)用系數(shù)和約束右端項(xiàng)在什么范圍（此時(shí)假定其它系數(shù)不變）時(shí)，最優(yōu)基保持不變。靈敏性分析是在求解模型時(shí)作出的，因此在求解模型時(shí)靈敏性分析是激活狀態(tài)，但是默認(rèn)是不激活的。為了激活靈敏性分析，運(yùn)行LINGO|Options，選擇General Solver Tab， 在Dual Computations 列表框中，選擇Prices and Ranges 選項(xiàng)。靈敏性分析耗費(fèi)相當(dāng)多的求解時(shí)間，因此當(dāng)速度很關(guān)鍵時(shí)，就沒(méi)有必要激活它。,靈敏性分析（Range，Ctrl+R）,加工奶制品的生產(chǎn)計(jì)劃,50桶牛奶,時(shí)間480小時(shí),至多加工100公斤A1,制訂生產(chǎn)計(jì)劃，使每天獲利最大,35元可買(mǎi)到1桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少?,可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?,A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？,每天：,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 243x1,獲利 164 x2,原料供應(yīng),勞動(dòng)時(shí)間,加工能力,決策變量,目標(biāo)函數(shù),每天獲利,約束條件,非負(fù)約束,線性規(guī)劃模型(LP),時(shí)間480小時(shí),至多加工100公斤A1,模型求解,軟件實(shí)現(xiàn),LINGO 11,max =72*x1+64*x2； x1+x250； 12*x1+8*x2480； 3*x1100；,Global optimal solution found. Objective value: 3360.000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤(rùn)3360元。,結(jié)果解釋,原料無(wú)剩余,時(shí)間無(wú)剩余,加工能力剩余40,三種資源,“資源” 剩余為零的約束為緊約束（有效約束）,max =72*x1+64*x2； x1+x250； 12*x1+8*x2480； 3*x1100；,Global optimal solution found. Objective value: 3360.000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000,結(jié)果解釋,最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量,原料增加1單位, 利潤(rùn)增長(zhǎng)48,時(shí)間增加1單位, 利潤(rùn)增長(zhǎng)2,加工能力增長(zhǎng)不影響利潤(rùn),影子價(jià)格,35元可買(mǎi)到1桶牛奶，要買(mǎi)嗎？,35 48, 應(yīng)該買(mǎi)！,聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？,2元！,Global optimal solution found. Objective value: 3360.000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000,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 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 40.000000,最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系數(shù)范圍(64,96),x2系數(shù)范圍(48,72),A1獲利增加到 30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃,x1系數(shù)由24 3=72增加為303=90，在允許范圍內(nèi),不變！,(約束條件不變),結(jié)果解釋,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 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 40.000000,影子價(jià)格有意義時(shí)約束右端的允許變化范圍,原料最多增加10,時(shí)間最多增加53,35元可買(mǎi)到1桶牛奶，每天最多買(mǎi)多少？,最多買(mǎi)10桶!,(目標(biāo)函數(shù)不變),例2 奶制品的生產(chǎn)銷售計(jì)劃,在例1基礎(chǔ)上深加工,制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大,30元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？,50桶牛奶, 480小時(shí),至多100公斤A1,B1，B2的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？,出售x1 千克 A1, x2 千克 A2，,x3千克 B1, x4千克 B2,原料供應(yīng),勞動(dòng)時(shí)間,加工能力,決策變量,目標(biāo)函數(shù),利潤(rùn),約束條件,非負(fù)約束,x5千克 A1加工B1， x6千克 A2加工B2,附加約束,模型求解,軟件實(shí)現(xiàn),LINGO 11,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2,OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2,結(jié)果解釋,每天銷售168 千克A2和19.2 千克B1， 利潤(rùn)3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2， 將得到的24千克A1全部加工成B1,除加工能力外均為緊約束,結(jié)果解釋,增加1桶牛奶使利潤(rùn)增長(zhǎng)37.92,