第二講對(duì)偶理論與靈敏度分析第1頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月

【例1】某企業(yè)用四種資源生產(chǎn)三種產(chǎn)品，工藝系數(shù)、資源限量及價(jià)值系數(shù)如下表：

建立總收益最大的數(shù)學(xué)模型。

產(chǎn)品資源ABC資源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550單件產(chǎn)品利潤(rùn)1008070線性規(guī)劃的對(duì)偶模型DualmodelofLP線性規(guī)劃的對(duì)偶模型第2頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【解】設(shè)x1，x2，x3分別為產(chǎn)品A，B，C的產(chǎn)量，則線性規(guī)劃數(shù)學(xué)模型為：

現(xiàn)在從另一個(gè)角度來(lái)考慮企業(yè)的決策問(wèn)題。假如企業(yè)不考慮自己生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源標(biāo)價(jià)出售，

問(wèn)題：決策者應(yīng)怎樣給定資源一個(gè)合理的價(jià)格？線性規(guī)劃的對(duì)偶模型DualmodelofLP第3頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月設(shè)y1，y2，y3及y4分別表示四種資源的單位增值價(jià)格(售價(jià)＝成本＋增值)，總增值最低可用minw=500y1+450y2+300y3+550y4

表示。企業(yè)生產(chǎn)一件產(chǎn)品A用了四種資源的數(shù)量分別是9，5，8和7個(gè)單位，利潤(rùn)是100,企業(yè)出售這些數(shù)量的資源所得的利潤(rùn)不能少于100，即同理，對(duì)產(chǎn)品B和C有線性規(guī)劃的對(duì)偶模型DualmodelofLP第4頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月稱上述線性規(guī)劃模型是前面生產(chǎn)計(jì)劃模型的對(duì)偶線性規(guī)劃模型,這一問(wèn)題稱為對(duì)偶問(wèn)題。生產(chǎn)計(jì)劃的線性規(guī)劃問(wèn)題稱為原始線性規(guī)劃問(wèn)題或原問(wèn)題。價(jià)格不可能小于零，即有yi≥0(i=1,…,4),從而企業(yè)的資源價(jià)格模型為線性規(guī)劃的對(duì)偶模型DualmodelofLP第5頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月注：以上兩問(wèn)題是同一組數(shù)據(jù)參數(shù)，只是位置有所不同，所描述的問(wèn)題實(shí)際上是從兩個(gè)不同的角度去描述。原始線性規(guī)劃問(wèn)題考慮的是充分利用現(xiàn)有資源，以產(chǎn)品數(shù)量和單位產(chǎn)品的利潤(rùn)來(lái)決定企業(yè)的總利潤(rùn)，沒(méi)有考慮資源的價(jià)格，實(shí)際上在構(gòu)成產(chǎn)品的利潤(rùn)中，不同的資源對(duì)利潤(rùn)的貢獻(xiàn)也不同，它是企業(yè)生產(chǎn)過(guò)程中一種隱含的潛在價(jià)值，經(jīng)濟(jì)學(xué)中稱為影子價(jià)格。線性規(guī)劃的對(duì)偶模型DualmodelofLP第6頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月第7頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃問(wèn)題(2.2)就是原線性規(guī)劃問(wèn)題(2.1)的對(duì)偶線性規(guī)劃問(wèn)題，反之，(2.2)的對(duì)偶問(wèn)題就是(2.1)．原問(wèn)題與對(duì)偶問(wèn)題有如下關(guān)系(假設(shè)原問(wèn)題(2.1))：(1)原問(wèn)題的約束個(gè)數(shù)(不含非負(fù)約束)等于對(duì)偶變量的個(gè)數(shù)(2)原問(wèn)題的目標(biāo)函數(shù)系數(shù)對(duì)應(yīng)于對(duì)偶問(wèn)題的右端項(xiàng)(3)原問(wèn)題的右端項(xiàng)對(duì)應(yīng)于對(duì)偶問(wèn)題的目標(biāo)函數(shù)系數(shù)(4)原問(wèn)題的約束矩陣轉(zhuǎn)置就是對(duì)偶問(wèn)題系數(shù)矩陣(5)原問(wèn)題求最大，對(duì)偶問(wèn)題是求最小(6)原問(wèn)題不等式約束符號(hào)為“≤”,對(duì)偶問(wèn)題不等式約束符號(hào)為“≥”線性規(guī)劃的對(duì)偶模型DualmodelofLP第8頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月

