Lingo的基本使用方法（課堂PPT）

1、.1LINGOLINGO軟件的基本使用方法軟件的基本使用方法.2LINGO軟件的功能與特點(diǎn)LINGO模型的功能 集成了線性(非線性) / 連續(xù)(整數(shù)) 優(yōu)化功能 具有多點(diǎn)搜索 / 全局優(yōu)化功能 提供了靈活的編程語言(矩陣生成器)，可方便地輸入模型 提供與其他數(shù)據(jù)文件的接口 提供與其他編程語言的接口 LINDO API 可用于自主開發(fā) 運(yùn)行速度較快.3 最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社會(huì)生活中經(jīng)常遇到的問題, 如:優(yōu)化模型和算法的重要意義結(jié)構(gòu)設(shè)計(jì)資源分配生產(chǎn)計(jì)劃運(yùn)輸方案 解決優(yōu)化問題的手段 經(jīng)驗(yàn)積累，主觀判斷 作試驗(yàn)，比優(yōu)劣 建立數(shù)學(xué)模型，求解最優(yōu)策略最優(yōu)化: 在一定條件下，尋求使目標(biāo)最

2、大(小)的決策 .4 LP QP NLP IP 全局優(yōu)化(選) ILP IQP INLP LINGOLINGO軟件的求解過程軟件的求解過程 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) (選) .5建模時(shí)需要注意的幾個(gè)基本問題建模時(shí)需要注意的幾個(gè)基本問題 1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù) 如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五

3、入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù) （如x/y 5 改為x5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng) (如小于103).6內(nèi)容提要內(nèi)容提要LINGO入門入門2.在在LINGO中使用集合中使用集合3. 運(yùn)算符和函數(shù)運(yùn)算符和函數(shù)4. LINGO的主要菜單命令的主要菜單命令5. LINGO命令窗口命令窗口 6.習(xí)題.71. LINGO入門入門LINGO入門入門2.在在LINGO中使用集合中使用集合3. 運(yùn)算符和函數(shù)運(yùn)算符和函數(shù)4. LINGO的主要菜單命令的主要菜單命令5. LINGO命令窗口命令窗口 6.習(xí)題.8LINGO

4、軟件的主要特色軟件的主要特色兩種命令模式兩種命令模式Windows模式模式： 通過下拉式菜單命令驅(qū)動(dòng)通過下拉式菜單命令驅(qū)動(dòng)LINGO運(yùn)行（多數(shù)運(yùn)行（多數(shù)菜單命令有快捷鍵，常用的菜單命令有快捷按鈕），圖形界菜單命令有快捷鍵，常用的菜單命令有快捷按鈕），圖形界面，使用方便；面，使用方便；命令行命令行 模式：僅在命令窗口模式：僅在命令窗口(Command Window)下操作，通下操作，通過輸入行命令驅(qū)動(dòng)過輸入行命令驅(qū)動(dòng)LINGO運(yùn)行運(yùn)行 。(這里主要介紹這種模式這里主要介紹這種模式).9LINGO 11.0功能增強(qiáng)，性能穩(wěn)定，解答結(jié)果可靠。功能增強(qiáng)，性能穩(wěn)定，解答結(jié)果可靠。LINGO 軟軟件主要具

5、有兩大優(yōu)點(diǎn)件主要具有兩大優(yōu)點(diǎn):內(nèi)置建模語言，允許以簡(jiǎn)練、直觀的方式描述較大規(guī)模的優(yōu)化內(nèi)置建模語言，允許以簡(jiǎn)練、直觀的方式描述較大規(guī)模的優(yōu)化問題，所需的數(shù)據(jù)可以以一定格式保存在獨(dú)立的文件中。問題，所需的數(shù)據(jù)可以以一定格式保存在獨(dú)立的文件中?？捎糜谇蠼饨?jīng)典的數(shù)學(xué)規(guī)劃問題，包括非線性整數(shù)規(guī)劃問題可用于求解經(jīng)典的數(shù)學(xué)規(guī)劃問題，包括非線性整數(shù)規(guī)劃問題;.10LINGOLINGO的界面的界面LINGO軟件的主窗口（用戶軟件的主窗口（用戶界面），所有其他窗口都界面），所有其他窗口都在這個(gè)窗口之內(nèi)。在這個(gè)窗口之內(nèi)。 模型窗口（模型窗口（Model Window），用于輸入），用于輸入LINGO優(yōu)化模型（即優(yōu)化

6、模型（即LINGO程序）。程序）。 狀態(tài)行（最左邊顯示狀態(tài)行（最左邊顯示“Ready”，表示，表示 “準(zhǔn)備就緒準(zhǔn)備就緒”）當(dāng)前時(shí)間當(dāng)前時(shí)間 當(dāng)前光標(biāo)的當(dāng)前光標(biāo)的位置位置 .11一個(gè)簡(jiǎn)單的一個(gè)簡(jiǎn)單的LINGO程序程序例例1 直接用LINGO來解如下二次規(guī)劃問題： 40,322100. .123 . 02779821212122212121為整數(shù)xxxxxxtsxxxxxxMax輸入窗口如下：輸入窗口如下：.12程序語句輸入的備注：程序語句輸入的備注：LINGO總是根據(jù)總是根據(jù)“MAX=”或或“MIN=”尋找目標(biāo)函數(shù)，而除注尋找目標(biāo)函數(shù)，而除注釋語句和釋語句和TITLE語句外的其他語句都是約束條件

7、，因此語句的語句外的其他語句都是約束條件，因此語句的順序并不重要順序并不重要 。限定變量取整數(shù)值的語句為限定變量取整數(shù)值的語句為“GIN(X1)”和和“GIN(X2)”，不，不可以寫成可以寫成“GIN(2)”，否則，否則LINGO將把這個(gè)模型看成沒有整將把這個(gè)模型看成沒有整數(shù)變量。數(shù)變量。LINGO中函數(shù)一律需要以中函數(shù)一律需要以“”開頭，其中整型變量函數(shù)（開頭，其中整型變量函數(shù)（BIN、GIN）和上下界限定函數(shù)（）和上下界限定函數(shù)（FREE、SUB、SLB）與）與LINDO中的命令類似。而且中的命令類似。而且0/1變量函數(shù)是變量函數(shù)是BIN函函數(shù)。數(shù)。.13輸出結(jié)果：輸出結(jié)果：運(yùn)行菜單命令運(yùn)

8、行菜單命令“LINGO|Solve” 最優(yōu)整數(shù)解最優(yōu)整數(shù)解X=(35，65)最大利潤(rùn)最大利潤(rùn)=11077.5 .14輸出結(jié)果備注：輸出結(jié)果備注：通過菜單 “WINDOW| Status Window”看到狀態(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)解。.15運(yùn)行狀態(tài)窗口運(yùn)行狀態(tài)窗口Variables（變量數(shù)量）：（變量數(shù)量）： 變量總數(shù)（變量總數(shù)（To

