1、LINGO軟件簡(jiǎn)介,常用優(yōu)化軟件,1. LINDO/LINGO軟件 2. MATLAB優(yōu)化工具箱 / Mathematic的優(yōu)化功能 3. SAS(統(tǒng)計(jì)分析)軟件的優(yōu)化功能 4. EXCEL軟件的優(yōu)化功能,MATLAB優(yōu)化工具箱能求解的優(yōu)化模型,優(yōu)化工具箱3.0 (MATLAB 7.0 R14),連續(xù)優(yōu)化,離散優(yōu)化,無約束優(yōu)化,非線性 極小 fminunc,非光滑(不可 微)優(yōu)化 fminsearch,非線性 方程(組) fzero fsolve,全局 優(yōu)化 暫缺,非線性 最小二乘 lsqnonlin lsqcurvefit,線性規(guī)劃 linprog,純0-1規(guī)劃 bintprog 一般IP(

2、暫缺),非線性規(guī)劃 fmincon fminimax fgoalattain fseminf,上下界約束 fminbnd fmincon lsqnonlin lsqcurvefit,約束線性 最小二乘 lsqnonneg lsqlin,約束優(yōu)化,二次規(guī)劃 quadprog,LINDO 公司軟件產(chǎn)品簡(jiǎn)要介紹,美國(guó)芝加哥(Chicago)大學(xué)的Linus Schrage教授于1980年前后開發(fā), 后來成立 LINDO系統(tǒng)公司（LINDO Systems Inc.）， 網(wǎng)址：,LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINDO

3、API: LINDO Application Programming Interface (V4.1) LINGO: Linear INteractive General Optimizer (V10.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0),演示(試用)版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版 （求解問題規(guī)模和選件不同）,LINDO/LINGO軟件能求解的模型,優(yōu)化,線性規(guī)劃,非線性規(guī)劃,二次規(guī)劃,連續(xù)優(yōu)化,整數(shù)規(guī)劃,LINDO,LINGO,LINGO軟件的功能與特點(diǎn),LINGO模型的優(yōu)點(diǎn),集成了線性(非線性) / 連續(xù)(整數(shù)) 優(yōu)化功能 具有

4、多點(diǎn)搜索 / 全局優(yōu)化功能 提供了靈活的編程語言(矩陣生成器)，可方便地輸入模型 提供與其他數(shù)據(jù)文件的接口 提供與其他編程語言的接口 LINDO API 可用于自主開發(fā) 運(yùn)行速度較快,LP QP NLP IP 全局優(yōu)化(選) ILP IQP INLP,LINGO軟件的求解過程,LINGO預(yù)處理程序,線性優(yōu)化求解程序,非線性優(yōu)化求解程序,分枝定界管理程序,1. 確定常數(shù) 2. 識(shí)別類型,1. 單純形算法 2. 內(nèi)點(diǎn)算法(選),1、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法(GRG) (選) 3、多點(diǎn)搜索(Multistart) (選),建模時(shí)需要注意的幾個(gè)基本問題,1、盡量使用實(shí)數(shù)優(yōu)化，減少整

5、數(shù)約束和整數(shù)變量 2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù) 如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等 3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù) （如x/y 5 改為x5y） 4、合理設(shè)定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng) (如小于103),LINGO軟件的基本使用方法,1. LINGO入門,安裝文件20M多一點(diǎn)，需要接受安裝協(xié)議、選擇安裝目錄（缺省C:LINGO8）。,LINGO軟件的安裝,安裝過程: 與一般Windows程序類似.,第一次運(yùn)行時(shí)提示輸入授權(quán)密碼，如圖：,LINGO軟件的主要特色,兩種命令模式,

6、Windows模式： 通過下拉式菜單命令驅(qū)動(dòng)LINGO運(yùn)行（多數(shù)菜單命令有快捷鍵，常用的菜單命令有快捷按鈕），圖形界面，使用方便；,命令行 模式：僅在命令窗口(Command Window)下操作，通過輸入行命令驅(qū)動(dòng)LINGO運(yùn)行 。,(這里主要介紹這種模式),LINGO界面簡(jiǎn)介,LINGO的界面,LINGO軟件的主窗口（用戶界面），所有其他窗口都在這個(gè)窗口之內(nèi)。,模型窗口（Model Window），用于輸入LINGO優(yōu)化模型（即LINGO程序）。,狀態(tài)行（最左邊顯示“Ready”，表示 “準(zhǔn)備就緒”）,當(dāng)前時(shí)間,當(dāng)前光標(biāo)的位置,LINGO的文件類型,.LG4：LINGO格式的模型文件，保存

