1、運(yùn)輸問題v運(yùn)輸問題及其數(shù)學(xué)模型v運(yùn)輸問題的表上作業(yè)法v運(yùn)輸問題的進(jìn)一步討論例1：某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)（銷地）出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位均為t）以及各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)（元/t）示于下表中要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小 4.1 運(yùn)輸問題及其數(shù)學(xué)模型單位 銷地 運(yùn)價(jià)產(chǎn)地產(chǎn)量2910291342584257銷量38464321 BBBB321AAAA2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地2910213428425運(yùn)輸問題網(wǎng)絡(luò)圖運(yùn)輸問題網(wǎng)絡(luò)圖 )4 . 3

2、 . 2 . 1, 3 . 2 . 1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij 約約束束條條件件：目目標(biāo)標(biāo)函函數(shù)數(shù)：為為運(yùn)運(yùn)量量設(shè)設(shè)產(chǎn)量約束銷量約束運(yùn)輸問題的一般提法是：設(shè)某種物資有 個(gè)產(chǎn)地m,1A,2A,mA各產(chǎn)地的產(chǎn)量是;,21maaa有 個(gè)銷地,1B,2B,nBn各銷地的銷量是.,21nbbb假定從產(chǎn)地 ), 2, 1(miAi到銷地), 2 , 1

3、(njBj運(yùn)輸單位物品的運(yùn)價(jià)是 ，問ijc怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最??？ 銷地產(chǎn)地產(chǎn)量銷 量1A2AmA1B2BnB11c12cnc111x12xnx121c22cnc221x22xnx21mc2mcmnc1mx2mxmnx1b2bnb1a2ama運(yùn)價(jià)表 ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)產(chǎn)銷平衡時(shí)，其模型如下：0,0,0ijijabc假設(shè)：當(dāng)產(chǎn)大于銷時(shí)，其模型是： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當(dāng)產(chǎn)小于銷時(shí)，其模型是：min ()0ijijijiijjijijZc xxaxbabx 1 1、平衡運(yùn)輸

4、問題必有可行解，也、平衡運(yùn)輸問題必有可行解，也必有最優(yōu)解；必有最優(yōu)解；運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)證明 記.11dbaminjji則令dbaxjiij), 2 , 1;, 2 , 1(njmi則 為運(yùn)輸問題的一個(gè)可行解。事實(shí)上：ijxnjijinjnjjiijabdadbax111), 2 , 1(mimijijmimijiijbadbdbax111), 2 , 1(nj又因. 0, 0jiba所以. 0ijx故 是一組可行解。ijx又因?yàn)榭傎M(fèi)用不會(huì)為負(fù)值（存在下界）。這說明，運(yùn)輸問題既有可行解，又必然有下界存在，因此一定有最優(yōu)解存在。 2 2、運(yùn)輸問題約束條件的系數(shù)矩陣、運(yùn)輸

5、問題約束條件的系數(shù)矩陣運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)對(duì)運(yùn)輸問題數(shù)學(xué)模型的結(jié)構(gòu)約束加以整理，可知其系數(shù)矩陣具有下述形式：m行n行1運(yùn)輸問題是一個(gè)具有mn個(gè)變量和n+m個(gè)等型約束的線性規(guī)劃問題。 （41）mnmmnnxxxxxxxxx,;,212222111211jmiijeep), 2 , 1;, 2 , 1(njmi() 1() 1() 1000110000101000ijimjmnmnmnpee2運(yùn)輸問題約束方程組的系數(shù)矩陣是一個(gè)只有0和1兩個(gè)數(shù)值的稀疏矩陣,其中1的總數(shù)為 2mn 個(gè)。3、約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，這對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在

6、后n個(gè)約束方程中也出現(xiàn)一次4、約束條件系數(shù)矩陣的秩是m+n-1。即運(yùn)輸問題的基變量總數(shù)是m+n-1證明：因A的前m行對(duì)應(yīng)元素的和與后n行對(duì)應(yīng)元素的和相等，恰好都是：nmE) 1 , 1 , 1 (1所以A的行向量是線性相關(guān)的。從而 r(A)m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1階子式1112121311|00010000001000000110100111010000001000nmDp pp ppp 所以 r(A)=m+n-1.對(duì)于產(chǎn)銷平衡運(yùn)輸問題，除了上述特點(diǎn)外，還有以下特點(diǎn)： 1 所有結(jié)構(gòu)約束條件都是等式約束 2 各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和 3 3、運(yùn)輸問題的

7、解、運(yùn)輸問題的解運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題是一種線性規(guī)劃問題。前面講述的單純形法是求解線性規(guī)劃問題十分有效的一般方法，因而可用單純形法求解運(yùn)輸問題。但是當(dāng)用單純形法求解運(yùn)輸問題時(shí)，先得在每個(gè)約束條件中引入一個(gè)人工變量，這樣一來，即使對(duì)于m=3、n=4這樣簡單的運(yùn)輸問題，變量數(shù)目也會(huì)達(dá)到19個(gè)之多。因此，我們利用運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)，引入了表上作業(yè)法來求解運(yùn)輸問題 4.2 用表上作業(yè)法求解運(yùn)輸問題表上作業(yè)法的基本思想：先設(shè)法給出一個(gè)初始方案,然后根據(jù)確定的判別準(zhǔn)則對(duì)初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如下圖所示。初始化最優(yōu)性檢驗(yàn)迭代（Iteration）最

