運籌學(xué)講義影子價格靈敏分析運輸問題

（優(yōu)選）運籌學(xué)講義影子價格靈敏度分析運輸問題當(dāng)前第1頁\共有111頁\編于星期五\15點對偶最優(yōu)解的經(jīng)濟(jì)含義――影子價格

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

當(dāng)B是原問題的最優(yōu)基時，Y=CBB-1就是影子價格向量。當(dāng)前第2頁\共有111頁\編于星期五\15點ABC擁有量工時1113材料1479單件利潤233影子價格舉例當(dāng)前第3頁\共有111頁\編于星期五\15點

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，則表示增加第一種資源不會增加利潤，因為第一種資源還沒有用完。當(dāng)前第4頁\共有111頁\編于星期五\15點影子價格是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作出的估價，這種估價不是資源的市場價格。它反映了在最優(yōu)經(jīng)濟(jì)結(jié)構(gòu)中，在資源得到最優(yōu)配置前提下，資源的邊際使用價值。單純形表中松弛變量所對應(yīng)的檢驗數(shù)的相反數(shù)是在該經(jīng)濟(jì)結(jié)構(gòu)中的影子價格，也可以說對偶問題的最優(yōu)解向量是結(jié)構(gòu)中的影子價格。當(dāng)前第5頁\共有111頁\編于星期五\15點定理1：在某項經(jīng)濟(jì)活動中，在資源得到最優(yōu)配置條件下，

此定理的經(jīng)濟(jì)意義：（1）若生產(chǎn)一個單位第j種產(chǎn)品按消耗資源的影子價格計算的支出等于銷售一個單位該產(chǎn)品所得收入，則可生產(chǎn)此產(chǎn)品。（2）如果生產(chǎn)一個單位的第j種產(chǎn)品按所消耗資源的影子價格計算的支出大于銷售一個單位該產(chǎn)品得到的收入，則不宜生產(chǎn)此產(chǎn)品。當(dāng)前第6頁\共有111頁\編于星期五\15點定理2：在某項經(jīng)濟(jì)活動中，在資源得到最優(yōu)配置條件下，（1）若第種資源供大于求，即則該項資源的影子價格為0（2）若第種資源供求平衡，即則該項資源的影子價格大于等于0。影子價格越大，說明這種資源越是相對緊缺（根據(jù)影子價格確定資源采購,當(dāng)市場價格低于影子價格，就買進(jìn)資源，當(dāng)市場價格高于影子價格，就賣出資源）影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0當(dāng)前第7頁\共有111頁\編于星期五\15點例ABC擁有量工時1113材料1479單件利潤233

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

