【文章內(nèi)容簡介】 地所決定的坐標(biāo)的最大、最小值決定的矩形之外，即 : =x=, =y=. 可以用 @bnd函數(shù)加上這個(gè)條件取代模型END上面的行，運(yùn)行NLP模型，全局最優(yōu)求解程序花費(fèi)的時(shí)間仍然很長，運(yùn)行 27分35秒時(shí)人為終止求解(按下“ Interrupt Solver”按鈕 )得到左邊模型窗口和全局求解器的狀態(tài)窗口 此時(shí)目標(biāo)函數(shù)值的下界（ Obj Bound=）與目前得到的最好的可行解的目標(biāo)函數(shù)值（ Best Obj=）相差已經(jīng)非常小，可以認(rèn)為已經(jīng)得到了全局最優(yōu)解。 計(jì)算結(jié)果 0 1 2 3 4 5 6 7 8 901234567835476112016工地與料場示意圖 : “*”表示料場，“ +”表示工地 可以認(rèn)為是模型的最后結(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)量 (噸公里 )。 稠密集合與稀疏集合 包含了兩個(gè)基本集合構(gòu)成的所有二元有序?qū)Φ呐缮戏Q為 稠密集合 (簡稱稠集 )。有時(shí)候，在實(shí)際問題中，一些屬性 (數(shù)組 ) 只在笛卡兒積的一個(gè)真子集合上定義，這種派生集合稱為 稀疏集合 (簡稱疏集 )。 例 4. (最短路問題 ) 在縱橫交錯(cuò)的公路網(wǎng)中，貨車司機(jī)希望找到一條從一個(gè)城市到另一個(gè)城市的最短路 . 下圖表示的是公路網(wǎng) , 節(jié)點(diǎn)表示貨車可以?？康某鞘?,弧上的權(quán)表示兩個(gè)城市之間的距離 (百公里 ). 那么 ,貨車從城市 S出發(fā)到達(dá)城市 T,如何選擇行駛路線 ,使所經(jīng)過的路程最短 ? S T A1 A2 A3 B1 B2 C1 C2 6 3 3 6 6 5 8 7 4 6 7 8 9 5 6 S T A1 A2 A3 B1 B2 C1 C2 6 3 3 6 6 5 8 7 4 6 7 8 9 5 6 分析 假設(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)行駛路線 . 而 S到 Ai(i=1,2,3)的最優(yōu)行駛路線是很容易得到的 (實(shí)際上 , 此例中 S到 Ai(i=1,2,3)只有唯一的道路 ) 分析 S T A1 A2 A3 B1 B2 C1 C2 6 3 3 6 6 5 8 7 4 6 7 8 9 5 6 此例中可把從 S到 T的行駛過程分成 4個(gè)階段 ,即 S→A i (i=1,2或 3), Ai → B j(j=1或 2), Bj → C k(k=1或 2), Ck → T. 記d(Y,X)為城市 Y與城市 X之間的直接距離 (若這兩個(gè)城市之間沒有道路直接相連，則可以認(rèn)為直接距離為 ∞)，用L(X)表示城市 S到城市 X的最優(yōu)行駛路線的路長 : ? ? ? ?? ? ? ? ? ?? ? ? ?0 。 1m in , , . 2YXLSL X L Y d Y X X S??? ? ?本例的計(jì)算 ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ?1 2 31 1 2 3 32 1 2 3 31 1 2 22 1 2 21 2 16 , 3 , 3 。m i n 6 , 8 , 7 10 7 。m i n 5 , 6 , 4 7 4 。m i n 6 , 8 15 8 。m i n 7, 9 16 9 。m i n 5 , 6 20 5.L A L A L AL B L A L A L A L AL B L A L A L A L AL C L B L B L BL C L B L B L BL T L C L C L C? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?S T A1 A2 A3 B1 B2 C1 C2 6 3 3 6 6 5 8 7 4 6 7 8 9 5 6 所以 , 從 S到 T的最優(yōu)行駛路線的路長為 20. 進(jìn)一步分析以上求解過程 , 可以得到從 S到 T的最優(yōu)行駛路線為 S→ A 3→ B 2→ C 1 → T. 這種計(jì)算方法在數(shù)學(xué)上稱為動(dòng)態(tài)規(guī)劃(Dynamic Programming) 本例的 LINGO求解 “CITIES”(城市 ):一個(gè)基本集合 (元素通過枚舉給出 ) L:CITIES對應(yīng)的屬性變量 (我們要求的最短路長 ) “ROADS”(道路 ):由 CITIES導(dǎo)出的一個(gè)派生集合 (請?zhí)貏e注意其用法 ),由于只有一部分城市之間有道路相連，所以不應(yīng)該把它定義成稠密集合，將其元素通過枚舉給出，這就是一個(gè)稀疏集合。 D:稀疏集合 ROADS對應(yīng)的屬性變量 (給定的距離 ) 本例的 LINGO求解 從模型中還可以看出：這個(gè) LINGO程序可以沒有目標(biāo)函數(shù)，這在 LINGO中，可以用來找可行解 (解方程組和不等式組 )。 在數(shù)據(jù)段對 L進(jìn)行賦值，只有 L(S)=0已知，后面的值為空 (但位置必須留出來，即逗號(hào)“，”一個(gè)也不能少，否則會(huì)出錯(cuò) )。如果這個(gè)語句直接寫成“ L=0；”，語法上看也是對的，但其含義是 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)系式“ IGT@index(S)”可以直接等價(jià)地寫成“ IGT1” 。這里 @index(S)實(shí)際上還是@index(CITIES,S)的簡寫，即返回 S在集合CITIES中的索引值。 本例的 LINGO求解結(jié)果 從 S到 T的最優(yōu)行駛路線的路長為 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ì)的效率如下表所示 (由于對稱性，只列出了嚴(yán)格上三角部分 )，問如何組隊(duì)可以使總效率最高？ 學(xué)生 S1 S2 S3 S4 S5 S6 S7 S8 S1 9 3 4 2 1 5 6 S2 1 7 3 5 2 1 S3 4 4 2 9 2 S4 1 5 5 2 S5 8 7 6 S6 2 3 S7 4 分析 這是一個(gè)匹配（ MATCHING）問題。把上表的效率矩陣記為 BENEFIT(由于對稱性，這個(gè)矩陣只有嚴(yán)格上三角部分共 28個(gè)數(shù)取非零值 )。 用 MATCH（ Si， Sj） =1表示同學(xué) Si， Sj組成一隊(duì) ，而MATCH（ Si， Sj） =0表示 Si， Sj不組隊(duì)。由于對稱性，只需考慮ij共 28個(gè) 01變量 (而不是全部 32個(gè)變量 )。 顯然 ,目標(biāo)函數(shù)正好是 BENEFIT(Si,Sj)*MATCH(Si,Sj)對 i,j之和。 約束條件是每個(gè)同學(xué)只能 (而且必須在 )某一組，即對于任意 i有 :只要屬性 MATCH的某個(gè)下標(biāo)為 i就加起來，此和應(yīng)該等于 1。 由上面的分析，因此，完整的數(shù)學(xué)模型如下 (顯然，這是一個(gè) 01線性規(guī)劃 )： ? ?? ?? ?31 } .{0)(21 , 2 , 3 , 4 ,I 1,)}(..1}),(),({II，或????????J , KM A TC HJ , KM A TC HtsJI* M A TC HJIB E N E F I TMinKJJI問題的 LINGO求解 “S1..S8”等價(jià)于寫成“ S1 S2 S3 S4 S5 S6 S7 S8”, 它沒有相關(guān)的屬性列表，只用于表示是一個(gè)下標(biāo)集合 在派生集合 PAIRS定義中增加了過濾條件 “ amp。2GTamp。1”,意思是第 2個(gè)父集合的元素的索引值 (用“ amp。2”表示 )大于第 1個(gè)父集合的元素的索引值 (用“ amp。1”表示 )。 PAIRS中的元素對應(yīng)于上表中的嚴(yán)格上三角部分的二維下標(biāo) (共 28個(gè)元素 )。BENEFIT和 MATCH是PAIRS的屬性。 注意數(shù)據(jù)段對 BENEFIT的賦值方式，“ LINGO按照列的順序?qū)傩宰兞康脑剡M(jìn)行賦值。在約束部分，過濾條件“ J EQ I 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)算次序。 LINGO求解結(jié)果 “LINGO|SOLVE”運(yùn)行這個(gè)程序，可以得到全局最優(yōu)值為 30 MATCH變量中多數(shù)為 0，可以更清晰地瀏覽最優(yōu)解。 選擇菜單命令“ LINGO|SOLUTION”，可以看到圖示對話框。 選擇屬性MATCH(變量 ) 選擇 Text(文本格式 ) 選擇 Nonzeros Only(只顯示非零值 ) 點(diǎn)擊“ OK”按鈕，得到關(guān)于最優(yōu)解的非零分量的報(bào)告 學(xué)生最佳的組隊(duì)方式是 (1,8),(2,4),(3,7),(5,6). 集合的使用小結(jié) 集合的不同類型及其關(guān)系 集合 派生集合 稀疏集合 稠密集合 基本集合 元素列表法 元素過濾法 直接列舉法 隱式列舉法 基本集合的定義語法 基本集合的定義格式為 (方括號(hào)“ [ ]”中的內(nèi)容是可選項(xiàng) , 可以沒有 ): setname [/member_list/] [: attribute_list]。 其中 setname為定義的集合名， member_list為元素列表，attribute_list為屬性列表。元素列表可以采用顯式列舉法 (即直接將所有元素全部列出 ,元素之間用逗號(hào)或空格分開 ),也可以采用隱式列舉法。隱式列舉法可以有幾種不同格式， 類型 隱式列舉格式 示例 示例集合表示的元素 數(shù)字型 1..n 1..5 1, 2, 3, 4, 5 字符 數(shù)字型 stringM..stringN Car101..car208 Car101, car102, … , car208 日期（星期）型 dayM..dayN MON..FRI MON, TUE, WED, THU, FRI 月份型 monthM..monthN OCT..JAN OCT, NOV, DEC, JAN 年份 月份型 monthYearM..monthYearN OCT2022..JAN2022 OCT2022, NOV2022, DEC2022, JAN2022 元素列表和屬性列表都是可選的。 當(dāng)屬性列表不在集合定義中出現(xiàn)時(shí)，這樣的集合往往只是為了將來在程序中作為一個(gè)循環(huán)變量來使用 ,或者作為構(gòu)造更復(fù)雜的派生集合的父集合使用 (匹配問題中的集合 STUDENTS沒有屬性列表 )。 而當(dāng)元素列表不在基本集合的定義中出現(xiàn)時(shí) ,則必須在程序的數(shù)據(jù)段以賦值語句的方式直接給出元素列表。