第二章線性規(guī)劃演示文稿目前一頁\總數(shù)九十九頁\編于十七點(diǎn)優(yōu)選第二章線性規(guī)劃目前二頁\總數(shù)九十九頁\編于十七點(diǎn)第二章規(guī)劃論模型1.線性規(guī)劃2.整數(shù)規(guī)劃3.非線性規(guī)劃4.動(dòng)態(tài)規(guī)劃目前三頁\總數(shù)九十九頁\編于十七點(diǎn)第一節(jié)線性規(guī)劃模型1.線性規(guī)劃模型2.單純形法3.對(duì)偶單純形法目前四頁\總數(shù)九十九頁\編于十七點(diǎn)一線性規(guī)劃的數(shù)學(xué)模型AB備用資源煤1230

勞動(dòng)日3260

倉庫0224

利潤(rùn)4050例1、生產(chǎn)計(jì)劃問題A,B各生產(chǎn)多少,可獲最大利潤(rùn)?目前五頁\總數(shù)九十九頁\編于十七點(diǎn)

x1

+2x2

303x1+2x2

60

2x2

24

x1，x2

0

maxZ=40x1+50x2解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1

，x2目前六頁\總數(shù)九十九頁\編于十七點(diǎn)例2求：最低成本的原料混合方案

原料ABＣ每單位成本

14102261253171642538

每單位添加劑中維生12148

素最低含量目前七頁\總數(shù)九十九頁\編于十七點(diǎn)解：設(shè)每單位添加劑中原料i的用量為xi(i=1,2,3,4)minZ=2x1

+5x2+6x3+8x44x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)目前八頁\總數(shù)九十九頁\編于十七點(diǎn)例3：任務(wù)分配問題：某車間有甲、乙兩臺(tái)機(jī)床，可用于加工三種工件。假定這兩臺(tái)車床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？目前九頁\總數(shù)九十九頁\編于十七點(diǎn)解設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：目前十頁\總數(shù)九十九頁\編于十七點(diǎn)二線性規(guī)劃模型特點(diǎn)決策變量：向量(x1…

xn)T決策人要考慮和控制的因素非負(fù)約束條件：線性等式或不等式目標(biāo)函數(shù)：Z=?(x1

…

xn)線性式，求Z極大或極小目前十一頁\總數(shù)九十九頁\編于十七點(diǎn)一般式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)目前十二頁\總數(shù)九十九頁\編于十七點(diǎn)線性規(guī)劃的標(biāo)準(zhǔn)型(standardmodel)

線性規(guī)劃的標(biāo)準(zhǔn)型：對(duì)目標(biāo)函數(shù)求極小，決策變量一律為非負(fù)變量，約束條件除變量的非負(fù)條件外，一律為等式約束。各種形式的線性規(guī)劃模型一律為等式約束。①若目標(biāo)函數(shù)為目前十三頁\總數(shù)九十九頁\編于十七點(diǎn)

則可令f=-z,此問題轉(zhuǎn)化為求

②若約束條件含則引進(jìn)有

稱為松弛變量③若約束條件含,則引進(jìn)新變量，有

稱為剩余變量。④若約束條件含則引進(jìn),于是

⑤若變量的符號(hào)不受限制，則可引進(jìn)兩個(gè)新量,

并以代入目標(biāo)函數(shù)及約束中消去，

目前十四頁\總數(shù)九十九頁\編于十七點(diǎn)

而在約束條件中增加例：把線性規(guī)劃

化為標(biāo)準(zhǔn)型.

分析：①令，將maxz改為求minf②用代替，其中③對(duì)不等式約束分別引進(jìn)松弛變量和剩余變量

目前十五頁\總數(shù)九十九頁\編于十七點(diǎn)

于是，原問題化為標(biāo)準(zhǔn)型：

目前十六頁\總數(shù)九十九頁\編于十七點(diǎn)

例4

把問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式目前十七頁\總數(shù)九十九頁\編于十七點(diǎn)