8、優(yōu)？yesSTOPno這和單純形法的求解思想完全一致，但是具體的作法則更加簡捷。例1 某部門有3個(gè)同類型的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)出售，各工廠的生產(chǎn)量、各銷售點(diǎn)的銷售量（假定單位為t）以及各工廠到銷售點(diǎn)的單位運(yùn)價(jià)（元/t）示于表4-2中，問如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？ 銷地產(chǎn)地產(chǎn)量4124111621039108511622銷 量8141214481A2A1B2B3B4B3A表 4-211x12x13x14x21x22x23x24x31x32x33x34x34333231242322213141141312116115893102114124minxxxxxxxxxxxxxcziji

9、jij4 , 3 , 2 , 1; 3 , 2, 1, 01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij該運(yùn)輸問題的數(shù)學(xué)模型為：可以證明：約束矩陣的秩 r (A) = m +n -1.基變量的個(gè)數(shù)為 m+n-1.表上作業(yè)法v計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案 , Go to 2表上作業(yè)法v計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案 , Go to 2下面介紹三種常用的方法。一、給出運(yùn)輸問題的初始可行解（初始調(diào)運(yùn)方案）l最小

10、元素法l西北角法l沃格爾(Vogel)法1。最小元素法思想：優(yōu)先滿足運(yùn)價(jià)（或運(yùn)距）最小的供銷業(yè)務(wù)。 銷地產(chǎn)地產(chǎn)量 4124111610398511622銷 量141214481A2A1B2B3B4B3A表 3-2228810 銷地產(chǎn)地產(chǎn)量 412411162109108511622銷 量 81414481A2A1B2B3B4B3A表 3-23210128 銷地產(chǎn)地產(chǎn)量 412112109108511622銷 量 8141214481A2A1B2B3B4B3A表 3-232104161068 銷地產(chǎn)地產(chǎn)量 4121182109108116銷 量 81214481A2A1B2B3B4B3A表 3-

11、2321041610651422148 銷地產(chǎn)地產(chǎn)量 412118210910811銷 量 812481A2A1B2B3B4B3A表 3-23210416106514221486146 銷地產(chǎn)地產(chǎn)量 4128210910811銷 量 812481A2A1B2B3B4B3A表 3-2321041610651422148614611此時(shí)得到一個(gè)初始調(diào)運(yùn)方案（初始可行解）：,1013x, 614x, 821x, 223x,1432x, 834x其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz246685143228116410此解滿足所有約束條件，且基變量（非零變量）的個(gè)數(shù)為6（等

12、于m+n-1=3+4-1=6). 西北角法西北角法是優(yōu)先滿足運(yùn)輸表中西北角（左上角）上空格的供銷需求。 銷地產(chǎn)地產(chǎn)量41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-281611x 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-281688 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量1214481A2A1B2B3B4B3A表 3-28168812x14 銷地產(chǎn)地產(chǎn)量 41241121039108511622銷 量141214481A2A1B2B3B4B3A表 3-

13、2816886 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量141214481A2A1B2B3B4B3A表 3-281688622x10 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量141214481A2A1B2B3B4B3A表 3-28168861064 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量1414481A2A1B2B3B4B3A表 3-2816886106423x12 銷地產(chǎn)地產(chǎn)量 412411210398511622銷 量141214481A2A1B2B3B4B3A表 3-281688610648 銷地產(chǎn)地產(chǎn)量 4124112103985116