【例2】寫出該線性規(guī)劃的對(duì)偶問(wèn)題【解】線性規(guī)劃的對(duì)偶模型DualmodelofLP第9頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃問(wèn)題的規(guī)范形式(或叫對(duì)稱形式)：定義：

目標(biāo)函數(shù)求極大值時(shí)，所有約束條件為≤號(hào)，變量非負(fù)；

目標(biāo)函數(shù)求極小值時(shí)，所有約束條件為≥號(hào)，變量非負(fù)。

注：

(1)線性規(guī)劃規(guī)范形式與標(biāo)準(zhǔn)型是兩種不同形式，但可以相互轉(zhuǎn)換。(2)規(guī)范形式的線性規(guī)劃問(wèn)題的對(duì)偶仍然是規(guī)范形式．線性規(guī)劃的對(duì)偶模型DualmodelofLP第10頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月對(duì)于一般的線性規(guī)劃問(wèn)題：其中為矩陣，為維列向量，為維向量，為維列向量(i=1,2,3;j=1,2)且令，此問(wèn)題可化為線性規(guī)劃的對(duì)偶模型DualmodelofLP第11頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月用分別表示以上四組約束的對(duì)偶問(wèn)題，則原問(wèn)題的對(duì)偶問(wèn)題是第12頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月令，整理得對(duì)偶問(wèn)題為

將原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系列于表2。第13頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月原問(wèn)題(或?qū)ε紗?wèn)題)對(duì)偶問(wèn)題(或原問(wèn)題)

目標(biāo)函數(shù)max目標(biāo)函數(shù)系數(shù)(資源限量)約束條件系數(shù)矩陣A(AT)

目標(biāo)函數(shù)min資源限量(目標(biāo)函數(shù)系數(shù))約束條件系數(shù)矩陣AT(A)變量n個(gè)變量第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量無(wú)約束約束n個(gè)約束第j個(gè)約束為≥第j個(gè)約束為≤第j個(gè)約束為=約束m個(gè)約束第i個(gè)約束≤第i個(gè)約束≥第i個(gè)約束為=變量m個(gè)變量第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量無(wú)約束

表2線性規(guī)劃的對(duì)偶模型DualmodelofLP第14頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【例3】寫出下列線性規(guī)劃的對(duì)偶問(wèn)題

【解】=≥≤≤y1≤0，y2≥0，y3無(wú)約束線性規(guī)劃的對(duì)偶模型DualmodelofLP第15頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月對(duì)偶問(wèn)題是(記為DP)：這里A是m×n矩陣,X是n×1列向量,Y是1×m行向量?！拘再|(zhì)1】

對(duì)稱性:

對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。

設(shè)原問(wèn)題是(記為L(zhǎng)P)：對(duì)偶性質(zhì)Dualproperty對(duì)偶性質(zhì)【性質(zhì)2】

弱對(duì)偶性:

設(shè)X*、Y*分別為L(zhǎng)P(max)與

DP(min)的可行解，則第16頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月對(duì)偶性質(zhì)Dualproperty由這個(gè)性質(zhì)可得到下面幾個(gè)結(jié)論：

(LP)的任一可行解的目標(biāo)值是(DP)的最優(yōu)值下界；(DP)的任一可行解的目標(biāo)是(LP)的最優(yōu)值的上界；

(2)在互為對(duì)偶的兩個(gè)問(wèn)題中，若一個(gè)問(wèn)題可行且具有無(wú)界解，則另一個(gè)問(wèn)題無(wú)可行解；

(3)若原問(wèn)題可行且另一個(gè)問(wèn)題不可行，則原問(wèn)題具有無(wú)界解。

注意:上述結(jié)論(2)及(3)的條件不能少。一個(gè)問(wèn)題無(wú)可行解時(shí)，另一個(gè)問(wèn)題可能有可行解(此時(shí)具有無(wú)界解)也可能無(wú)可行解。第17頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月例如：無(wú)可行解，而對(duì)偶問(wèn)題有可行解，由結(jié)論(3)知必有無(wú)界解。對(duì)偶性質(zhì)Dualproperty第18頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【性質(zhì)3】最優(yōu)準(zhǔn)則定理:

設(shè)X*與Y*分別是(LP)與(DP)的可行解，則X*、Y*是(LP)與(DP)的最優(yōu)解當(dāng)且僅當(dāng)CX*=Y*b.對(duì)偶性質(zhì)Dualproperty【性質(zhì)4】對(duì)偶性：若互為對(duì)偶的兩個(gè)問(wèn)題其中一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且最優(yōu)值相同。另一結(jié)論：若(LP)與(DP)都有可行解，則兩者都有最優(yōu)解，若一個(gè)問(wèn)題無(wú)最優(yōu)解，則另一問(wèn)題也無(wú)最優(yōu)解。【性質(zhì)5】互補(bǔ)松弛定理:

設(shè)X*、Y*分別為(LP)與(DP)的可行解，XS和YS分別是它們的松弛變量的可行解，則X*和Y*是最優(yōu)解當(dāng)且僅當(dāng)YSX*=0和

Y*XS=0第19頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月性質(zhì)5告訴我們已知一個(gè)問(wèn)題的最優(yōu)解時(shí)求另一個(gè)問(wèn)題的最優(yōu)解的方法，即已知Y*求X*或已知X*求Y*。Y*

XS=0和YSX*

=0兩式稱為互補(bǔ)松弛條件。將互補(bǔ)松弛條件寫成下式由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：對(duì)偶性質(zhì)Dualproperty第20頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月(1)當(dāng)yi*>0時(shí)，,反之當(dāng),時(shí)yi*=0；利用上述關(guān)系，建立對(duì)偶問(wèn)題(或原問(wèn)題)的約束線性方程組，方程組的解即為最優(yōu)解。【例4】已知線性規(guī)劃的最優(yōu)解是,求對(duì)偶問(wèn)題的最優(yōu)解。對(duì)偶性質(zhì)Dualproperty第21頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【解】對(duì)偶問(wèn)題是因?yàn)閤1≠0，x2≠0，所以對(duì)偶問(wèn)題的第一、二個(gè)約束的松弛變量等于零，即解此線性方程組得y1=1,y2=1,從而對(duì)偶問(wèn)題的最優(yōu)解為Y=(1，1)，最優(yōu)值w=26。對(duì)偶性質(zhì)Dualproperty第22頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【例5】已知線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解為Y=(0，－2)，求原問(wèn)題的最優(yōu)解?！窘狻繉?duì)偶問(wèn)題是對(duì)偶性質(zhì)Dualproperty第23頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月解方程組得：x1=－5,x3=－1,所以原問(wèn)題的最優(yōu)解為X=(－5，0，－1)T，最優(yōu)值Z=－12。因?yàn)閥2≠0，所以原問(wèn)題第二個(gè)松弛變量=0，由y1=0、y2=2知，松弛變量故x2=0，則原問(wèn)題的約束條件為線性方程組：對(duì)偶性質(zhì)Dualproperty第24頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【例6】證明該線性規(guī)劃無(wú)最優(yōu)解：【證】容易看出X=(4，0，0)是一可行解。對(duì)偶問(wèn)題將三個(gè)約束的兩端分別相加得,而第二個(gè)約束有y2≥1,矛盾，故對(duì)偶問(wèn)題無(wú)可行解，因而原問(wèn)題具有無(wú)界解，即無(wú)最優(yōu)解。對(duì)偶性質(zhì)Dualproperty第25頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【性質(zhì)6】LP(max)的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于DP(min)的一組基本解，其中第j個(gè)決策變量xj的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于(DP)中第j個(gè)松弛變量的解，第i個(gè)松弛變量的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于第i個(gè)對(duì)偶變量yi的解。反之，(DP)的檢驗(yàn)數(shù)(注意：不乘負(fù)號(hào))對(duì)應(yīng)于(LP)的一組基本解。對(duì)偶性質(zhì)Dualproperty注：應(yīng)用性質(zhì)6的前提是線性規(guī)劃為規(guī)范形式，而性質(zhì)1-5則對(duì)所有形式線性規(guī)劃有效。第26頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月根據(jù)對(duì)偶性質(zhì)；可將原問(wèn)題與對(duì)偶問(wèn)題解的對(duì)應(yīng)關(guān)系列表如下：一個(gè)問(wèn)題max另一個(gè)問(wèn)題min有最優(yōu)解有最優(yōu)解性質(zhì)4無(wú)無(wú)最優(yōu)解無(wú)最優(yōu)解性質(zhì)4最優(yōu)無(wú)界解(有可行解)無(wú)可行解性質(zhì)2解無(wú)可行解無(wú)界解(有可行解)應(yīng)用已知最優(yōu)解通過(guò)解方程求最優(yōu)解性質(zhì)5已知檢驗(yàn)數(shù)檢驗(yàn)數(shù)乘以－1求得基本解性質(zhì)6對(duì)偶性質(zhì)Dualproperty第27頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月影子價(jià)格因?yàn)樵瓎?wèn)題和對(duì)偶問(wèn)題的最優(yōu)值相等，將線性規(guī)劃的目標(biāo)函數(shù)表達(dá)成資源的函數(shù)，故有即yi是第i種資源的變化率，說(shuō)明當(dāng)其它資源供應(yīng)量bk(k≠i)不變時(shí)，bi增加一個(gè)單位時(shí)目標(biāo)值Z增加yi個(gè)單位．對(duì)偶性質(zhì)Dualproperty第28頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月正確理解影子價(jià)格，利用影子價(jià)格作下列經(jīng)濟(jì)活動(dòng)分析:調(diào)節(jié)生產(chǎn)規(guī)模．例如，目標(biāo)函數(shù)Z表示利潤(rùn)(或產(chǎn)值)當(dāng)?shù)趇種資源的影子價(jià)格大于零(或高于市場(chǎng)價(jià)格)時(shí)，表示有利可圖，企業(yè)應(yīng)購(gòu)進(jìn)該資源擴(kuò)大生產(chǎn)規(guī)模，當(dāng)影子價(jià)格等于零(或低于市場(chǎng)價(jià)格)，企業(yè)不能增加收益，這時(shí)應(yīng)將資源賣掉或出讓，縮小生產(chǎn)規(guī)模。生產(chǎn)要素對(duì)產(chǎn)出貢獻(xiàn)的分解．通過(guò)影子價(jià)格分析每種資源獲得多少產(chǎn)出．例如，企業(yè)獲得100萬(wàn)元的利潤(rùn)，生產(chǎn)過(guò)程中產(chǎn)品的直接消耗的資源有材料A、材料B、設(shè)備和工時(shí)，這些資源各產(chǎn)生多少利潤(rùn)，由影子價(jià)格可以大致估計(jì)出來(lái)。對(duì)偶性質(zhì)Dualproperty第29頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月由性質(zhì)2.5知，第i個(gè)松弛變量大于零時(shí)第i個(gè)對(duì)偶變量等于零，并不能說(shuō)明該資源在生產(chǎn)過(guò)程中沒(méi)有作出貢獻(xiàn)，只能理解為第i種資源有剩余時(shí)再增加該資源量不能給企業(yè)帶來(lái)利潤(rùn)或產(chǎn)值的增加．影子價(jià)格是企業(yè)生產(chǎn)過(guò)程中資源的一種隱含的潛在價(jià)值，表明單位資源的貢獻(xiàn)，與市場(chǎng)價(jià)格是不同的兩個(gè)概念．同一種資源在不同的企業(yè)、生產(chǎn)不同的產(chǎn)品或在不同時(shí)期影子價(jià)格都不一樣．例如，某種鋼板市場(chǎng)價(jià)格是每噸8000元，一個(gè)企業(yè)用來(lái)生產(chǎn)汽車，另一個(gè)企業(yè)用來(lái)生產(chǎn)空調(diào)外殼，每噸鋼板的產(chǎn)值是不一樣的．對(duì)偶性質(zhì)Dualproperty第30頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月影子價(jià)格是一個(gè)變量．由的含義知影子價(jià)格是一種邊際產(chǎn)出，與bi的基數(shù)有關(guān)，在最優(yōu)基B不變的條件下yi不變，當(dāng)某種資源增加或減少后，最優(yōu)基B可能發(fā)生了變化，這時(shí)yi的值也隨之發(fā)生變化．對(duì)偶性質(zhì)Dualproperty第31頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月

