對(duì)偶單純形法靈敏度分析

對(duì)偶單純形法靈敏度分析第一頁，共六十六頁，2022年，8月28日第四節(jié)對(duì)偶單純形法

對(duì)偶單純形法并不是求對(duì)偶問題解的方法，而是利用單純形法求解規(guī)劃問題時(shí)運(yùn)用了對(duì)偶理論。也就是說：對(duì)偶單純形法與單純形法一樣都是是求解線性規(guī)劃的一種基本方法。它是根據(jù)對(duì)偶原理和單純形法原理設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。

在了解對(duì)偶單純形法的實(shí)質(zhì)之前，我們回顧一下單純形法。單純形法開始于初始基可行解。如果不滿足最優(yōu)性條件，則要換基迭代轉(zhuǎn)到能使目標(biāo)函數(shù)值得到改善的鄰近頂點(diǎn)上。在這個(gè)轉(zhuǎn)換過程中，存在兩個(gè)原則:一是首先保持原問題的解仍是可行的，另一個(gè)是要求目標(biāo)函數(shù)值有改善。

如何保證可行？第二頁，共六十六頁，2022年，8月28日項(xiàng)目非基變量基變量XBXNXS0XSbBNICj-ZjCBCN0項(xiàng)目基變量非基變量XBXNXSCBXBB-1bIB-1NB-1

Cj-Zj0CN-CBB-1N-CBB-1

初始單純形表CBCN0單純形法是在保持所有約束條件常數(shù)項(xiàng)總是保持大于等于零的情況（保證可行），通過迭代，使所有檢驗(yàn)數(shù)小于等于零（求最大值），求得最優(yōu)解。第三頁，共六十六頁，2022年，8月28日1、當(dāng)原問題達(dá)到最優(yōu)時(shí)，松弛變量經(jīng)過上述轉(zhuǎn)換后構(gòu)成的檢驗(yàn)數(shù)的相反數(shù)為其對(duì)偶問題的一個(gè)可行解，反之亦成立原問題表中的檢驗(yàn)數(shù)滿足最優(yōu)性條件CN-CBB-1N≤0

-CBB-1≤0;ATY≥CT;

Y≥0YT=CBB-1從上面可以看出：也就是說，當(dāng)原問題達(dá)到最優(yōu)時(shí)，對(duì)偶問題的解可行。并且根據(jù)對(duì)偶的性質(zhì)，我們可以確定此時(shí)對(duì)偶問題也達(dá)到最優(yōu)CB:1×mB-1：m×mCBB-1：1×mY：m×1第四頁，共六十六頁，2022年，8月28日項(xiàng)目非基變量基變量XBXNXS0XSbBNICj-ZjCBCN0項(xiàng)目基變量非基變量XBXNXSCBXBB-1bIB-1NB-1

Cj-Zj0CN-CBB-1N-CBB-1

初始單純形表也就是：?jiǎn)渭冃畏ㄓ?jì)算時(shí)只要原問題可行（B-1b≥0），對(duì)偶問題可行（即檢驗(yàn)數(shù)小于0），解就是最優(yōu)解。單純形法的基本過程就是保證原問題解可行的情況下，不停迭代，直至對(duì)偶問題也達(dá)到可行，此時(shí)原問題達(dá)到最優(yōu)，對(duì)偶問題也達(dá)到最優(yōu)第五頁，共六十六頁，2022年，8月28日根據(jù)剛才所說，單純形法只要單純形法計(jì)算時(shí)只要原問題可行（B-1b≥0），對(duì)偶問題可行（即檢驗(yàn)數(shù)小于0），解就是最優(yōu)解。所以，我們利用單純形法對(duì)原問題求解時(shí)，如果首先保持對(duì)偶問題的可行性（即原問題檢驗(yàn)數(shù)≤0），然后再看原問題是否可行，如果此時(shí)原問題的解不可行，則換基迭代，換基過程中保證對(duì)偶可行（檢驗(yàn)數(shù)≤0），直至原問題由不可行解變?yōu)榭尚薪猓藭r(shí)就得到它的最優(yōu)解，——這就是對(duì)偶單純形法的基本思想。第四節(jié)對(duì)偶單純形法