于是轉(zhuǎn)化為標(biāo)準(zhǔn)形式♂返回目前十八頁\總數(shù)九十九頁\編于十七點(diǎn)1.1基本概念目前十九頁\總數(shù)九十九頁\編于十七點(diǎn)目前二十頁\總數(shù)九十九頁\編于十七點(diǎn)圖解法的步驟：1.求可行解集合。分別求出滿足每個(gè)約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標(biāo)函數(shù)圖形。先過原點(diǎn)作一條矢量指向點(diǎn)（c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)圖形；3.求最優(yōu)解。依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是最優(yōu)解。一般地，將目標(biāo)函數(shù)直線放在可行域中求最大值時(shí)直線沿著矢量方向移動(dòng)求最小值時(shí)沿著矢量的反方向移動(dòng)三.圖解法GraphicalMethod目前二十一頁\總數(shù)九十九頁\編于十七點(diǎn)x1x2O1020304010203040(3,4)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85例5目前二十二頁\總數(shù)九十九頁\編于十七點(diǎn)246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)minZ=x1+2x2例6(1,2)目前二十三頁\總數(shù)九十九頁\編于十七點(diǎn)246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2例7有無窮多個(gè)最優(yōu)解即具有多重解,通解為0≤α≤1

當(dāng)α=0.5時(shí)Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)目前二十四頁\總數(shù)九十九頁\編于十七點(diǎn)246x1x2246(1,2)無界解(無最優(yōu)解)maxZ=x1+2x2例8目前二十五頁\總數(shù)九十九頁\編于十七點(diǎn)x1x2O10203040102030405050無可行解即無最優(yōu)解maxZ=10x1+4x2例9目前二十六頁\總數(shù)九十九頁\編于十七點(diǎn)由以上例題可知，線性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例5,例6)2.有多重解(例7)3.有無界解(例8)4.無可行解(例9)1、2情形為有最優(yōu)解3、4情形為無最優(yōu)解目前二十七頁\總數(shù)九十九頁\編于十七點(diǎn)四.凸集(convexset)目前二十八頁\總數(shù)九十九頁\編于十七點(diǎn)可行域的性質(zhì)線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解在極點(diǎn)上凸集凸集不是凸集極點(diǎn)目前二十九頁\總數(shù)九十九頁\編于十七點(diǎn)目前三十頁\總數(shù)九十九頁\編于十七點(diǎn)目前三十一頁\總數(shù)九十九頁\編于十七點(diǎn)目前三十二頁\總數(shù)九十九頁\編于十七點(diǎn)目前三十三頁\總數(shù)九十九頁\編于十七點(diǎn)六.單純形法（Simplexmethods）(Dantzing,1947)單純形法是求解線性規(guī)劃問題的一種有效算法。其基本思想是根據(jù)線性規(guī)劃問題的標(biāo)準(zhǔn)形，先求出一個(gè)基可行解，判別是否為最優(yōu)解，若不是，再轉(zhuǎn)換到另一基可行解，并使目標(biāo)函數(shù)值減小，重復(fù)上述過程，直到求出最優(yōu)解。下面來分析說明、

目前三十四頁\總數(shù)九十九頁\編于十七點(diǎn)引入松馳變量并將該問題化為標(biāo)準(zhǔn)形LP：

目前三十五頁\總數(shù)九十九頁\編于十七點(diǎn)，為其基，為基變量；，令非基變量得基可行解目標(biāo)函數(shù)值為。目前三十六頁\總數(shù)九十九頁\編于十七點(diǎn)目前三十七頁\總數(shù)九十九頁\編于十七點(diǎn)目前三十八頁\總數(shù)九十九頁\編于十七點(diǎn)目前三十九頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十一頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十二頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十三頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十四頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十五頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十六頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十七頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十八頁\總數(shù)九十九頁\編于十七點(diǎn)目前四十九頁\總數(shù)九十九頁\編于十七點(diǎn)目前五十頁\總數(shù)九十九頁\編于十七點(diǎn)2.9m鋼筋架子1002.1m各100，原料長(zhǎng)7.4m1.5m

ⅠⅡⅢⅣⅤ2.9m120102.1m002211.5m31203

合計(jì)

7.47.37.27.16.6

料頭00.10.20.30.8例3、合理下料問題目前五十一頁\總數(shù)九十九頁\編于十七點(diǎn)解：設(shè)按第i種方案下料的原材料為xi根minZ=0.1x2

+0.2x3+0.3x4+0.8x5x1+2x2+x4=1002x3+2x4+x5=100

3x1+x2+2x3+3x5=100

xi

0(i=1,…,5)，且為整數(shù)目前五十二頁\總數(shù)九十九頁\編于十七點(diǎn)例4、運(yùn)輸問題工廠/倉庫123庫存

121350222430334210

