最優(yōu)化理論與方法1(2014-簡版)

1、最優(yōu)化理論與方法講義(上)第一章 緒論1.1 學(xué)科簡介最優(yōu)化這一數(shù)學(xué)分支，為這些問題的解決提供了理論基礎(chǔ)和求解方法。最優(yōu)化就是在一切可能的方案中選擇一個最好的方案以達到最優(yōu)目標(biāo)的學(xué)科。1.1.1 優(yōu)化的含義優(yōu)化是從處理各種事物的一切可能的方案中，尋求最優(yōu)的方案。（1）來源：優(yōu)化一語來自英文Optimization，其本意是尋優(yōu)的過程；（2）優(yōu)化過程：是尋找約束空間下給定函數(shù)取極大值（以max表示)或極小(以min表示)的過程。1.2 發(fā)展概況第一階段人類智能優(yōu)化第二階段數(shù)學(xué)規(guī)劃方法優(yōu)化第三階段工程優(yōu)化第四階段現(xiàn)代優(yōu)化方法1.3研究意義研究意義：最優(yōu)化在本質(zhì)上是一門交叉學(xué)科，它對許多學(xué)科產(chǎn)生了重

2、大影響，并已成為不同領(lǐng)域中很多工作都不可或缺的工具。應(yīng)用范圍：信息工程及設(shè)計、經(jīng)濟規(guī)劃、生產(chǎn)管理、交通運輸、國防工業(yè)以及科學(xué)研究等諸多領(lǐng)域?？傊?，它是一門應(yīng)用性相當(dāng)廣泛的學(xué)科，討論決策的問題具有最佳選擇之特性。它尋找最佳的計算方法，研究這些計算方法的理論性質(zhì)及其實際計算表現(xiàn)。1.4 示例例1 資源分配問題 某工廠生產(chǎn)A和B兩種產(chǎn)品，A產(chǎn)品單位價格為萬元，B產(chǎn)品單位價格為萬元。每生產(chǎn)一個單位A 產(chǎn)品需消耗煤噸，電度，人工個人日；每生產(chǎn)一個單位B 產(chǎn)品需消耗煤噸，電度，人工個人日?，F(xiàn)有可利用生產(chǎn)資源煤C 噸，電E 度，勞動力L個人日，欲找出其最優(yōu)分配方案，使產(chǎn)值最大。分析：(1)產(chǎn)值的表達式；(2

3、)優(yōu)化變量確定：A 產(chǎn)品，B 產(chǎn)品；(3)優(yōu)化約束條件：生產(chǎn)資源煤約束；生產(chǎn)資源電約束；生產(chǎn)資源勞動力約束。例2 指派問題設(shè)有四項任務(wù)、派四個人、去完成。每個人都可以承擔(dān)四項任務(wù)中的任何一項，但所消耗的資金不同。設(shè)完成所需資金為。如何分配任務(wù)，使總支出最少?分析：設(shè)變量則總支出可表示為：數(shù)學(xué)模型：1.5 最優(yōu)化的數(shù)學(xué)模型 最優(yōu)化的數(shù)學(xué)模型是描述實際優(yōu)化問題目標(biāo)函數(shù)、變量關(guān)系、有關(guān)約束條件和意圖的數(shù)學(xué)表達式，并能反映物理現(xiàn)象各主要因素的內(nèi)在聯(lián)系，是進行最優(yōu)化的基礎(chǔ)。1.5.1 基本概念1、決策變量(Decision variables)問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可

4、由決策者決定和控制，也稱優(yōu)化變量。決策變量或優(yōu)化變量的全體實際上是一組變量，可用一個列向量表示。優(yōu)化變量的數(shù)目稱為優(yōu)化問題的維數(shù)，如n個優(yōu)化變量，則稱為n維優(yōu)化問題。優(yōu)化問題的維數(shù)表征優(yōu)化的自由度。優(yōu)化變量愈多，則問題的自由度愈大、可供選擇的方案愈多，但難度亦愈大、求解亦愈復(fù)雜。 通常，小型優(yōu)化問題：一般含有210個優(yōu)化變量； 中型優(yōu)化問題：1050個優(yōu)化變量； 大型優(yōu)化問題：50個以上的優(yōu)化變量。如何選定優(yōu)化變量？確定優(yōu)化變量時應(yīng)注意以下幾點：（1）抓主要，舍次要。 （2）根據(jù)要解決問題的特殊性來選擇優(yōu)化變量。2、約束條件(Constraint conditions)指決策變量取值時受到的各

5、種資源條件的限制。約束又可按其數(shù)學(xué)表達形式分成等式約束和不等式約束兩種類型：(1)等式約束：(2)不等式約束：根據(jù)約束的性質(zhì)可以把它們區(qū)分成：性能約束針對性能要求而提出的限制條件稱作性能約束。邊界約束只是對設(shè)計變量的取值范圍加以限制的約束稱作邊界約束。圖1-2 優(yōu)化問題中的約束面(或約束線)(a)、二變量問題的約束線 (b)三變量問題的約束面可行域：在優(yōu)化問題中，滿足所有約束條件的點所構(gòu)成的集合。 如約束條件和的二維設(shè)計問題的可行域D。圖 約束條件規(guī)定的可行域D一般情況下，可行域可表示為：不可行域：可行點和不可行點：約束邊界上的可行點為邊界點，其余可行點為內(nèi)點。起作用的約束與不起作用的約束：滿

