數(shù)學(xué)規(guī)劃及Lingo

1、數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 實(shí)際問題中實(shí)際問題中的優(yōu)化模型的優(yōu)化模型211, 2 , 1, 0)( , 2 , 1, 0)(. .),(),()(mjxhmixgtsxxxxfzMaxMinjiTn或x決策變量決策變量 f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0, hj(x)=0 約束條件約束條件數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃線性規(guī)劃線性規(guī)劃:目標(biāo)函數(shù)和約束條件均為線性。目標(biāo)函數(shù)和約束條件均為線性。非線性規(guī)劃：目標(biāo)函數(shù)和約束條件至少一個(gè)非線性規(guī)劃：目標(biāo)函數(shù)和約束條件至少一個(gè)非線性的。非線性的。整數(shù)規(guī)劃：決策變量取值為整數(shù)。整數(shù)規(guī)劃：決策變量取值為整數(shù)。多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個(gè)數(shù)決策變量個(gè)數(shù)n和

2、約束條件個(gè)數(shù)和約束條件個(gè)數(shù)m1+m2較大；較大； 最優(yōu)解在可行域的邊界上取得。最優(yōu)解在可行域的邊界上取得。 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型重點(diǎn)在模型的建立、軟件求解及結(jié)果的分析。重點(diǎn)在模型的建立、軟件求解及結(jié)果的分析。數(shù)學(xué)軟件求解優(yōu)化模型包括：數(shù)學(xué)軟件求解優(yōu)化模型包括：LingoLingo、MatlabMatlab等。等。為了結(jié)合結(jié)果分析，這里我們主要介紹為了結(jié)合結(jié)果分析，這里我們主要介紹Lingo 11Lingo 11軟件。軟件。LINGO簡(jiǎn)介簡(jiǎn)介 LINGO 軟件有多種版本，如LINDO，GINO 和LINGO(包括LINGO NL)軟件。 LINGO 是一種專門用于求解數(shù)學(xué)規(guī)劃問題的優(yōu)化計(jì)算軟

3、件包，版權(quán)現(xiàn)在由美國(guó)LINDO 系統(tǒng)公司所擁有。LINGO 軟件包的特點(diǎn)是程序執(zhí)行速度快，易于方便地輸入、修改、求解和分析一個(gè)數(shù)學(xué)規(guī)劃（優(yōu)化問題），因此LINGO 在教學(xué)，科研和工業(yè)界得到廣泛應(yīng)用。LINGO 11有兩種命令模式Windows 模式, 通過下拉式菜單命令驅(qū)動(dòng)LINGO 運(yùn)行。命令行(Command-Line) 模式,僅在命令窗口下操作。LINGO 軟件主要具有兩大優(yōu)點(diǎn)1、可用于求解非線性規(guī)劃問題，包括非線性整數(shù)規(guī)劃問題。還可以進(jìn)行靈敏性分析。2、LINGO 包含了內(nèi)置的建模語言，允許以簡(jiǎn)練、直觀的方式描述較大規(guī)模的優(yōu)化問題，模型中所需的數(shù)據(jù)可以以一定格式保存在獨(dú)立的文件中。說明

4、：說明：LPLP問題的數(shù)學(xué)模型及問題的數(shù)學(xué)模型及LINGOLINGO程序程序2132minxx 0,60021003502121121xxxxxxx 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)、約束和說明語句）后面均增加了一個(gè)分號(hào)“;”（7） 模型結(jié)束標(biāo)志“END”也被刪除了（LINGO 中只有當(dāng)模型以“MODEL：”開始時(shí)才能以“END” 結(jié)束）。

5、（5） LINGO中變量不區(qū)分大小寫；（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 來解二次規(guī)劃問題2221212123 . 027798maxxxxxxx為整數(shù)0,2100212121xxxxxx s.t. max=98*x1+277*x2-x12-0.3*x1*x2-2*x22;x1+x2100;x12*x2;gin(x1);gin(x2);1) 變量和行

6、名可以超過8 個(gè)字符，但不能超過32 個(gè)字符，且必須以字母開頭;2) LINGO 已假定各變量非負(fù)（除非用函數(shù)free或sub 或slb 另行說明）;3) 變量可以放在約束條件的右端（同時(shí)數(shù)字也可放在約束條件的左端）。但為了提高效率，應(yīng)盡可能采用線性表達(dá)式定義目標(biāo)和約束（如果可能).說明：說明：求解結(jié)果：求解結(jié)果：6181minijijijxc8 , 2 , 1; 6 , 2 , 1, 06 , 2 , 1,8 , 2 , 1,8161jixiexjdxijijijjiijs.t. LINGO的編程對(duì)于復(fù)雜的優(yōu)化模型的求解時(shí)要涉及到LINGO編程，即，定義集合、使用循環(huán)語句和文件輸入輸出操作等

