運籌學講義影子價格-靈敏度分析-運輸問題

影子價格1精選課件對偶最優(yōu)解的經(jīng)濟含義――影子價格

代表著當?shù)趇個右端常數(shù)增加一個單位時，最優(yōu)目標函數(shù)值的相應增量。其含義是在目前已給定的情況下，最優(yōu)目標值隨資源數(shù)量變化的變化率；其經(jīng)濟含義是為約束條件所付出的代價。

當B是原問題的最優(yōu)基時，Y=CBB-1就是影子價格向量。2精選課件ABC擁有量工時1113材料1479單件利潤233影子價格舉例3精選課件

y*1=5/3,y*2=1/3

即工時的影子價格為5/3，材料的影子價格為1/3。分析：1.y1=5/3說明在現(xiàn)有的資源限量的條件下，增加一個單位第一種資源可以給企業(yè)帶來5/3元的利潤；如果要出售該資源，其價格至少在本錢價上加5/3元。如果y1為0，那么表示增加第一種資源不會增加利潤，因為第一種資源還沒有用完。4精選課件影子價格是根據(jù)資源在生產(chǎn)中作出的奉獻而作出的估價，這種估價不是資源的市場價格。它反映了在最優(yōu)經(jīng)濟結構中，在資源得到最優(yōu)配置前提下，資源的邊際使用價值。單純形表中松弛變量所對應的檢驗數(shù)的相反數(shù)是在該經(jīng)濟結構中的影子價格，也可以說對偶問題的最優(yōu)解向量是結構中的影子價格。5精選課件定理1：在某項經(jīng)濟活動中，在資源得到最優(yōu)配置條件下，