6、足的約束為起作用約束,否則為不起作用的約束。(等式約束一定是起作用約束)3、目標(biāo)函數(shù)(Objective function)它是決策變量的函數(shù)。為了對優(yōu)化進行定量評價，必須構(gòu)造包含優(yōu)化變量的評價函數(shù)，它是優(yōu)化的目標(biāo)，稱為目標(biāo)函數(shù)，以表示。 在優(yōu)化過程中，通過優(yōu)化變量的不斷向值改善的方向自動調(diào)整，最后求得值最好或最滿意的X值。在構(gòu)造目標(biāo)函數(shù)時，目標(biāo)函數(shù)的最優(yōu)值可能是最大值，也可能是最小值。在優(yōu)化問題中，可以只有一個目標(biāo)函數(shù)，稱為單目標(biāo)函數(shù)。當(dāng)在同一設(shè)計中要提出多個目標(biāo)函數(shù)時，這種問題稱為多目標(biāo)函數(shù)的最優(yōu)化問題。3.1 目標(biāo)函數(shù)等值(線)面n 定義：在高維空間中，使目標(biāo)函數(shù)值取同一常數(shù)的點集，稱為

7、的等值線（或等值面）。 （或定義：對于具有相等目標(biāo)函數(shù)值的自變量構(gòu)成的平面曲線或曲面稱為等值線或等值面。）n 數(shù)學(xué)表達式為一系列常數(shù)，代表一族維超曲面。對于具有相等目標(biāo)函數(shù)值的自變量構(gòu)成的平面曲線或曲面稱為等值線或等值面。n 性質(zhì)在通常情況下，若目標(biāo)函數(shù)是連續(xù)的單值函數(shù)，則其等值線具有以下性質(zhì)：(1) 不同值的等值線不相交；(2) 除極值點所在的等值線外，等值線不會中斷；(3) 等值線稠密的地方，目標(biāo)函數(shù)值變化較快，而稀疏的地方，目標(biāo)函數(shù)值變化較慢；(4) 在極值點附近，等值線近似地呈現(xiàn)為同心橢球面族(橢圓族)。4、可行域(Feasible region)滿足約束條件的決策變量的取值范圍。5、

8、最優(yōu)解(Optimal solution)可行域中使目標(biāo)函數(shù)達到最優(yōu)的決策變量的值。1.5.4 優(yōu)化問題一般數(shù)學(xué)形式設(shè)優(yōu)化變量向量 求目標(biāo)函數(shù) 滿足約束條件 ： 即 s.t. 1.5.5 建模實例建立優(yōu)化問題的數(shù)學(xué)模型一般步驟：(1)根據(jù)問題要求，應(yīng)用專業(yè)范圍內(nèi)的現(xiàn)行理論和經(jīng)驗等，對優(yōu)化對象進行分析。(2)對諸參數(shù)進行分析，以確定問題的原始參數(shù)、優(yōu)化常數(shù)和優(yōu)化變量。(3)根據(jù)問題要求，確定并構(gòu)造目標(biāo)函數(shù)和相應(yīng)的約束條件，有時要構(gòu)造多目標(biāo)函數(shù)。(4)必要時對數(shù)學(xué)模型進行規(guī)范化，以消除諸組成項間由于量綱不同等原因?qū)е碌臄?shù)量懸殊的影響。例 混合飼料配合以最低成本確定滿足動物所需營養(yǎng)的最優(yōu)混合飼料。設(shè)

9、每天需要混合飼料的批量為100磅，這份飼料必須含：至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)成分為：解：設(shè)是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉的量(磅)。1.5.6 優(yōu)化設(shè)計的分類1.6 優(yōu)化問題的幾何解釋和基本解法1.6.1 幾何解釋無約束優(yōu)化問題就是在沒有限制的條件下，對優(yōu)化變量求目標(biāo)函數(shù)的極小點。在優(yōu)化空間內(nèi)，目標(biāo)函數(shù)是以等值面的形式反映出來的，則無約束優(yōu)化問題的極小點即為等值面的中心。約束優(yōu)化問題是在可行域內(nèi)對設(shè)計變量求目標(biāo)函數(shù)的極小點，此極小點在可行域內(nèi)或在可行域邊界上。求目標(biāo)函數(shù)在可行

10、域D上的極小點，是在與可行域D有交集的等值線中找出具有最小值的等值線。例1：二維非線性規(guī)劃問題目標(biāo)函數(shù)等值線是以點(2，0)為圓心的一組同心圓。如不考慮約束，其無約束最優(yōu)解是： 約束方程所圍成的可行域是D，此時例2：非線性規(guī)劃問題：由圖易見約束直線與等值線的切點就是最優(yōu)點，利用解析幾何的方法得到該切點和最優(yōu)值為：例3：非線性規(guī)劃問題：解：畫出等式約束曲線的圖形。這是一條拋物線；畫出不等式約束區(qū)域：和；畫出目標(biāo)函數(shù)等值線，以及等值線與可行集的切點?？梢娍尚杏驗榍€段ABCD。點是使目標(biāo)函數(shù)值最小的可行點，其坐標(biāo)可通過解方程組：得出： 1.6.2 優(yōu)化問題的基本解法求解優(yōu)化問題的基本解法有：解析法

11、和數(shù)值解法。1.6.2.1 解析法利用數(shù)學(xué)分析(微分、變分等）的方法，根據(jù)函數(shù)（泛函）極值的必要條件和充分條件求出其最優(yōu)解析解的求解方法。局限性：工程優(yōu)化問題的目標(biāo)函數(shù)和約束條件往往比較復(fù)雜，有時甚至還無法用數(shù)學(xué)方程描述，在這種情況下應(yīng)用數(shù)學(xué)分析方法就會帶來麻煩。1.6.2.2 數(shù)值解法這是一種數(shù)值近似計算方法，又稱為數(shù)值迭代方法。它是根據(jù)目標(biāo)函數(shù)的變化規(guī)律，以適當(dāng)?shù)牟介L沿著能使目標(biāo)函數(shù)值下降的方向，逐步向目標(biāo)函數(shù)值的最優(yōu)點進行探索，逐步逼近到目標(biāo)函數(shù)的最優(yōu)點或直至達到最優(yōu)點。數(shù)值解法（迭代法）是優(yōu)化設(shè)計問題的基本解法。其中也可能用到解析法，如最速下降方向的選取、最優(yōu)步長的確定等。數(shù)值計算的迭

