OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好1

OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2024/3/24OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]第一章緒論1.1題解Operations漢語翻譯工作、操作、行動、手術(shù)、運算OperationsResearch日本——運用學(xué)港臺——作業(yè)研究中國大陸——運籌學(xué)OperationalResearch原來名稱，意為軍事行動研究——歷史淵源OR12OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]緒論1.2運籌學(xué)的歷史早期運籌思想：田忌賽馬丁渭修宮沈括運糧Erlang1917排隊論Harris1920存儲論Levinson1930零售貿(mào)易康脫洛維奇1939LP

OR13OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]緒論1.2運籌學(xué)的歷史軍事運籌學(xué)階段德軍空襲防空系統(tǒng)Blackett運輸船編隊空襲逃避深水炸彈轟炸機編隊OR14OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]緒論1.2運籌學(xué)的歷史管理運籌學(xué)階段戰(zhàn)后人員三分:軍隊、大學(xué)、企業(yè)大學(xué)：課程、專業(yè)、碩士、博士企業(yè)：美國鋼鐵聯(lián)合公司英國國家煤炭局運籌學(xué)在中國：50年代中期引入華羅庚推廣優(yōu)選法、統(tǒng)籌法中國郵遞員問題、運輸問題

OR15OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]1.3學(xué)科性質(zhì)應(yīng)用學(xué)科Morse&Kimball定義：運籌學(xué)是為決策機構(gòu)在對其控制的業(yè)務(wù)活動進行決策時提供的數(shù)量化為基礎(chǔ)的科學(xué)方法。Churchman定義：運籌學(xué)是應(yīng)用科學(xué)的方法、技術(shù)和工具，來處理一個系統(tǒng)運行中的問題，使系統(tǒng)控制得到最優(yōu)的解決方法。中國定義：運籌學(xué)是應(yīng)用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。OR16OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]1.4定性與定量例：店主進貨兩者都是常用的決策方法定性是基礎(chǔ)，定量是工具，定量為定性服務(wù)。定性有主觀性也有有效性，定量有科學(xué)性也有局限性。管理科學(xué)的發(fā)展，定量越來越多。但定量不可替代定性。OR17OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]1.5運籌學(xué)的模型模型：真實事物的模仿，主要因素、相互關(guān)系、系統(tǒng)結(jié)構(gòu)。形象模型：如地球儀、沙盤、風(fēng)洞模擬模型：建港口，模擬船只到達。學(xué)生模擬企業(yè)管理系統(tǒng)運行。數(shù)學(xué)模型：用符號或數(shù)學(xué)工具描述現(xiàn)實系統(tǒng)。V=F（xi,yj,uk)G(xi,yj,uk)≥0OR18OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]1.6運籌學(xué)的學(xué)科體系規(guī)劃論：線性規(guī)劃、非線性規(guī)劃|、整數(shù)規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃圖論與網(wǎng)絡(luò)存儲論排隊論決策論對策論計算機仿真OR19OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]1.7運籌學(xué)的工作步驟確定問題搜集數(shù)據(jù)建立模型檢驗?zāi)Ｐ颓蠼饽Ｐ徒Y(jié)果分析結(jié)果實施OR110OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]1.8運籌學(xué)與計算機計算機為運籌學(xué)提供解題工具。本書有現(xiàn)成的程序可以利用要學(xué)會解題的思路與方法，建立模型很重要。OR111OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]第二章線性規(guī)劃與單純形法2.1LP(linearprogramming)的基本概念LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟效益的優(yōu)化方法。LP有一組有待決策的變量，一個線性的目標函數(shù)，一組線性的約束條件。OR112OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.1.1LP的數(shù)學(xué)模型

例題1—生產(chǎn)計劃問題某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動力設(shè)備原材料9434510360200300利潤元/kg70120OR113OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例題1建模問題：如何安排生產(chǎn)計劃，使得獲利最多？步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg2、確定目標函數(shù)：maxZ=70X1+120X23、確定約束條件：人力約束9X1+4X2≤360設(shè)備約束4X1+5X2

≤200原材料約束3X1+10X2

≤300