9、tal）、）、 非線性變量數(shù)（非線性變量數(shù)（Nonlinear）、）、 整數(shù)變量數(shù)（整數(shù)變量數(shù)（Integer）。）。Constraints（約束數(shù)量）：（約束數(shù)量）： 約束總數(shù)（約束總數(shù)（Total）、）、 非線性約束個(gè)數(shù)非線性約束個(gè)數(shù)(Nonlinear)。Nonzeros（非零系數(shù)數(shù)量）：（非零系數(shù)數(shù)量）： 總數(shù)（總數(shù)（Total）、）、 非線性項(xiàng)系數(shù)個(gè)數(shù)非線性項(xiàng)系數(shù)個(gè)數(shù)(Nonlinear)。Generator Memory Used (K) (內(nèi)存使用內(nèi)存使用量量)Elapsed Runtime (hh:mm:ss)（求（求解花費(fèi)的時(shí)間）解花費(fèi)的時(shí)間） .16運(yùn)行狀態(tài)窗口運(yùn)行狀態(tài)窗口

10、求解求解器器(求求解程解程序序)狀狀態(tài)框態(tài)框當(dāng)前模型的類型當(dāng)前模型的類型 :LP，QP，ILP，IQP，PILP， PIQP，NLP，INLP，PINLP （以（以I開頭表示開頭表示IP，以，以PI開頭表示開頭表示PIP） 當(dāng)前解的狀態(tài)當(dāng)前解的狀態(tài) : Global Optimum, Local Optimum, Feasible, Infeasible“(不可行不可行), Unbounded“(無界無界), Interrupted“(中斷中斷), Undetermined“(未確定未確定) 解的目標(biāo)函數(shù)值解的目標(biāo)函數(shù)值 當(dāng)前約束不滿足的總量當(dāng)前約束不滿足的總量(不是不不是不滿足的約束的個(gè)數(shù)滿

11、足的約束的個(gè)數(shù)):實(shí)數(shù)（即使實(shí)數(shù)（即使該值該值=0，當(dāng)前解也可能不可行，當(dāng)前解也可能不可行，因?yàn)檫@個(gè)量中沒有考慮用上下界因?yàn)檫@個(gè)量中沒有考慮用上下界命令形式給出的約束）命令形式給出的約束） 目前為止的目前為止的迭代次數(shù)迭代次數(shù) .17運(yùn)行狀態(tài)窗口運(yùn)行狀態(tài)窗口擴(kuò)展擴(kuò)展的求的求解器解器(求解求解程序程序)狀態(tài)狀態(tài)框框使用的特殊求解程序使用的特殊求解程序 :B-and-B (分枝定界算法分枝定界算法)Global (全局最優(yōu)求解程序全局最優(yōu)求解程序)Multistart(用多個(gè)初始點(diǎn)求解的程序用多個(gè)初始點(diǎn)求解的程序) 目前為止找到的可行目前為止找到的可行解的最佳目標(biāo)函數(shù)值解的最佳目標(biāo)函數(shù)值 目標(biāo)函數(shù)

12、值的界目標(biāo)函數(shù)值的界 特殊求解程序當(dāng)前運(yùn)行步數(shù)：特殊求解程序當(dāng)前運(yùn)行步數(shù)：分枝數(shù)分枝數(shù)(對(duì)對(duì)B-and-B程序程序)；子問題數(shù)子問題數(shù)(對(duì)對(duì)Global程序程序)；初始點(diǎn)數(shù)初始點(diǎn)數(shù)(對(duì)對(duì)Multistart程序程序)有效步數(shù)有效步數(shù) .18注：凡是可以從一個(gè)約束直接解出變量取值時(shí)，這個(gè)變量就不注：凡是可以從一個(gè)約束直接解出變量取值時(shí)，這個(gè)變量就不認(rèn)為是決策變量而是固定變量，不列入統(tǒng)計(jì)中；只含有固定變認(rèn)為是決策變量而是固定變量，不列入統(tǒng)計(jì)中；只含有固定變量的約束也不列入約束統(tǒng)計(jì)中。量的約束也不列入約束統(tǒng)計(jì)中。運(yùn)行狀態(tài)窗口運(yùn)行狀態(tài)窗口.19一個(gè)簡(jiǎn)單的一個(gè)簡(jiǎn)單的LINGO程序程序LINGO的基本用法