12、代方法具有以下特點：(1)是數(shù)值計算而不是數(shù)學(xué)分析方法；(2)具有簡單的邏輯結(jié)構(gòu)并能反復(fù)進行同樣的數(shù)值計算；(3)最后得出的是逼近精確解的近似解。這些特點正與計算機的工作特點相一致。在數(shù)學(xué)規(guī)劃中，采用進行迭代運算時，求n維函數(shù)的極值點的具體算法如下圖所示。一、求解步驟：數(shù)值迭代法的基本思路：是進行反復(fù)的數(shù)值計算，尋求目標(biāo)函數(shù)值不斷下降的可行計算點，直到最后獲得足夠精度的最優(yōu)點。這種方法的求優(yōu)過程大致可歸納為以下步驟：(1)首先初選一個盡可能靠近最小點的初始點，從出發(fā)按照一定的原則尋找可行方向和初始步長，向前跨出一步達到點；(2)得到新點后再選擇一個新的使函數(shù)值迅速下降的方向及適當(dāng)?shù)牟介L，從點出

13、發(fā)再跨出一步，達到點，并依此類推，一步一步地向前探索并重復(fù)數(shù)值計算，最終達到目標(biāo)函數(shù)的最優(yōu)點。在中間過程中每一步的迭代形式為：上式中：第k步迭代計算所得到的點，稱第k步迭代點，亦為第k步設(shè)計方案；第k步迭代計算的步長； 圖 迭代計算機逐步逼近最優(yōu)點過程示意圖第k步迭代計算的探索方向。 用迭代法逐步逼近最優(yōu)點的探索過程如右圖所示。 u 運用迭代法，每次迭代所得新的點的目標(biāo)函數(shù)都應(yīng)滿足函數(shù)值下降的要求：u 迭代法要解決的問題：即(1)選擇搜索方向；(2)確定步長因子；(3)給定收斂準(zhǔn)則。(一) 柯西收斂準(zhǔn)則點列收斂的充要條件是：對于任意指定的實數(shù)，都存在一個只與有關(guān)而與無關(guān)的自然數(shù)N，使得當(dāng)兩自然

14、數(shù)m，p > N時，滿足或 或 (二) 迭代終止準(zhǔn)則（1）點距準(zhǔn)則 或 其中是事先給定的要求精度。（2）函數(shù)值下降量準(zhǔn)則 或 （3）目標(biāo)函數(shù)梯度準(zhǔn)則至于采用哪種收斂準(zhǔn)則，可視具體問題而定?？梢匀。旱诙?線性規(guī)劃2.1 線性規(guī)劃問題及其數(shù)學(xué)模型2.1.1 問題的提出例1：（下料問題）某車間有長度為180cm的鋼管（數(shù)量足夠多），今要將其截為三種不同長度的管料，長度分別為70cm、52cm和35cm。生產(chǎn)任務(wù)規(guī)定，70cm的管料只需100根，而52cm、35cm的管料分別不少于150根、120根，問應(yīng)采取怎樣的截法才能完成任務(wù)，同時使剩下的余料最少？解：所用可能的截法共有8種，見下表：截法

15、一二三四五六七八需要量/根長度(cm)705235211100001000210321015010130235120余料長度(cm)56235246235上述下料問題的數(shù)學(xué)模型為： s.t. 2.1.2 基本特點l 線性規(guī)劃問題的共同特征：l 一組決策變量表示一個方案，一般大于等于零。l 約束條件是線性等式或不等式。l 目標(biāo)函數(shù)是線性的，且求目標(biāo)函數(shù)最大化或最小化。l 線性規(guī)劃模型的一般形式：l 線性規(guī)劃問題的標(biāo)準(zhǔn)形式(1)標(biāo)準(zhǔn)形式為目標(biāo)函數(shù)最小、約束條件等式、決策變量非負。(2)簡寫形式(3) 向量形式s.t. 其中，(4) 矩陣形式其中 目標(biāo)函數(shù)最小；約束條件等式；決策變量非負。l 一般線

16、性規(guī)劃問題的標(biāo)準(zhǔn)化 等價于 “£” 約束：加入非負松馳變量例1：目標(biāo)函數(shù) 約束條件 改為 “³” 約束： 減去非負剩余變量，即可正可負（即無約束）。例2： 其中2.2 線性規(guī)劃的圖解法2.2.1 圖解法如上述例1的數(shù)學(xué)模型目標(biāo)函數(shù) 約束條件 2.2.2 圖解法求解步驟l 由全部約束條件作圖求出可行域；l 作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動方向；l 平移目標(biāo)函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。2.2.3 線性規(guī)劃問題求解的幾種可能結(jié)果(A) 唯一最優(yōu)解； (B) 無窮多最優(yōu)解；(A) (B)(C) 無界解；(D) 無可行解。 其可行域為空集2.2.4 由圖解法得到的

17、啟示l 可行域是有界或無界的凸多邊形。l 若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。l 若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。l 解題思路：找出凸集的頂點，計算其目標(biāo)函數(shù)值，比較即得。2.3 線性規(guī)劃解的性質(zhì)2.3.1 線性規(guī)劃解的概念u 標(biāo)準(zhǔn)型其中，設(shè)，即約束方程組中沒有多余的方程，則應(yīng)有。如果用表示矩陣的第列，則也可記為。u 基：若可逆，則稱為線性規(guī)劃式的基。稱為基向量。有時也稱向量組為的基，而將稱為基矩陣（或稱基陣）基(描述二)：若是矩陣中m×m階非奇異子矩陣（|B|0，即可逆），則是線性規(guī)劃問題的一個基矩陣（或稱基陣）。不妨設(shè)：其中 求解 ，則