14、銷 量141214481A2A1B2B3B4B3A表 3-2816886106432x822 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量141214481A2A1B2B3B4B3A表 3-28168861064822814 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量1412481A2A1B2B3B4B3A表 3-2816886106482281434x14 銷地產(chǎn)地產(chǎn)量 4124112103985116銷 量141214481A2A1B2B3B4B3A表 3-28168861064822814此時(shí)得到一個(gè)初始調(diào)運(yùn)方案（初始可行解）：, 811x, 812x, 622x, 4

15、23x, 833x,1434x其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz3726141183410612848此解滿足所有約束條件，且基變量（非零變量）的個(gè)數(shù)為6（等于m+n-1=3+4-1=6). 沃格爾（Vogel)法初看起來，最小元素法十分合理。但是，有時(shí)按某一最小單位運(yùn)價(jià)安排物品調(diào)運(yùn)時(shí)，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其他供銷點(diǎn)，從而使整個(gè)運(yùn)輸費(fèi)用增加。沃格爾法的思想： 對(duì)每一個(gè)供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運(yùn)價(jià)中找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià)，并稱這兩個(gè)單位運(yùn)價(jià)之差為該供應(yīng)地或銷售地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)

16、費(fèi)損失不大；反之，如果罰數(shù)的值很大，不按最小運(yùn)價(jià)組織運(yùn)輸就會(huì)造成很大的損失，故應(yīng)盡量按最大罰數(shù)安排運(yùn)輸。銷 地產(chǎn)地產(chǎn)量行罰數(shù)1234124111602103910181161銷 量8121448列罰數(shù)12513231A2A1B2B3B4B3A51422148銷 地產(chǎn)地產(chǎn)量行罰數(shù)123 412411160021039101185112212銷 量8141248列罰數(shù)12513221331A2A1B2B3B4B3A8146146銷 地產(chǎn)地產(chǎn)量行罰數(shù)123 41241116000103911185112212銷 量141248列罰數(shù)125132213321 21A2A1B2B3B4B3A814614

17、6281082銷 地產(chǎn)地產(chǎn)量行罰數(shù)456 41211710396851122銷 量1448列罰數(shù)412561A2A1B2B3B4B3A814614628108241216124銷 地產(chǎn)地產(chǎn)量行罰數(shù)456 412117010360851122銷 量1448列罰數(shù)4125 261A2A1B2B3B4B3A81461462810824121612494此時(shí)得到一個(gè)初始調(diào)運(yùn)方案（初始可行解）：,1213x, 414x, 821x, 224x3214,x, 834x其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz244685149228114412此解滿足所有約束條件，且基變量（非零變

18、量）的個(gè)數(shù)為6（等于m+n-1=3+4-1=6).比較上述三種方法給出的初始基可行解，以沃格爾法給出的解的目標(biāo)函數(shù)值最小，最小元素法次之，西北角法解的目標(biāo)函數(shù)值最大。 一般說來，沃格爾法得出的初始解的質(zhì)量最好，常用來作為運(yùn)輸問題最優(yōu)解的近似值。 銷地產(chǎn)地產(chǎn)量 414681250837514銷 量6563201A2A1B2B3B4B3A課堂練習(xí)課堂練習(xí)表上作業(yè)法v計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案 , Go to 2二、解的最優(yōu)性檢驗(yàn)前面得到了初始基可行解，一般來說此解并非最優(yōu)。下面介紹最優(yōu)性檢驗(yàn)的兩種方法。1 閉回路法(Cycle method)2 對(duì)偶變量法（dual

19、 variable method）也稱為位勢(shì)法補(bǔ)充：閉回路的數(shù)學(xué)定義補(bǔ)充：閉回路的數(shù)學(xué)定義定義：定義：凡是能排成凡是能排成1 112222311 12 122321,.,.,ssssssi ji ji ji ji ji ji ji ji ji ji ji jxxxxxxxxxxxx或形式的變量的集合稱為一個(gè)閉回路，并將這些變量稱為這形式的變量的集合稱為一個(gè)閉回路，并將這些變量稱為這個(gè)閉回路的頂點(diǎn)。個(gè)閉回路的頂點(diǎn)。由此可以看出閉回路的幾何特點(diǎn)：由此可以看出閉回路的幾何特點(diǎn)： 閉回路都是一條封閉折線，每個(gè)頂點(diǎn)格子都是轉(zhuǎn)角點(diǎn)閉回路都是一條封閉折線，每個(gè)頂點(diǎn)格子都是轉(zhuǎn)角點(diǎn) 每一行或每一列只有且僅有兩個(gè)