需求401535目前五十三頁\總數(shù)九十九頁\編于十七點(diǎn)設(shè)xij為i

倉庫運(yùn)到j(luò)工廠的原棉數(shù)量(i

＝1，2，3，j＝1，2，3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13

50x21+x22+x23

30x31+x32+x33

10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij

0目前五十四頁\總數(shù)九十九頁\編于十七點(diǎn)八.對(duì)偶理論與靈敏度分析一、LP的對(duì)偶問題

1.引例

生產(chǎn)計(jì)劃問題是一個(gè)在有限資源的條件下，求使利潤(rùn)最大的生產(chǎn)計(jì)劃安排問題，其數(shù)學(xué)模型為：

現(xiàn)從另一角度考慮此問題。假設(shè)有客戶提出要求，租賃工廠的工時(shí)和購買工廠的材料，為其加工生產(chǎn)別的產(chǎn)品，由客戶支付工時(shí)費(fèi)和材料費(fèi)，此時(shí)工廠應(yīng)考慮如何為每種資源定價(jià)，同樣使其獲得的利潤(rùn)最大？目前五十五頁\總數(shù)九十九頁\編于十七點(diǎn)解:1)決策變量：設(shè)y1,y2分別表示出售單位原材料的價(jià)格（含附加值）和出租設(shè)備單位工時(shí)的租金

3)約束條件:工廠決策者考慮：（1）出售原材料和出租設(shè)備應(yīng)不少于自己生產(chǎn)產(chǎn)品的獲利，否則不如自己生產(chǎn)為好。因此有2）目標(biāo)函數(shù)：此時(shí)工廠的總收入為W=24y1+26y2,這也是租賃方需要付出的成本.而在這個(gè)問題中,是企業(yè)不生產(chǎn),將自己的資源出售或出租,因此,此時(shí),起決定作用的是租賃方,所以此時(shí)的目標(biāo)函數(shù)為

MinW=24y1+26y2目前五十六頁\總數(shù)九十九頁\編于十七點(diǎn)2）價(jià)格應(yīng)盡量低，否則沒有競(jìng)爭(zhēng)力（此價(jià)格可成為與客戶談判的底價(jià)租賃者考慮：希望價(jià)格越低越好，否則另找他人。于是，能夠使雙方共同接受的是：

上述兩個(gè)LP問題的數(shù)學(xué)模型是在同一企業(yè)的資源狀況和生產(chǎn)條件下產(chǎn)生的，且是同一個(gè)問題從不同角度考慮所產(chǎn)生的，因此兩者密切相關(guān)。稱這兩個(gè)LP問題是互為對(duì)偶的兩個(gè)LP問題。其中一個(gè)是另一個(gè)問題的對(duì)偶問題。目前五十七頁\總數(shù)九十九頁\編于十七點(diǎn)一般地對(duì)于任何一個(gè)線性規(guī)劃問題都有一個(gè)與之相對(duì)應(yīng)的對(duì)偶問題。原問題與對(duì)偶問題的一般形式為：

原問題（LP）對(duì)偶問題（DP）相應(yīng)的矩陣形式為：目前五十八頁\總數(shù)九十九頁\編于十七點(diǎn)對(duì)稱形式的對(duì)偶問題為：（LP）（DP）二、對(duì)偶理論1.原問題與對(duì)偶問題的關(guān)系由以上兩式可知,原問題與對(duì)偶問題之間具有如下關(guān)系(1)一個(gè)問題中的約束條件個(gè)數(shù)等于它的對(duì)偶問題中的變量數(shù);(2)一個(gè)問題中目標(biāo)函數(shù)的系數(shù)是其對(duì)偶問題中約束條件的右端項(xiàng);(3)約束條件在一個(gè)問題中為“”,則在其對(duì)偶問題中為“”;(4)目標(biāo)函數(shù)在一個(gè)問題中為求最大值,在其對(duì)偶問題中則為求最小值目前五十九頁\總數(shù)九十九頁\編于十七點(diǎn)例1、寫出下列線性規(guī)劃問題的對(duì)偶問題（P27）非對(duì)稱形式的對(duì)偶問題為：（LP）（DP）目前六十頁\總數(shù)九十九頁\編于十七點(diǎn)原問題Max（對(duì)偶問題）對(duì)偶問題Min（原問題）約束條件數(shù)=m