18、基變量，令可求出：特別地，若，則，相應(yīng)地將分解為。這樣變?yōu)榱?則 若令,則是上述標(biāo)準(zhǔn)型線性規(guī)劃問題的一個基本解。u 基本解：對于基，令非基變量為零，求得滿足的解，稱為對應(yīng)的基本解（或稱基解）。u 基本可行解：非負的基本解稱為基本可行解。u 可行基：對應(yīng)基本可行解的基稱為 可行基。u 最優(yōu)解：使達到最小值的可行解稱為最優(yōu)解。u 線性規(guī)劃解的關(guān)系圖由于A是矩陣，故線性規(guī)劃問題的不同的基最多有個。而一個基最多對應(yīng)一個基本可行解，故此線性規(guī)劃問題最多有個基本可行解。上述分析可知，基本可行解中非零分量的個數(shù)不會超過，若基本可行解中非零分量的個數(shù)恰為，稱此基本可行解為非退化的基本可行解，否則稱為退化的基本

19、可行解。若一個線性規(guī)劃的所有基本可行解都是非退化的，稱此線性規(guī)劃是非退化的。例：求基陣、基本可行解。，A的秩是3。根據(jù)定義 是一個基陣，它對應(yīng)的基本解為顯然它是基本可行解。另根據(jù)定義 也是一個基陣，它對應(yīng)的基本解為 它不是基本可行解。2.3.2 線性規(guī)劃問題的幾何意義2.3.2.1 基本概念一、凸集設(shè)是n維歐式空間的一點集，對，連線上的一切點，則為凸集。二、頂點若是凸集，；若不能用不同的兩點，的線性組合表示為：，則為頂點。三、凸組合設(shè)是維向量空間中的個點，若存在，且，使則為的凸組合。2.3.2.2 基本定理定理1：若線性規(guī)劃問題存在可行域，則其可行域：是凸集。證明：設(shè)，則有，令為和連線上的任意

20、一點，則： （只要驗證X在D中即可!）顯然，將代入約束條件，有引理1：可行解為基本可行解 的正分量(非零分量)在A中所對應(yīng)的列向量線性無關(guān)。定理2：線性規(guī)劃問題的基本可行解對應(yīng)于可行域D的頂點。定理3：若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。2.3.2.3 幾點結(jié)論Ø 線性規(guī)劃問題的可行域是凸集。Ø 基本可行解與可行域的頂點一一對應(yīng)。Ø 若線性規(guī)劃有最優(yōu)解，則必在其可行域的頂點處取得。2.4 單純形法2.4.1 單純形法的思路基本思路：從線性規(guī)劃可行域的某一個頂點出發(fā)，沿著使目標(biāo)函數(shù)下降的方向?qū)で笙乱粋€頂點，而頂點個數(shù)是有限的。所以

21、，只有這個線性規(guī)劃有最優(yōu)解，那么通過有限步迭代之后，必可求出最優(yōu)解。或表述為：從線性規(guī)劃可行域出發(fā)，找出一基本可行解(極點)，若其不是最優(yōu)，找到一個相鄰極點新的目標(biāo)函數(shù)值不大于原目標(biāo)函數(shù)值，經(jīng)過有限次迭代給出最優(yōu)解或判斷無最優(yōu)解。2.4.2 準(zhǔn)備工作為了用迭代法求出線性規(guī)劃的最優(yōu)解，有以下幾個問題需要首先解決：(1)最優(yōu)解判別準(zhǔn)則。即迭代到什么時候，可以認(rèn)為最優(yōu)解已經(jīng)得到，迭代可以終止了。(2)換基運算。即從一個基本可行解迭代出另一個基本可行解的方法。(3)進基列的選擇。即進行什么樣的換基運算，可以使目標(biāo)函數(shù)值有較大下降。1、最優(yōu)解判別準(zhǔn)則考慮標(biāo)準(zhǔn)形式的線性規(guī)劃如果已知一個可行基B是一個m階單

22、位矩陣，不妨設(shè)B剛好位于矩陣A的前m列。這是，約束方程的形式為：其中，。此時，與B相對應(yīng)的基本可行解是。設(shè)，為單位矩陣，則有于是，線性規(guī)劃問題可記為顯然，是此線性規(guī)劃的一個基本可行解。所對應(yīng)的目標(biāo)函數(shù)值為由可得，則 由于，故當(dāng)時，即此時是線性規(guī)劃的最優(yōu)值。定理1(最優(yōu)解判別準(zhǔn)則)：對于上述線性規(guī)劃問題，當(dāng)時，此線性規(guī)劃的最優(yōu)解。用分量的形式來表示，令則當(dāng)時，是其最優(yōu)解。又當(dāng)時，若令則因，1是第個分量，所以因此稱為或的判別數(shù)，由以上討論可知，基向量或基變量的判別數(shù)必定為零。可見，定理1又可敘述為：定理I：若線性規(guī)劃各判別數(shù)，則基本可行解就是這個線性規(guī)劃的最優(yōu)解。舉例：判斷是否為下面線性規(guī)劃的最優(yōu)