即工時的影子價格為5/3，材料的影子價格為1/3。如果目前市場上材料的價格低于1/3，則企業(yè)可以購進(jìn)材料來擴(kuò)大生產(chǎn)，反之可以賣掉部分材料。如果有客戶以高于5/3的價格購買工時，則可以出售一些工時，反之則反當(dāng)前第8頁\共有111頁\編于星期五\15點和市場價格的比較市場價格影子價格商品的價值的貨幣表現(xiàn)資源最優(yōu)利用時的邊際價值隨著市場的供求情況和有關(guān)方針，政策的變化而變化。隨著經(jīng)濟(jì)結(jié)構(gòu)的變化而變化，同一資源在不同的經(jīng)濟(jì)結(jié)構(gòu)中影子價格不同。它的制定含定價者的主觀因素它的形成完全由經(jīng)濟(jì)結(jié)構(gòu)的客觀條件確定。它的制定是個比較復(fù)雜的過程，不存在統(tǒng)一的計算公式。它的計算是比較容易的。用單純形法求得當(dāng)前第9頁\共有111頁\編于星期五\15點繼續(xù)比較任何一種商品的市場價格都不可能為0影子價格可以為0，當(dāng)資源過剩是，其影子價格為0市場價格為已知數(shù)，相對比較穩(wěn)定。影子價格則有賴于資源利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)，產(chǎn)品的結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。當(dāng)前第10頁\共有111頁\編于星期五\15點例(生產(chǎn)決策問題)某工廠可以用A，B兩種原料生產(chǎn)I,II,III三種產(chǎn)品，每種產(chǎn)品需要同時用兩種原料，有關(guā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，工廠應(yīng)如何決策？

(2)若目前市場上原料B的實際價格為0.8萬元/t，工廠應(yīng)如何決策？解：建立模型，設(shè)x1,x2,x3分別表示I，II，III的生產(chǎn)量，則模型如下：對偶問題當(dāng)前第11頁\共有111頁\編于星期五\15點模型討論：若把y1,y2當(dāng)作原料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)品獲得的利潤低，另一方面，為了增強(qiáng)出售資源的市場競爭力，定價希望低一些，定價的目標(biāo)是在比生產(chǎn)產(chǎn)品獲得更多利潤的前提下的最小利潤，這個定價模型就是對偶問題。如果把資源A的量由7增加到8，會導(dǎo)致什么結(jié)果呢？影子價格：在最有情況下，y1的值就是資源A的影子價格，所以要把影子價格與資源A的市場價格做比較，如果影子價格大于市場價格，考慮出售部分資源以獲得更大利潤，否則，則從市場買進(jìn)該資源。當(dāng)前第12頁\共有111頁\編于星期五\15點影子價格的經(jīng)濟(jì)意義：在資源得到最優(yōu)配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量。影子價格是一種靜態(tài)的資源最優(yōu)配置價格，不能表現(xiàn)資源在不同時期動態(tài)配置時的最優(yōu)價格，只反映某種資源的稀缺程度和資源與總體積極效益之間的關(guān)系，不能代替資源本身的價值。程序編寫：執(zhí)行結(jié)果如下：當(dāng)前第13頁\共有111頁\編于星期五\15點說明：從紅框部分知道，A的影子的價格為0.6，B的影子價格為0.8，松弛變量的值都是0，說明約束是緊約束(約束取等號)，即資源沒有剩余，影子價格有意義必須是緊約束。影子價格是對應(yīng)最優(yōu)基來說的，如果約束的改變使得最優(yōu)基發(fā)生改變，當(dāng)前的影子價格也就沒有任何意義了。通過對右端項的靈敏性分析：當(dāng)前第14頁\共有111頁\編于星期五\15點在最優(yōu)基不變時，A,B的右端項變化范圍分別為(4.67,22)和(3.5,21)對問題(1)0.5<0.6,應(yīng)該購進(jìn)原料A，擴(kuò)大生產(chǎn)能力，最大購進(jìn)15t，利潤增加(0.6-0.50*15=1.5萬元對于問題(2),0.8>0.6，應(yīng)該售出部分原料將使利潤更大，最大售出量為3.33t,利潤將會增加(0.8-0.6)*3.33=0.66萬元當(dāng)前第15頁\共有111頁\編于星期五\15點例(奶制品的加工問題)1桶牛奶3公斤A1

12小時8小時4公斤A2

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

制訂生產(chǎn)計劃，使每天獲利最大(1)35元可買到1桶牛奶，買嗎？若買，每天最多買多少?(2)可聘用臨時工人，付出的工資最多是每小時幾元?(3)A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計劃？每天：當(dāng)前第16頁\共有111頁\編于星期五\15點1桶牛奶3公斤A1

12小時8小時4公斤A2

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

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

獲利24×3x1

獲利16×4x2

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

50桶牛奶每天當(dāng)前第17頁\共有111頁\編于星期五\15點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元。模型求解當(dāng)前第18頁\共有111頁\編于星期五\15點模型求解reducedcost值表示當(dāng)該非基變量增加一個單位時（其他非基變量保持不變）目標(biāo)函數(shù)減少的量(對max型問題)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中對應(yīng)系數(shù)應(yīng)增加的量當(dāng)前第19頁\共有111頁\編于星期五\15點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三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋當(dāng)前第20頁\共有111頁\編于星期五\15點OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000結(jié)果解釋最優(yōu)解下“資源”增加1單位時“效益”的增量時間加1單位,利潤增2影子價格35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！

聘用臨時工人付出的工資最多每小時幾元？2元！當(dāng)前第21頁\共有111頁\編于星期五\15點RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

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

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

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋當(dāng)前第22頁\共有111頁\編于星期五\15點結(jié)果解釋RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶？(目標(biāo)函數(shù)不變)注意:充分但可能不必要當(dāng)前第23頁\共有111頁\編于星期五\15點靈敏度分析當(dāng)前第24頁\共有111頁\編于星期五\15點

在生產(chǎn)計劃問題的一般形式中，A代表企業(yè)的技術(shù)狀況，b代表企業(yè)的資源狀況，而C代表企業(yè)產(chǎn)品的市場狀況，在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計劃和最大利潤由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。在實際生產(chǎn)過程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產(chǎn)計劃，而在計劃實施前或?qū)嵤┲猩鲜鰻顩r發(fā)生了改變，則決策者所關(guān)心的是目前所執(zhí)行的計劃還是不是最優(yōu)，如果不是應(yīng)該如何修訂原來的最優(yōu)計劃。當(dāng)前第25頁\共有111頁\編于星期五\15點更進(jìn)一步，為了防止在各類狀況發(fā)生時，來不及隨時對其變化作出反應(yīng)，即所謂“計劃不如變化快”，企業(yè)應(yīng)當(dāng)預(yù)先了解，當(dāng)各項因素變化時，應(yīng)當(dāng)作出什么樣的反應(yīng)。當(dāng)前第26頁\共有111頁\編于星期五\15點