7、了模型窗口中所能夠看到的所有文本和其他對(duì)象及其格式信息； .LNG：文本格式的模型文件，不保存模型中的格式信息（如字體、顏色、嵌入對(duì)象等）； .LDT：LINGO數(shù)據(jù)文件； .LTF：LINGO命令腳本文件； .LGR：LINGO報(bào)告文件； .LTX： LINDO格式的模型文件； .MPS：示MPS（數(shù)學(xué)規(guī)劃系統(tǒng)）格式的模型文件。,除“LG4”文件外，另外幾種格式的文件都是普通的文本文件，可以用任何文本編輯器打開和編輯。,運(yùn)行狀態(tài)窗口,Variables（變量數(shù)量）： 變量總數(shù)（Total）、 非線性變量數(shù)（Nonlinear）、 整數(shù)變量數(shù)（Integer）。,Constraints（約束數(shù)

8、量）： 約束總數(shù)（Total）、 非線性約束個(gè)數(shù)(Nonlinear)。,Nonzeros（非零系數(shù)數(shù)量）： 總數(shù)（Total）、 非線性項(xiàng)系數(shù)個(gè)數(shù)(Nonlinear)。,Generator Memory Used (K) (內(nèi)存使用量),Elapsed Runtime (hh:mm:ss)（求解花費(fèi)的時(shí)間）,運(yùn)行狀態(tài)窗口,求解器(求解程序)狀態(tài)框,當(dāng)前模型的類型 :LP，QP，ILP，IQP，PILP， PIQP，NLP，INLP，PINLP （以I開頭表示IP，以PI開頭表示PIP）,當(dāng)前解的狀態(tài) : Global Optimum, Local Optimum, Feasible, In

9、feasible“(不可行), Unbounded“(無界), Interrupted“(中斷), Undetermined“(未確定),解的目標(biāo)函數(shù)值,當(dāng)前約束不滿足的總量,目前為止的迭代次數(shù),運(yùn)行狀態(tài)窗口,擴(kuò)展的求解器(求解程序)狀態(tài)框,使用的特殊求解程序 : B-and-B (分枝定界算法) Global (全局最優(yōu)求解程序) Multistart(用多個(gè)初始點(diǎn)求解的程序),目前為止找到的可行解的最佳目標(biāo)函數(shù)值,目標(biāo)函數(shù)值的界,特殊求解程序當(dāng)前運(yùn)行步數(shù)： 分枝數(shù)(對(duì)B-and-B程序)； 子問題數(shù)(對(duì)Global程序)； 初始點(diǎn)數(shù)(對(duì)Multistart程序),有效步數(shù),一個(gè)簡(jiǎn)單的LIN

10、GO程序,例1 直接用LINGO來解如下二次規(guī)劃問題：,輸入窗口如下：,程序語句輸入的備注：,LINGO總是根據(jù)“MAX=”或“MIN=”尋找目標(biāo)函數(shù)，而除注釋語句和TITLE語句外的其他語句都是約束條件，因此語句的順序并不重要 。 限定變量取整數(shù)值的語句為“GIN(X1)”和“GIN(X2)” 。 LINGO中函數(shù)一律需要以“”開頭，其中整型變量函數(shù)是BIN、GIN和上下界限定函數(shù)是FREE、SUB、SLB。,輸出結(jié)果：,運(yùn)行菜單命令“LINGO|Solve”,最優(yōu)整數(shù)解 X=(35，65),最大利潤(rùn)=11077.5,輸出結(jié)果備注：,通過菜單 “WINDOW| Status Window”看

11、到狀態(tài)窗口，可看到最佳目標(biāo)值“Best Obj”與問題的上界“Obj Bound”已經(jīng)是一樣的，當(dāng)前解的最大利潤(rùn)與這兩個(gè)值非常接近，是計(jì)算誤差引起的。如果采用全局最優(yōu)求解程序(后面介紹)，可以驗(yàn)證它就是全局最優(yōu)解。,LINGO是將它作為PINLP(純整數(shù)非線性規(guī)劃)來求解，因此找到的是局部最優(yōu)解。,一個(gè)簡(jiǎn)單的LINGO程序,LINGO的基本用法的幾點(diǎn)注意事項(xiàng),LINGO中不區(qū)分大小寫字母；變量和行名可以超過8個(gè)字符，但不能超過32個(gè)字符，且必須以字母開頭。 用LINGO解優(yōu)化模型時(shí)已假定所有變量非負(fù)(除非用限定變量取值范圍的函數(shù)free或sub或slb另行說明)。 變量可以放在約束條件的右端(

12、同時(shí)數(shù)字也可放在約束條件的左端)。但為了提高LINGO求解時(shí)的效率，應(yīng)盡可能采用線性表達(dá)式定義目標(biāo)和約束(如果可能的話)。 語句是組成LINGO模型的基本單位,每個(gè)語句都以分號(hào)結(jié)尾，編寫程序時(shí)應(yīng)注意模型的可讀性。例如：一行只寫一個(gè)語句，按照語句之間的嵌套關(guān)系對(duì)語句安排適當(dāng)?shù)目s進(jìn)，增強(qiáng)層次感。 以感嘆號(hào)開始的是說明語句(說明語句也需要以分號(hào)結(jié)束)）。,2.在LINGO中使用集合,集合的基本用法和LINGO模型的基本要素,理解LINGO建模語言最重要的是理解集合（Set）及其屬性（Attribute）的概念。,例2. SAILCO公司需要決定下四個(gè)季度的帆船生產(chǎn)量。下四個(gè)季度的帆船需求量分別是40