變量個(gè)數(shù)=m第i個(gè)約束條件為“≤”第i個(gè)約束條件為“≥”第i個(gè)約束條件為“=”

第i個(gè)變量≥0

第i個(gè)變量≤0

第i個(gè)變量無限制變量個(gè)數(shù)=n

約束條件個(gè)數(shù)=n第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量無限制

第i個(gè)約束條件為“≥”第i個(gè)約束條件為“≤”第i個(gè)約束條件為“=”第i個(gè)約束條件的右端項(xiàng)目標(biāo)函第i個(gè)變量的系數(shù)

目標(biāo)函數(shù)第i個(gè)變量的系數(shù)第i個(gè)約束條件的右端頂歸納對(duì)稱形式與非對(duì)稱形式的對(duì)偶,原問題與對(duì)偶問題之間的關(guān)系如下表所示目前六十一頁\總數(shù)九十九頁\編于十七點(diǎn)2.

設(shè)

對(duì)偶問題的基本定理MaxZ=CXMinW=Yb（1）（對(duì)稱性）對(duì)偶問題的對(duì)偶是原問題；（2）（弱對(duì)偶定理）若X(0)是原問題的可行解，Y(0)是對(duì)偶問題的可行解,則有（3）（無界性）若原問題（對(duì)偶問題）為無界解，則其對(duì)偶問題（原問題）無可行解；（4）（最優(yōu)性定理），若X(0)

、Y(0)分別是互為對(duì)偶問題的可行解，且CX(0)=Y(0)b，則X(0)

、Y(0)分別是它們的最優(yōu)解（5）（強(qiáng)對(duì)偶定理）若互為對(duì)偶問題之一有最優(yōu)解，則另一問題必有最優(yōu)解，且它們的目標(biāo)函數(shù)值相等。目前六十二頁\總數(shù)九十九頁\編于十七點(diǎn)目前六十三頁\總數(shù)九十九頁\編于十七點(diǎn)三、對(duì)偶單純形法1.單純形法的重新解釋X*是最大化LP問題最優(yōu)解的充要條件是同時(shí)滿足：①（稱為原始可行條件）②（稱為對(duì)偶可行條件）因此，單純形法是在保持原始可行下，經(jīng)過迭代，逐步實(shí)現(xiàn)對(duì)偶可行，達(dá)到求出最優(yōu)解的過程。即單純形法的迭代是先保證現(xiàn)行解對(duì)原問題可行，即，然后從0到

根據(jù)對(duì)偶問題的對(duì)稱性，也可以在保持對(duì)偶可行下，經(jīng)過迭代，逐步實(shí)現(xiàn)原始可行，以求得最優(yōu)解。對(duì)偶單純形法就是根據(jù)這種思想所設(shè)計(jì)的。因此，對(duì)偶單純形法是先保證現(xiàn)行解對(duì)對(duì)偶問題可行，即，然后從0到目前六十四頁\總數(shù)九十九頁\編于十七點(diǎn)例14用對(duì)偶單純形法求解下列線性規(guī)劃問題：解：化為標(biāo)準(zhǔn)形后，用對(duì)偶單純形法求解過程如下表所示cj-12-8-16-1200CBXBby1y2y3y4y5y600y5y6-2-3-2-1-4010-2-20-401w01281612002.對(duì)偶單純形法的計(jì)算步驟：目前六十五頁\總數(shù)九十九頁\編于十七點(diǎn)cj-12-8-16-1200CBXBby1y2y3y4y5y60-12y5y4-23/4-2-1-40101/21/2010-1/4w-96216003cj-12-8-16-1200CBXBby1y2y3y4y5y600y2y42-1/42140-10-1/20-211/2-1/4w-13208023目前六十六頁\總數(shù)九十九頁\編于十七點(diǎn)cj-12-8-16-1200CBXBby1y2y3y4y5y6-8-16y2y33/21/811020-1/21/401-1/2-1/41/8w-14000442上表中常數(shù)列b所對(duì)應(yīng)的系數(shù)均為非負(fù)，已求得問題的最優(yōu)解，最優(yōu)解為y=(y1,y2,y3,y4)T=(0,3/2,1/8,0)；最優(yōu)值為z*=14注意：對(duì)偶單純形法仍是求解原問題，它是適用于當(dāng)原問題無可行基解，且所有檢驗(yàn)數(shù)均大于0的情況。若原問題既無可行基解，而檢驗(yàn)數(shù)中又有小于0的情況，只能用人工變量法求解。在計(jì)算機(jī)求解時(shí)，只有人工變量法，沒有對(duì)偶單純形法。目前六十七頁\總數(shù)九十九頁\編于十七點(diǎn)四、對(duì)偶解的經(jīng)濟(jì)含義和影子價(jià)格目前六十八頁\總數(shù)九十九頁\編于十七點(diǎn)

