1、管理運籌學第4章 對偶線性規(guī)劃與靈敏度分析對偶性是線性規(guī)劃最重要的內容之一，也是線性規(guī)劃早期研究的最重要成果之一。每一個線性規(guī)劃問題必然有與之相伴而生的另一個線性規(guī)劃問題，其中一個問題稱為原問題，另一個稱為對偶問題。這兩個問題之間存在著非常密切的關系。本章主要涉及對偶的三個問題：一是給定了原問題，如何寫出其對偶問題；二是研究原問題和對偶問題之間的關系；最后給出解線性規(guī)劃的對偶單純形方法。4.1 原問題與對偶問題在對稱形式下，原問題與對偶問題有如下關系：原問題中求目標函數極大值，對偶問題中為求目標函數極小值；原總是中約束條件個數等于對偶問題中變量的個數，原問題中變量的個數等于對偶總是中的約束條件

2、個數；原問題中約束條件符號為，對偶問題中約束條件符號為；原問題目標函數的系數是其對偶問題約束條件的右端項，而原問題約束條件的右端項則是其對偶問題目標函數的系數。4.1 原問題與對偶問題但是，并非所有線性規(guī)劃都具有上述對稱形式，對于一般情況下線性規(guī)劃問題的對偶問題，可以分以下幾種情況來討論： 1. 等號約束問題【定理4.1】如果原始問題的約束條件是等式，則對偶問題中的變量無符號限制。2. 極大化目標函數、約束條件為的問題【定理4.2】 如果極小化原始問題中的約束條件（不包括變量非負約束）為，則對偶問題中的變量具有非正（0）約束。4.1 原問題與對偶問題于是可得到下面的推論：【推論4.1】 如果原

3、始問題中的變量無符號限制，則對偶問題中的約束條件為等式約束。【推論4.2】 如果原始問題中的變量具有非正（0）約束，則極小化對偶問題的約束條件為約束。4.1 原問題與對偶問題為了更好地理解以上結論，給出如下例子。【例4-2】 寫出以下原始問題的對偶問題： max z=2x1-x2+4x3+x4 x1+3x2-x3+5x412s.t. -2x1-2x2+3x3-2x4=25 3x1+x2-2x3+x418 x10 x20 x3:unr x404.1 原問題與對偶問題極大化問題（max）極小化問題（min）約束aijxicjyj0變量aijxi=cjyj:unraijxicjyj0變量xi0aij

4、yjbi約束xi:unraijyj=bixi0aijyjbi 通過對稱形式和一般形式的討論，可以對原始問題和對偶問題之間的關系做出如下總結： 4.2 對偶問題的基本性質1. 對稱性：對偶問題的對偶是原問題。設原始問題為：max z=CTXs.t. AXb (P) X0根據定義，對偶問題為：min =bTYs.t. ATYC (D) Y04.2 對偶問題的基本性質2. 弱對偶性極小化原始問題的任一可行解的目標函數值總是大于或等于極大化對偶問題的任一可行解的目標函數值。也就是說，若 是原問題的可行解， 是對偶問題的可行解。則恒有： 。這就是弱對偶定理，其證明如下：證明：設原始問題為max z=CT

5、Xs.t.AXb (P) X0則對偶問題為：min =bTYs.t.ATYC (D) Y04.2 對偶問題的基本性質3.最優(yōu)性如果XF和XF分別是原始問題和對偶問題的可行解，并且它們對應的目標函數值相等，則XF和XF分別是原始問題和對偶問題的最優(yōu)解。即可行解是最優(yōu)解時的性質：設是原問題的可行解，是對偶問題的可行解，當z=CTX= bTY =w時，X，Y是最優(yōu)解。證明如下：證明：設XF 是原問題的最優(yōu)解，YF 是其對偶問題的最優(yōu)解由弱對偶性， CTXFbTYF可知CTX CTXF bTYFbTY又由已知 z=CTX= bTY =w所以CTX =CTXF=bTYF=bTY即X也是原問題的最優(yōu)解，Y