13、條，60條，75條，25條，這些需求必須按時(shí)滿足。每個(gè)季度正常的生產(chǎn)能力是40條帆船，每條船的生產(chǎn)費(fèi)用為400美元。如果加班生產(chǎn)，每條船的生產(chǎn)費(fèi)用為450美元。每個(gè)季度末，每條船的庫(kù)存費(fèi)用為20美元。假定生產(chǎn)提前期為0，初始庫(kù)存為10條船。如何安排生產(chǎn)可使總費(fèi)用最小？,用DEM,RP,OP,INV分別表示需求量、正常生產(chǎn)的產(chǎn)量、加班生產(chǎn)的產(chǎn)量、庫(kù)存量，則DEM,RP,OP,INV對(duì)每個(gè)季度都應(yīng)該有一個(gè)對(duì)應(yīng)的值，也就說他們都應(yīng)該是一個(gè)由4個(gè)元素組成的數(shù)組，其中DEM是已知的，而RP,OP,INV是未知數(shù)。,問題的模型(可以看出是LP模型 ),目標(biāo)函數(shù)是所有費(fèi)用的和,約束條件主要有兩個(gè)：,1）能力

14、限制：,2）產(chǎn)品數(shù)量的平衡方程：,加上變量的非負(fù)約束,注：LINDO中沒有數(shù)組，只能對(duì)每個(gè)季度分別定義變量，如正常產(chǎn)量就要有RP1，RP2，RP3，RP4 4個(gè)變量等。寫起來就比較麻煩，尤其是更多(如1000個(gè)季度)的時(shí)候。 記四個(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稱為該集合的屬性(即定義在該集合上的

15、屬性)。,集合及其屬性,集合元素及集合的屬性確定的所有變量,LINGO中定義集合及其屬性,LP模型在LINGO中的一個(gè)典型輸入方式,以“MODEL：”開始,以“END”結(jié)束,給出優(yōu)化目標(biāo)和約束,目標(biāo)函數(shù)的定義方式,SUM(集合（下標(biāo)）：關(guān)于集合的屬性的表達(dá)式),對(duì)語句中冒號(hào)“：”后面的表達(dá)式，按照“：”前面的集合指定的下標(biāo)（元素）進(jìn)行求和。,本例中目標(biāo)函數(shù)也可以等價(jià)地寫成 SUM(QUARTERS(i): 400*RP(i) +450*OP(i) +20*INV(i) )， “SUM”相當(dāng)于求和符號(hào)“”， “QUARTERS(i)”相當(dāng)于“ ”的含義。 由于本例中目標(biāo)函數(shù)對(duì)集合QUARTERS

16、的所有元素(下標(biāo)) 都要求和，所以可以將下標(biāo)i省去。,約束的定義方式,循環(huán)函數(shù) FOR(集合(下標(biāo))：關(guān)于集合的屬性的約束關(guān)系式),對(duì)冒號(hào)“：”前面的集合的每個(gè)元素（下標(biāo)），冒號(hào)“：”后面的約束關(guān)系式都要成立,本例中，每個(gè)季度正常的生產(chǎn)能力是40條帆船，這正是語句“FOR(QUARTERS(I):RP(I)40);”的含義。 由于對(duì)所有元素(下標(biāo)I),約束的形式是一樣的，所以也可以像上面定義目標(biāo)函數(shù)時(shí)一樣，將下標(biāo)i省去， 這個(gè)語句可以簡(jiǎn)化成“FOR(QUARTERS:RP1；“#GT#”是邏輯運(yùn)算符號(hào)，意思是“大于（Greater Than的字首字母縮寫）” 。,約束的定義方式,問題的求解：運(yùn)

17、行菜單命令“LINGO|Solve”,最小成本=78450,注：由于輸入中沒有給出行名，所以行名是系統(tǒng)自動(dòng)按照行號(hào)1-9生成的。 選擇菜單命令“LINGO|Generate|Disply model（Ctrl+G）”，可以得到展開形式的模型(如圖)，可以看到完整的模型，也能確定行號(hào)(行號(hào)放在方括號(hào)“ ”中，且數(shù)字前面帶有下劃線“_”)。 最好在輸入模型時(shí)用戶主動(dòng)設(shè)定約束的行名(即約束名)，使程序清晰些。單一約束的行名設(shè)置方法就是將行名放在方括號(hào)“ ”中，置于約束之前。 后面將結(jié)合具體例子介紹在使用集合的情況下如何設(shè)置行名。,小結(jié):LINGO模型最基本的組成要素,一般來說， LINGO中建立的優(yōu)

18、化模型可以由五個(gè)部分組成，或稱為五“段”（SECTION）：,（1）集合段（SETS）：以“ SETS:” 開始， “ENDSETS”結(jié)束，定義必要的集合變量（SET）及其元素（MEMBER，含義類似于數(shù)組的下標(biāo)）和屬性（ATTRIBUTE，含義類似于數(shù)組）。,如上例中定義了集合quarters(含義是季節(jié))，它包含四個(gè)元素即四個(gè)季節(jié)指標(biāo)(1,2,3,4)，每個(gè)季節(jié)都有需求(DEM)、正常生產(chǎn)量(RP)、加班生產(chǎn)量(OP)、庫(kù)存量(INV)等屬性(相當(dāng)于數(shù)組，數(shù)組下標(biāo)由quarters元素決定)。一旦這樣的定義建立起來，如果quarters的數(shù)量不是4而是1000,只需擴(kuò)展其元素為1,2,.,

19、1000,每個(gè)季節(jié)仍然都有DEM,RP,OP,INV這樣的屬性(這些量的具體數(shù)值如果是常量，則可在數(shù)據(jù)段輸入；如果是未知數(shù)，則可在初始段輸入初值)。當(dāng)quarters的數(shù)量不是4而是1000時(shí)，沒有必要把1,2，.,1000全部一個(gè)一個(gè)列出來，而是可以如下定義quarters集合：“quarters/1.1000/:DEM,RP,OP,INV;” ,“1.1000”的意思就是從1到1000的所有整數(shù)。,（2）目標(biāo)與約束段：目標(biāo)函數(shù)、約束條件等，沒有段的開始和結(jié)束標(biāo)記，因此實(shí)際上就是除其它四個(gè)段(都有明確的段標(biāo)記)外的LINGO模型。 這里一般要用到LINGO的內(nèi)部函數(shù)，尤其是與集合相關(guān)的求和函

20、數(shù)SUM和循環(huán)函數(shù)FOR等。 上例中定義的目標(biāo)函數(shù)與quarters的元素?cái)?shù)目是 4或 1000并無具體的關(guān)系。約束的表示也類似。,（3）數(shù)據(jù)段(DATA)：以 “DATA:” 開始, “ENDDATA”結(jié)束，對(duì)集合的屬性(數(shù)組)輸入必要的常數(shù)數(shù)據(jù)。 格式為：“attribute(屬性) = value_list(常數(shù)列表);” 常數(shù)列表(value_list)中數(shù)據(jù)之間可以用逗號(hào)“,”分開，也可以用空格分開(回車等價(jià)于一個(gè)空格),如上面對(duì)DEM的賦值也可以寫成“DEM=40 60 75 25；”。,在LINGO模型中，如果想在運(yùn)行時(shí)才對(duì)參數(shù)賦值，可以在數(shù)據(jù)段使用輸入語句。但這僅能用于對(duì)單個(gè)變