對(duì)偶單純形法對(duì)于任何一個(gè)可行基B,為原問(wèn)題的一個(gè)基可行解，單純形法是從一個(gè)基可行解到另一個(gè)相鄰的基可行解，直到基B滿足

為止。對(duì)偶單純形法DualSimplexMethod單純形法首先化問(wèn)題為標(biāo)準(zhǔn)型：第32頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月對(duì)偶單純形法DualSimplexMethod原始單純形法的思想：

從滿足可行性條件的一個(gè)基可行解(即基B滿足)出發(fā)，經(jīng)過(guò)換基運(yùn)算迭代到另一個(gè)基可行解，直到找到滿足最優(yōu)性條件()的基可行解，這就是原問(wèn)題的最優(yōu)解。－CBB－1bC-CBB－1AλB-1bB-1AXBbX對(duì)于任意基B,對(duì)應(yīng)的單純形表為第33頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月若上表為最優(yōu)單純形表，則下列兩個(gè)式子同時(shí)成立：對(duì)偶單純形法DualSimplexMethod問(wèn)題：可否從滿足條件(2)的基出發(fā)去找原問(wèn)題的最優(yōu)解？對(duì)偶單純形法思想：從滿足條件(2)的基(一般稱為正則基)B出發(fā)，經(jīng)過(guò)換基運(yùn)算到另一個(gè)正則基，即一直保證條件(2)成立，直到找到一個(gè)滿足條件(1)的正則基。－CBB－1bC-CBB－1AλB-1bB-1AXBX第34頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月對(duì)偶單純形法的計(jì)算步驟：(1)將線性規(guī)劃的約束化為等式，找出一個(gè)正則基，即全部檢驗(yàn)數(shù)λj≤0（max）或λj≥0（min）,求出其對(duì)應(yīng)的基本解，當(dāng)基本解可行時(shí)，則達(dá)到最優(yōu)解；若基本解不可行，即有某個(gè)基變量的解bi<0，則進(jìn)行換基計(jì)算；(2)換基計(jì)算(i)先確定出基變量:

l行對(duì)應(yīng)的變量出基；(ii)再選進(jìn)基變量:求最小比值(3)求新的基本解，用初等變換將主元素alk化為l,k列其它元素化為零，得到新的基本解，轉(zhuǎn)到第(1)步重復(fù)運(yùn)算。對(duì)偶單純形法DualSimplexMethod第35頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【例7】用對(duì)偶單純形法求解【解】先將約束不等式化為等式，再兩邊同乘以(－1)，得到x4、x5為基變量，用對(duì)偶單純形法，迭代過(guò)程如表2-7所示。對(duì)偶單純形法DualSimplexMethod第36頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月XBx1x2x3x4x5b表(1)x4x5-1-1[-1]1-141001－5→－3λj41↑300表2-7對(duì)偶單純形法DualSimplexMethod最優(yōu)解：X＝(4，1，0)T；Z=17表(2)x2x51[-2]1013-11015－8→λj3↑0210表(3)x2x101105/2-3/2-1/2-1/21/2－1/214λj0013/25/23/2第37頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月

線性規(guī)劃的靈敏度分析也稱為敏感性分析，它是研究和分析數(shù)據(jù)(cj，bi，aij)的波動(dòng)對(duì)最優(yōu)解的影響程度，主要研究下面兩個(gè)方面：(1)當(dāng)模型中這些數(shù)據(jù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，最優(yōu)解有什么變化，或這些數(shù)據(jù)在什么范圍內(nèi)變化時(shí)，原最優(yōu)解或最優(yōu)基不變；(2)若最優(yōu)解或最優(yōu)基發(fā)生變化后，如何求出新的最優(yōu)基或最優(yōu)解。靈敏度分析靈敏度分析

SensitivityAnalysis第38頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月

設(shè)線性規(guī)劃

其中Am×n，線性規(guī)劃有最優(yōu)解，設(shè)基B為最優(yōu)基，則有靈敏度分析

SensitivityAnalysis求解思路：將變化后的數(shù)據(jù)代入上述公式，看看可行性條件與最優(yōu)性條件是否依然成立：若成立，則還是最優(yōu)解；若不成立，則利用單純形法或?qū)ε紗渭冃畏汕蟪鲎兓蟮淖顑?yōu)解。第39頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月價(jià)值系數(shù)cj的變化分析為使最優(yōu)解不變，求cj的變化范圍靈敏度分析