13、的幾點(diǎn)注意事項(xiàng)的基本用法的幾點(diǎn)注意事項(xiàng) LINGO中不區(qū)分大小寫字母；變量和行名可以超過8個(gè)字符，但不能超過32個(gè)字符，且必須以字母開頭。用LINGO解優(yōu)化模型時(shí)已假定所有變量非負(fù)(除非用限定變量取值范圍的函數(shù)free或sub或slb另行說明)。變量可以放在約束條件的右端(同時(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)開始的是說明語句(說明語句也

14、需要以分號(hào)結(jié)束)。.20LINGOLINGO的文件類型的文件類型.LG4：LINGO格式的模型文件，保存了模型窗口中所能夠看到格式的模型文件，保存了模型窗口中所能夠看到的所有文本和其他對(duì)象及其格式信息；的所有文本和其他對(duì)象及其格式信息；.LNG：文本格式的模型文件，不保存模型中的格式信息（如字：文本格式的模型文件，不保存模型中的格式信息（如字體、顏色、嵌入對(duì)象等）；體、顏色、嵌入對(duì)象等）；.LDT：LINGO數(shù)據(jù)文件；數(shù)據(jù)文件；.LTF：LINGO命令腳本文件；命令腳本文件；.LGR：LINGO報(bào)告文件；報(bào)告文件；.LTX： LINDO格式的模型文件；格式的模型文件；.MPS：表示：表示MPS

15、（數(shù)學(xué)規(guī)劃系統(tǒng)）格式的模型文件。（數(shù)學(xué)規(guī)劃系統(tǒng)）格式的模型文件。除除“LG4”文件外，文件外，另外幾種格式的文件另外幾種格式的文件都是普通的文本文件都是普通的文本文件，可以用任何文本編，可以用任何文本編輯器打開和編輯。輯器打開和編輯。.212.在在LINGO中使用集合中使用集合 LINGO入門入門2.在在LINGO中使用集合中使用集合3. 運(yùn)算符和函數(shù)運(yùn)算符和函數(shù)4. LINGO的主要菜單命令的主要菜單命令5. LINGO命令窗口命令窗口 6.習(xí)題.22集合的基本用法和集合的基本用法和LINGO模型的基本要素模型的基本要素 理解理解LINGO建模語言最重要的是理解集合（建模語言最重要的是理解集

16、合（Set）及其屬性（）及其屬性（Attribute）的概念。）的概念。 例例2 SAILCO公司需要決定下四個(gè)季度的帆船生產(chǎn)量。下四個(gè)季公司需要決定下四個(gè)季度的帆船生產(chǎn)量。下四個(gè)季度的帆船需求量分別是度的帆船需求量分別是40條，條，60條，條，75條，條，25條，這些需求必須條，這些需求必須按時(shí)滿足。每個(gè)季度正常的生產(chǎn)能力是按時(shí)滿足。每個(gè)季度正常的生產(chǎn)能力是40條帆船，每條船的生產(chǎn)條帆船，每條船的生產(chǎn)費(fèi)用為費(fèi)用為400美元。如果加班生產(chǎn)，每條船的生產(chǎn)費(fèi)用為美元。如果加班生產(chǎn)，每條船的生產(chǎn)費(fèi)用為450美元。美元。每個(gè)季度末，每條船的庫存費(fèi)用為每個(gè)季度末，每條船的庫存費(fèi)用為20美元。假定生產(chǎn)提前

17、期為美元。假定生產(chǎn)提前期為0，初始庫存為，初始庫存為10條船。如何安排生產(chǎn)可使總費(fèi)用最??？條船。如何安排生產(chǎn)可使總費(fèi)用最??？用用DEM,RP,OP,INV分別表示需求量、正常生產(chǎn)的產(chǎn)量、加班生分別表示需求量、正常生產(chǎn)的產(chǎn)量、加班生產(chǎn)的產(chǎn)量、庫存量，則產(chǎn)的產(chǎn)量、庫存量，則DEM,RP,OP,INV對(duì)每個(gè)季度都應(yīng)該有一對(duì)每個(gè)季度都應(yīng)該有一個(gè)對(duì)應(yīng)的值，也就說他們都應(yīng)該是一個(gè)由個(gè)對(duì)應(yīng)的值，也就說他們都應(yīng)該是一個(gè)由4個(gè)元素組成的數(shù)組，個(gè)元素組成的數(shù)組，其中其中DEM是已知的，而是已知的，而RP,OP,INV是未知數(shù)。是未知數(shù)。 .23問題的模型問題的模型( (可以看出是可以看出是LP模型模型 )目標(biāo)函數(shù)

18、是所有費(fèi)用的和目標(biāo)函數(shù)是所有費(fèi)用的和4, 3 , 2, 1)(20)(450)(400MINIIINVIOPIRP 約束條件主要有兩個(gè)：約束條件主要有兩個(gè)：1）能力限制：）能力限制：4 , 3 , 2 , 1,40)(RPII2）產(chǎn)品數(shù)量的平衡方程：）產(chǎn)品數(shù)量的平衡方程：4 , 3 , 2 , 1),()()() 1()(IIDEMIOPIRPIINVIINV10)0(INV加上變量的非負(fù)約束加上變量的非負(fù)約束.24注：注：LINGO中沒有數(shù)組，只能對(duì)每個(gè)季度分別定義變量，如正常產(chǎn)量就要有RP1，RP2，RP3，RP4 4個(gè)變量等。寫起來就比較麻煩，尤其是更多(如1000個(gè)季度)的時(shí)候。 記四

19、個(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稱為該集合的屬性(即定義在該集合上的屬性)。.25QUARTERS集合的屬性DEM RPOP INVQUARTERS集合2341 集合及其屬性集合及其屬性 .26集合元素及集合的屬性確定的所有變量集合元素及集合的屬性確定的所有變量集合QUARTERS的元素1234定

20、義在集合QUARTERS上的屬性DEM DEM(1) DEM(2) DEM(3) DEM(4)RPRP(1)RP(2)RP(3)RP(4)OPOP(1)OP(2)OP(3)OP(4)INVINV(1)INV(2)INV(3)INV(4).27LINGO中定義集合及其屬性中定義集合及其屬性 LP模型在模型在LINGO中的一個(gè)典型輸入方式中的一個(gè)典型輸入方式 以以“MODEL：”開始開始 以以“END”結(jié)結(jié)束束集合定義部分從集合定義部分從(“SETS：”到到“ENDSETS” )：定義集合及其屬性定義集合及其屬性數(shù)據(jù)輸入部分從數(shù)據(jù)輸入部分從(“DATA：”到到“ENDDATA” )給出優(yōu)化目標(biāo)給出

21、優(yōu)化目標(biāo)和約束和約束 .28目標(biāo)函數(shù)的定義方式目標(biāo)函數(shù)的定義方式SUM(集合（下標(biāo)）：關(guān)于集合的屬性的表達(dá)式集合（下標(biāo)）：關(guān)于集合的屬性的表達(dá)式)對(duì)語句中冒號(hào)對(duì)語句中冒號(hào)“：”后面的表達(dá)式，按照后面的表達(dá)式，按照“：”前面的集合前面的集合指定的下標(biāo)（元素）進(jìn)行求和。指定的下標(biāo)（元素）進(jìn)行求和。 本例中目標(biāo)函數(shù)也可以等價(jià)地寫成本例中目標(biāo)函數(shù)也可以等價(jià)地寫成SUM(QUARTERS(i): 400*RP(i) +450*OP(i) +20*INV(i) )，“SUM”相當(dāng)于求和符號(hào)相當(dāng)于求和符號(hào)“”，“QUARTERS(i)”相當(dāng)于相當(dāng)于“iQUARTERS”的含義。的含義。由于本例中目標(biāo)函數(shù)對(duì)集

22、合由于本例中目標(biāo)函數(shù)對(duì)集合QUARTERS的所有元素的所有元素(下標(biāo)下標(biāo)) 都要都要求和，所以可以將下標(biāo)求和，所以可以將下標(biāo)i省去。省去。 .29約束的定義方式約束的定義方式循環(huán)函數(shù)循環(huán)函數(shù)FOR(集合集合(下標(biāo)下標(biāo))：關(guān)于集合的屬性的約束關(guān)系式：關(guān)于集合的屬性的約束關(guān)系式) 對(duì)冒號(hào)對(duì)冒號(hào)“：”前面的集合的每個(gè)元素（下標(biāo)），冒號(hào)前面的集合的每個(gè)元素（下標(biāo)），冒號(hào)“：”后面后面的約束關(guān)系式都要成立的約束關(guān)系式都要成立 本例中，每個(gè)季度正常的生產(chǎn)能力是本例中，每個(gè)季度正常的生產(chǎn)能力是40條帆船，這正是語句條帆船，這正是語句“FOR(QUARTERS(I):RP(I)40);”的含義。的含義。由于對(duì)

23、所有元素由于對(duì)所有元素(下標(biāo)下標(biāo)I),約束的形式是一樣的，所以也可以像上約束的形式是一樣的，所以也可以像上面定義目標(biāo)函數(shù)時(shí)一樣，將下標(biāo)面定義目標(biāo)函數(shù)時(shí)一樣，將下標(biāo)i省去，省去，這個(gè)語句可以簡(jiǎn)化成這個(gè)語句可以簡(jiǎn)化成“FOR(QUARTERS:RP1；“#GT#”是邏輯運(yùn)算符號(hào)，意思是是邏輯運(yùn)算符號(hào)，意思是“大于（大于（Greater Than的字首字母縮寫的字首字母縮寫）” 。約束的定義方式約束的定義方式.31問題的求解：運(yùn)行菜單命令問題的求解：運(yùn)行菜單命令“LINGO|Solve” 全局最優(yōu)解全局最優(yōu)解RP=(40,40,40,25),OP=(0,10,35,0) 最小成本最小成本=78450

24、 .32注：由于輸入中沒有給出行名，所以行名是系統(tǒng)自動(dòng)按照行號(hào)注：由于輸入中沒有給出行名，所以行名是系統(tǒng)自動(dòng)按照行號(hào)1-9生成的。生成的。 選擇菜單命令選擇菜單命令“LINGO|Generate|Disply model（Ctrl+G）”，可以得到展開形式的模型，可以得到展開形式的模型(如圖如圖)，可以看到完整的模型，也能，可以看到完整的模型，也能確定行號(hào)確定行號(hào)(行號(hào)放在方括號(hào)行號(hào)放在方括號(hào)“ ”中，且數(shù)字前面帶有下劃線中，且數(shù)字前面帶有下劃線“_”)。 最好在輸入模型時(shí)用戶主動(dòng)設(shè)定約束的行名最好在輸入模型時(shí)用戶主動(dòng)設(shè)定約束的行名(即約束名即約束名)，使程，使程序清晰些。單一約束的行名設(shè)置方

25、法就是將行名放在方括號(hào)序清晰些。單一約束的行名設(shè)置方法就是將行名放在方括號(hào)“ ”中，置于約束之前。中，置于約束之前。 后面將結(jié)合具體例子介紹在使用集合的情況下如何設(shè)置行名。后面將結(jié)合具體例子介紹在使用集合的情況下如何設(shè)置行名。 .33小結(jié)小結(jié):LINGO模型最基本的組成要素模型最基本的組成要素 一般來說，一般來說， LINGO中建立的優(yōu)化模型可以由五個(gè)部分組成，或中建立的優(yōu)化模型可以由五個(gè)部分組成，或稱為五稱為五“段段”（SECTION）：）：（1 1）集合段（）集合段（SETSSETS）：）：以以“ SETS:” 開始，開始， “ENDSETS”結(jié)結(jié)束，定義必要的集合變量（束，定義必要的集合

26、變量（SET）及其元素（）及其元素（MEMBER，含，含義類似于數(shù)組的下標(biāo)）和屬性（義類似于數(shù)組的下標(biāo)）和屬性（ATTRIBUTE，含義類似于數(shù)，含義類似于數(shù)組）。組）。如上例中定義了集合如上例中定義了集合quarters(含義是季節(jié)含義是季節(jié))，它包含四個(gè)元素即四個(gè)季節(jié)指標(biāo)，它包含四個(gè)元素即四個(gè)季節(jié)指標(biāo)(1,2,3,4)，每個(gè)季節(jié)都有需求，每個(gè)季節(jié)都有需求(DEM)、正常生產(chǎn)量、正常生產(chǎn)量(RP)、加班生產(chǎn)量、加班生產(chǎn)量(OP)、庫存、庫存量量(INV)等屬性等屬性(相當(dāng)于數(shù)組，數(shù)組下標(biāo)由相當(dāng)于數(shù)組，數(shù)組下標(biāo)由quarters元素決定元素決定)。一旦這樣的定義。一旦這樣的定義建立起來，如果建

27、立起來，如果quarters的數(shù)量不是的數(shù)量不是4而是而是1000,只需擴(kuò)展其元素為只需擴(kuò)展其元素為1,2,.,1000,每每個(gè)季節(jié)仍然都有個(gè)季節(jié)仍然都有DEM,RP,OP,INV這樣的屬性這樣的屬性(這些量的具體數(shù)值如果是常量，這些量的具體數(shù)值如果是常量，則可在數(shù)據(jù)段輸入；如果是未知數(shù)，則可不則可在數(shù)據(jù)段輸入；如果是未知數(shù)，則可不 在初始段輸入初值在初始段輸入初值)。當(dāng)。當(dāng)quarters的的數(shù)量不是數(shù)量不是4而是而是1000時(shí)，沒有必要把時(shí)，沒有必要把1,2，.,1000全部一個(gè)一個(gè)列出來，而是可全部一個(gè)一個(gè)列出來，而是可以如下定義以如下定義quarters集合：集合：“quarters/

28、1.1000/:DEM,RP,OP,INV;” ,“1.1000”的的意思就是從意思就是從1到到1000的所有整數(shù)。的所有整數(shù)。.34（2 2）目標(biāo)與約束段）目標(biāo)與約束段：目標(biāo)函數(shù)、約束條件等，沒有段的開始和：目標(biāo)函數(shù)、約束條件等，沒有段的開始和結(jié)束標(biāo)記，因此實(shí)際上就是除其它四個(gè)段結(jié)束標(biāo)記，因此實(shí)際上就是除其它四個(gè)段(都有明確的段標(biāo)記都有明確的段標(biāo)記)外的外的LINGO模型。模型。這里一般要用到這里一般要用到LINGO的內(nèi)部函數(shù)，尤其是與集合相關(guān)的求和的內(nèi)部函數(shù)，尤其是與集合相關(guān)的求和函數(shù)函數(shù)SUM和循環(huán)函數(shù)和循環(huán)函數(shù)FOR等。等。上例中定義的目標(biāo)函數(shù)與上例中定義的目標(biāo)函數(shù)與quarters的

29、元素?cái)?shù)目是的元素?cái)?shù)目是 4或或 1000并無并無具體的關(guān)系。約束的表示也類似。具體的關(guān)系。約束的表示也類似。.35（3 3）數(shù)據(jù)段）數(shù)據(jù)段(DATA)(DATA)：以：以 “DATA:” 開始開始, “ENDDATA”結(jié)束，對(duì)集結(jié)束，對(duì)集合的屬性合的屬性(數(shù)組數(shù)組)輸入必要的常數(shù)數(shù)據(jù)。輸入必要的常數(shù)數(shù)據(jù)。格式為：格式為：“attribute(屬性屬性) = value_list(常數(shù)列表常數(shù)列表);”常數(shù)列表常數(shù)列表(value_list)中數(shù)據(jù)之間可以用逗號(hào)中數(shù)據(jù)之間可以用逗號(hào)“,”分開，也可以用空分開，也可以用空格分開格分開(回車等價(jià)于一個(gè)空格回車等價(jià)于一個(gè)空格),如上面對(duì)如上面對(duì)DEM的