6、也是其對偶問題的最優(yōu)解。4.2 對偶問題的基本性質4.無界性如果原始問題和對偶問題中的任一個目標函數無界，則另一個必定無可行解。注意這個性質的逆命題不成立，即一個問題無可行解，不能推得另一個問題目標函數無界。事實上，一對原始對偶問題都沒有可行解的情況是存在的。 4.2 對偶問題的基本性質5.對偶定理若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們的最優(yōu)解的目標函數值相等。證明：由于原問題及其對偶問題均具有可行解，根據弱對偶性，可以確定原問題的目標函數具有上界，對偶問題的目標函數具有下界，因此兩者均具有最優(yōu)解。設原問題的最優(yōu)基為B，對應的基礎最優(yōu)解為X，通過單純形法可知，原問題的最優(yōu)

7、值為z=CTX= B-1b，且CT B-1A04.2 對偶問題的基本性質對于對偶問題，令YT= B-1，則由上式可得AYTCT又由于Y是對偶問題的可行解，其對應的目標函數值w =YTb= B-1 b所以有 z=CTX= bYT = w可知，當原問題為最優(yōu)解時，其對偶問題的解為可行解，且有z =w，由最優(yōu)性，這時兩者的解均為最優(yōu)解，且它們的目標函數值相等。4.2 對偶問題的基本性質6.互補松弛關系【定理4.3】 若X=(x1，x2，xn)T和Y=(y1，y2，ym)T分別是原始問題和對偶問題的最優(yōu)解，則有或用矩陣向量表示為4.2 對偶問題的基本性質證明：設原始問題為max z=CTXs.t.AX

8、b (P)X0則對偶問題為：min z=bTYs.t.ATYC (D)Y04.2 對偶問題的基本性質【推論4.3】 由于Xo，Yo分別是原始對偶問題的最優(yōu)解，因此在以上兩式中，有4.2 對偶問題的基本性質【推論4.4】 若原始問題的最優(yōu)解Xo對于某一個約束i，有 則對偶問題最優(yōu)解中該約束對應的對偶變量 Yio=0反之，若在對偶問題的最優(yōu)解中，第i個對偶變量 Yio0則原始問題最優(yōu)解對于相應的第i個約束是等號約束，即 也就是說，原始問題最優(yōu)解中的第i個松弛變量等于0。4.2 對偶問題的基本性質【定理4.4】 若向量 和 分別是原始問題和對偶問題的最優(yōu)解，當且僅當它們滿足以下三個條件：（1）X、X

9、S是原始問題 min z=CTX s.t.AX-Xs=b(P)X，Xs0的可行解。這個條件稱為原始可行條件。4.2 對偶問題的基本性質（2）Y、Ys是對偶問題max z=bTYs.t. ATY+Ys=C (D) Y，Ys0的可行解。這個條件稱為對偶可行條件（Dual Feasible Condition，DFC）。（3）X、Xs、Y、Ys滿足 YTXs=0 YsTX=0這個條件稱為互補松弛條件（Complementary Slackness Condition，CSC）。4.2 對偶問題的基本性質綜上所述，單純形法和Kuhn-Tucker條件的關系可敘述如下：在單純形迭代過程中，如果當前基B是

10、原始可行基而不是最優(yōu)基，則（1）原始問題相應的解X、Xs滿足原始可行條件；（2）對偶問題相應的解YT=CBTB-1、YsT=CT-YTA中至少有一個不滿足對偶可行條件；（3）X、Xs、Y、Ys在單純形疊代的每一步，都滿足互補松弛關系。當B不僅可行，而且是最優(yōu)基時，對偶問題相應的解YT=CBTB-1、YsT=CT-YTA才滿足對偶可行條件。因此，可以把單純形法看成在原始可行條件和互補松弛條件得到滿足的條件下，不斷改進對偶可行條件的過程，一旦三個條件都得到滿足，也就得到了最優(yōu)解。4.2 對偶問題的基本性質7. 互補基解線性規(guī)劃的原問題及其對偶問題之間存在一對互補的基解，其中原問題的松馳變量對應對偶