7、。如LINGO程序?yàn)椋簃odel:!6發(fā)點(diǎn)8收點(diǎn)運(yùn)輸問題;sets: !集合段; warehouses/wh1.wh6/: capacity; vendors/v1.v8/: 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)=c

8、apacity(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模型中使用集之前，必須在集部分事

9、先定義。集部分以關(guān)鍵字“sets:”開始，以“endsets”結(jié)束。模型的集部分為了定義一個(gè)原始集，必須詳細(xì)聲明：集的名字可選，集的成員可選，集成員的屬性定義一個(gè)原始集，用下面的語法：setname/member_list/:attribute_list;原始集集可以分為兩類，即：原始集和派生集為了定義一個(gè)派生集，必須詳細(xì)聲明：集的名字父集的名字可選，集成員可選，集成員的屬性可用下面的語法定義一個(gè)派生集：setname(parent_set_list)/member_list/:attribute_list;例如：sets: product/A B/; machine/M N/; week/1

10、.2/; allowed(product,machine,week):x;endsets 派生集優(yōu)先級(jí)運(yùn)算符最高#NOT# ，（負(fù)號(hào)）* ，/+，（減號(hào)）#EQ#，#NE#，#GE#，#GT#，#LE#，#LT#AND#，#OR#最低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ù)

11、。 sign(x)：如果x=0時(shí)，返回不超過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ù)的，也就是說下界為0，上界為+。free取消了默認(rèn)的下界為0的限制，使變量也可以取負(fù)值。bnd用于

12、設(shè)定一個(gè)變量的上下界,它也可以取消默認(rèn)下界為0的約束。變量界定函數(shù)集循環(huán)函數(shù)集循環(huán)函數(shù)遍歷整個(gè)集進(jìn)行操作。其語法為function(setname(set_index_list)|conditional_qualifier:expression_list);1for該函數(shù)用來產(chǎn)生對(duì)集成員的約束?；诮ＵZ言的標(biāo)量需要顯式輸入每個(gè)約束，不過for函數(shù)允許只輸入一個(gè)約束，然后LINGO自動(dòng)產(chǎn)生每個(gè)集成員的約model:sets:number/1.5/:x;endsetsfor(number(I): x(I)=I2);end例：產(chǎn)生序列1,4,9,16,252sum該函數(shù)返回遍歷指定的集成員的一個(gè)表

13、達(dá)式的和。例：求向量5，1，3，4，6，10前5 個(gè)數(shù)的和。model:data:N=6;enddatasets:number/1.N/:x;endsetsdata:x = 5 1 3 4 6 10;enddatas=sum(number(I) | I #le# 5: x);end3min和max例：求向量5，1，3，4，6，10前5 個(gè)數(shù)的最小值，后3 個(gè)數(shù)的最大值。model:data:N=6;enddatasets:number/1.N/:x;endsetsdata:x = 5 1 3 4 6 10;enddataminv=min(number(I) | I #le# 5: x);max

14、v=max(number(I) | I #ge# N-2: x);end輸入和輸出函數(shù)可以把模型和外部數(shù)據(jù)比如文本文件、數(shù)據(jù)庫和電子表格等連接起來。 輸入和輸出函數(shù)1file函數(shù) 該函數(shù)用從外部文件中輸入數(shù)據(jù)，可以放在模型中任何地方。該函數(shù)的語法格式為file(filename)。這里filename是文件名，可以采用相對(duì)路徑和絕對(duì)路徑兩種表示方式。2text函數(shù)該函數(shù)被用在數(shù)據(jù)部分用來把解輸出至文本文件中。它可以輸出集成員和集屬性值。其語法為text(filename) 用該命令產(chǎn)生當(dāng)前模型的靈敏性分析報(bào)告：研究當(dāng)目標(biāo)函數(shù)的費(fèi)用系數(shù)和約束右端項(xiàng)在什么范圍（此時(shí)假定其它系數(shù)不變）時(shí)，最優(yōu)基保持

15、不變。靈敏性分析是在求解模型時(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í)，就沒有必要激活它。靈敏性分析（Range，Ctrl+R） 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A

16、1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 4808

17、1221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 軟件實(shí)現(xiàn)軟件實(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

18、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.000000DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元。元。 結(jié)果解釋結(jié)果解釋 原料無剩余原料

19、無剩余時(shí)間無剩余時(shí)間無剩余加工能力剩余加工能力剩余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.00

20、0000 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é)果解釋結(jié)果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增增加加1單位時(shí)單位時(shí)“效益效益”的的增量增量 原料增加原料增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)48 時(shí)間增加時(shí)間增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)2 加工能力增長(zhǎng)不影響利潤(rùn)加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時(shí)工人付出的工資最

21、多每小時(shí)幾元？聘用臨時(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.00

22、0000 4 40.00000 0.000000RANGES 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