也就是說：對(duì)偶單純形法是在保持原問題所有檢驗(yàn)數(shù)都小于等于零的基礎(chǔ)上，通過迭代，使原問題的解（即右邊常數(shù)項(xiàng)）都大于等于零，從而求得最優(yōu)解。第六頁，共六十六頁，2022年，8月28日第四節(jié)對(duì)偶單純形法（2）初始解不可行，即右端常數(shù)項(xiàng)有負(fù)分量（如果原問題可行，則直接用單純形法）使用對(duì)偶單純形法必須滿足兩個(gè)條件：（1）單純形表中的所有檢驗(yàn)數(shù)必須符合對(duì)偶可行，即小于等于0第七頁，共六十六頁，2022年，8月28日①先找一個(gè)基，建立初始對(duì)偶單純形表，使檢驗(yàn)數(shù)全部非正，即C全部為非正；②若b列元素非負(fù)，則已經(jīng)是最優(yōu)基。反之，則換基迭代，直至原問題可行。第四節(jié)對(duì)偶單純形法怎么做呢？第八頁，共六十六頁，2022年，8月28日例用對(duì)偶單純形法求解該問題用單純形法求解時(shí)，需要先化標(biāo)準(zhǔn)型，此時(shí)約束方程兩邊左邊需要減去剩余變量，同時(shí)為了構(gòu)造單位陣，需要添加人工變量，采用大M法求解。第四節(jié)對(duì)偶單純形法思考：上面約束方程化為標(biāo)準(zhǔn)型后，兩邊乘以-1，就可得到單位陣。此時(shí)能否用單純形法？原因?答：不能。因?yàn)榇藭r(shí)右邊常數(shù)項(xiàng)為負(fù)數(shù)，解不可行。為了保證初始解可行第九頁，共六十六頁，2022年，8月28日例用對(duì)偶單純形法求解第四節(jié)對(duì)偶單純形法能否用對(duì)偶單純形法呢？對(duì)偶單純形法初始對(duì)偶單純形表只要保證對(duì)偶可行，即檢驗(yàn)數(shù)全部非正即可。并不要求初始解可行，所以右邊常數(shù)項(xiàng)可以非負(fù)，此題目?jī)r(jià)值系數(shù)均為負(fù)，意味著初始單純形表格的檢驗(yàn)數(shù)為負(fù)，而右端常數(shù)項(xiàng)又有負(fù)數(shù)，正好滿足對(duì)偶單純形法的要求。第十頁，共六十六頁，2022年，8月28日例用對(duì)偶單純形法求解將約束方程化為標(biāo)準(zhǔn)型，再用（-1）乘不等式兩邊第四節(jié)對(duì)偶單純形法第十一頁，共六十六頁，2022年，8月28日cj

-1-40-300CBXBbx1

x2x3x4x5x600x5x6-3-2-1-21-11021-4-1010-1-40-300此時(shí)，初始單純形表檢驗(yàn)數(shù)均小于等于0，對(duì)偶可行，但原問題初始解不可行第四節(jié)對(duì)偶單純形法初始對(duì)偶單純形表第十二頁，共六十六頁，2022年，8月28日cj

-1-40-300CBXBbx1

x2x3x4x5x600x5x6-3-2-1-21-11021-4-1010-1-40-300先選出基變量后選進(jìn)基變量原問題不可行，應(yīng)該換基迭代。但按對(duì)偶單純形法的思想，每次均應(yīng)保證檢驗(yàn)數(shù)均非正cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10第十三頁，共六十六頁，2022年，8月28日cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10-10x1x37417/205/2-2-1/203/213/2-1-1/270-1/20-1/2-2-1/2最優(yōu)解X*=（7，0，4，0）TZ*=-7第十四頁，共六十六頁，2022年，8月28日例6用對(duì)偶單純形法求解（P）第十五頁，共六十六頁，2022年，8月28日1-4/3---10-5/21/21-1/221-1/23/20-1/20-4-10-1-8/5--22/501-1/5-2/51/511/5107/5-1/5-2/500-3/5-8/5-1/5[][]單純形表第十六頁，共六十六頁，2022年，8月28日第四節(jié)對(duì)偶單純形法