非負性約束X1≥0X2≥0OR114OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例題2——配方問題養(yǎng)海貍鼠飼料中營養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：飼料VaVbVc價格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495營養(yǎng)要求70030200OR115OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例題2建模設(shè)抓取飼料Ix1kg;飼料IIx2kg;飼料IIIx3kg……目標函數(shù)：最省錢minZ=2x1+7x2+4x3+9x4+5x5約束條件：3x2+2x2+x3+6x4+18x5≥700營養(yǎng)要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1

≤50,x2≤60,x3≤50,x4≤70,x5≤40非負性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0OR116OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例題3：人員安排問題醫(yī)院護士24小時值班，每次值班8小時。不同時段需要的護士人數(shù)不等。據(jù)統(tǒng)計：

序號時段最少人數(shù)安排人數(shù)106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6OR117OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例題3建模目標函數(shù)：minZ=x1+x2+x3+x4+x5+x6約束條件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30非負性約束：xj

≥0,j=1,2,…6OR118OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]歸納：線性規(guī)劃的一般模式目標函數(shù)：max(min)Z=c1x1+c2x2+c3x3+…+cnxn約束條件：a11x1+a12x2+a13x3+…+a1nxn≤(=≥)b1

a21x1+a22x2+a23x3+…+a2nxn

≤(=≥)b2

…………am1x1+am2x2+am3x3+…+amnxn

≤(=≥)bn非負性約束：x1

≥0,x2≥0,…,xn≥0OR119OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.1.2線性規(guī)劃圖解法由中學(xué)知識可知：y=ax+b是一條直線，同理：Z=70x1+120x2→x2=70/120x1-Z/120也是一條直線，以Z為參數(shù)的一族等值線。9x1+4x2

≤360→x1≤360/9-4/9x2

是直線x1=360/9-4/9x2下方的半平面。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點，就是滿足所有約束條件的解，稱之為可行解。OR120OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例1圖示.9080604020020406080100x1

x29x1+4x2

≤3604x1+5x2

≤2003x1+10x2

≤300ABCDEFGHIZ=70x1+120x2OR121OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]概念概念：1、可行解：滿足所有約束條件的解。2、可行域：即可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。3、基解：約束條件的交點稱為基解（直觀）4、基可行解：基解當(dāng)中的可行解。5、凸集：集合內(nèi)任意兩點的連線上的點均屬于這個集合。如：實心球、三角形OR122OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]結(jié)論可行域是個凸集可行域有有限個頂點最優(yōu)值在可行域的頂點上達到無窮多解的情形無界解情形無解情形OR123OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.1.3線性規(guī)劃的標準型代數(shù)式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj

≥0j=1,2,…,nOR124OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]線性規(guī)劃的標準型和式：maxZ=∑cjxj

∑aijxj=bii=1,2,…,mxj≥0

j=1,2,…,nj=1nnj=1OR125OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]線性規(guī)劃的標準型向量式：maxZ=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,nC=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=1OR126OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]線性規(guī)劃的標準型矩陣式：maxZ=CXAX=bX≥0

其中：b=(b1,b2,…,bm)T

a11

a12….a1nA=a21

a22…a2n………

am1

am2…amnOR127OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]標準型的特征目標函數(shù)極大化約束條件為等式?jīng)Q策變量非負OR128OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]非標準型轉(zhuǎn)化為標準型目標函數(shù)極小化轉(zhuǎn)為極大化：minZ=－max(－Z)，一個數(shù)的極小化等價于其相反數(shù)的極大化。不等式約束的轉(zhuǎn)化：∑aijxj≤bi加入松弛變量

∑aijxj≥bi減去剩余變量非正變量：即xk

≤0則令x’k=－xk

自由變量：即xk無約束，令xk=x’k－x”kOR129OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]非標準型轉(zhuǎn)化舉例之一maxZ=70X1+120X2maxZ=70X1+120X29X1+4X2≤3609X1+4X2+X3=3604X1+5X2

≤2004X1+5X2+x4=2003X1+10X2

≤3003X1+10X2+x5=300

