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

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