案例ab鋼鐵的配礦問題教學(xué)用教案7靈敏度

2023/5/23管理運(yùn)籌學(xué)課程組391§7靈敏度分析

系數(shù)bi、cj及技術(shù)條件

變化，最優(yōu)解的最優(yōu)性、可行性是否變化？

系數(shù)在什么范圍內(nèi)變化，最優(yōu)解或最優(yōu)性不變？

如何求新的最優(yōu)解？本節(jié)重點(diǎn)2023/5/23管理運(yùn)籌學(xué)課程組3927.1靈敏度分析的原理是最優(yōu)解，則可行性條件最優(yōu)性條件正則性

bi非基變量cj基變量cB增加新變量一個(gè)非基變量

系數(shù)aij的變化，要視aij對(duì)應(yīng)的變量是基變量或非基變量而定。2023/5/23管理運(yùn)籌學(xué)課程組393靈敏度分析的步驟（1）計(jì)算出由參數(shù)aij,bi,cj的變化而引起的最終單純形表上有關(guān)數(shù)字的變化。（2）檢查原問題是否仍有可行解。（3）檢查對(duì)偶問題是否仍有可行解。（4）按表2-5所列情況得出結(jié)論和決定繼續(xù)計(jì)算的步驟2023/5/23管理運(yùn)籌學(xué)課程組394原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量表2-52023/5/23管理運(yùn)籌學(xué)課程組395（1）當(dāng)cr是基變量xr的系數(shù)，即crCB，cr變化cr后，有aaaCACBBABCABCrnrrrrBLLL),,,()0,,,,0(21111D+=D+---最優(yōu)解不變1、目標(biāo)函數(shù)中價(jià)值系數(shù)C的變化2023/5/23管理運(yùn)籌學(xué)課程組396cr的變化范圍時(shí)，檢驗(yàn)數(shù)都滿足則最優(yōu)基不變。2023/5/23管理運(yùn)籌學(xué)課程組397（2）當(dāng)cj是非基底變量xj的系數(shù)，檢驗(yàn)數(shù)為或當(dāng)cj變化cj后，檢驗(yàn)數(shù)應(yīng)要小于或等于零，即2023/5/23管理運(yùn)籌學(xué)課程組398例2-7已知線性規(guī)劃問題的標(biāo)準(zhǔn)形式為其最優(yōu)單純形表如下表所示。問：1、當(dāng)c1由-1變?yōu)?時(shí)，求新問題的最優(yōu)解2、討論c2在什么范圍內(nèi)變化時(shí)，原有的最優(yōu)解仍是最優(yōu)解2023/5/23管理運(yùn)籌學(xué)課程組399cj-12100CBXBx1x2x3x4x52x26111100x51030111-30-1-20z=12解

(1)由上表可知，當(dāng)c1由－1變?yōu)?時(shí)，因?yàn)閏1是非基變量x1的價(jià)值系數(shù)，因此由c1的改變受影響的只是自己的檢驗(yàn)數(shù)，因最優(yōu)性準(zhǔn)則已經(jīng)不滿足，重新迭代，得到新問題的最優(yōu)解2023/5/23管理運(yùn)籌學(xué)課程組3910cj-12100CBXBx1x2x3x4x52x26111100x51030111-30-1-20z=12當(dāng)c1由-1變?yōu)?時(shí)，新的線型規(guī)劃問題的最優(yōu)解變?yōu)?023/5/23管理運(yùn)籌學(xué)課程組3911（2）要使原最優(yōu)解仍為最優(yōu)解，只要在新的條件下仍滿足最優(yōu)性準(zhǔn)則：2023/5/23管理運(yùn)籌學(xué)課程組3912即得故當(dāng)x1的價(jià)值系數(shù)改變量時(shí)，原有最優(yōu)解仍能保持為最優(yōu)解。2023/5/23管理運(yùn)籌學(xué)課程組3913例2-8已知線型規(guī)劃問題為其最終單純形表如下表所示2023/5/23管理運(yùn)籌學(xué)課程組3914cj703020000CBXBbx1x2x3x4x5x603070x4x2x11801575001010－4/51/103/10100－12/53/10－1/101－1/61/6－Z00－40－2－20/3問（1）c2在什么范圍變化，最優(yōu)基不變？（2）c3在什么范圍內(nèi)變化，最優(yōu)基不變？2023/5/23管理運(yùn)籌學(xué)課程組3915解：（1）設(shè)c2變化為，則變化之后得到的最終單純形表如下表cj7030＋Δc220000

CBXBbx1x2x3x4x5x6030＋Δc270x4x2X11801575001010－4/51/103/10100－12/53/10－1/101－1/61/6－Z000