X1≥0X2≥0Xj≥0j=1,2,…,5OR130OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]非標準型轉(zhuǎn)化舉例之二minZ=x1+2x2-3x3maxZ’=x’1－2x2+3(x’3－x”3)

x1+x2+x3

≤9－x’1+x2+x’3－x”3+x4=9-x1-2x2+x3≥2x’1－2x2+x’3－x”3-x5=23x1+x2-3x3=5－3x’1+x2－3(x’3－

x”3

)=5x1≤0x2≥0x3無約束

x’1≥0x2≥0x’3≥0x”3≥0x4≥0

x5≥0

OR131OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.1.4基可行解基的概念：如前所述LP標準型和式：maxZ=∑cjxj

∑aijxj=bi

xj

≥0

j=1,2,…,n

矩陣式：maxZ=CXAX=bX≥0

約束方程的系數(shù)矩陣A的秩為m，且m<n。設(shè)A=B+N，B是A中m

m階非奇異子矩陣，則稱B是LP的一個基，即：B是A中m個線性無關(guān)向量組。nj=1nj=1OR132OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]基解的概念不失一般性,設(shè)B是A的前m列,即B=(p1,p2,…,pm）,其相對應(yīng)的變量XB=(x1,x2,…,xm)T,稱為基變量；其余變量XN=(Xm+1,…,Xn)T稱為非基變量。令所有非基變量等于零,則X=（x1,x2,…xm,0,…,0)T稱為基解。OR133OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]基可行解的概念基可行解：基解可正可負，負則不可行（違背非負性約束條件），稱滿足所有約束條件的基解為基可行解。退化的基可行解：若某個基變量取值為零，則稱之為退化的基可行解?；獾臄?shù)目：最多Cmn=n!/m!(n-m)!OR134OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例題6基可行解說明

maxZ=70X1+120X2P1P2P3P4P5

9X1+4X2+X3=36094100

4X1+5X2+x4=200A=45010

3X1+10X2+x5=300310001

Xj≥0j=1,2,…,5這里m=3,n=5。Cmn=10OR135OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]例題6基可行解說明基（p3,p4,p5）

，令非基變量x1,x2=0，則基變量x3=360,x4=200,x5=300,可行解基（p2,p4,p5）,令非基變量x1=0,x3=0基變量x2=90,x4=－250,x5=－600.非可行解基（p2,p3,p4），令非基變量x1,x5=0，則基變量x2=30,x3=240,x4=50,可行解（P21圖）OR136OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.2單純形法2.2.1初始基可行解的確定從系數(shù)矩陣中找到一個可行基B，不妨設(shè)B由A的前m列組成，即B=(P1,P2,……Pm)。進行等價變換－－約束方程兩端分別左乘B－1得X1++a’1m+1xm+1+…+a’1nxn=b’1

x2++a’2m+1xm+1+…+a’2nxn=b’2……………..

xm+a’mm+1xm+1+…+a’mnxn=b’m令非基變量為0，得基可行解X(0)=(b1’，b2’，……bm，0，……0）Tz0=∑cibi’OR137OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.2單純形法2.2.2最優(yōu)性檢驗：LP經(jīng)過若干步迭代，成為如下形式：X1++a’1m+1xm+1+…+a’1nxn=b’1

x1=b’1-∑

a’1jxj

x2++a’2m+1xm+1+…+a’2nxn=b’2x2=b’2-∑a’2jxj……………..……………..

xm+a’mm+1xm+1+…+a’mnxn=b’mxm=b’m-∑a’mjxjOR138OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]單純形法一般性表示：xi=b’i-∑a’ijxji=1,2,…m將xi代入目標函數(shù)得：Z=∑cjxj=∑

cixi+∑

cjxj

=∑ci（b’i-∑a’ijxj）+∑

cjxj=∑cibi’+∑(cj-∑

cia’ij)xj令：σj=cj-∑

cia’ijz0=∑cibi’則Z=z0+∑σjxj

σj判別準則：

σj≤0

時,達到最優(yōu)解OR139OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]單純形法2.2.2基變換若存在σj≥0，則取max{σj

}=σK