此定理的經(jīng)濟意義：〔1〕假設生產(chǎn)一個單位第j種產(chǎn)品按消耗資源的影子價格計算的支出等于銷售一個單位該產(chǎn)品所得收入，那么可生產(chǎn)此產(chǎn)品。〔2〕如果生產(chǎn)一個單位的第j種產(chǎn)品按所消耗資源的影子價格計算的支出大于銷售一個單位該產(chǎn)品得到的收入，那么不宜生產(chǎn)此產(chǎn)品。6精選課件定理2：在某項經(jīng)濟活動中，在資源得到最優(yōu)配置條件下，〔1〕假設第種資源供大于求，即那么該項資源的影子價格為0〔2〕假設第種資源供求平衡，即那么該項資源的影子價格大于等于0。影子價格越大，說明這種資源越是相對緊缺〔根據(jù)影子價格確定資源采購,當市場價格低于影子價格，就買進資源，當市場價格高于影子價格，就賣出資源〕影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)方案下某種資源有剩余，這種資源的影子價格一定等于07精選課件例ABC擁有量工時1113材料1479單件利潤233y*1=5/3,y*2=1/3即工時的影子價格為5/3，材料的影子價格為1/3。如果目前市場上材料的價格低于1/3，那么企業(yè)可以購進材料來擴大生產(chǎn)，反之可以賣掉局部材料。如果有客戶以高于5/3的價格購置工時，那么可以出售一些工時，反之那么反8精選課件和市場價格的比較市場價格影子價格商品的價值的貨幣表現(xiàn)資源最優(yōu)利用時的邊際價值隨著市場的供求情況和有關方針，政策的變化而變化。隨著經(jīng)濟結構的變化而變化，同一資源在不同的經(jīng)濟結構中影子價格不同。它的制定含定價者的主觀因素它的形成完全由經(jīng)濟結構的客觀條件確定。它的制定是個比較復雜的過程，不存在統(tǒng)一的計算公式。它的計算是比較容易的。用單純形法求得9精選課件繼續(xù)比較任何一種商品的市場價格都不可能為0影子價格可以為0，當資源過剩是，其影子價格為0市場價格為已知數(shù)，相對比較穩(wěn)定。影子價格則有賴于資源利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務，產(chǎn)品的結構等情況發(fā)生變化，資源的影子價格也隨之改變。10精選課件例(生產(chǎn)決策問題)某工廠可以用A，B兩種原料生產(chǎn)I,II,III三種產(chǎn)品，每種產(chǎn)品需要同時用兩種原料，有關數(shù)據(jù)如下表(單位消耗與資源限制)：產(chǎn)品I產(chǎn)品II產(chǎn)品III現(xiàn)有原料/t原料A2127原料B13211單位產(chǎn)品利潤/萬元231求：(1)假設目前市場上原料A的實際價格為0.5萬元/t，工廠應如何決策？(2)假設目前市場上原料B的實際價格為0.8萬元/t，工廠應如何決策？解：建立模型，設x1,x2,x3分別表示I，II，III的生產(chǎn)量，那么模型如下：對偶問題11精選課件模型討論：假設把y1,y2當作原料A，B的定價，用兩個單位的A，1個單位的B，假設生產(chǎn)產(chǎn)品I只能賺2萬元，現(xiàn)在考慮把資源拿到市場上賣，定價y1,y2,使得2y1+y2≥2,也就是一定比生產(chǎn)產(chǎn)品I賺得多。產(chǎn)品II，III同理。亦即對偶問題的約束條件保證了資源直接在市場上出售一定不會比生產(chǎn)產(chǎn)品獲得的利潤低，另一方面，為了增強出售資源的市場競爭力，定價希望低一些，定價的目標是在比生產(chǎn)產(chǎn)品獲得更多利潤的前提下的最小利潤，這個定價模型就是對偶問題。如果把資源A的量由7增加到8，會導致什么結果呢？影子價格：在最有情況下，y1的值就是資源A的影子價格，所以要把影子價格與資源A的市場價格做比較，如果影子價格大于市場價格，考慮出售局部資源以獲得更大利潤，否那么，那么從市場買進該資源。12精選課件影子價格的經(jīng)濟意義：在資源得到最優(yōu)配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量。影子價格是一種靜態(tài)的資源最優(yōu)配置價格，不能表現(xiàn)資源在不同時期動態(tài)配置時的最優(yōu)價格，只反映某種資源的稀缺程度和資源與總體積極效益之間的關系，不能代替資源本身的價值。程序編寫：執(zhí)行結果如下：13精選課件說明：從紅框局部知道，A的影子的價格為0.6，B的影子價格為0.8，松弛變量的值都是0，說明約束是緊約束(約束取等號)，即資源沒有剩余，影子價格有意義必須是緊約束。影子價格是對應最優(yōu)基來說的，如果約束的改變使得最優(yōu)基發(fā)生改變，當前的影子價格也就沒有任何意義了。通過對右端項的靈敏性分析：14精選課件在最優(yōu)基不變時，A,B的右端項變化范圍分別為(4.67,22)和(3.5,21)對問題(1)0.5<0.6,應該購進原料A，擴大生產(chǎn)能力，最大購進15t，利潤增加(0.6-0.50*15=1.5萬元對于問題(2),0.8>0.6，應該售出局部原料將使利潤更大，最大售出量為3.33t,利潤將會增加(0.8-0.6)*3.33=0.66萬元15精選課件例(奶制品的加工問題)1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

制訂生產(chǎn)方案，使每天獲利最大(1)35元可買到1桶牛奶，買嗎？假設買，每天最多買多少?(2)可聘用臨時工人，付出的工資最多是每小時幾元?(3)A1的獲利增加到30元/公斤，應否改變生產(chǎn)方案？每天：16精選課件1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供給勞動時間加工能力決策變量目標函數(shù)每天獲利約束條件非負約束線性規(guī)劃模型(LP)時間480小時至多加工100公斤A1

50桶牛奶每天17精選課件max72x1+64x2st2〕x1+x2<503〕12x1+8x2<4804〕3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。模型求解18精選課件模型求解reducedcost值表示當該非基變量增加一個單位時〔其他非基變量保持不變〕目標函數(shù)減少的量(對max型問題)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解為：為了使該非基變量變成基變量，目標函數(shù)中對應系數(shù)應增加的量19精選課件OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料無剩余時間無剩余加工能力剩余40max72x1+64x2st2〕x1+x2<503〕12x1+8x2<4804〕3x1<100end三種資源“資源〞剩余為零的約束為緊約束〔有效約束〕結果解釋20精選課件OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000結果解釋最優(yōu)解下“資源〞增加1單位時“效益〞的增量時間加1單位,利潤增2影子價格35元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？2元！21精選課件RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應否改變生產(chǎn)方案x1系數(shù)由243=72增加為303=90，在允許范圍內不變！(約束條件不變)結果解釋22精選課件結果解釋RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶？(目標函數(shù)不變)注意:充分但可能不必要23精選課件靈敏度分析24精選課件在生產(chǎn)方案問題的一般形式中，A代表企業(yè)的技術狀況，b代表企業(yè)的資源狀況，而C代表企業(yè)產(chǎn)品的市場狀況，在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)方案和最大利潤由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。在實際生產(chǎn)過程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最正確的生產(chǎn)方案，而在方案實施前或實施中上述狀況發(fā)生了改變，那么決策者所關心的是目前所執(zhí)行的方案還是不是最優(yōu)，如果不是應該如何修訂原來的最優(yōu)方案。25精選課件更進一步，為了防止在各類狀況發(fā)生時，來不及隨時對其變化作出反響，即所謂“方案不如變化快〞，企業(yè)應當預先了解，當各項因素變化時，應當作出什么樣的反響。26精選課件設線性規(guī)劃問題：maxZ=CXs.t.AX=bA代表企業(yè)技術狀況b代表企業(yè)資源狀況C代表企業(yè)產(chǎn)品市場狀況〔利潤)這些因素不變的情況下，企業(yè)最優(yōu)生產(chǎn)方案和最大利潤由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。27精選課件最優(yōu)化后分析，可歸為以下兩類問題：1〕當系數(shù)A，b，C發(fā)生改變時，目前最優(yōu)基是否還最優(yōu)？2〕為保持目前最優(yōu)基還是最優(yōu)，系數(shù)A，b，C的允許變化范圍是什么？假設每次只有一種系數(shù)變化靈敏度分析包括以下五種：①目標系數(shù)C變化基變量系數(shù)發(fā)生變化；非基變量系數(shù)發(fā)生變化；②右端常數(shù)b變化③增加一個變量④增加一個約束⑤技術系數(shù)A發(fā)生變化28精選課件CBXBcjCBCN

