金晶晶
(福建交通職業(yè)技術學院基礎部,福建福州350007)
Lingo軟件在數(shù)學建模競賽中的應用
金晶晶
(福建交通職業(yè)技術學院基礎部,福建福州350007)
針對三道全國大學生數(shù)學建模競賽賽題,利用Lingo軟件對模型進行求解,并分析了Lingo軟件在求解較大規(guī)模數(shù)學規(guī)劃模型所發(fā)揮的作用。
Lingo軟件;數(shù)學建模;數(shù)學規(guī)劃;曲線擬合
數(shù)學建模(Mathematical Modeling)是對現(xiàn)實世界的一個特定對象,為了一個特定目的,根據特有的內在規(guī)律,作出一些必要的簡化假設,運用適當?shù)臄?shù)學工具,得到一個數(shù)學結構的過程[1]。
Lingo是Linear Interactive and General Optimizer的縮寫。Lingo軟件是美國芝加哥大學的Linus Schrage教授于1980年前后開發(fā)出來的一套專門用于求解最優(yōu)化問題的軟件包,即“交互式的線性和通用優(yōu)化求解器”,包括功能強大的建模語言,建立和編輯問題的全功能環(huán)境,讀取和寫入Excel和數(shù)據庫的功能,以及一系列完全內置的求解程序。使用者甚至不需要指定或啟動特定的求解器,因為Lingo會讀取方程式并自動選擇合適的求解器。目前Lingo產品已經有Lingo8.0版本,新版本的求解規(guī)模都在原有基礎上得到進一步加強。Lingo軟件的最大特色在于其具有的快速建構模型、輕松編輯數(shù)據、強大求解工具、交互式模型或建立完成應用、豐富的文件支持??v觀近幾年全國大學生數(shù)學建模競賽賽題,參賽者大都需要處理較復雜的數(shù)學規(guī)劃和曲線擬合等問題,模型的建立與求解較為復雜、計算量大,而matlab、mathmatica等軟件語法比較復雜不易掌握。Lingo軟件程序簡潔、計算精度高、結果可靠、易于修改和擴展,其內部建模語言是建立與求解大規(guī)模數(shù)學規(guī)劃模型的有力武器。2000年全國大學生數(shù)學建模競賽B題(鋼管訂購和運輸)中的最小費用流問題、2004年全國大學生數(shù)學建模競賽C題(酒后駕車)的曲線擬合問題、2006年全國大學生數(shù)學建模競賽中C題(易拉罐的最優(yōu)設計)的非線性規(guī)劃問題都可以充分展示用Lingo建模語言求解的優(yōu)越性。
歷年全國大學生數(shù)學建模競賽都需解決最優(yōu)生產計劃、最優(yōu)分配最優(yōu)設計、最優(yōu)決策、最佳管理等較為復雜的非線性規(guī)劃問題,模型由決策變量、目標函數(shù)、約束條件三個要素組成,其計算量較大,可用Lingo軟件求解。
2006“高教社杯”全國大學生數(shù)學建模競賽C題[3]第二小題,設易拉罐是一個正圓柱體,什么是它的最優(yōu)設計?經測量得圓柱的上底厚度為a=0.036cm、下底厚度為c=0.040cm、圓柱側壁厚度為b=0.012 cm??紤]易拉罐設計美觀性、便于把握以及材料節(jié)省等因素,于是建立目標規(guī)劃模型如下:利用Lingo8.0編程如下:
Lingo以語句Model開始,以語句End結束,這兩個語句單獨成一行。語句分為集合定義部分、數(shù)據初始化部分、目標函數(shù)、約束條件部分,這幾個部分的先后次序無關緊要。min開頭的語句表示求目標函數(shù)最小值?!?”開頭的語句是注釋語句,Lingo不作運行,每條中間語句必須以“;”號作為結尾。注意乘號不能省略,語句不計大小寫。
運行SOVLE,得部分結果如下:
即底面半徑為3.268480,圓柱體高為10.57760時,用料體積為5.157389,此為最優(yōu)設計。第三題亦可按此方法迎刃而解。上例充分體現(xiàn)Lingo其簡單易學、方便快捷的優(yōu)越性。
曲線擬合在眾多領域中得到了廣泛的應用,將曲線擬合問題轉化為數(shù)學規(guī)劃模型,并使用Lingo軟件來求解,該方法簡便快捷,是實現(xiàn)曲線擬合的一個有效方法。
2004年全國大學生數(shù)學建模競賽C題(酒后駕車)中給出某人短時間內喝下兩瓶啤酒后,間隔一定時間得到數(shù)據。以下建立無約束的非線性規(guī)劃模型[2]。間隔一定時間t測量他的血液中酒精含量y (毫克/百毫升),得到數(shù)據如表1:
表1 2004年全國大學生數(shù)學建模競賽C題(酒后駕車)數(shù)據
題目要求結合給定數(shù)據建立飲酒后血液中酒精濃度的數(shù)學模型。通過建立微分方程模型得到短時間內喝酒后血液中酒精濃度與時間的關系為:
求均方誤差
取極小值的待定系數(shù),即為最小二乘解。下面用Lingo軟件求解,具體算法如下:
以上程序中,SETS和ENDSETS之間的語句是對集合作定義,在此所定義的BAC是包含23個成員的集合,T和Y是BAC的兩個屬性,分別表示時間t和血液中酒精濃度y,它們都是含有23個成員的一維數(shù)組。DATA和ENDDATA之間的語句是對T和Y的進行賦值,其中@SUM和@EXP是Lingo提供的內部函數(shù),@SUM的作用是對某個集合的所有成員求某個表達式的和,該函數(shù)需要兩個參數(shù),第一個參數(shù)為集合名稱,指定對該集合的所有成員求和,此處第一個參數(shù)是BAC,它有23個成員,則求和運算對這23個成員進行。第二個參數(shù)是一個表達式,表示求和運算對該表達式進行,兩個參數(shù)之間用“:”號隔開。如果有約束條件,可放在目標函數(shù)之后,此處沒有約束條件,故目標函數(shù)之后即以END結束整個程序。點擊SOLVE,運行結果如下:
LINGO求多元函數(shù)極小值時內部所采用的算法效率高、速度快、精度高。用于非線性曲線擬合時,對擬合函數(shù)的形式無任何限制,無需初始值,能準確地得到回歸系數(shù)的最小二乘解,計算精度高,程序簡潔。
運籌學的交通運輸問題中,往往要求在完成運輸任務的前提下,尋求一個使總運輸費用最省的運輸方案,這就是最小費用流問題。如果只考慮單位貨物的運輸費用,那么這個問題就變成最短路問題。模型的傳統(tǒng)求解迭代次數(shù)太多,比較復雜,而matlab、mathmatica等軟件語法復雜不易編程,Lingo8.0其內部語言為解決該類問題的強有力武器。
2000年全國大學生數(shù)學建模競賽B題“鋼管的訂購和運輸”是一道離散優(yōu)化問題。如圖1,有7家鋼管生產廠Si(i=1,2,…7),提供鋼管到一條擬鋪設鋼管的天然氣輸送主管道上的15個站點 Aj(j=1,2,…15)。鋼管可通過公路和鐵路運至鋪設地點,圖中粗線表示鐵路,單細線表示公路,雙細線表示要鋪設的管道(假設沿管道或者原有公路,或者建有施工公路),空心圓點表示火車站。鋼管運到站點后由各站點沿管道向兩邊鋪設直至合攏。該題要求制定鋼管訂購和運輸?shù)膬?yōu)化計劃,使總費用最小。
圖1 天然氣輸送主管道圖
欲解決該問題首先需確定從Si至Aj的最優(yōu)路徑,從而確定出鋼管從i地運往j地的最小運費,即求解最小費用流問題。根據該題的需要,不妨設從Si至Aj的鋼管經過鐵路后,一旦走公路,則不會再通過鐵路運輸。下以S2為例,計算S2至Aj的最優(yōu)路徑。圖1中Bk/Lk(k=16,2,…,32)中表示S2至沿鐵路至火車站Bk的費用為Lk。問題轉化為求以Si為起點、Aj為終點的賦權圖的最短路徑問題。由Dijkstra算法,運用Lingo8.0編程如下:
以上SETS開始至ENDSETS結束的內容是定義所有的邊?!癈ITIES/1..33/:F;”是用集合CITIES定義一維變量 F,其格式為:“setname/memberlist(or1.. n)/:attribute,...”,一個集合只需要給出維數(shù)(mem-berlist,用1..n表示或其他文字符號表示或用集合表示),后接具有該維數(shù)的變量(attribute)。以上DATA開始至ENDDATA結束的內容是賦以上各邊以相應的權。Dijkstra算法的循環(huán)語句為:“@FOR(CITIES( i)|i#LT# @SIZE(CITIES):F(i)= @MIN( ROADS(i,j):D(i,j)+F(j)));”,其中邏輯運算符“#LT#”表示小于。
即可求得單位鋼管從S2到Aj的最小運費F(j) (j=1,…,15)如下:
表2 單位鋼管從S2到Aj的最小運費
同理可求得S1,S3,S4,S5,S7,S7各點到目的點的最優(yōu)單位運費。
經定量分析可得較合理的方案為:S1,S2,S3負責往鋪設點A1至A9供應鋼管,S4、S5、S6、S7負責往A8至 A15供應鋼管。
Lingo軟件內置建模語言以較少的語句、直觀的方式描述較大規(guī)模的數(shù)學規(guī)劃模型。其中,@ SUM、@For和@IF等語句的應用,極大地方便了數(shù)學模型的建立。此外,由曲線擬合模型可得,可以將原先不屬于優(yōu)化問題的模型,利用Lingo軟件內部建模語言進行求解,較之傳統(tǒng)的求解方法更簡單。
在實際應用領域,Lingo其線性、非線性和整數(shù)規(guī)劃求解程序已經被全世界數(shù)千萬的公司用來做最大化利潤和最小化成本的分析。Lingo能在產品分銷、成分混合、生產與個人事務安排、存貨管理、生產線性規(guī)劃、運輸、財務金融、投資分配、資本預算、混合排程、庫存管理、資源配置等問題的數(shù)學建模中發(fā)揮巨大作用。
[1]姜啟源,謝金星,葉 俊.數(shù)學模型:第三版[M].北京:高等教育出版社,2003:3-4.
[2]袁新生,廖大慶.用Lingo6.0求解大型數(shù)學規(guī)劃[J].工科數(shù)學,2001(5):73-77.
Application of Lingo Software to Mathematical Contest in Modeling
J IN Jing-jing
(Basic Courses Dept.,Fujian Communication Technology College,Fuzhou 350007,China)
On the analysis of three questions in National Mathematical Contest in Modeling for College students,this paper puts forward the way in solving the model by using Lingo software accordingly,and analyzes the role the Lingo software plays in solving large-scale mathematical optimization model.
Lingo software;mathematical modeling;mathematical optimization;curve fitting
book=85,ebook=160
O141.4
A
1008-4738(2010)04-0085-04
2010-06-20
福建交通職業(yè)技術學院科技發(fā)展基金(Ky1001)。
金晶晶(1983-),男,福建交通職業(yè)技術學院基礎部助教,理學碩士,研究方向:組合數(shù)學與圖論。