其含義是：若對(duì)原問題右端常數(shù)項(xiàng)向量b中的某一常數(shù)項(xiàng)bi增加一個(gè)單位，目標(biāo)函數(shù)的最優(yōu)值Z*的變化將是yi*。換句話說，yi*表示當(dāng)bi增加一個(gè)單位時(shí)，目標(biāo)函數(shù)最優(yōu)值的相應(yīng)增量。實(shí)質(zhì)上yi*就是第i種資源邊際價(jià)值的一種表現(xiàn)，也是對(duì)第i種資源的一種估價(jià)。事實(shí)上，如引例中互為對(duì)偶LP問題分別描述生產(chǎn)計(jì)劃問題和資源的定價(jià)問題，其數(shù)學(xué)模型分別是：原問題對(duì)偶問題目前六十九頁\總數(shù)九十九頁\編于十七點(diǎn)cj4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5Z36001/56/5用單純形法求得其最優(yōu)表為：由此，它們的最優(yōu)解分別是X*=(6,4)T和Y*=(1/5,6/5)

最優(yōu)值為：Z*=W*=36=24y1*+26y2*

目前七十頁\總數(shù)九十九頁\編于十七點(diǎn)

其中y1*=1/5表示單獨(dú)對(duì)材料增加1個(gè)單位，可使Z值增加1/5個(gè)單位的利潤(rùn)；y2*=6/5表示單獨(dú)對(duì)工時(shí)增加1個(gè)單位，可使Z值增加6/5個(gè)單位的利潤(rùn)。

2.影子價(jià)格的定義

把某一經(jīng)濟(jì)結(jié)構(gòu)中的某種資源，在最優(yōu)決策下的邊際價(jià)值稱為該資源在此經(jīng)濟(jì)結(jié)構(gòu)中的影子價(jià)格。影子價(jià)格是在最優(yōu)決策下對(duì)資源的一種估價(jià)，沒有最優(yōu)決策就沒有影子價(jià)格，所以影子價(jià)格又稱“最優(yōu)計(jì)劃價(jià)格”，“預(yù)測(cè)價(jià)格”等等。資源的影子價(jià)格定量的反映了單位資源在最優(yōu)生產(chǎn)方案中為總收益所做出的貢獻(xiàn)，因此，資源的影子價(jià)格也可稱為在最優(yōu)方案中投入生產(chǎn)的機(jī)會(huì)成本。目前七十一頁\總數(shù)九十九頁\編于十七點(diǎn)3、影子價(jià)格的求法資源的影子價(jià)格Y*=CBB-1，即為最優(yōu)單純形表中松馳變量對(duì)應(yīng)的檢驗(yàn)數(shù)。例如：在生產(chǎn)計(jì)劃問題中，最優(yōu)表如下cj4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5Z36001/56/5兩種資源：材料的影子價(jià)格為y1=1/5

工時(shí)的影子價(jià)格為y2=6/5目前七十二頁\總數(shù)九十九頁\編于十七點(diǎn)

（2）對(duì)市場(chǎng)資源的最優(yōu)配置起著推進(jìn)作用即在配置資源時(shí)，對(duì)于影子價(jià)格大的企業(yè)，資源優(yōu)先供給（3）可以預(yù)測(cè)產(chǎn)品的價(jià)格產(chǎn)品的機(jī)會(huì)成本為CBB-1A-C，只有當(dāng)產(chǎn)品價(jià)格定在機(jī)會(huì)成本之上，企業(yè)才有利可圖。（4）可作為同類企業(yè)經(jīng)濟(jì)效益評(píng)估指標(biāo)之一。對(duì)于資源影子價(jià)格越大的企業(yè)，資源的利用所帶來的收益就越大，經(jīng)濟(jì)效益就越好。4.影子價(jià)格的參謀作用

