運(yùn)籌學(xué)靈敏度分析課件

第六節(jié)線性規(guī)劃應(yīng)用舉例

例1：某工廠生產(chǎn)A,B兩種產(chǎn)品，均需經(jīng)過兩道工序，每種產(chǎn)品需各工序加工的時(shí)間及各工序可提供的時(shí)間如下表。生產(chǎn)產(chǎn)品B同時(shí)生產(chǎn)出副產(chǎn)品C，每生產(chǎn)一噸產(chǎn)品B可同時(shí)得到2噸產(chǎn)品C，無需費(fèi)用。出售一頓A盈利400元，B盈利1000元，C盈利300元，而生產(chǎn)要報(bào)廢的C每噸損失200元，經(jīng)預(yù)測C最大銷量為5噸，列模型決定A,B產(chǎn)量，使工廠總盈利最大。

maxZ=4X1+10X2+3X3-2X42X1+3X2≤123X1+4X2≤24X3+X4=2X2X3≤5X1,X2,X3,X4≥0

例2：某工廠生產(chǎn)的一種產(chǎn)品由四個(gè)零件一和三個(gè)零件二組成，這兩種零件要用兩種原材料，由于三個(gè)車間擁有的設(shè)備和工藝不同，每個(gè)工班原材料耗用量和零件產(chǎn)量不同，問三個(gè)車間應(yīng)各開多少工班，才能使該產(chǎn)品的配套數(shù)達(dá)到最大。分析：可控變量是什么，目標(biāo)和約束是什么每班用料數(shù)（公斤）每班產(chǎn)量（件數(shù)）A材料B材料零件一零件二一車間二車間三車間853698768594資源限量300500可控變量：三個(gè)車間工班數(shù)，目標(biāo)：產(chǎn)品配套數(shù)，約束資源約束

maxZ=y(7x1+6x2+8x3)/4≥y(5x1+9x2+4x3)/3≥y8x1+5x2+3x3≤3006x1+9x2+8x3≤500x1,x2,x3,y≥0

解先看有多少種裁料方案，再進(jìn)行組合和選擇。方案：

例3合理利用線材問題現(xiàn)要做一百套鋼管,每套要長為2.9m、2.1m和1.5m的鋼管各一根。已知原料長7.4m，問應(yīng)如何下料，使用的原料最省。

設(shè)用方案Ⅰ,Ⅱ,…,Ⅷ分別裁原料鋼管x1,x2,…,x8根,則：Minz=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4≥

1002x2+x3+3x5+2x6+x7≥100x1+x3+3x4+2x6+3x7+4x8≥100x1,x2,x3,x4,x5,x6,x7,x8≥0

例4某工廠要用三種原材料C,P,H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A,B,D。已知產(chǎn)品的規(guī)格要求、單價(jià)和原料的供應(yīng)量、單價(jià)如下表。該廠應(yīng)如何安排生產(chǎn)，能使利潤最大？

例5連續(xù)投資問題。某單位有資金10萬元，在今后5年內(nèi)可考慮下列投資項(xiàng)目，已知：項(xiàng)目A：從第1到第4年每年初可投資，并于次年末回收本利115%；項(xiàng)目B：第3年初需要投資，到第5年末回收本利125%，但最大投資額不超過4萬元；項(xiàng)目C：第2年初需要投資，到第5年末能回收本利140%，但最大投資額不超過3萬元；項(xiàng)目D：5年內(nèi)每年初可購買公債，當(dāng)年末回收本利106%。問它應(yīng)該如何安排每年的投資，使到5年末擁有的資金最多？年份項(xiàng)目一二三四五AX1AX2AX3AX4AB

X3BCX2CDX1DX2DX3DX4DX5D

x2A+x2C+x2D=1.06x1D解：每年的投資額應(yīng)不超過手中的資金。由于項(xiàng)目D每年都可投資，且當(dāng)年末就可收回。所以該單位每年必然把資金全部投出去，即投資額等于手中的資金數(shù)。設(shè)第i年投資各項(xiàng)目的資金為xiA,xib,xiC,xiD。數(shù)學(xué)模型為：