SensitivityAnalysis由最優(yōu)性條件可知，當(dāng)目標(biāo)函數(shù)系數(shù)發(fā)生變化時(shí)，有可能引起檢驗(yàn)數(shù)的變化，從而影響最優(yōu)性條件是否滿足？要使最優(yōu)解不變，即當(dāng)cj變化為

后，檢驗(yàn)數(shù)仍然是小于等于零，即這時(shí)分cj是非基變量和基變量的系數(shù)兩種情況討論。第40頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月(1)cj是非基變量xj的系數(shù)即cj的增量不超過(guò)cj的檢驗(yàn)數(shù)的相反數(shù)時(shí)，最優(yōu)解不變，否則最優(yōu)解就要改變。所以

(2)ci是基變量xi的系數(shù)

因ci∈CB

，故每個(gè)檢驗(yàn)數(shù)λj中含有,當(dāng)ci變化為ci＋Δci

后λj同時(shí)變化，這時(shí)靈敏度分析

SensitivityAnalysis第41頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月令要使得所有，則有靈敏度分析

SensitivityAnalysis第42頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月要使得所有，則有只要求出上限δ2及下限δ1就可以求出Δci的變化區(qū)間靈敏度分析

SensitivityAnalysis第43頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月資源限量bi變化分析為了使最優(yōu)基B不變，求bi的變化范圍。

設(shè)br的增量為Δbr,b的增量為原性規(guī)劃的最優(yōu)解為X，基變量為XB=B－1b，要使最優(yōu)基B不變，即要求而靈敏度分析