21、量賦值，輸入語句格式為：“變量名 = ？；”。例如，上例中如果需要在求解模型時(shí)才給出初始庫(kù)存量(記為A)，則可以在模型中數(shù)據(jù)段寫上語句：”A = ?；” 在求解時(shí)LINDO系統(tǒng)給出提示界面，等待用戶輸入變量A的數(shù)值。當(dāng)然，此時(shí)的約束語句 INV(1)=10+RP(1)+OP(1)-DEM(1); 也應(yīng)該改寫成 INV(1)=A+RP(1)+OP(1)-DEM(1); 這樣，模型就可以計(jì)算任意初始庫(kù)存量(而不僅僅只能計(jì)算初始庫(kù)存量為10)的情況了。,（4）初始段(INIT)：以“INIT: ”開始， “ENDINIT”結(jié)束，對(duì)集合的屬性(數(shù)組)定義初值(因?yàn)榍蠼馑惴ㄒ话闶堑惴?，所以用戶如果?/p>

22、給出一個(gè)比較好的迭代初值，對(duì)提高算法的計(jì)算效果是有益的)。 如果有一個(gè)接近最優(yōu)解的初值，對(duì)LINGO求解模型是有幫助的。定義初值的格式為： “attribute（屬性） = value_list（常數(shù)列表）；” 這與數(shù)據(jù)段中的用法是類似的。 上例中沒有初始化部分，我們將在下一個(gè)例子中舉例說明。,（5）計(jì)算段(CALC)：以“CALC: ”開始， “ENDCALC”結(jié)束，對(duì)一些原始數(shù)據(jù)進(jìn)行計(jì)算處理。 在實(shí)際問題中，輸入的數(shù)據(jù)通常是原始數(shù)據(jù)，不一定能在模型中直接使用，可以在這個(gè)段對(duì)這些原始數(shù)據(jù)進(jìn)行一定的“預(yù)處理”，得到模型中真正需要的數(shù)據(jù)。,例如上例，如果希望得到全年的總需求和季度平均需求，可以增

