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

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