xj

bXBTXNTCBTXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N假設B是最優(yōu)基，那么最優(yōu)表形式如下靈敏度分析總是在最優(yōu)表上進行29精選課件例2線性規(guī)劃CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/330精選課件靈敏度分析CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/331精選課件CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/33-2*〔-1〕-3*2=-132精選課件CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3價值系數(shù)CN發(fā)生改變C3C3-4如果C3>4,那么目前解不再是最優(yōu)解,應該用單純形方法繼續(xù)求解,否那么解不變。即對于C3而言,使最優(yōu)解不變的條件是C3≤4。33精選課件CBXBcj23500

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/3∞3x22012-1/31/31－Ｚ-8001-5/3-1/3價值系數(shù)CN發(fā)生改變2x1211/207/6-1/65x3101/21-1/61/6－Ｚ-90-0.50-3/2-1/234精選課件CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3價值系數(shù)CB發(fā)生改變C1-3C1C11-4/3C11/3C1-1C1-3≤0,1-4/3C1≤0,1/3C1-1≤0?≤C1≤3假設C1<3/4那么x4進基，x1出基假設3<C1那么x3或x5進基，x2出基35精選課件CBXBcj1/23300

xj

bx1x2x3x4x50x43111100x59147011/2x1110-14/3-1/33/43x22012-1/31/3∞－Ｚ-13/200-5/21/3-5/6價值系數(shù)CB發(fā)生改變0x43/43/40-3/41-1/43x29/41/417/401/4－Ｚ-27/4-1/40-9/40-3/436精選課件CBXBcj43300