使用對(duì)偶單純形法求初始解時(shí)右邊常數(shù)項(xiàng)可以為負(fù)，所以對(duì)于一些大于等于號(hào)的約束表達(dá)式不需要添加人工變量，只要兩邊同時(shí)乘上-1，就可用對(duì)偶單純形法求解，簡(jiǎn)化計(jì)算，這是該方法的優(yōu)點(diǎn)。缺點(diǎn)是很難找到一個(gè)初始解使得所有檢驗(yàn)數(shù)都小于等于零，因而很少單獨(dú)使用。第十七頁，共六十六頁，2022年，8月28日1、什么是靈敏度分析？

靈敏度分析是指系統(tǒng)或事物因?yàn)橹車鷹l件變化而顯示出來的敏感程度分析。一、含義和研究對(duì)象第五節(jié)靈敏度分析第十八頁，共六十六頁，2022年，8月28日

在生產(chǎn)計(jì)劃問題的一般形式中，A代表企業(yè)的技術(shù)狀況，b代表企業(yè)的資源狀況，而C代表企業(yè)產(chǎn)品的市場(chǎng)狀況，在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計(jì)劃和最大利潤(rùn)由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。在實(shí)際生產(chǎn)過程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產(chǎn)計(jì)劃，而在計(jì)劃實(shí)施前或?qū)嵤┲猩鲜鰻顩r發(fā)生了改變，則決策者所關(guān)心的是目前所執(zhí)行的計(jì)劃還是不是最優(yōu)，如果不是應(yīng)該如何修訂原來的最優(yōu)計(jì)劃。更進(jìn)一步，為了防止在各類狀況發(fā)生時(shí)，來不及隨時(shí)對(duì)其變化作出反應(yīng)，即所謂“計(jì)劃不如變化快”，企業(yè)應(yīng)當(dāng)預(yù)先了解，當(dāng)各項(xiàng)因素變化時(shí)，應(yīng)當(dāng)作出什么樣的反應(yīng)。第五節(jié)靈敏度分析第十九頁，共六十六頁，2022年，8月28日1、什么是靈敏度分析？