（1）指出企業(yè)挖潛革新的途徑影價(jià)>0，說明該資源已耗盡，成為短線資源。影價(jià)=0，說明該資源有剩余，成為長(zhǎng)線資源。目前七十三頁\總數(shù)九十九頁\編于十七點(diǎn)例題:

某化工廠有三種資源A、B、C，生產(chǎn)三種產(chǎn)品甲、乙、丙，設(shè)甲、乙、丙的產(chǎn)量分別為x1,x2,x3,其數(shù)學(xué)模型為：已解得最優(yōu)單純形表如下

CBXBbx1x2x3x4x5x6250x2x3x610023020-1/4101/2-1/403/20101/20200-211Z400120(1)求三種資源的影子價(jià)格,并解釋其經(jīng)濟(jì)含義;(2)市場(chǎng)看好，決定增加一種資源的供應(yīng)量，問應(yīng)增加哪種資源？目前七十四頁\總數(shù)九十九頁\編于十七點(diǎn)§2.5優(yōu)化后分析（靈敏度分析）面對(duì)市場(chǎng)變化，靈敏度分析的任務(wù)是須解決以下兩類問題一、當(dāng)系數(shù)A、b、C中的某個(gè)發(fā)生變化時(shí),目前的最優(yōu)基是否仍最優(yōu)（即目前的最優(yōu)生產(chǎn)方案是否要變化）?(稱為模型參數(shù)的靈敏度分析)二、增加一個(gè)變量或增加一個(gè)約束條件時(shí)，目前的最優(yōu)基是否仍最優(yōu)（即目前的最優(yōu)生產(chǎn)方案是否要變化）(稱為模型結(jié)構(gòu)的靈敏度分析)

靈敏度分析的方法是在目前最優(yōu)基B下進(jìn)行的。即當(dāng)參數(shù)A、b、c中的某一個(gè)或幾個(gè)發(fā)生變化時(shí)，考察是否影響以下兩式的成立？

目前七十五頁\總數(shù)九十九頁\編于十七點(diǎn)1、對(duì)于參數(shù)b的靈敏度分析從矩陣形式的單純形表中可以看出，b的變化只影響最優(yōu)解的變化和最優(yōu)值的變化。bXXBB-1bB-1AZCBB-1bCBB-1A-C因此，當(dāng)時(shí)，最優(yōu)基不變（即生產(chǎn)產(chǎn)品的品種不變，但數(shù)量及最優(yōu)值會(huì)變化）。是一個(gè)不等式組，從中可以解得b的變化范圍若B-1b中有小于0的分量，則需用對(duì)偶單純形法迭代，以求出新的最優(yōu)方案。目前七十六頁\總數(shù)九十九頁\編于十七點(diǎn)

例題16對(duì)于生產(chǎn)計(jì)劃問題，為使最優(yōu)方案不變，試討論第二個(gè)約束條件b2的變化范圍。cj4300CBXBbx1x2x3x4

34x2x146013/5-2/510-2/53/5Z36001/56/5解：生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型和最優(yōu)單純形表為：目前七十七頁\總數(shù)九十九頁\編于十七點(diǎn)

從矩陣形式的單純形表中可知，b2的變化只影響解的可行性B-1b≥0,因此，為使最優(yōu)解不變，只需變化以后的B-1b≥0即可。由解得：目前七十八頁\總數(shù)九十九頁\編于十七點(diǎn)若b2變化超過范圍，則需用對(duì)偶單純形法進(jìn)行求解。如b2=6，則cj4300CBXBbx1x2x3x4

34x2x112-6013/5-2/510-2/53/5Z12001/56/5將上述數(shù)字替換最優(yōu)單純形表中相應(yīng)位置的數(shù)據(jù)得：目前七十九頁\總數(shù)九十九頁\編于十七點(diǎn)cj4300CBXBbx1x2x3x4

30x2x33153/2101/2-5/201-3/2Z91/2003/2用對(duì)偶單純形法迭代，求出的最優(yōu)單純形表如下：得到新的最優(yōu)解為：x1=0,x2=3;maxz=9目前八十頁\總數(shù)九十九頁\編于十七點(diǎn)2.對(duì)價(jià)值系數(shù)Cj變化的分析（1）當(dāng)CN（非基變量的目標(biāo)函數(shù)系數(shù)）中某個(gè)Cj發(fā)生變化時(shí)，只影響到非基變量xj的檢驗(yàn)數(shù)由于所以,當(dāng)即當(dāng)時(shí),最優(yōu)解不變反之,當(dāng)時(shí),最優(yōu)解改變,需要用單純形法重新進(jìn)行迭代,以求得新的最優(yōu)解.目前八十一頁\總數(shù)九十九頁\編于十七點(diǎn)例題17對(duì)于下列線性規(guī)劃模型,為使最優(yōu)解不變，討論非基變量y1的目標(biāo)函數(shù)系數(shù)c3的變化范圍。用單純形法求得其最優(yōu)表為：cj43200CBXBbx1x2