xj

bx1x2x3x4x50x43111100x59147014x1110-14/3-1/3∞3x22012-1/31/33/2－Ｚ-10001-13/31/3價值系數(shù)CB發(fā)生改變4X13111100X56036-11－Ｚ-120-1-1-4037精選課件右端常數(shù)b發(fā)生改變CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3b14b1/3-33-b1/39/4≤b1≤9-3-5b1/338精選課件CBXBcj23300xj

bx1x2x3x4x50x42111100x59147012x1-1/310-14/3-1/33x27/3012-1/31/3－Ｚ-19/300-1-5/3-1/3右端常數(shù)b發(fā)生改變0X51-303-413X2211110－Ｚ-6-100-30最小比值1139精選課件右端常數(shù)b發(fā)生改變CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3b24-b2/3b2/3-13≤b2≤12-b2/3-540精選課件增加一個變量假設企業(yè)在方案期內，有新的產(chǎn)品可以生產(chǎn)，那么在知道新產(chǎn)品的單位利潤，單件資源消耗量時，可以在最優(yōu)表中補充一列，其中的前m行可以由基矩陣的逆矩陣得到，而檢驗數(shù)行也可以由與其它列相同的方法計算得到。假設檢驗數(shù)非正，那么原最優(yōu)解仍為最優(yōu)，原生產(chǎn)方案不變，不生產(chǎn)這種新產(chǎn)品；否那么，當檢驗數(shù)為正時，那么應以該變量進基，作單純形迭代，從而找出新的最優(yōu)解。41精選課件靈敏度分析例2CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33/53x22012-1/31/36－Ｚ-800-1-5/3-1/35x623x65/31/32/35x63/53/50-3/54/5-1/513x29/5-1/5111/5-3/52/50－Ｚ-42/5-2/50-3/5-11/5-1/50CBXBcj23300xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/342精選課件增加一個約束在企業(yè)的生產(chǎn)過程中，經(jīng)常有一些突發(fā)事件產(chǎn)生，造成原本不緊缺的某種資源變成為緊缺資源，對生產(chǎn)方案造成影響，所以需要增加約束條件。1〕假設把目前的最優(yōu)解代入新增加的約束，能滿足約束條件，那么說明該增加的約束對最優(yōu)解不構成影響，即不影響最優(yōu)生產(chǎn)方案的實施。2)假設當前最優(yōu)解不滿足新增加的約束，那么應把新的約束添到原問題的最優(yōu)表內新的一行中去，用對偶單純形方法來進行迭代，求出新的最優(yōu)解。43精選課件靈敏度分析例增加約束CBXBcj23300xj

bx1x2x3x4x50x43111100x59147010x65221002x1110-14/3-1/33x22012-1/31/30x6522100－Ｚ-800-1-5/3-1/30x60010010CBXBcj23300xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/344精選課件靈敏度分析增加約束CBXBcj233000xj