23、加這個(gè)段： CALC: T_DEM = SUM(quarters: DEM); !總需求; A_DEM = T_DEM / size(quarters); !平均需求; ENDCALC 在計(jì)算段中也可以使用集合函數(shù)（其中函數(shù)size(quarters)表示集合quarters的元素個(gè)數(shù)，這里也就是4）。這時(shí)，變量T_DEM的值就是總需求，A_DEM的值就是平均需求（如果需要的話，這兩個(gè)變量就可以在程序的其它地方作為常數(shù)使用了）。 注：上面的兩個(gè)語句不能交換順序，因?yàn)橛?jì)算A_DEM必須要用到T_DEM的值。此外，在計(jì)算段中只能直接使用賦值語句，而不能包含需要經(jīng)過解方程或經(jīng)過求解優(yōu)化問題以后才能決

24、定的變量。,基本集合與派生集合,例3 建筑工地的位置(用平面坐標(biāo)a, b表示，距離單位：公里)及水泥日用量d(噸)下表給出。有兩個(gè)臨時(shí)料場(chǎng)位于P (5,1), Q (2, 7),日儲(chǔ)量各有20噸。從A, B兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使總的噸公里數(shù)最小。兩個(gè)新的料場(chǎng)應(yīng)建在何處，節(jié)省的噸公里數(shù)有多大？,建立模型,記工地的位置為 ，水泥日用量為 ；料場(chǎng)位置為 ，日儲(chǔ)量為 ；從料場(chǎng) 向工地 的運(yùn)送量為 。,使用現(xiàn)有臨時(shí)料場(chǎng)時(shí)，決策變量只有 （非負(fù)），所以這是LP模型；當(dāng)為新建料場(chǎng)選址時(shí)決策變量為 和 ，由于目標(biāo)函數(shù) 對(duì) 是非線性的，所以在新建料場(chǎng)時(shí)是NLP模型。先解NLP模型，而把現(xiàn)有臨時(shí)料場(chǎng)

25、的位置作為初始解告訴LINGO。,本例中集合的概念,利用集合的概念，可以定義需求點(diǎn)DEMAND和供應(yīng)點(diǎn)SUPPLY兩個(gè)集合，分別有6個(gè)和2個(gè)元素(下標(biāo))。但決策變量(運(yùn)送量) 與集合DEMAND和集合SUPPLY都有關(guān)系的。該如何定義這樣的屬性？,集合的屬性相當(dāng)于以集合的元素為下標(biāo)的數(shù)組。這里的 相當(dāng)于二維數(shù)組。它的兩個(gè)下標(biāo)分別來自集合DEMAND和SUPPLY，因此可以定義一個(gè)由二元對(duì)組成的新的集合，然后將 定義成這個(gè)新集合的屬性。,輸入程序,定義了三個(gè)集合，其中LINK在前兩個(gè)集合DEMAND 和SUPPLY的基礎(chǔ)上定義,LINGO建模語言也稱為矩陣生成器（MATRIX GENERATOR

26、）。類似DEMAND 和SUPPLY直接把元素列舉出來的集合，稱為基本集合(primary set),而把LINK這種基于其它集合而派生出來的二維或多維集合稱為派生集合(derived set)。由于是DEMAND 和SUPPLY生成了派生集合LINK，所以DEMAND 和SUPPLY 稱為L(zhǎng)INK的父集合。,表示集合LINK中的元素就是集合DEMAND 和SUPPLY的元素組合成的有序二元組， 從數(shù)學(xué)上看LINK是DEMAND 和SUPPLY的笛卡兒積，也就是說 LINK=(S，T)|S DEMAND，T SUPPLY 因此，其屬性C也就是一個(gè)6*2的矩陣（或者說是含有12個(gè)元素的二維數(shù)組）

27、。,輸入程序,初始段,INGO對(duì)數(shù)據(jù)是按列賦值的 語句的實(shí)際賦值順序是X=(5,2), Y=(1,7), 而不是X=(5,1), Y=（2,7) 等價(jià)寫法： “X=5,2； Y=1,7；”,同理，數(shù)據(jù)段中對(duì)常數(shù)數(shù)組A，B的賦值語句也可以寫成 A, B=1.25 1.25 8.75 0.75 0.5 4.75 5.75 5 3 6.5 7.25 7.75；,輸入程序,解答:運(yùn)行菜單命令“LINGO|Solve”,局部最優(yōu)解X(1)=7.249997， X(2)=5.695940，Y(1)=7.749998， Y(2)=4.928524，C（略）， 最小運(yùn)量=89.8835(噸公里)。,問題:最小

28、運(yùn)量89.8835是不是全局最優(yōu),用“LINGO|Options”菜單命令打開選項(xiàng)對(duì)話框，在“Global Solver”選項(xiàng)卡上選擇“Use Global Solver”, 激活全局最優(yōu)求解程序。,問題:最小運(yùn)量89.8835是不是全局最優(yōu),此時(shí)目標(biāo)函數(shù)值的下界（Obj Bound=85.2638）與目前得到的最好的可行解的目標(biāo)函數(shù)值（Best Obj=85.2661）相差已經(jīng)非常小，可以認(rèn)為已經(jīng)得到了全局最優(yōu)解。,計(jì)算結(jié)果,工地與料場(chǎng)示意圖 : “*”表示料場(chǎng)，“+”表示工地,可以認(rèn)為是模型的最后結(jié)果,附注：如果要把料廠P(5, 1), Q (2, 7)的位置看成是已知并且固定的，這時(shí)是L