y1x3x4

34x2x14601-1/53/5-2/5104/5-2/53/5Z36003/51/56/5目前八十二頁\總數(shù)九十九頁\編于十七點(diǎn)解：因?yàn)閥1為非基變量，其目標(biāo)函數(shù)系數(shù)c3的變化只會(huì)影響到y(tǒng)1的檢驗(yàn)數(shù)，因此為使最優(yōu)解不變，只需即若C3=3,則代入最優(yōu)單純形表中相應(yīng)位置繼續(xù)迭代以求出新的最優(yōu)解。cj43200CBXBbx1x2y1x3x4

34x2x14601-1/53/5-2/5104/5-2/53/5Z3600-2/51/56/5目前八十三頁\總數(shù)九十九頁\編于十七點(diǎn)（2）當(dāng)CB(即基變量的目標(biāo)函數(shù)系數(shù))中某個(gè)Cj發(fā)生變化時(shí)則會(huì)影響到所有變量的檢驗(yàn)數(shù)σ=CBB-1A－C解不等式組例18設(shè)基變量x1的系數(shù)C1變化為，在最優(yōu)性不變的條件下，試確定的范圍解：目前八十四頁\總數(shù)九十九頁\編于十七點(diǎn)將上述數(shù)字替換單純形表中相應(yīng)位置的數(shù)字得：cj4300CBXBbx1x2x3x4

35x2x146013/5-2/510-2/53/5Z4200-1/58/5目前八十五頁\總數(shù)九十九頁\編于十七點(diǎn)用單純形法迭代得最優(yōu)解表如下：cj4300CBXBbx1x2x3x4

05x3x120/326/305/31-2/312/301/3Z130/301/3016/15（3）技術(shù)系數(shù)aij變化的分析

第一種情況（當(dāng)jJN）：即aij為非基變量xj的技術(shù)系數(shù)時(shí)，它的變化只影響xj的系數(shù)列B-1Pj和檢驗(yàn)數(shù)，為使最優(yōu)方案不變，只需

目前八十六頁\總數(shù)九十九頁\編于十七點(diǎn)cj43200CBXBbx1x2

y1x3x4

34x2x14601-1/53/5-2/5104/5-2/53/5Z36003/51/56/5例18對(duì)于下列規(guī)劃問題的最優(yōu)解，若由于工藝改進(jìn)，y1的技術(shù)系數(shù)改為p3=(1,1)T，試討論最優(yōu)解的變化。解：最優(yōu)解改變。此時(shí)其系數(shù)列改為：目前八十七頁\總數(shù)九十九頁\編于十七點(diǎn)

第二種情況（當(dāng)jJB）：由于B中元素的改變影響到B-1的變化，因此也影響到整個(gè)單純形表T(B)的變化。目前的基B對(duì)應(yīng)的解有可能既不是原始可行，也不是對(duì)偶可行。于是不如重新求解將上述數(shù)據(jù)替換最優(yōu)表中相應(yīng)位置的數(shù)據(jù)，然后再用單純形法求得新的最優(yōu)解。cj43200CBXBbx1x2

y1x3x4

