第七章 運(yùn)輸問題(1表上作業(yè))

第七章運(yùn)輸問題TransportationProblem第七章運(yùn)輸問題運(yùn)輸問題在工商管理中有著廣泛的應(yīng)用，是一類重要的和特殊的線性規(guī)劃問題。由于這類線性規(guī)劃問題在結(jié)構(gòu)上有特殊性，所以有專門的解法——表上作業(yè)法等，用以簡便求解這類問題。管理運(yùn)籌學(xué)軟件中也為求解這類問題編制了專門的程序供我們使用。第七章運(yùn)輸問題7.1運(yùn)輸問題的模型§7.1運(yùn)輸問題的模型例1.

某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？運(yùn)費(fèi)單價(jià)銷地產(chǎn)地B1B2B3產(chǎn)量(件)A1646200A2655300銷量(件)150150200§7.1運(yùn)輸問題的模型解：這是一個(gè)產(chǎn)銷平衡問題：總產(chǎn)量=總銷量=500。設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，如：x12表示從產(chǎn)地A1

運(yùn)往銷地B2

的運(yùn)輸數(shù)量。于是我們得到新的綜合表格：運(yùn)費(fèi)單價(jià)銷地產(chǎn)地B1B2B3產(chǎn)量(件)A1646200A2655300銷量(件)150150200§7.1運(yùn)輸問題的模型解：這是一個(gè)產(chǎn)銷平衡問題：總產(chǎn)量=總銷量=500。設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，如：x12表示從產(chǎn)地A1

運(yùn)往銷地B2

的運(yùn)輸數(shù)量。于是我們得到新的綜合表格：運(yùn)費(fèi)單價(jià)銷地產(chǎn)地辦運(yùn)輸量B1B2B3產(chǎn)量(件)A16x114x126x13200A26x215x225x23300銷量(件)150150200500500運(yùn)費(fèi)單價(jià)銷地產(chǎn)地辦運(yùn)輸量B1B2B3產(chǎn)量(件)A16x114x126x13200A26x215x225x23300銷量(件)150150200500500minf=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）。解得：minf=2500，x11=50，x12=150，x13=0，x21=

100，x22=0，x23=200?！?.1運(yùn)輸問題的模型1.一般運(yùn)輸問題的線性規(guī)劃模型假設(shè)A1，A2，…，Am表示某物資的m個(gè)產(chǎn)地；B1，B2，…，Bn表示某物資的n個(gè)銷地；si表示產(chǎn)地Ai的產(chǎn)量；dj表示銷地Bj

的銷量；cij表示把物資從產(chǎn)地Ai

運(yùn)往銷地Bj

的單位運(yùn)價(jià)。如果s1+s2+…+sm

=d1+d2+…+dn，稱該運(yùn)輸問題是產(chǎn)銷平衡的；否則，稱它是產(chǎn)銷不平衡的。§7.1運(yùn)輸問題的模型銷地產(chǎn)地B1B2…Bn產(chǎn)量A1c11

x11c12

x12…c1n

x1ns1A2c21

x21c22

x22…c2n

x2ns2┇┇┇┇┇┇Amcm1

xm1cm2

xm2…cmnxmnsm銷量d1d2…dn

§7.1運(yùn)輸問題的模型設(shè)xij為從產(chǎn)地Ai

運(yùn)往銷地Bj

的運(yùn)輸量，則對于產(chǎn)銷平衡問題，可得到下列運(yùn)輸問題的模型：

mnminf=cijxij

i=1j=1

n

s.t.xij=si

i=1,2,…,m

j=1

m

xij

=dj

j=1,2,…,n

i=1

xij≥0(i=1,2,…,m;j=1,2,…,n)。運(yùn)費(fèi)單價(jià)銷地產(chǎn)地辦運(yùn)輸量B1B2B3產(chǎn)量(件)A16x114x126x13200A26x215x225x23300銷量(件)150150200500500minf=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）。§7.1運(yùn)輸問題的模型設(shè)xij為從產(chǎn)地Ai

運(yùn)往銷地Bj

的運(yùn)輸量，則對于產(chǎn)銷平衡問題，可得到下列運(yùn)輸問題的模型：

mnminf=cijxij

i=1j=1

n

s.t.xij=si

i=1,2,…,m

j=1

m

xij

=dj

j=1,2,…,n

i=1