是指研究線性規(guī)劃模型的某些參數(shù)(bi,cj,aij）或限制量（xj,約束條件）的變化對(duì)最優(yōu)解的影響及其程度的分析過程<也稱為優(yōu)化后分析>。一、含義和研究對(duì)象s.t.第五節(jié)靈敏度分析第二十頁，共六十六頁，2022年，8月28日回答兩個(gè)問題：

①這些系數(shù)在什么范圍內(nèi)發(fā)生變化時(shí)，最優(yōu)解不變？②系數(shù)變化超出上述范圍，如何用最簡(jiǎn)便的方法求出新的最優(yōu)解？2、靈敏度分析的研究對(duì)象：

目標(biāo)函數(shù)的系數(shù)cj變化對(duì)最優(yōu)解的影響；約束方程右端系數(shù)bi變化對(duì)最優(yōu)解的影響；約束方程組系數(shù)矩陣A變化對(duì)最優(yōu)解的影響；

一、含義和研究對(duì)象第二十一頁，共六十六頁，2022年，8月28日

1、在最終單純形表的基礎(chǔ)上進(jìn)行；2、盡量減少附加的計(jì)算工作量；

二、進(jìn)行靈敏度分析的基本原則第二十二頁，共六十六頁，2022年，8月28日三、靈敏度分析的步驟原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優(yōu)解或最優(yōu)基不變用單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，編制新的單純形表重新計(jì)算先求問題的最優(yōu)解.將參數(shù)的改變通過計(jì)算反映到最終單純形表上來.檢查原問題的可行解和檢驗(yàn)數(shù)是否滿足最優(yōu).4.依據(jù)不同情況決定繼續(xù)計(jì)算或得到結(jié)論.第二十三頁，共六十六頁，2022年，8月28日4.分析增加一個(gè)約束條件的變化四、靈敏度分析的主要內(nèi)容1.分析

cj

的變化2.分析

bi

的變化3.分析系數(shù)

aij的變化5.分析增加一個(gè)變量

xj的變化

系數(shù)矩陣As.t.第二十四頁，共六十六頁，2022年，8月28日

對(duì)偶問題決策變量的最優(yōu)解<影子價(jià)格>：初始單純形表最優(yōu)單純形表X*=B-1bCN－CBB-1N≤0－CBB-1≤0

原問題基變量的最優(yōu)解：Z*=CBB-1b最優(yōu)值：Y*T=CBB-1第二十五頁，共六十六頁，2022年，8月28日Y*T=CBB-1

XB

I

0基變量非基變量XB基變量基變量基可系數(shù)行解

CN－CBB-1NB-1NB-1XNXsB-1bCBB-1b－CBB-1Z*=CBB-1b分析cj

的變化原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優(yōu)解或最優(yōu)基不變用單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，編制新的單純形表重新計(jì)算最優(yōu)值可能已變第二十六頁，共六十六頁，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15變化

x1,x2≥0maxs.t.2x1+2x2≤12z=(2+λ1)x1+(3+λ2)x2

4x1≤165x2≤

15qi當(dāng)λ2=0時(shí)，將λ1反映在最終單純形表中，可得從而，表中解仍為最優(yōu)解的條件是即當(dāng)

時(shí)問題的最優(yōu)解不變。例1-1分析λ1和λ2分別在什么范圍變化時(shí)，最優(yōu)解不變？第二十七頁，共六十六頁，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15變化

x1,x2≥0maxs.t.2x1+2x2≤12z=(2+λ1)x1+(3+λ2)x2

4x1≤165x2≤

15qi當(dāng)λ1=0時(shí)，將λ2

反映在最終單純形表中，可得從而，表中解仍為最優(yōu)解的條件是即當(dāng)時(shí)問題的最優(yōu)解不變。例1-1分析λ1和λ2分別在什么范圍變化時(shí)，最優(yōu)解不變？第二十八頁，共六十六頁，2022年，8月28日美佳公司計(jì)劃生產(chǎn)I、II兩種產(chǎn)品，每天生產(chǎn)條件如表，問(1)該公司應(yīng)如何安排生產(chǎn)計(jì)劃才能使總利潤(rùn)最多?(2)若產(chǎn)品Ⅰ的利潤(rùn)不變，則產(chǎn)品Ⅱ的利潤(rùn)在什么范圍內(nèi)變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？(3)若產(chǎn)品Ⅰ的利潤(rùn)降至1.5百元/單位，而產(chǎn)品Ⅱ的利潤(rùn)增至2百元/單位，最優(yōu)生產(chǎn)計(jì)劃有何變化

？例2-1設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)利潤(rùn)(百元)ⅠⅡ每天可用能力資源產(chǎn)品0562112115245第二十九頁，共六十六頁，2022年，8月28日例2-1如何安排生產(chǎn)計(jì)劃才能使總利潤(rùn)最多？解：(1)設(shè)x1,x2分別表示Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)數(shù)量，得LP模型maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0用單純形法求解得最終單純形表設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)利潤(rùn)(百元)ⅠⅡ每天可用能力資源產(chǎn)品0562112115245第三十頁，共六十六頁，2022年，8月28日例2-1如何安排生產(chǎn)計(jì)劃才能使總利潤(rùn)最多？解：(1)設(shè)x1,x2分別表示Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)數(shù)量，得LP模型maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0用單純形法求解得最終單純形表得最優(yōu)解為：X*=(7/2,3/2,15/2,0,0)Tzmax=8.5(百元)。即每天生產(chǎn)3.5單位產(chǎn)品Ⅰ，1.5單位產(chǎn)品Ⅱ時(shí)總利潤(rùn)最多，且第三十一頁，共六十六頁，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-1解：(2)將產(chǎn)品Ⅱ的利潤(rùn)變化反映在最終單純形表中，可得maxz=2x1+(1+△c2)x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0表中解仍為最優(yōu)解的條件是產(chǎn)品Ⅱ的利潤(rùn)在什么范圍內(nèi)變化時(shí)，最優(yōu)生產(chǎn)計(jì)劃不會(huì)發(fā)生變化？即故當(dāng)產(chǎn)品Ⅱ的利潤(rùn)在范圍變化時(shí)，最優(yōu)生產(chǎn)計(jì)劃不變。1→1+△c2第三十二頁，共六十六頁，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-1產(chǎn)品Ⅰ利潤(rùn)降至1.5百元/單位，產(chǎn)品Ⅱ的利潤(rùn)增至2百元/單位，生產(chǎn)計(jì)劃如何變化？解：(3)將產(chǎn)品Ⅰ、Ⅱ的利潤(rùn)變化反映在最終單純形表中，可得maxz=1.5x1+2x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0因有非基變量的檢驗(yàn)數(shù)大于零需繼續(xù)用單純形法迭代計(jì)算第三十三頁，共六十六頁，2022年，8月28日例2-1產(chǎn)品Ⅰ利潤(rùn)降至1.5百元/單位，產(chǎn)品Ⅱ的利潤(rùn)增至2百元/單位，生產(chǎn)計(jì)劃如何變化？需繼續(xù)用單純形法迭代計(jì)算θ614-得最優(yōu)解為：X*=(2,3,0,6,0)T說明隨產(chǎn)品利潤(rùn)的改變，為獲得最高利潤(rùn)，應(yīng)將生產(chǎn)計(jì)劃調(diào)整為每天生產(chǎn)2單位產(chǎn)品Ⅰ，3單位產(chǎn)品Ⅱ，且zmax=9(百元)。第三十四頁，共六十六頁，2022年，8月28日Y*T=CBB-1