設(shè)線性規(guī)劃問題：

maxZ=CXs.t.AX=bA代表企業(yè)技術(shù)狀況b代表企業(yè)資源狀況C代表企業(yè)產(chǎn)品市場狀況（利潤)

這些因素不變的情況下，企業(yè)最優(yōu)生產(chǎn)計劃和最大利潤由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定。當(dāng)前第27頁\共有111頁\編于星期五\15點最優(yōu)化后分析，可歸為以下兩類問題：1）當(dāng)系數(shù)A，b，C發(fā)生改變時，目前最優(yōu)基是否還最優(yōu)？2）為保持目前最優(yōu)基還是最優(yōu)，系數(shù)A，b，C的允許變化范圍是什么？假設(shè)每次只有一種系數(shù)變化靈敏度分析包括以下五種：①目標(biāo)系數(shù)C變化基變量系數(shù)發(fā)生變化；非基變量系數(shù)發(fā)生變化；②右端常數(shù)b變化③增加一個變量④增加一個約束⑤技術(shù)系數(shù)A發(fā)生變化當(dāng)前第28頁\共有111頁\編于星期五\15點CBXBcjCBCN

xj

bXBTXNTCBTXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N若B是最優(yōu)基，則最優(yōu)表形式如下靈敏度分析總是在最優(yōu)表上進(jìn)行當(dāng)前第29頁\共有111頁\編于星期五\15點例2線性規(guī)劃CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3當(dāng)前第30頁\共有111頁\編于星期五\15點靈敏度分析CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3當(dāng)前第31頁\共有111頁\編于星期五\15點CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/33-2*（-1）-3*2=-1當(dāng)前第32頁\共有111頁\編于星期五\15點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)解,應(yīng)該用單純形方法繼續(xù)求解,否則解不變。即對于C3而言,使最優(yōu)解不變的條件是C3≤4。當(dāng)前第33頁\共有111頁\編于星期五\15點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/2當(dāng)前第34頁\共有111頁\編于星期五\15點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進(jìn)基，x1出基若3<C1