xij≥0(i=1,2,…,m;j=1,2,…,n)?！?.1運(yùn)輸問題的模型2.一般模型的系數(shù)矩陣特征1.共有m+n行，分別表示各產(chǎn)地和銷地；m×n列，分別表示各變量；2.每列只有兩個(gè)1，其余為0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用。運(yùn)費(fèi)單價(jià)銷地產(chǎn)地辦運(yùn)輸量B1B2B3產(chǎn)量(件)A16x114x126x13200A26x215x225x23300銷量(件)150150200500500minf=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）?！?.1運(yùn)輸問題的模型2.一般模型的系數(shù)矩陣特征1.共有m+n行，分別表示各產(chǎn)地和銷地；m×n列，分別表示各變量；2.每列只有兩個(gè)1，其余為0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用?！?.1運(yùn)輸問題的模型3.一般模型有時(shí)會(huì)發(fā)生一些如下變化：1）有時(shí)求目標(biāo)函數(shù)最大值。如求利潤最大或營業(yè)額最大等；2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，模型中可直接加入（等式或不等式）約束；3）產(chǎn)銷不平衡時(shí)，可加入虛設(shè)的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。第七章運(yùn)輸問題7.1運(yùn)輸問題的模型7.2運(yùn)輸問題的表上作業(yè)法§7.2運(yùn)輸問題的表上作業(yè)法表上作業(yè)法是一種求解運(yùn)輸問題的特殊方法，其實(shí)質(zhì)是單純形法。運(yùn)輸問題都存在最優(yōu)解?！?.2運(yùn)輸問題的表上作業(yè)法計(jì)算過程（假設(shè)產(chǎn)銷平衡）：1.找出初始基本可行解。對于有m個(gè)產(chǎn)地n個(gè)銷地的產(chǎn)銷平衡問題，則有m個(gè)關(guān)于產(chǎn)量的約束方程和n個(gè)關(guān)于銷量的約束方程。運(yùn)費(fèi)單價(jià)銷地產(chǎn)地辦運(yùn)輸量B1B2B3產(chǎn)量(件)A16x114x126x13200A26x215x225x23300銷量(件)150150200500500minf=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）?！?.2運(yùn)輸問題的表上作業(yè)法計(jì)算過程（假設(shè)產(chǎn)銷平衡）：1.找出初始基本可行解。對于有m個(gè)產(chǎn)地n個(gè)銷地的產(chǎn)銷平衡問題，則有m個(gè)關(guān)于產(chǎn)量的約束方程和n個(gè)關(guān)于銷量的約束方程。由于產(chǎn)銷平衡，其模型最多只有m+n-1個(gè)獨(dú)立的約束方程，即運(yùn)輸問題有m+n-1個(gè)基變量。運(yùn)費(fèi)單價(jià)銷地產(chǎn)地辦運(yùn)輸量B1B2B3產(chǎn)量(件)A16x114x126x13200A26x215x225x23300銷量(件)150150200500500minf=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）?！?.2運(yùn)輸問題的表上作業(yè)法計(jì)算過程（假設(shè)產(chǎn)銷平衡）：1.找出初始基可行解。對于有m個(gè)產(chǎn)地n個(gè)銷地的產(chǎn)銷平衡問題，則有m個(gè)關(guān)于產(chǎn)量的約束方程和n個(gè)關(guān)于銷量的約束方程。由于產(chǎn)銷平衡，其模型最多只有m+n-1個(gè)獨(dú)立的約束方程，即運(yùn)輸問題有m+n-1個(gè)基變量?！?.2運(yùn)輸問題的表上作業(yè)法計(jì)算過程（假設(shè)產(chǎn)銷平衡）：1.找出初始基可行解。2.求各非基變量的檢驗(yàn)數(shù)。即檢驗(yàn)除了上述m+n-1個(gè)基變量以外的空格的檢驗(yàn)數(shù)判別是否達(dá)到最優(yōu)解，如果已是最優(yōu)，停止計(jì)算，否則轉(zhuǎn)到下一步?！?.2運(yùn)輸問題的表上作業(yè)法計(jì)算過程（假設(shè)產(chǎn)銷平衡）：1.找出初始基可行解。2.求各非基變量的檢驗(yàn)數(shù)。3.確定入基變量和出基變量，找出新的基可行解。4.重復(fù)2、3直到得到最優(yōu)解?！?.2運(yùn)輸問題的表上作業(yè)法1.找出初始基可行解?！?.2運(yùn)輸問題的表上作業(yè)法例.喜慶食品公司有三個(gè)生產(chǎn)面包的分廠A1，A2，A3，有四個(gè)銷售公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運(yùn)價(jià)如表所示，在表中產(chǎn)量與銷量的單位為噸，運(yùn)價(jià)的單位為百元/噸。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下總運(yùn)費(fèi)最少？銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量36562020§7.2運(yùn)輸問題的表上作業(yè)法1.找出初始基可行解。最小元素法