20、頂點(diǎn)格子每一行或每一列只有且僅有兩個(gè)頂點(diǎn)格子1. 每兩個(gè)頂點(diǎn)格子的連線都是水平的或垂直的。每兩個(gè)頂點(diǎn)格子的連線都是水平的或垂直的?？梢宰C明的一個(gè)重要結(jié)論：可以證明的一個(gè)重要結(jié)論：m+n-1個(gè)變量構(gòu)成基變量的充要條件是它不含閉回路，即個(gè)變量構(gòu)成基變量的充要條件是它不含閉回路，即不存在以這些變量為頂點(diǎn)的閉回路不存在以這些變量為頂點(diǎn)的閉回路 閉回路法（閉回路法（cycle method)下面用最小元素法所確定的初始基本可行解來說明。下面用最小元素法所確定的初始基本可行解來說明。與單純性原理相同，現(xiàn)目標(biāo)是運(yùn)費(fèi)最少，故檢驗(yàn)每一個(gè)非與單純性原理相同，現(xiàn)目標(biāo)是運(yùn)費(fèi)最少，故檢驗(yàn)每一個(gè)非基變量（對(duì)應(yīng)于運(yùn)輸表中的

21、空格）的檢驗(yàn)數(shù)是否基變量（對(duì)應(yīng)于運(yùn)輸表中的空格）的檢驗(yàn)數(shù)是否. 0ij?ij若所有空格的檢驗(yàn)數(shù)全非負(fù)，則不管怎樣均不能使運(yùn)輸費(fèi)若所有空格的檢驗(yàn)數(shù)全非負(fù)，則不管怎樣均不能使運(yùn)輸費(fèi)用降低，即目標(biāo)函數(shù)值已無法改進(jìn)，這個(gè)解就是最優(yōu)解用降低，即目標(biāo)函數(shù)值已無法改進(jìn)，這個(gè)解就是最優(yōu)解 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A3A1B2B3B4B考慮空格考慮空格(A1,B1),設(shè)想由產(chǎn)地設(shè)想由產(chǎn)地A1供應(yīng)一個(gè)單位的物品給銷地供應(yīng)一個(gè)單位的物品給銷地B1，為，為使運(yùn)入銷地使運(yùn)入銷地B1的物品總量不大于它的銷量，應(yīng)將的物品總量不大于它的銷量，應(yīng)將A

22、2運(yùn)到運(yùn)到B1的物品的物品數(shù)量減數(shù)量減1，即將格子（，即將格子（A2,B1）中填入的數(shù)字）中填入的數(shù)字8改為改為7；另一方面，為使產(chǎn)地另一方面，為使產(chǎn)地A2運(yùn)出的物品數(shù)量正好等于它的產(chǎn)量運(yùn)出的物品數(shù)量正好等于它的產(chǎn)量(保證新保證新得到的解仍為基可行解得到的解仍為基可行解)，應(yīng)將，應(yīng)將A2運(yùn)到運(yùn)到B3的物品數(shù)量增的物品數(shù)量增1。同理同理A1運(yùn)往運(yùn)往B3的物品數(shù)量減的物品數(shù)量減1，A1運(yùn)出的物品數(shù)量正好等于其產(chǎn)量運(yùn)出的物品數(shù)量正好等于其產(chǎn)量按照上述設(shè)想，由產(chǎn)地按照上述設(shè)想，由產(chǎn)地A1供給供給1個(gè)單位物品給銷地個(gè)單位物品給銷地B1,由此由此引起的總運(yùn)費(fèi)變化是：引起的總運(yùn)費(fèi)變化是：11212313c

23、-c +c -c= 4-2+3-4 =1根據(jù)檢驗(yàn)數(shù)的定義，它正是非基變量根據(jù)檢驗(yàn)數(shù)的定義，它正是非基變量x11(或者說空格或者說空格(A1,B1)的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)定義定義1：基變量（有數(shù)字的）對(duì)應(yīng)的格為基格；非基變量（空格）基變量（有數(shù)字的）對(duì)應(yīng)的格為基格；非基變量（空格）對(duì)應(yīng)的頂點(diǎn)為非基格。對(duì)應(yīng)的頂點(diǎn)為非基格。定義定義2：從每一空格（非基格）出發(fā)，沿水平或垂直方向前進(jìn)，每從每一空格（非基格）出發(fā)，沿水平或垂直方向前進(jìn)，每碰到數(shù)字格轉(zhuǎn)碰到數(shù)字格轉(zhuǎn)90o（有些情況也可以不改變方向）繼續(xù)前（有些情況也可以不改變方向）繼續(xù)前進(jìn)，直到回到出發(fā)的空格為止，由此形成的封閉的折線稱進(jìn)，直到回到出發(fā)的空格為止