23、解。解： ，取為基，即為基變量，則是與對應(yīng)的基本可行解。又 ，。則判別數(shù)為可見， 因此，是其最優(yōu)解。定理2：若線性規(guī)劃的某個判別數(shù)，而相應(yīng)的列向量，則這個線性規(guī)劃無最優(yōu)解。證明（略，詳見傅英定等主編最優(yōu)化理論與方法P53）以上的討論，均是假定約束方程的系數(shù)矩陣A中有一個單位矩陣I。如果A中沒有單位矩陣，或者所取的基B并不是一個單位矩陣，那么，這是定理1與定理2的結(jié)論是否還成立呢？對于上述線性規(guī)劃，設(shè)，可逆，取為基。則 (*)由可逆，則可得 于是 若，則是一個基本可行解。如果進一步， 或 ，對式(*) 的任一可行解，必有故 為式(*)的最優(yōu)解。綜上，可將非正作為式(*)的最優(yōu)解的判別條件。又由于

24、 所以，與是完全等價的。令 (*)仍稱為或的判別數(shù)。顯然，前面定義的判別數(shù)是式(*)中B=I時的一種特殊情形。2、換基運算所謂換基運算就是從一個基本可行解迭代出一個新的基本可行解的方法。由于只考慮基本可行解之間的迭代問題，暫不涉及目標(biāo)函數(shù)，這里先考慮以下這一組特殊的約束。用矩陣表示，即，于是 是一個基本可行解。 現(xiàn)在從出發(fā)，尋找新的基本可行解。對于矩陣用表示矩陣A的第列，則有其中是一個基。 若，則可用矩陣的初等變換(不換行)將第列變?yōu)槌跏紗挝幌蛄?，即。此時，變?yōu)榉浅跏紗挝幌蛄浚c此同時，矩陣變?yōu)槠渲?()于是得到新基以上的運算稱為換基運算。稱為主元，稱為進基列，稱為出基列，稱為進基變量，稱為出

25、基變量。然而，在換基運算中應(yīng)選取什么樣的元作為主元呢？令 其中是第個分量。又由于 則可得到若，則就是一個基本可行解。而就是。于是，由可知，必有。又當(dāng)時，由式()中第4式可得 因此，當(dāng)時，為使，應(yīng)有故當(dāng)符合條件 ()此時，可取為主元對進行換基運算，得到新基：及新的基本可行解：換基運算的步驟：(1)在進基列中按式()選取主元；(2)按式()計算、，得到上述所示的新的基本可行解。舉例：給定約束條件顯然，是一個初始基本可行解。如果要將引入基中則主元應(yīng)滿足于是中的元就是主元。按照式()作換基運算，得到新的基本可行解是 同理可將引入基中，則主元應(yīng)滿足則為主元。以為主元對按照式()作換基運算，得到新的基本可

26、行解為 應(yīng)當(dāng)注意：并不是A的任何一列都可以引入基中。如上例中就不能入基，因為導(dǎo)致，即無論在中取哪一個為主元，均不能保證，故在確定進基列的時候，應(yīng)保證該列至少有一個正分量。3、進基列的選擇以上換基運算分析可知，對進基列的要求是至少有一個正分量。然而滿足這個條件的列向量可能很多。那么，挑選哪一個作為進基列更好呢？這需要與目標(biāo)函數(shù)聯(lián)系起來。如果在上例的約束條件上加上一個目標(biāo)函數(shù)：于是 則在、和處相應(yīng)的目標(biāo)函數(shù)值為 同相比，處目標(biāo)函數(shù)值上升，處目標(biāo)函數(shù)值下降，則此時應(yīng)該選取作進基列。然而，對于一般的線性規(guī)劃來說，選擇什么樣的列作進基列可以使目標(biāo)函數(shù)值下降呢？定理3：設(shè)線性規(guī)劃滿足以下條件： (1) 基

27、本可行解非退化；(2) 的判斷數(shù)；(3) 的分量中至少有一個為正。則用作進基列將得到使目標(biāo)函數(shù)值下降的基本可行解。定理3的證明詳見傅英定等主編最優(yōu)化理論與方法P60-P61）。 但一般的線性規(guī)劃符合進基列條件的列通常不止一個，那么，選取哪一列作進基列最好呢？由于 所以，當(dāng)最大時，目標(biāo)函數(shù)值下降最快?？梢娕c進基列的選擇有關(guān)。如果對每一個可供選擇的進基列都計算一次，再比較各個的大小，則當(dāng)可供選擇的進基列數(shù)目較大時，相應(yīng)的計算量也較大。所以，通常情況下，若有多個列滿足進基列的條件，則選取判別數(shù)最大的那一列作進基列，這時目標(biāo)函數(shù)值獲得較大的下降。舉例：對于線性規(guī)劃取為基，則由于、均有正分量，故、都可作

28、進基列但，故選取為將使目標(biāo)函數(shù)值得到較大下降。2.4.3 單純形算法1、初始單純形表的建立對于線性規(guī)劃其中B是可逆矩陣，可作為這個線性規(guī)劃的基，并建立以下矩陣： ()由上述討論可知：u 是線性規(guī)劃的一個基本可行解。u 的各分量就是判別數(shù)。u 是對應(yīng)于基本可行解的目標(biāo)函數(shù)值。因此，矩陣式()記錄著我們所關(guān)心的關(guān)于線性規(guī)劃的全部信息。我們將這個矩陣稱為線性規(guī)劃的初始單純形表。特別地，若基是單位矩陣，則初始單純形表變?yōu)?()如果將A用來表示，則基向量的判斷數(shù)為零，且將目標(biāo)函數(shù)值用來表示，則式()又可記為其中此時，線性規(guī)劃對應(yīng)的初始單純形表的一般形式即為下表所示。 1 1 1 0 0 0 初始單純形表

