優(yōu)化建模與LINGO簡介.ppt

優(yōu)化建模與LINDO/LINGO軟件,最優(yōu)化是工程技術(shù)、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的問題, 如:,優(yōu)化模型和算法的重要意義,結(jié)構(gòu)設計,資源分配,生產(chǎn)計劃,運輸方案,解決優(yōu)化問題的手段,經(jīng)驗積累，主觀判斷,作試驗，比優(yōu)劣,建立數(shù)學模型，求解最優(yōu)策略,最優(yōu)化: 在一定條件下，尋求使目標最大(小)的決策,優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件,優(yōu)化問題的一般形式,無約束優(yōu)化(沒有約束)與約束優(yōu)化(有約束) 可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值),局部最優(yōu)解與整體最優(yōu)解,局部最優(yōu)解 (Local Optimal Solution, 如 x1 ) 整體最優(yōu)解 (Global Optimal Solution, 如 x2 ),優(yōu)化模型的 簡單分類,線性規(guī)劃(LP) 目標和約束均為線性函數(shù) 非線性規(guī)劃(NLP) 目標或約束中存在非線性函數(shù) 二次規(guī)劃(QP) 目標為二次函數(shù)、約束為線性 整數(shù)規(guī)劃(IP) 決策變量(全部或部分)為整數(shù) 整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP) 純整數(shù)規(guī)劃(PIP), 混合整數(shù)規(guī)劃(MIP) 一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃,連續(xù)優(yōu)化,離散優(yōu)化,數(shù)學規(guī)劃,優(yōu)化模型的簡單分類和求解難度,優(yōu)化,線性規(guī)劃,非線性規(guī)劃,二次規(guī)劃,連續(xù)優(yōu)化,整數(shù)規(guī)劃,問題求解的難度增加,2. 優(yōu)化問題的建模實例,50桶牛奶,時間480小時,至多加工100公斤A1,制訂生產(chǎn)計劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少?,可聘用臨時工人，付出的工資最多是每小時幾元?,A1的獲利增加到 30元/公斤，應否改變生產(chǎn)計劃？,每天：,線性規(guī)劃模型例1: 奶制品生產(chǎn)計劃,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 243x1,獲利 164 x2,原料供應,勞動時間,加工能力,決策變量,目標函數(shù),每天獲利,約束條件,非負約束,線性規(guī)劃模型(LP),時間480小時,至多加工100公斤A1,模型求解,圖解法,約束條件,目標函數(shù),z=c (常數(shù)) 等值線,在B(20,30)點得到最優(yōu)解,目標函數(shù)和約束條件是線性函數(shù),可行域為直線段圍成的凸多邊形,目標函數(shù)的等值線為直線,最優(yōu)解一定在凸多邊形的某個頂點取得。,求解LP的基本思想,思路：從可行域的某一頂點開始，只需在有限多個頂點中一個一個找下去，一定能得到最優(yōu)解。,LP的約束和目標函數(shù)均為線性函數(shù),2維,可行域 線段組成的凸多邊形,目標函數(shù) 等值線為直線,最優(yōu)解 凸多邊形的某個頂點,n維,超平面組成的凸多面體,等值線是超平面,凸多面體的某個頂點,LP的通常解法是單純形法(G. B. Dantzig, 1947),內(nèi)點算法(Interior point method) 20世紀80年代人們提出的一類新的算法內(nèi)點算法 也是迭代法，但不再從可行域的一個頂點轉(zhuǎn)換到另一個頂點，而是直接從可行域的內(nèi)部逼近最優(yōu)解。,LP其他算法,有效集(Active Set)方法 LP是QP的特例（只需令所有二次項為零即可） 可以用QP的算法解QP(如: 有效集方法),線性規(guī)劃模型的解的幾種情況,某廠生產(chǎn)兩個牌號的同一種產(chǎn)品，如何確定產(chǎn)量使利潤最大,二次規(guī)劃模型產(chǎn)銷計劃問題,= （100-x1-0.1 x2-2）x1 +（280-0.2x1-2x2-3）x2 =98 x1 + 277 x2 x12 0.3 x1 x2 2x22,約束,x1 + x2 100 x1 2 x2 x1 , x2 0,二次規(guī)劃模型(QP),若還要求產(chǎn)量為整數(shù)，則是整數(shù)二次規(guī)劃模型(IQP),非線性規(guī)劃模型選址問題,某公司有6個建筑工地，位置坐標為(ai, bi) (單位：公里),水泥日用量di (單位：噸）,假設：料場和工地之間有直線道路,用例中數(shù)據(jù)計算，最優(yōu)解為,總噸公里數(shù)為136.2,線性規(guī)劃模型(LP),決策變量：ci j (料場j到工地i的運量）12維,選址問題：NLP,2）改建兩個新料場，需要確定新料場位置(xj,yj)和運量cij ，在其它條件不變下使總噸公里數(shù)最小。,決策變量： ci j，(xj,yj)16維,非線性規(guī)劃模型 (NLP),整數(shù)規(guī)劃 - 聘用方案,決策變量：周一至周日每天(新)聘用人數(shù) x1, x2,x7,目標函數(shù)：7天(新)聘用人數(shù)之和,約束條件：周一至周日每天需要人數(shù),連續(xù)工作5天,設系統(tǒng)已進入穩(wěn)態(tài)（不是開始的幾周）,聘用方案,整數(shù)規(guī)劃 模型(IP),丁的蛙泳成績退步到115”2；戊的自由泳成績進步到57”5, 組成接力隊的方案是否應該調(diào)整？,如何選拔隊員組成4100米混合泳接力隊?,0-1規(guī)劃 混合泳接力隊的選拔,5名候選人的百米成績,窮舉法：,目標函數(shù),若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij(秒)隊員i 第j 種泳姿的百米成績,約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,0-1規(guī)劃: 整數(shù)規(guī)劃的特例,無約束優(yōu)化,更多的優(yōu)化問題,線性規(guī)劃,非線性規(guī)劃,網(wǎng)絡優(yōu)化,組合優(yōu)化,整數(shù)規(guī)劃,不確定規(guī)劃,多目標規(guī)劃,目標規(guī)劃,動態(tài)規(guī)劃,連續(xù)優(yōu)化,離散優(yōu)化,從其他角度分類,應用廣泛：生產(chǎn)和運作管理、經(jīng)濟與金融、圖論和網(wǎng)絡優(yōu)化、目標規(guī)劃問題、對策論、排隊論、存儲論，以及更加綜合、更加復雜的決策問題等 實際問題規(guī)模往往較大，用軟件求解比較方便,3. LINDO/LINGO軟件簡介,LINDO 公司軟件產(chǎn)品簡要介紹,美國芝加哥(Chicago)大學的Linus Schrage教授于1980年前后開發(fā), 后來成立 LINDO系統(tǒng)公司（LINDO Systems Inc.）， 網(wǎng)址：,LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINDO API: LINDO Application Programming Interface (V4.1) LINGO: Linear INteractive General Optimizer (V10.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0),演示(試用)版、高級版、超級版、工業(yè)版、擴展版 （求解問題規(guī)模和選件不同）,LP QP NLP IP 全局優(yōu)化(選) ILP IQP INLP,LINGO軟件的求解過程,LINGO預處理程序,線性優(yōu)化求解程序,非線性優(yōu)化求解程序,分枝定界管理程序,1. 確定常數(shù) 2. 識別類型,1. 單純形算法 2. 內(nèi)點算法(選),1、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法(GRG) (選) 3、多點搜索(Multistart) (選),建模時需要注意的幾個基本問題,1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量 2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù) 如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等 3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù) （如x/y 5 改為x5y） 4、合理設定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級要適當 (如小于103),安裝文件20M多一點，需要接受安裝協(xié)議、選擇安裝目錄（缺省C:LINGO9）。,LINGO軟件的安裝,安裝過程: 與LINDO for Windows類似.,安裝完成前，在出現(xiàn)的對話框(如圖)中選擇缺省的建模(即編程)語言，系統(tǒng)推薦的是采用LINGO。安裝后可通過“LINGO|Options|File Format”命令修改缺省的建模（即編程）語言。,第一次運行時提示輸入授權(quán)密碼，如圖：,一個簡單的LINGO程序,例 直接用LINGO來解如下二次規(guī)劃問題：,輸入窗口如下：,程序語句輸入的備注：,LINGO總是根據(jù)“MAX=”或“MIN=”尋找目標函數(shù)，而除注釋語句和TITLE語句外的其他語句都是約束條件，因此語句的順序并不重要 。 限定變量取整數(shù)值的語句為“GIN(X1)”和“GIN(X2)”，不可以寫成“GIN(2)”，否則LINGO將把這個模型看成沒有整數(shù)變量。 LINGO中函數(shù)一律需要以“”開頭，其中整型變量函數(shù)（BIN、GIN）和上下界限定函數(shù)（FREE、SUB、SLB）與LINDO中的命令類似。而且0/1變量函數(shù)是BIN函數(shù)。,輸出結(jié)果：,運行菜單命令“LINGO|Solve”,最優(yōu)整數(shù)解 X=(35，65),最大利潤=11077.5,輸出結(jié)果備注：,通過菜單 “WINDOW| Status Window”看到狀態(tài)窗口，可看到最佳目標值“Best Obj”與問題的上界“Obj Bound”已經(jīng)是一樣的，當前解的最大利潤與這兩個值非常接近，是計算誤差引起的。如果采用全局最優(yōu)求解程序(后面介紹)，可以驗證它就是全局最優(yōu)解。,LINGO是將它作為PINLP(純整數(shù)非線性規(guī)劃)來求解，因此找到的是局部最優(yōu)解。,一個簡單的LINGO程序,LINGO的基本用法的幾點注意事項,LINGO中不區(qū)分大小寫字母；變量和行名可以超過8個字符，但不能超過32個字符，且必須以字母開頭。 用LINGO解優(yōu)化模型時已假定所有變量非負(除非用限定變量取值范圍的函數(shù)free或sub或slb另行說明)。 變量可以放在約束條件的右端(同時數(shù)字也可放在約束條件的左端)。但為了提高LINGO求解時的效率，應盡可能采用線性表達式定義目標和約束(如果可能的話)。 語句是組成LINGO模型的基本單位,每個語句都以分號結(jié)尾，編寫程序時應注意模型的可讀性。例如：一行只寫一個語句，按照語句之間的嵌套關(guān)系對語句安排適當?shù)目s進，增強層次感。 以感嘆號開始的是說明語句(說明語句也需要以分號結(jié)束)）。,集合的基本用法和LINGO模型的基本要素,理解LINGO建模語言最重要的是理解集合（Set）及其屬性（Attribute）的概念。,例 SAILCO公司需要決定下四個季度的帆船生產(chǎn)量。下四個季度的帆船需求量分別是40條，60條，75條，25條，這些需求必須按時滿足。每個季度正常的生產(chǎn)能力是40條帆船，每條船的生產(chǎn)費用為400美元。如果加班生產(chǎn)，每條船的生產(chǎn)費用為450美元。每個季度末，每條船的庫存費用為20美元。假定生產(chǎn)提前期為0，初始庫存為10條船。如何安排生產(chǎn)可使總費用最??？,用DEM,RP,OP,INV分別表示需求量、正常生產(chǎn)的產(chǎn)量、加班生產(chǎn)的產(chǎn)量、庫存量，則DEM,RP,OP,INV對每個季度都應該有一個對應的值，也就說他們都應該是一個由4個元素組成的數(shù)組，其中DEM是已知的，而RP,OP,INV是未知數(shù)。,問題的模型(可以看出是LP模型 ),目標函數(shù)是所有費用的和,約束條件主要有兩個：,1）能力限制：,2）產(chǎn)品數(shù)量的平衡方程：,加上變量的非負約束,注：LINDO中沒有數(shù)組，只能對每個季度分別定義變量，如正常產(chǎn)量就要有RP1，RP2，RP3，RP4 4個變量等。寫起來就比較麻煩，尤其是更多(如1000個季度)的時候。 記四個季度組成的集合QUARTERS=1，2，3，4，它們就是上面數(shù)組的下標集合，而數(shù)組DEM,RP,OP, INV對集合QUARTERS中的每個元素1，2，3，4分別對應于一個值。LINGO正是充分利用了這種數(shù)組及其下標的關(guān)系，引入了“集合”及其“屬性”的概念，把QUARTERS=1，2，3，4稱為集合，把DEM,RP,OP, INV稱為該集合的屬性(即定義在該集合上的屬性)。,集合及其屬性,集合元素及集合的屬性確定的所有變量,LINGO中定義集合及其屬性,LP模型在LINGO中的一個典型輸入方式,以“MODEL：”開始,以“END”結(jié)束,給出優(yōu)化目標和約束,目標函數(shù)的定義方式,SUM(集合（下標）：關(guān)于集合的屬性的表達式),對語句中冒號“：”后面的表達式，按照“：”前面的集合指定的下標（元素）進行求和。,本例中目標函數(shù)也可以等價地寫成 SUM(QUARTERS(i): 400*RP(i) +450*OP(i) +20*INV(i) )， “SUM”相當于求和符號“”， “QUARTERS(i)”相當于“iQUARTERS”的含義。 由于本例中目標函數(shù)對集合QUARTERS的所有元素(下標) 都要求和，所以可以將下標i省去。,約束的定義方式,循環(huán)函數(shù) FOR(集合(下標)：關(guān)于集合的屬性的約束關(guān)系式),對冒號“：”前面的集合的每個元素（下標），冒號“：”后面的約束關(guān)系式都要成立,本例中，每個季度正常的生產(chǎn)能力是40條帆船，這正是語句“FOR(QUARTERS(I):RP(I)40);”的含義。 由于對所有元素(下標I),約束的形式是一樣的，所以也可以像上面定義目標函數(shù)時一樣，將下標i省去， 這個語句可以簡化成“FOR(QUARTERS:RP40);” 。,本例中，對于產(chǎn)品數(shù)量的平衡方程，由于下標i=1時的約束關(guān)系式與i=2，3，4時有所區(qū)別，所以不能省略下標“i”。實際上，i=1時要用到變量INV（0），但定義的屬性變量中INV不包含INV（0）(INV(0)=10是一個已知的)。 為了區(qū)別i=1和i=2，3，4，把i=1時的約束關(guān)系式單獨寫出，即“INV(1)=10+RP(1)+OP(1)-DEM(1);” ； 而對i=2，3，4對應的約束，對下標集合的元素（下標i）增加了一個邏輯關(guān)系式“i#GT#1”（這個限制條件與集合之間有一個豎線“|”分開，稱為過濾條件）。 限制條件“i#GT#1”是一個邏輯表達式，意思就是i1；“#GT#”是邏輯運算符號，意思是“大于（Greater Than的字首字母縮寫）” 。,約束的定義方式,問題的求解：運行菜單命令“LINGO|Solve”,最小成本=78450,注：由于輸入中沒有給出行名，所以行名是系統(tǒng)自動按照行號1-9生成的。 選擇菜單命令“LINGO|Generate|Disply model（Ctrl+G）”，可以得到展開形式的模型(如圖)，可以看到完整的模型，也能確定行號(行號放在方括號“ ”中，且數(shù)字前面帶有下劃線“_”)。 最好在輸入模型時用戶主動設定約束的行名(即約束名)，使程序清晰些。單一約束的行名設置方法就是將行名放在方括號“ ”中，置于約束之前。 后面將結(jié)合具體例子介紹在使用集合的情況下如何設置行名。,基本集合與派生集合,例 建筑工地的位置(用平面坐標a, b表示，距離單位：公里)及水泥日用量d(噸)下表給出。有兩個臨時料場位于P (5,1), Q (2, 7),日儲量各有20噸。從A, B兩料場分別向各工地運送多少噸水泥，使總的噸公里數(shù)最小。兩個新的料場應建在何處，節(jié)省的噸公里數(shù)有多大？,建立模型,記工地的位置為 ，水泥日用量為 ；料場位置為 ，日儲量為 ；從料場 向工地 的運送量為 。,使用現(xiàn)有臨時料場時，決策變量只有 （非負），所以這是LP模型；當為新建料場選址時決策變量為 和 ，由于目標函數(shù) 對 是非線性的，所以在新建料場時是NLP模型。先解NLP模型，而把現(xiàn)有臨時料場的位置作為初始解告訴LINGO。,本例中集合的概念,利用集合的概念，可以定義需求點DEMAND和供應點SUPPLY兩個集合，分別有6個和2個元素(下標)。但決策變量(運送量) 與集合DEMAND和集合SUPPLY都有關(guān)系的。該如何定義這樣的屬性？,集合的屬性相當于以集合的元素為下標的數(shù)組。這里的 相當于二維數(shù)組。它的兩個下標分別來自集合DEMAND和SUPPLY，因此可以定義一個由二元對組成的新的集合，然后將 定義成這個新集合的屬性。,輸入程序,定義了三個集合，其中LINK在前兩個集合DEMAND 和SUPPLY的基礎上定義,表示集合LINK中的元素就是集合DEMAND 和SUPPLY的元素組合成的有序二元組， 從數(shù)學上看LINK是DEMAND 和SUPPLY的笛卡兒積，也就是說 LINK=（S，T）|SDEMAND，TSUPPLY 因此，其屬性C也就是一個6*2的矩陣（或者說是含有12個元素的二維數(shù)組）。,LINGO建模語言也稱為矩陣生成器（MATRIX GENERATOR）。類似DEMAND 和SUPPLY直接把元素列舉出來的集合，稱為基本集合(primary set),而把LINK這種基于其它集合而派生出來的二維或多維集合稱為派生集合(derived set)。由于是DEMAND 和SUPPLY生成了派生集合LINK，所以DEMAND 和SUPPLY 稱為LINK的父集合。,輸入程序,初始段,INGO對數(shù)據(jù)是按列賦值的 語句的實際賦值順序是X=(5,2), Y=(1,7), 而不是X=(5,1), Y=（2,7) 等價寫法： “X=5,2； Y=1,7；”,同理，數(shù)據(jù)段中對常數(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；,輸入程序,解答:運行菜單命令“LINGO|Solve”,局部最優(yōu)解X(1)=7.249997， X(2)=5.695940，Y(1)=7.749998， Y(2)=4.928524，C（略）， 最小運量=89.8835(噸公里)。,問題:最小運量89.8835是不是全局最優(yōu),是用“LINGO|Options”菜單命令打開選項對話框，在“Global Solver”選項卡上選擇“Use Global Solver”, 激活全局最優(yōu)求解程序。,問題:最小運量89.8835是不是全局最優(yōu),此時目標函數(shù)值的下界（Obj Bound=85.2638）與目前得到的最好的可行解的目標函數(shù)值（Best Obj=85.2661）相差已經(jīng)非常小，可以認為已經(jīng)得到了全局最優(yōu)解。,計算結(jié)果,工地與料場示意圖 : “*”表示料場，“+”表示工地,可以認為是模型的最后結(jié)果,附注：如果要把料廠P(5, 1), Q (2, 7)的位置看成是已知并且固定的，這時是LP模型。只需要把初始段的“X Y =5，1，2，7；”語句移到數(shù)據(jù)段就可以了。此時，運行結(jié)果告訴我們得到全局最優(yōu)解（變量C的取值這里略去），最小運量136.2275(噸公里)。,稠密集合與稀疏集合,包含了兩個基本集合構(gòu)成的所有二元有序?qū)Φ呐缮戏Q為稠密集合(簡稱稠集)。有時候，在實際問題中，一些屬性(數(shù)組) 只在笛卡兒積的一個真子集合上定義，這種派生集合稱為稀疏集合(簡稱疏集)。,例 (最短路問題) 在縱橫交錯的公路網(wǎng)中，貨車司機希望找到一條從一個城市到另一個城市的最短路. 下圖表示的是公路網(wǎng), 節(jié)點表示貨車可以停靠的城市,弧上的權(quán)表示兩個城市之間的距離(百公里). 那么,貨車從城市S出發(fā)到達城市T,如何選擇行駛路線,使所經(jīng)過的路程最短?,分析,假設從S到T的最優(yōu)行駛路線 P 經(jīng)過城市C1, 則P中從S到C1的子路也一定是從S到C1的最優(yōu)行駛路線; 假設 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)行駛路線. 而S到Ai(i=1,2,3)的最優(yōu)行駛路線是很容易得到的(實際上, 此例中S到Ai(i=1,2,3)只有唯一的道路),分析,此例中可把從S到T的行駛過程分成4個階段,即 SAi (i=1,2或3), Ai Bj(j=1或2), Bj Ck(k=1或2), Ck T. 記d(Y,X)為城市Y與城市X之間的直接距離(若這兩個城市之間沒有道路直接相連，則可以認為直接距離為)，用L(X)表示城市S到城市X的最優(yōu)行駛路線的路長:,本例的計算,所以, 從S到T的最優(yōu)行駛路線的路長為20. 進一步分析以上求解過程, 可以得到從S到T的最優(yōu)行駛路線為 S A3 B2 C1 T.,這種計算方法在數(shù)學上稱為動態(tài)規(guī)劃(Dynamic Programming),本例的LINGO求解,“CITIES”(城市):一個基本集合(元素通過枚舉給出),L:CITIES對應的屬性變量(我們要求的最短路長),“ROADS”(道路):由CITIES導出的一個派生集合(請?zhí)貏e注意其用法),由于只有一部分城市之間有道路相連，所以不應該把它定義成稠密集合，將其元素通過枚舉給出，這就是一個稀疏集合。,D:稀疏集合ROADS對應的屬性變量(給定的距離),本例的LINGO求解,從模型中還可以看出：這個LINGO程序可以沒有目標函數(shù)，這在LINGO中，可以用來找可行解(解方程組和不等式組)。,在數(shù)據(jù)段對L進行賦值，只有L(S)=0已知，后面的值為空(但位置必須留出來，即逗號“，”一個也不能少，否則會出錯)。如果這個語句直接寫成“L=0；”，語法上看也是對的，但其含義是L所有元素的取值全部為0，所以也會與題意不符。,本例的LINGO求解,雖然集合CITIES中的元素不是數(shù)字，但當它以CITIES(I)的形式出現(xiàn)在循環(huán)中時，引用下標I卻實際上仍是正整數(shù)，也就是說I指的正是元素在集合中的位置(順序)，一般稱為元素的索引(INDEX)。,在for循環(huán)中的過濾條件里用了一個函數(shù)“index”, 其作用是返回一個元素在集合中的索引值，這里index(S)=1(即元素S在集合中的索引值為1)，所以邏輯關(guān)系式“I#GT#index(S)”可以可以直接等價地寫成“I#GT#1” 。這里index(S)實際上還是index(CITIES,S)的簡寫，即返回S在集合CITIES中的索引值。,本例的LINGO求解結(jié)果,從S到T的最優(yōu)行駛路線的路長為20(進一步分析，可以得到最優(yōu)行駛路線為S A3 B2 C1 T)。,本例中定義稀疏集合ROADS的方法是將其元素通過枚舉給出，有時如果元素比較多，用起來不方便。另一種定義稀疏集合的方法是“元素過濾”法，能夠從笛卡兒積中系統(tǒng)地過濾下來一些真正的元素。,集合的使用小結(jié),集合的不同類型及其關(guān)系,運算符及其優(yōu)先級,算術(shù)運算符,加、減、乘、除、乘方等數(shù)學運算(即數(shù)與數(shù)之間的運算，運算結(jié)果也是數(shù))。 LINGO中的算術(shù)運算符有以下5種： +（加法）， （減法或負號）， *（乘法）， /（除法）， (求冪)。,邏輯運算符,運算結(jié)果只有“真”(TRUE)和“假”(FALSE)兩個值(稱為“邏輯值”)，LINGO中用數(shù)字1代表TRUE，其他值(典型的值是0)都是FALSE。 在LINGO中，邏輯運算(表達式)通常作為過濾條件使用,邏輯運算符有9種，可以分成兩類： #AND#(與),#OR#(或),#NOT#(非)：邏輯值之間的運算，它們操作的對象本身已經(jīng)是邏輯值或邏輯表達式，計算結(jié)果也是邏輯值。 #EQ#(等于),#NE#(不等于),#GT#(大于),#GE#(大于等于),#LT#(小于),#LE#(小于等于)：是“數(shù)與數(shù)之間”的比較,也就是它們操作的對象本身必須是兩個數(shù), 計算得到的結(jié)果是邏輯值。,關(guān)系運算符,表示是“數(shù)與數(shù)之間”的大小關(guān)系，在LINGO中用來表示優(yōu)化模型的約束條件。LINGO中關(guān)系運算符有3種： (即=，大于等于) (在優(yōu)化模型中約束一般沒有嚴格小于、嚴格大于關(guān)系),運算符的優(yōu)先級,變量定界函數(shù),對變量的取值范圍附加限制，共有以下四種： BND(L, X, U) ：限制L = X = U。 注意LINGO中沒有與LINDO命令SLB、SUB類似的函數(shù)SLB和SUB BIN(X) ：限制X為0或1。注意LINDO中的命令是INT，但LINGO中這個函數(shù)的名字卻不是INT(X) FREE(X)：取消對X的符號限制（即可取負數(shù)、0或正數(shù)） GIN(X)：限制X為整數(shù),LINGO的主要菜單命令,工具欄,File|Open （F3） 打開文件,File|Print （F7） 打印文件,Edit|Copy (Ctrl+C) 復制,Edit|Undo (Ctrl+Z) 取消操作,Edit|Find (Ctrl+F) 查找,LINGO|Solution (Alt+O)顯示解答,Edit|Match Parenthesis (Ctrl+P) 匹配括號,LINGO|Options (Ctrl+I) 選項設置,Window|Close All (Alt+X) 關(guān)閉所有窗口,Help|Contents （F1） 在線幫助,File|New （F2） 新建文件,File|Save (F4) 保存文件,Edit|Cut (Ctrl+X) 剪切,Edit|Paste (Ctrl+V) 粘貼,Edit|Redo (Ctrl+Y) 恢復操作,Edit | Go To Line (Ctrl+T) 定位某行,LINGO|Solve (Ctrl+S) 求解模型,LINGO|Picture (Ctrl+K) 模型圖示,Window|Send to Back (Ctrl+B) 窗口后置,Window|Tile (Alt+T) 平鋪窗口,上下文相關(guān)的幫助,文件(File)主菜單,File|Export File 優(yōu)化模型輸出到文件，有兩個子菜單，分別表示兩種輸出格式（都是文本文件）： MPS Format（MPS格式）：是IBM公司制定的一種數(shù)學規(guī)劃文件格式。 MPI Format（MPI格式）：是LINDO公司制定的一種數(shù)學規(guī)劃文件格式。 File|User Database Info 彈出對話框，用戶輸入用戶使用數(shù)據(jù)庫時需要驗證的用戶名（User ID）和密碼（Password），這些信息在使用ODBC()函數(shù)訪問數(shù)據(jù)庫時要用到。,編輯（Edit）主菜單,將WINDOWS剪貼板中的內(nèi)容粘貼到當前光標處。 “Edit|Paste（粘貼命令）” 僅用于剪貼板中的內(nèi)容是文本的情形。 “Edit|Paste Special （特殊粘貼命令）”可以用于剪貼板中的內(nèi)容不是文本的情形，可以插入其它應用程序中生成的對象（Object）或?qū)ο蟮逆溄樱↙ink）。 例如，LINGO模型中可能會在數(shù)據(jù)段用到從其它應用程序中生成的數(shù)據(jù)對象（如EXCEL電子表格數(shù)據(jù)），這時用“Edit|Paste Special ”是很方便的。,Edit|Paste 和Edit|Paste Special ,編輯（Edit）主菜單,Edit|Match Parenthesis,用于匹配模型中的括號： 如果當前沒有選定括號，則把光標移動到離當前光標最近的一個括號并選中這個括號。 當選定一個括號后，則把光標移動到與這個括號相匹配的括號并選中這個括號。,Edit|Paste Function,還有下一級子菜單和下下一級子菜單，用于按函數(shù)類型選擇LINGO的某個函數(shù)，粘貼到當前光標處。,編輯（Edit）主菜單,Edit|Select Font,彈出對話框，控制顯示字體、字形、大小、顏色、效果等。 注：這些顯示特性只有當文件保存為LINGO格式（*.LG4）的文件時才能保存下來。 此外，如果“按語法顯示色彩”選項是有效的(參見“LINGO|Options”)，在模型窗口中將不能通過“Edit|Select Font”菜單命令控制文本的顏色。,編輯（Edit）主菜單,Edit|Insert New Object,插入其它應用程序中生成的整個對象或?qū)ο蟮逆溄?。前面介紹過的“Edit|Paste Special ”與此類似，但“Paste Special”命令一般用于粘貼某個外部對象的一部分，而這里的命令是插入整個對象或?qū)ο蟮逆溄印?Edit|Links,在模型窗口中選擇一個外部對象的鏈接，然后選擇“Edit|Links（鏈接）”命令，則彈出一個對話框，可以修改這個外部對象的鏈接屬性。,編輯（Edit）主菜單,Edit|Object Properties,在模型窗口中選擇一個鏈接或嵌入對象（OLE），然后選擇“Edit|Object Properties（對象屬性）”命令，則彈出一個對話框，可以修改這個對象的屬性。主要包括以下屬性： display of the object：對象的顯示; the objects source: 對象的源; type of update (automatic or manual): 修改方式（自動或人工修改）； opening a link to the object：打開對象的一個鏈接； updating the object：修改對象； breaking the link to the object：斷開對象的鏈接。,LINGO系統(tǒng)(LINGO)主菜單,LINGO|LOOK（模型顯示）,模型窗口下才能使用，按照LINGO模型的輸入形式以文本方式顯示，顯示時對輸入的所有行(包括說明語句)按順序編號。將彈出一個對話框，在對話框中選擇“All”將對所有行進行顯示，也可以選擇“Selected”輸入起始行，這時只顯示相應行的內(nèi)容。,LINGO|Generate和LINGO|Picture,都是在模型窗口下才能使用，它們的功能是按照LINGO模型的完整形式（例如將屬性按下標（集合的每個元素）展開）顯示目標函數(shù)和約束（只有非零項會顯示出來）。,LINGO系統(tǒng)(LINGO)主菜單,LINGO|Generate,結(jié)果以代數(shù)表達式的形式給出，按照是否在屏幕上顯示結(jié)果的要求，可以選擇“Display model（Ctrl+G）”和“Dont display model（Ctrl+Q）”兩個子菜單供選擇。在屏幕上不顯示時，運行該命令的目的可能僅僅是為了以后選擇適當?shù)那蠼獬绦蚴褂谩?例如，選址問題， LINGO|Generate命令顯示的結(jié)果如圖。 注：在LINGO 8.0以及更早以前的版本中，如果有非線性變量項，對應的非線性變量前的系數(shù)將以問號（“？”）顯示。,LINGO系統(tǒng)(LINGO)主菜單,LINGO|Generate,結(jié)果按照矩陣形式以圖形方式給出。 例：選址問題， 該命令的結(jié)果如圖。 該顯示中非線性項的系數(shù)以黑色顯示為“？”，線性項的系數(shù)為正時顯示為蘭色，為負則為紅色(本例沒有紅色)。 在這個圖形上單擊鼠標右鍵，可以出現(xiàn)一個相關(guān)聯(lián)的顯示控制菜單(如圖中寫有“Zoom In”的菜單所示)，這個菜單可以控制圖形顯示的內(nèi)容的放大(Zoom In)、縮小(Zoom Out)、顯示全部內(nèi)容(View All),也可以控制該窗口是否顯示行名(Row Names)、變量名(Var Names)、滾動條(Scroll Bars)。,LINGO系統(tǒng)(LINGO)主菜單,LINGO|Options命令,打開一個含有7個選項卡的窗口,通過它修改LINGO系統(tǒng)的各種控制參數(shù)和選項。,新的設置生效,新的設置生效，并關(guān)閉窗口,當前設置變?yōu)槟J設置，下次啟動LINGO時這些設置仍然有效,恢復LINGO系統(tǒng)定義的原始默認設置(缺省設置),廢棄本次操作，退出對話框,顯示本對話框的幫助信息,LINGO|Options|Interface（界面）選項卡,錯誤信息對話框:如果選擇該選項，求解程序遇到錯誤時將打開一個對話框顯示錯誤，關(guān)閉該對話框后程序才會繼續(xù)執(zhí)行；否則，錯誤信息將在報告窗口顯示，程序仍會繼續(xù)執(zhí)行,彈出屏幕:如果選擇該選項，則LINGO每次啟動時會在屏幕上彈出一個對話框，顯示LINGO的版本和版權(quán)信息；否則不彈出,解的截斷:小于等于這個值的解將報告為“0” （缺省是10-9）,填充數(shù)據(jù)庫表:當LINGO向電子表（如EXCEL文件）或數(shù)據(jù)庫中輸出數(shù)據(jù)時，如果電子表或數(shù)據(jù)庫中用來接收收據(jù)的空間大于實際輸出的數(shù)據(jù)占用的空間，是否對多余的表空間進行數(shù)據(jù)填充？（缺省值為不進行填充）,LINGO|Options|Interface（界面）選項卡,狀態(tài)欄:如果選擇該選項，則LINGO系統(tǒng)在主窗口最下面一行顯示狀態(tài)欄；否則不顯示,狀態(tài)窗口:如果選擇該選項，則LINGO系統(tǒng)每次運行LINGO| Solve命令時會在屏幕上彈出狀態(tài)窗口；否則不彈出,工具欄:如果選擇該選項，則顯示工具欄；否則不顯示,簡潔輸出:如果選擇該選項，則LINGO系統(tǒng)對求解結(jié)果報告等將以簡潔形式輸出；否則以詳細形式輸出,LINGO|Options|Interface（界面）選項卡,LINGO擴展格式:模型文件的缺省保存格式是lg4格式（這是一種二進制文件，只有LINGO能讀出）,LINDO純文本格式:模型文件的缺省保存格式變?yōu)長INDO格式（純文本）,LINGO純文本格式:模型文件的缺省保存格式變?yōu)閘ng格式（純文本）,LINGO|Options|Interface（界面）選項卡,行數(shù)限制:語法配色的行數(shù)限制（缺省為1000）。LINGO模型窗口中將LINGO關(guān)鍵此顯示為蘭色，注釋為綠色，其他為黑色，超過該行數(shù)限制后則不再區(qū)分顏色。特別地，設置行數(shù)限制為0時，整個文件不再區(qū)分顏色。,括號匹配:如果選擇該選項，則模型中當前光標所在處的括號及其相匹配的括號將以紅色顯示；否則不使用該功能,延遲:設置語法配色的延遲時間（秒，缺省為0，從最后一次擊鍵算起）。,LINGO|Options|Interface（界面）選項卡,報告發(fā)送到命令窗口:如果選擇該選項，則輸出信息會發(fā)送到命令窗口；否則不使用該功能,輸入信息反饋:如果選擇該選項，則用File|Take Command命令執(zhí)行命令腳本文件時，處理信息會發(fā)送到命令窗口；否則不使用該功能,頁面大小限制:命令窗口每次顯示的行數(shù)的最大值為Length（缺省為沒有限制），顯示這么多行后會暫停，等待用戶響應；每行最大字符數(shù)為Width（缺省為74，可以設定為64-200之間），多余的字符將被截斷,行數(shù)限制:命令窗口能顯示的行數(shù)的最大值為Maximum（缺省為800）；如果要顯示的內(nèi)容超過這個值，每次從命令窗口滾動刪除的最小行數(shù)為Minimum（缺省為400）,LINGO|Options|General Solver(通用求解程序)選項卡,矩陣生成器的內(nèi)存限制:缺省值為32M，矩陣生成器使用的內(nèi)存超過該限制，LINGO將報告“The model generator ran out of memory“,運行限制: 迭代次數(shù):求解一個模型時，允許的最大迭代次數(shù)（缺省值為無限）,運行限制: 運行時間:求解一個模型時，允許的最大運行時間（秒）（缺省值為無限）,對偶計算:求解時控制對偶計算的級別，有三種可能的設置： None: 不計算任何對偶信息； Prices：計算對偶價格（缺省設置）； Prices and Ranges:計算對偶價格并分析敏感性; Prices, Opt Only: 只計算最優(yōu)行的對偶價格 。,LINGO|Options|General Solver(通用求解程序)選項卡,固定變量的歸結(jié)、簡化:求解前對固定變量的歸結(jié)程度（相當于預處理程度）： None：不歸結(jié)； Always：總是歸結(jié)； Not with global and multistart：在全局優(yōu)化和多初值優(yōu)化程序中不歸結(jié)。,模型的重新生成:控制重新生成模型的頻率，有三種可能的設置： Only when text changes：只有當模型的文本修改后才再生成模型； When text changes or with external references：當模型的文本修改或模型含有外部引用時（缺省設置）； Always：每當有需要時。,LINGO|Options|General Solver(通用求解程序)選項卡,線性化程度:決定求解模型時線性化的程度，有四種可能的設置： Solver Decides：若變量數(shù)小于等于12個，則盡可能全部線性化；否則不做任何線性化（缺省設置） None：不做任何線性化 Low：對函數(shù)ABS(), MAX(), MIN(), SMAX(), SMIN()，以及二進制變量與連續(xù)變量的乘積項做線性化 High：同上，此外對邏輯運算符#LE#, #EQ#, #GE#, #NE#做線性化,線性化的誤差限:設置線性化的誤差限（缺省值為10-6）,線性化的大M系數(shù):設置線性化的大M系數(shù)（缺省值為106）,LINGO|Options|General Solver(通用求解程序)選項卡,允許無限制地使用基本集合的成員名:選擇該選項可以保持與LINGO4.0以前的版本兼容：即允許使用基本集合的成員名稱直接作為該成員在該集合的索引值（LINGO4.0以后的版本要求使用INDEX函數(shù)）,檢查數(shù)據(jù)和模型中的名稱是否重復使用:選擇該選項,LINGO將檢查數(shù)據(jù)和模型中的名稱是否重復使用，如基本集合的成員名是否與決策變量名重復,檢查數(shù)據(jù)和模型中的名稱是否重復使用:選擇該選項,LINGO將檢查數(shù)據(jù)和模型中的名稱是否重復使用，如基本集合的成員名是否與決策變量名重復,最小化內(nèi)存使用量:是否最小化內(nèi)存使用量。缺省設置為“是”。使用這個功能的一個缺點是可能引起計算速度下降,LINGO|OPTIONS|Linear Solver(線性求解程序)選項卡,求解時的算法，有四種可能的設置： Solver Decides：LINGO自動選擇算法（缺省設置） Primal Simplex：原始單純形法 Dual Simplex：對偶單純形法 Barrier: 障礙法 (即內(nèi)點法),模型降維:控制是否檢查模型中的無關(guān)變量，從而降低模型的規(guī)模： Off：不檢查 On：檢查 Solver Decides：LINGO自動決定（缺省設置）,初始線性可行性誤差限:控制線性模型中約束滿足的初始誤差限（缺省值為3*10-6）.,最后線性可行性誤差限:控制線性模型中約束滿足的最后誤差限（缺省值為10-7）.,LINGO|OPTIONS|Linear Solver(線性求解程序)選項卡,原始單純形法:有三種可能的設置： Solver Decides：LINGO自動決定（缺省設置） Partial：LINGO 對一部分可能的出基變量進行嘗試 Devex：用Steepest-Edge（最陡邊）近似算法對所有可能的變量進行嘗試，找到使目標值下降最多的出基變量,對偶單純形法:有三種可能的設置： Solver Decides：LINGO自動決定（缺省設置） Dantzig：按最大下降比例法確定出基變量 Steepest-Edge：最陡邊策略，對所有可能的變量進行嘗試，找到使目標值下降最多的出基變量,價格策略（決定出基變量的策略）,LINGO|OPTIONS|Linear Solver(線性求解程序)選項卡,冷啟動時:設置LINGO|Debug命令調(diào)試所使用的程序（冷啟動的含義是不從當前基開始，而是從頭開始運行）。有四種可能的設置： Solver Decides：LINGO自動選擇算法(缺省設置) Primal Simplex：原始單純形法 Dual Simplex：對偶單純形法 Barrier: 障礙法 (即內(nèi)點法),熱啟動時同冷啟動（熱啟動的含義是從當前基開始運行）,調(diào)試時采用的求解程序,矩陣分解:選擇該選項，LINGO將嘗試將一個大模型分解為幾個小模型求解；否則不嘗試,檢查模型的數(shù)據(jù)平衡性:選擇該選項,LINGO檢查模型中的數(shù)據(jù)是否平衡（數(shù)量級是否相差太大）并嘗試改變尺度使模型平衡；否則不嘗試,LINGO|OPTIONS|Nonlinear Solver(非線性求解程序)選項卡,初始非線性可行性誤差限:控制模型中約束滿足的初始誤差限(缺省值為10-3),最后非線性可行性誤差限:控制模型中約束滿足的最后誤差限(缺省值為10-6),非線性規(guī)劃的最優(yōu)性誤差限:當目標函數(shù)在當前解的梯度小于等于這個值以后，停止迭代(缺省值為2*10-7),緩慢改進的迭代次數(shù)的上限:當目標函數(shù)在連續(xù)這么多次迭代沒有顯著改進以后，停止迭代(缺省值為5),非線性求解程序的版本:在個別情況下,可能老版本會更有效些,可能的選擇有: Solver Decides：LINGO自動選擇 (缺省設置，目前就是2.0版)； Ver 1.0：選擇1.0 版本； Ver 2.0：選擇2.0 版本。,LINGO|OPTIONS|Nonlinear Solver(非線性求解程序)選項卡,導數(shù)計算方式:設置導數(shù)計算方式,有5種選擇: Solver Decides：LINGO自動選擇 (缺省設置) Backward analytical：前向解析法計算導數(shù)； Forward analytical：前向解析法計算導數(shù) Central differences：中心差分法計算數(shù)值導數(shù) Forward differences：前向差分法計算數(shù)值導數(shù)。,生成初始解:選擇該選項, LINGO將用啟發(fā)式方法生成初始解;否則不生成(缺省值),識別二次規(guī)劃:選擇該選項, LINGO將判別模型是否為二次規(guī)劃，若是則采用二次規(guī)劃算法（包含在線性規(guī)劃的內(nèi)點法中）；否則不判別（缺省值）,策略,LINGO|OPTIONS|Nonlinear Solver(非線性求解程序)選項卡,SLP方向:選擇該選項, LINGO在每次迭代時用SLP (Successive LP，逐次線性規(guī)劃)方法尋找搜索方向(缺省值),有選擇地檢查約束:選擇該選項, LINGO在每次迭代時只檢查必須檢查的約束（如果有些約束函數(shù)在某些區(qū)域沒有定義，這樣做會出現(xiàn)錯誤）；否則，檢查所有約束（缺省值）,策略,最陡邊策略:選擇該選項, LINGO在每次迭代時將對所有可能的變量進行嘗試，找到使目標值下降最多的變量進行迭代；缺省值為不使用最陡邊策略,LINGO|OPTIONS|Integer Pre-Solver(整數(shù)預處理程序)選項卡,最小時間:每個分枝節(jié)點使用啟發(fā)式搜索的最小時間（秒）,水平:控制采用啟發(fā)式搜索的次數(shù)（缺省值為3，可能的值為0-100）. 啟發(fā)式方法的目的是從分枝節(jié)點的連續(xù)解出發(fā)，搜索一個好的整數(shù)解。,探測水平(級別):控制采用探測(Probing)技術(shù)的級別(探測能夠用于混合整數(shù)線性規(guī)劃模型，收緊變量的上下界和約束的右端項的值)。可能的取值為： Solver Decides：LINGO自動決定(缺省設置) 1-7：探測級別逐步升高。,啟發(fā)式方法,約束的割(平面),LINGO|OPTIONS|Integer Pre-Solver(整數(shù)預處理程序)選項卡,最大迭代檢查的次數(shù):為了尋找合適的割，最大迭代檢查的次數(shù)。,應用節(jié)點:控制在分枝定界樹中，哪些節(jié)點需要增加割（平面），可能的取值為： Root Only：僅根節(jié)點增加割（平面） All Nodes：所有節(jié)點均增加割（平面） Solver Decides：LINGO自動決定(缺省設置),相對上限:控制生成的割（平面）的個數(shù)相對于原問題的約束個數(shù)的上限（比值），缺省值