29、P模型。只需要把初始段的“X Y =5，1，2，7；”語句移到數(shù)據(jù)段就可以了。此時(shí)，運(yùn)行結(jié)果告訴我們得到全局最優(yōu)解（變量C的取值這里略去），最小運(yùn)量136.2275(噸公里)。,稠密集合與稀疏集合,包含了兩個(gè)基本集合構(gòu)成的所有二元有序?qū)Φ呐缮戏Q為稠密集合(簡(jiǎn)稱稠集)。有時(shí)候，在實(shí)際問題中，一些屬性(數(shù)組) 只在笛卡兒積的一個(gè)真子集合上定義，這種派生集合稱為稀疏集合(簡(jiǎn)稱疏集)。,例4. (最短路問題) 在縱橫交錯(cuò)的公路網(wǎng)中，貨車司機(jī)希望找到一條從一個(gè)城市到另一個(gè)城市的最短路. 下圖表示的是公路網(wǎng), 節(jié)點(diǎn)表示貨車可以?？康某鞘?弧上的權(quán)表示兩個(gè)城市之間的距離(百公里). 那么,貨車從城市S出

30、發(fā)到達(dá)城市T,如何選擇行駛路線,使所經(jīng)過的路程最短?,分析,假設(shè)從S到T的最優(yōu)行駛路線 P 經(jīng)過城市C1, 則P中從S到C1的子路也一定是從S到C1的最優(yōu)行駛路線; 假設(shè) P 經(jīng)過城市C2, 則P中從S到C2的子路也一定是從S到C2的最優(yōu)行駛路線. 因此, 為得到從S到T的最優(yōu)行駛路線, 只需要先求出從S到Ck(k=1,2)的最優(yōu)行駛路線, 就可以方便地得到從S到T的最優(yōu)行駛路線. 同樣,為了求出從S到Ck(k=1,2)的最優(yōu)行駛路線, 只需要先求出從S到Bj(j=1,2)的最優(yōu)行駛路線; 為了求出從S到Bj(j=1,2)的最優(yōu)行駛路線, 只需要先求出從S到Ai (i=1,2,3)的最優(yōu)行駛路

31、線. 而S到Ai(i=1,2,3)的最優(yōu)行駛路線是很容易得到的(實(shí)際上, 此例中S到Ai(i=1,2,3)只有唯一的道路),分析,此例中可把從S到T的行駛過程分成4個(gè)階段,即 SAi (i=1,2或3), Ai Bj(j=1或2), Bj Ck(k=1或2), Ck T. 記d(Y,X)為城市Y與城市X之間的直接距離(若這兩個(gè)城市之間沒有道路直接相連，則可以認(rèn)為直接距離為)，用L(X)表示城市S到城市X的最優(yōu)行駛路線的路長(zhǎng):,本例的計(jì)算,所以, 從S到T的最優(yōu)行駛路線的路長(zhǎng)為20. 進(jìn)一步分析以上求解過程, 可以得到從S到T的最優(yōu)行駛路線為 S A3 B2 C1 T.,這種計(jì)算方法在數(shù)學(xué)上稱為

32、動(dòng)態(tài)規(guī)劃(Dynamic Programming),本例的LINGO求解,“CITIES”(城市):一個(gè)基本集合(元素通過枚舉給出),L:CITIES對(duì)應(yīng)的屬性變量(我們要求的最短路長(zhǎng)),“ROADS”(道路):由CITIES導(dǎo)出的一個(gè)派生集合(請(qǐng)?zhí)貏e注意其用法),由于只有一部分城市之間有道路相連，所以不應(yīng)該把它定義成稠密集合，將其元素通過枚舉給出，這就是一個(gè)稀疏集合。,D:稀疏集合ROADS對(duì)應(yīng)的屬性變量(給定的距離),本例的LINGO求解,從模型中還可以看出：這個(gè)LINGO程序可以沒有目標(biāo)函數(shù)，這在LINGO中，可以用來找可行解(解方程組和不等式組)。,在數(shù)據(jù)段對(duì)L進(jìn)行賦值，只有L(S)=