29、記錄著以下信息：(1) 等式約束的有關(guān)數(shù)據(jù)；(2) 各列向量的判別數(shù)；(3) 初始基本可行解；(4) 對應(yīng)于的目標(biāo)函數(shù)值。對于基B=I的線性規(guī)劃，建立初始單純形表需要計算非基變量的判別數(shù)，以及相應(yīng)的目標(biāo)函數(shù)值。2、換基運算后的新單純形表在初始單純形表上對線性規(guī)劃作換基運算。首先確定主元，然后按其規(guī)則作換基運算，并對單純形表的最后一行作相應(yīng)的變換，即 （注意，此時） 于是，初始單純形表變?yōu)樾聠渭冃伪砣缦聢D所示。 1 0 1 1 0 0 0 0 上表中：(1) 是新單純形表中判別數(shù)； (2) 是新基本可行解所對應(yīng)的目標(biāo)函數(shù)值。其中在新單純形表中，(1) 若，則就是最優(yōu)解。(2) 若有某個，而，則原

30、規(guī)劃無最優(yōu)解。(3) 若有且有正分量，則可定理3選擇進基列再次作換基運算。3、單純形算法 設(shè)A 中有個列構(gòu)成單位矩陣。已知：計算步驟：(1) 構(gòu)造初始單純形表其中(2) 求。(3) 若，則(其中，)就是最優(yōu)解，否則轉(zhuǎn)(4)。(4) 若，則無最優(yōu)解，否則轉(zhuǎn)(5)。(5) 求。(6) 以為主元對初始單純形表作換基運算得到新單純形表，轉(zhuǎn)(2)。舉例：求解線性規(guī)劃解：取為初始基。則為初始基本可行集。由計算出：，、為基變量所對應(yīng)的判別數(shù)，必有因此，初始單純形表如下所示。 b1 3 -1 0 2 00 -2 1 0 00 -4 3 0 8 1712100 -1 3 0 -2 00在非零判別數(shù)中，只有，且有

31、正分量，故應(yīng)將引入基底。由，可知，應(yīng)選為主元作換基運算得到如下新單純形表。 b1 2/5 0 1/4 2 00 -1/2 1 1/4 0 00 -5/2 0 -3/4 8 11031 0 1/2 0 -3/4 -2 0-9上表中只有，且有正分量，故應(yīng)以為主元作換基運算得到如下新單純形表。 b2/5 1 0 1/10 4/5 01/5 0 1 3/10 2/5 01 0 0 -1/2 10 14511-1/5 0 0 -4/5 -12/5 0-11上表中各判別數(shù)，故當(dāng)前基本可行解為為最優(yōu)解。此時目標(biāo)函數(shù)值為。由上可知，利用單純形方法求解線性規(guī)劃，首先找出一個基本可行解。將目標(biāo)函數(shù)寫成非基變量的線

32、性組合(再加上一個常數(shù))的形式。如果組合的系數(shù)全部非負，則已經(jīng)找到最優(yōu)解。如果組合的系數(shù)中有負數(shù)，從中選取一個變量(“進基”)來增加取值，可以使得函數(shù)值減少。根據(jù)約束條件，可以控制增加的范圍。在進基變量取最大值時，有一個變量出，從而得到另一個基可行解。重復(fù)上面的過程，可以求得最優(yōu)解。4、單純形法的進一步討論問題：線性規(guī)劃問題化為標(biāo)準(zhǔn)形時，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構(gòu)造初始可行基？獲取初始基本可行解的方法通常有大M法和兩階段法，這兩種方法都是引入非負人工變量來求解。對于線性規(guī)劃引入 使得約束條件變?yōu)轱@然變量對應(yīng)的基陣為單位陣。由此可以得到一個基本可行解為。（即為基變量，為非基變量

33、）。利用單純形方法可以在基本可行解的范圍內(nèi)進行迭代，一旦找到不含這些人工變量的基本可行解，迭代就可以回到原問題范圍內(nèi)進行。問題：約束條件已改變，目標(biāo)函數(shù)如何調(diào)整？-“懲罰”人工變量！4.1 大M法大M法也稱懲罰法，該方法是在目標(biāo)函數(shù)中增加含人工變量的項，共有項，其中M為任意大的正數(shù)，則原線性規(guī)劃問題變?yōu)檩o助問題求解上述線性規(guī)劃問題就是從最小化角度迫使人工變量取零，以達到求原問題最優(yōu)解的目的。此時可作為一個基本可行解，對上述線性規(guī)劃問題可以用單純形方法求解。容易理解，若為輔助線性規(guī)劃問題的最優(yōu)解，當(dāng)時，即為原問題的最優(yōu)解；否則，原問題無可行解。舉例：求解線性規(guī)劃問題解：(1)加入松弛變量和剩余變

34、量進行標(biāo)準(zhǔn)化, 加入人工變量構(gòu)造初始可行基。(2)用單純形法求解其最優(yōu)解為，目標(biāo)函數(shù)值。(3)求解結(jié)果出現(xiàn)檢驗數(shù)非正若基變量中含非零的人工變量，則無可行解；否則，有最優(yōu)解。4.1 兩階段法由于在大M法中引入一個很大的正數(shù)，可能產(chǎn)生較大的舍入誤差，且在計算機上處理困難，故在實際問題中常用兩階段法。所謂兩階段法，就是將線性規(guī)劃問題的求解過程分成兩階段，即先求初始基，再求解。兩階段法與大M法的不同之處在于其輔助問題中的目標(biāo)函數(shù)僅為各人工變量之和，即輔助問題當(dāng)輔助線性規(guī)劃問題的最優(yōu)解時，若為其最優(yōu)解，則當(dāng)時，必為原問題的最優(yōu)解；否則，原問題無可行解。第一階段：構(gòu)造如下的線性規(guī)劃問題用單純形法求解上述問