24、，由此形成的封閉的折線稱為閉回路。為閉回路。規(guī)定：起始頂點(diǎn)的空格為第一頂點(diǎn)，則規(guī)定：起始頂點(diǎn)的空格為第一頂點(diǎn)，則 =閉回路上奇數(shù)次頂點(diǎn)運(yùn)價(jià)之和閉回路上奇數(shù)次頂點(diǎn)運(yùn)價(jià)之和 閉回路上偶數(shù)次頂點(diǎn)運(yùn)價(jià)之和閉回路上偶數(shù)次頂點(diǎn)運(yùn)價(jià)之和 ij 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2143241323211111cccc1 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-221165121434321212cccc21 銷地產(chǎn)地產(chǎn)

25、量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-213411651023131434322222cccccc121 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-21341192313142424cccc1121 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-210611432834141323213131cccccc102111 銷地產(chǎn)地產(chǎn)量

26、412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2124116111314343333cccc12101121 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-212111012檢驗(yàn)數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。 對(duì)偶變量法（位勢(shì)法）(dual variable method) 用閉回路法判定一個(gè)運(yùn)輸方案是否最優(yōu)，需要找出所有空格的閉回路，并計(jì)算其檢驗(yàn)數(shù)。當(dāng)運(yùn)輸問題的產(chǎn)地和銷地很多時(shí)，空格的數(shù)目很大，計(jì)算檢驗(yàn)數(shù)的工作量很大，而用對(duì)偶變

