【正文】 記早上 8： 00面試開始為 0時(shí)刻 )(i=1, 2, 3, 4； j=1, 2, 3)， T為完成全部面試所花費(fèi)的最少時(shí)間。 優(yōu)化目標(biāo)為 ? ?? ?33MaxMin iii txT ?? 優(yōu)化建模 a. 時(shí)間先后次序約束 (每人只有參加完前一個(gè)階段的面試后才能進(jìn)入下一個(gè)階段 )： xij+ tij ?xi， j+1 (i=1, 2, 3, 4； j=1, 2) j同一時(shí)間只能面試 1名同學(xué)：用 01變量 yik表示第 k名同學(xué)是否排在第 i名同學(xué)前面 (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)化目標(biāo)改寫為如下線性優(yōu)化目標(biāo)： 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) 這個(gè)問(wèn)題的 01非線性規(guī)劃模型 (當(dāng)然所有變量還有非負(fù)約束，變量 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。 求解模型 這個(gè)模型可以如下輸入 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分鐘，面試順序?yàn)?4123 (即丁 甲 乙 丙 )。早上 8:00面試開始，最早 9:24面試可以全部結(jié)束。 優(yōu)化建模 同樣，如果利用 LINGO的建模語(yǔ)言，可以編寫一個(gè)更一般的 LINGO模型。先準(zhǔn)備一個(gè)數(shù)據(jù)文件 (文本文件 )，其中的內(nèi)容如下： ! 被面試者集合 。 1 2 3 4~ ! 面試階段的集合 。 1 2 3~ ! 已知的面試所需要的時(shí)間 。 13 15 20 10 20 18 20 16 10 8 10 15 ! 數(shù)據(jù)結(jié)束 。 優(yōu)化建模 LINGO模型如下： 0505b Model: Title 面試問(wèn)題 。 SETS: ! Person = 被面試者集合 ， Stage = 面試階段的集合 。 Person/FILE()/。 Stage/FILE()/。 ! T = 已知的面試所需要的時(shí)間 ， X = 面試開始時(shí)間 。 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é)束時(shí)間 。 MAXT = max(PXS(i,j)|jEQsize(stage): x(i,j)+t(i,j))。 ! 只有參加完前一個(gè)階段的面試后才能進(jìn)入下一個(gè)階段 。 for(PXS(i,j)|jLTsize(stage):[ORDER]x(i,j)+t(i,j)x(i,j+1))。 ! 同一時(shí)間只能面試 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 優(yōu)化建模 求解這個(gè)模型，得到的結(jié)果與前面的完全相同。 可以很清楚地看到，使用 LINGO建模語(yǔ)言的集合和屬性概念，得到的模型具有非常好的結(jié)構(gòu)性，反映了相應(yīng)的優(yōu)化模型的本質(zhì)，目標(biāo)、決策變量、約束一清二楚，容易閱讀和理解，而且還可以讓數(shù)據(jù)與程序完全分離，這種優(yōu)越性是 LINDO軟件無(wú)法與之相比的。 優(yōu)化建模 消防車調(diào)度問(wèn)題 例 某市消防中心同時(shí)接到了三處火警報(bào)告。根據(jù)當(dāng)前的火勢(shì)，三處火警地點(diǎn)分別需要 2輛、 2輛和3輛消防車前往滅火。三處火警地點(diǎn)的損失將依賴于消防車到達(dá)的及時(shí)程度：記 tij為第 j輛消防車到達(dá)火警地點(diǎn) i的時(shí)間 (分鐘 )，則三處火警地點(diǎn)的損失分別為 : 6t11+4t12， 7t21+3t22， 9t31+8t32+5t33。 目前可供消防中心調(diào)度的消防車正好有 7輛，分別屬于三個(gè)消防站 (可用消防車數(shù)量分別為 3輛、 2輛、2輛 )。消防車從三個(gè)消防站到三個(gè)火警地點(diǎn)所需要的時(shí)間如表 56所示。該公司應(yīng)如何調(diào)度消防車，才能使總損失最??？ 優(yōu)化建模 如果三處火警地點(diǎn)的損失分別為 : 4t11+6t12， 3t21+7t22， 5t31+8t32+9t33， 調(diào)度方案是否需要改變？ 消防站到三個(gè)火警地點(diǎn)所需要的時(shí)間 時(shí)間 (分鐘 ) 火警地點(diǎn) 1 火警地點(diǎn) 2 火警地點(diǎn) 3 消防站 1 6 7 9 消防站 2 5 8 11 消防站 3 6 9 10 優(yōu)化建模 問(wèn)題分析 本題考慮的是為每個(gè)火警地點(diǎn)分配消防車的問(wèn)題，初步看來(lái)與線性規(guī)劃中經(jīng)典的運(yùn)輸問(wèn)題有些類似。本題的問(wèn)題可以看成是指派問(wèn)題和運(yùn)輸問(wèn)題的一種變形，我們下面首先把它變成一個(gè)運(yùn)輸問(wèn)題建模求解。 決策變量 為了用運(yùn)輸問(wèn)題建模求解，很自然地把 3個(gè)消防站看成供應(yīng)點(diǎn)。如果直接把 3個(gè)火警地點(diǎn)看成需求點(diǎn)，我們卻不能很方便地描述消防車到達(dá)的先后次序，因此難以確定損失的大小。下面我們把 7輛車的需求分別看成 7個(gè)需求點(diǎn) (分別對(duì)應(yīng)于到達(dá)時(shí)間 t11, t12, t21, t22, t31, t32, t33)。用 xi j表示消防站 i是否向第 j個(gè)需求點(diǎn)派車(1表示派車， 0表示不派車 )，則共有 21個(gè) 01變量。 優(yōu)化建模 決策目標(biāo) 題目中給出的損失函數(shù)都是消防車到達(dá)時(shí)間的線性函數(shù)，所以由所給數(shù)據(jù)進(jìn)行簡(jiǎn)單的計(jì)算可知，如果消防站 1向第 6個(gè)需求點(diǎn)派車 (即消防站 1向火警地點(diǎn) 3派車但該消防車是到達(dá)火警地點(diǎn) 3的第二輛車 )，則由此引起的損失為 8*9=72。同理計(jì)算，可以得到損失矩