11、問題的變量，對偶問題的剩余變量對應原問題的變量；這些互相對應的變量如果在一個問題的解中是基變量，則在另一問題的解中是非基變量； 將這對互補的基解分別代入原問題和對偶問題的目標函數有z=y。證明：因為Zj -Cj =CBB-1Pj - Cj =YT Pj - Cj所以，YT Pj -（Zj -Cj）= Cj也就是 -（Zj -Cj）= Cj4.3 對偶單純形法由上一節(jié)知道，線性規(guī)劃取得最優(yōu)解的充分必要條件是原始可行、對偶可行和互補松弛條件同時滿足。同時，也曾指出，單純形迭代過程實際上是在滿足原始可行條件和互補松弛條件的基礎上，不斷改進對偶可行性的過程，一旦對偶可行條件得到滿足，就得到了最優(yōu)解。對

12、偶單純形法則是從另一角度來進行的。對偶單純形法在迭代過程中保持對偶可行條件和互補松弛條件滿足，并且在迭代過程中不斷改進原始可行條件。一旦原始可行條件得到滿足，也就求得了最優(yōu)解。為了說明對偶單純形法原理，先建立有關概念和定理。4.3 對偶單純形法【定義4.1】 （對偶可行基）設B為原始問題的一個基，若XT=CBTB-1是對偶問題的可行解，則稱B為原始問題的對偶可行基。【定理4. 5】 若基B既是原始問題的可行基，又是原始問題的對偶可行基，則B必定是原始問題的最優(yōu)基。證明：因為B是原始問題的可行基，因此4.3 對偶單純形法同時因為B是對偶可行基，根據對偶可行基的定義，XT=CBTB-1滿足對偶問題

13、的約束條件，即XTACTXT0或：CBTB-1A-CT0T-CBTB-10T以上兩個條件，就是：zjcj0,j=1, 2, , n, n+1, , n+m因此，B是原始問題的最優(yōu)基。4.3 對偶單純形法對偶單純形法的計算步驟如下：（1）確定換出基的變量：存在小于零的bi 時，令 br =min bi ，其對應變量xr 為換出基的變量（2）確定換入基的變量：為使迭代后表中第r行基變量為正值，因而只有對應rj 0（j=m+1，n）的非基變量才可以考慮作為換入基的變量；為使迭代后表中對偶總是的解仍為可行解，令：稱r，S 為主元素，xs 為換入基的變量。4.3 對偶單純形法（3）用換入變量替換換出變量

14、，得到一個新的基。用新的基再檢查是否所有bi（i=1，2，m，）。如果是，找到了問題的最優(yōu)解，如果否，回到第一步再重復計算。由對偶問題的基本性質知，當對偶問題存在可行解時，原問題可能存在可行解，也可能無可行解，對出現后一種情況的判別準則為：對br 0，而對所有j=1，n，有rj 0。因為在這種情況下，如把表中第r行的約束方程列出有因rj 0（j=m+1，n），又br 0時，有 ，這表明生產過程中如果某種資源bi 未得到充分利用時，該種資源的影子價格為0；又當資源的影子價格不為0時，表明該種資源在生產中已消耗完畢。從影子價格的含義上再來考察單純形法的計算。4.4 線性規(guī)劃對偶問題的經濟解釋（4）

15、記 ，式中 代表第j種產品的產值， 是生產該種產品所消耗各種資源的影子價格的總和，即產品的隱含成本。當產品產值大于隱含成本時，表明生產該項產品有利，可在計算中安排，否則用這些資源來生產別的產品更為有利，就不在生產計劃中安排。這就是單純形法中各個檢驗數的經濟意義。（5）一般講，對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當估價，這種做人直接涉及資源的最有效利用。4.4 線性規(guī)劃對偶問題的經濟解釋4.4.2 互補松弛關系的經濟解釋互補松弛關系在經濟學中應用也十分廣泛，尤其是結合線性規(guī)劃問題的對偶形式，更能體現線性規(guī)劃模型和實際應用之間的關系。在考慮互補松弛條