27、量法就簡便得多。nmvvvuuuY.2121 對(duì)產(chǎn)銷平衡運(yùn)輸問題，若用u1,u2,um分別表示前m個(gè)約束等式相對(duì)應(yīng)的對(duì)偶變量，用v1,v2vn 分別表示后n個(gè)等式相對(duì)應(yīng)的對(duì)偶變量，即有對(duì)偶向量這時(shí)可將運(yùn)輸問題的對(duì)偶規(guī)劃寫成：的符號(hào)不限jiijjinjjjmiiivunjmicvustvbuaZ,.1,.1.max11前面學(xué)習(xí)知道，線性規(guī)劃問題變量xj的檢驗(yàn)數(shù)可表示為：1jjjBjjjjczcc B PcYP由此可寫出運(yùn)輸問題某變量xij(對(duì)應(yīng)于運(yùn)輸表中(Ai,Bj)的檢驗(yàn)數(shù)如下：1212(,., ,.)()ijijijijijmijijjjniiczcYPcu uuv vvPcuv其中 分別稱

28、為行位勢(shì)、列位勢(shì)。jivu ,有基變量所對(duì)應(yīng)的檢驗(yàn)數(shù)為零，可從m+n-1個(gè)等式0)(jiijvuc（2.2）解出所有的行位勢(shì)、列位勢(shì)。（2.1）可以證明，不論令 為何值， 始終不變。avi)(jivu 即 將不會(huì)隨 的取值而改變。 ijiv為此，在求解方程組（2.2）時(shí)，為計(jì)算簡便，可指定一個(gè)位勢(shì)等于一個(gè)較小的整數(shù)或零。 銷地產(chǎn)地產(chǎn)量412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv10410392jiijvuc行位勢(shì)列位勢(shì)設(shè)u1=1當(dāng)然，也可用采用解方程組的辦法來求位勢(shì)：1314212332344112356uv

29、uvuvuvuvuv兩種方法任選一種 銷地產(chǎn)地產(chǎn)量 412104611168210239108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv1041039212111012)(jiijijvuc三。解的改進(jìn)（用閉回路法調(diào)整）選擇進(jìn)基變量的原則：,min|0Nklijiji j J即選擇非基變量中檢驗(yàn)數(shù)最小的一個(gè)進(jìn)基。在進(jìn)基格點(diǎn)所對(duì)應(yīng)的閉回路上，定義頂點(diǎn)的序號(hào)：自進(jìn)基格點(diǎn)起選定一個(gè)方向（比如順時(shí)針方向），依次為第一格、第二格、在奇數(shù)格點(diǎn)上減少調(diào)整量 ，在偶數(shù)格點(diǎn)上增加調(diào)整量 。其中調(diào)整量為),( |minjixij為閉回路中偶數(shù)格點(diǎn) 銷地產(chǎn)地產(chǎn)量 412

30、41116821039108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv104103921211012210602222 銷地產(chǎn)地產(chǎn)量 412124411168210329108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309jiijvuc)(jiijijvuc四。表上作業(yè)法計(jì)算中的兩個(gè)問題 無窮多個(gè)最優(yōu)解若在最優(yōu)解中，某個(gè)非基變量的檢驗(yàn)數(shù)為零，則該問題有無窮多個(gè)最優(yōu)解此時(shí)得到一個(gè)最優(yōu)解：,1213x, 414x, 821x, 224x,1432x, 834x其余變量全等于零?？傔\(yùn)

31、費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz244685149228114412 銷地產(chǎn)地產(chǎn)量 412124411168210329108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039221121309 銷地產(chǎn)地產(chǎn)量 412124111621039108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv141039134284444 銷地產(chǎn)地產(chǎn)量 441212411164210369108145118622銷 量8141214481A2A1B2B3B4B3A表 3-2iujv14103922112139

32、0此時(shí)得另一個(gè)最優(yōu)解：, 411x,1213x, 421x, 624x,1432x, 834x其余變量全等于零?？傔\(yùn)費(fèi)為（目標(biāo)函數(shù)值）3141ijijijxcz24468514962441244 退化情況與一般LP問題類似，運(yùn)輸問題也可能出現(xiàn)退化了的基本可行解。有以下兩種情況：（1）在確定初始基本可行解時(shí)，若已確定在空格）在確定初始基本可行解時(shí)，若已確定在空格 處處),(ji要添上調(diào)運(yùn)量要添上調(diào)運(yùn)量 ，而此時(shí)發(fā)點(diǎn)的當(dāng)前可發(fā)送量與收點(diǎn)的當(dāng)，而此時(shí)發(fā)點(diǎn)的當(dāng)前可發(fā)送量與收點(diǎn)的當(dāng)前需求量恰好相等。即發(fā)點(diǎn)的當(dāng)前發(fā)送量已全部用完，而收前需求量恰好相等。即發(fā)點(diǎn)的當(dāng)前發(fā)送量已全部用完，而收點(diǎn)的需求量已全部滿足

33、。因此應(yīng)同時(shí)劃掉發(fā)送的行及接受的點(diǎn)的需求量已全部滿足。因此應(yīng)同時(shí)劃掉發(fā)送的行及接受的列。為了使調(diào)運(yùn)表上確保有列。為了使調(diào)運(yùn)表上確保有(m+n-1)個(gè)基變量的值，就需要個(gè)基變量的值，就需要在在所劃掉的行（或列）的任一空格添上調(diào)運(yùn)量所劃掉的行（或列）的任一空格添上調(diào)運(yùn)量0。這樣就得到。這樣就得到有有一個(gè)基變量取值為一個(gè)基變量取值為0的基本可行解的基本可行解退化解。退化解。ijx例如：下表給出一個(gè)例如：下表給出一個(gè)34運(yùn)輸?shù)倪\(yùn)價(jià)及發(fā)送量與需求量。運(yùn)輸?shù)倪\(yùn)價(jià)及發(fā)送量與需求量。試用最小元素法求該問題的一個(gè)初始基本可行解。試用最小元素法求該問題的一個(gè)初始基本可行解。 銷地產(chǎn)地產(chǎn)量3114577738121

34、069銷 量3656481A2A1B2B3B4B3A表 4-26011634此時(shí)得到一個(gè)退化了的初始基本可行解：, 012x, 113x, 614x, 423x, 331x, 632x其余變量全等于零。 在用閉回路調(diào)整當(dāng)前基本可行解時(shí)，有多個(gè)偶數(shù)格值相等且都是極小值點(diǎn) 。此時(shí)只能取一個(gè)離基，其余的仍作為基格。例如：下表給出一個(gè)34運(yùn)輸問題的基本可行解及發(fā)送量與需求量、基本可行解的檢驗(yàn)數(shù)。試用閉回路法對(duì)其做出調(diào)整。 銷地產(chǎn)地產(chǎn)量 317339銷 量3646481A2A1B2B3B4B3A表 4-514112311633333333 銷地產(chǎn)地產(chǎn)量 347369銷 量3646481A2A1B2B3B