bx1x2x3x4x5x62x1110-14/3-1/303x22012-1/31/300x652210012x1110-14/3-1/303x22012-1/31/300x6-100-1-201－Ｚ-800-1-5/3-1/30最小比值15/645精選課件靈敏度分析A中元素改變如果N中數(shù)據(jù)改變，可以用增加一個變量來處理如果B中元素改變，那么情況較復雜，一般需要修改問題后重新求解46精選課件運輸問題問題的提出一般的運輸問題就是要解決把某種產(chǎn)品從假設干個產(chǎn)地調運到假設干個銷地，在每個產(chǎn)地的供給量與每個銷地的需求量，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。47精選課件例某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？單位運費B1B2B3產(chǎn)量A1646200A2655300銷選課件解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500設xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到以下運輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、2；j=1、2、3〕49精選課件運輸規(guī)劃問題的數(shù)學模型運輸問題的一般形式：產(chǎn)銷平衡A1、A2、…、Am表示某物資的m個產(chǎn)地；B1、B2、…、Bn表示某物質的n個銷地；ai表示產(chǎn)地Ai的產(chǎn)量；bj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到以下一般運輸量問題的模型：50精選課件變化：1〕有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等；2〕當某些運輸線路上的能力有限制時，在模型中直接參加約束條件〔等式或不等式約束)；3〕產(chǎn)銷不平衡時，可參加假想的產(chǎn)地〔銷大于產(chǎn)時〕或銷地〔產(chǎn)大于銷時〕。定理:設有m個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，那么基變量數(shù)為m+n-1。51精選課件表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質是單純形法。步驟描述方法第一步求初始基行可行解（初始調運方案）最小元素法、元素差額法、第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當非基變量的檢驗數(shù)σij全都非負時得到最優(yōu)解，若存在檢驗數(shù)σij<0，說明還沒有達到最優(yōu)，轉第三步。閉回路法和位勢法第三步調整運量，即換基，選一個變量出基，對原運量進行調整得到新的基可行解，轉入第二步52精選課件表上作業(yè)法例2某運輸資料如下表所示：單位銷地運價產(chǎn)地產(chǎn)量311310719284741059銷量3656問：應如何調運可使總運輸費用最??？53精選課件解：第1步求初始方案方法1：最小元素法根本思想是就近供給，即從運價最小的地方開始供給〔調運〕，然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2

4A39銷量365631131019274105834163354精選課件總的運輸費＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元 元素差額法對最小元素法進行了改進，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調運，否那么會增加總運費。例如下面兩種運輸方案。85102120151515510總運費是z=10×8+5×2+15×1=105最小元素法：55精選課件85102120151551510總運費z=10×5+15×2+5×1=85后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先調運x21，到后來就有可能x11≠0，這樣會使總運費增加較大，從而先調運x21，再是x22，其次是x12用元素差額法求得的根本可行解更接近最優(yōu)解，所以也稱為近似方案。56精選課件方法2：Vogel法元素差額法1〕從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量行差額A177A2

41A391銷量3656列差額251331131019274105857精選課件2〕再從差值最大的行或列中找出最小運價確定供需關系和供需數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量供給完畢或得到滿足時，劃去運價表中對應的行或列。重復1)和2)，直到找出初始解為至。B1B2B3B4產(chǎn)量行差額A177A2

41A3

91銷量3656列差額2513311310192741058558精選課件單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額71135215××59精選課件單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額7135275×××3×60精選課件單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額113515×××3×631××2該方案的總運費:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元61精選課件第2步最優(yōu)解的判別〔檢驗數(shù)的求法〕 求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為λij由第一章知，求最小值的運輸問題的最優(yōu)判別準那么是：所有非基變量的檢驗數(shù)都非負，那么運輸方案最優(yōu)求檢驗數(shù)的方法有兩種：閉回路法位勢法〔▲〕62精選課件閉回路的概念為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表63精選課件例下表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉90度與另一頂點連接，表3－3中的變量x32及x33不是閉回路的頂點，只是連線的交點。64精選課件閉回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組不能構成一條閉回路，但A中包含有閉回路

