【正文】 : Model: min =T。 T = x13+ t13。 T = x23+ t23。 T = x33+ t33。 T = x43+ t43。 x11+ t11 = x12。 x12+ t12 = x13。 x21+ t21 = x22。 x22+ t22 = x23。 x31+ t31 = x32。 x32+ t32 = x33。 x41+ t41 = x42。 x42+ t42 = x43。 求解模型 這個模型可以如下輸入 LINGO： x11+ t11 x21= T*y12。 x21+ t21 x11= T*(1y12)。 x12+ t12 x22= T*y12。 x22+ t22 x12= T*(1y12)。 x13+ t13 x23= T*y12。 x23+ t23 x13= T*(1y12)。 x11+ t11 x31= T*y13。 x31+ t31 x11= T*(1y13)。 x12+ t12 x32= T*y12。 x32+ t32 x12= T*(1y13)。 x13+ t13 x33= T*y13。 x33+ t33 x13= T*(1y13)。 x11+ t11 x41= T*y14。 x41+ t41 x11= T*(1y14)。 x12+ t12 x42= T*y14。 x42+ t42 x12= T*(1y14)。 x13+ t13 x43= T*y14。 x43+ t43 x13= T*(1y14)。 x21+ t21 x31= T*y23。 x31+ t31 x21= T*(1y23)。 x22+ t22 x32= T*y23。 x32+ t32 x32= T*(1y23)。 x23+ t23 x33= T*y23。 x33+ t33 x23= T*(1y23)。 x21+ t21 x41= T*y24。 x41+ t41 x21= T*(1y24)。 x22+ t22 x42= T*y24。 x42+ t42 x22= T*(1y24)。 x23+ t23 x43= T*y24。 x43+ t43 x23= T*(1y24)。 x31+ t31 x41= T*y34。 x41+ t41 x31= T*(1y34)。 x32+ t32 x42= T*y34。 x42+ t42 x32= T*(1y34)。 x33+ t33 x43= T*y34。 x43+ t43 x33= T*(1y34)。 t11=13。 t12=15。 t13=20。 t21=10。 t22=20。 t23=18。 t31=20。 t32=16。 t33=10。 t41=8。 t42=10。 t43=15。 bin(y12)。 bin(y13)。 bin(y14)。 bin(y23)。 bin(y24)。 bin(y34)。 End 用 LINGO求解得到 ： Local optimal solution found at iteration: 4357 Objective value: Variable Value Reduced Cost T X13 T13 X23 T23 X33 T33 X43 T43 X11 T11 X12 T12 Variable Value Reduced Cost X21 T21 X22 T22 X31 T31 X32 T32 X41 T41 X42 T42 Y12 Y13 Y14 Y23 Y24 Y34 即所有面試完成至少需要 84分鐘，面試順序為 4123 (即丁 甲 乙 丙 )。早上 8:00面試開始，最早 9:24面試可以全部結(jié)束。 同樣，如果利用 LINGO的建模語言，可以編寫一個更一般的 LINGO模型。先準備一個數(shù)據(jù)文件 (文本文件 )，其中的內(nèi)容如下： ! 被面試者集合 。 1 2 3 4~ ! 面試階段的集合 。 1 2 3~ ! 已知的面試所需要的時間 。 13 15 20 10 20 18 20 16 10 8 10 15 ! 數(shù)據(jù)結(jié)束 。 LINGO模型如下： Model: Title 面試問題 。 SETS: ! Person = 被面試者集合 ， Stage = 面試階段的集合 。 Person/FILE()/。 Stage/FILE()/。 ! T = 已知的面試所需要的時間 ， X = 面試開始時間 。 PXS(Person,Stage): T, X。 ! Y(i,k) = 1: k排在 i前 ， 0：否則 。 PXP(Person,Person)|1 LT 2: Y。 ENDSETS DATA: T=FILE()。 ENDDATA [obj] min =MAXT。 ! MAXT是面試的最后結(jié)束時間 。 MAXT = max(PXS(i,j)|jEQsize(stage): x(i,j)+t(i,j))。 ! 只有參加完前一個階段的面試后才能進入下一個階段 。 for(PXS(i,j)|jLTsize(stage):[ORDER]x(i,j)+t(i,j)x(i,j+1))。 ! 同一時間只能面試 1名同學(xué) 。 for(Stage(j): for(PXP(i,k):[SORT1]x(i, j)+t(i, j)x(k,j)MAXT*Y(i,k) )。 for(PXP(i,k):[SORT2]x(k,j)+t(k,j)x(i, j)MAXT*(1Y(i,k)) )。 )。 for(PXP: bin(y))。 End 求解這個模型，得到的結(jié)果與前面的完全相同。 可以很清楚地看到，使用 LINGO建模語言的集合和屬性概念，得到的模型具有非常好的結(jié)構(gòu)性，反映了相應(yīng)的優(yōu)化模型的本質(zhì)，目標、決策變量、約束一清二楚，容易閱讀和理解，而且還可以讓數(shù)據(jù)與程序完全分離，這種優(yōu)越性是 LINDO軟件無法與之相比的。 消防車調(diào)度問題 例 某市消防中心同時接到了三處火警報告。根據(jù)當前的火勢，三處火警地點分別需要 2輛、 2輛和3輛消防車前往滅火。三處火警地點的損失將依賴于消防車到達的及時程度：記 tij為第 j輛消防車到達火警地點 i的時間 (分鐘 )，則三處火警地點的損失分別為 : 6t11+4t12， 7t21+3t22， 9t31+8t32+5t33。 目前可供消防中心調(diào)度的消防車正好有 7輛，分別屬于三個消防站 (可用消防車數(shù)量分別為 3輛、 2輛、2輛 )。消防車從三個消防站到三個火警地點所需要的時間如表 56所示。該公司應(yīng)如何調(diào)度消防車，才能使總損失最?。? 如果三處火警地點的損失分別為 : 4t11+6t12， 3t21+7t22， 5t31+8t32+9t33， 調(diào)度方案是否需要改變？ 消防站到三個火警地點所需要的時間 時間 (分鐘 ) 火警地點 1 火警地點 2 火警地點 3 消防站 1 6 7 9 消防站 2 5 8 11 消防站 3 6 9 10 問題分析 本題考慮的是為每個火警地點分配消防車的問題，初步看來與線性規(guī)劃中經(jīng)典的運輸問題有些類似。本題的問題可以看成是指派問題和運輸問題的一種變形，我們下面首先把它變成一個運輸問題建模求解。 決策變量 為了用運輸問題建模求解，很自然地把 3個消防站看成供應(yīng)點。如果直接把 3個火警地點看成需求點，我們卻不能很方便地描述消防車到達的先后次序，因此難以確定損失的大小。下面我們把 7輛車的需求分別看成 7個需求點 (分別對應(yīng)于到達時間 t11, t12, t21, t22, t31, t32, t33)。用 xi j表示消防站 i是否向第 j個需求點派車(1表示派車， 0表示不派車 )，則共有 21個 01變量。 決策目標 題目中給出的損失函數(shù)都是消防車到達時間的線性函數(shù)，所以由所給數(shù)據(jù)進行簡單的計算可知，如果消防站 1向第 6個需求點派車 (即消防站 1向火警地點 3派車但該消防車是到達火警地點 3的第二輛車 )，則由此引起的損失為 8*9=72。同理計算，可以得到損失矩陣 (元素分別記為 ci j)。 ci j 火警地點 1 火警地點 2 火警地點 3 j=1 j=2 j=3 j=4 j=5 j=6 j=7 消防站 i=1 36 24 49 21 81 72 45 消防站 i=2 30 20 56 24 99 88 55 消防站 i=3 36 24 63 27 90 80 50 于是，使總損失最小的決策目標為 ? ?? ?? 7131Minjijiij xcZ 約束條件 約束條件有兩類：一類是消防站擁有的消防車的數(shù)量限制，另一類是各需求點對消防車的需求量限制。 消防站擁有的消防車的數(shù)量限制可以表示為 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27 =2 x31+x32+x33+x34+x35+x36+x37=2 各需求點對消防車的需求量限制可以表示為 .7,6,5,4,3,2,1,131????jxi ij模型求解 將如上構(gòu)成的線性規(guī)劃模型輸入 LINDO： ! 消防車問題 Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17 +30x21+20x22+56x23+24x24+99x25+88x26+55x27 +36x31+24x32+63x33+27x34+90x35+80x36+50x37 SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3 x21+x22+x23+x24+x25+x26+x27 = 2 x31+x32+x33+x34+x35+x36+x37 = 2 x11+x21+x31 =1 x12+x22+x32 =1 x13+x23+x33 = 1 x14+x24+x34 =1 x15+x25+x35 =1 x16+x26+x36 = 1 x17+x27+x37 = 1 END