16、件的時候，一般會考慮以下幾種情形：（1）若在最優(yōu)生產計劃下，第i種設備的能力大于這種設備實際耗用，或者說第i種設備能力有剩余，這種設備的微小增加對利潤沒有影響，按邊際貢獻的概念，有4.4 線性規(guī)劃對偶問題的經濟解釋在這種情況下，原問題最優(yōu)解中會有：在這種情況下，第i種設備開工的機會成本小于實際成本，松弛變量xm+j0，對降低總成本來說，這種設備不開工更為有利，即Yi=0。于是互補松弛關系ixm+j=0成立。反之，如果在最優(yōu)解中，某一種設備開工，即Yi0，可以肯定，這種設備的實際成本與機會成本相等，即可以斷定這種設備能力沒有剩余, 即松弛變量xm+j=0，從而同樣滿足互補松弛條件Yixm+j=0

17、也成立。4.4 線性規(guī)劃對偶問題的經濟解釋（2） 如果在最優(yōu)設備運行計劃下，第i種產品的實際生產量超過需求量，也就是說某種產品的機會成本高于這種產品的利潤，此時有：而松弛變量Yn+i0這時再增加一個單位需求，不會影響設備運行計劃，即對最小成本沒有影響，在這種情況下，最優(yōu)解中這種產品一定不會安排生產，因此有即影子價格等于0。于是互補松弛關系Yn+ixi=0成立。4.4 線性規(guī)劃對偶問題的經濟解釋反之，如果某一種產品需求的影子價格xi0，這時產品需求每增加一個單位將會引起總成本zo的增加，這說明實際生產這種產品的數量恰等于需求量，即或松弛變量Yn+i=0，于是互補松弛關系Yn+ixi=0成立。4.

18、4 線性規(guī)劃對偶問題的經濟解釋4.4.3 最大利潤問題以及對偶問題的經濟解釋各種設備能力的邊際利潤率為： 由此可知，對偶問題最優(yōu)解中對偶變量xio(i=1,2,m)的值就是相應設備的能力對總利潤的邊際貢獻。xio也成為相應設備能力約束的影子價格，xio越大，表明相應的設備能力每增加一個單位，引起總利潤的增加越大，也就是說，相對于最優(yōu)生產計劃來說，這種設備能力比較緊缺；xio較小，表明設備能力相對不緊缺；xio=0，說明在最優(yōu)生產計劃下第I種設備能力有剩余。4.4 線性規(guī)劃對偶問題的經濟解釋4.4.4 關于弱對偶定理的經濟學解釋弱對偶定理說明了這樣一個事實：極大化原始問題的任一可行解的目標函數值

19、總是小于或等于極小化對偶問題的任一可行解的目標函數值。對于最大利潤問題，定理2.4的形式成為CTXYTAXYTb上式種左邊的不等式，是由于某些產品的利潤率和機會成本不相等引起的，即CTYTA。當取得最優(yōu)解時，由于互補松弛條件的作用，凡機會成本和利潤率不相等的產品都將不安排生產，因而使得不等式成為等式。4.4 線性規(guī)劃對偶問題的經濟解釋右邊的不等式是由于某些設備的實際耗用小于設備的實際能力引起的，即AXb同樣由于互補松弛條件，實際耗用和能力不等的這些設備，影子價格都等于零，從而使右邊的不等式也成為等式。這樣，當原始和對偶問題都取得最優(yōu)解時，有CTX=YTAX=YTb4.4 線性規(guī)劃對偶問題的經濟

20、解釋4.4.5 經濟解釋的例子 【例4-5】 某工廠擁有A、B、C三種類型的設備，生產甲、乙、丙、丁四種產品。每件產品在生產中需要占用的設備機時數，每件產品可以獲得的利潤以及三種設備可利用的時數如表4-3所示，用線性規(guī)劃制訂使總利潤最大的生產計劃。4.4 線性規(guī)劃對偶問題的經濟解釋 【例4-6】 求解表4-4中的利潤最大問題：4.4 線性規(guī)劃對偶問題的經濟解釋由此可以清楚地看出，資源剩余量和影子價格之間以及“機會成本利潤率”和產品產量之間的互補松弛關系（表中箭頭表示“一個變量大于零，導致另一個變量等于零”的互補松弛關系）。可以看出最優(yōu)解中產品不安排生產的原因是這種產品的機會成本高于利潤率。一般

