運(yùn)籌學(xué)第二章電子講稿

運(yùn)籌學(xué)第二章電子講稿第1頁，課件共58頁，創(chuàng)作于2023年2月XB=B-1b-B-1NXNΖ=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN-CBB-1N)XN單純形表XBXNXSB-1bIB-1NB-1

-CBB-1b0CN-CBB-1N-CBB-1第2頁，課件共58頁，創(chuàng)作于2023年2月§3.對偶問題的提出原問題：有n種食物，每種食物含有m種營養(yǎng)成分，第j種食物每個單位含第i種營養(yǎng)成分為aij單位?，F(xiàn)知每人每天需要第i種營養(yǎng)成分為bi單位，第j種食物的單價(jià)為cj。試問一個消費(fèi)者如何選購食物，才能使得既滿足需要，又花費(fèi)最小？問題歸結(jié)為minCXs.t.AX≥bX≥0第3頁，課件共58頁，創(chuàng)作于2023年2月xj—選購第j種食物的數(shù)量（單位）對偶問題：設(shè)有一個制造商，要生產(chǎn)m種不同的藥丸來代替上述n種不同的食物。試問每種藥丸的價(jià)格如何確定，才能獲利最大？設(shè)第i種藥丸的價(jià)格為yimaxw=YbYA≤CY≥0第4頁，課件共58頁，創(chuàng)作于2023年2月§4.線性規(guī)劃的對偶理論4.1.原問題與對偶問題的關(guān)系原問題(P)maxΖ=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…a1nxn≤b1a21x1+a22x2+…a2nxn≤b2┆┆┆┆┆am1x1+am2x2+…amnxn≤bmxj≥0,j=1,2,…,n第5頁，課件共58頁，創(chuàng)作于2023年2月(P)maxΖ=CXAX≤bX≥0對偶問題(D)minω=b1y1+b2y2+…+bmyms.t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2┆┆┆┆┆a1ny1+a2ny2+…+amnym≥cnyi≥0,i=1,2,…,m第6頁，課件共58頁，創(chuàng)作于2023年2月(D)minω=YbYA≥CY≥0x1x2

…xny1a11a12…a1nb1

y2a21a22…a2nb2

┆┆┆┆┆ymam1am2…amnbmc1c2…cn

≤≥maxmin第7頁，課件共58頁，創(chuàng)作于2023年2月

例寫出下面問題的對偶問題maxΖ=8x1+9x2s.t.4x1+x2≤52x1+3x2≤6x1,x2≥0對偶問題是：minω=5y1+6y2s.t.4y1+2y2≥8y1+3y2≥9y1,y2≥0第8頁，課件共58頁，創(chuàng)作于2023年2月對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題maxΖ=CXs.t.AX=bX≥0其對偶問題是minω=Ybs.t.YA≥CY無非負(fù)約束[證]標(biāo)準(zhǔn)形式的線性規(guī)劃問題可以寫為第9頁，課件共58頁，創(chuàng)作于2023年2月maxΖ=CXs.t.AX≤b-AX≤-bX≥0其對偶問題為minω=Y’b-Y”bs.t.Y’A-Y”A≥CY’,Y”≥0令Y=Y’-Y”，則上述問題變?yōu)榈?0頁，課件共58頁，創(chuàng)作于2023年2月minω=Ybs.t.YA≥CY沒有限制一般，有下列結(jié)論第11頁，課件共58頁，創(chuàng)作于2023年2月原問題（對偶問題）對偶問題（原問題）目標(biāo)函數(shù)maxz目標(biāo)函數(shù)minω變量n個約束條件n個≥0≥≤0≤無約束=m個m個≤約束條件≥0≥≤0=無約束變量約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)第12頁，課件共58頁，創(chuàng)作于2023年2月例maxΖ=2x1+x2+3x3+x4s.t.x1+x2+x3+x4≤52x1-x2+3x3=-4x1-x3+x4≥1x1≥0,x2,x4無約束,x3≤0minω=5y1+4y2-y3s.t.y1-2y2-y3≥2y1+y2=1y1+3y2-y3≤3y1+y3=1其對偶問題為第13頁，課件共58頁，創(chuàng)作于2023年2月y1≥0，y2無約束，y3≤0第14頁，課件共58頁，創(chuàng)作于2023年2月4.2.對偶問題的基本性質(zhì)1.對稱性：對偶問題的對偶問題是原問題。2.弱對偶性：若X和?分別為(P)，(D)的可行解，則有Ζ=CX≤?b=ω3.無界性：若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解。4.可行解是最優(yōu)解的性質(zhì)：若X,?分別是問題(P),(D)的可行解。并且CX=?b，則X,?分別為(P),(D)的最優(yōu)解。^^^^^第15頁，課件共58頁，創(chuàng)作于2023年2月5.對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。6.互補(bǔ)松馳性(松緊定理)：若X，?分別是(P),(D)問題的可行解，那么X,?為最優(yōu)解的充要條件是：