XB

I

0基變量非基變量XB基變量基變量基可系數(shù)行解

CN－CBB-1NB-1NB-1XNXsB-1bCBB-1b－CBB-1Z*=CBB-1b分析cj

的變化原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優(yōu)解或最優(yōu)基不變用單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，編制新的單純形表重新計(jì)算第三十五頁，共六十六頁，2022年，8月28日B-1NB-1Y*T=CBB-1

XB

I

0基變量非基變量XB基變量基變量基可系數(shù)行解

CN－CBB-1NXNXsB-1bCBB-1b－CBB-1Z*=CBB-1b原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優(yōu)解或最優(yōu)基不變用單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，編制新的單純形表重新計(jì)算分析bi的變化最優(yōu)解或最優(yōu)值可能已變第三十六頁，共六十六頁，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15變化

x1,x2≥0maxs.t.2x1+2x2≤12+λ1z=2x1+3x2

4x1≤16+λ25x2≤

15+λ3分析λi分別在什么范圍變化時(shí)，最優(yōu)基不變？例1-2qi第三十七頁，共六十六頁，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15變化

x1,x2≥0maxs.t.2x1+2x2≤12+λ1z=2x1+3x2

4x1≤16+λ25x2≤

15+λ3例1-2解：先分析λ1的變化范圍:為使最優(yōu)基不變，則需,即從而得到同理可得λ2與λ3的取值范圍分析λi分別在什么范圍變化時(shí)，最優(yōu)基不變？第三十八頁，共六十六頁，2022年，8月28日