變量組變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；65精選課件可以證明，如果對閉回路的方向不加區(qū)別〔即只要起點及其他所有頂點完全相同，而不區(qū)別行進方向〕，那么以每一個非基量為起始頂點的閉回路就存在而且唯一。因此，對每一個非基變量可以找到而且只能找到唯一的一個閉回路。下表中用虛線畫出以非基變量x22為起始頂點的閉回路。66精選課件表以非基變量x22為起始頂點的閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量3[]11[]341037139[]218[]47[]4610[]539銷量365620(產(chǎn)銷平衡)A1A2A367精選課件可以計算出以非基變量x22為起始頂點的閉回路調整使總的運輸費用發(fā)生的變化為9–2+3–10+5–4＝1即總的運費增加1個單位，這就說明這個調整不能改善目標值。從上面的討論可以看出，當某個非基變量增加一個單位時，有假設干個基變量的取值受其影響。68精選課件這個過程就是尋找一個以非基變量x24為起始頂點的閉回路——{x24，x14，x13，x23}，這個閉回路的其他頂點均為基變量(對應著填上數(shù)字的格)。容易計算出上述調整使總的運輸費用發(fā)生的變化為8–10+3–2＝-1，即總的運費減少1個單位，這就說明原始方案不是最優(yōu)方案，可以進行調整以得到更好的方案。69精選課件這樣，利用單位產(chǎn)品變化〔運輸?shù)膯挝毁M用〕可計算出它們對目標函數(shù)的綜合影響，其作用與線性規(guī)劃單純形方法中的檢驗數(shù)完全相同。故也稱這個綜合影響為該非基變量對應的檢驗數(shù)。上面計算的兩個非基變量的檢驗數(shù)為24=-1，22=1。閉回路方法原理就是通過尋找閉回路來找到非基變量的檢驗數(shù)。70精選課件如果規(guī)定作為起始頂點的非基變量為第1個頂點，閉回路的其他頂點依次為第2個頂點、第3個頂點……，那么就有

ij=(閉回路上的奇數(shù)次頂點單位運費之和)-(閉回路上的偶數(shù)次頂點單位運費之和)其中ij

為非基變量的下角指標。71精選課件按上述作法，可計算出表1的所有非基變量的檢驗數(shù)，把它們填入相應位置的方括號內，如下圖。銷地產(chǎn)地B1B2B3B4產(chǎn)量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539銷量365620(產(chǎn)銷平衡)表初始基本可行解及檢驗數(shù)72精選課件顯然，當所有非基變量的檢驗數(shù)均大于或等于零時，現(xiàn)行的調運方案就是最優(yōu)方案，因為此時對現(xiàn)行方案作任何調整都將導致總的運輸費用增加。閉回路法的主要缺點是：當變量個數(shù)較多時，尋找閉回路以及計算兩方面都會產(chǎn)生困難。73精選課件用位勢法對初始方案進行最優(yōu)性檢驗：1〕由ij=Cij-〔Ui+Vj〕計算位勢Ui，Vj，因對基變量而言有ij=0，即Cij-〔Ui+Vj〕=0，令U1=0即參照系2〕再由ij=Cij-〔Ui+Vj〕計算非基變量的檢驗數(shù)ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029〔1〕〔2〕〔1〕〔-1〕〔10〕〔12〕當存在非基變量的檢驗數(shù)kl≥0，說明現(xiàn)行方案為最優(yōu)方案，否那么目標本錢還可以進一步減小。74精選課件當存在非基變量的檢驗數(shù)

kl<0且kl=min{ij}時，令Xkl進基。從表中知可選X24進基。第3步確定換入基的變量第4步確定換出基的變量以進基變量xik為起點的閉回路中，標有負號的最小運量作為調整量θ，θ對應的基變量為出基變量，并打上“×〞以示換出作為非基變量。求

=Min{xij

xij對應閉回路上的偶數(shù)標號格}=xpq那么確定xpq為出基變量，