?XS=0,YSX=0(即若AiX<bi=>?i=0AiX=bi<=?i>0

?Pj=Cj<=Xj>0

?Pj>Cj=>Xj=0)^^^^^^^第16頁，課件共58頁，創(chuàng)作于2023年2月例1.求解下列線性規(guī)劃問題maxΖ=x1+2x2+3x3+4x4s.t.x1+2x2+2x3+3x4≤202x1+x2+3x3+2x4≤20xj≥0,j=1,2,3,4[解]其對偶問題為minω=20y1+20y2s.t.y1+2y2≥12y1+y2≥22y1+3y2≥33y1+2y2≥4y1,y2≥0(1.2,0.2)1212..y1y2第17頁，課件共58頁，創(chuàng)作于2023年2月用圖解法得最優(yōu)解y1=1.2,y2=0.2根據(jù)松緊定理，原問題的最優(yōu)解必滿足

?XS=0及YSX=0^及(y3,y4,y5,y6)=0x5(y1,y2)x6=0x1x2x3x4將y1=1.2,y2=0.2代入對偶問題的約束條件，得y3≠0,y4≠0,所以x1=x2=0又因y1>0,y2>0。所以x5=x6=0，即原問題為等式約束第18頁，課件共58頁，創(chuàng)作于2023年2月x1=x2=0x1+2x2+2x3+3x4=202x1+x2+3x3+2x4=20即x1=x2=0，x3=4,x4=4∴原問題的最優(yōu)解為(0,0,4,4)T7.原問題單純形表的檢驗(yàn)數(shù)行對應(yīng)其對偶問題的一個基解.其對應(yīng)關(guān)系見表：XBXNXS0CN-CBB-1N-CBB-1YS1–YS2-Y第19頁，課件共58頁，創(chuàng)作于2023年2月YS1為對應(yīng)原問題中基變量XB的剩余變量，YS2是對應(yīng)問題中非基變量XN的剩余變量。設(shè)B是原問題的一個可行基，則A=(B,N)

maxΖ=CBXB+CNXNBXB+NXN+XS=bXB,XN,XS≥0相應(yīng)地對偶問題可表示為minω=YbYB-YS1=CBYN-YS2=CNY,YS1,YS2≥0第20頁，課件共58頁，創(chuàng)作于2023年2月令Y=CBB-1，則YS1=0-YS2=CN-CBB-1N例1.maxΖ=x1+4x2+3x3s.t.2x1+2x2+x3≤4x1+2x2+2x3≤6xj≥0對偶問題為minω=4y1+6y2

s.t.