美佳公司計(jì)劃生產(chǎn)I、II兩種產(chǎn)品，每天生產(chǎn)條件如表，問(4)若設(shè)備A和B的能力不變，調(diào)試工序能力在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)基不變？(5)設(shè)備A和調(diào)試工序每天能力不變，而設(shè)備B能力增加到32，問最優(yōu)生產(chǎn)計(jì)劃如何變化？例2-2設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)利潤(rùn)(百元)ⅠⅡ每天可用能力資源產(chǎn)品0562112115245maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0得最優(yōu)解為：X*=(7/2,3/2,15/2,0,0)T第三十九頁，共六十六頁，2022年，8月28日例2-2解：調(diào)試工序能力在什么范圍變化，最優(yōu)基不變？maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5+△b3x1,x2≥0(4)由最終單純形表，可得第四十頁，共六十六頁，2022年，8月28日例2-2解：maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5+△b3x1,x2≥0(4)由最終單純形表，可得由，計(jì)算得調(diào)試工序能力在什么范圍變化，最優(yōu)基不變？第四十一頁，共六十六頁，2022年，8月28日例2-2因此當(dāng)調(diào)試工序能力在范圍變化時(shí)，問題的最優(yōu)基不變。調(diào)試工序能力在什么范圍變化，最優(yōu)基不變？為使最優(yōu)基不變，則需,即從而得到5→5+△b3第四十二頁，共六十六頁，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-2解：(5)由最終單純形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0設(shè)備B可用能力增加到32，生產(chǎn)計(jì)劃如何變化？第四十三頁，共六十六頁，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-2解：(5)由最終單純形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0設(shè)備B可用能力增加到32，生產(chǎn)計(jì)劃如何變化？反映到最終單純形表可得第四十四頁，共六十六頁，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-2解：(5)由最終單純形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0設(shè)備B可用能力增加到32，生產(chǎn)計(jì)劃如何變化？反映到最終單純形表可得第四十五頁，共六十六頁，2022年，8月28日例2-2解：(5)由最終單純形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0設(shè)備B可用能力增加到32，生產(chǎn)計(jì)劃如何變化？表中原問題為非可行解，用對(duì)偶單純形法繼續(xù)計(jì)算得最優(yōu)解為：X*=(5,0,15,2,0)Tzmax=10(百元)。第四十六頁，共六十六頁，2022年，8月28日B-1NB-1Y*T=CBB-1

XB

I

0基變量非基變量XB基變量基變量基可系數(shù)行解

CN－CBB-1NXNXsB-1bCBB-1b－CBB-1Z*=CBB-1b原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優(yōu)解或最優(yōu)基不變用單純形法繼續(xù)迭代求最優(yōu)解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，編制新的單純形表重新計(jì)算分析bi的變化第四十七頁，共六十六頁，2022年，8月28日4.分析增加一個(gè)約束條件的變化四、靈敏度分析的主要內(nèi)容1.分析

cj

的變化2.分析

bi

的變化3.分析系數(shù)

aij的變化5.分析增加一個(gè)變量

xj的變化系數(shù)矩陣As.t.第四十八頁，共六十六頁，2022年，8月28日增加一個(gè)新變量xj的分析若企業(yè)在計(jì)劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單位利潤(rùn)，單件資源消耗量時(shí)，可以在最優(yōu)表中補(bǔ)充一列，其中的前m行可以由基矩陣的逆矩陣得到，而檢驗(yàn)數(shù)行也可以由與其它列相同的方法計(jì)算得到。若檢驗(yàn)數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計(jì)劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當(dāng)檢驗(yàn)數(shù)為正時(shí)，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。第四十九頁，共六十六頁，2022年，8月28日增加一個(gè)新變量xj的分析項(xiàng)目基變量非基變量CB

XBB–1

b

XBXN

XsIB–1

N

B–1

檢驗(yàn)數(shù)0(CN-

CBB–1

N

)-CBB–1

項(xiàng)目0Xs

b非基變量基變量XBXNXsB

N

I檢驗(yàn)數(shù)CB

CN0XjPjCjXjB-1PjCj–CBB-1Pj第五十頁，共六十六頁，2022年，8月28日增加一個(gè)新變量xj的分析項(xiàng)目基變量非基變量CB

XBB–1

b

XBXN

XsIB–1

N

B–1

檢驗(yàn)數(shù)0(CN-

CBB–1

N

)-CBB–1

XjB-1PjCj–CBB-1Pj此時(shí)如果檢驗(yàn)數(shù)小于0，原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計(jì)劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當(dāng)檢驗(yàn)數(shù)為正時(shí)，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。第五十一頁，共六十六頁，2022年，8月28日增加一個(gè)新變量xj的分析計(jì)算步驟：項(xiàng)目基變量非基變量CB

XBB–1

b

XBXN

XsIB–1

N

B–1

檢驗(yàn)數(shù)0XjB-1PjCj–CBB-1Pj(CN-

CBB–1

N

)-CBB–1

第五十二頁，共六十六頁，2022年，8月28日例

