【正文】 記早上 8： 00面試開始為 0時刻 )(i=1, 2, 3, 4； j=1, 2, 3)， T為完成全部面試所花費的最少時間。 優(yōu)化目標為 ? ?? ?33MaxMin iii txT ?? 優(yōu)化建模 a. 時間先后次序約束 (每人只有參加完前一個階段的面試后才能進入下一個階段 )： xij+ tij ?xi， j+1 (i=1, 2, 3, 4； j=1, 2) j同一時間只能面試 1名同學：用 01變量 yik表示第 k名同學是否排在第 i名同學前面 (1表示是，0表示否 )，則 xij+ tij–xkj?Tyik (i, k=1, 2, 3, 4。 j=1, 2, 3。 ik) xkj+ tkj–xij?T(1–yik) (i, k=1, 2, 3, 4。 j=1, 2, 3。 ik) 約束條件： 優(yōu)化建模 可以將非線性的優(yōu)化目標改寫為如下線性優(yōu)化目標： Min T . T ? x13+ t13 T ? x23+ t23 T ? x33+ t33 T ? x43+ t43 優(yōu)化建模 Min T . xij+ tij ?xi, j+1 (i=1, 2, 3, 4； j=1, 2) xij+ tij–xkj?Tyik (i, k=1, 2, 3, 4。 j=1, 2, 3。 ik) xkj+ tkj–xij?T(1–yik) (i, k=1, 2, 3, 4。 j=1, 2, 3。 ik) xi3+ ti3?T (i=1, 2, 3, 4) 這個問題的 01非線性規(guī)劃模型 (當然所有變量還有非負約束，變量 yik還有 01約束 ) : 優(yōu)化建模 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： 優(yōu)化建模 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)。 優(yōu)化建模 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)。 優(yōu)化建模 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。 優(yōu)化建模 bin(y12)。 bin(y13)。 bin(y14)。 bin(y23)。 bin(y24)。 bin(y34)。 End 優(yōu)化建模 用 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 優(yōu)化建模 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é)束。 優(yōu)化建模 同樣，如果利用 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é)束 。 優(yōu)化建模 LINGO模型如下： 0505b 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 優(yōu)化建模 [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名同學 。 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 優(yōu)化建模 求解這個模型，得到的結(jié)果與前面的完全相同。 可以很清楚地看到，使用 LINGO建模語言的集合和屬性概念，得到的模型具有非常好的結(jié)構(gòu)性，反映了相應的優(yōu)化模型的本質(zhì)，目標、決策變量、約束一清二楚，容易閱讀和理解，而且還可以讓數(shù)據(jù)與程序完全分離，這種優(yōu)越性是 LINDO軟件無法與之相比的。 優(yōu)化建模 消防車調(diào)度問題 例 某市消防中心同時接到了三處火警報告。根據(jù)當前的火勢，三處火警地點分別需要 2輛、 2輛和3輛消防車前往滅火。三處火警地點的損失將依賴于消防車到達的及時程度：記 tij為第 j輛消防車到達火警地點 i的時間 (分鐘 )，則三處火警地點的損失分別為 : 6t11+4t12， 7t21+3t22， 9t31+8t32+5t33。 目前可供消防中心調(diào)度的消防車正好有 7輛，分別屬于三個消防站 (可用消防車數(shù)量分別為 3輛、 2輛、2輛 )。消防車從三個消防站到三個火警地點所需要的時間如表 56所示。該公司應如何調(diào)度消防車，才能使總損失最??？ 優(yōu)化建模 如果三處火警地點的損失分別為 : 4t11+6t12， 3t21+7t22， 5t31+8t32+9t33， 調(diào)度方案是否需要改變？ 消防站到三個火警地點所需要的時間 時間 (分鐘 ) 火警地點 1 火警地點 2 火警地點 3 消防站 1 6 7 9 消防站 2 5 8 11 消防站 3 6 9 10 優(yōu)化建模 問題分析 本題考慮的是為每個火警地點分配消防車的問題，初步看來與線性規(guī)劃中經(jīng)典的運輸問題有些類似。本題的問題可以看成是指派問題和運輸問題的一種變形，我們下面首先把它變成一個運輸問題建模求解。 決策變量 為了用運輸問題建模求解，很自然地把 3個消防站看成供應點。如果直接把 3個火警地點看成需求點，我們卻不能很方便地描述消防車到達的先后次序，因此難以確定損失的大小。下面我們把 7輛車的需求分別看成 7個需求點 (分別對應于到達時間 t11, t12, t21, t22, t31, t32, t33)。用 xi j表示消防站 i是否向第 j個需求點派車(1表示派車， 0表示不派車 )，則共有 21個 01變量。 優(yōu)化建模 決策目標 題目中給出的損失函數(shù)都是消防車到達時間的線性函數(shù)，所以由所給數(shù)據(jù)進行簡單的計算可知，如果消防站 1向第 6個需求點派車 (即消防站 1向火警地點 3派車但該消防車是到達火警地點 3的第二輛車 )，則由此引起的損失為 8*9=72。同理計算，可以得到損失矩