2y1+y2≥12y1+2y2≥4第21頁，課件共58頁，創(chuàng)作于2023年2月y1+2y2≥3y1,y2≥0初始單純形表為422110612201014300對偶問題的基本解為y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3其最終表為第22頁，課件共58頁，創(chuàng)作于2023年2月13/2101-1/22–101–11-10–200–1-1由原問題的最終表可知，y1=1,y2=1(最優(yōu)解)，ys1=2第23頁，課件共58頁，創(chuàng)作于2023年2月§5.對偶問題的經(jīng)濟(jì)解釋——影子價(jià)格設(shè)B是最優(yōu)基，則目標(biāo)函數(shù)的最優(yōu)值是Ζ*=CBB-1b=Y*byi*的經(jīng)濟(jì)意義是：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。影子價(jià)格：在其它數(shù)據(jù)不變的條件下，一個約束右邊的項(xiàng)增加一個單位，目標(biāo)函數(shù)第24頁，課件共58頁，創(chuàng)作于2023年2月最優(yōu)值的變化，稱為與這個約束相聯(lián)系的影子價(jià)格。在完全市場經(jīng)濟(jì)的條件下，當(dāng)某種資源的市價(jià)低于影子價(jià)格，企業(yè)應(yīng)買進(jìn)資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市價(jià)高于影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣掉，因此影子價(jià)格有調(diào)節(jié)市場的作用。第25頁，課件共58頁，創(chuàng)作于2023年2月例某工廠以一種貴重金屬為原料生產(chǎn)兩種產(chǎn)品，兩種產(chǎn)品都必須經(jīng)過粗加工和精加工兩道工序，生產(chǎn)每件A產(chǎn)品需粗加工1小時(shí)，精加工2小時(shí)，需貴金屬3克，出廠價(jià)60元，生產(chǎn)B產(chǎn)品需粗加工7小時(shí)，精加工4小時(shí)，需貴金屬2克，出廠價(jià)70元。在一個生產(chǎn)周期中，按該廠的設(shè)備和人員，粗加工能力為140，000小時(shí)，精加工能力為100，000小時(shí)，由計(jì)劃渠道供應(yīng)的貴金屬只有120公斤。每個粗加工工時(shí)的成本計(jì)為1.5元，精加工工時(shí)為2.5元，每克貴金屬成本為10元。因本廠的工人工資和設(shè)備折舊在同一個生產(chǎn)周期內(nèi)是固定第26頁，課件共58頁，創(chuàng)作于2023年2月的，所以不論產(chǎn)品多少，都以其最大加工能力的工時(shí)計(jì)入成本，而貴金屬按實(shí)際使用量計(jì)入成本。如設(shè)A、B產(chǎn)品分別生產(chǎn)x1和x2千件，則利潤可按下式計(jì)算（單位：萬元）S=6x1+7x2-[（3x1+2x2）+（141.5+102.5)]=3x1+5x2-46使得毛利最大的生產(chǎn)計(jì)劃即為如下線性規(guī)劃的最優(yōu)解：第27頁，課件共58頁，創(chuàng)作于2023年2月maxS1=3x1+5x2（S1=S+46）

s.t.x1+7x2

