最優(yōu)化方法及其應(yīng)用要點

第一章最優(yōu)化問題總論無論做任何一件事，人們總希望以最少的代價取得最大的效益，也就是力求最好，這就是優(yōu)化問題．最優(yōu)化就是在一切可能的方案中選擇一個最好的方案以達到最優(yōu)目標的學科．例如，從甲地到乙地有公路、水路、鐵路、航空四種走法，如果我們追求的目標是省錢，那么只要比較一下這四種走法的票價，從中選擇最便宜的那一種走法就達到目標．這是最簡單的最優(yōu)化問題，實際優(yōu)化問題一般都比較復(fù)雜．概括地說，凡是追求最優(yōu)目標的數(shù)學問題都屬于最優(yōu)化問題．作為最優(yōu)化問題，一般要有三個要素：第一是目標；第二是方案；第三是限制條件．而且目標應(yīng)是方案的“函數(shù)”．如果方案與時間無關(guān)，則該問題屬于靜態(tài)最優(yōu)化問題；否則稱為動態(tài)最優(yōu)化問題．§1.1最優(yōu)化問題數(shù)學模型最簡單的最優(yōu)化問題實際上在高等數(shù)學中已遇到，這就是所謂函數(shù)極值，我們習慣上又稱之為經(jīng)典極值問題．例1.1對邊長為a的正方形鐵板，在四個角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？解設(shè)剪去的正方形邊長為x，由題意易知，與此相應(yīng)的水槽容積為．令 ，得兩個駐點：．第一個駐點不合實際，這是因為剪去4個邊長為的正方形相當于將鐵板全部剪去．現(xiàn)在來判斷第二個駐點是否為極大點．∵ ，，∴ 是極大點．因此，每個角剪去邊長為的正方形可使所制成的水槽容積最大．例1.2求側(cè)面積為常數(shù)，體積最大的長方體體積．解設(shè)長方體的長、寬、高分別為體積為，則依題意知體積為，條件為．由拉格朗日乘數(shù)法，考慮函數(shù)， 由題意可知應(yīng)是正數(shù)，由此，將上面三個等式分別乘以并利用條件，得到比較以上三式可得，從而．又側(cè)面積固定的長方體的最大體積客觀存在，因此側(cè)面積固定的長方體中以正方體體積最大，其最大值為．例1.3某單位擬建一排四間的停車房，平面位置如圖1.1所示．由于資金及材料的限制，圍墻和隔墻的總長度不能超過40m，為使車房面積最大，應(yīng)如何選擇長、寬尺寸？解設(shè)四間停車房長為，寬為．由題意可知面積為，且變量，應(yīng)滿足，．x2x1圖1.1x2x1圖1.1以上三個例子，雖然簡單，但是它代表了三種類型的最優(yōu)化問題．第一個例子代表無約束極值問題：一般可表示為或．這里，是定義在上的可微函數(shù)．求極值的方法是從如下含有個未知數(shù)的非線性方程組中解出駐點，然后判定或驗證這些駐點是不是極值點．第二個例子代表具有等式約束的極值問題：一般可表示為該問題的求解通常采用拉格朗日乘數(shù)法，即把這個問題轉(zhuǎn)化為求的無約束極值問題．第三個例子代表具有不等式約束的極值問題．下面具體分析上述三種類型的最優(yōu)化問題中按經(jīng)典極值問題解法可能出現(xiàn)不能解決的情況：（1）當變量個數(shù)增加且方程組又是非線性，求解此方程組只有在相當特殊情況下才能人工解出．正因為如此，通常高等數(shù)學中的求極值問題的變量個數(shù)一般不超過三個．（2）當限制條件出現(xiàn)不等式，無論變量數(shù)多少，按經(jīng)典極值方法求解根本無法解決．直到本世紀50年代，最優(yōu)化理論的建立以及電子計算機的迅速發(fā)展，才為求解各種最優(yōu)化問題提供了雄厚的基礎(chǔ)和有效手段．不過最優(yōu)化方法作為一門嶄新的應(yīng)用學科，有關(guān)理論和方法還沒有完善，有許多問題還有待解決，目前正處于迅速發(fā)展之中．最優(yōu)化問題的數(shù)學模型包含三個要素：變量（又稱設(shè)計變量）、目標函數(shù)、約束條件．一、變量一個優(yōu)化設(shè)計方案是用一組設(shè)計參數(shù)的最優(yōu)組合來表示的．這些設(shè)計參數(shù)可概括地劃分為兩類：一類是可以根據(jù)客觀規(guī)律、具體條件、已有數(shù)據(jù)等預(yù)先給定的參數(shù)，統(tǒng)稱為常量；另一類是在優(yōu)化過程中經(jīng)過逐步調(diào)整，最后達到最優(yōu)值的獨立參數(shù)，稱為變量．優(yōu)化問題的目的就是使各變量達到最優(yōu)組合．變量的個數(shù)稱為優(yōu)化問題的維數(shù)．例如有個變量的優(yōu)化問題就是在維空間中尋優(yōu)．維空間中的點就代表優(yōu)化問題中的一個方案．當變量為連續(xù)量時，稱為連續(xù)變量；若變量只能在離散量中取值，稱為離散變量．二、目標函數(shù)反映變量間相互關(guān)系的數(shù)學表達式稱為目標函數(shù)．其值的大小可以用來評價優(yōu)化方案的好壞．按照規(guī)范化的形式，一般把優(yōu)化問題歸結(jié)為求目標函數(shù)的極小化問題，換句話說，目標函數(shù)值越小，優(yōu)化方案越好．對于某些追求目標函數(shù)極大的問題，可以轉(zhuǎn)化成求其負值最小的問題，即．因此在本書的敘述中，一律把優(yōu)化問題描述為目標函數(shù)的極小化問題，其一般形式為．如果優(yōu)化問題只有一個目標函數(shù)，稱為單目標函數(shù)，如果優(yōu)化問題同時追求多個目標，則該問題的目標函數(shù)稱為多目標函數(shù)．多目標優(yōu)化問題的目標函數(shù)通常表示為，其中．這時的目標函數(shù)在目標空間中是一個維矢量，所以又稱之為矢量優(yōu)化問題（一般用min加一個前綴“”來表示矢量極小化）．三、約束條件變量間本身應(yīng)該遵循的限制條件的數(shù)學表達式稱為約束條件或約束函數(shù)．約束條件按其表達式可分為不等式約束和等式約束兩種，即上式中“s.t.”為Subjectto的縮寫，意即“滿足于”或“受限于”．按約束條件的作用還可將約束條件劃分為起作用的約束（緊約束、有效約束）和不起作用的約束（松約束、消極約束）．等式約束相當于空間里一條曲線（曲面或超曲面），點X必須為該曲線（曲面或超曲面）上的一點，因而總是緊約束．有一個獨立的等式約束，就可用代入法消去一個變量，使優(yōu)化問題降低一維．因此，數(shù)學模型中獨立的等式約束個數(shù)應(yīng)小于變量個數(shù)；如果相等，就不是一個待定優(yōu)化系統(tǒng)，而是一個沒有優(yōu)化余地的既定系統(tǒng)．不等式約束通常是以其邊界表現(xiàn)出約束作用的，它只限制點X必須落在允許的區(qū)域內(nèi)（包括邊界上），因而不等式約束的個數(shù)與變量個數(shù)無關(guān)．不帶約束條件的優(yōu)化問題稱為無約束最優(yōu)化問題；帶約束條件的優(yōu)化問題稱為約束最優(yōu)化問題．四、帶約束條件的優(yōu)化問題數(shù)學模型表示形式綜上所述，全書所要討論的問題是如下的（靜態(tài)）最優(yōu)化問題，其表示形式有三種：第一種最優(yōu)化問題表示形式為 第二種最優(yōu)化問題表示形式為 第三種最優(yōu)化問題表示形式為 （1.1）其中．上述三種表示形式中，稱為集約束．在所討論的最優(yōu)化問題中，集約束是無關(guān)緊要的．這是因為一般，不然的話，通常也可用不等式約束表達出來．因此今后一般不再考慮集約束．滿足所有約束的點稱為容許點或可行點．容許點的集合稱為容許集或可行域．可用表示．一般地，對于最優(yōu)化問題（1.1）的求解，是指在可行域內(nèi)找一點，使得目標函數(shù)在該點取得極小值，即這樣的稱為問題（1.1）的最優(yōu)點，也稱極小點，而相應(yīng)的目標函數(shù)值稱為最優(yōu)值；合起來，稱為最優(yōu)解，但習慣上常把本身稱為最優(yōu)解．最優(yōu)點的各分量和最優(yōu)值必須是有限數(shù)．§1.2最優(yōu)化問題的算法一、二維最優(yōu)化問題的圖解法二維最優(yōu)化問題具有鮮明的幾何解釋，這對于理解有關(guān)理論和掌握所述的方法是很有益處的．下面討論的二維最優(yōu)化問題為（一）約束集合當約束函數(shù)為線性時，等式約束在的坐標平面上為一條直線；不等式約束在的坐標平面上為一半平面．當約束函數(shù)（例如）為非線性時，則等式約束條件在的坐標平面上為一條曲線（如圖1.2所示）．當約束函數(shù)（例如）為非線性時，則不等式約束在的坐標平面上為曲線把坐標平面分成兩部分當中的一部分（如圖1.3所示）．圖1.2 圖1.3綜上所述，當把約束條件中的每一個等式所確定的曲線，以及每一個不等式所確定的部分在坐標平面上畫出之后，它們相交的公共部分即為約束集合D．例1.4在坐標平面上畫出約束集合．解滿足的區(qū)域為以原點為圓心，半徑為1的圓盤；滿足的區(qū)域為第一象限中的扇形（如圖1.4所示）．（二）等高線我們知道在三維空間中表示一張曲面．（其中為常數(shù)）在三維空間中表示平行于平面的一個平面，這個平面上任何一點的高度都等于常數(shù)（如圖1.5所示）．圖1.4 圖1.5現(xiàn)在，在三維空間中曲面與平面有一條交線．交線在平面上的投影曲線是，可見曲線上的點到平面的高度都等于常數(shù)，也即曲線上的的函數(shù)值都具有相同的值．當常數(shù)取不同的值時，重復(fù)上面的討論，在平面上得到一簇曲線——等高線．不難看出，等高線的形狀完全由曲面的形狀所決定；反之，由等高線的形狀也可以推測出曲面的形狀．在以后的討論中，不必具體畫出曲面的圖形，只須在平面上變動常數(shù)畫出曲線簇．例1.5在坐標平面上畫出目標函數(shù)的等高線．解因為當取時，曲線表示是以原點為圓心，半徑為的圓．因此等高線是一簇以原點為圓心的同心圓（如圖1.6所示）．圖1.6（三）幾何意義及圖解法當在坐標平面上分別畫出約束集合D以及目標函數(shù)的等高線后，不難求出二維最優(yōu)化問題的最優(yōu)解．下面舉例說明．例1.6用圖解法求解二維最優(yōu)化問題解由例1.4得到約束集合D（如圖1.7所示）．目標函數(shù)的等高線是以為圓心的同心圓，并且這簇同心圓的外圈比內(nèi)圈的目標函數(shù)值大．因此，這一問題成為在約束集合中找一點，使其落在半徑最小的那個同心圓上．不難看出，問題的最優(yōu)解．圖1.7二、最優(yōu)化問題的迭代解法（一）迭代方法在經(jīng)典極值問題中，解析法雖然具有概念簡明，計算精確等優(yōu)點，但因只能適用于簡單或特殊問題的尋優(yōu)，對于復(fù)雜的工程實際問題通常無能為力，所以極少使用．最優(yōu)化問題的迭代算法是指：從某一選定的初始點出發(fā)，根據(jù)目標函數(shù)、約束函數(shù)在該點的某些信息，確定本次迭代的一個搜索方向和適當?shù)牟介L，從而到達一個新點，用式子表示即為 （1.2）式中代表前一次已取得的迭代點，在開始計算時為迭代初始點，代表新的迭代點，代表第次迭代計算的搜索方向，代表第次迭代計算的步長因子．按照式（1.2）進行一系列迭代計算所根據(jù)的思想是所謂的“爬山法”，就是將尋求函數(shù)極小點（無約束或約束極小點）的過程比喻為向“山”的頂峰攀登的過程，始終保持向“高”的方向前進，直至達到“山頂”．當然“山頂”可以理解為目標函數(shù)的極大值，也可以理解為極小值，前者稱為上升算法，后者稱為下降算法．這兩種算法都有一個共同的特點，就是每前進一步都應(yīng)該使目標函數(shù)有所改善，同時還要為下一步移動的搜索方向提供有用的信息．如果是下降算法，則序列迭代點的目標函數(shù)值必須滿足下列關(guān)系．如果是求一個約束的極小點，則每一次迭代的新點都應(yīng)該在約束可行域內(nèi)，即圖1.8為迭代過程示意圖．由上面的迭代過程可知，在迭代過程中有兩個規(guī)則需要確定：一個是搜索方向的選取；一個是步長因子的選?。坏┖偷倪x取方法確定，則一種迭代算法就確定，即不同的規(guī)則就對應(yīng)不同的最優(yōu)化方法．（二）收斂速度與計算終止準則（1）收斂速度作為一個算法，能夠收斂于問題的最優(yōu)解當然是必要８的，但僅收斂還不夠，還必須能以較快的速度收斂，這才是好的算法．圖1.8定義1.1設(shè)由算法A產(chǎn)生的迭代點列在某種“||·||”的意義下收斂于點，即，若存在實數(shù)及一個與迭代次數(shù)無關(guān)的常數(shù)，使得則稱算法A產(chǎn)生的迭代點列具有階收斂速度，或稱算法A為階收斂的．特別地：①當時，稱迭代點列具有線性收斂速度或稱算法A為線性收斂的．②當時，或時，稱迭代點列具有超線性收斂速度或稱算法A是超線性收斂．③當時，迭代點列叫做具有二階收斂速度或算法A是二階收斂的．一般認為，具有超線性收斂或二階收斂的算法是較快速的算法．例1.7設(shè)一算法A產(chǎn)生迭代點列，它收斂于點，試判定算法A的收斂速度．解因為 ，即?。运惴ˋ具有線性收斂速度．例1.8設(shè)一算法A產(chǎn)生迭代點列，它收斂于，試確定A的收斂速度．解因為 ，即?。訟是超線性收斂的．（2）計算終止準則用迭代方法尋優(yōu)時，其迭代過程不能無限制地進行下去，那么什么時候截斷這種迭代呢？這就是迭代什么時候終止的問題．從理論上說，當然希望最終迭代點到達理論極小點，或者使最終迭代點與理論極小點之間的距離足夠小時才終止迭代．但是這在實際上是辦不到的．因為對于一個待求的優(yōu)化問題，其理論極小點在哪里并不知道．所知道的只是通過迭代計算獲得的迭代點列，因此只能從點列所提供的信息來判斷是否應(yīng)該終止迭代．對于無約束優(yōu)化問題通常采用的迭代終止準則有以下幾種：①點距準則相鄰兩迭代點之間的距離已達到充分小，即，上式中是一個充分小的正數(shù)，代表計算精度．②函數(shù)下降量準則相鄰兩迭代點的函數(shù)值下降量已達到充分?。敃r，可用函數(shù)絕對下降量準則．當時，可用函數(shù)相對下降量準則．③梯度準則目標函數(shù)在迭代點的梯度已達到充分小，即．這一準則對于定義域上的凸函數(shù)是完全正確的．若是非凸函數(shù)，有可能導(dǎo)致誤把駐點作為最優(yōu)點．（凸函數(shù)的定義請參見第二章2.6節(jié)）對于約束優(yōu)化問題，不同的優(yōu)化方法有各自的終止準則．綜上所述，優(yōu)化算法的基本迭代過程如下：①選定初始點，置．②按照某種規(guī)則確定搜索方向．③按某種規(guī)則確定使得．④計算．⑤判定是否滿足終止準則．若滿足，則打印和，停機；否則置，轉(zhuǎn)②．上述算法用框圖表達如圖1.9．NYNYX是否滿足終止準則輸出X，f(X)開始結(jié)束選定X0確定P確定t，使得f(X0+tP)<f(X0)X=X0+tPX0=X圖1.9§1.3最優(yōu)化算法分類所謂優(yōu)化算法，其實就是一種搜索過程或規(guī)則，它是基于某種思想和機制，通過一定的途徑或規(guī)則來得到滿足用戶要求的問題的解．就優(yōu)化機制與行為而分，目前工程中常用的優(yōu)化算法主要可分為：經(jīng)典算法、構(gòu)造型算法、改進型算法、基于系統(tǒng)動態(tài)演化的算法和混合型算法等．（1）經(jīng)典算法．包括線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃和分枝定界等運籌學中的傳統(tǒng)算法，其算法計算復(fù)雜性一般很大，只適于求解小規(guī)模問題，在工程中往往不實用．（2）構(gòu)造型算法．用構(gòu)造的方法快速建立問題的解，通常算法的優(yōu)化質(zhì)量差，難以滿足工程需要．譬如，調(diào)度問題中的典型構(gòu)造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法等．（3）改進型算法，或稱鄰域搜索算法．從任一解出發(fā)，對其鄰域的不斷搜索和當前解的替換來實現(xiàn)優(yōu)化．根據(jù)搜索行為，它又可分為局部搜索法和指導(dǎo)性搜索法．①局部搜索法．以局部優(yōu)化策略在當前解的鄰域中貪婪搜索，如只接受優(yōu)于當前解的狀態(tài)作為下一當前解的爬山法；接受當前解鄰域中的最好解作為下一當前解的最陡下降法等．②指導(dǎo)性搜索法．利用一些指導(dǎo)規(guī)則來指導(dǎo)整個解空間中優(yōu)良解的探索，如SA、GA、TS等．（4）基于系統(tǒng)動態(tài)演化的算法．將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動態(tài)的演化過程，基于系統(tǒng)動態(tài)的演化來實現(xiàn)優(yōu)化，如神經(jīng)網(wǎng)絡(luò)和混沌搜索等．（5）混合型算法．指上述各算法從結(jié)構(gòu)或操作上相混合而產(chǎn)生的各類算法．優(yōu)化算法當然還可以從別的角度進行分類，如確定性算法和不確定性算法，局部優(yōu)化算法和全局優(yōu)化算法等．§1.4組合優(yōu)化問題簡介一、組合優(yōu)化問題建模優(yōu)化問題涉及的工程領(lǐng)域很廣，問題種類與性質(zhì)繁多，歸納而言，最優(yōu)化問題可分為函數(shù)優(yōu)化問題和組合優(yōu)化問題兩大類，上一節(jié)介紹的最優(yōu)化數(shù)學模型屬于函數(shù)優(yōu)化問題，該函數(shù)優(yōu)化的對象是一定區(qū)間內(nèi)的連續(xù)變量，而組合優(yōu)化的對象則是解空間中的離散狀態(tài)．本節(jié)重點介紹組合優(yōu)化問題．組合優(yōu)化問題是通過對數(shù)學方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，所研究的問題涉及信息技術(shù)、經(jīng)濟管理、工業(yè)工程、交通運輸、通信網(wǎng)絡(luò)等諸多領(lǐng)域，該問題數(shù)學模型可表示為其中為目標函數(shù)，和為約束函數(shù)，X為決策變量，表示有限個點組成的集合．一個組合優(yōu)化問題可用3個參數(shù)表示，其中表示決策變量的定義域，D表示可行解區(qū)域，D中的任何一個元素稱為該問題的可行解，表示目標函數(shù)，滿足的可行解稱為該問題的最優(yōu)解．組合最優(yōu)化問題的特點是可行解集合為有限集．由直觀可知，只要將中有限個點逐一判別是否滿足約束條件和比較目標函數(shù)值的大小，該問題的最優(yōu)解一定存在并可以求得，下面是三個典型的組合優(yōu)化問題．例1.90-1背包問題（knapsackproblem）設(shè)有一個容積為的背包，個體積分別為，價值分別為的物品，如何以最大的價值裝包?這個問題稱為0-1背包問題．用數(shù)學模型表示為， （1.3）其中目標（1.3）欲使包內(nèi)所裝物品的價值最大，式（1.4）為包的能力限制，式（1.5）表示為二進制變量，表示裝第i個物品，則表示不裝．例1.10旅行商問題（TSP，travelingsalesmanproblem）一個商人欲到個城市推銷商品，每兩個城市i和之間的距離為，如何選擇一條道路使得商人每個城市走一遍后回到起點且所走路徑最短．TSP還可以細分為對稱和非對稱距離兩大類問題．當對任意的時都有，則稱該TSP為對稱距離TSP，否則稱為非對稱距離TSP．對一般的TSP，它的一種數(shù)學模型描述為， （1.6）以上是基于圖論的數(shù)學模型．其中式（1.10）中的決策變量=1表示商人行走的路線包含從城市到城市的路徑，表示商人沒有選擇走這條路．的約束可以減少變量的個數(shù)，使得共有個決策變量．目標（1.6）要求距離之和最小．式（1.7）要求商人從城市出來一次，式（1.8）要求商人走入城市只有一次．式（1.7）和式（1.8）表示每個城市經(jīng)過一次．僅有式（1.7）和式（1.8）的約束無法避免回路的產(chǎn)生，一條回路是由個城市和條弧組成，因此，式（1.9）約束旅行商在任何一個城市子集中不形成回路，其中表示集合中元素個數(shù)．例1.11聚類問題m維空間上的個模式要求聚類成類，使得各類本身內(nèi)的點最相近，即，其中為第類的中心，，，為第類中的點數(shù)．二、算法復(fù)雜性前面給大家介紹的三個組合優(yōu)化問題例子，模型建立都比較簡單，但要求它們的最優(yōu)解卻很困難，而解模型的困難主要原因是所謂的“組合爆炸”，如聚類問題的可能劃分方式有個，TSP問題有個．顯然狀態(tài)數(shù)量隨問題規(guī)模呈超指數(shù)增長，若計算機每秒處理1億種排列，則列舉20個城市問題的20！種排列約需幾百年．如此巨大的計算量是無法承受的，更不用談更大規(guī)模問題的求解，因此解決這些問題的關(guān)鍵在于尋求有效的優(yōu)化算法，也正是由于組合優(yōu)化問題算法的復(fù)雜性，激起了人們對它的理論與算法研究的興趣．算法的復(fù)雜性是指算法對時間復(fù)雜性和對空間復(fù)雜性．按照算法復(fù)雜性求解的難易程度，可把組合優(yōu)化問題分為P類，NP類和NP完全類．算法或問題的復(fù)雜性一般表示為問題規(guī)模（如TSP問題中的城市數(shù)）的函數(shù)，時間的復(fù)雜性記為，空間的復(fù)雜性記為．在算法分析和設(shè)計中，沿用實用性的復(fù)雜性概念，即把求解問題的關(guān)鍵操作，如加、減、乘，比較等運算指定為基本操作，算法執(zhí)行基本操作的次數(shù)則定義的算法的時間復(fù)雜性，算法執(zhí)行期間占用的存儲單元則定義為算法的空間復(fù)雜性．P類問題指具有多項式時間求解算法的問題類．許多優(yōu)化問題仍沒有找到求得最優(yōu)解的多項式時間算法，稱這種比P類問題更廣泛的問題為非確定型多項式算法的問題類，即NP問題．三、NP完全問題離散問題的求解常常要從有限個方案中選出一個滿意的結(jié)果來，也許有人認為，從有限個方案中挑選一個，總是比較容易的．然而，事實并非如此，關(guān)鍵在于問題的規(guī)模．由于計算機的出現(xiàn)，人們對問題的求解在觀念上發(fā)生了改變，一個在理論上可解的問題如果在求解時需要花費相當多，以至于不合理的時間（如幾百年甚至更長時間），我們不能認為它已解決，而應(yīng)當努力尋找更好的算法．如何比較算法的好壞呢？從不同的角度出發(fā)可以有不同的回答．這里，僅就算法的計算速度作一個十分粗略的比較．設(shè)有一臺每小時能進行M次運算的計算機．并設(shè)問題已有兩種不同的算法，算法A對規(guī)模為的問題約需作次運算，算法B則約需作次運算．運用算法A在一個小時內(nèi)大約可解一個規(guī)模為的問題，而算法B則大約可解一個規(guī)模為的問題．現(xiàn)在假設(shè)計算機有了改進，例如計算速度提高了100倍．此時，利用算法A能求解的問題規(guī)模增大了10倍，利用算法B可解的問題規(guī)模只增加了．前者得到了成倍的增加，而后者則幾乎沒有什么改變，今天無法求解的問題，將來也很少有希望解決．由于這一原因，對算法作如下分類．定義1.2（多項式算法）設(shè)A是求解某類問題D的一個算法，為問題D的規(guī)模，用表示用算法A在計算機上求解這一問題時需作的初等運算的次數(shù)．若存在一個多項式和正整數(shù)N，當時，總有（不論求解的D是怎樣的具體實例），則稱算法A是求解問題D的一個多項式算法．定義1.3（指數(shù)算法）設(shè)算法B是求解某類問題D的一個算法，若存在一個常數(shù)，對任意，總可以找到問題D的一個規(guī)模為的實例，用算法B求解時，所需的計算量約為，則稱B為求解問題D的一個指數(shù)算法．多項式算法被稱為是“好”算法（或有效算法），而指數(shù)算法則一般認為是“壞”算法，因為它只能用來求解規(guī)模很小的問題．這樣看來，對一個問題只有在找到求解它的多項式算法后才能較為放心．然而十分可惜的是，對于許多具有廣泛應(yīng)用價值的離散模型，人們至今仍未找到多項式算法．現(xiàn)在的任何算法在最壞的情況下計算量均可達到或接近．1971年和1972年，S.Cook和R.Karp分別發(fā)表了相關(guān)論文，奠定了NP完全理論基礎(chǔ)．Cook指出，NP完全類問題，具有兩個性質(zhì)：（1）這類問題中的任何一個問題至今均未發(fā)現(xiàn)有多項式算法．（2）只要其中任一個問題找到了多項式算法，那么其他所有問題也就有了多項式算法．現(xiàn)在，NP完全類中的問題已被擴充到了四千多個，其中包括前面討論的旅行商問題．對它們的研究使人們越來越相信這樣一個猜測：對這類問題也許根本不存在多項式算法．第二章最優(yōu)化問題數(shù)學基礎(chǔ)為了便于學習最優(yōu)化方法，本章將對與優(yōu)化方法密切相關(guān)的數(shù)學知識作一簡要介紹，而有些數(shù)學知識將在講解各種算法時，隨之介紹．§2.1二次型與正定矩陣一、二次型與實對稱矩陣二次型理論在最優(yōu)化設(shè)計中應(yīng)用十分廣泛．應(yīng)用矩陣的乘法運算，二次型與實對稱矩陣緊密地聯(lián)系在一起了，從而二次型的基本問題又可轉(zhuǎn)化成實對稱矩陣問題．二次型理論問題起源于化二次曲線和二次曲面的方程為標準形式的問題．推廣到n維空間中，二次超曲面的一般方程為用矩陣表示可簡記為其中矩陣A的元素正是二次型的項的系數(shù)的一半，是二次型的項的系數(shù)．因此，二次型和它的矩陣A是相互唯一決定的，且．二、正定矩陣定義2.1如果二次型對于任何一組不全為零的數(shù)恒有，則稱正定，且二次型矩陣A也稱為正定．簡言之，一個對稱矩陣A如果是正定的，則二次型對于所有非零向量X其值總為正．類似可以給出定義，若二次型，則A為半正定矩陣；若，則A為半負定矩陣；若二次型既不是半正定又不是半負定，就稱矩陣A為不定的．矩陣A為正定的充要條件是它的行列式的順序主子式全部大于零，即．由此可見，正定矩陣必然是非奇異的．例2.1判斷矩陣是否正定．解∵，∴A是正定的．§2.2方向?qū)?shù)與梯度一、方向?qū)?shù)所謂方向?qū)?shù)的概念是作為偏導(dǎo)數(shù)的一個推廣而引入的，它主要研究函數(shù)沿任一給定方向的變化率．定義2.2設(shè)在點處可微，P是固定不變的非零向量，是方向P上的單位向量，則稱極限 （2.1）為函數(shù)在點處沿P方向的方向?qū)?shù)，式中是它的記號．定義2.3設(shè)是連續(xù)函數(shù)，，且，若存在，當時都有，則稱P為在點處的下降方向．若，則稱P為在點處的上升方向．由以上兩個定義可立刻得到如下的結(jié)論：若，則從出發(fā)在附近沿P方向是下降；若，則從出發(fā)在附近沿P方向是上升．事實上，若，則當充分小時，根據(jù)式（2.1）必有，即 ，其中是從出發(fā)在P方向上的點，說明是下降的．同理可以說明，若，則是上升的．二、梯度定義2.4以的n個偏導(dǎo)數(shù)為分量的向量稱為在X處的梯度，記為梯度也可以稱為函數(shù)關(guān)于向量的一階導(dǎo)數(shù)．以下幾個特殊類型函數(shù)的梯度公式是常用的：（1）若（常數(shù)），則，即；（2）．證設(shè)，則．于是的第個分量是所以．（3）．（4）若是對稱矩陣，則．三、梯度與方向?qū)?shù)之間的關(guān)系定理2.1設(shè)在點處可微，則，其中是方向上的單位向量．證明在相應(yīng)的數(shù)學分析中可找到（故略去）．由這個定理容易得到下列結(jié)論：(1)若，則P的方向是函數(shù)在點處的下降方向；(2)若，則的方向是函數(shù)在點處的上升方向．方向?qū)?shù)的正負決定了函數(shù)值的升降，而升降的快慢就由它的絕對值大小決定．絕對值越大，升降的速度就越快，即=，上式中的等號，當且僅當?shù)姆较蚺c的方向相同時才成立．由此可得如下重要結(jié)論(如圖2.1所示）：(1)梯度方向是函數(shù)值的最速上升方向；(2)函數(shù)在與其梯度正交的方向上變化率為零；(3)函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；(4)梯度反方向是函數(shù)值的最速下降方向．對于一個最優(yōu)化問題，為了盡快得到最優(yōu)解，在每一步迭代過程中所選取的搜索方向總是希望它等于或者是靠近于目標函數(shù)的負梯度（即－）圖2.1的方向，這樣才能使函數(shù)值下降的最快．例2.2試求目標函數(shù)在點處的最速下降方向，并求沿這個方向移動一個單位長后新點的目標函數(shù)值．解因為，所以最速下降方向是．這個方向上的單位向量是．故新點是，對應(yīng)目標函數(shù)值為．§2.3海色矩陣及泰勒展式一、海色（Hesse）矩陣前面說過，梯度是關(guān)于的一階導(dǎo)數(shù)，現(xiàn)在要問關(guān)于的二階導(dǎo)數(shù)是什么？定義2.5設(shè)：，，如果在點處對于自變量的各分量的二階偏導(dǎo)數(shù)都存在，則稱函數(shù)在點處二階可導(dǎo)，并且稱矩陣是在點處的Hesse矩陣．在數(shù)學分析中已經(jīng)知道，當在點處的所有二階偏導(dǎo)數(shù)為連續(xù)時有因此，在這種情況下Hesse矩陣是對稱的．例2.3求目標函數(shù)的梯度和Hesse矩陣．解因為，所以 ．又因為所以 ．例2.4設(shè)，求線性函數(shù)在任意點X處的梯度和Hesse矩陣．解設(shè)，則， （2.2）∴．由式（2.2）進而知∴ （階零矩陣）．例2.5設(shè)是對稱矩陣，，求二次函數(shù)在任意點處的梯度和Hesse矩陣．解設(shè)，，則將它對各變量求偏導(dǎo)數(shù)，得∴ ．在上式中顯然再對它們求偏導(dǎo)數(shù)得∴．以上例子說明，元函數(shù)求導(dǎo)與一元函數(shù)的求導(dǎo)在形式上是一致的，即線性函數(shù)的一階導(dǎo)數(shù)為常向量，其二階導(dǎo)數(shù)為零矩陣；而二次函數(shù)的一階導(dǎo)數(shù)為線性向量函數(shù)，二階導(dǎo)數(shù)為常矩陣．最后介紹在今后的計算中要用到的向量函數(shù)的導(dǎo)數(shù)．定義2.6設(shè)，記，如果在點處對于自變量的各分量的偏導(dǎo)數(shù)都存在，則稱向量函數(shù)在點處是一階可導(dǎo)的，并且稱矩陣是在點處的一階導(dǎo)數(shù)或Jacobi矩陣，簡記為．由于元函數(shù)的梯度是向量函數(shù)所以的一階導(dǎo)數(shù)或Jacobi矩陣為即 ．據(jù)此，從上式得知，函數(shù)梯度的Jacobi矩陣即為此函數(shù)的Hesse矩陣．下面給出今后要用到的幾個公式：（1），其中是分量全為常數(shù)的維向量，是階零矩陣．（2），其中是維向量，是階單位矩陣．（3），其中是階矩陣．（4）設(shè)，其中，，則．二、泰勒展開式多元函數(shù)的泰勒展開在最優(yōu)化方法中十分重要，許多方法及其收斂性的證明是從它出發(fā)的，這里給出泰勒展開定理及其證明．定理2.2設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，則，（2.3）其中，而．證設(shè)，于是，．對按一元函數(shù)在點展開，得到，其中．令，于是． （2.4）又因為，，代入式（2.4）中，所以．式（2.3）還可以寫成．§2.4極小點的判定條件函數(shù)在局部極小點應(yīng)滿足什么條件？反之，滿足什么條件的是局部極小點？這是我們關(guān)心的基本問題．下面針對多元函數(shù)的情形給出各類極小點的定義．定義2.7對于任意給定的實數(shù)，滿足不等式的的集合稱為點的鄰域，記為．定義2.8設(shè)，若存在點和數(shù)，都有，則稱為的局部極小點（非嚴格）．定義2.9設(shè)，若存在點和數(shù)，但，都有，則稱為的嚴格局部極小點．定義2.10設(shè)，若存在點，都有，則稱為在D上的全局極小點（非嚴格）．定義2.11設(shè)，若存在點，但，都有，則稱為在D上的嚴格全局極小點．由以上定義看到，是局部極小點，是指在以為中心的一個鄰域中在點處取得最小的值；而是全局極小點，是指在定義域D中在點處取得最小的值．全局極小點可能在某個局部極小點處取得，也可能在D的邊界上取得．實際問題通常是求全局極小點，但是直到目前為止，最優(yōu)化中絕大多數(shù)方法都是求局部極小點的，解決這一矛盾的一種方法是先求出所有的局部極小點，再求全局極小點．定理2.3設(shè)具有連續(xù)的一階偏導(dǎo)數(shù)．若是的局部極小點并且是D的內(nèi)點，則． （2.5）證設(shè)是任意單位向量，因為是的局部極小點，所以存在，當或時總有． （2.6）引入輔助一元函數(shù)，此時，由式（2.6）得．又因是D的內(nèi)點，所以與它對應(yīng)的是的局部極小點．又根據(jù)一元函數(shù)極小點的必要條件，得到，即．再由單位向量的任意性得．這里條件（2.5）僅僅是必要的，而不是充分的．例如在點處的梯度是，但是雙曲面的鞍點，而不是極小點（如圖2.2所示）．圖2.2定義2.12設(shè)是D的內(nèi)點．若，則稱為的駐點．定理2.4設(shè)具有連續(xù)二階偏導(dǎo)數(shù)，是D的一個內(nèi)點．若，并且是正定的，則是的嚴格局部極小點．證因為是正定矩陣，則必存在，使得對于所有的都有（參看高等代數(shù)二次型理論）．現(xiàn)在將在點處按泰勒公式展開，并注意到，于是可得當充分接近（但）時，上式左端的符號取決于右端第一項，因此．一般說來，這個定理僅具有理論意義．因為對于復(fù)雜的目標函數(shù)，Hesse矩陣不易求得，它的正定性就更難判定了．定理2.5若多元函數(shù)在其極小點處的Hesse矩陣是正定的，則它在這個極小點附近的等值面近似地呈現(xiàn)為同心橢球面簇．證設(shè)是多元函數(shù)的極小點，并設(shè)是充分靠近極小點的一個等值面，即充分?。言邳c展成泰勒公式，即右端第二項因是極小點有而消失．如果略去第4項，那么，又因為，所以（2.7）按假設(shè)正定，由二次型理論知式（2.7）是以為中心的橢球面方程．§2.5錐、凸集、凸錐在本節(jié)中，給出維Euclid空間中的錐、凸集和凸錐的定義，以及與其相關(guān)的一些概念和性質(zhì)．一、定義與簡單性質(zhì)定義2.13集合．若及任意的數(shù)，均有，則稱C為錐．定義2.14設(shè)是中的個已知點．若對于某點存在常數(shù)且使得，則稱是的凸組合．若且，則稱是的嚴格凸組合．定義2.15集合．若和，以及任意的數(shù)，均有則稱C為凸集．定義2.16設(shè)且，，則集合稱為中的半空間．特別地，規(guī)定空集是凸集．容易驗證，空間、半空間、超平面、直線、點、球都是凸集．定理2.6任意一組凸集的交仍然是凸集．證設(shè)，其中I是的下標集，都是凸集．任取，則對于任意都是．任取且，因是凸集，有．于是，即C是凸集．若集合C為錐，C又為凸集，則稱C為凸錐．若C為凸集，也為閉集，則稱C為閉凸集．若C為凸錐，也為閉集，則稱C為閉凸錐．由數(shù)學歸納法不難證明如下的定理2.7和2.8．定理2.7集合C為凸集的充分必要條件是，及任意數(shù)（），，有．定理2.8集合C為凸錐的充分必要條件是，及任意數(shù)（），均有．定義2.17有限個半空間的交稱為多面集，其中為矩陣，為維向量．例2.6集合為多面集，其幾何表示如圖2.3畫斜線部分．圖2.3在多面集的表達式中，若，則多面集也是凸錐，稱為多面錐．在有關(guān)凸集的理論及應(yīng)用中，極點和極方向的概念有著重要作用．定義2.18設(shè)為非空凸集，，若不能表示成中兩個不同點的凸組合；換言之，若假設(shè)，，必推得，則稱是凸集的極點．按此定義，圖2.4中多邊形的頂點和是極點，而和不是極點．圖2.4中圓周上的點均為極點．圖2.4由圖2.4可以看出，在給定的兩個凸集中，任何一點都能表示成極點的凸組合．定義2.19設(shè)為中的閉凸集，為非零向量，如果對中的每一個，都有射線，則稱向量為的方向．又設(shè)和是的兩個方向，若對任何正數(shù)，有，則稱和是兩個不同的方向．若的方向不能表示成該集合的兩個不同方向的正的線性組合，則稱為的極方向．圖2.5例2.7如圖2.5所示，對于集合，凡是與向量夾角小于或等于的向量，都是它的方向．和是的兩個極方向．的其它方向都能表示成這兩個極方向的正線性組合．例2.8設(shè)為非空集合，是非零向量．證明為的方向的充要條件是且．證按照定義2.19，為的方向的充要條件是對每一個，有．（2.8）根據(jù)集合的定義，由式（2.8）可得，（2.9）．（2.10）由于，及可取任意非負數(shù)，因此由式（2.9）和式（2.10）知及．對于有界多面集，它的每一個點可用極點的凸組合來表示，反之，由極點的凸組合表示的點一定屬于這個多面集．對此可簡要說明如下：設(shè)有多面集，如圖2.6(a)所示．若，則其中均為非負數(shù)，且，即為極點，和的凸組合．反之，設(shè)，，，則，即．如果多面集是無界的，那么對于該多面集中的任一點（極點除外），只用極點來表示是不行的，還需要用極方向．如圖2.6(b)所示，這時有，其中是中某個數(shù)，是某一個非負數(shù)．圖2.6概括起來，有下列定理：定理2.9設(shè)為非空多面集，則有（1）極點集非空，且存在有限個極點（2）極方向集合為空集的充要條件是有界．若無界，則存在有限個極方向（3）的充要條件是，其中，，．關(guān)于上述定理的證明參見參考文獻[6]．二、凸集分離定理凸集分離定理是凸分析中最重要的定理之一，它在最優(yōu)化理論和模型當中具有重要的應(yīng)用．所謂集合的分離是指對于兩個集合C1和C2存在一個超平面H，使得C1在H的一邊，而C2在H的另一邊．如果超平面方程為，那么對位于H某一邊的點必有，而對位于H另一邊的必有．定義2.20設(shè)C1和C2是中的兩個非空集合，是超平面，若對于每一個都有，對于每一個都有（或情況恰好相反），則稱超平面H分離集合C1和C2．定理2.10若C為閉凸集，，則存在，，以及數(shù)，對，有，并且存在，使得．定理2.11設(shè)C為凸集，，則存在，，使得，有．定理2.12設(shè)C為閉凸集，則C可表為所有包含C的半空間的交，即，其中．上述定理的證明過程參見參考文獻[6]．§2.6凸函數(shù)一、各類凸函數(shù)定義及性質(zhì)設(shè)函數(shù)定義在凸集C上，其中．定義2.21若存在常數(shù)，使得，以及，若有，則稱為一致凸函數(shù)；若有，則稱為嚴格凸函數(shù)；若有，則稱為凸函數(shù)．定義2.22設(shè)為可微函數(shù)．若，當都有，則稱為偽凸函數(shù)．定義2.23對，且，以及，若，則稱為嚴格擬凸函數(shù)；定義2.24對，以及，若，則稱為擬凸函數(shù)；定義2.25對，且，以及，若，則稱為強擬凸函數(shù)．定理2.13若為一致凸函數(shù)，則為嚴格凸函數(shù)．證：設(shè)為一致凸函數(shù)，則，，及，有，即為嚴格凸函數(shù)．定理2.14若為嚴格凸函數(shù)，則為凸函數(shù)．定理2.15設(shè)為可微函數(shù)．若為凸函數(shù)，則為偽凸函數(shù)．定理2.16設(shè)為偽凸函數(shù)，則為嚴格擬凸函數(shù)．定理2.17設(shè)為下半連續(xù)的嚴格擬凸函數(shù)，則為擬凸函數(shù)．定理2.18若為嚴格凸函數(shù)，則為強擬凸函數(shù)．定理2.19設(shè)為強擬凸函數(shù)，則為嚴格擬凸函數(shù)．下半連續(xù)的定義及定理2.14—定理2.19的證明過程參見參考文獻[6]．上述幾種凸函數(shù)有圖2.7所示的關(guān)系．圖2.7凸函數(shù)與凸集之間有如下關(guān)系：定理2.20設(shè)，其中C為非空凸集．若是凸函數(shù)，則對于任意實數(shù)，水平集是凸集．證若是空集，則是凸集．以下設(shè)非空，任取，則．設(shè)且，由是凸函數(shù)知，即，所以是凸集．判定一個函數(shù)是否為凸函數(shù)，一般說來是比較困難，但當函數(shù)可微時，有如下幾個定理可供使用．定理2.21設(shè)是可微函數(shù)，其中C為凸集．則（1）為凸函數(shù)的充要條件是，都有； （2.11）（2）為嚴格凸函數(shù)的充要條件是，且，都有．證（1）先證必要性．已知是C上的凸函數(shù)，要證式（2.11）．由凸函數(shù)定義知，對滿足的任意數(shù)都有，令，則．代入上式中，經(jīng)移項可得． （2.12）令，由的可微性，利用一階泰勒展式、方向?qū)?shù)定義及式（2.12），可得．這就證明了式（2.11）．再證充分性．任取一對數(shù)且．考慮點，根據(jù)充分性假設(shè)，應(yīng)有，．兩式分別乘以和后相加，得到．由凸函數(shù)定義知，是C上的凸函數(shù)．（2）充分性可依照（1）的充分性證得，下證必要性．因為嚴格凸函數(shù)本身是凸函數(shù)，所以，且，都有以下證明式中只能取“>”號．假設(shè)存在，且，使得 ． （2.12）取，由的嚴格凸性，有． （2.13）把式（2.12）代入式（2.13）中，經(jīng)整理得．根據(jù)本定理（1）部分結(jié)論得知，此式與是凸函數(shù)相矛盾．定理2.22設(shè)是二次可微函數(shù)，C為非空開凸集，則為C上凸函數(shù)的充要條件是Hesse矩陣在C上任意點均半正定．證明略．定理2.23設(shè)是二次可微函數(shù)，C為非空凸集．若Hesse矩陣在C上任意點均正定，則在C上為嚴格凸函數(shù)．證明略，需要注意，該定理的逆命題不真．例如在上為嚴格凸函數(shù)，但是它的Hesse矩陣在點處是半正定的．二、凸規(guī)劃定義2.26設(shè)，其中是非空凸集，是凸函數(shù)，則形式為的問題稱為凸規(guī)劃問題．更進一步，設(shè)若都是上的凸函數(shù)，都是上的線性函數(shù)，則容易驗證C是凸集．事實上，因為都是凸函數(shù)，根據(jù)定理2.20集合也都是凸集．此外，超平面，也都是凸集．顯然，C是的交集，根據(jù)定理2.6，C是凸集．于是，在這種情況下凸規(guī)劃問題又可表示成如下形式：如下定理指明凸規(guī)劃的一個重要性質(zhì)．定理2.24設(shè)是凸規(guī)劃問題的局部極小點，（1）若是凸函數(shù)，則是凸規(guī)劃問題全局極小點；（2）若是嚴格凸函數(shù)，則是凸規(guī)劃問題的唯一全局極小點．證（1）使用反證法．假設(shè)不是全局極小點，則必存在使得．對于與的任意凸組合，其中且，根據(jù)的凸性，有由此看到，當充分小時，充分接近，注意到此時也有，而這與是局部極小點相矛盾．因此必是全局極小點．（2）假設(shè)不是唯一全局極小點．必存在但使得．考慮中點．由的嚴格凸性，有．此式與為全局極小點相矛盾．這就證明了唯一性．定義2.27形式為（2.14）的函數(shù)稱為元二次函數(shù)，其中，這里的A是對稱矩陣，即．若A為正定，則稱（2.14）為正定二次函數(shù)．注意到，由定理2.23知，正定二次函數(shù)是嚴格凸函數(shù)，在最優(yōu)化算法構(gòu)造中它起著特殊的作用．定義2.28形式為 （2.15）的問題稱為二次規(guī)劃問題，其中是矩陣，是矩陣．正定§2.7約束問題的最優(yōu)性條件所謂最優(yōu)性條件就是最優(yōu)化問題的目標函數(shù)與約束函數(shù)在最優(yōu)點處滿足的充要條件．這種條件對于最優(yōu)化算法的終止判定和最優(yōu)化理論推證都是至關(guān)重要的．最優(yōu)性必要條件是指在最優(yōu)點處滿足哪些條件；充分條件是指滿足哪些條件的點是最優(yōu)點．本節(jié)僅講述最基本的結(jié)論．一、約束最優(yōu)解對約束優(yōu)化問題的求解，其目的是在由約束條件所規(guī)定的可行域內(nèi)，尋求一個目標函數(shù)值最小的點及其函數(shù)值．這樣的解稱為約束最優(yōu)解．約束最優(yōu)點除了可能落在可行域內(nèi)的情況外，更常常是在約束邊界上或等式約束曲面上，因此它的定義及它的一階必要條件與無約束優(yōu)化問題不同．（一）約束優(yōu)化問題的類型約束優(yōu)化問題根據(jù)約束條件類型的不同分為三種，其數(shù)學模型如下：（1）不等式約束優(yōu)化問題（IP型）（2.16）（2）等式約束優(yōu)化問題（EP型）（3）一般約束優(yōu)化問題（GP型）（二）約束優(yōu)化問題的局部解與全局解按一般約束優(yōu)化問題，其可行域為．若對某可行點存在，當與它鄰域的點之距離時，總有則稱為該約束優(yōu)化問題的一個局部最優(yōu)解．下面以一個簡單例子說明．設(shè)有１圖2.8對某些約束優(yōu)化問題，局部解可能有多個．在所有的局部最優(yōu)解中，目標函數(shù)值最小的那個解稱為全局最優(yōu)解．在上例中，由于，所以全局最優(yōu)解為．由此可知，約束優(yōu)化問題全局解一定是局部解，而局部解不一定是全局解．這與無約束優(yōu)化問題是相同的．二、約束優(yōu)化問題局部解的一階必要條件對于約束，現(xiàn)在進一步闡明起作用約束與不起作用約束的概念．一般的約束優(yōu)化問題，其約束包含不等式約束和等式約束．在可行點處，如果有，則該約束稱可行點的起作用約束；而如果有，則該約束稱可行點的不起作用約束．對于等式約束，顯然在任意可行點處的等式約束都是起作用約束．在某個可行點處，起作用約束在的鄰域內(nèi)起到限制可行域范圍的作用，而不起作用約束在處的鄰域內(nèi)就不產(chǎn)生影響．因此，應(yīng)把注意力集中在起作用約束上．（一）IP型約束問題的一階必要條件圖2.9所示為具有三個不等式約束的二維最優(yōu)化問題．圖2.9圖2.9（a）是最優(yōu)點在可行域內(nèi)部的一種情況．在此種情形下，點的全部約束函數(shù)值均大于零，所以這組約束條件對其最優(yōu)點都不起作用．換句話說，如果除掉全部約束，其最優(yōu)點也仍是同一個點．因此這種約束優(yōu)化問題與無約束優(yōu)化問題是等價的．圖2.9（b）所示的約束最優(yōu)點在的邊界曲線與目標函數(shù)等值線的切點處．此時，，所以是起作用約束，而其余的兩個是不起作用約束．既然約束最優(yōu)點是目標函數(shù)等值線與邊界的切點，則在點處目標函數(shù)的梯度與約束函數(shù)梯度矢量必共線，而且方向一致．若取非負乘子，則在處存在如下關(guān)系．另一種情況如圖2.9（c）所示．當前迭代點在兩約束交點上，該點目標函數(shù)的梯度矢量夾于兩約束函數(shù)的梯度矢量之間．顯然，在點鄰近的可行域內(nèi)部不存在目標函數(shù)值比更小的可行點．因此，點就是約束最優(yōu)點，記作．由圖可知，此時點目標函數(shù)的梯度可表達為約束函數(shù)梯度和的線性組合．若用代替即有成立，且式中的乘子和必為非負．總結(jié)以上各種情況，最優(yōu)解的一階必要條件為對于（2.16）IP型約束問題的一階必要條件討論如下：設(shè)最優(yōu)點位于個約束邊界的匯交處，則這個約束條件組成一個起作用的約束集．按上面的分析，對于點必有下式成立 （2.17）但是在實際求解過程中，并不能預(yù)先知道最優(yōu)點位于哪一個或哪幾個約束邊界的匯交處．為此，把個約束全部考慮進去，并取不起作用約束的相應(yīng)乘子為零，則最優(yōu)解的一階必要條件應(yīng)把式（2.17）修改為 （2.18）式（2.18）為IP型問題約束最優(yōu)解的一階必要條件，它與式（2.17）等價．因為在下，對于起作用約束，必有使式（2.18）中的第四式成立；對于不起作用約束，雖然而必有，可見式（2.18）與式（2.17）等價．（二）EP型約束問題的一階必要條件圖2.10所示為具有一個等式約束條件的二維化問題，其數(shù)學模型為在該問題中，等式約束曲線是它的可行域，而且目標函數(shù)等值線與約束曲線的切點是該約束問題的最優(yōu)解．圖2.10在點處，目標函數(shù)的梯度與約束函數(shù)的梯度共線．因此，在最優(yōu)點處一定存在一個乘子，使得成立．對于一般的維等式約束優(yōu)化問題，其數(shù)學模型為則為其解的一階必要條件為（三）GP型約束問題解的一階必要條件由上述不等式約束優(yōu)化與等式約束優(yōu)化問題的一階必要條件，可以推出一般約束優(yōu)化問題的條件．設(shè)維一般約束優(yōu)化問題的數(shù)學模型為 （2.19）則為其解的一階必要條件應(yīng)為 （2.20）函數(shù)稱為關(guān)于問題（2.19）的廣義拉格朗日函數(shù)，式中，為拉格朗日乘子．由于引入拉格朗日函數(shù)，條件（2.20）中的第一式可寫為．（四）Kuhn—Tｕcker條件（簡稱K—T條件）在優(yōu)化實用計算中，常常需要判斷某可行迭代點是否可作為約束最優(yōu)點輸出而結(jié)束迭代，或者對此輸出的可行結(jié)果進行檢查，觀察它是否已滿足約束最優(yōu)解的必要條件，這種判斷或檢驗通常借助于條件進行的．對于IP型問題，條件可敘述如下：如果是一個局部極小點，且各梯度矢量組成線性無關(guān)的矢量系，那么必存在一組非負乘子，使得成立．必須指出，在一般情形下，條件是判別約束極小點的一階必要條件，但并非充分條件．只是對于凸規(guī)劃問題，即對于目標函數(shù)為凸函數(shù)，可行域為凸集的最優(yōu)化問題，條件才是約束最優(yōu)化問題的充分條件．而且，在這種情況下的局部最優(yōu)解也必為全局最優(yōu)解．應(yīng)用條件檢驗?zāi)车c是否為約束最優(yōu)點的具體作法可按下述步驟進行：（1）檢驗是否為可行點．為此需要計算處的諸約束函數(shù)值，若是可行點，則．（2）選出可行點處的起作用約束．前面已求得個值，其中等于零或相當接近零的約束就是起作用約束．把這些起作用約束重新編排成序列．（3）計算點目標函數(shù)的梯度和I個起作用約束函數(shù)的梯度．（4）按條件，點應(yīng)滿足. (2.21）將式（2.21）中的各梯度矢量用其分量表示，則可得到為變量的線性方程組由于矢量系是線性無關(guān)的，所以該方程組存在唯一解．通過解此線性方程組，求得一組乘子，若所有乘子均為非負，即，則即為約束最優(yōu)解．否則，點就不是約束最優(yōu)點．例2.9設(shè)約束優(yōu)化問題它的當前迭代點為，試用條件判別它是否為約束最優(yōu)點．解：（1）計算點的諸約束函數(shù)值是可行點．（2）點起作用約束是．（3）求點梯度（4）求拉格朗日乘子按條件應(yīng)有寫成線性方程組解得．乘子均為非負，故滿足約束最優(yōu)解的一階必要條件．如圖2.11所示，點確為該約束優(yōu)化問題的局部最優(yōu)解，由于可行域是凸集，所以點也是該問題的全局最優(yōu)解．圖2.11GP型的約束最優(yōu)化問題的條件類似于IP型約束最優(yōu)化問題的條件：如果是一個局部極小點，且各梯度矢量和組成線性無關(guān)的矢量系，那么必存在兩組乘子和，使得（2.22）成立．三、約束優(yōu)化問題局部解的二階充分條件GP型的約束最優(yōu)化問題的極小點的二階充分條件是：設(shè)對條件和是可行的，若存在向量和，它們滿足條件（2.22），而且對滿足條件（2.23）的任意非零向量有，則為GP型的約束最優(yōu)化問題的嚴格局部極小點．這里當然要求和二次連續(xù)可微．式（2.23）中的是的下標的集合．第三章線性規(guī)劃及其對偶問題線性規(guī)劃是最優(yōu)化問題的一種特殊情形，也是運籌學的一個重要分支，它的實質(zhì)是從多個變量中選取一組適當?shù)淖兞孔鳛榻猓惯@組變量滿足一組確定的線性式，而且使一個線性目標函數(shù)達到最優(yōu)（最大或最?。€性規(guī)劃的應(yīng)用極為廣泛，自1949年美國數(shù)學家G.B.Dantzing提出一般線性規(guī)劃問題求解的方法——單純形法之后，線性規(guī)劃無論在理論上、計算方法和開拓新的應(yīng)用領(lǐng)域中，都獲得了長足的進步，線性規(guī)劃從解決技術(shù)問題的最優(yōu)化設(shè)計到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)、軍事、經(jīng)濟計劃和管理決策等領(lǐng)域都有廣泛的發(fā)展和應(yīng)用．本章主要從線性規(guī)劃的基本概念、數(shù)學模型、單純形法、對偶理論、靈敏度分析等方面進行介紹．§3.1線性規(guī)劃數(shù)學模型基本原理一、線性規(guī)劃的數(shù)學模型滿足以下三個條件的數(shù)學模型稱為線性規(guī)劃的數(shù)學模型：（1）每一個問題都用一組決策變量表示某一方案；每一組值就代表一個具體方案．（2）有一個目標函數(shù)，可用決策變量的線性函數(shù)來表示，按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化．（3）有一組約束條件，可用一組線性等式或不等式來表示．線性規(guī)劃問題的一般形式為這里，目標函數(shù)中的系數(shù)叫做目標函數(shù)系數(shù)或價值系數(shù)，約束條件中的常數(shù)叫做資源系數(shù)，約束條件中的系數(shù)叫做約束系數(shù)或技術(shù)系數(shù)．二、線性規(guī)劃問題的標準形式所謂線性規(guī)劃問題的標準形式，是指目標函數(shù)要求，所有約束條件都是等式約束，且所有決策定量都是非負的，即或簡寫為可以規(guī)定各約束條件中的資源系數(shù)，否則等式兩端乘以“”．線性規(guī)劃問題的矩陣表示為其中，，，．任意的線性規(guī)劃模型都可以轉(zhuǎn)化為標準形式：（1）若目標函數(shù)是求最大值的問題，這時只需將所有目標函數(shù)系數(shù)乘以“－1”，求最大值的問題就變成了求最小值的問題，即．求其最優(yōu)解后，把最優(yōu)目標函數(shù)值反號即得原問題的目標函數(shù)值．（2）若約束條件為不等式，這里有兩種情況：一種是“≤”不等式，則可在“≤”不等式的左端加入一個非負的新變量（叫松馳變量），把不等式變?yōu)榈仁剑涣硪环N是“≥”不等式，則可在“≥”不等式的左端減去一個非負松馳變量（也叫剩余變量），把不等式變?yōu)榈仁剑神Y變量在目標函數(shù)中對應(yīng)的系數(shù)為零．（3）若存在取值無約束的變量，可令，其中，．例3.1將下列線性規(guī)劃問題化為標準形式解將目標函數(shù)變?yōu)?，令，其中，在第一個約束不等式中加入松馳變量，在第二個約束不等式中減去剩余變量，則可得標準形式三、線性規(guī)劃的解的概念和基本定理考慮線性規(guī)劃標準形式的約束條件，其中為矩陣，，是維向量．假定增廣矩陣的秩=矩陣的秩，把矩陣的列進行可能的重新排列，使．這里B為矩陣，且有逆矩陣存在，即，稱B為該線性規(guī)劃問題的一個基．不失一般性，設(shè)，稱為基向量，與基向量對應(yīng)的變量稱為基變量，記為，其余的變量稱為非基變量，記為．令個非基變量均為0，并用高斯消元法，可得一個解，稱為該約束方程組的基解，其中．滿足非負約束條件（基解的非零分量都）的基解稱為基可行解．對應(yīng)于基可行解的基稱為可行基．基可行解的非零分量個數(shù)小于時，稱為退化解．線性規(guī)劃的解的基本定理：引理3.1線性規(guī)劃問題的可行解為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的．證必要性由基可行解的定義可知．下證充分性若向量組線性無關(guān)，則必有；當時，它們恰構(gòu)成一個基，從而為相應(yīng)的基可行解．當時，則一定可以從其余的列向量中取出個與構(gòu)成最大的線性無關(guān)向量組，其對應(yīng)的解恰為，所以它是基可行解．定理3.1線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點．證不失一般性，假設(shè)基可行解X的前個分量為正，故． （3.1）現(xiàn)在分兩步來討論，分別用反證法．（1）若X不是基可行解，則它一定不是可行域D的頂點．根據(jù)引理3.1，若X不是基可行解，則其正分量所對應(yīng)的系數(shù)列向量線性相關(guān)，即存在一組不全為零的數(shù)，使得 （3.2）用一個的數(shù)乘式（3.2），再分別與式（3.1）相加和相減，得到，．現(xiàn)取，，由可得，即是連線的中點．另一方面，當充分小時，可保證，即是可行解，這證明了不是可行域的頂點．（2）若不是可行域的頂點，則它一定不是基可行解．因為不是可行域的頂點，故在可行域中可找到不同的兩點，，，使 ．設(shè)是基可行解，對應(yīng)向量組線性無關(guān)，當時，有，由于是可行域的兩點，應(yīng)滿足．將這兩式相減，即得．因，所以上式系數(shù)不全為零，故向量組線性相關(guān)，與假設(shè)矛盾，即X不是基可行解．定理3.2若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)．證設(shè)是可行域的頂點，若不是頂點，且目標函數(shù)在處達到最優(yōu)（標準形式是）．因不是頂點，所以它可以用D的頂點線性表示為．因此． （3.3）在所有的頂點中必然能找到某一個頂點，使是所有中最小者，并且將代替式（3.3）中的所有，得到，由此得到．根據(jù)假設(shè)，是最小值，所以只能有，即目標函數(shù)在頂點處也達到最小值．§3.2線性規(guī)劃迭代算法單純形法是求解線性規(guī)劃問題的迭代算法．一、單純形法的計算步驟單純形法的基本思路是：從可行域中某個基可行解（一個頂點）開始，轉(zhuǎn)換到另一個基可行解（頂點），直到目標函數(shù)達到最優(yōu)時，基可行解即為最優(yōu)解．單純形法的基本過程如圖3.1所示．是否最優(yōu)解或無有限最優(yōu)解是否最優(yōu)解或無有限最優(yōu)解解NY開始結(jié)束開始初始基可行解圖3.1為計算方便，通常借助于單純形表來計算，從初始單純形表3.1開始，每迭代一步構(gòu)造一個新單純形表．單純型表中列中填入基變量；列中填入基變量的價值系數(shù)；列中填入約束方程組右端的常數(shù)；列的數(shù)字是在確定換入變量后，按規(guī)則計算填入；最后一行稱為檢驗數(shù)行，對應(yīng)各非基變量的檢驗數(shù)是，（這里令）．表3.1…………c1x1b11…0a1,m+1…a1nc2x2b20…0a2,m+1…a2n┇┇┇┇…┇┇…┇┇cmxmbm0…0am,m+1…amnθm－f(x)0…0…單純形法的計算步驟：（1）找出初始可行基，確定初始基可行解，建立初始單純形表．（3）在中，若所有，則此問題無最優(yōu)解，停止計算．否則轉(zhuǎn)入下一步．（4）根據(jù)，確定為換入變量．按規(guī)則計算，可確定為換出變量，轉(zhuǎn)入下一步．（5）以為主元素進行迭代（用高斯消元法），把所對應(yīng)的列向量，單純形法的流程圖如圖3.2所示．初始可行基開始初始可行基開始以為主元素進行迭代得到最優(yōu)解得到最優(yōu)解YYNYNY所有所有?計算計算圖3.2若目標函數(shù)要求實現(xiàn)最大化，一方面可將最大化轉(zhuǎn)換為最小化，另一方面也可在上述計算步驟中將判定最優(yōu)解的改為，將換入變量的條件改為．二、初始可行基的確定若線性規(guī)劃問題是則從中一般能直接觀察到存在一個初始可行基．（2）對所有約束條件是“≤”形式的不等式，可以利用化標準形式的方法，在每個約束條件的左端加入一個松馳變量，經(jīng)過整理重新對及進行編號，可得下列方程組顯然得到一個單位矩陣B可作為初始可行基．（3）對所有約束條件是“≥”形式的不等式及等式約束情況，若不存在單位矩陣時，可采用人工變量，即對不等式約束減去一個非負的剩余變量后，再加入一個非負的人工變量；對等式約束再加入一個非負的人工變量，總可得到一個單位矩陣作為初始可行基．例3.2求解線性規(guī)劃問題解：將線性規(guī)劃問題化為標準形式作初始單純形表，按單純形法計算步驟進行迭代，結(jié)果如下（表3.2）．表3.2CBXBb－2－3000x1x2x3x4x50x381210040x41640010－0x5120[4]00130－2－30000x32[1]010－1/220x416400104－3x2301001/4－9－20003/4－2x121010－1/2－0x4800－41[2]4－3x2301001/412130020－1/4－2x141011/400x５400－21/21－3x22011/2－1/8014003/21/80表3.2最后一行的檢驗數(shù)均為正，這表示目標函數(shù)值已不可能再減小，于是得到最優(yōu)解，目標函數(shù)值．三、單純形法的有關(guān)說明對線性規(guī)劃問題 （3.5）若系數(shù)矩陣中不含單位矩陣，沒有明顯的基可行解時，常采用引入非負人工變量的方法來求初始基可行解．下面分別介紹常用的“大M法”和“兩階段法”．（一）大M法在約束條件式（3.5）中加入人工變量，人工變量在目標函數(shù)中的價值系數(shù)為M，M為一個很大的正數(shù)．在迭代過程中，將人工變量從基變量中逐個換出，如果在最終表中當所有檢驗數(shù)時，基變量中不再含有非零的人工變量，這表示原問題有解，否則無可行解．例3.3求解線性規(guī)劃問題解：將原問題化為標準形式并引入人工變量，得用單純形法計算，得表3.3．根據(jù)表3.3的最后一行的檢驗數(shù)均，得最優(yōu)解，最優(yōu)值，由于人工變量的值均為零，故得原問題的最優(yōu)解，最優(yōu)值為．表3.3CBXBb－31100MMx1x2x3x4x5x6x70x4111－21100011Mx63－4120－1103/2Mx71－20[1]00011－4M－3+6M1－M1－30M000x4103－20100－1－Mx610[1]00－11－211x31－2010001－－M－1－11－M00M000x412[3]001－22－541x210100－11－2－1x31－2010001－－2－10001M－1M+1－3x141001/3－2/32/3－5/31x210100－11－2/31x390012/3－4/34/3－7/320001/31/3M－1/3M－2/3（二）兩階段法兩階段法是把線性規(guī)劃問題的求解過程分為兩個階段：第一階段，給原問題加入人工變量，構(gòu)造僅含價值系數(shù)為1的人工變量的目標函數(shù)且要求實現(xiàn)最小化，其約束條件與原問題相同，即然后用單純形法求解上述問題，若得到，這說明原問題存在基可行解，可進入第二階段計算，否則原問題無可行解，停止計算．第二階段，將第一階段計算得到的最終表，除去人工變量，將目標函數(shù)行的系數(shù)換為原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始單純形表進行計算．例3.4用兩階段法求解線性規(guī)劃問題解第一階段，標準化并引入人工變量，得如下的線性規(guī)劃，用單純形法計算該線性規(guī)劃（見表3.4），．表3.4CBXBb0000011x1x2x3x4x5x6x70x4111－211000111x63－4120－1103/21x71－20[1]00011－46－1－301000x4103－20100－1－1x610[1]00－11－210x31－2010001－－10－1001030x412[3]001－22－540x210100－11－2－0x31－2010001－00000011由于人工變量，所以得原問題的基可行解為．于是進入第二階段計算（見表3.5），最優(yōu)解為，最優(yōu)值，于是原問題的最優(yōu)解為，最優(yōu)值為．表3.5CBXBb－31100x1x2x3x4x50x412[3]001－241x210100－1－1x31－20100－－2－10001－3x141001/3－2/31x210100－11x390012/3－4/320001/31/3§3.3對偶問題的基本原理一、對偶問題的提出對偶性是線性規(guī)劃的重要內(nèi)容之一，每一個線性規(guī)劃問題必然有與之相伴而生的另一個線性規(guī)劃問題，我們稱一個叫原問題，另一個叫對偶問題，這兩個問題有著非常密切的關(guān)系，讓我們先分析一個實際的線性規(guī)劃模型與其對偶線性規(guī)劃問題的經(jīng)濟意義．表3.6產(chǎn)品設(shè)備總工時限制/h甲/h21370乙/h42280丙/h30115丁/h22050單位利潤/千元8102解設(shè)分別為產(chǎn)品的產(chǎn)量，構(gòu)造此問題的線性規(guī)劃模型為現(xiàn)在從另一個角度來討論該問題．假設(shè)工廠考慮不安排生產(chǎn)，而準備將所有設(shè)備出租，收取租費．于是，需要為每種設(shè)備的臺時進行估價．設(shè)分別表示甲、乙、丙、丁4種設(shè)備的臺時估價．由表3.6可知，生產(chǎn)一件產(chǎn)品需用各設(shè)備臺時分別為，如果將不用于生產(chǎn)產(chǎn)品，而是用于出租，那么將得到租費．當然，工廠為了不至于蝕本，在為設(shè)備定價時，保證用于生產(chǎn)產(chǎn)品的各設(shè)備臺時得到的租費，不能低于產(chǎn)品的單位利潤8千元，即．按照同樣分析，用于生產(chǎn)一件產(chǎn)品的各設(shè)備臺時，，，所得的租費，不能低于產(chǎn)品的單位利潤10千元，即．同理，還有．另外，價格顯然不能為負值，所以．企業(yè)現(xiàn)在設(shè)備的總以時數(shù)為70h，80h，15h，50h，如果將這些臺時都用于出租，企業(yè)的總收入為．企業(yè)為了能夠得到租用設(shè)備的用戶，使出租設(shè)備的計劃成交，在價格滿足上述約束的條件下，應(yīng)將設(shè)備價值定得盡可能低，因此取的最小值，綜合上述分析，可得到一個與例3.5相對應(yīng)的線性規(guī)劃，即稱后一個規(guī)劃問題為前一個規(guī)劃問題的對偶問題，反之，也稱前一個規(guī)劃問題是后一個規(guī)劃問題的對偶問題．二、原問題與對偶問題的表達形式和關(guān)系在線性規(guī)劃的對偶理論中，把如下線性規(guī)劃形式稱為原問題的標準形式而把如下線性規(guī)劃形式稱為對偶問題的標準形式若用矩陣形式表示，則原問題和對偶問題分別可寫成如下形式：原問題 （3.6）對偶問題 （3.7）原問題與對偶問題的關(guān)系見表3.7．表3.7原問題（對偶問題）對偶問題（原問題）minmax目標函數(shù)系數(shù)右邊常數(shù)約束條件系數(shù)矩陣右邊常數(shù)目標函數(shù)系數(shù)系數(shù)矩陣的轉(zhuǎn)置第個約束條件為“≥”型第個約束條件為“=”型第個約束條件為“≤”型第個變量≥0第個變量無限制第個變量≤0第個變量≥0第個變量無限制第個變量≤0第個約束條件為“≤”型第個約束條件為“=”型第個約束條件為“≥”型例3.6求下面線性規(guī)劃問題的對偶問題解：根據(jù)表3.7可直接寫出上述問題的對偶問題三、對偶理論定理3.3（弱對偶定理）對偶問題（max）的任何可行解，其目標函數(shù)值總是不大于原問題（min）任何可行解的目標函數(shù)值．證由定理所設(shè)及問題（3.6）和問題（3.7）容易看出．定理3.4（對偶定理）假如原問題或?qū)ε紗栴}之一具有有限的最優(yōu)解，則另一問題也具有有限的最優(yōu)解，且兩者相應(yīng)的目標函數(shù)值相等．假如一個問題的目標函數(shù)值是無界的，則另一問題沒有可行解．證明從略．定理3.5（互補松馳定理）假如和分別是原問題（3.6）和對偶問題（3.7）的可行解，是原問題剩余變量的值，是對偶問題松馳變量的值，則、分別是原問題和對偶問題最優(yōu)解的充要條件是．證由定理所設(shè)，可知有 （3.8） （3.9）分別以左乘式（3.8），以右乘式（3.9），兩式相減，得．若，根據(jù)弱對偶定理知．這說明，分別是原問題和對偶問題最優(yōu)解，反之亦然．根據(jù)互補松馳定理和決策變量滿足非負條件可知，在最優(yōu)解時，和同時等于0，所以有，．于是，互補松馳定理也可以這樣敘述：最優(yōu)化時，假如一個問題的某個變量取正數(shù)，則相應(yīng)的另一個問題的約束條件必取等式；或者一個問題中的約束條件不取等式，則相應(yīng)于另一問題中的變量必為零．例3.7已知線性規(guī)劃問題已知其對偶問題的最優(yōu)解為，試用對偶理論找出原問題的最優(yōu)解．解：先寫出它的對偶問題將的值代入約束條件，得（2），（3），（4）為嚴格不等式，由互補松馳定理得，因，原問題的兩個約束條件應(yīng)取等式，故有，．求解后得到，故原問題的最優(yōu)解為．四、對偶問題的迭代算法對偶單純形法是對偶問題的迭代算法，其基本思想是：從原問題的一個基本解出發(fā)，此基本解不一定是可行解，但它對應(yīng)著對偶問題的一個可行解；然后檢驗原問題的基本解是否可行，即是否有負的分量．如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解．如果得到的基本解的分量皆非負，則該基本解為最優(yōu)解．也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行解，使原問題的基本解由不可行逐步變?yōu)榭尚校斖瑫r得到對偶問題與原問題的可行解時，便得到原問題的最優(yōu)解．對線性規(guī)劃問題的標準形式對偶單純形法的計算步驟如下：(1)找出原問題的一個基，構(gòu)成初始對偶基可行解，使所有檢驗數(shù)，構(gòu)成初始對偶單純形表．(2)若所有，則當前的解是最優(yōu)解，停止計算，否則計算，則行為主行，該行對應(yīng)的基變量為換出變量．(3)若所有，則對偶問題無界，原問題無解，停止計算，否則計算，則列為主列，該列對應(yīng)的基變量為換入變量．(4)以為主元素進行迭代，然后轉(zhuǎn)回步驟(2)．對偶單純形法的流程圖如圖3.3所示．例3.8用對偶單純形法求解下述線性規(guī)劃問題建立初始單純形表，見表3.8．原問題的基本解的檢驗數(shù)開始原問題的基本解的檢驗數(shù)開始以為主元素進行迭代得到最優(yōu)解得到最優(yōu)解YYNYNY所有所有?計算計算圖3.3表3.8CBXBb23400x1x2x3x4x50x4－3－1－2－1100x5－4[－2]1－30123400從表3.8看出，所有檢驗數(shù)，則對應(yīng)對偶問題的解是可行的，因列數(shù)字為負，需進行迭代，計算．所以為換出變量．又因為，所以為換入變量，以換入、換出變量所在行列交叉處元素“－2”為主元素，按單純形法計算步驟進行迭代，得表3.9．表3.9CBXBb23400x1x2x3x4x50x4－10[－5/2]1/21－1/22x121－1/23/20－1/2041013x22/501－1/5－2/51/52x111/5107/5－1/5－2/5003/58/51/5由表3.9的最后一行看出，所有檢驗數(shù)，故原問題的最優(yōu)解為．若對應(yīng)兩個約束條件對偶變量為，，則可得對偶問題的最優(yōu)解為．§3.4線性規(guī)劃問題靈敏度在建立實際的線性規(guī)劃模型時，所收集到的數(shù)據(jù)不是很精確；另一方面在實際應(yīng)用中，各種信息瞬息萬變，已形成的數(shù)學模型中的某些數(shù)據(jù)需要隨之而變．因此，對于一個線性規(guī)劃問題，研究當數(shù)據(jù)發(fā)生變動時解的變化情況是很重要的．下面僅介紹兩種數(shù)據(jù)變化而導(dǎo)致解的變化的情況，這就是靈敏度分析問題．一、價值系數(shù)的變化假設(shè)只有一個系數(shù)變化，其它系數(shù)保持不變，的變化只影響檢驗解而不影響解的非負定性，下面分別就是非基變量系數(shù)和基變量系數(shù)兩種情況進行討論．（1）是非基變量的系數(shù)由于不變，因而對任何都不變．這時非基變量的系數(shù)的變化只影響與有關(guān)的一個檢驗數(shù)的變化，而對其它沒有影響，設(shè)系數(shù)從變化到，這時檢驗數(shù)被所代替，在當前解是原問題的最優(yōu)解時，有，假如，則必須引進基，單純形法繼續(xù)進行，否則原解仍是變化后的新問題的最優(yōu)解，最優(yōu)解不變相當于變化的界限為．（2）為基變量的系數(shù)當被所代替時，變成，可計算為． （3.10）特別是當時，，且，因此，仍為零．由式（3.10）知，基變量的價值系數(shù)的變化會引起整個價值系數(shù)行的變化，變化值為乘以最終表相應(yīng)該基變量所在的行的數(shù)值．列本身則調(diào)整為．由式（3.10）可看出，當對某個非基變量，式（3.10）為負時會引起基的變化，若要保持最優(yōu)解不變，分析變化值且大于或小于零以及值是正或負的情況，得出會保持最優(yōu)解不變的的變化界限為．例3.8以例3.2的最終表為例，設(shè)基變量的系數(shù)變化，在原最優(yōu)解不變條件下，確定的變化范圍．解此時例3.2的最終表便成為表3.10表3.10CBXBb－2－3+000x1x2x3x4x5－2x141001/400x5400－21/21－3x22011/2－1/8003/21/80為了保持原最優(yōu)解不變，則的檢驗數(shù)應(yīng)當為零，進行行初等變換，得表3.11．表3.11CBXBb－2－3+000x1x2x3x4x5－2x141001/400x5400－21/21－3+x22011/2－1/80003/2－1/8+0從表（3.11）可得且．由此可得的變化范圍為，即的價值系數(shù)可以在[0，4]之間變化，而不影響原最優(yōu)解．二、資源系數(shù)的變化假設(shè)資源系數(shù)變化為，的變化將會影響解的可行性，但不會引起檢驗數(shù)的符號變化．根據(jù)基可行解的矩陣表示可知，，所以只要變化必定會導(dǎo)致最優(yōu)解的數(shù)值發(fā)生變化，最優(yōu)解的變化分為兩類：一類是保持，最優(yōu)基B不變；另一類是中出現(xiàn)負分量，這將使最優(yōu)基B變化，若最優(yōu)基不變，則只需將變化后的代入的表達式重新計算即可；若中出現(xiàn)負分量，則要通過迭代求解新的最優(yōu)基和最優(yōu)解．設(shè)系數(shù)變化到，而其它系數(shù)都不變，這樣使最終表中原問題的解相應(yīng)變化為，其中為原最優(yōu)解，為的第個分量，為的第行第列元素，為了保持最優(yōu)基不變，應(yīng)使，即．由此可得到保持最優(yōu)基不變時，資源系數(shù)的變化界限為．例3.9若例3.2的第二個約束條件中變化為，在最優(yōu)解不變的條件下，求的變化范圍．解計算可得所以的變化范圍是（－8，16）．顯然的變化范圍是（8，32）．第四章一維搜索法由第一章關(guān)于求解最優(yōu)化問題概述中我們知道，從已知迭代點出發(fā)按照基本迭代公式來求解最優(yōu)化問題，其關(guān)鍵在于如何構(gòu)造一個搜索方向和確定一個步長，使下一迭代點處的目標函數(shù)值下降，即．現(xiàn)在我們來討論，當搜索方向已經(jīng)確定的情況下，如何來確定步長？步長因子的選取有多種方法，