35、題，若，進入第二階段；否則,原問題無可行解。第二階段：去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表，然后利用單純形法求解即可（下面舉例說明，仍用大M法的例)。舉例：求解線性規(guī)劃問題解：(1)構(gòu)造第一階段問題并求解。利用單純形法求解表3中不含人工變量且，轉(zhuǎn)入第二階段。表4：去掉人工變量后的初始單純形表表5：最終單純形表單純形法計算中的幾個問題：1、目標(biāo)函數(shù)極小化時解的最優(yōu)性判斷只需用檢驗數(shù)作為最優(yōu)性的標(biāo)志。2、無可行解的判斷當(dāng)求解結(jié)果出現(xiàn)所有時，如基變量仍含有非零的人工變量（兩階段法求解時第一階段目標(biāo)函數(shù)值不等于0），則原線性規(guī)劃問題無可行解。單純形法有三種形式： 方程組形式； 表格形式；

36、矩陣形式。一、方程組形式的單純形法1、思路由一個基本可行解轉(zhuǎn)化為另一個基本可行解。例1： 改寫 2、單純形法的幾何意義3、單純形法的計算步驟二、單純形表從上述單純形法迭代原理中可知，每一次迭代計算只要表示出當(dāng)前的約束方程組及目標(biāo)函數(shù)即可。按定義，化為當(dāng)前基對應(yīng)的典式。例2：用單純形表求解LP問題解：化標(biāo)準(zhǔn)型表1：列初始單純形表(單位矩陣對應(yīng)的變量為基變量)表2：換基(初等行變換，主列化為單位向量，主元為1)表3：換基(初等行變換，主列化為單位向量，主元為1)步驟：1、初始基可行解的確定l 觀察法：直接觀察得到初始可行基。l 約束條件: 加入松弛變量即形成可行基。l 約束條件: 加入非負人工變量

37、。 2、最優(yōu)性檢驗與解的判別(1)最優(yōu)解判別定理：若為基可行解，且全部，則為最優(yōu)解。(2)唯一最優(yōu)解判別定理：若所有，則存在唯一最優(yōu)解。(3)無窮多最優(yōu)解判定定理：若，且存在某一個非基變量的，則存在無窮多最優(yōu)解。(4)無界解判定定理：若有某一個非基變量的，并且對應(yīng)的非基變量的系數(shù)，則具有無界解。令為基變量，為非基變量，則是一初始基可行解。5、對偶線性規(guī)劃5.1 問題提出假設(shè)某工廠有種設(shè)備：，一年內(nèi)各設(shè)備的生產(chǎn)能力(有效臺時數(shù))為。利用這些設(shè)備可以加工種產(chǎn)品：，單位產(chǎn)品的利潤分別為。第種產(chǎn)品需要在第種設(shè)備上加工的臺時數(shù)為。問在設(shè)備能力允許的條件下怎樣安排生產(chǎn)計劃，使全年總收入最多?設(shè)為各產(chǎn)品的計

38、劃年產(chǎn)量，為全年總收入，則該問題的數(shù)學(xué)模型為        (P)換個角度(從經(jīng)濟問題角度)：假設(shè)工廠將所有的設(shè)備用于出租，需要給各種設(shè)備制定出租價格。定價原則有兩條：一是出租后得到的單位利潤不得少于直接生產(chǎn)時的收入；二是出租價格盡量的低，以利于市場競爭。設(shè)第種設(shè)備的單位臺時的出租價格為，全年總收入為，則得到另一個線性規(guī)劃問題的數(shù)學(xué)模型為 (D)如果將式(P)的線性規(guī)劃問題稱作原問題，則式(D)為其對偶問題。5.2 對稱形式的對偶線性規(guī)劃定義(從數(shù)學(xué)問題角度)：線性規(guī)劃問題(P)為對稱形式的線性規(guī)劃問題，其對偶規(guī)劃(D)定義

39、為或矩陣形式舉例：已知線性規(guī)劃寫出其對偶線性規(guī)劃。解：       令，則其對偶線性規(guī)劃為即 由對稱形式的線性規(guī)劃問題構(gòu)造其對偶問題的一般規(guī)則是：原規(guī)劃問題是求目標(biāo)函數(shù)最大，其約束條件統(tǒng)一是“”，則其對偶問題是目標(biāo)函數(shù)最小，其約束條件統(tǒng)一為“”；原規(guī)劃問題中與相應(yīng)的每個約束條件，對應(yīng)著對偶問題的一個決策變量；原規(guī)劃問題的一個決策變量，對應(yīng)著對偶問題的一個約束條件 5.3 非對稱形式的對偶線性規(guī)劃在討論線性規(guī)劃的標(biāo)準(zhǔn)形式時，需將不等式約束都轉(zhuǎn)化為等式約束，而得到下面形式的線性規(guī)劃 ()然而線性規(guī)劃()的對偶規(guī)劃應(yīng)該是什么形式呢？主要思想：將非對稱

40、形式的線性規(guī)劃問題轉(zhuǎn)化為對稱形式的線性規(guī)劃問題，再寫出其對偶問題，也可由其對應(yīng)關(guān)系表直接寫出。分析思路：線性規(guī)劃等價于則線性規(guī)劃()可變?yōu)?()因此式()的對偶規(guī)劃為 ()令，則式()變?yōu)?()由的表達式可知，這里不能再要求。這就是式()的對偶規(guī)劃。舉例：寫出下面線性規(guī)劃的對偶規(guī)劃解： 令，則得到原規(guī)劃的對偶規(guī)劃為通常，非對稱形式的線性規(guī)劃問題轉(zhuǎn)化為對稱形式的線性規(guī)劃問題的步驟如下：第1步 目標(biāo)函數(shù)：對最大化問題轉(zhuǎn)化為最小化問題，即； 第2步 約束條件：對“”不等式方程兩邊同乘以“-1”；對“=”等式方程可寫成兩個“”式，即第3步 決策變量：若，可令，使；若無約束，令，使。舉例：試求下述線性規(guī)