30、賦值也可以寫成的賦值也可以寫成“DEM=40 60 75 25；”。 在LINGO模型中，如果想在運(yùn)行時(shí)才對(duì)參數(shù)賦值，可以在數(shù)據(jù)段使用輸入語句。但這僅能用于對(duì)單個(gè)變量賦值，輸入語句格式為：“變量名 = ？；”。例如，上例中如果需要在求解模型時(shí)才給出初始庫存量(記為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ì)算任意初始庫存量(而不僅僅只能計(jì)算初始庫存量為10)的

31、情況了。.36（4 4）初始段）初始段(INIT)(INIT)：以：以“INIT: ”開始，開始， “ENDINIT”結(jié)束，對(duì)結(jié)束，對(duì)集合的屬性集合的屬性(數(shù)組數(shù)組)定義初值定義初值(因?yàn)榍蠼馑惴ㄒ话闶堑惴?，所以因?yàn)榍蠼馑惴ㄒ话闶堑惴?，所以用戶如果能給出一個(gè)比較好的迭代初值，對(duì)提高算法的計(jì)算效果用戶如果能給出一個(gè)比較好的迭代初值，對(duì)提高算法的計(jì)算效果是有益的是有益的)。如果有一個(gè)接近最優(yōu)解的初值，對(duì)如果有一個(gè)接近最優(yōu)解的初值，對(duì)LINGO求解模型是有幫助求解模型是有幫助的。定義初值的格式為：的。定義初值的格式為：“attribute（屬性）（屬性） = value_list（常數(shù)列表）