x1A+x1D=10x3A+x3B+x3D=1.15x1A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D

x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD≥0Maxz=1.15x4A+1.4x2C+1.25x3B+1.06x5D第一節(jié)改進(jìn)單純型法

需要求的幾個(gè)重要指標(biāo)，不需要完全的矩陣變換就可求得。需要求的：基可行解，θ，非基變量σ，XBB-1bB-1B-1Pk初始表為單位陣（初始基）確定主元素-Y=-CBB-1σk

求σ，確定換入變量xk,計(jì)算B-1Pk,計(jì)算θ，確定主元素，對簡化單純型表作旋轉(zhuǎn)變換簡化單純形表CjCCBXBB-1bXbAB-1bB-1AσC－CBB-1ACjCBCSCN1CBXBB-1bXBXSXN1CSXSbBEN1CBXBB-1bEB-1B-1N1σ0CS－CBB-1CN1－CBB-1N1初始表以B為基的單純形表當(dāng)XS為松弛變量時(shí)CS=0,松弛變量檢驗(yàn)數(shù)為－CBB-1

，CBB-1稱為單純形乘子CjCBCNCBXBB-1bXBXNbBNB-1bEB-1Nσ0CN－CBB-1N最優(yōu)單純形表B-1cBB

-1EO

兩規(guī)劃最優(yōu)目標(biāo)函數(shù)值相等為Z=ω=CBB-1b此時(shí)最優(yōu)解XB=B-1b，Y=CBB-1(為原規(guī)劃松弛變量在最終表中的檢驗(yàn)數(shù),即單純形乘子）原始問題maxz=C

Xs.t. AX≤b X≥0對偶問題minω=Ybs.t.YA≥C Y≥0≤maxbAC

CTATbT≥minmnmn

1、原始問題是利潤最大化的生產(chǎn)計(jì)劃問題單位產(chǎn)品的利潤（元/件）產(chǎn)品產(chǎn)量（件）總利潤（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）第三節(jié)對偶的經(jīng)濟(jì)解釋對偶問題是資源定價(jià)問題，對偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價(jià)格（ShadowPrice）影子價(jià)格為當(dāng)bi有單位增量，若原最終優(yōu)基不變，總收益Z的變化，也可以說yi是對第i種資源的一種價(jià)格估計(jì)，由于影子價(jià)格是指資源增加時(shí)對最優(yōu)收益的貢獻(xiàn)，所以又稱它為資源的機(jī)會(huì)成本或者邊際產(chǎn)出當(dāng)市場價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)該買進(jìn)資源用于擴(kuò)大生產(chǎn)，高于影子價(jià)格時(shí)，企業(yè)應(yīng)該將已有資源賣掉。影子價(jià)格的計(jì)算

例子：兩種產(chǎn)品由三種原料混合而成，A包括原料一60%，原料二40%，B包括原料一50%，原料二10%，原料三40%，原料一、二、三限量為11250,4000,6000（噸）.試建立模型，求解。A每噸25美元，B每噸10美元maxZ=25x1+10x20.6x1+0.5x2≤120000.4x1+0.1x2≤40000.4x2≤6000x1,x2≥0

一個(gè)不起作用約束的影響價(jià)格總為0,一個(gè)起作用約束的影子價(jià)格在資源在一定范圍內(nèi)變化時(shí)是不變的。這個(gè)變化范圍就是關(guān)于資源限量bi的靈敏度不起作用的約束是對最優(yōu)解而言，該約束的松弛變量的值不為0起作用的約束是是對最優(yōu)解而言，該約束的松弛變量的值為0

x2=0x1=0x3=0x4=0OABC不起作用約束,影子價(jià)格為0起作用約束，影子價(jià)格不為0第四節(jié)對偶理論