為調整量；75精選課件B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)調整步驟為：在進基變量的閉回路中標有正號的變量加上調整量θ，標有負號的變量減去調整量θ，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗數(shù)重新檢驗。12576精選課件當所有非基變量的檢驗數(shù)均非負時，那么當前調運方案即為最優(yōu)方案，如表此時最小總運費：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元B1B2B3B4UiA1A2A3Vj3113101927410585363120-2-531039〔0〕〔2〕〔2〕〔1〕〔12〕〔9〕77精選課件表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平衡表及單位運價表確定初始調運方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負檢驗數(shù)，用閉合回路調整，得到新的調運方案得到最優(yōu)方案，算出總運價78精選課件表上作業(yè)法計算中的問題：〔1〕假設運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取σij<0中最小者對應的變量為換入變量?！?〕無窮多最優(yōu)解 產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，那么該問題有無窮多最優(yōu)解。79精選課件⑵退化解： ※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時那么需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。 ※利用進基變量的閉回路對解進行調整時，標有負號的最小運量〔超過2個最小值〕作為調整量θ，選擇任意一個最小運量對應的基變量作為出基變量，并打上“×〞以示作為非基變量。80精選課件銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數(shù)是0，經(jīng)過調整，可得到另一個最優(yōu)解。81精選課件銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A24A39銷量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任選一個變量作為基變量，例如選x34例3：用最小元素法求初始可行解82精選課件運輸問題的應用求極大值問題目標函數(shù)求利潤最大或營業(yè)額最大等問題。83精選課件求解方法： 將極大化問題轉化為極小化問題。設極大化問題的運價表為C，用一個較大的數(shù)M〔M≥max{cij}〕去減每一個cij得到矩陣C′，其中C′=〔M－cij〕≥0,將C′作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解。84精選課件例3以下矩陣C是Ai〔I=1，2，3〕到Bj的噸公里利潤,運輸部門如何安排運輸方案使總利潤最大.銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量814985精選課件銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149得到新的最小化運輸問題，用表上作業(yè)法求解即可。86精選課件

產(chǎn)銷不平衡的運輸問題 當總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。當產(chǎn)大于銷時，即：數(shù)學模型為：87精選課件由于總產(chǎn)量大于總銷量，必有局部產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設一個倉庫，假設該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運價為零，即Ci,n+1=0,〔i=1，…，m〕。那么平衡問題的數(shù)學模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可88精選課件當銷大于產(chǎn)時，即：數(shù)學模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設一個產(chǎn)地Am+1，產(chǎn)量為：89精選課件銷大于產(chǎn)化為平衡問題的數(shù)學模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。90精選課件例4求以下表中極小化運輸問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：91精選課件所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達B1，用一個很大的正數(shù)M表示運價C21。虛設一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj206035452018092精選課件下表為計算結果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj206035452018093精選課件3.生產(chǎn)與儲存問題例5某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的本錢如右表。如果生產(chǎn)出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。季度生產(chǎn)能力/臺單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.394精選課件解：設xij為第i季度生產(chǎn)的第j季度交貨的柴油機數(shù)目，那么應滿足：交貨：

x11=10生產(chǎn)：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生產(chǎn)的柴油機數(shù)目看作第i個生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機數(shù)目看作第j個銷售點的銷量；設cij是第i季度生產(chǎn)的第j季度交貨的每臺柴油機的實際本錢，應該等于該季度單位本錢加上儲存、維護等費用?？蓸嬙煲韵庐a(chǎn)銷平衡問題：95精選課件jiⅠⅡⅢⅣ產(chǎn)量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010銷量1015252010070由于產(chǎn)大于銷，加上一個虛擬的銷地D，化為平衡問題，即可應用表上作業(yè)法求解。96精選課件該問題的數(shù)學模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23 +11.4x24+11.0x33+11.15x34+11.3x44

jiⅠⅡⅢⅣD產(chǎn)量Ⅰ10.810.9511.111.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010銷選課件jiⅠⅡⅢⅣD產(chǎn)量Ⅰ1015025Ⅱ053035Ⅲ25530Ⅳ1010銷量1015252030100100最優(yōu)生產(chǎn)決策如下表，最小費用z＝773萬元。98精選課件例(運輸問題)兩個糧庫A1,A2,向三個糧站B1,B2,B3調運大米，兩個糧庫現(xiàn)存大米分別為4t，8t，三個兩站至少需要大米分別為2t,4t,5t，兩個糧庫到三個糧站的距離(km)如下表，求使運費最低。B1B2B3庫存A1122484A23012248需求245解：(1)問題分析：總需求量為11t，小于總庫存量12