140(粗加工能力約束）2x1+4x2

100（精加工能力約束）3x1+2x2

120（貴金屬用量約束）

x1，x2

0用單純形法求解可得如下最優(yōu)表：XBbx1x2x3x4x5

x27.50100.375-0.25x135100-0.250.5x352.5001-2.3351.25-142.5000-1.125-0.25第28頁，課件共58頁，創(chuàng)作于2023年2月由松馳變量的檢驗(yàn)數(shù)可知：粗加工能力的影子價(jià)格為0；精加工能力的影子價(jià)格為1.125，單位是萬元/千小時(shí)；貴金屬的影子價(jià)格為0.25萬元/公斤。第29頁，課件共58頁，創(chuàng)作于2023年2月§6.對偶單純形法對偶單純形法的思想是：使對偶問題保持可行，而使原問題從非可行的基本解，逐步達(dá)到基本可行解，這樣就得到了兩個問題的最優(yōu)解。計(jì)算步驟：(1)列出初始單純形表，檢驗(yàn)b列數(shù)字，若其全部非負(fù)且檢驗(yàn)數(shù)j≤0，則已得到最優(yōu)解，停止；若b列中至少有一個負(fù)分量，且j≤0,轉(zhuǎn)(2)第30頁，課件共58頁，創(chuàng)作于2023年2月(2)按min(B-1b)i(B-1b)i<0=(B-1b)l確定換出變量xl；(3)確定換入變量若xl所在行的各系數(shù)alj≥0(j=1,2,…,n),則無可行解，停止；若alj<0，則計(jì)算θ=minj/aljalj<0=k/alkxk為換入變量。(保持對偶問題的可行性)(4)以alk為主元素，按單純形法在表中進(jìn)行迭代運(yùn)算，得新的表.轉(zhuǎn)(1)第31頁，課件共58頁，創(chuàng)作于2023年2月例.minΖ=3x1+4x2+5x3s.t.x1+2x2+3x3≥52x1+2x2+x3≥6x1,x2,x3≥0[解]引進(jìn)松馳變量，問題化為minΖ=3x1+4x2+5x3s.t.x1+2x2+3x3-x4=52x1+2x2+x3-x5=6x1,x2,x3,x4,x5≥0第32頁，課件共58頁，創(chuàng)作于2023年2月XBbx1x2x3x4x5

x4–5–1–2–310x5–6–2–2–101–3–4–500x4–20–1–5/21–1/2x13111/20–1/20–1-7/20–3/2x22015/2-11/2x1110–21–100–1–1–1所以最優(yōu)解為x1=1,x2=2,x3=0，Ζmin=11第33頁，課件共58頁，創(chuàng)作于2023年2月§7.靈敏度分析問題：①當(dāng)aij,bi,cj中的一個或幾個發(fā)生變化時(shí)，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化？②這些系數(shù)在什么范圍變化時(shí)，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變？可按下表中的幾種情況處理：原問題對偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解表中的解仍為最優(yōu)解可行解可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引入人工變量，編制新的單純形表求最優(yōu)解第34頁，課件共58頁，創(chuàng)作于2023年2月7.1資源數(shù)量變化的分析資源數(shù)量變化是指系數(shù)br發(fā)生變化，其它參數(shù)不變。原最優(yōu)解為b*=B-1bbr的變化僅引起最優(yōu)解的變化XB’=B-1b’=B-1(b+Δb)=B-1=B-1+B-1=B-1b+B-1若要所得的基還是最優(yōu)基，必須XB’≥0，而其若大于零，則得到的解必為最優(yōu)解。

b1b100

┆┆┆┆br+Δbrbr

Δbr

Δbr┆┆┆┆bmbm00第35頁，課件共58頁，創(chuàng)作于2023年2月0┆br┆

0

0a1rΔbra1r

┆┆┆B-1Δbr=airΔbr=Δbrair

┆┆┆0amrΔbramrB-1的第r列元素要XB’≥0,即要b*+B-1≥0即bi+Δbrair≥0Δbr≥-bi/air若air>0Δbr≤-bi/air若air<0max{-bi/airair>0}≤Δbr≤min{–bi/airair<0}第36頁，課件共58頁，創(chuàng)作于2023年2月例.線性規(guī)劃問題maxΖ=-x2+3x2-2x5

s.t.

x1+3x2-x3+2x5=7-2x2+4x3+x4=12-4x2+3x3+8x5+x6=10xj≥0XBbx1x2x3x4x5x6x1713–1020x4120–24100x6100–43081-1030–20第37頁，課件共58頁，創(chuàng)作于2023年2月最終表是XBbx1x2x3x4x5x6

x245/2101/104/50x351/5013/102/50x611100–1/2101-1/500–4/5–12/50B=[P2,P3,P6]5/21/100B-1=1/53/1001-1/21

第38頁，課件共58頁，創(chuàng)作于2023年2月求b2的變動范圍1/10B-12列=3/10-1/2max{-4/(1/10),-5/(3/10)}≤Δb2≤min{-11/((-1/2)}-50/3≤Δb2≤22要保持最優(yōu)基不變，則-14/3≤b2≤34若Δb2超出此范圍，則b<0可用對偶單純形法繼續(xù)求解第39頁，課件共58頁，創(chuàng)作于2023年2月例上題中，若令b2增加Δb2=30,則5/21/10003B-1Δb=1/53/10030=91–1/210-15將上式結(jié)果反映到最終表中，得下表XBbx1x2x3x4x5x6x24+35/2101/104/50x35+41/5013/102/50x611-15100-1/2101-1/500–4/5–12/50第40頁，課件共58頁，創(chuàng)作于2023年2月x68–2001–20-2XBbx1x2x3x4x5x6x231/5*100**x333/5*010**-9/5000–92/5–8/57.2.目標(biāo)函數(shù)中價(jià)值系數(shù)cj的變化分析(1)cj是非基變量xj的系數(shù)根據(jù)單純形表的矩陣表示第41頁，課件共58頁，創(chuàng)作于2023年2月B-1bIB-1N–CBB-1b0CN-CBB-1N由于CB沒有改變，故影響的僅是檢驗(yàn)數(shù)j=cj-CBB-1Pj若cj變化Δcj,要保證最優(yōu)解不變只須其檢驗(yàn)數(shù)仍小于或等于零，即

j’=cj’-CBB-1Pj=cj+Δcj-CBB-1Pj≤0或Δcj≤-(cj-CBB-1Pj)=-j第42頁，課件共58頁，創(chuàng)作于2023年2月(2)cr是基變量xr的系數(shù)在cr沒有變化時(shí),r=cr-CBB-1Pr=0若cr變化Δcr,則CB’=CB+(0,…,0,Δcr,0,…,0)CB’B-1=CBB-1+(0,…,0,Δcr,0,…，0)B-1’=C’-CB’B-1A=C’-CBB-1A-(0,…,0,Δcr,0,…,0)B-1A=C’-CBB-1A-Δcr(ar1,ar2,…,arn)B-1A的第r行元素第43頁，課件共58頁，創(chuàng)作于2023年2月j’=cj-CBB-1Pj-Δcrarj(j≠r)=j-Δcrarjr’=cr+Δcr-CBB-1Pj-Δcrarr=0若要保持原最優(yōu)解不變則必須j’≤0,即j-Δcrarj≤0即Δcr≤j/arj(若arj<0)Δcr≥j/arj(若arj>0)arj為xr所在行的各系數(shù)(j=1,…,n)第44頁，課件共58頁，創(chuàng)作于2023年2月即Δcr的變化范圍為max{j/arjarj>0}≤Δcr≤min{j/arjair<0}例.一線性規(guī)劃模型為maxΖ=9x1+8x2+50x3+19x4s.t.3x1+2x2+10x3+4x4≤182x3+1/2x4≤3xj0,j=1,2,3,4最后單純形表為第45頁，課件共58頁，創(chuàng)作于2023年2月bx1x2x3x4x5x6224/3012/3–10/3–1/2–1/310–1/64/3-4–2/300–13/3–10/3問保持現(xiàn)行解為最優(yōu)的條件下，c1,c3的變動范圍。c1為非基變量的系數(shù)Δc1≤4,-∞≤c1≤13c3為基變量的系數(shù)max≤Δc3≤min,,-10/3-4-2/3-13/34/3-1/2-1/3-1/6

第46頁，課件共58頁，創(chuàng)作于2023年2月-5/2≤Δc3≤2∴50-5/2≤c3≤50+27.3技術(shù)系數(shù)aij的變化若約束條件系數(shù)矩陣中某一元素aij變化了Δaij,且它是非基變量xj的系數(shù)向量Pj的分量原最優(yōu)解滿足j=cj-CBB-1Pj≤0aij變化Δaij后第47頁，課件共58頁，創(chuàng)作于2023年2月aij

┆Pj’=aij+Δaij

┆amj

j’=cj-CBB-1Pj’0┆=cj-CBB-1Pj-CBB-1

Δaij

┆

0第48頁，課件共58頁，創(chuàng)作于2023年2月=j-yjΔaij要使原最優(yōu)解保持不變，必須j，≤0，即j-yiΔaij≤0Δaij≥j/yiyi>0Δaij≤j/yiyi<0（1）約束條件增加一個變量(B,N,Pn+1)X=b(I,B-1N,B-1Pn+1)X=B-1b第49頁，課件共58頁，創(chuàng)作于2023年2月即B-1Pn+1為現(xiàn)行基下，xn+1在約束條件中的系數(shù)列向量。xn+1的檢驗(yàn)數(shù)為n+1=Cn+1-CBB-1Pn+1

B-1在原始單純形表的單位陣處若n+1≤0，現(xiàn)行解為最優(yōu)，否則，繼續(xù)迭代。例.某工廠計(jì)劃生產(chǎn)A,B,C三種產(chǎn)品，需要甲,乙兩種資源。資源限量、每種產(chǎn)品的單位利潤和單位產(chǎn)品的資源消耗量如下表所示，試確定使利潤最大的生產(chǎn)計(jì)劃。第50頁，課件共58頁，創(chuàng)作于2023年2月

產(chǎn)品資源ABC資源限量(噸)甲1/31/31/31乙1/34/37/33單位產(chǎn)品的利潤(元)231[解]以x1,x2,x3分別表示A,B,C三種產(chǎn)品的產(chǎn)量，則該問題的線性規(guī)劃模型如下：第51頁，課件共58頁，創(chuàng)作于2023年2月maxΖ=2x1+3x2+x3s.t.1/3x1+1/3x2+1/3x3≤11/3x1+4/3x2+7/3x3≤3x1,x2,x3≥0引入松馳變量，可得初始單純形表11/31/31/31031/31/31/30123100最終單純形表為第52頁，課件共58頁，創(chuàng)作于2023年2月110–14–12012–11-800–3–5–1假設(shè)這個工廠研制了一種新產(chǎn)品D，單位新產(chǎn)品D