33、0已知，后面的值為空(但位置必須留出來，即逗號(hào)“，”一個(gè)也不能少，否則會(huì)出錯(cuò))。如果這個(gè)語句直接寫成“L=0；”，語法上看也是對(duì)的，但其含義是L所有元素的取值全部為0，所以也會(huì)與題意不符。,本例的LINGO求解,雖然集合CITIES中的元素不是數(shù)字，但當(dāng)它以CITIES(I)的形式出現(xiàn)在循環(huán)中時(shí)，引用下標(biāo)I卻實(shí)際上仍是正整數(shù)，也就是說I指的正是元素在集合中的位置(順序)，一般稱為元素的索引(INDEX)。,在for循環(huán)中的過濾條件里用了一個(gè)函數(shù)“index”, 其作用是返回一個(gè)元素在集合中的索引值，這里index(S)=1(即元素S在集合中的索引值為1)，所以邏輯關(guān)系式“I#GT#index(

34、S)”可以直接等價(jià)地寫成“I#GT#1” 。這里index(S)實(shí)際上還是index(CITIES,S)的簡(jiǎn)寫，即返回S在集合CITIES中的索引值。,本例的LINGO求解結(jié)果,從S到T的最優(yōu)行駛路線的路長(zhǎng)為20(進(jìn)一步分析，可以得到最優(yōu)行駛路線為S A3 B2 C1 T)。,本例中定義稀疏集合ROADS的方法是將其元素通過枚舉給出，有時(shí)如果元素比較多，用起來不方便。另一種定義稀疏集合的方法是“元素過濾”法，能夠從笛卡兒積中系統(tǒng)地過濾下來一些真正的元素。,例5. 某班8名同學(xué)準(zhǔn)備分成4個(gè)調(diào)查隊(duì)(每隊(duì)兩人)前往4個(gè)地區(qū)進(jìn)行社會(huì)調(diào)查。這8名同學(xué)兩兩之間組隊(duì)的效率如下表所示(由于對(duì)稱性，只列出了嚴(yán)格

35、上三角部分)，問如何組隊(duì)可以使總效率最高？,分析,這是一個(gè)匹配（MATCHING）問題。把上表的效率矩陣記為BENEFIT(由于對(duì)稱性，這個(gè)矩陣只有嚴(yán)格上三角部分共28個(gè)數(shù)取非零值)。 用MATCH（Si，Sj）=1表示同學(xué)Si，Sj組成一隊(duì) ，而MATCH（Si，Sj）=0表示Si，Sj不組隊(duì)。由于對(duì)稱性，只需考慮i=，大于等于) (在優(yōu)化模型中約束一般沒有嚴(yán)格小于、嚴(yán)格大于關(guān)系),運(yùn)算符的優(yōu)先級(jí),基本的數(shù)學(xué)函數(shù),在LINGO中建立優(yōu)化模型時(shí)可以引用大量的內(nèi)部函數(shù),這些函數(shù)以” 打頭。LINGO中包括相當(dāng)豐富的數(shù)學(xué)函數(shù),這些函數(shù)的用法非常簡(jiǎn)單,下面一一列出。,ABS(X)：絕對(duì)值函數(shù)，返回X

36、的絕對(duì)值。 COS(X)：余弦函數(shù)，返回X的余弦值（X的單位是弧度）。 EXP(X)：指數(shù)函數(shù)，返回,FLOOR(X)：取整函數(shù)，返回X的整數(shù)部分(向最靠近0的方向取整)。 LGM(X) ：返回X的伽瑪(gamma)函數(shù)的自然對(duì)數(shù)值(當(dāng)X為整數(shù)時(shí)LGM(X) = LOG(X-1)??；當(dāng)X不為整數(shù)時(shí)，采用線性插值得到結(jié)果)。 LOG(X)：自然對(duì)數(shù)函數(shù)，返回X的自然對(duì)數(shù)值。,的值(其中e=2.718281.)。,基本的數(shù)學(xué)函數(shù),SIGN(X)：符號(hào)函數(shù)，返回X的符號(hào)值（X = 0時(shí)返回+1）。 SIN(X)：正弦函數(shù)，返回X的正弦值（X的單位是弧度）。 SMAX(list)：最大值函數(shù)，返回一列

37、數(shù)(list)的最大值。 SMIN(list)：最小值函數(shù)，返回一列數(shù)(list)的最小值。 SQR(X)：平方函數(shù)，返回X的平方（即X*X）的值。 SQRT(X)：開平方函數(shù)，返回X的正的平方根的值。 TAN(X)：正切函數(shù)，返回X的正切值（X的單位是弧度）。,集合循環(huán)函數(shù),集合上的元素(下標(biāo))進(jìn)行循環(huán)操作的函數(shù), 一般用法如下: function(setname ( set_index_list) | condition : expression_list); 其中：,function 集合函數(shù)名,FOR、MAX、MIN、SUM之一； Setname 集合名； set_index_list