32、；（常數(shù)列表）；”這與數(shù)據(jù)段中的用法是類似的。這與數(shù)據(jù)段中的用法是類似的。上例中沒有初始化部分，我們將在下一個(gè)例子中舉例說明。上例中沒有初始化部分，我們將在下一個(gè)例子中舉例說明。.37（5 5）計(jì)算段）計(jì)算段(CALC)(CALC)：以：以“CALC: ”開始，開始， “ENDCALC”結(jié)束結(jié)束，對(duì)一些原始數(shù)據(jù)進(jìn)行計(jì)算處理。，對(duì)一些原始數(shù)據(jù)進(jìn)行計(jì)算處理。在實(shí)際問題中，輸入的數(shù)據(jù)通常是原始數(shù)據(jù)，不一定能在模型在實(shí)際問題中，輸入的數(shù)據(jù)通常是原始數(shù)據(jù)，不一定能在模型中直接使用，可以在這個(gè)段對(duì)這些原始數(shù)據(jù)進(jìn)行一定的中直接使用，可以在這個(gè)段對(duì)這些原始數(shù)據(jù)進(jìn)行一定的“預(yù)處理預(yù)處理”，得到模型中真正需要的數(shù)

33、據(jù)。，得到模型中真正需要的數(shù)據(jù)。例如上例，如果希望得到全年的總需求和季度平均需求，可以增加這個(gè)段：例如上例，如果希望得到全年的總需求和季度平均需求，可以增加這個(gè)段：CALC: T_DEM = SUM(quarters: DEM); !總需求總需求; A_DEM = T_DEM / size(quarters); !平均需求平均需求;ENDCALC在計(jì)算段中也可以使用集合函數(shù)（其中函數(shù)在計(jì)算段中也可以使用集合函數(shù)（其中函數(shù)size(quarters)表示集合表示集合quarters的元素個(gè)數(shù)，這里也就是的元素個(gè)數(shù)，這里也就是4）。這時(shí)，變量）。這時(shí)，變量T_DEM的值就是總需求，的值就是總需求，

34、A_DEM的值就是平均需求（如果需要的話，這兩個(gè)變量就可以在程序的其它地方作的值就是平均需求（如果需要的話，這兩個(gè)變量就可以在程序的其它地方作為常數(shù)使用了）。為常數(shù)使用了）。注：上面的兩個(gè)語句不能交換順序，因?yàn)橛?jì)算注：上面的兩個(gè)語句不能交換順序，因?yàn)橛?jì)算A_DEM必須要用到必須要用到T_DEM的的值。此外，在計(jì)算段中只能直接使用賦值語句，而不能包含需要經(jīng)過解方程值。此外，在計(jì)算段中只能直接使用賦值語句，而不能包含需要經(jīng)過解方程或經(jīng)過求解優(yōu)化問題以后才能決定的變量?；蚪?jīng)過求解優(yōu)化問題以后才能決定的變量。.38基本集合與派生集合基本集合與派生集合 例例3 建筑工地的位置建筑工地的位置(用平面坐標(biāo)用

35、平面坐標(biāo)a, b表示，距離單位：公里表示，距離單位：公里)及水及水泥日用量泥日用量d(噸噸)下表給出。有兩個(gè)臨時(shí)料場(chǎng)位于下表給出。有兩個(gè)臨時(shí)料場(chǎng)位于P (5,1), Q (2, 7),日日儲(chǔ)量各有儲(chǔ)量各有20噸。從噸。從A, B兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使總的噸公里數(shù)最小。兩個(gè)新的料場(chǎng)應(yīng)建在何處，節(jié)省的噸公里數(shù)總的噸公里數(shù)最小。兩個(gè)新的料場(chǎng)應(yīng)建在何處，節(jié)省的噸公里數(shù)有多大？有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611.39建立模型建立模型記工地的位置為記工地的位置為 ，水泥日用量為，水泥