則x3或x5進(jìn)基，x2出基當(dāng)前第35頁\共有111頁\編于星期五\15點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/4當(dāng)前第36頁\共有111頁\編于星期五\15點CBXBcj43300

xj

bx1x2x3x4x50x43111100x59147014x1110-14/3-1/3∞3x22012-1/31/33/2－Ｚ-10001-13/31/3價值系數(shù)CB發(fā)生改變4X13111100X56036-11－Ｚ-120-1-1-40當(dāng)前第37頁\共有111頁\編于星期五\15點右端常數(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/3當(dāng)前第38頁\共有111頁\編于星期五\15點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最小比值11當(dāng)前第39頁\共有111頁\編于星期五\15點右端常數(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-5當(dāng)前第40頁\共有111頁\編于星期五\15點增加一個變量若企業(yè)在計劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單位利潤，單件資源消耗量時，可以在最優(yōu)表中補(bǔ)充一列，其中的前m行可以由基矩陣的逆矩陣得到，而檢驗數(shù)行也可以由與其它列相同的方法計算得到。若檢驗數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當(dāng)檢驗數(shù)為正時，則應(yīng)以該變量進(jìn)基，作單純形迭代，從而找出新的最優(yōu)解。當(dāng)前第41頁\共有111頁\編于星期五\15點靈敏度分析例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/3當(dāng)前第42頁\共有111頁\編于星期五\15點增加一個約束在企業(yè)的生產(chǎn)過程中，經(jīng)常有一些突發(fā)事件產(chǎn)生，造成原本不緊缺的某種資源變成為緊缺資源，對生產(chǎn)計劃造成影響，所以需要增加約束條件。1）若把目前的最優(yōu)解代入新增加的約束，能滿足約束條件，則說明該增加的約束對最優(yōu)解不構(gòu)成影響，即不影響最優(yōu)生產(chǎn)計劃的實施。2)若當(dāng)前最優(yōu)解不滿足新增加的約束，則應(yīng)把新的約束添到原問題的最優(yōu)表內(nèi)新的一行中去，用對偶單純形方法來進(jìn)行迭代，求出新的最優(yōu)解。當(dāng)前第43頁\共有111頁\編于星期五\15點靈敏度分析例增加約束CBXBcj23300xj

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

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3當(dāng)前第44頁\共有111頁\編于星期五\15點靈敏度分析增加約束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/6當(dāng)前第45頁\共有111頁\編于星期五\15點靈敏度分析A中元素改變?nèi)绻鸑中數(shù)據(jù)改變，可以用增加一個變量來處理如果B中元素改變，則情況較復(fù)雜，一般需要修改問題后重新求解當(dāng)前第46頁\共有111頁\編于星期五\15點運輸問題

問題的提出一般的運輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地，在每個產(chǎn)地的供應(yīng)量與每個銷地的需求量已知，并知道各地之間的運輸單價的前提下，如何確定一個使得總的運輸費用最小的方案。當(dāng)前第47頁\共有111頁\編于星期五\15點例某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？單位運費B1B2B3產(chǎn)量A1646200A2655300銷量150150200當(dāng)前第48頁\共有111頁\編于星期五\15點解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500

設(shè)xij

為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）當(dāng)前第49頁\共有111頁\編于星期五\15點運輸規(guī)劃問題的數(shù)學(xué)模型運輸問題的一般形式：產(chǎn)銷平衡A1、A2、…、Am

表示某物資的m個產(chǎn)地；B1、B2、…、Bn

表示某物質(zhì)的n個銷地；ai

表示產(chǎn)地Ai的產(chǎn)量；bj

表示銷地Bj

的銷量；cij表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設(shè)xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：當(dāng)前第50頁\共有111頁\編于星期五\15點變化：

1）有時目標(biāo)函數(shù)求最大。如求利潤最大或營業(yè)額最大等；

2）當(dāng)某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束)；

3）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。定理:

設(shè)有m個產(chǎn)地n個銷地且產(chǎn)銷平衡的運輸問題，則基變量數(shù)為m+n-1。當(dāng)前第51頁\共有111頁\編于星期五\15點表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運方案）最小元素法、元素差額法、第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗數(shù)σij全都非負(fù)時得到最優(yōu)解，若存在檢驗數(shù)σij<0，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位勢法第三步調(diào)整運量，即換基，選一個變量出基，對原運量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步當(dāng)前第52頁\共有111頁\編于星期五\15點表上作業(yè)法例2某運輸資料如下表所示：單位銷地運價產(chǎn)地產(chǎn)量311310719284741059銷量3656問：應(yīng)如何調(diào)運可使總運輸費用最小？當(dāng)前第53頁\共有111頁\編于星期五\15點解：第1步求初始方案方法1：最小元素法基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)運），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633當(dāng)前第54頁\共有111頁\編于星期五\15點總的運輸費＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元

元素差額法對最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案。85102120151515510總運費是z=10×8+5×2+15×1=105最小元素法：當(dāng)前第55頁\共有111頁\編于星期五\15點85102120151551510總運費z=10×5+15×2+5×1=85后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先調(diào)運x21，到后來就有可能x11≠0，這樣會使總運費增加較大，從而先調(diào)運x21，再是x22，其次是x12用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。當(dāng)前第56頁\共有111頁\編于星期五\15點方法2：Vogel法元素差額法1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量行差額A177A2

41A391銷量3656列差額2513311310192741058當(dāng)前第57頁\共有111頁\編于星期五\15點2）再從差值最大的行或列中找出最小運價確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列。重復(fù)1)和2)，直到找出初始解為至。B1B2B3B4產(chǎn)量行差額A177A2

41A3

91銷量3656列差額25133113101927410585當(dāng)前第58頁\共有111頁\編于星期五\15點單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額71135215××當(dāng)前第59頁\共有111頁\編于星期五\15點單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額7135275×××3×當(dāng)前第60頁\共有111頁\編于星期五\15點單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額113515×××3×631××2該方案的總運費:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元當(dāng)前第61頁\共有111頁\編于星期五\15點第2步最優(yōu)解的判別（檢驗數(shù)的求法）

求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為λij由第一章知，求最小值的運輸問題的最優(yōu)判別準(zhǔn)則是：所有非基變量的檢驗數(shù)都非負(fù)，則運輸方案最優(yōu)求檢驗數(shù)的方法有兩種：閉回路法位勢法（▲）當(dāng)前第62頁\共有111頁\編于星期五\15點閉回路的概念為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。如下表當(dāng)前第63頁\共有111頁\編于星期五\15點例下表中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個頂點，這8個頂點間用水平或垂直線段連接起來，組成一條封閉的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43

一條回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉(zhuǎn)90度與另一頂點連接，表3－3中的變量x32及x33不是閉回路的頂點，只是連線的交點。當(dāng)前第64頁\共有111頁\編于星期五\15點閉回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如變量組不能構(gòu)成一條閉回路，但A中包含有閉回路

變量組變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路；當(dāng)前第65頁\共有111頁\編于星期五\15點

可以證明，如果對閉回路的方向不加區(qū)別（即只要起點及其他所有頂點完全相同，而不區(qū)別行進(jìn)方向），那么以每一個非基量為起始頂點的閉回路就存在而且唯一。因此，對每一個非基變量可以找到而且只能找到唯一的一個閉回路。下表中用虛線畫出以非基變量x22

為起始頂點的閉回路。當(dāng)前第66頁\共有111頁\編于星期五\15點表以非基變量x22

為起始頂點的閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量3[]11[]341037139[]218[]47[]4610[]539銷量365620(產(chǎn)銷平衡)A1A2A3當(dāng)前第67頁\共有111頁\編于星期五\15點

可以計算出以非基變量x22

為起始頂點的閉回路調(diào)整使總的運輸費用發(fā)生的變化為