，相應(yīng)之非基變量XK若取非零，將使Z增加,故令XK進基。令XK≠0，其余非基變量保持為零。XK原是非基變量，取零值，若XK

≠0將迫使某個原基變量為零，當(dāng)XK取值超過任意b’i/a’ik

時,將破壞非負性條件,于是令θ=min{b’i/a’ika’ik>0}=b’L/a’Lk。這時原基變量XL=0，由基變量變成非基變量，a’Lk處在變量轉(zhuǎn)換的交叉點上，稱之為樞軸元素σj≥0OR140OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]單純形法解題舉例單純形表的格式：CjC1C2…Cn

θiCBXBbx1

x2….xn

C1C2

…Cmx1x2…xmb1b2…bma11a12…a1na21a22…a2n………am1am2…amnθ1θ2…θm

σjσ1σ2…σnOR141OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]CjC1C2…CnCBXBbX1

X2

X3X4X5θj000X3X4X536020030094100

45010310001904030σj0

7012000000120X3X4X224050

307.8010-0.42.5001-0.50.31000.130.7620100σj360034000-12701200X3X1X2842024001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.2OR142OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.2.3單純形法的計算步驟

找到初始可行基，建立單純形表計算檢驗數(shù)，若所有σj≤0

則得最優(yōu)解，結(jié)束。否則轉(zhuǎn)下步若某σK

≥0而P’K≤0，則最優(yōu)解無界，結(jié)束。否則轉(zhuǎn)下步根據(jù)max{σj

}=

σK原則確定XK

進基變量；根據(jù)θ規(guī)則：θ=min{b’i/a’ika’ik

>0}=b’L/a’Lk確定XL為出基變量以a’Lk

為樞軸元素進行迭代，回到第二步OR143OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.3單純形法的進一步探討2.3.1極小化問題直接求解：檢驗數(shù)的判別由所有σj≤0

即為最優(yōu)，變?yōu)樗笑襧≥0則為最優(yōu)。人工變量法之一：大M法人工變量價值系數(shù)M例人工變量法之二：構(gòu)造目標函數(shù)，分階段求解例2.3.2無窮多最優(yōu)解情形：非基變量檢驗數(shù)σj=02.3.3退化解的情形：有兩個以上θ值相等OR144OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.3.4單純形法的計算機求解程序說明應(yīng)用舉例例題1例題2OR145OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]2.5LP應(yīng)用舉例之一例13合理下料問題料長7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？關(guān)鍵：設(shè)變量。方案料型123456782.9米2.1米1.5米120101000022113031203104合計殘料7.47.37.27.16.66.56.36.000.10.20.30.80.91.11.4OR146OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]應(yīng)用舉例之二例14混合配方問題A、B、C、D四種原料配制三種產(chǎn)品，三類約束：技術(shù)要求、原料限量、市場容量。已知產(chǎn)品價格和原料價格，求利潤最大的配方。關(guān)鍵：設(shè)變量。OR147OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]應(yīng)用舉例之三例15.滾動投資問題茲有100萬元閑錢，投資方向有四：

第四年第一年第二年第三年A項目110%B項目135%C項目125%D項目104%第五年各年投資什么項目，使第五年末資本總額為最大？OR148OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]應(yīng)用舉例之四例16動態(tài)生產(chǎn)計劃問題工廠做n個月的生產(chǎn)計劃，第j月需求量dj、正常生產(chǎn)能力aj、加班生產(chǎn)能力bj、正常生產(chǎn)成本cj、加班生產(chǎn)成本ej、庫存能力為I、庫存費用hj，設(shè)期初、期末庫存為零。求費用最小的生產(chǎn)計劃。設(shè)第月正常生產(chǎn)xj件，加班生產(chǎn)件yj，存儲zj件。則：本期生產(chǎn)+上期庫存-本期庫存=本期需求OR149OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]第三章對偶問題與靈敏度分析要求：了解LP對偶問題的實際背景了解對偶問題的建立規(guī)則與基本性質(zhì)掌握對偶最優(yōu)解的計算及其經(jīng)濟解釋掌握LP的靈敏度分析理解計算機輸出的影子價格與靈敏度分析的內(nèi)容OR150OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]3.1對偶問題3.1.1對偶問題的提出回顧例題1：現(xiàn)在A、B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的價格底線是什么？產(chǎn)品A產(chǎn)品B資源限制勞動力設(shè)備原材料9434510360200300單位利潤70120OR151OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]對偶模型設(shè)每個工時收費Y1元，設(shè)備臺時費用Y2元，原材料附加費Y3元。出租收入不低于生產(chǎn)收入：9y1+4y2+3y3≥704y1+5y2+10y3