我們很容易的直觀想到,為了減少運(yùn)費(fèi),應(yīng)優(yōu)先考慮單位運(yùn)輸價(jià)格最小(或運(yùn)輸距離最短)的供銷業(yè)務(wù),最大限度的滿足其供銷量?！?.2運(yùn)輸問題的表上作業(yè)法例.喜慶食品公司有三個(gè)生產(chǎn)面包的分廠A1，A2，A3，有四個(gè)銷售公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運(yùn)價(jià)如表所示，在表中產(chǎn)量與銷量的單位為噸，運(yùn)價(jià)的單位為百元/噸。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下總運(yùn)費(fèi)最少？銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量36562020銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法§7.2運(yùn)輸問題的表上作業(yè)法1.找出初始基可行解。注意兩個(gè)問題：1.當(dāng)我們?nèi)《▁ij的值之后，會(huì)出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時(shí)只能劃去Ai行或Bj列，但不能同時(shí)劃去Ai行與Bj列。2.用最小元素法時(shí)，可能會(huì)出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時(shí)在這一行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過數(shù)或零的格為m+n-1個(gè)，即保證基變量的個(gè)數(shù)為m+n-1個(gè)。銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131083043A2192831031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131083043A2192830031A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131083043A2192830030A37410593063銷量30605406302020最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131083053A2192830030A37410593063銷量30605506302020最小元素法§7.2運(yùn)輸問題的表上作業(yè)法1.找出初始基可行解。注意兩個(gè)問題：1.當(dāng)我們?nèi)《▁ij的值之后，會(huì)出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時(shí)只能劃去Ai行或Bj列，但不能同時(shí)劃去Ai行與Bj列。2.用最小元素法時(shí)，可能會(huì)出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時(shí)在這一行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過數(shù)或零的格為m+n-1個(gè)，即保證基變量的個(gè)數(shù)為m+n-1個(gè)?！?.2運(yùn)輸問題的表上作業(yè)法計(jì)算過程（假設(shè)產(chǎn)銷平衡）：1.找出初始基可行解。2.求各非基變量的檢驗(yàn)數(shù)§7.2運(yùn)輸問題的表上作業(yè)法2.求各非基變量的檢驗(yàn)數(shù)所謂閉回路是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)；只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉回路。一個(gè)空格存在唯一的閉回路。銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路§7.2運(yùn)輸問題的表上作業(yè)法2.求各非基變量的檢驗(yàn)數(shù)閉回路所謂閉回路是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉回路。一個(gè)空格存在唯一的閉回路。銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路§7.2運(yùn)輸問題的表上作業(yè)法2.求各非基變量的檢驗(yàn)數(shù)對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對這個(gè)空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后我們計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化。銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730

+143A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730+14-13A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730+14-13A2192841031+1A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730+14-13A219284103-11+1A37410593063銷量30605406302020閉回路檢驗(yàn)數(shù)即為3-3+2-1=1銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730+143A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730+143-1A2192841031A37410593063銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730+143-1A2192841031A37410593063+1銷量30605406302020閉回路銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310730+143-1A2192841031A3741059306-13+1銷量30605406302020閉回路檢驗(yàn)數(shù)即為11-10+5-4=2銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路檢驗(yàn)數(shù)即為7-5+10-3+2-1=10銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107301243A21928410311-1A374105930106123銷量30605406302020閉回路§7.3運(yùn)輸問題的表上作業(yè)法2.求各非基變量的檢驗(yàn)數(shù)對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,我們必須對這個(gè)空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后我們計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化。如果所有代表非基變量的空格的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解?！?.2運(yùn)輸問題的表上作業(yè)法計(jì)算過程（假設(shè)產(chǎn)銷平衡）：1.找出初始基可行解。2.求各非基變量的檢驗(yàn)數(shù)。3.確定入基變量和出基變量，找出新的基可行解。——閉回路調(diào)整法閉回路調(diào)整法1.選取所有負(fù)檢驗(yàn)數(shù)最小的非基變量作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)。銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107301243A21928410311-1A374105930106123銷量30605406302020閉回路調(diào)整法閉回路調(diào)整法選取所有負(fù)檢驗(yàn)數(shù)最小的非基變量xij作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)。在以xij為出發(fā)點(diǎn)的閉回路中，找出所有偶數(shù)的頂點(diǎn)的調(diào)運(yùn)量,以其中的最小的變量為換出變量將該閉回路上所有的奇數(shù)頂點(diǎn)的調(diào)運(yùn)量增加這一數(shù)值，所有的偶數(shù)頂點(diǎn)的調(diào)運(yùn)量減少這一數(shù)值。銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路調(diào)整法銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131073043A2192841031A37410593063銷量30605406302020閉回路調(diào)整法閉回路調(diào)整法選取所有負(fù)檢驗(yàn)數(shù)最小的非基變量xij作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)。在以xij為出發(fā)點(diǎn)的閉回路中，找出所有偶數(shù)的頂點(diǎn)的調(diào)運(yùn)量,以其中的最小的變量為換出變量將該閉回路上所有的奇數(shù)頂點(diǎn)的調(diào)運(yùn)量增加這一數(shù)值，所有的偶數(shù)頂點(diǎn)的調(diào)運(yùn)量減少這一數(shù)值。銷地產(chǎn)地B1B2B3B4產(chǎn)量A131131074（+1）3（-1）A21928431（-1）（+1）A374105963銷量36562020閉回路調(diào)整法銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311310752A2192843

1A374105963銷量36562020閉回路調(diào)整法銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107300252A2192841032

11A37410593096123銷量306