對偶規(guī)劃與靈敏度分析【課件】

對偶規(guī)劃與靈敏度分析

對偶線性規(guī)劃對偶定理對偶單純形法靈敏度分析1對偶規(guī)劃與靈敏度分析對偶線性規(guī)劃1

對偶理論是線性規(guī)劃的重要內容之一。對應于每個線性規(guī)劃問題都伴生一個相應的線性規(guī)劃問題。

原問題和對偶問題緊密關聯(lián),它們不但有相同的數(shù)據(jù)集合,相同的最優(yōu)目標函數(shù)值,而且在求得一個線性規(guī)劃的最優(yōu)解的同時,也同步得到對偶線性規(guī)劃的最優(yōu)解。由對偶問題引伸出來的對偶解還有著重要的經濟意義,是研究經濟學的重要概念和工具之一。

2對偶理論是線性規(guī)劃的重要內容之一。對應于每個線性規(guī)劃對偶問題的提出例1、某工廠生產甲,乙兩種產品,這兩種產品需要在A,B,C三種不同設備上加工。每種甲、乙產品在不同設備上加工所需的臺時,它們銷售后所能獲得的利潤,以及這三種設備在計劃期內能提供的有限臺時數(shù)均列于表。試問如何安排生產計劃,即甲,乙兩種產品各生產多少噸,可使該廠所獲得利潤達到最大。對偶線性規(guī)劃設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）32303對偶問題的提出對偶線性規(guī)劃設備每噸產品的加工臺時可供臺時數(shù)

假設計劃期內甲乙兩種產品各生產噸，設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230用圖解法或單純形法可求得最優(yōu)解(元)即在計劃期內甲產品生產噸，乙產品生產8噸，可以使總利潤達到最大，為元。4假設計劃期內甲乙兩種產品各生產噸，設備每噸產

現(xiàn)在從另一個角度來考慮該工廠的生產問題:假設該廠的決策者打算不再自己生產甲,乙產品,而是把各種設備的有限臺時數(shù)租讓給其他工廠使用,這時工廠的決策者應該如何確定各種設備的租價。設分別為設備A，B，C每臺時的租價，約束條件：把設備租出去所獲得的租金不應低于利用這些設備自行生產所獲得的利潤目標函數(shù)：所獲租金總額盡量少．5現(xiàn)在從另一個角度來考慮該工廠的生產問題:設由此可得兩個對稱的線性規(guī)劃：6由此可得兩個對稱的線性規(guī)劃：6矩陣形式：7矩陣形式：7可以得到另一個線性規(guī)劃:稱之為原線性規(guī)劃問題的對偶問題,

對偶線性規(guī)劃考慮如下具有不等式約束的線性規(guī)劃問題8對偶線性規(guī)劃考慮如下具有不等式約束的線性規(guī)劃問題89910101111

若令線性規(guī)劃標準型的對偶規(guī)劃為:

線性規(guī)劃問題標準型的對偶問題考慮一個標準形式的線性規(guī)劃問題由于任何一個等式約束都可以用兩個不等式約束等價地表示,所以標準形線性規(guī)劃問題可等價表示為:它的對偶規(guī)劃為:12若令線性規(guī)劃標準型對偶線性規(guī)劃的求法

從任何一個線性規(guī)劃出發(fā),都可以求出相應的對偶規(guī)劃,在實際求解過程中,通常不通過求標準型,而是利用如下反映原始問題與對偶問題對應關系的原始─對偶表:

目標函數(shù)變量系數(shù)約束條件右端項約束條件右端項目標函數(shù)變量系數(shù)

約束條件個數(shù):n個變量個數(shù):n個變量個數(shù):m個約束條件個數(shù):m個目標函數(shù)minW目標函數(shù)maxZ對偶問題(或原問題)原問題(或對偶問題)13對偶線性規(guī)劃的求法目標函數(shù)變量系數(shù)約束條件右端項約束條件個數(shù)解:對偶規(guī)劃:例2寫出下列線性規(guī)劃的對偶問題14解:對偶規(guī)劃:例2寫出下列線性規(guī)劃的對偶問題14例3寫出下列線性規(guī)劃的對偶問題解:上述問題的對偶規(guī)劃:15例3寫出下列線性規(guī)劃的對偶問題解:上述問題的對偶規(guī)劃:15

本節(jié)討論幾條重要的對偶定理,這些定理揭示了原始問題的解和對偶問題的解之間的基本關系。定理1:(對合性)對偶問題的對偶是原問題。證明:設原問題為對偶問題為改寫對偶問題為對偶問題的對偶為對偶定理16本節(jié)討論幾條重要的對偶定理,這些定理揭示了原始問題的解和

定理2:弱對偶定理

若是原(極小化)問題的可行解,是對偶(極大化)問題的可行解,那么

證明：因為是對偶問題的可行解，所以滿足約束條件又因為是原問題的可行解，可得，,所以。注:原(極小化)問題的最優(yōu)目標函數(shù)值以對偶問題任一可行解的目標函數(shù)值為下界。對偶(極大化)問題的最優(yōu)目標函數(shù)值以原問題任一可行解的目標函數(shù)值為上界。

推論1:如果原問題沒有下界(即minZ→－∞),則對偶問題不可行。如果對偶問題沒有上界(即maxW→＋∞),則原問題不可行。

若原問題與對偶問題之一無界,則另一個無可行解。17定理2:弱對偶定理證明：因為是對偶問題的可行解，所證明:由弱對偶定理,對于原始問題的所有可行解,都有因此是原問題的最優(yōu)解。同理,對于對偶問題的所有可行解,都有所以是對偶問題的最優(yōu)解。推論2：最優(yōu)性定理

若是原問題的可行解，是對偶問題的可行解，而且兩者的目標函數(shù)值相等，即，則和分別是原問題和對偶問題的最優(yōu)解。18證明:由弱對偶定理,對于原始問題的所有可行解,都有證明:設是原問題(min)的最優(yōu)解,則對應的基Ｂ必有。若定義,則,

因此為對偶問題的可行解,而且,由最優(yōu)性定理,是對偶問題的最優(yōu)解。

定理3:強對偶定理如果原問題(min)與對偶問題(max)之一有最優(yōu)解,那么另一個也有最優(yōu)解,而且目標函數(shù)值相等。19證明:設是原問題(min)的最優(yōu)解,則對應的基Ｂ必有證明:設滿足原問題(min)的最優(yōu)性條件,則對應的基Ｂ必有。若定義,則,