由即時(shí)，最優(yōu)基不變2023/5/23管理運(yùn)籌學(xué)課程組3916（2）若c3由20變?yōu)?0＋Δc3則變化后的檢驗(yàn)數(shù)為得Δc3≤4時(shí)，最優(yōu)基不變。若Δc3＞4則我們可用單純形法繼續(xù)計(jì)算。2023/5/23管理運(yùn)籌學(xué)課程組3917例2-9某公司生產(chǎn)兩種產(chǎn)品，最優(yōu)生產(chǎn)計(jì)劃采用有如下線性規(guī)劃模型已知該線性問題的最優(yōu)解為最終單純形表如下表所示。（1）若c1由2降至1.5，c2由1升至2，最優(yōu)解會(huì)有什么變化？（2）若c1不變，c2在什么范圍內(nèi)變化，最優(yōu)解不發(fā)生變化？2023/5/23管理運(yùn)籌學(xué)課程組391821000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/217/2解：（1）將c1，c2的變化直接反映到最終的單純形表上如下表2023/5/23管理運(yùn)籌學(xué)課程組3919cj1.52000CBXBb’x1x2x3x4x50x315/2001[5/4]-15/21.5x17/21001/4-1/22x23/2010-1/43/2z=17/20001/8-9/40x46004/51-61.5x1210-1/5012x23011/50000-1/100-3/2由于將c1，c2的變化直接反映到最終單純形表后，變量x4的檢驗(yàn)數(shù)大于0，故需繼續(xù)迭代單純列表。最后得到最優(yōu)解為

2023/5/23管理運(yùn)籌學(xué)課程組3920(2)設(shè)反映到最終單純形表中如下cj2000CBXBb’x1x2x3x4x502x3x1x215/27/23/20100011005/41/4-1/4－15/2－1/23/200－4為使表中的解為最優(yōu)解，則則c2的變化范圍2023/5/23管理運(yùn)籌學(xué)課程組3921cj503000CBXBbx1x2x3x43050x2x1201501101-1/2-23/2cj-zj00-5-15已知線性規(guī)劃問題最優(yōu)單純形表練習(xí)12023/5/23管理運(yùn)籌學(xué)課程組3922XB′=B-1(b+△b)其中△b=(0,…,△br,0,…,0)T只要XB′≥0，最終表中檢驗(yàn)數(shù)不變（b變化，不影響檢驗(yàn)數(shù)），則最優(yōu)性不變，但最優(yōu)解的值發(fā)生變化,XB′成為新的最優(yōu)解.B-1(b+△b)=B-1b+B-1△b≥0新的最優(yōu)解允許范圍是:

當(dāng)某一個(gè)資源系數(shù)br發(fā)生變化，亦即br′=br+△br

，其他系數(shù)不變，這樣最終的單純形表中原問題的解相應(yīng)地變化為2、資源系數(shù)br的靈敏度變化分析2023/5/23管理運(yùn)籌學(xué)課程組3923B-1的第r列進(jìn)一步得，最終表中b列元素bbairir-3D

B-1b,0babriri3D+i=1，2，…，mi=1，2，…，miririrabba;/0-3D>iririrabba/0-￡D<2023/5/23管理運(yùn)籌學(xué)課程組3924得到公式:

若仍成立，則因?yàn)闆]有改變，因此最優(yōu)解仍是最優(yōu)解.此時(shí)為新問題的最優(yōu)解.為新問題的最優(yōu)值.若，但因仍成立.因此是一個(gè)解，.故可用對(duì)偶單純形法再次進(jìn)行迭代，直到求得新的最優(yōu)解.2023/5/23管理運(yùn)籌學(xué)課程組3925例2-10在例2-9的結(jié)果中，進(jìn)一步考慮（1）若=8，分析解的變化（2）在多大范圍內(nèi)變化，問題的最優(yōu)基不變解：（1）2023/5/23管理運(yùn)籌學(xué)課程組3926將其反映到最終單純形表中如下表所示cj

21000CBXBb’x1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010[-1/4]3/2000-1/4-1/20x315051002x15110010x420-401-60-100-2z=10由于將b2的變化直接反映到最終單純形表后，原問題的基解不可行，但檢驗(yàn)數(shù)均為非正，需繼續(xù)用對(duì)偶單純形法迭代單純列表。最后得最優(yōu)解為2023/5/23管理運(yùn)籌學(xué)課程組3927(2)令將其反映到最終單純形表中，b’列的數(shù)字為當(dāng)時(shí)問題的最優(yōu)基不變，解得2023/5/23管理運(yùn)籌學(xué)課程組3928例2-11已知線性規(guī)劃問題及其最優(yōu)單純形表若右端列向量求新問題的最優(yōu)解？2023/5/23管理運(yùn)籌學(xué)課程組3929cj-1-14000CBXBb’X1x2x3x4x5x6-104X1X5x31/3613/131-1/301/30-2/302001102/311/301/30-40-10-2z=17解：當(dāng)b由改變?yōu)闀r(shí)2023/5/23管理運(yùn)籌學(xué)課程組3930