38、 集合索引列表(不需使用索引時(shí)可以省略)； Condition 用邏輯表達(dá)式描述的過濾條件(通常含有索引，無條件時(shí)可以省略)； expression_list 一個(gè)表達(dá)式(對(duì)FOR函數(shù)，可以是一組表達(dá)式。,集合循環(huán)函數(shù),四個(gè)集合函數(shù)名的含義: FOR(集合元素的循環(huán)函數(shù))： 對(duì)集合setname的每個(gè)元素獨(dú)立地生成表達(dá)式，表達(dá)式由expression_list描述（通常是優(yōu)化問題的約束）。 MAX（集合屬性的最大值函數(shù)）：返回集合setname上的表達(dá)式的最大值。 MIN（集合屬性的最小值函數(shù)）：返回集合setname上的表達(dá)式的最小值。 SUM(集合屬性的求和函數(shù)):返回集合setname上

39、的表達(dá)式的和。,集合操作函數(shù),INDEX( set_name, primitive_set_element) 給出元素primitive_set_element在集合set_name中的索引值(即按定義集合時(shí)元素出現(xiàn)順序的位置編號(hào))。省略set_name，LINGO按模型中定義的集合順序找到第一個(gè)含有該元素的集合，并返回索引值。如果沒有找到該元素，則出錯(cuò)。 注: Set_name的索引值是正整數(shù)且只能位于1和元素個(gè)數(shù)之間。例:定義一個(gè)女孩姓名集合(GIRLS)和男孩姓名集合(BOYS) ： SETS: GIRLS /DEBBIE, SUE, ALICE/; BOYS /BOB, JOE, SU

40、E, FRED/; ENDSETS 都有SUE, GIRLS在BOYS前定義,調(diào)用INDEX(SUE)將返2，相當(dāng)于INDEX(GIRLS,SUE) 。要找男孩中名為SUE的小孩的索引，應(yīng)該使用INDEX(BOYS, SUE)，返3。,集合操作函數(shù),IN( set_name, primitive_index_1 , primitive_index_2 .) 判斷一個(gè)集合中是否含有某個(gè)索引值。如果集合set_name中包含由索引primitive_index_1 , primitive_index_2 .所對(duì)應(yīng)元素，則返回1(邏輯值“真”)，否則返回0(邏輯值“假”)。索引用“ ENDSETS,

41、如果集合C是由集合A，B派生的，例如： SETS: A / 1.3/:; B / X Y Z/:; C( A, B) / 1,X 1,Z 2,Y 3,X/:; ENDSETS 判斷C中是否包含元素（2，Y），則可以利用以下語句： X = IN( C, INDEX( A, 2), INDEX( B, Y); 對(duì)本例，結(jié)果是X=1（真）。 注：X既是集合B的元素，又對(duì)X賦值1，在LINGO中這種表達(dá)是允許的，因?yàn)榍罢呤羌系脑?，后者是變量，邏輯上沒有關(guān)系(除了同名外),所以不會(huì)出現(xiàn)混淆。,集合操作函數(shù),IN( set_name, primitive_index_1 , primitive_ind

42、ex_2 .),WRAP(I,N) 此函數(shù)對(duì)N1無定義 當(dāng)I位于區(qū)間1, N內(nèi)時(shí)直接返回I；一般地，返回 J = I - K *N , 其中J位于區(qū)間1, N ， K為整數(shù)。即 WRAP(I,N)= MOD（I，N）（此函數(shù)8.0版本沒有）。 但當(dāng)MOD(I,N)=0時(shí)WRAP(I,N)=N. 此函數(shù)可以用來防止集合的索引值越界。 用戶在編寫LINGO程序時(shí)，應(yīng)注意避免LINGO模型求解時(shí)出現(xiàn)集合的索引值越界的錯(cuò)誤。,集合操作函數(shù),SIZE (set_name) 返回?cái)?shù)據(jù)集set_name中包含元素的個(gè)數(shù)。,變量定界函數(shù),對(duì)變量的取值范圍附加限制，共有以下四種： BND(L, X, U) ：限

43、制L = X 1的正整數(shù)）：N點(diǎn)求解,5. LINGO命令窗口,LINGO命令行 模式,LINGO有兩種命令模式：Windows模式, 命令行 (Command-Line) 模式。這里簡(jiǎn)單介紹一下命令行模式下的主要行命令。 可以通過菜單命令“Window|Command Window （Ctrl+1）”打開命令窗口，在命令窗口下操作。 在命令窗口下的提示符 “：”后面鍵入 COMMANDS（COM）可以看到LINGO的所有行命令,部分行命令的基本功能,在LINGO中不再支持LINDO的部分行命令，如DATE，TABL，SDBC，F(xiàn)BS，F(xiàn)PUN，SMPN等。LINGO也增加了一些與LINDO不同的命令（見下表）。,部分行命令的基本功能,通過文件輸入輸出數(shù)據(jù),通過文件輸入輸出數(shù)據(jù)可以將LINGO程序和程序處理的數(shù)據(jù)分離開來。 “程序和數(shù)據(jù)的分離”是結(jié)構(gòu)化程序設(shè)計(jì)、面向?qū)ο缶幊痰幕疽蟆?實(shí)際問題通常需要處理大規(guī)模的實(shí)際數(shù)據(jù)，而這些數(shù)據(jù)通常都是在其它應(yīng)用系統(tǒng)中生成的，或者已經(jīng)