因此為對偶問題的基本可行解。

定理4:設滿足原問題(min)的最優(yōu)性條件的一個基本解,則其對應的線性規(guī)劃問題(min)的檢驗數(shù)對應對偶問題的一個基本可行解。20證明:設滿足原問題(min)的最優(yōu)性條件,則對應的基Ｂ必原問題與對偶問題可能出現(xiàn)的情況(1)兩者都有最優(yōu)解,且最優(yōu)值相等;(2)一個有可行解,但無界,則另一個無可行解;(3)兩者都無可行解。21原問題與對偶問題可能出現(xiàn)的情況21定理5：互補松弛定理

如果分別是原問題(min)和對偶問題（max)的可行解，那么和為最優(yōu)解的充要條件是

通常稱為互補松弛條件。證明：充分性必要性22定理5：互補松弛定理證明：充分性必要性22例5、已知線性規(guī)劃問題:其對偶問題的最優(yōu)解。試用互補松弛定理找出原問題的最優(yōu)解。解：原問題的對偶問題為：由對偶問題最優(yōu)解可知，由互補松弛定理，解方程組所以原問題最優(yōu)解23例5、已知線性規(guī)劃問題:解：原問題的對偶問題為：23

假設計劃期內甲乙兩種產品各生產噸，設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230用圖解法或單純形法可求得最優(yōu)解(元)即在計劃期內甲產品生產噸，乙產品生產8噸，可以使總利潤達到最大，為元。例１:對偶最優(yōu)解的經濟解釋—影子價格

24假設計劃期內甲乙兩種產品各生產噸，設備每噸產2525

由強對偶定理可知，如果原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且它們的目標函數(shù)值相等，即有：其中是線性規(guī)劃原問題約束條件的右端數(shù)據(jù)向量，它代表各種資源的擁有量。為對偶問題最優(yōu)解，它代表在資源最優(yōu)利用條件下對各種單位資源的估價，這種估計不是資源的市場價格，而是根據(jù)資源在生產中所作出的貢獻（如創(chuàng)造利潤，產值等）而作出估價，為區(qū)別起見，稱之為影子價格(shadowprice)。26由強對偶定理可知，如果原問題有最優(yōu)解，那么對偶問題也

影子價格的大小客觀地反映了各種不同資源在系統(tǒng)內的稀缺程度。如果第i種資源供大于求，即在達到最優(yōu)解時，該種資源沒有用完，或松弛變量，由互補松弛定理，在對偶最優(yōu)解中，第i種資源的影子價格。反之如果第i種資源的影子價格，那么由互補松弛定理，原問題的第i個約束為嚴格等式，即，這表明第i種資源已經用完，成為稀缺資源。

資源的影子價格同時也是一種機會成本,在市場經濟的條件下,當某種資源的市場價格低于影子價格時,企業(yè)應買進這種資源用于擴大生產;相反當某種資源的市場價格高于影子價格時,企業(yè)應賣出這種資源。隨著資源的買進賣出,企業(yè)資源的影子價格也將隨之發(fā)生變化,一直到影子價格與市場價格保持同等水平時,才處于平衡狀態(tài)。

27影子價格的大小客觀地反映了各種不同資源在系統(tǒng)內的稀缺程度設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230例１:對偶最優(yōu)解其中為設備A的影子價格，在資源最優(yōu)利用的條件下，設備A每增加一個單位臺時，可以使總利潤增加元。若設備Ａ可供臺時數(shù)＝３７，則28設備每噸產品的加工臺時可供臺時數(shù)甲乙A3436利潤（對偶單純形法

單純形法是以保持原問題可行為條件，即不論進行怎樣的基變換，常數(shù)列必須保持非負。利用對偶問題的對稱性，我們從另一個角度來考慮求解原問題最優(yōu)解的方法，這種方法以保持對偶問題可行為條件，即不論進行何種基變換，必須保持所有的檢驗數(shù)非負，同時取消原問題必須可行的要求，即取消常數(shù)列的非負限制，通過基變換使原問題在非可行解的基礎上逐步轉換成基本可行解，一旦原問題的基本解可行，則該基本可行解也就是最優(yōu)解，這就是對偶單純形法的基本思想。單純形法：可行性→最優(yōu)性對偶單純形法：最優(yōu)性→可行性

29對偶單純形法單純形法是以保持原問題可行為條件，即不論進行例6求解下列線性規(guī)劃

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2,x3≥0解