35、4B3A表 4-514112110333 運(yùn)輸問題的進(jìn)一步討論運(yùn)輸問題的進(jìn)一步討論一、產(chǎn)銷不平衡運(yùn)輸問題一、產(chǎn)銷不平衡運(yùn)輸問題對(duì)產(chǎn)銷不平衡問題，可轉(zhuǎn)化為平衡問題，然后按表上作業(yè)對(duì)產(chǎn)銷不平衡問題，可轉(zhuǎn)化為平衡問題，然后按表上作業(yè)法求解。轉(zhuǎn)換辦法：法求解。轉(zhuǎn)換辦法： 若產(chǎn)大于銷，增加一個(gè)假想的銷地（可視為庫存地）其銷若產(chǎn)大于銷，增加一個(gè)假想的銷地（可視為庫存地）其銷量設(shè)定為余量，相應(yīng)的運(yùn)價(jià)設(shè)為量設(shè)定為余量，相應(yīng)的運(yùn)價(jià)設(shè)為0 0。 若銷大于產(chǎn)，增加一個(gè)虛擬的產(chǎn)地，其產(chǎn)量設(shè)定為不足若銷大于產(chǎn)，增加一個(gè)虛擬的產(chǎn)地，其產(chǎn)量設(shè)定為不足量，相應(yīng)的運(yùn)價(jià)也設(shè)為量，相應(yīng)的運(yùn)價(jià)也設(shè)為0 0。例例4 某市有某市有3個(gè)造

36、紙廠個(gè)造紙廠 ， 和和 ，有，有4個(gè)集中用戶個(gè)集中用戶 和和 ，各工廠的生產(chǎn)量、各用戶的需用量以及各，各工廠的生產(chǎn)量、各用戶的需用量以及各工廠到用戶的單位運(yùn)價(jià)（元工廠到用戶的單位運(yùn)價(jià)（元/t）示于表）示于表3-14中，問如何調(diào)運(yùn)中，問如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最?。坎拍苁箍傔\(yùn)費(fèi)最?。?A2A3A1B,2B,3B4B 銷地產(chǎn)地產(chǎn)量31234811259567159銷 量43561A2A1B2B3B4B3A表 3-142218可增加一個(gè)假想的銷地可增加一個(gè)假想的銷地5B 銷地產(chǎn)地產(chǎn)量 31234081125905671509銷 量435641A2A1B2B3B4B3A表 3-145B例題例題5：彈性需求

37、問題：彈性需求問題v設(shè)有三煤礦供應(yīng)四地區(qū)，資料如下：設(shè)有三煤礦供應(yīng)四地區(qū)，資料如下：運(yùn)價(jià)運(yùn)價(jià) 地區(qū)地區(qū)煤礦煤礦甲甲乙乙丙丙丁丁產(chǎn)量產(chǎn)量 A B C161419131320221923171525506050最低需求最低需求最高需求最高需求3050707003010不限不限解題思路：v設(shè)法轉(zhuǎn)化為標(biāo)準(zhǔn)型設(shè)法轉(zhuǎn)化為標(biāo)準(zhǔn)型v本題產(chǎn)量本題產(chǎn)量160萬噸，最低需求萬噸，最低需求110萬噸，最高需求無萬噸，最高需求無限。實(shí)質(zhì)上比較現(xiàn)實(shí)的最高需求限。實(shí)質(zhì)上比較現(xiàn)實(shí)的最高需求210萬噸萬噸v產(chǎn)量大于最小需求；小于最大需求。而標(biāo)準(zhǔn)型是：產(chǎn)量大于最小需求；小于最大需求。而標(biāo)準(zhǔn)型是：產(chǎn)量產(chǎn)量=銷量。銷量。v處理辦法：

38、設(shè)想一個(gè)虛擬煤礦處理辦法：設(shè)想一個(gè)虛擬煤礦D，生產(chǎn)，生產(chǎn)50萬噸，但萬噸，但這個(gè)產(chǎn)量只能供應(yīng)可有可無的最高需求部分，于是這個(gè)產(chǎn)量只能供應(yīng)可有可無的最高需求部分，于是各地的需求也應(yīng)分為兩個(gè)部分：基本需求、機(jī)動(dòng)需各地的需求也應(yīng)分為兩個(gè)部分：基本需求、機(jī)動(dòng)需求求v虛擬產(chǎn)量的運(yùn)輸費(fèi)用為零，但它對(duì)于基本需求來講，虛擬產(chǎn)量的運(yùn)輸費(fèi)用為零，但它對(duì)于基本需求來講，運(yùn)費(fèi)為無窮大。運(yùn)費(fèi)為無窮大。建模：運(yùn)價(jià) 地區(qū)煤礦甲1甲2乙丙丁1丁2產(chǎn)量 A B C D161419M1614190131320M2219230171225M1712250 50 60 50 50需求量302070301050 210210最優(yōu)解：運(yùn)