36、日用量為 ；料場(chǎng)位置為；料場(chǎng)位置為 ，日儲(chǔ)量為，日儲(chǔ)量為 ；從料場(chǎng)；從料場(chǎng) 向工地向工地 的運(yùn)送量為的運(yùn)送量為 。 ),(iiba6, 1,idi),(jjyx2 , 1,jejjiijc 2622112161MIN1s.t.,1,2,62,1,23ijjijijiijijijjifcxayacdicej使用現(xiàn)有臨時(shí)料場(chǎng)時(shí)，決策變量只有使用現(xiàn)有臨時(shí)料場(chǎng)時(shí)，決策變量只有 （非負(fù)），所以這是（非負(fù)），所以這是LP模型；當(dāng)為新模型；當(dāng)為新建料場(chǎng)選址時(shí)決策變量為建料場(chǎng)選址時(shí)決策變量為 和和 ，由于目標(biāo)函數(shù)，由于目標(biāo)函數(shù) 對(duì)對(duì) 是非線性的，是非線性的，所以在新建料場(chǎng)時(shí)是所以在新建料場(chǎng)時(shí)是NLP模型。先解

37、模型。先解NLP模型，而把現(xiàn)有臨時(shí)料場(chǎng)的位置作模型，而把現(xiàn)有臨時(shí)料場(chǎng)的位置作為初始解告訴為初始解告訴LINGO。 ijcijcjjyx ,fjjyx ,.40本例中集合的概念本例中集合的概念利用集合的概念，可以定義需求點(diǎn)利用集合的概念，可以定義需求點(diǎn)DEMAND和供應(yīng)點(diǎn)和供應(yīng)點(diǎn)SUPPLY兩個(gè)集合，分別有兩個(gè)集合，分別有6個(gè)和個(gè)和2個(gè)元素個(gè)元素(下標(biāo)下標(biāo))。但決策變量。但決策變量(運(yùn)送量運(yùn)送量) 與集合與集合DEMAND和集合和集合SUPPLY都有關(guān)系的。該如何定義這樣都有關(guān)系的。該如何定義這樣的屬性？的屬性？ijc集合的屬性相當(dāng)于以集合的元素為下標(biāo)的數(shù)組。這里的集合的屬性相當(dāng)于以集合的元素為

38、下標(biāo)的數(shù)組。這里的 相當(dāng)于相當(dāng)于二維數(shù)組。它的兩個(gè)下標(biāo)分別來自集合二維數(shù)組。它的兩個(gè)下標(biāo)分別來自集合DEMAND和和SUPPLY，因此可以定義一個(gè)由二元對(duì)組成的新的集合，然后將因此可以定義一個(gè)由二元對(duì)組成的新的集合，然后將 定義成定義成這個(gè)新集合的屬性。這個(gè)新集合的屬性。ijcijc.41輸入程序輸入程序 定義了三個(gè)集合，其中定義了三個(gè)集合，其中LINK在前在前兩個(gè)集合兩個(gè)集合DEMAND 和和SUPPLY的的基礎(chǔ)上定義基礎(chǔ)上定義表示集合表示集合LINK中的元素就是集合中的元素就是集合DEMAND 和和SUPPLY的元素組合成的有序二元組，的元素組合成的有序二元組，從數(shù)學(xué)上看從數(shù)學(xué)上看LINK

39、是是DEMAND 和和SUPPLY的笛的笛卡兒積，也就是說卡兒積，也就是說LINK=（S，T）|SDEMAND，TSUPPLY因此，其屬性因此，其屬性C也就是一個(gè)也就是一個(gè)6*2的矩陣（或者的矩陣（或者說是含有說是含有12個(gè)元素的二維數(shù)組）。個(gè)元素的二維數(shù)組）。LINGO建模語言也稱為矩陣生成器（建模語言也稱為矩陣生成器（MATRIX GENERATOR）。類似）。類似DEMAND 和和SUPPLY直接把元素列舉出來的集合，稱直接把元素列舉出來的集合，稱為為基本集合基本集合(primary set),而把而把LINK這種基于其它集合而派生出這種基于其它集合而派生出來的二維或多維集合稱為來的二維

40、或多維集合稱為派生集合派生集合(derived set)。由于是。由于是DEMAND 和和SUPPLY生成了派生集合生成了派生集合LINK，所以，所以DEMAND 和和SUPPLY 稱為稱為L(zhǎng)INK的的父集合父集合。.42輸入程序輸入程序 初始段 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；.43輸入程序輸入程序

41、定義目標(biāo)和約束，與前例的方法是類似(這里包含了派生集合)，請(qǐng)?zhí)貏e注意進(jìn)一步體會(huì)集合函數(shù)SUM和FOR的用法。由于新建料場(chǎng)的位置理論上講可以是任意的，所以在約束的最后(模型的“END”語句上面的一行)用free函數(shù)取消了變量X、Y的非負(fù)限制在程序開頭用TITLE語句對(duì)這個(gè)模型取了一個(gè)標(biāo)題“LOCATION PROBLEM；并且對(duì)目標(biāo)行（OBJ）和兩類約束（DEMAND_CON、SUPPLY_CON）分別進(jìn)行了命名(請(qǐng)?zhí)貏e注意這里約束命名的特點(diǎn))。 .44解答解答:運(yùn)行菜單命令運(yùn)行菜單命令“LINGO|Solve” 局部最優(yōu)解局部最優(yōu)解X(1)=7.249997， X(2)=5.695940，Y(

42、1)=7.749998， Y(2)=4.928524，C（略），（略），最小運(yùn)量最小運(yùn)量=89.8835(噸公里噸公里)。 問題問題:最小運(yùn)量最小運(yùn)量89.8835是不是全局最優(yōu)是不是全局最優(yōu) 是用是用“LINGO|Options”菜單命令打開選項(xiàng)對(duì)話框，在菜單命令打開選項(xiàng)對(duì)話框，在“Global Solver”選項(xiàng)卡上選擇選項(xiàng)卡上選擇“Use Global Solver”, 激活全局最優(yōu)求解程激活全局最優(yōu)求解程序。序。.45問題問題:最小運(yùn)量最小運(yùn)量89.8835是不是全局最優(yōu)是不是全局最優(yōu) 為減少計(jì)算工作量，對(duì)為減少計(jì)算工作量，對(duì)X，Y的取值再做一些限制。雖然理論上的取值再做一些限制。雖然

43、理論上新建料場(chǎng)的位置可以是任意的，但顯然最佳的料場(chǎng)位置不應(yīng)該離新建料場(chǎng)的位置可以是任意的，但顯然最佳的料場(chǎng)位置不應(yīng)該離工地太遠(yuǎn)，至少不應(yīng)該超出現(xiàn)在工地太遠(yuǎn)，至少不應(yīng)該超出現(xiàn)在6個(gè)工地所決定的坐標(biāo)的最大、個(gè)工地所決定的坐標(biāo)的最大、最小值決定的矩形之外，即最小值決定的矩形之外，即: 0.5=x=8.75, 0.75=y=7.75. 可以用可以用bnd函數(shù)加函數(shù)加上這個(gè)條件取代模型上這個(gè)條件取代模型END上面的行，運(yùn)行上面的行，運(yùn)行NLP模型，全局最優(yōu)模型，全局最優(yōu)求解程序花費(fèi)的時(shí)間求解程序花費(fèi)的時(shí)間仍然很長(zhǎng)，運(yùn)行仍然很長(zhǎng)，運(yùn)行27分分35秒時(shí)人為終止求解秒時(shí)人為終止求解(按下按下“Interrup

44、t Solver”按鈕按鈕)得到左得到左邊模型窗口和全局求邊模型窗口和全局求解器的狀態(tài)窗口解器的狀態(tài)窗口此時(shí)目標(biāo)函數(shù)值的下界（此時(shí)目標(biāo)函數(shù)值的下界（Obj Bound=85.2638）與目前得到的最好）與目前得到的最好的可行解的目標(biāo)函數(shù)值（的可行解的目標(biāo)函數(shù)值（Best Obj=85.2661）相差已經(jīng)非常小，可）相差已經(jīng)非常小，可以認(rèn)為已經(jīng)得到了全局最優(yōu)解。以認(rèn)為已經(jīng)得到了全局最優(yōu)解。 .46計(jì)算結(jié)果計(jì)算結(jié)果 012345678901234567835476112016工地與料場(chǎng)示意圖工地與料場(chǎng)示意圖 : “*”表示料場(chǎng)，表示料場(chǎng)，“+”表表示工地示工地 可以認(rèn)為是模型的最后結(jié)果可以認(rèn)為是模