SensitivityAnalysis第44頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月因?yàn)殪`敏度分析

SensitivityAnalysis第45頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月所以

令靈敏度分析

SensitivityAnalysis第46頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月因而要使得所有必須滿足這個(gè)公式與求的上、下限的公式類似，比值的分子都小于等于零，分母是B－1中第r列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。當(dāng)某個(gè)時(shí)，可能無(wú)上界或無(wú)下界。靈敏度分析

SensitivityAnalysis第47頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月約束系數(shù)的靈敏度分析1、非基變量的系數(shù)列向量發(fā)生變化則改變后只影響的檢驗(yàn)數(shù)，而對(duì)其他的檢驗(yàn)數(shù)沒(méi)有影響由于是對(duì)偶可行解，要使最優(yōu)基B不變，則必須有靈敏度分析

SensitivityAnalysis第48頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月當(dāng)中只有第i個(gè)分量發(fā)生變化靈敏度分析

SensitivityAnalysis第49頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月2、基變量的系數(shù)列向量發(fā)生變化當(dāng)最優(yōu)基B的列向量發(fā)生變化時(shí)，也發(fā)生變化，從單純形表可知，幾乎所有位置都受到影響，故很難給出變化范圍的一般公式，在實(shí)際問(wèn)題中往往重新計(jì)算。3、增加新的決策變量假設(shè)增加一個(gè)新變量，其對(duì)應(yīng)的目標(biāo)函數(shù)系數(shù)為，在約束函數(shù)中對(duì)應(yīng)的列向量，在最優(yōu)單純形表中增加一列相應(yīng)的檢驗(yàn)數(shù)為

若，則原問(wèn)題最優(yōu)解不變?nèi)?，則以為新的進(jìn)基變量，可用單純形法繼續(xù)迭代。靈敏度分析

SensitivityAnalysis第50頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月4、增加新的約束條件(i)若在原問(wèn)題中增加一個(gè)新的不等式約束條件先將原問(wèn)題的最優(yōu)解代入新的約束條件中，若滿足，則原最優(yōu)解是新問(wèn)題的最優(yōu)解，否則需將新約束加入原問(wèn)題，具體做法：(1)引入松弛變量，新約束成為(2)在單純形表中增加一行一列，并以為基變量，下面的系數(shù)為，注意在單純形表中的列向量是單位向量，而原來(lái)的m個(gè)基變量對(duì)應(yīng)的列向量可能不是單位向量，故應(yīng)先做初等變換，然后繼續(xù)迭代求解。靈敏度分析

SensitivityAnalysis第51頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月(ii)若在原問(wèn)題中增加一個(gè)新的等式約束條件先將原問(wèn)題的最優(yōu)解代入新的約束條件中，若滿足，則原最優(yōu)解不變，否則在新約束引入人工變量，再用大M法求解新問(wèn)題。靈敏度分析

SensitivityAnalysis第52頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月注：由以上討論可知，當(dāng)某些參數(shù)變化時(shí)，并不一定要用單純形法重新計(jì)算，而可從原最優(yōu)單純形表出發(fā)，做適當(dāng)修改，再根據(jù)具體情況求得新最優(yōu)解，其步驟如下：(1)修改原最優(yōu)單純形表，以反映參數(shù)的變化。(2)檢驗(yàn)以上修改是否使最優(yōu)解發(fā)生變化，即以下式子是否成立：(3)若滿足可行性而不滿足最優(yōu)性，則用單純形法求解；若滿足最優(yōu)性而不滿足可行性，則用對(duì)偶單純形法求解。(4)若可行性與最優(yōu)性都不滿足，則引入人工變量后重新求解；若最優(yōu)性與可行性都滿足，則最優(yōu)基不變。靈敏度分析

SensitivityAnalysis第53頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【例8】考慮下列線性規(guī)劃求出最優(yōu)解后，分別對(duì)下列各種變化進(jìn)行靈敏度分析，求出變化后的最優(yōu)解。綜合應(yīng)用靈敏度分析

SensitivityAnalysis第54頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月(2)改變目標(biāo)函數(shù)x3的系數(shù)為c3=1;(3)改變x2的系數(shù)為(4)改變約束(1)為(5)增加新約束(1)改變右端常數(shù)為:第55頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月【解】加入松弛變量x4、x5、x6，用單純形法計(jì)算，最優(yōu)表如2－10所示。表2－10Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/70－1/74/7010x60－200－111λj0－31/70－2/7－20/70

最優(yōu)解X=(1，0，2，0，0，1)T

，最優(yōu)值Z=10靈敏度分析

SensitivityAnalysis第56頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月最優(yōu)基矩陣及其逆(1)基變量的解為基本解不可行，將求得的XB代替表2－10中的常數(shù)項(xiàng)，用對(duì)偶單純形法求解，其結(jié)果見(jiàn)表2－11所示。靈敏度分析

SensitivityAnalysis第57頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月表2－11Cj2－14000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/70－1/74/706/70x60[－2]00－11－2λj0－31/70－2/7－20/70

4x30011/71/145/1417/72x1100－1/73/71/74/7－1x201001/2－1/21λj000－2/7－9/14－31/14

靈敏度分析

SensitivityAnalysis第58頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月最優(yōu)解(2)由表2－10容易得到基變量x3的系數(shù)c3的增量變化范圍是而c3=1不在允許的變化范圍之外，故表2－10的解不是最優(yōu)解。非基變量的檢驗(yàn)數(shù)x4進(jìn)基，用單純形法計(jì)算，得到表2－12靈敏度分析

SensitivityAnalysis第59頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月表2－12XBx1x2x3x4x5x6

bx305/71[1/7]3/702x112/70－1/74/701x60－200－111λj0－16/701/7－11/70

x405713014x11110103x60－200－111λj0－3－10－20

最優(yōu)解為X=(3，0，0，14，0，1)T，最優(yōu)值Z=6。靈敏度分析

SensitivityAnalysis第60頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月(3)這時(shí)目標(biāo)函數(shù)的系數(shù)和約束條件的系數(shù)都變化了，同樣求出λ2判別最優(yōu)解是否改變。x2進(jìn)基，計(jì)算結(jié)果如表2－13所示靈敏度分析

SensitivityAnalysis第61頁(yè)，課件共66頁(yè)，創(chuàng)作于2023年2月表2－13Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11－10－1/74/7010x60[3]00－111λj050－2/7－20/70

4

x3001