一、對偶問題的性質(zhì)1、對偶的對偶就是原始問題對偶的定義maxz=CXs.t.AX≤bX≥0minω=Ybs.t.YA≥C Y≥0對偶的定義maxω=-Ybs.t.-YA≤-C Y≥0minz’=-C

Xs.t.-AX≥-bX≥02、其他形式問題的對偶原始問題約束條件的性質(zhì)，影響對偶問題變量的性質(zhì)。原始問題變量的性質(zhì)，影響對偶問題約束條件的性質(zhì)。maxz=C

Xs.t.AX≤bX≥0minω=Ybs.t.YA≥CY≥0maxz=C

Xs.t.AX=bX≥0minω=Ybs.t.YA≥CY:unrmaxz=C

Xs.t.AX≥bX≥0minω=Ybs.t.YA≥CY≤0原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)maxZ目標(biāo)minω變量（n個(gè)）≥0≤0無約束約束（n個(gè)）≥≤=約束（m個(gè)）≤≥=變量（m個(gè)）≥0≤0無約束minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxω=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4

-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始問題變量的個(gè)數(shù)(3)等于對偶問題約束條件的個(gè)數(shù)(3)；原始問題約束條件的個(gè)數(shù)(4)等于對偶問題變量的個(gè)數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)。原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)。二、原始對偶關(guān)系1、可行解的目標(biāo)函數(shù)值之間的關(guān)系

設(shè)XF、YF分別是原始問題和對偶問題的可行解

z=C

XF≤YF

AXF≤YF

b=ω2、最優(yōu)解的目標(biāo)函數(shù)值之間的關(guān)系

設(shè)Xo、Yo分別是原始問題和對偶問題的最優(yōu)解

z=C

Xo=YoAXo=Yob=Ymaxz=CXs.t. AX+XS=b X,XS≥0minω=Ybs.t.YA-YS=C Y,YS

≥0

YSX=0Y

XS=0ATY-EYsCTmn=nXAEXsb=nmm3、基解與檢驗(yàn)數(shù)之間的關(guān)系

單純形表和對偶maxz=C

Xs.t.AX+XS=bX,XS≥0minω=Yb

s.t.YA

-YS=CY,YS≥0minω=Yb

s.t.YA

≥

CY≥0對偶問題maxz=C

Xs.t.AX≤bX≥0原始問題引進(jìn)松弛變量引進(jìn)松弛變量maxz=C

Xs.t.AX+XS=bX,XS≥0minY=Yb

s.t.YA

-YS=CY,YS≥0令Y

=CB

B-1則由YS

=YA–C得YS=

CBB-1A–C為對偶問題基解

結(jié)論：原問題單純型表的檢驗(yàn)數(shù)與其對偶問題的基解互為相反數(shù)y1...yi...ymym+1...ym+j...

yn+m

x1...xj...xnxn+1xn+ixn+m

對偶問題的變量對偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個(gè)大于0，另一個(gè)一定等于0檢驗(yàn)數(shù)與基解的對應(yīng)關(guān)系第五節(jié)對偶單純形法

把對其對偶問題運(yùn)用單純型算法的計(jì)算步驟反應(yīng)在對原問題的求解步驟上面。在原問題初始表檢驗(yàn)數(shù)≤0,B-1b為非可行解的時(shí)候可用。通常不單獨(dú)使用，運(yùn)用與靈敏度分析時(shí)候較多。如何從最優(yōu)單純形表中讀出對偶問題的解（1）

x1x2x3x4x5x6x7x5

****100x6

****010x7

****001

x1x2x3x4x5x6x7初始單純形表最優(yōu)單純形表σ****000σ-y4-y5-y6-y7-y1-y2-y3-ATYEYs-CTmn=nXAEXsb=nmmMinZ=2x1+3x2+4x3

S.t.

x1+2x2+x3≥32x1-x2+x3≥4