minz=5x1+2x2+6x32x1+4x2+8x3-x4=244x1+x2+4x3-x5=8x1、x2,x3,x4,x5≥0

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2,x3,x4,x5≥030例6求解下列線性規(guī)劃解30Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-80031Cj52600bCBXBx1x2x3x4x50x4-2[-4

對偶單純形法基變換的次序和一般單純形法不同:一般單純形法首先由最大減少原則確定換入變量,然而用最小比值原則確定換出變量。

對偶單純形法則是先將具有負分量的基變量取出,作為換出變量,然后確定某個非基變量作為換入變量。其變換目的是在保持對偶問題可行性的前提下,使原問題的基本解向可行解靠攏。32對偶單純形法基變換的次序和一般單純形法不同:32對偶單純形法的計算步驟如下:（4）以為主元進行旋轉變換，得新的單純形表，返回（2）。

（2）確定換出變量根據(jù)，確定基變量作為換出變量。檢驗所在行各元素若所有,則無可行解，停止計算。否則轉入(３).（3）確定換入變量按最大比值原則，若確定非基變量為換入變量。(1)根據(jù)原始線性規(guī)劃,列出初始單純形表,檢查b列數(shù)字,若b列數(shù)字全部非負,則已經求得最優(yōu)解,停止計算。若b列中至少有一個負分量,則轉入(2).33對偶單純形法的計算步驟如下:（4）以為主元進行旋轉變換例6用對偶單純形法求解下列線性規(guī)劃

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2,x3≥0解將問題改寫成如下形式

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2,x3,x4,x5≥0顯然,p4、p5可以構成現(xiàn)成的單位基,此時,非基變量在目標函數(shù)中的系數(shù)全為負數(shù),因此p4、p5構成的就是初始正則基。34例6用對偶單純形法求解下列線性規(guī)劃解將問題改寫成如下Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-800-2x21/212-1/4060x5-7/20[-2]-1/41-24021/20-120θ4/(-7/2)02/-2(1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/211/2001/40-3235Cj52600bCBXBx1x2x3x4x50x4-2[-4最后一個單純形表中,已得到一個可行的正則解,因而得到問題的最優(yōu)解為X*=(0,4,1)T最優(yōu)值為z*=14(1)對于形如minz=CX,AX≥b,X≥0,且C≥0的線性規(guī)劃問題。因為將其改寫為max(－z)=－CX,－AX+XS=－b,X≥0,則立即可以得到初始正則解;

(2)在靈敏度分析中,有時需要用對偶單純形法,可使問題的處理簡化。對偶單純形法在以下情況下較為方便。36最后一個單純形表中,已得到一個可行的正則解,因而得到問題的最例7用對偶單純形法求解解：先化為標準型

對偶單純形允許約束方程右端為負，因此可將方程2，3兩端同乘-1，可得含單位矩陣的標準型：37例7用對偶單純形法求解解：先化為標準型37據(jù)此列出初始單純形表,并施行對偶單純形法迭代步驟如下:5/47/4000-1/41/40102x2

2-1/4-3/40014x1

35/43/41004x3

02/30007/3-1/30011/310/3x2

21/3100-4/3-16/3x4

0101018x3

000023100-3-1-10x5

00101-1-2x4

00013218x3

0x5

x4

x3

x2

x1

bXB

CB

00023C可得最優(yōu)解38據(jù)此列出初始單純形表,并施行對偶單純形法迭代步驟如下:5/例8用對偶單純形法求解下列線性規(guī)劃

minz=x1+2x2x1+x2

≤42x1+3x2≥18x1、x2≥0解將問題改寫成如下形式

minz=x1+2x2x1+x2+x3=4－2x1－3x2+x4=－18x1、x2,x3,x4≥0顯然,p3、p4可以構成現(xiàn)成的單位基,此時,非基變量在目標函數(shù)中的系數(shù)全為負數(shù),因此p3、p4構成的就是初始z正則基。39例8用對偶單純形法求解下列線性規(guī)劃解將問題改寫成如下靈敏度分析線性規(guī)劃問題所對應的數(shù)據(jù)集合Ａ,b,Ｃ常常是通過預測或估計所得到的統(tǒng)計數(shù)據(jù),在實際使用中,不免會有一定的誤差。而且隨著市場環(huán)境,工藝條件和資源數(shù)量的改變,這些數(shù)據(jù)完全可能發(fā)生變化。

因此有必要來分析一下當這些數(shù)據(jù)發(fā)生波動時,對目前的最優(yōu)解,最優(yōu)值或者最優(yōu)基會產生什么影響,這就是所謂的靈敏度分析。

40靈敏度分析線性規(guī)劃問題所對應的數(shù)據(jù)集合Ａ,b,Ｃ常靈敏度分析主要討論如下二類問題:數(shù)據(jù)集合在什么范圍內波動將不影響最優(yōu)解或最優(yōu)基？

若最優(yōu)解發(fā)生變化,應如何找到新的最優(yōu)解。CC1

C2

…Cn

CB

XB

bx1

x2

…xn

CB1

XB1

B-1bB-1A=B-1(P1，P2，…，Pn)CB2

XB2

::CBm

XBm

C-CBTB-1A列出標準型線性規(guī)劃問題最優(yōu)單純形表:41靈敏度分析主要討論如下二類問題:CC1C2…CnCB價值向量C的改變

當價值向量由時,檢驗行應修改為:目標函數(shù)值應為。只要非基變量檢驗數(shù)那么原最優(yōu)解仍然為最優(yōu)。至于目標函數(shù)值是否改變,取決于分別就價值系數(shù)對應非基變量或基變量加以討論:42價值向量C的改變當價值向量由若是非基變量的價值系數(shù)，為其改變量，在最優(yōu)表中檢驗數(shù)發(fā)生變化。

若超出范圍，那么，當前解已不是最優(yōu)解。此時以修改后的最優(yōu)單純形表出發(fā)，進行單純形迭代，直至求出新的最優(yōu)解。

由只要即就可以保持現(xiàn)行最優(yōu)解仍為最優(yōu)。

43若是非基變量的價值系數(shù)，為其改變量，在最優(yōu)表中檢驗數(shù)

若是某基變量的價值系數(shù)，為改變量，在最優(yōu)表中所有的非基變量檢驗數(shù)均發(fā)生了變化.

由上式可得到一個不等式組，求解該不等式組就可得到價值系數(shù)的可變動范圍。由，只要檢驗數(shù)：

或則最優(yōu)解仍然保持為最優(yōu).

44若是某基變量的價值系數(shù)，為改變量，在最優(yōu)表中所有的例7、某工廠用甲乙兩種原料生產A,B,C,D四種產品,每種產品的利潤,現(xiàn)有原料數(shù)及每種產品消耗原料定額如表所示:

原料（公斤）產品（萬件）供應量ABCD甲乙321040021/2183利潤（萬元/萬件）985019問應該怎樣組織生產,才能使總利潤最大,若產品Ａ或Ｃ的利潤產生波動,波動范圍多大時,原最優(yōu)解保持不變？解：設生產Ａ，Ｂ，Ｃ，Ｄ四種產品各萬件，則此問題的線性規(guī)劃模型為：45例7、某工廠用甲乙兩種原料生產A,B,C,D四種產品,每種產標準化,引入松弛變量x5,x6,,

利用單純形表求解:42/30013/310/324/3012/3-10/3-1/2-1/310-1/64/321x4x3-19-500-20-23102612/301/21/3-5/30011/401/213/2x1x3-9-50-9-80-13/20251-3203/21-50011/401/233/2x5x30-50-9-8-50-19009/53/232104100021/201183x5x600x1x2x3x4x5x6bXBCBθ-9-8-50-1900C即最優(yōu)生產方案是生產Ｃ產品1萬件,Ｄ產品2萬件,不生產Ａ,Ｂ兩種產品?？傻米畲罄麧櫈?8萬元。46標準化,引入松弛變量x5,x6,,利用單純形表求解:C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z8842/30013/310/3最優(yōu)表:原最優(yōu)解不變，最優(yōu)利潤值（萬元）也不變。(1)若有改變量。因為為非基變量，由推得即或時47C-9-8-50-C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z8842/30013/310/3最優(yōu)表:(２)若有改變量。因為為基變量，由推得即當或時原最優(yōu)解不變，最優(yōu)利潤值萬元48C-9-8-50-右端項向量b的改變

當右端項向量時，改變的是表中右端常數(shù)列。此時基變量，目標函數(shù)值。而檢驗行的檢驗向量保持不變。

若，可用對偶單純形法再次進行迭代，直到求得新最優(yōu)解。

為了使B可行，只要或49右端項向量b的改變當右端項向量時，改變的是表例8、在例7中,若想增加甲種原料,問增加多少時原最優(yōu)基不變？

解：設甲種原料的改變量為,則由即

最優(yōu)目標函數(shù)值(萬元)由此可以推得，即當時，原最優(yōu)基不變。此時最優(yōu)解或50例8、在例7中,若想增加甲種原料,問增加多少時原最優(yōu)基不變？約束矩陣A的改變

假設原線性規(guī)劃問題有一個最優(yōu)解其中Ｂ為最優(yōu)基，

約束矩陣A的改變可能導致不同的最優(yōu)解和最優(yōu)基.以下只涉及兩種較簡單的情形:

增加一個變量,

增加一個約束條件。51約束矩陣A的改變假設原線性規(guī)劃問題約束矩陣A的改變可

增加一個變量增加一個新變量，對應的價值系數(shù)為，對應的系數(shù)列向量為，可得新的線性規(guī)劃問題：設，則

為新問題的一個可行解。因此可在此基礎上開始單純形法，求新的最優(yōu)解。如果，則，是新問題的最優(yōu)解。否則以為換入變量進行基變換，繼續(xù)使用單純形算法為新的線性規(guī)劃尋求一個最優(yōu)解。52增加一個變量增加一個新變量，對應的價值系數(shù)為，增加一個約束

如果加入一個新的約束條件，不妨假設此約束條件為不等式形式，即

在附加不等式約束左端加上一個松弛變量

,

新的線性規(guī)劃變成

53增加一個約束如果加入一個新的約束條件，不妨假設此約束條件由此可以在原來最優(yōu)基Ｂ的基礎上定義一個新的基,

是非奇異矩陣，得到新問題的一個基本解在原最優(yōu)解基礎上對新問題作初等行變換,使基變量對應的系數(shù)列向量為單位矩陣,該基本解不一定是可行解,但是由于Ｂ是原線性規(guī)劃問題的最優(yōu)基,所以能保證該線性規(guī)劃的對偶規(guī)劃是可行的。54由此可以在原來最優(yōu)基Ｂ的基礎上定義一個新的基,是非奇異結論:如果由新基定義的基本解

是非負的。那么該基本解就是有附加約束條件的新線性規(guī)劃問題的最優(yōu)解。不滿足非負條件。那么至少有一個基變量小于零,此時可用對偶單純形法求出新問題的最優(yōu)解。55結論:如果由新基定義的基本解55解:(1)設生產Ｅ產品x7萬件,1萬件E產品的利潤為c7萬元,則數(shù)學模型變?yōu)?例9、在例7中,若考慮生產另一種產品Ｅ,已知每生產1萬件Ｅ產品要消耗甲原料3公斤,乙原料1公斤,那么,Ｅ產品的每萬件利潤為多少時才有利于該種產品投產？若假設該工廠又增加了用電量不超過9千瓦的限制,已知生產Ａ,Ｂ,Ｃ,Ｄ四種產品各1萬件分別耗電4,3,5,2千瓦,問此約束是否改變了原最優(yōu)決策方案？56解:(1)設生產Ｅ產品x7萬件,1萬件E產品的利潤為c7萬元

已知是原問題的最優(yōu)解,若令,則是現(xiàn)問題的一個可行解,但未必是最優(yōu)解。

若要Ｅ產品投產，即，則其檢驗數(shù),即

得每萬件E產品利潤萬元時，有利于生產E產品。57已知是原問題的最優(yōu)解,若令,

由此可的新的最優(yōu)解,即最優(yōu)生產方案為生產萬件Ｄ產品和件Ｅ產品,總利潤為萬元。C

-9-8-50-1900-17θ

CB

XB

bx1x2x3x4x5x6x7-19X4224/3012/3-10/3-4/3-50x31-1/2-1/310-1/64/35/6

42/30013/310/3-2/3-19X418/56/54/58/512/5-6/50-17x76/5-3/5-2/56/50-1/58/51

18/52/54/5021/522/50例如當萬元時，代入原線性規(guī)劃的最優(yōu)單純形表，得增加新變量的單純形表，其中58由此可的新的最優(yōu)解,即最優(yōu)生產方案(２)假設生產Ａ,Ｂ,Ｃ,Ｄ四種產品各1萬件分別耗電4,3,5,2千瓦,工廠又增加了用電量不超過9千瓦的限制,則相當于原問題約束方程組增加了一個約束方程

增加松弛變量，得

利用原線性規(guī)劃最優(yōu)單純形表，增加一行和一列得一張新表，作初等行變換，使基變量對應的系數(shù)列向量為單位矩陣，若變換結果使基變量取了負值，則對應的基不是可行基，要用對偶單純形法進行了基變換，并求得最優(yōu)解，否則變換結果已為最優(yōu)解。59(２)假設生產Ａ,Ｂ,Ｃ,Ｄ四種產品各1萬件分別耗電4,3-20100-2-52-1/34/3001-1-4/34/34/3-10/30104-16/32/3X4x3x5

-19-50010-1/20025/2-104/3-1/601-1/3-1/210-10/32/3104/322X4x3x7

-19-50010025348x7

004/3-1/601-1/3-1/21x3-500-10/32/3104/322X4-1926/310/30001877/3010/313/3002/34010/313/3002/34x7x6x5x4x3x2x1bXB

CB

θ000-19-50-8-9c可見增加用電約束以后，最優(yōu)生產方案是萬件Ｃ產品，萬件Ｄ產品，總利潤為萬元，比原問題的最大利潤減少。60-20100-2-52-1/34/3001-1-4/34/3編輯本段現(xiàn)代意義的“策劃”現(xiàn)代意義的“策劃”可以理解為借助一定的信息素材，為達到特定的目的、目標而進行設計、策劃，以為具體的可操作性行為提供創(chuàng)意、思路、方法與對策。策劃就是一種策略、籌劃、謀劃或者計劃、打算、它是為個人、企業(yè)、組織機構為了達到一定的目的，充分調查市場環(huán)境、以及相關聯(lián)的環(huán)境的基礎之上，遵循一定的方法或者規(guī)則對未來即將發(fā)生的事情，進行系統(tǒng)、周密、科學地預測并制定科學的可行性的策劃方案，同時在發(fā)展中不斷地調整以適應環(huán)境的變化，從而制定切合實際情況的科學的方案就叫做策劃。綜上所述策劃有以下幾個主要的特點：第一、策劃的本質一種思維智慧的結晶。第二、策劃具有目的性，不論什么策劃方案，都是有一定的目的，不然策劃就沒意義了。第三、策劃具有前瞻性、預測性，策劃是人們在一定思考以及調查的基礎之上進行的科學的預測、因此具有一定的前瞻性。第四、策劃具有一定的不確定性、風險性。策劃既然是一種預測或者籌劃就一定具有不確定性或者風險。第五、策劃具有一定的科學性。策劃是人們在調查的基礎之上、進行總結、科學的預測，策劃不是一種突然的想法、或者突發(fā)奇想的方法、它是建立在科學的基礎之上進行的預測、籌劃。第六、策劃具有科學的創(chuàng)意，策劃是人們思維智慧的結晶，策劃是一種思維的革新、具有創(chuàng)意的策劃，才是真正的策劃，策劃的靈魂就是創(chuàng)意。第七、策劃具有可操作性，這是策劃方案的前提，如果一個策劃連最基本的可操作性就沒有，那么這個策劃方案，再有創(chuàng)意、再好也是一個失敗的策劃方案。發(fā)展觀念：從用戶和市場需求入手，逐步認識、掌握及運用行業(yè)發(fā)展規(guī)律，推行“知本運營(人力資源)戰(zhàn)略”、“資本運營戰(zhàn)略”、“資訊運營戰(zhàn)略”及“創(chuàng)新+速度”戰(zhàn)略，高速成長，非線性發(fā)展。經營策略：通過用戶評判、以提高用戶為主導來樹立企業(yè)品牌；通過對外拓展，標準化運營模式，大幅度擴展、鞏固設計市場份額；通過開放式、多方位的合作形式，建立、豐富工作室的人力資源隊伍。工作風氣：寬厚、專業(yè)、創(chuàng)新、高效。營銷策劃的方法營銷策劃是對營銷活動的設計與計劃，而營銷活動是企業(yè)的市場開拓活動，它貫穿于企業(yè)經營管理過程。因此，凡是涉及市場開拓的企業(yè)經營活動都是營銷策劃的內容。1．點子方法什么是點子？從現(xiàn)代營銷角度來說，點子是指有豐富市場經驗的營銷策劃人員經過深思熟慮，為營銷方案的具體實施所想出的主意與方法。2．創(chuàng)意方法創(chuàng)意是指在市場調研前提下，以市場策略為依據(jù)，經過獨特的心智訓練后，有意識地運用新的方法組合舊的要素的過程。3．謀略方法謀略是關于某項事物、事情的決策和領導實施方案。編輯本段非策劃的含義非策劃是相對于策劃提出的一個策劃思想.著名策劃人蘭何水生認為，策劃人不能把自己禁錮在策劃里頭尋死覓活，策劃人的高境界應該是超脫，超脫于策劃理論技能之外，利用其他專業(yè)行業(yè)的知識解決策劃內部的問題及與其他策劃的較量，好比說，策劃是正派武功，非策劃是邪門歪道，策劃人首先是敢于突破創(chuàng)新的人，沾一點、學一點甚至全用邪門歪道解決策劃問題首先使得你看問題的視角和解決問題的方法更寬廣，此外你的非策劃必然讓對手琢磨不透更易取勝。編輯本段概念及延伸概述有人問什么是策劃。做某件事的邏輯順序就是策劃，也稱作創(chuàng)意策劃。簡單的策劃，也可以說是想法、創(chuàng)意、點子。比如某人要喝水，先要打井，要先勘測哪塊地方打下去會有好喝的水出來，要找好將要約好來打井的朋友，要找鏟子，大家某時間地點集合一起去挖井，把這些做事的過程邏輯寫下來以后就是一個策劃。策劃是書面語言（或圖表）就是在這些書面語言（圖表）中闡述出一個實現(xiàn)某件事情的理論邏輯過程，有人說，有好的想法，在心里就好，何必要寫下來，到時把這個想法，用原話即時說出來給必要的人聽就是了。用原話與書面的對比效果：原話需要你們雙方親身某個場合，嘴巴交流，需要占用雙方的時間，表達思想需要各種技巧，你的想法在這些條件下，能否被對方記住，你離開了，這些思想交流的過程就消失了，這些都是原話的弊端，如果你真的想讓對方看到你的思想，你就必須要寫下來，把這些思想放在了紙上，既可以方便你根據(jù)所得的資料即時改善想法，也不用你每個必要的人面前都占用時間去賣力的表達一遍，寫在紙上也可以方便傳播你的想法，別人可以在任何方便的時候，看到你的想法，這時你的想法就是策劃了。策劃的分類策劃根據(jù)公司的職業(yè)需要有分成游戲策劃，市場策劃，營銷策劃，廣告策劃，產品策劃，節(jié)目策劃，電影策劃，房地產策劃等等。雖然策劃的職業(yè)不同，需要了解或找尋的知識資料也不同，但是策劃要做的事情的方式都是一樣的，無論從事哪方面的專職策劃只要能掌握的策劃邏輯就好，都不需要深入去學習相關行業(yè)的專業(yè)技能，比如做網絡游戲策劃，我們只要知道程序可以這么做到就好，不用告訴程序員程序要怎么樣去寫，所以策劃作為一個工作的門檻是很低的，你有思想有好的點子會寫字或畫圖表達出來就可以成為策劃。當然如果能全面的了解各方面的知識是最好了，特別是了解營銷方面的知識會對策劃的聯(lián)想創(chuàng)意方面很有幫助。策劃的啟蒙策劃最初就來自于我們小時候的隨著年齡而不停止的夢想，后來形成了很多想法，某個想法靈機閃現(xiàn)脫穎而出，它沖動著一時占據(jù)了你的思維，最后你把這個靈機閃現(xiàn)的想法寫下它的實現(xiàn)的邏輯過程就是策劃，所以好的策劃一開始來自你的好的想法，常常好的想法來自你現(xiàn)實生活中的一些東西而形成產生的靈機想象，抓住靈機想象，不斷調查得到資料，來務實的分析清楚即將去做某件事情的每一個細節(jié)過程得失，可能造成的問題與結果，在策劃中根據(jù)其中各種問題的來提出解決方案，并分析其可行性。比如上面，策劃中要分析清楚，要喝水是否就一定要打井呢，有沒其他更好的方法，分析種種原因狀況以后，再下定要做打井這件事情的決心，有了決心開始做事；打在哪里好？是否需要其他什么證照辦理，是否需要與某些涉及到的人或者事物協(xié)調好才能打井？確定無誤了，找朋友幫忙或者請工人來打井……所以讓人看明白為什么要這么去做這件事情，就是策劃要做的事情。精品系列課件文檔本文檔下載后可以修改編輯，歡迎下載收藏。61編輯本段現(xiàn)代意義的“策劃”精品系列課件文檔本文檔下載后可以修對偶規(guī)劃與靈敏度分析

對偶線性規(guī)劃對偶定理對偶單純形法靈敏度分析62對偶規(guī)劃與靈敏度分析對偶線性規(guī)劃1

對偶理論是線性規(guī)劃的重要內容之一。對應于每個線性規(guī)劃問題都伴生一個相應的線性規(guī)劃問題。

原問題和對偶問題緊密關聯(lián),它們不但有相同的數(shù)據(jù)集合,相同的最優(yōu)目標函數(shù)值,而且在求得一個線性規(guī)劃的最優(yōu)解的同時,也同步得到對偶線性規(guī)劃的最優(yōu)解。由對偶問題引伸出來的對偶解還有著重要的經濟意義,是研究經濟學的重要概念和工具之一。

63對偶理論是線性規(guī)劃的重要內容之一。對應于每個線性規(guī)劃對偶問題的提出例1、某工廠生產甲,乙兩種產品,這兩種產品需要在A,B,C三種不同設備上加工。每種甲、乙產品在不同設備上加工所需的臺時,它們銷售后所能獲得的利潤,以及這三種設備在計劃期內能提供的有限臺時數(shù)均列于表。試問如何安排生產計劃,即甲,乙兩種產品各生產多少噸,可使該廠所獲得利潤達到最大。對偶線性規(guī)劃設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）323064對偶問題的提出對偶線性規(guī)劃設備每噸產品的加工臺時可供臺時數(shù)

假設計劃期內甲乙兩種產品各生產噸，設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230用圖解法或單純形法可求得最優(yōu)解(元)即在計劃期內甲產品生產噸，乙產品生產8噸，可以使總利潤達到最大，為元。65假設計劃期內甲乙兩種產品各生產噸，設備每噸產

現(xiàn)在從另一個角度來考慮該工廠的生產問題:假設該廠的決策者打算不再自己生產甲,乙產品,而是把各種設備的有限臺時數(shù)租讓給其他工廠使用,這時工廠的決策者應該如何確定各種設備的租價。設分別為設備A，B，C每臺時的租價，約束條件：把設備租出去所獲得的租金不應低于利用這些設備自行生產所獲得的利潤目標函數(shù)：所獲租金總額盡量少．66現(xiàn)在從另一個角度來考慮該工廠的生產問題:設由此可得兩個對稱的線性規(guī)劃：67由此可得兩個對稱的線性規(guī)劃：6矩陣形式：68矩陣形式：7可以得到另一個線性規(guī)劃:稱之為原線性規(guī)劃問題的對偶問題,

對偶線性規(guī)劃考慮如下具有不等式約束的線性規(guī)劃問題69對偶線性規(guī)劃考慮如下具有不等式約束的線性規(guī)劃問題870971107211

若令線性規(guī)劃標準型的對偶規(guī)劃為:

線性規(guī)劃問題標準型的對偶問題考慮一個標準形式的線性規(guī)劃問題由于任何一個等式約束都可以用兩個不等式約束等價地表示,所以標準形線性規(guī)劃問題可等價表示為:它的對偶規(guī)劃為:73若令線性規(guī)劃標準型對偶線性規(guī)劃的求法

從任何一個線性規(guī)劃出發(fā),都可以求出相應的對偶規(guī)劃,在實際求解過程中,通常不通過求標準型,而是利用如下反映原始問題與對偶問題對應關系的原始─對偶表:

目標函數(shù)變量系數(shù)約束條件右端項約束條件右端項目標函數(shù)變量系數(shù)

約束條件個數(shù):n個變量個數(shù):n個變量個數(shù):m個約束條件個數(shù):m個目標函數(shù)minW目標函數(shù)maxZ對偶問題(或原問題)原問題(或對偶問題)74對偶線性規(guī)劃的求法目標函數(shù)變量系數(shù)約束條件右端項約束條件個數(shù)解:對偶規(guī)劃:例2寫出下列線性規(guī)劃的對偶問題75解:對偶規(guī)劃:例2寫出下列線性規(guī)劃的對偶問題14例3寫出下列線性規(guī)劃的對偶問題解:上述問題的對偶規(guī)劃:76例3寫出下列線性規(guī)劃的對偶問題解:上述問題的對偶規(guī)劃:15

本節(jié)討論幾條重要的對偶定理,這些定理揭示了原始問題的解和對偶問題的解之間的基本關系。定理1:(對合性)對偶問題的對偶是原問題。證明:設原問題為對偶問題為改寫對偶問題為對偶問題的對偶為對偶定理77本節(jié)討論幾條重要的對偶定理,這些定理揭示了原始問題的解和

定理2:弱對偶定理

若是原(極小化)問題的可行解,是對偶(極大化)問題的可行解,那么

證明：因為是對偶問題的可行解，所以滿足約束條件又因為是原問題的可行解，可得，,所以。注:原(極小化)問題的最優(yōu)目標函數(shù)值以對偶問題任一可行解的目標函數(shù)值為下界。對偶(極大化)問題的最優(yōu)目標函數(shù)值以原問題任一可行解的目標函數(shù)值為上界。

推論1:如果原問題沒有下界(即minZ→－∞),則對偶問題不可行。如果對偶問題沒有上界(即maxW→＋∞),則原問題不可行。

若原問題與對偶問題之一無界,則另一個無可行解。78定理2:弱對偶定理證明：因為是對偶問題的可行解，所證明:由弱對偶定理,對于原始問題的所有可行解,都有因此是原問題的最優(yōu)解。同理,對于對偶問題的所有可行解,都有所以是對偶問題的最優(yōu)解。推論2：最優(yōu)性定理

若是原問題的可行解，是對偶問題的可行解，而且兩者的目標函數(shù)值相等，即，則和分別是原問題和對偶問題的最優(yōu)解。79證明:由弱對偶定理,對于原始問題的所有可行解,都有證明:設是原問題(min)的最優(yōu)解,則對應的基Ｂ必有。若定義,則,

因此為對偶問題的可行解,而且,由最優(yōu)性定理,是對偶問題的最優(yōu)解。

定理3:強對偶定理如果原問題(min)與對偶問題(max)之一有最優(yōu)解,那么另一個也有最優(yōu)解,而且目標函數(shù)值相等。80證明:設是原問題(min)的最優(yōu)解,則對應的基Ｂ必有證明:設滿足原問題(min)的最優(yōu)性條件,則對應的基Ｂ必有。若定義,則,

因此為對偶問題的基本可行解。

定理4:設滿足原問題(min)的最優(yōu)性條件的一個基本解,則其對應的線性規(guī)劃問題(min)的檢驗數(shù)對應對偶問題的一個基本可行解。81證明:設滿足原問題(min)的最優(yōu)性條件,則對應的基Ｂ必原問題與對偶問題可能出現(xiàn)的情況(1)兩者都有最優(yōu)解,且最優(yōu)值相等;(2)一個有可行解,但無界,則另一個無可行解;(3)兩者都無可行解。82原問題與對偶問題可能出現(xiàn)的情況21定理5：互補松弛定理

如果分別是原問題(min)和對偶問題（max)的可行解，那么和為最優(yōu)解的充要條件是

通常稱為互補松弛條件。證明：充分性必要性83定理5：互補松弛定理證明：充分性必要性22例5、已知線性規(guī)劃問題:其對偶問題的最優(yōu)解。試用互補松弛定理找出原問題的最優(yōu)解。解：原問題的對偶問題為：由對偶問題最優(yōu)解可知，由互補松弛定理，解方程組所以原問題最優(yōu)解84例5、已知線性規(guī)劃問題:解：原問題的對偶問題為：23

假設計劃期內甲乙兩種產品各生產噸，設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230用圖解法或單純形法可求得最優(yōu)解(元)即在計劃期內甲產品生產噸，乙產品生產8噸，可以使總利潤達到最大，為元。例１:對偶最優(yōu)解的經濟解釋—影子價格

85假設計劃期內甲乙兩種產品各生產噸，設備每噸產8625

由強對偶定理可知，如果原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且它們的目標函數(shù)值相等，即有：其中是線性規(guī)劃原問題約束條件的右端數(shù)據(jù)向量，它代表各種資源的擁有量。為對偶問題最優(yōu)解，它代表在資源最優(yōu)利用條件下對各種單位資源的估價，這種估計不是資源的市場價格，而是根據(jù)資源在生產中所作出的貢獻（如創(chuàng)造利潤，產值等）而作出估價，為區(qū)別起見，稱之為影子價格(shadowprice)。87由強對偶定理可知，如果原問題有最優(yōu)解，那么對偶問題也

影子價格的大小客觀地反映了各種不同資源在系統(tǒng)內的稀缺程度。如果第i種資源供大于求，即在達到最優(yōu)解時，該種資源沒有用完，或松弛變量，由互補松弛定理，在對偶最優(yōu)解中，第i種資源的影子價格。反之如果第i種資源的影子價格，那么由互補松弛定理，原問題的第i個約束為嚴格等式，即，這表明第i種資源已經用完，成為稀缺資源。

資源的影子價格同時也是一種機會成本,在市場經濟的條件下,當某種資源的市場價格低于影子價格時,企業(yè)應買進這種資源用于擴大生產;相反當某種資源的市場價格高于影子價格時,企業(yè)應賣出這種資源。隨著資源的買進賣出,企業(yè)資源的影子價格也將隨之發(fā)生變化,一直到影子價格與市場價格保持同等水平時,才處于平衡狀態(tài)。

88影子價格的大小客觀地反映了各種不同資源在系統(tǒng)內的稀缺程度設備每噸產品的加工臺時可供臺時數(shù)甲乙ABC359448364076利潤（元/噸）3230例１:對偶最優(yōu)解其中為設備A的影子價格，在資源最優(yōu)利用的條件下，設備A每增加一個單位臺時，可以使總利潤增加元。若設備Ａ可供臺時數(shù)＝３７，則89設備每噸產品的加工臺時可供臺時數(shù)甲乙A3436利潤（對偶單純形法

單純形法是以保持原問題可行為條件，即不論進行怎樣的基變換，常數(shù)列必須保持非負。利用對偶問題的對稱性，我們從另一個角度來考慮求解原問題最優(yōu)解的方法，這種方法以保持對偶問題可行為條件，即不論進行何種基變換，必須保持所有的檢驗數(shù)非負，同時取消原問題必須可行的要求，即取消常數(shù)列的非負限制，通過基變換使原問題在非可行解的基礎上逐步轉換成基本可行解，一旦原問題的基本解可行，則該基本可行解也就是最優(yōu)解，這就是對偶單純形法的基本思想。單純形法：可行性→最優(yōu)性對偶單純形法：最優(yōu)性→可行性

90對偶單純形法單純形法是以保持原問題可行為條件，即不論進行例6求解下列線性規(guī)劃

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2,x3≥0解

minz=5x1+2x2+6x32x1+4x2+8x3-x4=244x1+x2+4x3-x5=8x1、x2,x3,x4,x5≥0

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2,x3,x4,x5≥091例6求解下列線性規(guī)劃解30Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-80092Cj52600bCBXBx1x2x3x4x50x4-2[-4

對偶單純形法基變換的次序和一般單純形法不同:一般單純形法首先由最大減少原則確定換入變量,然而用最小比值原則確定換出變量。

對偶單純形法則是先將具有負分量的基變量取出,作為換出變量,然后確定某個非基變量作為換入變量。其變換目的是在保持對偶問題可行性的前提下,使原問題的基本解向可行解靠攏。93對偶單純形法基變換的次序和一般單純形法不同:32對偶單純形法的計算步驟如下:（4）以為主元進行旋轉變換，得新的單純形表，返回（2）。

（2）確定換出變量根據(jù)，確定基變量作為換出變量。檢驗所在行各元素若所有,則無可行解，停止計算。否則轉入(３).（3）確定換入變量按最大比值原則，若確定非基變量為換入變量。(1)根據(jù)原始線性規(guī)劃,列出初始單純形表,檢查b列數(shù)字,若b列數(shù)字全部非負,則已經求得最優(yōu)解,停止計算。若b列中至少有一個負分量,則轉入(2).94對偶單純形法的計算步驟如下:（4）以為主元進行旋轉變換例6用對偶單純形法求解下列線性規(guī)劃

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2,x3≥0解將問題改寫成如下形式

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2,x3,x4,x5≥0顯然,p4、p5可以構成現(xiàn)成的單位基,此時,非基變量在目標函數(shù)中的系數(shù)全為負數(shù),因此p4、p5構成的就是初始正則基。95例6用對偶單純形法求解下列線性規(guī)劃解將問題改寫成如下Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-800-2x21/212-1/4060x5-7/20[-2]-1/41-24021/20-120θ4/(-7/2)02/-2(1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/211/2001/40-3296Cj52600bCBXBx1x2x3x4x50x4-2[-4最后一個單純形表中,已得到一個可行的正則解,因而得到問題的最優(yōu)解為X*=(0,4,1)T最優(yōu)值為z*=14(1)對于形如minz=CX,AX≥b,X≥0,且C≥0的線性規(guī)劃問題。因為將其改寫為max(－z)=－CX,－AX+XS=－b,X≥0,則立即可以得到初始正則解;

(2)在靈敏度分析中,有時需要用對偶單純形法,可使問題的處理簡化。對偶單純形法在以下情況下較為方便。97最后一個單純形表中,已得到一個可行的正則解,因而得到問題的最例7用對偶單純形法求解解：先化為標準型

對偶單純形允許約束方程右端為負，因此可將方程2，3兩端同乘-1，可得含單位矩陣的標準型：98例7用對偶單純形法求解解：先化為標準型37據(jù)此列出初始單純形表,并施行對偶單純形法迭代步驟如下:5/47/4000-1/41/40102x2

2-1/4-3/40014x1

35/43/41004x3

02/30007/3-1/30011/310/3x2

21/3100-4/3-16/3x4

0101018x3

000023100-3-1-10x5

00101-1-2x4

00013218x3

0x5

x4

x3

x2

x1

bXB

CB

00023C可得最優(yōu)解99據(jù)此列出初始單純形表,并施行對偶單純形法迭代步驟如下:5/例8用對偶單純形法求解下列線性規(guī)劃

minz=x1+2x2x1+x2

≤42x1+3x2≥18x1、x2≥0解將問題改寫成如下形式

minz=x1+2x2x1+x2+x3=4－2x1－3x2+x4=－18x1、x2,x3,x4≥0顯然,p3、p4可以構成現(xiàn)成的單位基,此時,非基變量在目標函數(shù)中的系數(shù)全為負數(shù),因此p3、p4構成的就是初始z正則基。100例8用對偶單純形法求解下列線性規(guī)劃解將問題改寫成如下靈敏度分析線性規(guī)劃問題所對應的數(shù)據(jù)集合Ａ,b,Ｃ常常是通過預測或估計所得到的統(tǒng)計數(shù)據(jù),在實際使用中,不免會有一定的誤差。而且隨著市場環(huán)境,工藝條件和資源數(shù)量的改變,這些數(shù)據(jù)完全可能發(fā)生變化。

因此有必要來分析一下當這些數(shù)據(jù)發(fā)生波動時,對目前的最優(yōu)解,最優(yōu)值或者最優(yōu)基會產生什么影響,這就是所謂的靈敏度分析。

101靈敏度分析線性規(guī)劃問題所對應的數(shù)據(jù)集合Ａ,b,Ｃ常靈敏度分析主要討論如下二類問題:數(shù)據(jù)集合在什么范圍內波動將不影響最優(yōu)解或最優(yōu)基？

若最優(yōu)解發(fā)生變化,應如何找到新的最優(yōu)解。CC1

C2

…Cn

CB

XB

bx1

x2

…xn

CB1

XB1

B-1bB-1A=B-1(P1，P2，…，Pn)CB2

XB2

::CBm

XBm

C-CBTB-1A列出標準型線性規(guī)劃問題最優(yōu)單純形表:102靈敏度分析主要討論如下二類問題:CC1C2…CnCB價值向量C的改變

當價值向量由時,檢驗行應修改為:目標函數(shù)值應為。只要非基變量檢驗數(shù)那么原最優(yōu)解仍然為最優(yōu)。至于目標函數(shù)值是否改變,取決于分別就價值系數(shù)對應非基變量或基變量加以討論:103價值向量C的改變當價值向量由若是非基變量的價值系數(shù)，為其改變量，在最優(yōu)表中檢驗數(shù)發(fā)生變化。

若超出范圍，那么，當前解已不是最優(yōu)解。此時以修改后的最優(yōu)單純形表出發(fā)，進行單純形迭代，直至求出新的最優(yōu)解。

由只要即就可以保持現(xiàn)行最優(yōu)解仍為最優(yōu)。

104若是非基變量的價值系數(shù)，為其改變量，在最優(yōu)表中檢驗數(shù)

若是某基變量的價值系數(shù)，為改變量，在最優(yōu)表中所有的非基變量檢驗數(shù)均發(fā)生了變化.

由上式可得到一個不等式組，求解該不等式組就可得到價值系數(shù)的可變動范圍。由，只要檢驗數(shù)：

或則最優(yōu)解仍然保持為最優(yōu).

105若是某基變量的價值系數(shù)，為改變量，在最優(yōu)表中所有的例7、某工廠用甲乙兩種原料生產A,B,C,D四種產品,每種產品的利潤,現(xiàn)有原料數(shù)及每種產品消耗原料定額如表所示:

原料（公斤）產品（萬件）供應量ABCD甲乙321040021/2183利潤（萬元/萬件）985019問應該怎樣組織生產,才能使總利潤最大,若產品Ａ或Ｃ的利潤產生波動,波動范圍多大時,原最優(yōu)解保持不變？解：設生產Ａ，Ｂ，Ｃ，Ｄ四種產品各萬件，則此問題的線性規(guī)劃模型為：106例7、某工廠用甲乙兩種原料生產A,B,C,D四種產品,每種產標準化,引入松弛變量x5,x6,,

利用單純形表求解:42/30013/310/324/3012/3-10/3-1/2-1/310-1/64/321x4x3-19-500-20-23102612/301/21/3-5/30011/401/213/2x1x3-9-50-9-80-13/20251-3203/21-50011/401/233/2x5x30-50-9-8-50-19009/53/232104100021/201183x5x600x1x2x3x4x5x6bXBCBθ-9-8-50-1900C即最優(yōu)生產方案是生產Ｃ產品1萬件,Ｄ產品2萬件,不生產Ａ,Ｂ兩種產品?？傻米畲罄麧櫈?8萬元。107標準化,引入松弛變量x5,x6,,利用單純形表求解:C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z8842/30013/310/3最優(yōu)表:原最優(yōu)解不變，最優(yōu)利潤值（萬元）也不變。(1)若有改變量。因為為非基變量，由推得即或時108C-9-8-50-C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310