41、劃問題的對偶問題解：設(shè)對應(yīng)于三個約束條件的對偶變量分別為，按照原問題與對偶問題的對應(yīng)關(guān)系，則其對偶問題為5.4 對偶定理上節(jié)著重討論了怎樣從一個已知的線性規(guī)劃寫出其對偶規(guī)劃。原規(guī)劃 與對偶規(guī)劃的最優(yōu)解之間，很自然地有著密切的關(guān)系。本節(jié)將主要討論對稱形式的對偶定理。設(shè)線性規(guī)劃其可行集為，以及其對偶規(guī)劃及其可行集為。定理1 ，必有證明：由于，則顯然，這個結(jié)論對于非對稱形式對偶規(guī)劃的可行集來說也是成立的。這就是說，如果原規(guī)劃是求極小，則原規(guī)劃的目標(biāo)函數(shù)值在可行集內(nèi)不大于對偶規(guī)劃的目標(biāo)函數(shù)值。定理2 線性規(guī)劃(LP)與其對偶規(guī)劃(DP)都有最優(yōu)解的充要條件是它們都有可行解。證明：必要性，顯然。下面證明

42、充分性。設(shè)和分別是問題(LP)和(DP)的可行解，則由定理1可知，這個不等式說明(LP)的目標(biāo)函數(shù)值在可行集上有下界，而(LP)是求極小，故必有最優(yōu)解。同理，(DP)的目標(biāo)函數(shù)值在可行集上有上界，而(LP)是求極大，故必有最優(yōu)解。推論：如果，且，則X與W分別是(LP) 與(DP)的最優(yōu)解。定理3 若線性規(guī)劃(LP)與其對偶規(guī)劃(DP)中有一個有最優(yōu)解，則另一個也必有最優(yōu)解，且其目標(biāo)函數(shù)的最優(yōu)解相等。證明：設(shè)(LP)有最優(yōu)解。引入剩余變量Y，將(LP)化成標(biāo)準(zhǔn)形式設(shè)為上式的一個最優(yōu)基本可行解，是所對應(yīng)的最優(yōu)基，是中基變量所組成的向量，則由最優(yōu)解判別準(zhǔn)則可知令，則由上式可知即 故是(DP)的可行解

43、。由因為 因此由定理2的推論可知，是(DP)的最優(yōu)解。此時，與分別是(LP)與(DP)的最優(yōu)值，即 證畢兩個互為對偶的線性規(guī)劃的解之間關(guān)系：n 兩個規(guī)劃都有可行解（或都有可行解）；n 兩個規(guī)劃都沒有最優(yōu)解（或都沒有可行解）；n 一個有可行解，但目標(biāo)函數(shù)在可行集上無界，則另一個沒有可行解。從上述證明還可以看出，如果是(LP)的最優(yōu)基，則就是(DP)的最優(yōu)解。這樣一來就可以直接從(LP)的最終單純形表中求得(DP)的最優(yōu)解。下面以對稱形式為例，討論如何直接地從原規(guī)劃的最終單純形表求其對偶規(guī)劃的最優(yōu)解的問題。定理4 設(shè)與分別為對稱形式的原規(guī)劃(LP)與對偶規(guī)劃(DP)的可行解，則與同時也分別是(LP

44、)與(DP)的最優(yōu)解的充要條件是證明：充分性。由條件式可知故 而與分別是(LP)與(DP)的可行解，由定理2的推論可知，與分別是(LP)與(DP)的最優(yōu)解。 必要性。由于與分別是(LP)與(DP)的可行解，所以則可得又與都是相應(yīng)線性規(guī)劃的最優(yōu)解，故因此 即 5.4 對偶單純形法對偶單純形法是利用對偶原理來求解原線性規(guī)劃問題的一種方法，而不是直接求對偶問題的方法。前面介紹的單純形法相對而言稱為原始單純形法。5.4.1 基本思想對于線性規(guī)劃及其對偶規(guī)劃定理5 設(shè)是(P)的任一基本解，對應(yīng)于基，若與分別是(P)與(D)的可行解，則、分別是(P)與(D)的最優(yōu)解。證明：由于是(D)的可行解，故，即 (

45、)這就說明是(P)對應(yīng)于基的可行解，且所有判別數(shù)，故是(P)的最優(yōu)解。又由定理2的推論，、分別是(P)與(D)的最優(yōu)解。證畢在定理的證明過程中可以看到，的判別數(shù)全部非正與是(D)的可行解是等價的（由于，即）。反之，若是(D)的可行解，則的判別數(shù)全部非正。定義 設(shè)是原規(guī)劃(P)的一個基本解，且的所有判斷數(shù)非正，則稱為(P)的一個正則解。所對應(yīng)的基稱為正則基。闡述之二：用單純形法求解線性規(guī)劃問題(LP)的思路是，由一個基本可行解迭代到下一個基本可行解，在迭代過程中始終保持解的可行性不變，檢驗數(shù)逐步變?yōu)槿繛榉钦倪^程。一旦所有檢驗數(shù)為非正，則對應(yīng)的基本可行解就是最優(yōu)解。當(dāng)所有檢驗數(shù)為非正時，由式() 可推得正是對偶問題(DP)的可行解，因此將原問題(LP)對應(yīng)于檢驗數(shù)全部非正的基本可行解稱為對偶可行解(或正則解?？梢赃@樣來解釋用單純形法求解原問題(LP)的迭代過程：由一個基本可行解經(jīng)迭代得到最優(yōu)解是在迭代過程中始終保持解的可行性不變，其對偶問題的解由不可行性逐步變?yōu)榭尚?，對偶問題的解一旦成為可行