45、型的最后結(jié)果 附注：如果要把料廠P(5, 1), Q (2, 7)的位置看成是已知并且固定的，這時(shí)是LP模型。只需要把初始段的“X Y =5，1，2，7；”語句移到數(shù)據(jù)段就可以了。此時(shí)，運(yùn)行結(jié)果告訴我們得到全局最優(yōu)解（變量C的取值這里略去），最小運(yùn)量136.2275(噸公里)。.47稠密集合與稀疏集合稠密集合與稀疏集合 包含了兩個(gè)基本集合構(gòu)成的所有二元有序?qū)Φ呐缮戏Q為包含了兩個(gè)基本集合構(gòu)成的所有二元有序?qū)Φ呐缮戏Q為稠密稠密集合集合(簡(jiǎn)稱稠集簡(jiǎn)稱稠集)。有時(shí)候，在實(shí)際問題中，一些屬性。有時(shí)候，在實(shí)際問題中，一些屬性(數(shù)組數(shù)組) 只在笛只在笛卡兒積的一個(gè)真子集合上定義，這種派生集合稱為卡兒

46、積的一個(gè)真子集合上定義，這種派生集合稱為稀疏集合稀疏集合(簡(jiǎn)稱簡(jiǎn)稱疏集疏集)。例例 (最短路問題最短路問題) 在縱橫交錯(cuò)的公路網(wǎng)中，貨車司機(jī)希望找到一條在縱橫交錯(cuò)的公路網(wǎng)中，貨車司機(jī)希望找到一條從一個(gè)城市到另一個(gè)城市的最短路從一個(gè)城市到另一個(gè)城市的最短路. 下圖表示的是公路網(wǎng)下圖表示的是公路網(wǎng), 節(jié)點(diǎn)表節(jié)點(diǎn)表示貨車可以停靠的城市示貨車可以?？康某鞘?弧上的權(quán)表示兩個(gè)城市之間的距離弧上的權(quán)表示兩個(gè)城市之間的距離(百公里百公里). 那么那么,貨車從城市貨車從城市S出發(fā)到達(dá)城市出發(fā)到達(dá)城市T,如何選擇行駛路線如何選擇行駛路線,使所經(jīng)過的使所經(jīng)過的路程最短路程最短?STA1 A2 A3 B1 B2 C

47、1 C2 633665874678956.48STA1 A2 A3 B1 B2 C1 C2 633665874678956分析分析 假設(shè)從假設(shè)從S到到T的最優(yōu)行駛路線的最優(yōu)行駛路線 P 經(jīng)過城市經(jīng)過城市C1, 則則P中從中從S到到C1的子路的子路也一定是從也一定是從S到到C1的最優(yōu)行駛路線的最優(yōu)行駛路線; 假設(shè)假設(shè) P 經(jīng)過城市經(jīng)過城市C2, 則則P中從中從S到到C2的子路也一定是從的子路也一定是從S到到C2的最優(yōu)的最優(yōu)行駛路線行駛路線. 因此因此, 為得到從為得到從S到到T的最優(yōu)行駛路線的最優(yōu)行駛路線, 只需要先求出從只需要先求出從S到到Ck(k=1,2)的最優(yōu)行駛路線的最優(yōu)行駛路線, 就可

48、以方便地得到從就可以方便地得到從S到到T的最優(yōu)行駛路線的最優(yōu)行駛路線. 同樣同樣,為了求出從為了求出從S到到Ck(k=1,2)的最優(yōu)行駛路線的最優(yōu)行駛路線, 只需要先求出從只需要先求出從S到到Bj(j=1,2)的最優(yōu)行駛路線的最優(yōu)行駛路線; 為了求出從為了求出從S到到Bj(j=1,2)的最優(yōu)行駛路線的最優(yōu)行駛路線, 只需要先求出從只需要先求出從S到到Ai (i=1,2,3)的最優(yōu)行駛路線的最優(yōu)行駛路線. 而而S到到Ai(i=1,2,3)的最優(yōu)行駛路線是很容的最優(yōu)行駛路線是很容易得到的易得到的(實(shí)際上實(shí)際上, 此例中此例中S到到Ai(i=1,2,3)只有唯一的道路只有唯一的道路) .49分析分析

49、 STA1 A2 A3 B1 B2 C1 C2 633665874678956此例中可把從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): 0;1min,.2YXL SL XL Yd Y XXS.50本例的計(jì)算本例的計(jì)算 1231123321233112221221216,3,3;min6,8,7107;min5,6,474;min6,8158;min7,91

50、69;min5,6205.L AL AL AL BL AL AL AL AL BL AL AL AL AL CL BL BL BL CL BL BL BL TL CL CL CSTA1 A2 A3 B1 B2 C1 C2 633665874678956所以, 從S到T的最優(yōu)行駛路線的路長(zhǎng)為20. 進(jìn)一步分析以上求解過程, 可以得到從S到T的最優(yōu)行駛路線為S A3 B2 C1 T.這種計(jì)算方法在數(shù)學(xué)上稱為動(dòng)態(tài)規(guī)劃(Dynamic Programming) .51本例的本例的LINGO求解求解“CITIES”(城市城市):一個(gè)基本集合一個(gè)基本集合(元素通過枚舉給出元素通過枚舉給出)L:CITIES

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

52、)=0已已知，后面的值為空知，后面的值為空(但位置必須留出來，但位置必須留出來，即逗號(hào)即逗號(hào)“，”一個(gè)也不能少，否則會(huì)出一個(gè)也不能少，否則會(huì)出錯(cuò)錯(cuò))。如果這個(gè)語句直接寫成。如果這個(gè)語句直接寫成“L=0；”，語法上看也是對(duì)的，但其含義是，語法上看也是對(duì)的，但其含義是L所所有元素的取值全部為有元素的取值全部為0，所以也會(huì)與題，所以也會(huì)與題意不符。意不符。.53本例的本例的LINGO求解求解雖然集合雖然集合CITIES中的元素不是數(shù)字，但當(dāng)中的元素不是數(shù)字，但當(dāng)它以它以CITIES(I)的形式出現(xiàn)在循環(huán)中時(shí)，引的形式出現(xiàn)在循環(huán)中時(shí)，引用下標(biāo)用下標(biāo)I卻實(shí)際上仍是正整數(shù)，也就是說卻實(shí)際上仍是正整數(shù)，也就