9–2+3–10+5–4＝1

即總的運費增加1個單位，這就說明這個調(diào)整不能改善目標(biāo)值。從上面的討論可以看出，當(dāng)某個非基變量增加一個單位時，有若干個基變量的取值受其影響。當(dāng)前第68頁\共有111頁\編于星期五\15點

這個過程就是尋找一個以非基變量x24

為起始頂點的閉回路——{x24

，x14

，x13

，x23}，這個閉回路的其他頂點均為基變量(對應(yīng)著填上數(shù)字的格)。容易計算出上述調(diào)整使總的運輸費用發(fā)生的變化為8–10+3–2＝-1，即總的運費減少1個單位，這就說明原始方案不是最優(yōu)方案，可以進(jìn)行調(diào)整以得到更好的方案。當(dāng)前第69頁\共有111頁\編于星期五\15點

這樣，利用單位產(chǎn)品變化（運輸?shù)膯挝毁M用）可計算出它們對目標(biāo)函數(shù)的綜合影響，其作用與線性規(guī)劃單純形方法中的檢驗數(shù)完全相同。故也稱這個綜合影響為該非基變量對應(yīng)的檢驗數(shù)。上面計算的兩個非基變量的檢驗數(shù)為24=-1，22=1。閉回路方法原理就是通過尋找閉回路來找到非基變量的檢驗數(shù)。當(dāng)前第70頁\共有111頁\編于星期五\15點

如果規(guī)定作為起始頂點的非基變量為第1個頂點，閉回路的其他頂點依次為第2個頂點、第3個頂點……，那么就有

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

其中ij

為非基變量的下角指標(biāo)。當(dāng)前第71頁\共有111頁\編于星期五\15點

按上述作法，可計算出表1的所有非基變量的檢驗數(shù)，把它們填入相應(yīng)位置的方括號內(nèi)，如圖所示。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539銷量365620(產(chǎn)銷平衡)表初始基本可行解及檢驗數(shù)當(dāng)前第72頁\共有111頁\編于星期五\15點

顯然，當(dāng)所有非基變量的檢驗數(shù)均大于或等于零時，現(xiàn)行的調(diào)運方案就是最優(yōu)方案，因為此時對現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運輸費用增加。閉回路法的主要缺點是：當(dāng)變量個數(shù)較多時，尋找閉回路以及計算兩方面都會產(chǎn)生困難。當(dāng)前第73頁\共有111頁\編于星期五\15點用位勢法對初始方案進(jìn)行最優(yōu)性檢驗：1）由ij=Cij-（Ui+Vj）計算位勢Ui

，Vj

，因?qū)兞慷杂衖j=0，即Cij-（Ui+Vj）=0，令U1=0即參照系2）再由ij=Cij-（Ui+Vj）計算非基變量的檢驗數(shù)ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029（1）（2）（1）（-1）（10）（12）當(dāng)存在非基變量的檢驗數(shù)kl

≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。當(dāng)前第74頁\共有111頁\編于星期五\15點當(dāng)存在非基變量的檢驗數(shù)kl<0且kl=min{ij}時，令Xkl進(jìn)基。從表中知可選X24進(jìn)基。第3步確定換入基的變量第4步確定換出基的變量以進(jìn)基變量xik為起點的閉回路中，標(biāo)有負(fù)號的最小運量作為調(diào)整量θ，θ對應(yīng)的基變量為出基變量，并打上“×”以示換出作為非基變量。求=Min{xijxij對應(yīng)閉回路上的偶數(shù)標(biāo)號格}=xpq那么確定xpq為出基變量，為調(diào)整量；當(dāng)前第75頁\共有111頁\編于星期五\15點B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)調(diào)整步驟為：在進(jìn)基變量的閉回路中標(biāo)有正號的變量加上調(diào)整量θ，標(biāo)有負(fù)號的變量減去調(diào)整量θ，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗數(shù)重新檢驗。125當(dāng)前第76頁\共有111頁\編于星期五\15點當(dāng)所有非基變量的檢驗數(shù)均非負(fù)時，則當(dāng)前調(diào)運方案即為最優(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）當(dāng)前第77頁\共有111頁\編于星期五\15點表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負(fù)檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，算出總運價當(dāng)前第78頁\共有111頁\編于星期五\15點表上作業(yè)法計算中的問題：（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取σij<0中最小者對應(yīng)的變量為換入變量。（2）無窮多最優(yōu)解 產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。當(dāng)前第79頁\共有111頁\編于星期五\15點⑵退化解：

※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補(bǔ)一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。

※利用進(jìn)基變量的閉回路對解進(jìn)行調(diào)整時，標(biāo)有負(fù)號的最小運量（超過2個最小值）作為調(diào)整量θ，選擇任意一個最小運量對應(yīng)的基變量作為出基變量，并打上“×”以示作為非基變量。當(dāng)前第80頁\共有111頁\編于星期五\15點

銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數(shù)是0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。當(dāng)前第81頁\共有111頁\編于星期五\15點

銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A24A39銷量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任選一個變量作為基變量，例如選x34例3：用最小元素法求初始可行解當(dāng)前第82頁\共有111頁\編于星期五\15點運輸問題的應(yīng)用

求極大值問題目標(biāo)函數(shù)求利潤最大或營業(yè)額最大等問題。當(dāng)前第83頁\共有111頁\編于星期五\15點求解方法： 將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為C，用一個較大的數(shù)M（M≥max{cij}）去減每一個cij得到矩陣C′，其中C′=（M－cij）≥0,將C′作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解。當(dāng)前第84頁\共有111頁\編于星期五\15點例3下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤,運輸部門如何安排運輸方案使總利潤最大.

銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149當(dāng)前第85頁\共有111頁\編于星期五\15點

銷地產(chǎn)地B1B2B3產(chǎn)量A12589A2910710A365412銷量8149得到新的最小化運輸問題，用表上作業(yè)法求解即可。當(dāng)前第86頁\共有111頁\編于星期五\15點

產(chǎn)銷不平衡的運輸問題 當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。

當(dāng)產(chǎn)大于銷時，即：數(shù)學(xué)模型為：當(dāng)前第87頁\共有111頁\編于星期五\15點由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設(shè)銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運價為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可當(dāng)前第88頁\共有111頁\編于星期五\15點

當(dāng)銷大于產(chǎn)時，即：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為：當(dāng)前第89頁\共有111頁\編于星期五\15點銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。當(dāng)前第90頁\共有111頁\編于星期五\15點例4求下列表中極小化運輸問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：當(dāng)前第91頁\共有111頁\編于星期五\15點所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達(dá)B1，用一個很大的正數(shù)M表示運價C21。虛設(shè)一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180當(dāng)前第92頁\共有111頁\編于星期五\15點下表為計算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180當(dāng)前第93頁\共有111頁\編于星期五\15點3.生產(chǎn)與儲存問題例5某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。季度生產(chǎn)能力/臺單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.3當(dāng)前第94頁\共有111頁\編于星期五\15點解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：

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)的柴油機(jī)數(shù)目看作第i個生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個銷售點的銷量；設(shè)cij是第i季度生產(chǎn)的第j季度交貨的每臺柴油機(jī)的實際成本，應(yīng)該等于該季度單位成本加上儲存、維護(hù)等費用?？蓸?gòu)造下列產(chǎn)銷平衡問題：當(dāng)前第95頁\共有111頁\編于星期五\15點jiⅠⅡⅢⅣ產(chǎn)量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010銷量1015252010070由于產(chǎn)大于銷，加上一個虛擬的銷地D，化為平衡問題，即可應(yīng)用表上作業(yè)法求解。當(dāng)前第96頁\共有111頁\編于星期五\15點該問題的數(shù)學(xué)模型：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.