華東理工運籌學

第一§1第一§1運籌學的產(chǎn)生與發(fā)前國際上比較公認的觀點是運籌學產(chǎn)生于第二次世界大戰(zhàn)前后。1937年英國部分科有限雷達的效用，以應對德軍的空襲。1938年波德塞（Bawdsey）雷達站的負責人由來。1939了一個由布萊開特（P.M.S.Blacket）領導的軍事科技攻關小組；由于其成員學科擴展到對軍事戰(zhàn)略性問題的研究。由于科學家的天賦、戰(zhàn)爭的需要以及不同學科的得運籌學在整個軍事領域迅速傳播，到1941年英國皇家陸、海、空三軍都成立了這樣的科學小組。比較典型的論題包括雷達布置策略、反空襲系統(tǒng)控制、海軍艦隊的編制和對敵潛艇的探測等。O.R.小組巨大成就所顯示出的神奇力量，促使其他盟究小組的工作為“OperationsResearch11948年英1948年英1952年成立，它的宗旨是滿足運籌學SocietiesIFORS國際上已有38個國家和地區(qū)成立了運籌學學會或類似的組織。60年代以來，運籌學得到了迅速的普及和發(fā)展。運籌學細分為許多分支，許多1956年在中國科學院力學研究所成立，1958年成立了運籌學研究室。1960年在濟南召開了全國應用運籌學的經(jīng)驗交流和推廣會議，19621978年先后在北京和成都召開了全國運籌學§2運籌學的內(nèi)2§3運籌學模模型在某種意義上說是客觀事物的簡化與抽象，是研究者經(jīng)過思維抽象象的系統(tǒng)稱為現(xiàn)實系統(tǒng)§3運籌學模模型在某種意義上說是客觀事物的簡化與抽象，是研究者經(jīng)過思維抽象象的系統(tǒng)稱為現(xiàn)實系統(tǒng)11求解單的描述為：用字母、數(shù)字和運算符來精確地反映變量之間相互關系的式子或式子組決策變量約束條件和目標函數(shù)思考題3第二性規(guī)第二性規(guī),§1線性規(guī)劃的數(shù)學模4資 設決策變x1x2分別表示在計劃期內(nèi)產(chǎn)設決策變x1x2分別表示在計劃期內(nèi)產(chǎn)品甲、乙的產(chǎn)量，此模型的約束條x12x24x14x2maxZ2x1x1+2x244x25A 8 x1，x2[2-2]8x1，x2[2-2]810名。此公司每天（8驗的準確率98％，每小時的工資4元；二級檢驗人員每小時可檢驗工15個，檢驗的準確率為95％，每小時的工資為3元；檢驗人員每出現(xiàn)一次錯檢，將給公司設決策變x1x2分別表示安排質(zhì)檢的一級、二級檢驗人員的數(shù)量，此模x1x25x1+3x2人員的工資和錯檢所造成的損失兩部分；因此，問題的目標函數(shù)可表示為minZ40x1x25 +3x2x1，x2線性規(guī)劃數(shù)學模型6max(min)Zc1x1c2max(min)Zc1x1c2x2cna11x1a12x2a1nxn(,a21x1a22x2a2nxn(,am1x1am2x2amnxn(,x1,x2,,xnAX(,X1n階價值系數(shù)矩陣（行向量，Xn1階決策變量矩陣（列向量§2線性規(guī)劃的圖解7決策變量的一組取值便構成了線性規(guī)劃問題的一個解；滿足約束條件（決策變量的一組取值便構成了線性規(guī)劃問題的一個解；滿足約束條件（包括；；約束條件x1+2x28要求問題的可行解位于直線x1+2 8的左（0，4每一個點（有無數(shù)多個）都是一個可行解。我們的目標是確定使目標函數(shù)Z2x13x2達到最大值的最優(yōu)解Z2x13x2x2xzZ023 x2x23xzZ值（截距）313B就是目標函數(shù)直線脫離可行域前經(jīng)過的最后一點，即68545x1+3x5x1+3x2455x1+3x245x X50592-22-2唯一最優(yōu)解（上述兩例的最優(yōu)解都是唯一的4CDB21123唯一最優(yōu)解（上述兩例的最優(yōu)解都是唯一的4CDB21123 78oA2-344211 5678o2-45421123 78o2-53、45421123 78o2-53、4兩種情況時，一般說明線性規(guī)劃問集合中任意兩點的線性組合仍然屬于該集合的集合稱為凸集，圖2-6（a（b）（c2-6介紹一種求解線性規(guī)劃的代數(shù)法——單純形法§3線性規(guī)劃的§3線性規(guī)劃的單純形3.1線性規(guī)劃問題的標準形（min限定為最小化；（4）AXbX0b1.無約束變量的處100syzy、zsyz的相對大小。用yzsxyz1001”即可。如maxZ2x13x2可以轉(zhuǎn)換為minW2x13x2Z和W絕4．負約束條件右端項的處即可將約束條件右端項轉(zhuǎn)換為非負。例如：x1-2x2-8x1+2x2-2x2x3-8可轉(zhuǎn)換x1+2x2x38maxZx12x2x1x2x3x1x2x33x1x22x3x10，0x3無約x3x4x5x4x50；1minWx12x23x4x1x2x4x5x6x1x2x4x5x73x1x22x42x5x1，x2，x4，x5，x6，x73.2單純形原AXbX0ba1nAXbX0ba1na2n mnaa其秩為mBmmAmn中的一個滿秩子陣（Bp1,p2,,系數(shù)矩陣Amn的秩為m，因為總可以使nm（因針對每一個約束條件都可以加有無窮多個解。若假設所有的非基變量均取零，那么該方程組相當于一個具有mmX(x1x2,xm,0,,0)T，我們圖2-7加以表示?？尚?基可行 基maxz2x13x20x30x4maxz2x13x20x30x4++++xj0，j06100010A0) 03BA3Bp, 時可x1x2為非基變量。令非基變量x1=x2=0，可求得關于x3x4x5的一為非負，故它同時又是一個基可行解；當然，與此基可行解對應的基B是一個可行.B.ag環(huán)實質(zhì)是從可行域中的某一基可行解開始，轉(zhuǎn)換到另一個基可行解，并且使目標函若線性規(guī)劃問題存在最優(yōu)解，它一定能在可行域的頂點上得到線性規(guī)劃問題的基可行解與其可行域的頂點一一對應們不難得到“若線性規(guī)劃問題存在最優(yōu)解，它一定能在基可行解中得到”單純形法的基本步驟可以概括為：（1）尋找一個基可行解并將其作為初始的基可行解；（2）單純形法的基本步驟可以概括為：（1）尋找一個基可行解并將其作為初始的基可行解；（2）判別該基可行解是否是最優(yōu)解，如果是最優(yōu)解求解過程結(jié)束，如果不是最優(yōu)解就轉(zhuǎn)換到另一個能使目標函數(shù)值變優(yōu)的基可行解；（3）將新的基可行解作無界解minw2x13x20x30x4+2+84+x54+x1，x2，x3，x4，x5x3x4x5是基變量。選擇初始基為單位矩陣等價于為每一約束方程選取一個210minw2x13x20x30x4+2++x5x1+244的非基變量中選擇。選擇可以通過使非基變量的值增加一個單位（0變化效果。因為我們只對相鄰的基可行解感興趣，所以非基變量 的取值仍為零x11x20代入式（2-2、式（2-3）（2-4），可得一個可行解w(2)(0)“ ”的基變量用非基變量加以表示，再代入目標函數(shù)消去基變量即可此函數(shù)minw2x13x20x30x4按上述結(jié)論很容易得到12,23,345012x112個單位；而23的遞減速度所以選取 為入基變量即選擇負檢驗數(shù)中絕對的遞減速度所以選取 為入基變量即選擇負檢驗數(shù)中絕對值最大的非基變量自然我們應盡可能地增加 的值以便使目標函數(shù)得到最大程度的減少對2x2的取值超過4x3將為負值。同理，從式（2-4）可以看出，當x2的取值3x5將為負值；從式（2-3）可知x2的增加并末引起x4的減少x4)min( （22 束方程中入基變量的系數(shù)是負數(shù)或零，如式（2-3），當入基變量增加時，相應將率先減少為零成為出基變量。在式（2-4）這一約束條件中，非基變 將替而成為基變量。為獲得新的基可行解進行如下初等變2．將式（2-8）代入式（2-2）消去式（2-2）中的x2，得到式（2-4．將式（2-8）代入式（2-1）消去式（2-1）中的x2，得到式（2-5minw2x10x20x30x4 x34 35+1241+34minw0x10x22x0xx1 531+34minw0x10x22x0xx1 53x15+x2再次用上述方法確定入、出基變量，即選取x1為入基變量，x3為出基變量向量，可得如式（2-9）~式（2-12）所示的另一個新的基可行解 各變量的系數(shù)可知， 仍不是最優(yōu)解（2-13）~式（2-16）所示的另一個新的基可行解 X(4,2,0,0,4)Tw(3)14。根據(jù)式（2-中各變量的系數(shù)可知， 就是最優(yōu)解minw0x10x2 xx0x3134528x1+ 5x2142x3121x31 12+14這樣可以使計劃期內(nèi)獲得14個單位的最大利潤。minw2x14x20x30x4這樣可以使計劃期內(nèi)獲得14個單位的最大利潤。minw2x14x20x30x4+82+x5+x1，x2，x3，x4，x5X(0)(0,0,8,16,12)T、w(0)02基變量為出基變對入基變量進行適當?shù)淖儞Q（2-21）~（2-X(1)(0,3,2,16,0)Tw(1)12minw2x10x20x30x4x5+35+x2選取x1為入基變量，x3為出基變量；對入基變量進行適當?shù)淖儞Q，可以得X(2)(2,3,0,8,0)T12+144x1+24416minw0x10x22x30x40x516minw0x10x22x30x40x5x135+x2根據(jù)式（2-25）中各變量的系數(shù)可知， 就是最優(yōu)解。對比式（2-25）和（2-13），所不同的是式（2-25）中非基變的檢驗數(shù)為0”，恰恰是這說明此題有無窮多最優(yōu)解。非基變x5的檢驗數(shù)為“0”，說x5增加（入基）可保持目標值不變，既然目前的目標值是最優(yōu)值，那么x5增加（入基）后的目標值maxZx12x22x1x22x33x1x24x3x1,x2,x3minwx12x22x1x22x3x43x1x24x3x5x1,x2,x3,x4,x512+14+X(0)(0,0,0,10,12)T、w(0)0x3基變X(0)(0,0,0,10,12)T、w(0)0x3基變量，而在選取出基變量時“最小比率”規(guī)則失效。由于在式（2-30）和式即原有基變量并不對入基變量的增加幅度有任何限制。由增加1個單位，目3個單位（33x3件變?yōu)椤罢龣z驗數(shù)中數(shù)值最大的檢驗數(shù)所對應的決策變量3.3單純形minw2x13x20x30x42-1+2++x5x1,x2,x3,x4,x52-1 b 00 8x1+244xj的檢驗數(shù)，這里有：jcjxj的檢驗數(shù)，這里有：jcjCBPj12(010400)23(020004)X(0)(0,0,8,16,12)Tw(0)033x將取代哪一個基變量，即min{ 2 標記，如表2-1中第三行第二列的“4]”。然后進行兩步初等變換：（1）用主元素除基準行使主元素變12）主元素同列的其他元素變?yōu)?。因為1202-2Xx1為入基變量并利用“最小比率”規(guī)則確定出基變量。通過上述初等變解。確 b 00 23 0 X(2)(2,3,0,8,0)Tw(3)14綜上X(2)(2,3,0,8,0)Tw(3)14綜上所述，單純形表求解線性規(guī)劃的一般步驟可概括為：（1）寫出問題的標準（4（537步稱為單純形法的迭代（循環(huán)的初等變換，每次迭代都給出了minw2x14x20x30x4+2++x5x1+244 b 0 442 b 0 283 x1,x2,x3,x4,x52-6X(2,3,0,8,0)T0j1,2,,5jx1,x2,x3,x4,x52-6X(2,3,0,8,0)T0j1,2,,5jminwx12x22x1x22x3x4 b 0 442 b 0 283 b 000 8 00 23 3x1x24x3x5x1,x2,x3,x4,3x1x24x3x5x1,x2,x3,x4,x5x3為入基變量，在確定出基變量時“最小比率”規(guī)則失效，入基變量x3(2,4)T3.4人工變量LP模型轉(zhuǎn)化為標準形式，即所有的變量均為非負、所有約束條件為等minw3x1x2x12x2x34x1x22x32x1x3x1,x2,x3 b 00 - minw3x1x2x30x4 -2minw3x1x2x30x4 -2x2+x3+-4x1+23-2+x1,x2,x3,x4,x5式（2-33）中松弛變量x4可以作為基變量，而在其它兩個約束中均不存在x6、量。在式（2-34）和式（2-35）中分別加入非負的人工變，可得如下的 -2x2+++ +x7-4x1+2-2+x1,x2,x3,x4,x5,x6,x7)M最小化問題時，一般用字母“M”來表示這一費用系數(shù)，而在最大化問題中，用M”來表示收益系數(shù)。在此“M”是一個充分大的正數(shù)。為了演示大“M”法的具較大的費用系數(shù)，因此目標函數(shù)變minz3x1x2x30x4較大的費用系數(shù)，因此目標函數(shù)變minz3x1x2x30x40x5Mx6始系統(tǒng)的一個基可行解，而非最優(yōu)解。繼續(xù)迭代一步，得到原始系統(tǒng)的最優(yōu)解X4,1,9,0,0)Tw2沒有再次入基的可能。用“大M法”求解LP問題，如果在所有變量的檢驗數(shù)均為 b 0 11 1- 011 11 M- b 0 31 minwx12x22x1x2x32x1minwx12x22x1x2x32x1x2x3x1,x2,x3minwx12x2x32x1x2x32x1x2x3x5x6x1,x2,x3,x4,x5此時，雖然所有變量的檢驗數(shù)均為非負，但是人工變量x6仍然為基變量，這 b b 0M 1M 52 M- 11 419 M- M-二階段它把LP問題的求解分為兩個階段來進行。第一階段：在原約束條件下，先求解一個目標函數(shù)只包含人工變量的人造LP問題；即令極小值目標函數(shù)中人工變量的系1二階段它把LP問題的求解分為兩個階段來進行。第一階段：在原約束條件下，先求解一個目標函數(shù)只包含人工變量的人造LP問題；即令極小值目標函數(shù)中人工變量的系1minwx6二階段，見表2-13： b 011 11 011 31 010 11 000 11 minw思考題minw思考題3121822：00~954現(xiàn)要截取2.9米、2.11.5米的元100根，已知原材料的長度是7.4米，某糖果廠用原A、B、C加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號1所示。問該廠每月生產(chǎn)這 b 01 01 52 11 419 54221.554221.51234單位（100m2）租金（元 1234甲乙丙ABC售（1）maxz2x1（2）maxz3x14x13x2x1（1）maxz2x1（2）maxz3x14x13x2x12x22x1x23x12x24x1x2x1x2x1,x2x1,x2（4）maxzx1x1x2x1x23x1x23x1x2x1,x2x1,x28maxz2x1x2x3x1+++=5x1++=22x1+++=6x1,,在保持x2x3為零的情況下，給出非基變量x1增加一個單位時的可年凈收入（元/公頃（4）x1maxZ2x1x2（4）x1maxZ2x1x23x3x1x22x3x42x13x25x3x4x1x26x34x4（1）minw3x1x2x3（2）maxZ4x15x22x12x2x3+x3+23x1x2x4+x1,x2,x3,x4x1+x1,x2,x3第三章線性規(guī)劃的對偶理2-1追求最大利潤的數(shù)學模型（62-1追求最大利潤的數(shù)學模型（6頁，現(xiàn)在讓我們從另minw8y116y212y1+4+4y32y1，y2，y3w8y116y212y1+4+4y32y1，y2，y3將站在廠商的立場上建立起來的數(shù)學模型同站在工廠立場上所建立的數(shù)學模原問題么后者就稱為其對偶問題定示例進行的，我們可么后者就稱為其對偶問題定示例進行的，我們可以很自然地將其推廣到生產(chǎn)n種產(chǎn)品、消耗m種資源的一原問對偶問maxzc1x1c2x2cnminwb1y1b2y2bma11x1a12x2a1nxna11y1a21y2am1yma21x1a22x2a2nxnam1x1am2x2amnxna12y1a22y2am2yma1ny1a2ny2amnymxjyi(j1,2,,(i1,2,,將該價格與市場價格相區(qū)別，稱其為影子價格（shadowprice。2.1原問題與其對偶問題的對應關[3-2]maxzx12x2[3-2]maxzx12x2x1x2x3x12x23x3x12x23x3x1,x2,x3x12x23x3x12x23x3x12x23x3x12x23x36兩邊同乘“-1x12x23x3maxzx12x2x1x2x3x12x23x3x12x23x3x12x23x3x1,x2,x3minw4z15z2minw4z15z26z3z1 z2z3 z4z12z22z32z4z13z23z33z4z1,z2,z3,z4y1z1y2z2y3z3z4minw4y15y26y1y2y3y12y22y3y13y23y3y10y20y3[3-3]maxzx12x2x1x2x3x12x23x3x12x23x3x10,x20,x3xx10,x20,x3x1z1x2z2x3z3z4z30,z40)maxwz12z23z3z1z2z3z4z12z23z33z4z12z23z33z4z1,z2,z3,z4minw4y15y26y1y2y3y12y22y3y13y23y3y13y23y3y10，y20，y31y12y22y3y13y23y3minw4y15y26y1y2y3y12y22y3y13y23y3y1,y12y22y3y13y23y3y1,y2,y32.2對偶性存在CXYb；X是原問題（max）Ymm=nn=約束條件右端項目標函數(shù)價值系數(shù)目標函數(shù)價值系數(shù)約束條件右端項約束條件系數(shù)矩陣約束條件系數(shù)矩陣minw2x13x20x30x4minw2x13x20x30x4+2+4+x54+x1,x2,x3,x4,w8y116y212 +4 y5y1+42y1,y2,y3,y4,y5y1y54 b b 00 3-2~3-52-1~2-4加以對照，不難得出原問題檢驗數(shù)對應其對偶問題基解的結(jié)論，對應關系見表3-6。利用單純形法求解線性規(guī)劃進行迭代時，在b列得到的是原問題的一個基可行解，而在檢驗數(shù)行得到的是對偶問題的一個基解。在保持b列是原問題的基可行解驗數(shù)行是對偶問題的基可行解的前提下，通過迭代使b列逐步成為原問題的基可行3-2~3-52-1~2-4加以對照，不難得出原問題檢驗數(shù)對應其對偶問題基解的結(jié)論，對應關系見表3-6。利用單純形法求解線性規(guī)劃進行迭代時，在b列得到的是原問題的一個基可行解，而在檢驗數(shù)行得到的是對偶問題的一個基解。在保持b列是原問題的基可行解驗數(shù)行是對偶問題的基可行解的前提下，通過迭代使b列逐步成為原問題的基可行行的基解開始迭代，從而省去了引入人工變量的麻煩（3-4中問題的求解就基變量X非基變量X松弛變量X0CNCB CBYSY b 8 b 8 2 0 3.1對偶單純形法的計算步（min數(shù)列向量3.1對偶單純形法的計算步（min數(shù)列向量b無非負的要求。若b非負，則已得到最優(yōu)解；若b列還存在負分量，轉(zhuǎn)選擇出基變量：在b列的負分量中選取絕對值最大的分量min{bi|bi該分量所在的行稱為主行，主行所對應的基變量即為出基變量生的列所對應的變量即為入基變量迭代運算：同單純形法一樣，對偶單純形法的迭代過程也是以主元素為minwx14x2x1+2x2 x42x1x2+4x4x1,x2,x3,x4minwx14x2x1+2x2 x4x5=2x1x2+4x4x6=x1,x2,x3,x4,x5,x6,3,,1x11,,3,,1x11,(1) 1（2）因b列仍然存在負分量，所以需要繼續(xù)迭代。同前可知，x6為出基變量，x3表3-9b列已經(jīng)不存在負分量，故表3-9給出了此問題的最優(yōu)解X 7Z3.2對偶單純形法中無可 b 10 74 b 10 3 b 00 §4靈敏度分行計算，然而這樣做既麻煩又沒§4靈敏度分行計算，然而這樣做既麻煩又沒有必要。在單純形法迭代時，每次運算都和基B有4.1資源系數(shù)變化的分資源系數(shù)發(fā)生變化，即b發(fā)生變化的靈敏度分析；該類問題關鍵是如何將b的 IB1（（最終單純形表中的每一列均可用其在初始單純形表中的相應列左乘 來得到；（最終單純形表中的每一列均可用其在初始單純形表中的相應列左乘 來得到；bB1b[3-6]LPminw5x112x24x30x4x1+2x2 =2x1x2 3x5=x1,x2,x3,x4,x5單純形求解可得如表3-11所示的最終單純形表，問（1）b2在什么范圍內(nèi)變（2）222/ 1/8b25b52/52b21/ 為保持最優(yōu)解不變，應有b0，即：8b2092b20，所以有b255范圍應在[5,10]之內(nèi)2 b b2/ 1/5571/ 2/5b2/ 1/5571/ 2/5 4.2價值系數(shù)變化的分[3-7]LPminw2x13x2x30x4+x3 =+7 x5=+4x1,x2,x3,x4,x5 b 50 b 7 時，最優(yōu)解保持不變；（2由“-1”減少至“-6”，求新的最優(yōu)解時，最優(yōu)解保持不變；（2由“-1”減少至“-6”，求新的最優(yōu)解身的檢驗數(shù) ，而與其他變量的檢驗數(shù)無關。計算變化后的并令其非負，即33求得保持最優(yōu)解不變c3的變化范圍c c40333 c3即只要 b 12 21 b 12 因為基變量的價值系數(shù)發(fā)生變化會引起CB的變化，進而可能引起整個檢驗數(shù)]優(yōu)解保持不變；（2）c1由“-2”減少至“-6”，求新的最優(yōu)解因為基變量的價值系數(shù)發(fā)生變化會引起CB的變化，進而可能引起整個檢驗數(shù)]優(yōu)解保持不變；（2）c1由“-2”減少至“-6”，求新的最優(yōu)解1(c,3) c50c53111 4/340(cc10c411/311 0(c,3)1/c10c151311/即保持原最優(yōu)解不變應有c][144.3技術系數(shù)變化的分 b 12 21 0 36 如果將原迭代過程繼承下來，我們就可以通過 將技術系數(shù)的變化反映進]4/ 如果將原迭代過程繼承下來，我們就可以通過 將技術系數(shù)的變化反映進]4/ 3c3CBBP1 12331/31/ 233 012333-10解：首先將變化反映進最終單純形表，形成3-174/ P11/ 1/ 2/ b 12 X解：首先將變化反映進最終單純形表，形成3-18 X解：首先將變化反映進最終單純形表，形成3-18 11/ 2/5 9/3-18X0,139)T [3-12]3-7a1110時，原最優(yōu)解是解：首先將變化反映進最終單純形表，形成3-194/P11/ 1/ 1/ b 12 b 01 x13x34x4x5方程兩側(cè)同乘“-1”并引入人工變量x6x13x34x4x5方程兩側(cè)同乘“-1”并引入人工變量x6x13x34x4x5x6 18X4.4增加一個新的變量的分（min[3-13]3-7x6 b M 33M- w=3M-0 [1/4] M-0 39 M- 3 4/ P61/4/ P61/ 1/ 其次計算新增變量x6在最終單純形表中的檢驗數(shù) 31604.5增加一個新的約束的分（1）x12x2（2）x12x2x3 b 12 12 解（1）：將原問題的最優(yōu) (1,2,0,0,0)T代入新增加的約束條X解（1）：將原問題的最優(yōu) (1,2,0,0,0)T代入新增加的約束條X Xx12x2x34x6x6思考題 b 0 1240 12 0 213 （1）minw2x12x2+2x2+x3+x2（1）minw2x12x2+2x2+x3+x2+3x32+4+6x1,x2,x3（2）max2x13x2+x3+2+2x33+x3+2x10,x20,x3（1）minw4x112x2（2）minwx12x23x3+3x3+3x4+2+232x2+2x3+x2+3x3+2x425x1,x2,x3x1,x2,x3,x4maxz3x1x26x13x25x33x14x25x3x1,x2,x3x1,x2,x3產(chǎn)品A的價值系數(shù)c1在什么范圍內(nèi)變化，才能確保原最優(yōu)解不變?nèi)鬰13變?yōu)?，最優(yōu)解將發(fā)生怎樣的變化低為2個單位，最優(yōu)解將發(fā)生怎樣的變化？x1x23x320若在原問題的基礎上增加一個約束條件3x1x22x320第四輸問 b 53 §1運輸問題的數(shù)學4-1所示。問該公§1運輸問題的數(shù)學4-1所示。問該公 minwciji14（i1,2,3；運出的商品總量等于其產(chǎn)量3（j1,2,3,4；運來的商品總量等于其銷量甲乙丙丁產(chǎn)量A337B19284C74593656將該引例的數(shù)學模型做一般性推廣，即可得到有m個產(chǎn)地、n問題的一般模型。注意：在此僅限于探討總產(chǎn)將該引例的數(shù)學模型做一般性推廣，即可得到有m個產(chǎn)地、n問題的一般模型。注意：在此僅限于探討總產(chǎn)量等于總銷量的產(chǎn)銷平衡運輸問題mminwciji1n（i1,2,m；運出的商品總量等于其產(chǎn)量m（j1,2,n；運來的商品總量等于其銷量地的數(shù)量mn；而決策變量個數(shù)是二者的積mn。由于在這mn個個數(shù)是mn1個?！?運輸問題的求；確定入基變量，若min{ijij0lkxlk2.1確定初始基可行能給出較好初始方案的最小元素法（theleastcostrule）和伏格爾法（Vogel’sapproximationmethod。1．最小能給出較好初始方案的最小元素法（theleastcostrule）和伏格爾法（Vogel’sapproximationmethod。1．最小4-2；將運價表的甲列運價劃去得表4-3，劃去甲列表明甲的需求已經(jīng)得到滿甲乙丙丁甲乙丙丁產(chǎn)量A7B34C93656甲乙丙丁甲乙丙丁甲乙丙丁產(chǎn)量A7B314C93656A33B1928C745mn1”個數(shù)字格（基變量）的初始基可行解。然而，問題并非總是如此，有時也會出現(xiàn)這樣的情況：在供需關系格（i,j）處填入一數(shù)字，剛好使第i個產(chǎn)地的產(chǎn)品調(diào)空，同時也使第j個銷地的需求得到滿足。按照前述的處理方法，此時需要在運價表上相應地劃去第i行和第j列。填入一數(shù)字同時劃去了一行和一列，如果時需要在第ijmn1”個數(shù)字格（基變量）的初始基可行解。然而，問題并非總是如此，有時也會出現(xiàn)這樣的情況：在供需關系格（i,j）處填入一數(shù)字，剛好使第i個產(chǎn)地的產(chǎn)品調(diào)空，同時也使第j個銷地的需求得到滿足。按照前述的處理方法，此時需要在運價表上相應地劃去第i行和第j列。填入一數(shù)字同時劃去了一行和一列，如果時需要在第ij列此前未被劃掉的任意一個空格上填一個“0”。填“0”格甲乙丙丁A437B314C6393656A33B1928C745將4-1的各工廠的產(chǎn)量做適當調(diào)整（4-7）1B4-84-9。6甲乙丙丁2甲乙丙丁A4B314C3656甲乙丙丁將4-1的各工廠的產(chǎn)量做適當調(diào)整（4-7）1B4-84-9。6甲乙丙丁2甲乙丙丁A4B314C3656甲乙丙丁A334B19284C7453656甲乙丙丁甲乙丙丁A044B314C3656A334B19284C7453656甲乙丙丁甲乙丙丁A044B314C3656A334B19284C7453656334A19284B745C3656334A19284B745C36560不妨選擇（A，乙4-104-11。注意這個“0”是不能填入（A，2．伏格爾最小元素法的缺點是只考慮了就近的問題卻沒有考慮就近所付出的機會成本。（選擇次小元素時的費用（如果存在兩個或兩個以上的最小元素費用增量定義為零。最大差對應的行或列中的最小元素確定了產(chǎn)品的供應1列和最下行，見表4-12。甲乙丙丁素是“4”，從而確定C與乙間的供應關系4-13即反應了這一供應關系。同最4-15~4-23甲乙丙丁素是“4”，從而確定C與乙間的供應關系4-13即反應了這一供應關系。同最4-15~4-23甲乙丙丁A7B4C693656A330B19281C74512513甲乙丙丁甲乙丙丁A7B4C6393656甲乙丙丁A330B19281C7452甲乙丙丁甲乙丙丁A7B4C6393656甲乙丙丁A330B19281C7452213甲乙丙丁甲乙丙丁A7B34C6393656A330B19281C745212甲乙丙丁甲乙丙丁A7B34C6393656A330B19281C745212甲乙丙丁甲乙丙丁A57B34C6393656A337B19286C74512甲乙丙丁甲乙丙丁A57B34C6393656A337B19286C74512甲乙丙丁甲乙丙丁A57B314C6393656A33B1928C7452甲乙丙丁甲乙丙丁A57B314C6393656A33B1928C74522.2基可行解的最優(yōu)性檢1．閉合甲乙丙丁A527B314C6393656A32.2基可行解的最優(yōu)性檢1．閉合甲乙丙丁A527B314C6393656A33B1928C745的閉合回路4-24中用虛線畫出了這條閉合回路。閉合回路的閉合回路4-24中用虛線畫出了這條閉合回路。閉合回路頂點所在格括號內(nèi)的數(shù)字是相應的單位運價，單位運價前的“-”號表示運量的調(diào)整方向。費減1個單位。增減相抵后，總的運費增加了1個單位。由檢驗數(shù)的經(jīng)濟含義可以知道，（A，甲）處單位運量調(diào)整所引起的運費增量就是（A，甲）的檢驗數(shù)，即甲乙丙丁甲乙丙丁A37B4C6393656甲乙丙丁11=12=7A34B9C3656甲乙丙丁A11=74B314C93甲乙丙丁11=12=7A34B9C3656甲乙丙丁A11=74B314C93656甲乙丙丁甲乙丙丁A11=12=7B322=124=-4C69甲乙丙丁甲乙丙丁A11=12=7B322=124=-4C693656A11=12=7B322=4C639365611=12=7A22=24=-4B33=69C36564-30中，241，說明方案2．位勢對于特定11=12=7A22=24=-4B33=69C36564-30中，241，說明方案2．位勢對于特定的調(diào)運方案的每一行 給出一個因子ui（稱為行位勢每一列給出甲乙丙丁A11=12=437B322=124=-4C31=633=393656個因子vj（稱為列位勢，使對于目前解的每一個基變xij有cijuivj的ui和vj可正、個因子vj（稱為列位勢，使對于目前解的每一個基變xij有cijuivj的ui和vj可正、可負也可以為零。那么任一非基變量xij的檢驗數(shù)cij(uivjuivkulvkulvcijcikclkcij(uivk)(ulvk)(ulvjcij(uivj對于一個m個產(chǎn)地、n個銷地的運輸問題m個行位勢、n個列位勢，即具mn”個位勢。運輸問題基變量的mn1”個，所以利用基變量mn1”個方程mn”個位勢，進而計算各非任意的值（如xij都有cijuivj4-31甲乙丙丁非基變xij（-cik）基變量基變xlj（-（+clk）基變量v30A12B45C293v第二步：利用cijuivjxij302.3方案的優(yōu)基變量。切記出基變量的“0”運量要用“空格”來表示，而不能留有“030A12B45C293v第二步：利用cijuivjxij302.3方案的優(yōu)基變量。切記出基變量的“0”運量要用“空格”來表示，而不能留有“0x24所處的閉合回路上（4-32所示）x24最大的增量“1”，相應x23出基、x135、x142。利用閉合回路法或位勢法計算各空格（非基變量）4-32甲乙丙丁§3運輸問題的拓甲乙丙丁A11=12=527B322=23=§3運輸問題的拓甲乙丙丁A11=12=527B322=23=14C31=633=39銷量3656A11=12=437B322=124=-4C31=633=3936563.1產(chǎn)大于銷的運輸問都應取為“03.1產(chǎn)大于銷的運輸問都應取為“035所示的產(chǎn)銷平衡運輸問題。甲乙丙丁戊產(chǎn)量甲乙丙丁產(chǎn)量A337B19284C745銷量36563.2銷大于產(chǎn)的運輸問[4-甲乙丙丁產(chǎn)量A337B19284C74593.2銷大于產(chǎn)的運輸問[4-甲乙丙丁產(chǎn)量A337B19284C7459656A3307B192804C745036563此運輸問題的總產(chǎn)量為20、總銷量為28，所以假設一個產(chǎn)地D并令其產(chǎn)量剛37所示的產(chǎn)銷平衡運輸問題。3.3運輸問此運輸問題的總產(chǎn)量為20、總銷量為28，所以假設一個產(chǎn)地D并令其產(chǎn)量剛37所示的產(chǎn)銷平衡運輸問題。3.3運輸問題的應用舉[4-4]設有三個化肥廠供應四個地區(qū)的化肥需求，假定等量化肥在這些地區(qū)4-38（單位：萬噸M0甲乙丙丁產(chǎn)量A337B19284C7459D00008656110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，除1、地區(qū)2和地3的最低需求外，地區(qū)4每年最多能分配到60（1603070060）萬噸，這樣其不限60210萬噸，大于總160萬噸，將此問題定義為銷大于產(chǎn)的運輸問題。為了求得平衡，在產(chǎn)銷平衡20D110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，除1、地區(qū)2和地3的最低需求外，地區(qū)4每年最多能分配到60（1603070060）萬噸，這樣其不限60210萬噸，大于總160萬噸，將此問題定義為銷大于產(chǎn)的運輸問題。為了求得平衡，在產(chǎn)銷平衡20D來供給，按前面講的，4-384-394-4-40（單位：萬噸0MMM0M0M0x1j1j年需要的產(chǎn)品數(shù)量（j1,2,3,4x2j2j年需要的產(chǎn)品數(shù)量（j2,3,4x2j2j年需要的產(chǎn)品數(shù)量（j2,3,4x3j3j年需要的產(chǎn)品數(shù)量（j3,4x3jx1j1j年需要的產(chǎn)品數(shù)量（j1,2,3,4x2j2j年需要的產(chǎn)品數(shù)量（j2,3,4x2j2j年需要的產(chǎn)品數(shù)量（j2,3,4x3j3j年需要的產(chǎn)品數(shù)量（j3,4x3j3j年需要的產(chǎn)品數(shù)量（j3,4x4j4j年需要的產(chǎn)品數(shù)量（j4四年的總銷量是2700件，按組織加班考慮，總產(chǎn)量是3200件，總產(chǎn)量銷量。假設一個銷地D，等價的平衡運輸問題如表4-所示。此時這一問題磚2633941234假設銷地D產(chǎn)102M02（加M03MM03（加MM04MMM0銷[4-6]A1、A2、A3、A4、A5A64-44所示的調(diào)進空車。平衡結(jié)果A1、A5、A6除裝運自己的貨物外，可多出空車21車次；A2、A3、A421車次。按最小空駛調(diào)度，可構造表4-45所示的運輸問題數(shù)據(jù)表，進88298543974[4-6]A1、A2、A3、A4、A5A64-44所示的調(diào)進空車。平衡結(jié)果A1、A5、A6除裝運自己的貨物外，可多出空車21車次；A2、A3、A421車次。按最小空駛調(diào)度，可構造表4-45所示的運輸問題數(shù)據(jù)表，進88298543974245到從29245946758324思考題A、B、C1000、20002000270A1、A2、A3三個倉庫，然后再思考題A、B、C1000、20002000270A1、A2、A3三個倉庫，然后再15025、105、60、3070噸。已知從該廠經(jīng)輸數(shù)量A2B2的道路關閉，故最優(yōu)調(diào)運方案將發(fā)生變化，甲乙丙A540B89C3327174第五數(shù)規(guī)第五數(shù)規(guī)（pureintegerprogramming如果僅僅是要求一部分變量取整，則稱為混合整數(shù)2133354224443542414222292647835463pogramming模型表示為：{minpogramming模型表示為：{minwCXAXbX0且（部分）為整數(shù)§1分枝定界分枝定界法（branchandboundmethod）具有靈活且便于用計算機求解等優(yōu)點。它的一般思想是利用連續(xù)的（線性規(guī)劃x*是非整數(shù)；那么在[x*]（x*的取整值）和[x*1kkkkxxkx*xx*kk 整數(shù)點的部分連續(xù)空間（[x*xx*1 [5-1]maxz40x19x1+7x27x1+20x2x1x29x1+7x27x1+20x2x1x20定義相應的線性規(guī)劃L0maxz40x19x1+7x27x1+20x2x1,x23455-5-1L0X(4.81,1.82)TX(0)(4.81,1.82)Tz(0)356z劃最優(yōu)值的上界（max。分枝定界法首先任意選擇一個非整數(shù)決策變量，在此不假設選x1L0的最優(yōu)解中x14.81，于是[x14、[x115L0的5-1L1：maxz40x1L2：maxz40x19x1+7x29x1+7x27x1+20x27x1+20x24x1,x2x1,x27x1+20x27x1+20x24x1,x2x1,x24,2.1)T，z(1)349；X(2)(5,1.57)T，z(2)341L 11的最優(yōu)解中x22.1，于是[x22、[x213L1的基礎上，分別增加約L4：maxz40x19x1+7x29x1+7x1+20x27x1+44x223x1,x2L3L4有：Xx1,x2(1.42,3)T(4,2)T327有整數(shù)最優(yōu)解，故整數(shù)規(guī)劃最優(yōu)值的下界（max）是該整數(shù)最優(yōu)值340因用340這一下界，可以舍棄L4L2的最L2尚需繼續(xù)分L6：maxz40x19x1+7x29x1+7x27x1+20x27x1+20x2x2x1,x2x2x1,x2，x2x1,x2x2x1,x2，，，L3（5-L2x21x22L5L6，求解L5L6有(5.44,1)T，z308L6z X[5-2]求解minw2x13x2x1 x2+x3=解 ，L6（無可行解x1+4x2+7 x5=x1+4x2+7 x5=的改變反映進最終單純形表，見表5-2（相當于L0的最優(yōu)解L1L2L1：minw2x13x2L2：minw2x13x2x1+x2+x3x4=+x2+x3=x1+4x2+7x3x5x5=x1+4x2+7 b w=- b 12 x1,x2,x30；x4,x5x1,x2,x30；x4,x5L1x1,x2,x30；x4,x5x1,x2,x30；x4,x5L1L2中新增加的約束條件x17x18轉(zhuǎn)換為x1x67x1x685-2L：X(7,1/2,0)T，w(1)31/1(8,0,0)T，L2： b 0 0 b 0 70 0 7 L2是整數(shù)最優(yōu)解所以其最優(yōu)（min）最優(yōu)值的上L2是整數(shù)最優(yōu)解所以其最優(yōu)（min）最優(yōu)值的上 (8,0,0)T，最優(yōu)X5-3，5-0-1為xj1xj0xj取整}；因此，0-10 801 ）Sj（j1,2,…,7在南區(qū)的S）Sj（j1,2,…,7在南區(qū)的S4和S5兩個點中至少選一個；（單位：萬元xj0或1xj0Sjxj1Sj7構造如下的數(shù)學模型 maxzPjxj7j11x1x2x3x4x5x6x7xj0或1（j0-10-1規(guī)劃的求解存在更簡便的方法，稱為“隱枚舉法（implicitenumerationmethod。用分枝定界法求解maxz3x1x22x12x2x3x14x22x12x2x3x14x2x30minw3x1x22x12x2x3x14x2x3x1~30（2）目標函數(shù)系數(shù)非負化為保持決策變量的0-1xjxj1xj；在此x11x1x21x2x31x32x12x2x3x14x2x302x22x1x30（5）按照排列順序依次令各變量取“1（5）按照排列順序依次令各變量取“1105-x20、x11、x30的目標值6。由于得到的兩個子問題均有可行解，所以x10x21x300-1規(guī)劃問題的最優(yōu)解是為最優(yōu)目標值的“上界”，將目標值較大的分枝剪去；將分枝邊界值已超過最優(yōu)目標值“上界”的分枝剪去規(guī)劃的一個約束條件是3x1x22x32x44x10的分枝就可以實Xmaxz8x12x24x37x43x13x2x32x43x55x13x22x33x13x2x32x43x55x13x22x3x4x50minw2x24x35x57x48x1103x2x33x52x43x123x22x3x5x45x1x1~2x3~50W=-4（可行解4W=-W=-22W=-11W=-W=-511W=-W=-33005-5-5-52號、3號結(jié)點所反映的解均為非可行解，優(yōu)先選擇邊界值較小去5號結(jié)點所在的分枝，因為該結(jié)點的目標邊界值已大于此“上界”。W=-4（可行解4W=-2W=-W=-1W=-§3指派問在現(xiàn)實世界經(jīng)常會遇到這樣的問題：有n個人恰好可承擔n項任務，一項任務率也就不同，于是產(chǎn)生了應指派哪個人去完成哪項任務，才能使完成n項任務總的pobe3-1,10 minzciji1jnjx(i1,,nx minzciji1jnjx(i1,,nx(j1,,0or第一個約束條件說明第ij項n nz(c1jk)x1cijxijcijkx1jzji2ji1jj3-2[5-6]5-69873456135-7M3J3、M4J2。由于此方案實現(xiàn)了“0”指派，而效率矩陣135-7M3J3、M4J2。由于此方案實現(xiàn)了“0”指派，而效率矩陣中的所有元素都非負的，所以它一定是最優(yōu)方案。回到原效率矩陣，可求得此方案的目標值為z7313143200032110200122978587754652345321001231001102321124356“（“（（（0211054206081303203211200122320032110200122（（0此例題即屬這種情況（5-11），由于尚未找到最優(yōu)解，計算往下進行。（（0此例題即屬這種情況（5-11），由于尚未找到最優(yōu)解，計算往下進行。4202102020114200021020200011 0√（ 20√ 22√該結(jié)果對應的最優(yōu)指派方案是：人員1—工作3、人員2—工作1、人員3—工作4、人員4—工作2，最短工作時間為20（小時。需要強調(diào)的是，由于在第九步（03-3該結(jié)果對應的最優(yōu)指派方案是：人員1—工作3、人員2—工作1、人員3—工作4、人員4—工作2，最短工作時間為20（小時。需要強調(diào)的是，由于在第九步（03-3]890500605089565題，我們就可以決定假想人所對應的效率矩陣元素是完成各項任務的最短時間題，我們就可以決定假想人所對應的效率矩陣元素是完成各項任務的最短時間42173454996895866000002533065905080]5-22所示的最優(yōu)指派方案（不唯一1[5-11]5-6中，若效率矩陣（5-6）代表的是各人在單位時間里完成03]5-22所示的最優(yōu)指派方案（不唯一1[5-11]5-6中，若效率矩陣（5-6）代表的是各人在單位時間里完成031792649056002089586658660000121321110102100012132111010210005-23所示的最優(yōu)指派方案（不唯一1思考題（1）maxzx1（2）maxz4x114x19x23x14x26x13x24x12x2x1x20x1x20機350該公司現(xiàn)有資金12000萬元可用于購據(jù)估計年凈（除成本）每架遠程客82萬元，中程客60萬元，短程客40萬元。設該3040架7013310000220（1）maxz2x1x25x33x43x12x2（1）maxz2x1x25x33x43x12x27x35x44x5x1x22x34x42x5xj0or1(j1,2,3,4,（2）maxz2x15x23x34x1x2x3x42x14x22x34x4x1x2x3x4xj0or1(j1,2,3,甲乙丙丁ABCDEF7420、30402、46千克。已知全部備用件的費用預算限制為150元，重量限制為20千克，問每第六章非線性規(guī)對實際問題解的精度要求越420、30402、46千克。已知全部備用件的費用預算限制為150元，重量限制為20千克，問每第六章非線性規(guī)對實際問題解的精度要求越來越高，非線性規(guī)劃自20世紀70年代以來得到了長足012345甲乙8丙9丁本章在簡要介紹非線性規(guī)劃基本概念和一維搜索的基礎上，重點介紹本章在簡要介紹非線性規(guī)劃基本概念和一維搜索的基礎上，重點介紹無約束值問題和約束極值問題的求解方法§1非線性規(guī)劃的數(shù)學模1.1非線性規(guī)劃問6-1]某商店經(jīng)銷A、B兩種產(chǎn)品，售價分別20380統(tǒng)計，售出一件A產(chǎn)品的平均時間為0.5B產(chǎn)品的平均時間與其銷售的數(shù)量成正比，表達式為10.2n。若該商店總的營業(yè)時間為1000小時，試確定使其營maxf(x)20x10.5xx0.2x2 2x10,x26-2]在層次分析（AnalyticHierarchyProcessAHP）中，為了進行a1n ann上能最好地反映判斷矩陣的估計，由aijwi/wj可得： minf(w)(aijwji1nwi1.2非線性規(guī)劃問題的數(shù)學模minf(X),X1.2非線性規(guī)劃問題的數(shù)學模minf(X),Xhi(X)0,(i1,2,,gj(X)0,(j1,2,,Xx1x2xn)T是nEnhi(X)0；hi(X)minf(X),Xgj(X)0,(j1,2,,1.3非線性規(guī)minf(X)(x12)2(x2h(X)x1x26fX)c，目標函數(shù)成為一條曲線或一張曲面；通常稱為值線或等值面fX)2fX)4166-1fX26-1fX26-6D題的最優(yōu)解X3,3fX2h(Xx1x260h(X)x1x26代替原來的約束h(Xx1x260，則新的非線性規(guī)劃的最優(yōu)解變?yōu)閄2,2)6-1中的CfX0h(X)x1x26注意：線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在§2極值問2-1（1）對于XXfXfX（1）對于XXfXfXXfX上的局部極小點，fX為局部極小值（2）對于XXfXfXXfX上的嚴格局部極小點，fX為嚴格局部極小值（3）XXRfXfXXfXR的全局極小點，fX為全局極小值（4）XXRfXfXXfXR的嚴格全局極小點，fX為嚴格全局極小值2-2極值點存在的[1（必要條件）]REnfXRf(Xf(Xf(X12n或f(X)式（6-2）中fX(fX)fX),fX)TfXX點處的 度由數(shù)學分析可知fX的方向為X點處等值面（等值線）的法線方向方6-2fX)0或fX0的點稱為平穩(wěn)點或駐點f(Xf(X 2n極值點一定是fX)0或fX0的點稱為平穩(wěn)點或駐點f(Xf(X 2n極值點一定是駐點，但駐點不一定是極值點]XR，若fX0ZEnZTH(X*)ZX*fX的嚴格局部極小點HX*fXX*處的（Hesse）矩陣2f(X2f(X)2f(X12f(X2f(X2f(X)H(X)2f(X2f(X2f(X) （1）ZTHZ0ZTHZH正定（2）ZTHZ0ZTHZH半正定（3）ZTHZ0ZTHZH負定（4）ZTHZ0ZTHZH半負定（5）ZTHZ不定H不定若矩陣H負定，則其各階左對角方陣的行列式負、正交替。 0 00 hhhh 0 0 00 hhhh 0；0；；0hhhhhhhhh2（充分條件）等價于，如果fX)X*點的梯度為零且海賽矩陣正定X*為fX)的嚴格局部極小點2-31．定R中的任意兩點X(1X(2f(X(1)(1)X(2))f(X(1))(1)f(X(2)fXR上的凸函數(shù)6-3fX為定義在上的嚴格凸函數(shù)。改變不等號的方向，即可得到凹函數(shù)和嚴格凹函數(shù)6-32．性]2．性]]+[性質(zhì)3]fX)為定義在凸集R上的凸函數(shù)，則對于任意實數(shù)bSbXXR,fXb}是凸集]]XR有fXTXX0XfXR（全局極小點3．判根據(jù)一階條件進行判REnfXRfXR(1)(2)的凸函數(shù)的充分必要條件是，對于屬于R的任意兩個不同點Xf(X(2))f(X(1))f(X(1))T(X(2)X(1)（3）根據(jù)二階條件REnfXRfXR的凸函數(shù)的充分必要條件是：fX)的海賽矩陣HX)R上處處半正（ZTHX)Z0的凸函數(shù)的充分必要條件是：fX)的海賽矩陣HX)R上處處半正（ZTHX)Z06-4]fXx2x2 （1）f(Xf1x1f2x2f(x)x2a和b，分別構造兩點的線性組合和兩點函數(shù)值 性組合；即在ab的情況下，取(0,1f1[a(1)b]f1(a)(1)f12(1)ab(1)2b2a2(1a2(1)b2(1)2(1)ab(1)[a2b22ab](1)(ab)2f(x)x為嚴格的凸函數(shù)，同理f(x)x也為嚴格的凸函數(shù)；所以22 222f(Xf1x1f2x2（2）一階條件證明fXx2 X(1)(a,b、X(2)(a，從 f(X(1))a2b2，f(X(2))a2b2，f(X(1))(2a,2b f(X(2))f(X(1))(X(2)X(1))f(X(1)b2a2b2(2a,2b)(aa,bb (a2a1)2(b2b1)2fXx2x2 （3）二階條件證明fXfXx2x2 （3）二階條件證明fXx2 f(X)的海賽矩陣H(X) 0 2§3凸規(guī)3-1考慮非線性規(guī)劃：minfXXgj(X)0,(j1,2,,規(guī)劃稱為凸規(guī)劃minf(X)x2x24x 1g1(X)x1x22g(X)xx122 x1,x2Hf( 2fX為嚴格凸函數(shù)；g2X g(23-2下降迭代算 g(23-2下降迭代算1．基本思給定一個X(0)，然后按某種規(guī)則（即算法找出一個比(0)更好(k)}，若這一解的序列有極限XX(1)，如此遞推即可得到一個解的序列l(wèi)im(X(k)X)kX為最優(yōu)解2．基本問由于遞推步驟的有限性，一般說很難得到精確解，當滿足所要求的精度時即停止迭代而得到一個近似解3．下降算若某種算法產(chǎn)生的解序列{X(kf(X(k若從 出發(fā)沿任何方向移動都不能使目標函數(shù)下降，則 是一個局部小點；若從 出發(fā)至少存在一個方向能使目標函數(shù)下降，則可選定某一下降方(k1)，沿這一方向前進一步，得到下一個點X(k)P(kP(k方向前進一步相當于在射線沿上選定新的點P(k)；其中P(k)為搜索方向X(kXk為步長k確定搜索方是關鍵的一步種算法的區(qū)別主要在于確定搜索方步長kX(k)P(kf(X最佳步長；即沿步長kX(k)P(kf(X最佳步長；即沿射線k：min(X(kP(k)P(k)(X(kfk來實現(xiàn)的，故稱這一過程為一維搜索6-一維搜索有一個非常重要的性質(zhì)，即在搜索方向上所得最優(yōu)點的梯度和搜向正交；這一性質(zhì)可表達f(X(k1))min(X(kP(k)X(kXP(kkf(X(k1))TP(k因為真正的極值點 在求解之前并不知道，因此只能根據(jù)相繼兩次迭代的X(k1)X(k1f(X(k1))f(X(k)34X(k1)X(k1f(X(k1))f(X(k)34f(X(k)§4一維材只介紹斐波那契和黃金分割兩種方法4-1斐波那契一維搜索過程是建立在一個被稱為斐波那契數(shù)序列基礎上的，斐波那契數(shù)序F0F1Fn1（n斐波那契法成功地實現(xiàn)了單峰函數(shù)f(x[ab上有一極小點x，在此區(qū)間內(nèi)任意取兩點a1和b1n012345678112358f(X(k1))f(X(k)f(X(k)X(k1)X(kX(kxab6-這說明xab6-這說明只要在區(qū)間[ab內(nèi)任意取兩點a1和b1（a1b1）并計算其函數(shù)值比較，就可以把搜索區(qū)間[a,b]縮減成[a,b1]或[a1b]。若要繼續(xù)縮小搜[a,b1或[a1,b]，只需在區(qū)間內(nèi)再取一點算出其函數(shù)值并與f(a1或f(b1加以值n次，能把區(qū)間縮減到什么程度呢？”或者換句話講“計算函n次，能把原來多大的區(qū)間縮減成單位如果用Fn表示計算n個函數(shù)值能縮短為單位區(qū)間的最大原區(qū)間長度，因為計算n個函數(shù)值所能獲得的最大縮短率為1/Fn，即計算n個函數(shù)值可把原長L0的區(qū)間縮計算n個函數(shù)值所能獲得的最大縮短率為1/Fn，即計算n個函數(shù)值可把原長L0的區(qū)間縮短為為L0例如計算12個函數(shù)值可把原長度為L0的區(qū)間縮短L 0若要想將區(qū)間長度縮短為原長度的（0<<1）倍，只要n足夠大一定能使F 斐波那契法使用對稱的搜索方式，逐步縮減搜索的區(qū)間，所采取的具體步確定兩個試點的位置a1、b1（對稱搜索，見圖6-Fn-Fn-abFn-Fn-6-6-6]試用斐波那契法f(x)3x212x10值，要求縮短后的區(qū)間不大于初始區(qū)間[1,4]0.05) 2，最優(yōu)值f) 2，最優(yōu)值f(x)2已知0.05、a1、b4，由式（6-3）Fn120n7abF6(ba)413(41)1baF6(ba)113(41)1f(a1)1.939；f(b1)f(a11.939f(b10.203搜索區(qū)間可以從[1,4]縮減為[1,2.857。從新的區(qū)間（a1，b2.857）開始，繼續(xù)選取對稱試點比較函數(shù)值，以使區(qū)間Fn-Fn-Fn-Fn-6-新的試點a1 (2.8571)1.707，將原來的試點a2.143視為已1b1。由于f(a新的試點a1 (2.8571)1.707，將原來的試點a2.143視為已1b1。由于f(a11.742f(b11.939，搜索區(qū)間可以進一步從[1,2.857縮減為[1.707,2.857]，如圖6-9所示。再從新的區(qū)間（a1.707長度不大于(41)0.050.15。2.0401.9371.989因此，符合精度要求的近似極小點為21.999644-2黃金分割斐波那契法n個點縮減某一區(qū)間時，區(qū)間長度的縮減率依次為 FF,,F1?，F(xiàn)將以上數(shù)列分為奇數(shù)F2k和偶數(shù)項F2FF2kn設當k時奇數(shù)F2k1F偶數(shù)2F22kF2k1F2k 1 F2 F2k1F2k1F2kF2k1F2k 1 F2 F2k1F2k1F2kF2k故F2k 1F2k1將 111212代入 11151以0.618不變的區(qū)間縮減率，代替斐波那契法每次不同的縮減率，就得到了黃0.618和0.382處，見圖6-10。b1ab6-6-7]f(x3x221x1在區(qū)間[0,20上的極小點，要求縮短后解：a0b20a1a0.382(ba)00.382(200)b1a0.618(ba)00.618(200)f(a17.64)9.08，f(b112.36)f(4.72)b1a0.618(ba)00.618(200)f(a17.64)9.08，f(b112.36)f(4.72)36.07，f(2.92)f(1.80)30.16，f(3.60)f(4.03)39.33，f(3.34)由于從一定的搜索區(qū)間出發(fā)所進行的黃金分割搜索與斐波那契搜索在原理6-因此，符合精度要求的近似極小點為3.344.033.685，近似極小值為237.6473255-1梯度法（最速下降法1．基本原5-1梯度法（最速下降法1．基本原X(kk次近似k1次近似點X(k1)，X(k)點以處作泰勒展開，有f(X)f(X(k)P(k))f(X(k))f(X(k))TP(k)0（）f(X(k))TP(kfXfX(k)P(kf(X(kX(k X(k)P(kP(k)P(k)的模一定且不為零，并設f(X(k（否則 是平穩(wěn)點那么，使式（6-4）成立有無窮多個，為了數(shù)能得到盡量大的改善，必須尋求能使f((k))TP(k)。由于fX(k))TP(k)f(X(k)P(k)f(X(k反向（P(k1）fX(kTP(kP(k)f(X(k被稱為負梯方向，在1）fX(kTP(kP(k)f(X(k被稱為負梯方向，在 的某一小的鄰域內(nèi)，負梯度方向是使函數(shù)值下降最快的方向以采用試算法，即首先選取一個值進行試算，看它是否滿足不等式f(X(k1))f(X(k)P(k))f(X(k不等式成立。由于采用負梯度方向，X(k另一種方法是通過在負梯度方向上的一維搜索，來確定使得f(X(k1))f P(k最小的，這種梯度法就是所謂的最速下降法k2．基本步給定一個初始近似點X(0)及其精度02fX(0 X(0)即為2fX(0 ，求步長0X(1X(00fX(0。2f(X(k)X(k1)=X(kkf 。如此反復，直到達到要求的精(k)f(X(k)f(X(k)))f(X(k))f(X(k))Tf(X(k)+1f(X(k))TH(X(k))f(X(k)2f(X(k))Tf(X(k)求導并令其為零，則有最佳步長kf(X(k))TH(X(k))f(X(k)與梯度有關，而且與海賽矩陣有關[6-8]試用梯度法fX)x11)2x21)2的極小點，0.1X(0)(0,0)T，f(X(0))解：取初始近似2f(X(0)[(2)2(2)2]28H(X) (2,2)2 2f2f(X(0)[(2)2(2)2]28H(X) (2,2)2 2f(X(0))Tf(X(0)80202 f(X(0))TH(X(0))f(X(0)22 1X(1)=Xf( =2 02 [(0)2(0)2]206-X(0)(0,0)經(jīng)過負梯度X(度方向總是直接指向圓心，一次迭代即能達到最[6-9]試用梯度法f(X)4x6x2x2x2x的極大點2 12解：該二次函數(shù)的絕對最優(yōu) (13