21、來說，一種產品在最優(yōu)解中是否安排生產，不僅與這種產品的利潤率有關，還與這種產品對資源的消耗以及各種資源的緊缺程度有關。而線性規(guī)劃模型，正是提供了對以上諸多因素進行系統(tǒng)分析的工具。4.5 靈敏度分析靈敏度分析是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。在以前討論線性規(guī)劃問題時，假定 都是常數。但實際上這些系數往往是估計值和預測值。如市場條件一變， 值就會變化； 往往是因工藝條件的改變而改變； 是根據資源投入后的經濟效果決定的一種決策選擇。因此提出這樣兩個問題：（1） 當這些參數有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化； 或者這些參數在什么范圍內變化時，線性規(guī)劃

22、問題的最優(yōu)解不變。（2）當線性規(guī)劃問題增加一個新的變量或新的約束，如何在原來最優(yōu)解的基礎上獲得新的最優(yōu)解。這就是靈敏度分析所要解決的問題。4.5 靈敏度分析靈敏度分析的步驟如下：（1）將參數的改變計算反映到最終單純形表上：按下列公式計算出由參數 的變化而引起的最終單純形表上有關數字的變化：（2）檢查原問題是否仍為可行解；（3）檢查對偶問題是否仍為可行解；4.5 靈敏度分析（4）按下表所列情況得出結論和決定繼續(xù)計算的步驟原問題對偶問題結論和決定繼續(xù)計算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解仍為問題最優(yōu)解用單純形法繼續(xù)迭代求最優(yōu)解用對偶單純形表繼續(xù)迭代求最優(yōu)解引進人工變量，

23、編制新的單純形表，重新計算4.5 靈敏度分析4.5.1 目標函數系數C的變化范圍C中元素cj的變化范圍與相應的變量xj是基變量還是非基變量有所不同，下面分別就這兩種情況來討論。m個基變量xBr（r=1,2,m）檢驗數為：4.5 靈敏度分析n-m個非基變量xj的檢驗數為：設某一個基變量xB在目標函數中的系數為cB， 當這個基變量xB的系數cB 變化成為cB=cB+ 時，m個基變量xBr在目標函數中的系數為：即基變量xB在目標函數中的系數cB的變化，在最優(yōu)解中只會影響這個基變量的檢驗數，其他基變量的檢驗數不會變化。如果檢驗數zB-cB-0，則原來的最優(yōu)基仍保持為最優(yōu)基，如果檢驗數zB-cB-0，則

24、原來的最優(yōu)基不再是最優(yōu)基，新的最優(yōu)基可以通過將xB進基，并進行后續(xù)的單純形迭代，得到新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析設某一個非基變量xk在目標函數中的系數為ck，當這個非基變量xk的系數ck 變化成為ck=ck+ 時，由上式可知，對基變量的檢驗數沒有影響，所有基變量的檢驗數仍為0。當這個非基變量xk的系數ck 變化成為ck=ck+ 時，n-m個非基變量xj在目標函數中的系數為：即非基變量xk在目標函數中的系數ck的變化，在最優(yōu)解中只會影響這個非基變量在目標函數中的系數，其他非基變量的系數不會變化。如果檢驗數zk-ck-0，則原來的最優(yōu)基仍保持為最優(yōu)基，如果檢驗數zk-ck-0，則原來的最

25、優(yōu)基不再是最優(yōu)基，新的最優(yōu)基可以通過將xk進基，并進行后續(xù)的單純形疊代，得到新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析 【例4-7】 線性規(guī)劃問題為： max z=2x1-x2+x3 x1+x2+x36 s.t. -x1+2x24 x1,x2,x30 求c2=-1在什么范圍內變化，原來的最優(yōu)基保持不變；當c2=3時，最優(yōu)基是否變化，如果變化，求新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析 4.5.2 右邊常數b的靈敏度分析當右邊常數向量b發(fā)生變化，成為b時，對變量的檢驗數沒有影響，而單純形表中的右邊常數將變成 。即右邊常數向量的變化只會影響最優(yōu)基的原始可行性而不會影響其對偶可行性。當變化以后的 時，原來