cj-1-14000CBXBb’X1x2x3x4x5x6－104X1X5x3－1521－1/301/30[－2/3]02001102/311/301/3-z

－90－40－10－2

123004X6X5x33/27/23/2－3/21/20－1/2013/23/201/2101/21/211/200-z

－6

－3－30－200由此可將上表中第三列修改后成為下表中的第三列，再用對(duì)偶單純形法進(jìn)行迭代，新問題的最優(yōu)解為最優(yōu)值為z*=62023/5/23管理運(yùn)籌學(xué)課程組3931Ａ＝（B，N）

（1）N變化分析當(dāng)N變?yōu)闀r(shí)，它不會(huì)使右邊常數(shù)（解值）變化，而只會(huì)引起檢驗(yàn)數(shù)變化，其變化后的檢驗(yàn)數(shù)為若非基列變?yōu)椋瑒t該列的檢驗(yàn)數(shù)為只要≤0，則最優(yōu)基不變，若＞0則可用單純形法繼續(xù)計(jì)算。

3

aij的變化分析2023/5/23管理運(yùn)籌學(xué)課程組3932例2-12將例2-8中的變?yōu)榻猓悍治龅弥兓蟮膯渭冃伪韈j703020000bCβXβx1x2x3x4x5x603070x4x2x1001010－205/2－1/2100－12/53/10－1/101－1/61/6180157500－200－2－20/3z*由于＝－20＜0，故上述基可行解是最優(yōu)解。2023/5/23管理運(yùn)籌學(xué)課程組3933（2）B變化分析（1）且，則此基為最優(yōu)基，為最優(yōu)解。（2）而中存在正數(shù)，則此基不是最優(yōu)解只是基可行解，用單純形法繼續(xù)計(jì)算。（3）而中存在負(fù)數(shù)，則解只是基解，這時(shí)可用對(duì)偶單純形法繼續(xù)計(jì)算。（4）若中存在正數(shù)，中存在負(fù)數(shù)，則此時(shí)該基解既不是基可行解，也不是正則解（即對(duì)偶問題的基可行解），故需用引進(jìn)人工變量，用人工變量法運(yùn)算或者從頭開始算起。2023/5/23管理運(yùn)籌學(xué)課程組3934練習(xí)2

在練習(xí)1中，如果新增加產(chǎn)品，其目標(biāo)系數(shù)為100，消耗系數(shù)為（9，3.5）是否應(yīng)該生產(chǎn)該產(chǎn)品cj503000CBXBbx1x2x3x43050x2x1201501101-1/2-23/2cj-zj00-5-15最優(yōu)單純形表2023/5/23管理運(yùn)籌學(xué)課程組39354

增添新變量和約束的影響分析