x1,x2,x3≥0標(biāo)準(zhǔn)化：MaxZ’=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0對偶單純形法cj34000CBXBby1y2y3y4y50y320y430y541[2]1001-101013001σ340004y210y440y511/211/200[5/2]01/210-1/203/201σ10-200和單純形法的比較

進(jìn)一步理解最優(yōu)單純形表中各元素的含義考慮問題Maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn

≤b1

a21x1+a22x2+…+a2nxn

≤b2…………

am1x1+am2x2+…+amnxn

≤bm

x1，x2，…，xn≥0引入m個(gè)松弛變量后，通過計(jì)算得到最優(yōu)單純形表。應(yīng)

-1-1能夠找到最優(yōu)基B的逆矩陣B，以及BN，檢驗(yàn)數(shù)等。

第六節(jié)靈敏度分析

A,b,C變化時(shí)對最優(yōu)解的影響，最優(yōu)解（最優(yōu)基）不變，A,b,C的變化范圍以下作圖看看C,b變化對最優(yōu)解的影響

x2=0x1=0x3=0x4=0OABCC的變化等值線斜率發(fā)生變化，旋轉(zhuǎn)

x2=0x1=0x3=0x4=0OABCb的變化約束對應(yīng)直線的截距變化，平移

思考，A的變化將如何影響最優(yōu)解。

兩類問題：一、已知變化，求新最優(yōu)解1、增廣陣(b,A)的變化。包括改變約束、增減變量，增減約束。主要充分利用原最終表信息得到一新表，在新表基礎(chǔ)上選擇適當(dāng)方法變化得新最優(yōu)解。比較原最終表B-1(b,A)新表B-1(b+Δb,A+ΔA)=B-1(b+Δb,P1+ΔP1，P2+ΔP2…Pn+ΔPn）=原最終表＋(B-1Δb,B-1ΔP1,

B-1ΔP2…B-1ΔPn）

2、C的變化僅對σ產(chǎn)生影響產(chǎn)生的新表可以分為四種情況：1）已是最優(yōu)解2）單純形法繼續(xù)求解3）對偶單純形法繼續(xù)求解4）人工變量法或保持原有最有基方法繼續(xù)求解二、未知變化，保持原最優(yōu)基，求變化范圍CjCCBXBB-1bXbAB-1bB-1AσC－CBB-1ACjC’CBXBB-1bXb’A’B-1b’B-1A’σC’－CB’

B-1A’原最終表新表原問題新問題CjC’CBXBB-1bXb+ΔbA+ΔA

B-1b+B-1ΔbB-1A+B-1ΔA

σC’－CB’

B-1A’CjC’CBXBB-1bXb+ΔbP1+ΔP1....Pn+ΔPnB-1b+B-1ΔbB-1P1+B-1Δ

P1...B-1Pn+B-1Δ

PnσC’－CB’

B-1A’價(jià)值系數(shù)C發(fā)生變化：

一、保持原最優(yōu)解，求變化范圍1、若ck是非基變量的系數(shù)：設(shè)ck變化為ck+ck

只要k’≤0，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù)

k用k’取代，繼續(xù)單純形法的表格計(jì)算。

例:MaxZ=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0

例：最優(yōu)單純形表從表中看到σ3=C3+ΔC3-（C2*a13+C1*a23）可得到ΔC3

≤9/5時(shí)，原最優(yōu)解不變。

2、若cs是基變量的系數(shù)：

例:MaxZ=2x1+3x2+0x3+0x4+0x5

S.t.

x1+2x2+x3=84x1+x4=16

4x2+x5=

12x1,x2,x3,x4,x5≥0

例、下表為最優(yōu)單純形表，考慮基變量系數(shù)c2發(fā)生變化從表中看到可得到-3≤ΔC2

≤1時(shí)，原最優(yōu)解不變。

二、已知C’，求新最優(yōu)解見書右端項(xiàng)b發(fā)生變化一、保