【文章內(nèi)容簡介】 11 1][][ ??? ??? ???????niniiiiiiiiiiiiniiiVlCwZGFCkZVVZ1 11)()()(? (3 13) ??????????????????????????????????????????????????????? ??????? ???10)203(,...,2,1。,...,2,10,0)193(,...,2,1)()183(,...2,1)173(,...,2,1)163(,...,2,1)153(,...,2,1143,...,2,1..1111 111或）（iijkininiimkiikimkljijkijniijnikkiZljmkxxniQGiFik i C iZiniPZniVZxnixxljMxmkAxts ? 4. 物流網(wǎng)絡布局問題的數(shù)學模型 牛頓法的基本思想 是用二次函數(shù)在極小點附近逼近)( xf，假設已得到極小的某個近似點 X(k)，將)( xf在 )( kx 作泰勒展開，略去二次以上的項得： )) . ((.)(21).()()()()()()(2)()()()( kkTkkTkTkxxxfxxxxxfxfxxf ????????? ? 取)( x?的極小點作為)( xf的極小點的下一個近似點 )1( ?kx 。由于)( x?是二次函數(shù)，極小點易求，即令梯度為零： ▽)( x?= ▽0)) . (()( )()(2)( ???? kkk xxxfxf 由此解得的 x 即為 )1( ?kx ，即 : )(()]([ )(1)()()(1)(2)()1( kkkkkkkxfxHxfxxfxx ?????????? 式中)( )( kxH為在點 )( kx 的 H e s s i a n 矩陣，此即為 牛頓法的迭代式。 求解方法 單目標優(yōu)化問題求解算法 ? 1．無約束優(yōu)化問題的牛頓法及其修正方法 ?牛頓法 阻尼牛頓法的迭代公式 為 : )()( )(1)()()()1( kkkkk xfxHxx ??? ?? ? 式中 )( k? 為迭代步長，由一維搜索方法確定，即 : )]([m i n]([ )(1)()(1)()( kkkkk xfHxfxfHxf ????? ?? ?? 阻尼牛頓法迭代步驟 如下 ： ①初始點)(0,0, )()0( kxfKx ?? ，計算＝令?； ②若 |)( )( kxf?| ≤ ? ， 停止 ， )(* kxx ? ；否則轉(zhuǎn)④ ③計算1)( )( ?kxH， 令)( )(1)( kk xfHS ??? ?； ④求)。(m i n)(m i n)(, )()()()()()()( kkkkkkk SxfxfSxf ??? ????使 ⑤令轉(zhuǎn),1,)()()()1( ????? KKSxx kkkk ?②； ?阻尼牛頓法 對等式約束問題 ),()(m i n 21 nxxxfxf ?? ..ts pjxh j ,3,2,1,0)( ??? 引入拉氏函數(shù) ??? )()(),( xhxfxL jj?? 可以轉(zhuǎn)化為求拉格朗日函數(shù)無約束的極值問題，這里特別說明兩點 ： ①為了便于在計算機上利用 直接尋優(yōu) 方法進行迭代計算，一般引 入? ????? 22 )]([)/( xhxLZ ji ),2,1。,2,1( pjni ?? ??函數(shù)，然后對 Z 函數(shù)求極小值，即可求得原問題的最優(yōu) 解。 ②對于不等式約束優(yōu)化問題，可設法引入松弛變量，使不等式變成等式。例如：對于下面不等式約束條件 g(X)=ax 1 + b x 2 +c ≥ 0 引入松弛變量 x 3 ，并為保證引入項為正值，均用松弛變量的平方，即有0)( 2321 ????? xcbxaxXg，其拉格朗日函數(shù)應為)()(),( XgXfXL ?? ??。 ? 2．拉格朗日乘子法 ① 給定初始點 X(0) ②構(gòu)成拉格朗日函數(shù) ),2,1。,2,1()()()(),( mupjXgXhXfXL uujj ?? ????? ? ? ??? ③構(gòu)成 Z 函數(shù)),2,1。,2,1。,2,1()()()/( 222 mupjniXgXhjxLZ ui ??? ???????? ?? ? ④按無約束優(yōu)化方法求解 Z 函數(shù)的無約束極值點 X*和極小值Z(X*) ，此即為原問題的最優(yōu)解。 ? 拉格朗日乘子法求約束優(yōu)化問題的計算步驟如下 ? 3．單純形法 ?基本思想 ? 單純形法是描述可行解從可行域的一個極點沿著可行域的邊界移到另一個相鄰的極點時，目標函數(shù)和基變量隨之變化的方法。 ?步驟 圖 單純形法的求解過程 考慮等式約束問題 其中，),2,1(, ljhf j ??是二次連續(xù)可微函數(shù)， nRx ? 運用乘子法，首先定義增廣拉格朗日函數(shù)（乘子懲罰函數(shù)）： ? ?? ????ljljjjjxhxhxfux1 12)(2)()(),(???? )()(2)()( xhxhxhxfTT ?? ??? 其中：0,))(,),(),(()(,),( 2121 ??? ????? TlT xhxhxhxhl ?? ),( ??? x與拉格朗日函數(shù)),( ?xL的區(qū)別在于增加了懲罰項)()(2xhxhT?, 而與懲罰函數(shù)的區(qū)別在于增加了乘子項))(( xhT??. 這種區(qū)別使得增廣拉格朗日函數(shù)與拉格朗日函數(shù)及懲罰函數(shù)具有不同的性態(tài)。對于),( ??? x，只要取足夠大的懲罰因子 ? ，不必趨向無窮大，就可以通過極小化),( ??? x求得問題的局部最優(yōu)解。 ? 4．非線性規(guī)劃及求解 ? 乘子法 多目標函數(shù)數(shù)學模型的一般表達式為： nTn Rxxxxx ?? ],[ 321 ? )(m i n)(m i n)(m i n21xfxfxfq? 受約束于： pjxhmixgji,2,1,0)(,2,1,0)(?????? 3 21 多目標函數(shù)的優(yōu)化方法 ? 1．統(tǒng)一目標法 將式（ 3 4 ）中的各個目標函數(shù)（或稱分目標函數(shù)）)(,),(),( 21 xfxfxf q? 統(tǒng)一到一個總的“統(tǒng)一目標函數(shù)” )( XF 中，即令： )}(,),(),({)(21 XfXfXffXf q?? 使式（ 3 21 ）的問題轉(zhuǎn)化為求解 nRXXf ?),(m i n pjXhmiXgtsji??,2,1,0)(,2,1,0)(..???? （ 1 ）加權(quán)組合法 式（ 3 20 ）則應改寫為： ? ?? ),2,1()()( qjXfwXf jj ? 式中 jw是第 j 項分目標函數(shù))( Xf j的加權(quán)因子，是一個大于零的數(shù)。此法的關(guān)鍵是加權(quán)因子的選擇。 （ 2 ）目標規(guī)劃法 先分別求出各個分目標函數(shù)的最優(yōu)值)( *xf j，然后根據(jù)多目標函數(shù)優(yōu)化設計的總體要求，作適當調(diào)整，制定出理想的最優(yōu)值)0(jf。則統(tǒng)一目標 函數(shù)可按如下的平方和法來構(gòu)成： ? ??? ),2,1()}0(/)]0()({[)( 2 qjffXfXf jjj ? 當各項分目標函數(shù)分別達到各自的理想最優(yōu)值)0(jf時，統(tǒng)一目標函數(shù))( Xf為最小。此法的關(guān)鍵在于選擇恰當?shù)?0(jf(j=1 ， 2 ， ? ， q) 值。 ? 極小化“統(tǒng)一目標函數(shù)”，為了使各個目標函數(shù)能均勻一致地趨向各自的最優(yōu)值，可采用的方法 （ 3 ）功效系數(shù)法 如果每個分目標函數(shù)),2,1)(( qjXf j ??都用一個稱為功效系數(shù)),2,1( qjj ???，并定義于10 ?? j?間的函數(shù)來表示該設計指標的好壞（當1?j?時表示最好 ， 0?j?時表示最壞），那么被稱作總功效系數(shù) η 的這些系數(shù)),( 21 q??? ?的幾何平均值 qqXf/121 ),()( ???? ??? 即表示該設計方案的好壞。因此，最優(yōu)設計方案應是： qq/121),( ???? ??直到 最大值 （ 4 ）乘除法 如果能將多目標函數(shù)優(yōu)化問題中的全部 q 個目標分為：目標函數(shù)法愈小愈好的所謂費用類（如材料、工時、成本、重量等）和目標函數(shù)值愈大愈好的所謂效益類（如產(chǎn)量、產(chǎn)值、利潤、效益等），且前者有 s 項 [ ∑ f i ( X ) ] ， ( i = 1 ，2 ， ? ， s) ，后者有 (q s) 項 [ ∑ f j ( X ) ] ， ( j = s + 1 ， s + 2 ， ? ， q) ，則統(tǒng)一目標函數(shù)可取為 : f ( X ) = ∑ f i ( X ) / ∑f j (X) 使 f(X) 直到 min 可得最優(yōu)解。 對式（ 3 20 ）中的 q 個分目標選出一個最重要的作為主要目標，例如選 f 1 (X) ，同時對其它 q 1 個分目標 f j ( X ) ( j ≠ 1) ，給出上下界值 : α j ≤ f j (X)≤ β j ， j ≠1 即限定這些分目標在一定范圍內(nèi)取值，把這些目標降為約束條件。于是，問題轉(zhuǎn)化為下列單目標優(yōu)化問題： min f 1 ( X ) . g i ( X ) ≤ 0 ， i=1 ， 2 ， ? ， m f j ( X ) β j ≤ 0 α j f j ( X ) ≤ 0 ， j=2 ， 3 ， ? ， q ? 2．主要目標法 設原問題是純整數(shù)線性規(guī)劃問題，并用單純形法對其松馳問題求解，且已獲得最優(yōu)單純形表。設在最優(yōu)表中，基變量為mxxx ?, 21，非基變量為nmm xxx ?, 21 ??，且最優(yōu)解中，基變量ix的取值 39。b 是分數(shù)，不滿足整數(shù)解的要求。由單純形表的迭代過程可知，單純形表第 i 行的數(shù)據(jù)代表如下的方程： 1)(2 139。39。?????nmjijijibxax （ 3 22 ） 把39。ib及39。ijb分別分解為兩部分： 2)(2 n ,2,m1,mj ,39。39。????????ijijijiiifNafNb （ 3 23 ） 其中，iji NN ,是整數(shù) nmmjfif ji ,2,1,10,10 ???????? 整數(shù)規(guī)劃及求解 ? 1．割平面法 將上述分解結(jié)果代入（ 3 5 ）式，經(jīng)過移項整理，可得 ? ??? ??????nmjnmjjijiijijixNNxxff1 1 （ 3 24 ） 顯然，當變量全部是整數(shù)量，（ 3 22 ）式的右端的計算結(jié)果必是整數(shù)，因而（ 3 22 ）式的左端也必等于整數(shù)。 注意到： 0,0 ?? jij xf ??????nmjijijifxff11 （ 3 25 ） 由于（ 3 23 ）式左端是整數(shù)，由（ 3 25 ）式，可知應是小于1 的整數(shù)，所以有 ?????nmjjijixff10 （ 3 26 ） （ 1 ）給定原問題的初始上界 z （ 2 ）給定原問題的初始下界z （ 3 ）將一個線性規(guī)劃問題分為兩枝 （ 4 ）分別求解上述一對分枝 ，某個分枝的可能情況： ①可行解：不必由此繼續(xù)分枝 ②到整數(shù)最優(yōu)解：不由此繼續(xù)分枝。 （ 5 ）修改原來的上、下界 結(jié)束準則：當所有 分枝均已查明，有 z