1.增加一個(gè)新變量在建立實(shí)際問題的數(shù)學(xué)模型時(shí)，可能漏掉了一些內(nèi)容，或只考慮了主要內(nèi)容忽略了次要內(nèi)容，在得到了最優(yōu)解后，再追加這些次要內(nèi)容，再討論新變量對(duì)原最優(yōu)解的影響。設(shè)原問題的最優(yōu)解：最優(yōu)基為B。現(xiàn)追加一個(gè)新變量，其價(jià)值系數(shù)為系數(shù)列向量新問題為：2023/5/23管理運(yùn)籌學(xué)課程組3936顯然原問題的最優(yōu)基B是新問題的可行基，原有變量的檢驗(yàn)數(shù)并沒有改變，而1若，則新問題的最優(yōu)性準(zhǔn)則仍滿足，故是新問題的最優(yōu)解，說明所追加的新變量對(duì)最優(yōu)解沒有影響，或者說新增加的內(nèi)容對(duì)總的結(jié)果是不利的（因?yàn)槿魟t達(dá)不到最優(yōu)解）2若說明新增加的內(nèi)容對(duì)總的結(jié)果有利，但不是新問題的最優(yōu)解。在原問題的最優(yōu)單純形表上增加一列以作為進(jìn)基變量，用單純形表繼續(xù)迭代，得新問題的最優(yōu)解。2023/5/23管理運(yùn)籌學(xué)課程組3937例2-13在例2-8中增加一個(gè)變量x7，模型為：解：故以B為基的單純形表如下表：2023/5/23管理運(yùn)籌學(xué)課程組3938cj70302000035CBXBbx1x2x3x4x5x6X703070x4x2x11801575001010－4/51/103/10100－12/53/10－1/101－1/61/6－8［1］0－Z－570000－40－2－20/35↑03570x4x7x130015750018100－1/103/1010003/10－1/10－1/3－1/61/6010－Z－57750－5－9/207/2－35/60由于故繼續(xù)用單純形法運(yùn)算，最后求的最優(yōu)解為（x1，x2，x3，x4，x5，x6，x7）＝（75，0，0，300，0，0，15），最優(yōu)目標(biāo)值Z*＝5775。2023/5/23管理運(yùn)籌學(xué)課程組39392.增加新約束條件若增加新的約束條件式中是n維行向量（1）因?yàn)樾聠栴}的可行域總是屬于原問題的可行域，決不會(huì)超過原可行域，因此若原問題的最優(yōu)解X*也滿足新增加的約束，則原問題的最優(yōu)解也是新問題的最優(yōu)解.即新增加的約束對(duì)結(jié)果沒有影響。（2）若原問題的最優(yōu)解X*不滿足新增加的約束條件，說明原問題的最優(yōu)解在新問題可行域之外，則需要重新求新問題的最優(yōu)解.2023/5/23管理運(yùn)籌學(xué)課程組3940Cj0右端00100新問題的基變量新問題的基矩陣2023/5/23管理運(yùn)籌學(xué)課程組3941在現(xiàn)行基下對(duì)應(yīng)變量的檢驗(yàn)數(shù)因此除了之外，檢驗(yàn)數(shù)與原問題相同。因此為基變量，故有2023/5/23管理運(yùn)籌學(xué)課程組39422023/5/23管理運(yùn)籌學(xué)課程組39430右端項(xiàng)001100（1）若因?yàn)楣蕽M足可行性條件，成立，故X為新問題的最優(yōu)解。（2）若則當(dāng)前解X不是可行解，而是基解。故可用對(duì)偶單純形法迭代，直到求得最優(yōu)解（或判斷此問題無可行解）。2023/5/23管理運(yùn)籌學(xué)課程組3944例2-14已知線性規(guī)劃問題其最優(yōu)單純形表為cj-1-14000CBXBx1x2x3x4x5x6-1x11/31-1/301/30-2/30x560200114x313/302/311/301/30-40-10-2z=172023/5/23管理運(yùn)籌學(xué)課程組3945現(xiàn)增加新約束求新問題的最優(yōu)解解：增加約束后的新問題為原問題的最優(yōu)解為帶入新增加的約束故X*不滿足新增加的約束條件，因此引入松弛變量x7后，新增加的約束條件變?yōu)?023/5/23管理運(yùn)籌學(xué)課程組3946cj-1-140000CBXBx1x2x3x4x5x6x7-1x11/31-1/301/30-2/300x5602001104x313/302/311/301/300x717-31600010-40-10-20z=17將第1行的3倍，第3行的（-6）倍分別加到第4行上，使基變量x1、x5、x3

、x7的系數(shù)列向量構(gòu)成單位矩陣，即得到下表2023/5/23管理運(yùn)籌學(xué)課程組3947cj-1-140000CBXBx1x2x3x4x5x6x7-1x11/31-1/301/30-2/300x5602001104x313/302/311/301/300x7-80-40-10[-4]10-40-10-20z=17111/2在表中故當(dāng)前解不是可行解，用對(duì)偶單純形法求解，x7是換出變量，A4為主行又p6是主列，是主元素2023/5/23管理運(yùn)籌學(xué)課程組3948cj-1-140000CBXBx1x2x3x4x5x6x7-1x15/311/301/200-1/60x54010-1/4101/44x311/301/311/4001/120x620101/401-1/40-20-10-2-1/2z=13新問題的最優(yōu)解要注意的是追加約束條件后，新問題的目標(biāo)函數(shù)值總不會(huì)比原問題的目標(biāo)函數(shù)值好（為什么）2023/5/23管理運(yùn)籌學(xué)課程組3949線性規(guī)劃綜合例題

某工廠使用5種生產(chǎn)方式，生產(chǎn)A、B、C三種產(chǎn)品，有關(guān)每種方法的批產(chǎn)量數(shù)據(jù)如表1、資源消耗如表2。有一合同要求至少生產(chǎn)A110單位。

表1每種方法的批產(chǎn)量

方法產(chǎn)品12345單價(jià)ABC3622164254110481054

方法產(chǎn)品12345數(shù)量工時(shí)機(jī)時(shí)成本/元01484119623011442178050-表2資源消耗

列出利潤(rùn)最大化的線性規(guī)劃模型2023/5/23管理運(yùn)籌學(xué)課程組3950MaxZ=20x1+30x2+40x3+5x4+45x5設(shè)xj為