53、是說I指指的正是元素在集合中的位置的正是元素在集合中的位置(順序順序)，一般稱，一般稱為元素的索引為元素的索引(INDEX)。在在for循環(huán)中的過濾條件里用了一個(gè)函數(shù)循環(huán)中的過濾條件里用了一個(gè)函數(shù)“index”, 其作用是返回一個(gè)元素在集合其作用是返回一個(gè)元素在集合中的索引值，這里中的索引值，這里index(S)=1(即元素即元素S在在集合中的索引值為集合中的索引值為1)，所以邏輯關(guān)系式，所以邏輯關(guān)系式“I#GT#index(S)”可以可以直接等價(jià)地可以可以直接等價(jià)地寫成寫成“I#GT#1” 。這里。這里index(S)實(shí)際上還實(shí)際上還是是index(CITIES,S)的簡(jiǎn)寫，即返回的簡(jiǎn)寫，即

54、返回S在集在集合合CITIES中的索引值。中的索引值。.54本例的本例的LINGO求解結(jié)果求解結(jié)果從S到T的最優(yōu)行駛路線的路長(zhǎng)為20(進(jìn)一步分析，可以得到最優(yōu)行駛路線為S A3 B2 C1 T)。 本例中定義稀疏集合本例中定義稀疏集合ROADS的方法是將其元素通過枚舉給出，有的方法是將其元素通過枚舉給出，有時(shí)如果元素比較多，用起來不方便。另一種定義稀疏集合的方法時(shí)如果元素比較多，用起來不方便。另一種定義稀疏集合的方法是是“元素過濾元素過濾”法，能夠從笛卡兒積中系統(tǒng)地過濾下來一些真正法，能夠從笛卡兒積中系統(tǒng)地過濾下來一些真正的元素。的元素。.55例例 某班某班8名同學(xué)準(zhǔn)備分成名同學(xué)準(zhǔn)備分成4個(gè)調(diào)

55、查隊(duì)個(gè)調(diào)查隊(duì)(每隊(duì)兩人每隊(duì)兩人)前往前往4個(gè)地區(qū)進(jìn)行個(gè)地區(qū)進(jìn)行社會(huì)調(diào)查。這社會(huì)調(diào)查。這8名同學(xué)兩兩之間組隊(duì)的效率如下表所示名同學(xué)兩兩之間組隊(duì)的效率如下表所示(由于對(duì)稱由于對(duì)稱性，只列出了嚴(yán)格上三角部分性，只列出了嚴(yán)格上三角部分)，問如何組隊(duì)可以使總效率最高，問如何組隊(duì)可以使總效率最高？學(xué)生S1S2S3S4S5S6S7S8S1-9342156S2-173521S3-44292S4-1552S5-876S6-23S7-4.56分析分析 這是一個(gè)匹配（MATCHING）問題。把上表的效率矩陣記為BENEFIT(由于對(duì)稱性，這個(gè)矩陣只有嚴(yán)格上三角部分共28個(gè)數(shù)取非零值)。 用MATCH（Si，Sj）=

56、1表示同學(xué)Si，Sj組成一隊(duì) ，而MATCH（Si，Sj）=0表示Si，Sj不組隊(duì)。由于對(duì)稱性，只需考慮ij共28個(gè)0-1變量(而不是全部32個(gè)變量)。 顯然,目標(biāo)函數(shù)正好是BENEFIT(Si,Sj)*MATCH(Si,Sj)對(duì)I,j之和。 約束條件是每個(gè)同學(xué)只能(而且必須在)某一組，即對(duì)于任意i有:只要屬性MATCH的某個(gè)下標(biāo)為i就加起來，此和應(yīng)該等于1。 由上面的分析，因此，完整的數(shù)學(xué)模型如下(顯然，這是一個(gè)0-1線性規(guī)劃)： 31.0)(21,2,3,4,I 1,)(. .1 ),(),(II，或J,KMATCHJ,KMATCHtsJI*MATCHJIBENEFITMaxKJJI.57

57、問題的問題的LINGO求解求解“S1.S8”等價(jià)于寫成“S1 S2 S3 S4 S5 S6 S7 S8”, 它沒有相關(guān)的屬性列表，只用于表示是一個(gè)下標(biāo)集合 在派生集合PAIRS定義中增加了過濾條件 “&2#GT#&1”,意思是第2個(gè)父集合的元素的索引值(用“&2”表示)大于第1個(gè)父集合的元素的索引值(用“&1”表示)。PAIRS中的元素對(duì)應(yīng)于上表中的嚴(yán)格上三角部分的二維下標(biāo)(共28個(gè)元素)。BENEFIT和MATCH是PAIRS的屬性。 注意數(shù)據(jù)段對(duì)BENEFIT的賦值方式，“LINGO按照列的順序?qū)傩宰兞康脑剡M(jìn)行賦值。在約束部分，過濾條件“J #EQ# I

58、 #OR# K #EQ# I”是由邏輯運(yùn)算符“#OR#（或者）”連接的一個(gè)復(fù)合的邏輯關(guān)系式，連接由“#EQ#（等于）”表示的兩個(gè)邏輯關(guān)系。由于“#OR#”的運(yùn)算級(jí)別低于“#EQ#”，所以這個(gè)邏輯式中沒有必要使用括號(hào)指定運(yùn)算次序。 .58LINGO求解結(jié)果求解結(jié)果“LINGO|SOLVE”運(yùn)行這個(gè)程序，可以得到全局最優(yōu)值為30 MATCH變量中多數(shù)為0，可以更清晰地瀏覽最優(yōu)解解。選擇菜單命令“LINGO|SOLUTION”，可以看到圖示對(duì)話框。選擇屬性MATCH(變量)選擇Text(文本格式)選擇Nonzeros Only(只顯示非零值)點(diǎn)擊“OK”按鈕，得到關(guān)于最優(yōu)解的非零分量的報(bào)告學(xué)生最佳的

59、組隊(duì)方式是學(xué)生最佳的組隊(duì)方式是(1,8),(2,4),(3,7),(5,6).59集合的使用小結(jié)集合的使用小結(jié) 集合的不同類型及其關(guān)系集合的不同類型及其關(guān)系 集合集合派生集合派生集合稀疏集合稀疏集合稠密集合稠密集合基本集合基本集合元素列表法元素列表法 元素過濾法元素過濾法 直接列舉法直接列舉法 隱式列舉法隱式列舉法 .60基本集合的定義語法基本集合的定義語法 基本集合的定義格式為(方括號(hào)“ ”中的內(nèi)容是可選項(xiàng), 可以沒有):setname /member_list/ : attribute_list;其中setname為定義的集合名，member_list為元素列表，attribute_lis

60、t為屬性列表。元素列表可以采用顯式列舉法(即直接將所有元素全部列出,元素之間用逗號(hào)或空格分開),也可以采用隱式列舉法。隱式列舉法可以有幾種不同格式，類型隱式列舉格式示例示例集合表示的元素?cái)?shù)字型1.n1.51, 2, 3, 4, 5字符-數(shù)字型stringM.stringNCar101.car208Car101, car102, , car208日期（星期）型dayM.dayNMON.FRIMON, TUE, WED, THU, FRI月份型monthM.monthNOCT.JANOCT, NOV, DEC, JAN年份-月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001, NOV2