34x2x146011/53/5-2/5101/5-2/53/5Z3600-3/51/56/5目前八十八頁\總數(shù)九十九頁\編于十七點(diǎn)注意：對(duì)于參數(shù)的靈敏度分析,在計(jì)算機(jī)軟件中只有對(duì)C、b的分析,沒有對(duì)A的分析.以下是計(jì)算機(jī)軟件的靈敏度分析.1、關(guān)于參數(shù)C的靈敏度分析2、關(guān)于參數(shù)b的靈敏度分析SummarizedReportforliuPage2Constr.StatusRHSShadowPriceSlackorSurplusMinimumRHSMaximumRHS12TightTight+24.000+26.000+0.2000+1.200000+17.333+16.000+39.0000+36.0000MaximizedOBJ=36Iteration=2ElapsedCPUsecond=0SummarizedReportforliuPage1NumberVariableSolutionOpportunityCostObjectiveCoefficientMinimumObj.CoeffMaximumObj.Coeff12X1X2+6.0000+4.000000+4.0000+3.0000+2.0000+2.6666+4.5000+6.0000MaximizedOBJ=36Iteration=2ElapsedCPUsecond=0目前八十九頁\總數(shù)九十九頁\編于十七點(diǎn)（4）對(duì)增加新產(chǎn)品的分析設(shè)某企業(yè)在計(jì)劃期內(nèi)，擬議生產(chǎn)新產(chǎn)品Xn+1，并已知新產(chǎn)品的單位利潤(rùn)為Cn+1，消耗系數(shù)向量為Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此時(shí)應(yīng)如何分析才能確定該新產(chǎn)品是否值得投產(chǎn)？增加新產(chǎn)品應(yīng)在不影響企業(yè)目前計(jì)劃期內(nèi)最優(yōu)生產(chǎn)的前提下進(jìn)行。因此可從現(xiàn)行的最優(yōu)基B出發(fā)考慮：若σn+1=CBB-1Pn+1－Cn+1<0，則應(yīng)投產(chǎn)若σn+1=CBB-1Pn+1－Cn+1>0，則不應(yīng)投入。

即新產(chǎn)品的機(jī)會(huì)成本小于目前的市場(chǎng)價(jià)格時(shí)，應(yīng)投產(chǎn)否則不應(yīng)投產(chǎn)。例19現(xiàn)有一新產(chǎn)品丙，經(jīng)預(yù)測(cè)其單位利潤(rùn)為3，技術(shù)消耗系數(shù)為P5=（2，2）T，問該產(chǎn)品是否值得投產(chǎn)？目前九十頁\總數(shù)九十九頁\編于十七點(diǎn)解：值得投產(chǎn)。cj43003CBXBbx1x2x3x4

y5

34x2x146013/5-2/52/510-2/53/52/5Z36001/56/5-1/5將此變量加入最優(yōu)單純形表中得：其系數(shù)列為：目前九十一頁\總數(shù)九十九頁\編于十七點(diǎn)

在企業(yè)生產(chǎn)過程中，經(jīng)常有新情況發(fā)生，造成原本不緊缺的某種資源變成為緊缺資源，對(duì)生產(chǎn)計(jì)劃造成影響，如水、電和資源的供應(yīng)不足等，對(duì)生產(chǎn)過程提出了新約束等。對(duì)增加新約束條件的分析方法步驟是：（5）對(duì)增加新約束條件的分析cj43003CBXBbx1x2x3x4y5

34y5x110205/23/2-111-1-110Z3801/21/210用單純形法迭代求得最優(yōu)解為：目前九十二頁\總數(shù)九十九頁\編于十七點(diǎn)

第一步：將目前的最優(yōu)解代入新增加的約束，若能滿足約束條件，則說明新增約束對(duì)目前的最優(yōu)解（即最優(yōu)生產(chǎn)方案）不構(gòu)成影響（稱此約束為不起作用約束），可暫時(shí)不考慮新增約束條件。否則轉(zhuǎn)下一步；第二步：把新增約束添加到原問題最終表中，并作初等行變換，構(gòu)成對(duì)偶可行的單純形表，并用對(duì)偶單純形法迭代，求出新的最優(yōu)解。例19對(duì)于生產(chǎn)計(jì)劃問題，設(shè)增加電力約束，生產(chǎn)1單位甲產(chǎn)品需耗電3個(gè)單位，生產(chǎn)1單位乙產(chǎn)品需耗電4個(gè)單位，且每天供電量不超過30單位。試分析此時(shí)最優(yōu)解的變化情況。目前九十三頁\總數(shù)九十九頁\編于十七點(diǎn)

解：將最優(yōu)解x1=6,x2=4代入約束條件，不滿足，說明約束條件起作用。將約束條件加入松馳變量，化為等式，加入最優(yōu)單純形表中。cj43000

CBXBbx1x2x3x4

x5340x2x1x54630013/5-2/50102/53/50

3

4

0

0

1Z36001/56/50在這個(gè)表中，由于x1,x2是基變量，必須為單位向量，因此將x1,x2化為單位向量得目前九十四頁\總數(shù)九十九頁\編于十七點(diǎn)cj43000