39、價(jià) 地區(qū)煤礦甲1甲2乙丙丁1丁2產(chǎn)量 A B C D30205020030103020 50 60 50 50 需求量302070301050 210210v例例6 6、有三個(gè)產(chǎn)地、有三個(gè)產(chǎn)地3A1,A23A1,A2和和A3A3生產(chǎn)同一種物品，使用者為生產(chǎn)同一種物品，使用者為B1,B2B1,B2和和B3B3，各產(chǎn)地到各使用者的單位運(yùn)價(jià)于下表中。這三，各產(chǎn)地到各使用者的單位運(yùn)價(jià)于下表中。這三個(gè)的需用量分別為個(gè)的需用量分別為1010、4 4和和6 6個(gè)單位，由于銷售需要和客觀條個(gè)單位，由于銷售需要和客觀條件的限制，產(chǎn)地件的限制，產(chǎn)地A1A1至少要發(fā)出至少要發(fā)出6 6個(gè)單位的產(chǎn)品，它最多只能個(gè)單位的

40、產(chǎn)品，它最多只能生產(chǎn)生產(chǎn)1111個(gè)單位的產(chǎn)品；個(gè)單位的產(chǎn)品；A2A2必須發(fā)出必須發(fā)出7 7個(gè)單位的產(chǎn)品；個(gè)單位的產(chǎn)品；A3A3至少至少要發(fā)出要發(fā)出4 4個(gè)單位的產(chǎn)品。試根據(jù)上述條件用表上作業(yè)法求解個(gè)單位的產(chǎn)品。試根據(jù)上述條件用表上作業(yè)法求解該問題。該問題。B1B1B2B2B3B3產(chǎn)量產(chǎn)量A1A12 24 43 36 6a111a111A2A21 15 56 6a2=7a2=7A3A33 32 24 4a3a34 4用量用量10104 46 6運(yùn)輸模型的應(yīng)用運(yùn)輸模型的應(yīng)用v例題例題7 7：某機(jī)床廠定下一年：某機(jī)床廠定下一年合同分別于各季度末交貨。合同分別于各季度末交貨。已知各季度生產(chǎn)成本不同，已

41、知各季度生產(chǎn)成本不同，允許存貨，存儲(chǔ)費(fèi)允許存貨，存儲(chǔ)費(fèi)0.120.12萬萬元元/ /臺(tái)季，三、四季度可以臺(tái)季，三、四季度可以加班生產(chǎn)，加班生產(chǎn)能力加班生產(chǎn)，加班生產(chǎn)能力8 8臺(tái)臺(tái)/ /季，加班費(fèi)用季，加班費(fèi)用3 3萬元萬元/ /臺(tái)臺(tái)季季度度正常生正常生產(chǎn)能力產(chǎn)能力單位成本單位成本（萬元）（萬元）交貨交貨臺(tái)數(shù)臺(tái)數(shù)1 12 23 34 4303032322020282810.5510.5510.810.8111111.111.12525303015154545分析：分析：v可用線性規(guī)劃，但用運(yùn)輸問題更簡單可用線性規(guī)劃，但用運(yùn)輸問題更簡單v要決策的問題是各季度生產(chǎn)量和交貨量設(shè)要決策的問題是各季度生產(chǎn)

42、量和交貨量設(shè)xijxij表示第表示第i i季度生季度生產(chǎn)第產(chǎn)第j j季度交貨的臺(tái)數(shù)季度交貨的臺(tái)數(shù)v因加班時(shí)間生產(chǎn)成本不同，故要區(qū)別開來，三四季度可加班，因加班時(shí)間生產(chǎn)成本不同，故要區(qū)別開來，三四季度可加班，視同增加兩個(gè)季度視同增加兩個(gè)季度v需求量合計(jì)需求量合計(jì)115115臺(tái)，生產(chǎn)能力合計(jì)臺(tái)，生產(chǎn)能力合計(jì)126126臺(tái)，供需不平衡，因此，臺(tái)，供需不平衡，因此，增加一項(xiàng)閑置能力。增加一項(xiàng)閑置能力。建模：建模： 成本成本 交貨交貨生產(chǎn)生產(chǎn) 閑置閑置 1 2 3 4 能力能力產(chǎn)量產(chǎn)量1季度正常生產(chǎn)季度正常生產(chǎn)2季度正常生產(chǎn)季度正常生產(chǎn)3季度正常生產(chǎn)季度正常生產(chǎn)3季度加班生產(chǎn)季度加班生產(chǎn)4季度正常生產(chǎn)季度正常生產(chǎn)4季度加班生產(chǎn)季度加班生產(chǎn)10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0