26、的最優(yōu)基仍為最優(yōu)基，否則，原來的基成為對偶可行基但不是原始可行基，這時要用對偶單純形法求得新的最優(yōu)基。4.5 靈敏度分析 【例4-8】 對以下線性規(guī)劃問題中第一個約束右邊常數b1=9進行靈敏度分析。 max z=-x1-x2+4x3 x1+x2+2x39 s.t. x1+x2-x32 -x1+x2+x34 x1,x2,x304.5 靈敏度分析4.5.3 增加一個新的變量當前最優(yōu)基是B。設新增加的變量xj在目標函數中的系數為cj，在約束中的系數向量是aj，計算 ， 在原單純形表中增加一個新的變量以及新的一列，將以上系數置于原單純形表中，構成新的單純形表。若新變量的檢驗數zj-cj0，則原來的基仍

27、為最優(yōu)基，原來的基變量以及基變量的值保持不變，新的變量xj=0是非基變量。否則xj進基，用單純形法繼續(xù)運行，直至獲得新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析【例4-9】線性規(guī)劃問題maxz=2x1-x2+x3 x1+x2+x36s.t. -x1+2x24 x1,x2,x30中，增加一個新的變量x6，它在目標函數中的系數c6=-1，在約束條件中的系數向量為 ，求新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析4.5.4 增加一個新的約束增加一個新的約束以后，如果原來的最優(yōu)解滿足新的約束，則原來的最優(yōu)解仍是新問題的最優(yōu)解，否則，最優(yōu)解將發(fā)生變化。 【例4-10】 設線性規(guī)劃問題為 max z=2x1-x2+x

28、3 x1+x2+x36 s.t. -x1+2x24 x1,x2,x304.5 靈敏度分析列出原問題的最優(yōu)單純形表：增加一個約束-x1+2x22，求新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析4.5.5 約束矩陣中系數的靈敏度分析1. A矩陣中非基變量系數的靈敏度分析非基變量xj對應的非基列向量aj中元素的變化，只會影響這個非基變量在目標函數中的系數而且，由于列向量aj不在基B中，因此aj中元素的變化不會影響 。當aj中的第r個元素arj變成arj=arj+時，變量xj的檢驗數為4.5 靈敏度分析當基的對偶可行性保持不變，由此可以得到的變化范圍。【例4-11】 在例4-4max z=-x1-x2+4x

29、3 x1+x2+2x39s.t. x1+x2-x32 -x1+x2+x34 x1,x2,x30中，對變量x2在第一個約束中的系數a12=1進行靈敏度分析。4.5 靈敏度分析2. A矩陣中基變量系數的靈敏度分析要象非基變量在約束矩陣中的系數一樣，來確定基變量在約束條件中系數的變化范圍，是十分困難的，在這里不作討論。對于基變量在約束條件中的系數，僅考慮當其中一個元素變化時如何求得新的最優(yōu)解。【例4-12】 對于例4-7中的線性規(guī)劃問題:max z=2x1-x2+x3 x1+x2+x36s.t. -x1+2x24 x1,x2,x30已經得到它的最優(yōu)單純形表。其中，x1是基變量，當x1在約束條件中的系

30、數向量 變?yōu)?時，求新的最優(yōu)解。4.5 靈敏度分析當約束條件右端項連續(xù)變化時，其參數線性規(guī)劃的形式為：式中 為原線性規(guī)劃問題的資源向量， 為變動向量， 為參數。4.5 靈敏度分析參數線性規(guī)劃問題的分析步驟為：（1）令 =0求解得最終單純形表；（2）將 或 項反映到最終單純形表中；（3）隨 值的增大或減小，觀察原問題或對偶問題，一是確定表中現有解（基）允許 值的變動范圍，二是當 值的變動超出這個范圍時，用單純形法或對偶單純形法求取新的解；（4）重復第3步，一直到 繼續(xù)增大或減小時，表中的解（基）不再出現變化時為止。4.5 靈敏度分析【例4-13】 分析 值變化時，下述線性規(guī)劃問題最優(yōu)解的變化。4.6線性規(guī)劃問題算法簡要介紹已經知道，解決同一種問題可以有多個算法，比較和衡量這些算法的好壞通常采納的主要標準是看這種方法解決該問題所花費時間。但是一個算法的執(zhí)行時間與很多因素有關，首先與所使用計算機的性能有關，其次與需要求解的具體問題有關，為了使衡量算法的好壞有一個比較科學客觀的標準，