美嘉公司例子maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)利潤(rùn)(百元)ⅠⅡ每天可用能力資源產(chǎn)品0562112115245如果該廠計(jì)劃推出新產(chǎn)品3，生產(chǎn)一件所需要設(shè)備A,B以及調(diào)試工序的時(shí)間分別是3h,4h,2h，該產(chǎn)品的預(yù)期利潤(rùn)3元/件，分析該種產(chǎn)品是否值得投產(chǎn)？如投產(chǎn)，對(duì)該公司的最優(yōu)生產(chǎn)計(jì)劃有何改變？第五十三頁，共六十六頁，2022年，8月28日是否值得生產(chǎn)，看檢驗(yàn)數(shù)，大于0，值得生產(chǎn)（影子價(jià)格特點(diǎn)）解：設(shè)該廠生產(chǎn)新產(chǎn)品3為x6件，C６=3,P6=(3,4,2)T檢驗(yàn)數(shù)大于0，值得生產(chǎn)分析該種產(chǎn)品是否值得投產(chǎn)？第五十四頁，共六十六頁，2022年，8月28日解：設(shè)該廠生產(chǎn)新產(chǎn)品3為x6件，C６=3,P6=(3,4,2)T如投產(chǎn)，對(duì)該公司的最優(yōu)生產(chǎn)計(jì)劃有何改變？因?yàn)闄z驗(yàn)數(shù)大于0，值得生產(chǎn)。也說明要投產(chǎn)的話，最優(yōu)計(jì)劃會(huì)改變，如何變，要通過計(jì)算，將結(jié)果反映到最終單純形表上。第五十五頁，共六十六頁，2022年，8月28日Cj210003CB

基bX1x2x3x4x5x60x315/22x17/21x23/20015/4-15/2-7100?-1/20010-1/43/22Cj-Zj000-1/4-1/21Cj210003CB

基bX1x2x3x4x5x60x351/42x17/23x63/407/213/8-9/40100?-1/2001/20-1/83/41Cj-Zj0-1/20-1/8-5/40第五十六頁，共六十六頁，2022年，8月28日Cj210003CB

基bX1x2x3x4x5x60x351/42x17/23x63/407/213/8-9/40100?-1/2001/20-1/83/41Cj-Zj0-1/20-1/8-5/40新的最優(yōu)生產(chǎn)計(jì)劃為每天生產(chǎn)1產(chǎn)品：7/2件生產(chǎn)2產(chǎn)品：0件；生產(chǎn)3產(chǎn)品：3/4件。第五十七頁，共六十六頁，2022年，8月28日參數(shù)aij的變化導(dǎo)致系數(shù)陣A的元素發(fā)生變化。相當(dāng)于增加1個(gè)新變量（系數(shù)陣A增加1列），如果xj在最終單純形表中為基變量，則aij的變化會(huì)使相應(yīng)的B,B-1發(fā)生變化，有可能出現(xiàn)原問題與對(duì)偶問題無可行解的情況。引進(jìn)人工變量，使用單純形法計(jì)算。如果該廠生產(chǎn)的產(chǎn)品2，生產(chǎn)一件所需要設(shè)備A,B以及調(diào)試工序的時(shí)間分別變?yōu)?h,4h,1h，該產(chǎn)品的利潤(rùn)變?yōu)?元/件，對(duì)該公司的最優(yōu)生產(chǎn)計(jì)劃有何改變？分析參數(shù)aij的變化第五十八頁，共六十六頁，2022年，8月28日解：將改變的產(chǎn)品看作是一件新的產(chǎn)品，生產(chǎn)量X2’將其反映到單純形表分析參數(shù)aij的變化第五十九頁，共六十六頁，2022年，8月28日Cj213000CB基bX1x2X2’x3x4x50x315/22x17/21x23/20011/215/4-15/210?0?-1/201?0-1/43/2Cj-Zj003/20-1/4-1/2Cj213000CB

基bX1

x2x2’x3x4x50x3-92x123x2’300014-2410001/2-20110-1/23Cj-Zj00001/2-5刪除X2所在列第六十頁，共六十六頁，2022年，8月28日原問題與對(duì)偶問題均為非可行解，先使原問題轉(zhuǎn)化為可行解第一行的約束：x3+4x4-24x5=-9,乘以（-1），加上人工變量-x3-4x4+24x5

+x6