≥120目標：ω=360y1+200y2+300y3出租收入越多越好？至少不低于某數(shù)OR152OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]原問題與對偶問題之比較原問題：對偶問題：maxZ=70X1+120X2minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3

≥70

4X1+5X2

≤200(3.1)4y1+5y2+10y3

≥120(3.2)3X1+10X2

≤300y1≥0,

y2≥0,

y3≥0X1≥0X2≥0OR153OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]3.1.2對偶規(guī)則原問題一般模型：對偶問題一般模型：maxZ=CXminω=YbAX

≤bYA≥CX≥0Y≥0OR154OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]對偶規(guī)則原問題有m個約束條件，對偶問題有m個變量原問題有n個變量，對偶問題有n個約束條件原問題的價值系數(shù)對應(yīng)對偶問題的右端項原問題的右端項對應(yīng)對偶問題的價值系數(shù)原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣原問題的約束條件與對偶問題方向相反原問題與對偶問題優(yōu)化方向相反OR155OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]對偶規(guī)則.原問題對偶問題目標函數(shù)maxmin目標函數(shù)約束條件

≤

≥=≥變量≤無約束

≥變量符號≤

無約束≥

≤約束條件=OR156OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]對偶規(guī)則簡捷記法原問題標準則對偶問題標準原問題不標準則對偶問題不標準例題2maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3

≤32x1+x2-4x3+x4+3x5

≥7y1+3y3≤2x1+2x3-x4≤

4-4y1+2y2

≤-6-x1+3x2-x4+x5=-2y1-y2-y3

≥

0x1，x2，x3

≥0;3y1+y3=1x4≤

0;x5無限制y1

≥0y2≤0y3

無約束

OR157OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]3.1.3對偶問題的基本性質(zhì)對稱性：對偶問題的對偶問題是原問題弱對偶性：極大化原問題的任一可行解的目標函數(shù)值，不大于其對偶問題任意可行解的目標函數(shù)值(鞍型圖)無界性：原問題無界，對偶問題無可行解對偶定理：若一個問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標函數(shù)值相等。若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-1OR158OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]3.1.4對偶最優(yōu)解的經(jīng)濟解釋—影子價格Z=ω=CX=Yb

Z/

b=(Yb)’=YZ=Yb=∑yibi的意義：Y是檢驗數(shù)的反數(shù)。在Y確定的前提下，每增加一個單位的i種資源，對目標函數(shù)的貢獻。結(jié)合例題1講解影子價格：y1=0:第一種資源過剩y2=13.6：設(shè)備臺時最緊張，每增加一個臺時，利潤增加13.6元。y3=5.2…影子價格所含有的信息：1、資源緊缺狀況2、確定資源轉(zhuǎn)讓基價參見：P403、取得緊缺資源的代價OR159OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]3.2靈敏度分析為什么進行靈敏度分析？靈敏度分析的兩把尺子：

σj=Cj-CBB-1pj≤0；

xB=B-1b≥03.2.1價值系數(shù)的靈敏度分析

Cj變化到什么程度可以保持最優(yōu)基不變？用

（參看P96）例題4：87.5≤C2≤233.33；36≤C1

≤96OR160OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]靈敏度分析右端項的靈敏度分析：bi變化到什么程度可以保持最優(yōu)基不變？用尺度

xB=B-1b≥0例題5：1

-3.12

1.16360

B-1b=00.4-0.2200≥00-0.120.16b3b3的變化范圍：227.586≤b3≤400OR161OPERATIONSRESEARCH運籌學(xué)怎樣把事情做到最好[1]其它形式的靈敏度分析

新產(chǎn)品的分析：