運(yùn)籌學(xué)課件06-運(yùn)輸問(wèn)題

第六章運(yùn)輸問(wèn)題6.1運(yùn)輸問(wèn)題的數(shù)學(xué)模型6.2初始基可行解的確定6.3最優(yōu)性檢驗(yàn)與基可行解的改進(jìn)6.4其他運(yùn)輸問(wèn)題7/22/202416.1運(yùn)輸問(wèn)題的數(shù)學(xué)模型若一家公司擁有多個(gè)工廠，這些工廠位于不同的地點(diǎn)，并且生產(chǎn)同一種產(chǎn)品。這些產(chǎn)品要運(yùn)輸?shù)讲煌牡攸c(diǎn)，以滿足用戶的需求。供應(yīng)節(jié)點(diǎn)：這些工廠，它們是運(yùn)輸?shù)钠瘘c(diǎn)；需求節(jié)點(diǎn)：用戶所在點(diǎn)，它們是運(yùn)輸?shù)慕K點(diǎn)或目的地。同時(shí)假定產(chǎn)品不能在供應(yīng)節(jié)點(diǎn)之間運(yùn)輸，也不能在需求節(jié)點(diǎn)之間運(yùn)輸。公司面臨的問(wèn)題是：應(yīng)如何組織運(yùn)輸，才能在滿足供應(yīng)節(jié)點(diǎn)的供應(yīng)量約束和需求節(jié)點(diǎn)的需求量約束的前提下，使得運(yùn)輸成本最低。這類問(wèn)題就是運(yùn)輸問(wèn)題。7/22/20242(1)運(yùn)輸問(wèn)題數(shù)學(xué)模型xij——供應(yīng)節(jié)點(diǎn)i至需求節(jié)點(diǎn)j的運(yùn)輸量；aij——供應(yīng)節(jié)點(diǎn)i的可供應(yīng)量，i=1,2,…,m；bij——需求節(jié)點(diǎn)j的需求量，j=1,2,…,n；cij——供應(yīng)節(jié)點(diǎn)i至需求節(jié)點(diǎn)j的單位運(yùn)輸成本。7/22/20243根據(jù)運(yùn)輸問(wèn)題中總供應(yīng)量與總需求量的關(guān)系可將運(yùn)輸問(wèn)題分為兩類：平衡型運(yùn)輸問(wèn)題和不平衡型運(yùn)輸問(wèn)題。平衡型運(yùn)輸問(wèn)題：不平衡型運(yùn)輸問(wèn)題：對(duì)于不平衡型運(yùn)輸問(wèn)題通常通過(guò)設(shè)立虛擬供應(yīng)節(jié)點(diǎn)或虛擬需求節(jié)點(diǎn)將其轉(zhuǎn)化為平衡型運(yùn)輸問(wèn)題求解。(2)運(yùn)輸問(wèn)題的分類7/22/20244平衡型運(yùn)輸問(wèn)題的數(shù)學(xué)模型模型包含變量：m×n個(gè)約束方程：m+n個(gè)秩：r(A)=m+n-1

m行n行稀疏矩陣7/22/20245(3)運(yùn)輸問(wèn)題的特征定理：平衡運(yùn)輸問(wèn)題必有可行解與最優(yōu)解。證：對(duì)于平衡運(yùn)輸問(wèn)題令：7/22/20246則有所以是運(yùn)輸問(wèn)題的一個(gè)可行解。又由于所以且為極小化問(wèn)題，故一定存在最優(yōu)解。7/22/20247定義：凡能排列成形式的變量集合，用一條封閉折線將它們連接起來(lái)形成的圖形稱之為一個(gè)閉回路。構(gòu)成回路的諸變量稱為閉回路的頂點(diǎn)；連接相鄰兩個(gè)頂點(diǎn)的線段稱為閉回路的邊。或每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)；每一條邊都是水平線段或垂直線段；每一行或列若有閉回路的頂點(diǎn)，則必有兩個(gè)幾何性質(zhì)7/22/20248(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,

x21轉(zhuǎn)角點(diǎn)轉(zhuǎn)角點(diǎn)7/22/20249運(yùn)輸問(wèn)題是一類特殊的線性規(guī)劃問(wèn)題對(duì)于平衡型運(yùn)輸問(wèn)題：約束方程數(shù)為m+n個(gè)，但有一個(gè)冗余方程，所以獨(dú)立方程數(shù)為m+n-1個(gè)，即秩r(A)=m+n-1。存在最優(yōu)解當(dāng)供應(yīng)量和需求量均為整數(shù)時(shí)，存在整數(shù)最優(yōu)解?；尚薪庵谢兞總€(gè)數(shù)為m+n-1個(gè)基可行解中基變量的重要特征：不含閉回路。任何一個(gè)非基變量與基變量含且僅含一個(gè)閉回路。運(yùn)輸問(wèn)題的基本性質(zhì)7/22/202410(4)平衡型運(yùn)輸問(wèn)題的對(duì)偶問(wèn)題由于r(A’)=m+n-1，獨(dú)立的約束方程個(gè)數(shù)為m+n-1;而變量個(gè)數(shù)為m+n，則其中有一個(gè)自由變量7/22/202411例：海華設(shè)備廠下設(shè)三個(gè)位于不同地點(diǎn)的分廠A，B，C，該三個(gè)分廠生產(chǎn)同一個(gè)設(shè)備，設(shè)每月的生產(chǎn)能力分別為14臺(tái)、27臺(tái)和19臺(tái)。海華設(shè)備廠有四個(gè)固定的用戶，該四個(gè)用戶下月的設(shè)備需求量分別為22臺(tái)、13臺(tái)、12臺(tái)和13臺(tái)。設(shè)各分廠的生產(chǎn)成本相同，從各分廠到各用戶的單位設(shè)備運(yùn)輸成本如下表所示，而且各分廠本月末的設(shè)備庫(kù)存量為零。問(wèn)該廠應(yīng)如何安排下月的生產(chǎn)與運(yùn)輸，才能在滿足四個(gè)用戶需求的前提下使總運(yùn)輸成本最低。7/22/2024122321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供應(yīng)量供應(yīng)節(jié)點(diǎn)運(yùn)輸成本需求量需求節(jié)點(diǎn)6753842759106海華設(shè)備廠運(yùn)輸問(wèn)題網(wǎng)絡(luò)圖7/22/202413海華設(shè)備廠運(yùn)輸問(wèn)題的表格表示7/22/202414供應(yīng)量約束需求量約束海華設(shè)備廠運(yùn)輸問(wèn)題線性規(guī)劃模型7/22/202415不平衡運(yùn)輸問(wèn)題(1)：供過(guò)于求設(shè)置虛擬需求節(jié)點(diǎn)232131sB=27sC=19d1=22d2=13d3=12sA=14供應(yīng)量需求量6758425910供應(yīng)節(jié)點(diǎn)運(yùn)輸成本需求節(jié)點(diǎn)4d4=130007/22/202416不平衡運(yùn)輸問(wèn)題(2)：供不應(yīng)求設(shè)置虛擬供應(yīng)節(jié)點(diǎn)221341sB=27d1=22d2=13d3=12d4=13sA=14供應(yīng)量需求量67538427供應(yīng)節(jié)點(diǎn)運(yùn)輸成本需求節(jié)點(diǎn)3sC=1900007/22/2024176.2初始基可行解的確定獲得初始基可行解的常用方法：西北角法最小元素法Vogel法7/22/202418813131466(1)西北角法7/22/202419(2)最小元素法(0)7/22/202420(2)最小元素法(1)7/22/202421(2)最小元素法(2)7/22/202422(2)最小元素法(3)7/22/202423(2)最小元素法(4)7/22/202424(2)最小元素法(5)7/22/202425(2)最小元素法(6)7/22/202426(3)Vogel法22113331233113313144131319127/22/2024276.3最優(yōu)性檢驗(yàn)與基可行解的改進(jìn)(1)最優(yōu)性檢驗(yàn)充要條件由于基變量的檢驗(yàn)數(shù)σij=0,只需確定非基變量的檢驗(yàn)數(shù)！確定非基變量檢驗(yàn)數(shù)的常用方法主要是：閉回路法——非基變量與基變量構(gòu)成唯一閉回路位勢(shì)法——利用對(duì)偶變量7/22/202428(2)閉回路法(0)7/22/2024295(2)閉回路法(1)σ12=c12-c11+c21-c22=7-6+8-4=57/22/202430-55(2)閉回路法(2)σ13=c13-c11+c21-c23=5-6+8-2=57/22/202431557(2)閉回路法(3)σ14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=77/22/2024327559σ24=c24-c23+c33-c34=7-2+10-6=9(2)閉回路法(4)7/22/2024337955-11σ31=c31-c33+c23-c21=5-10+2-8=-11(2)閉回路法(5)7/22/2024347559-11-3σ32=c32-c33+c23-c22=9-10+2-4=-3(2)閉回路法(6)7/22/202435(3)位勢(shì)法對(duì)偶規(guī)劃由于對(duì)偶變量的個(gè)數(shù)為m+n，而系數(shù)矩陣的秩為m+n-1，我們可以通過(guò)設(shè)定自由變量的值得到所有對(duì)偶變量。7/22/202436(3)位勢(shì)法(0)7/22/202437選擇含基變量最多的行或列，令相應(yīng)的u或v為零。(3)位勢(shì)法(1)7/22/202438v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2(3)位勢(shì)法(2)7/22/202439u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8(3)位勢(shì)法(3)7/22/202440v4=c34-u3=6-8=-2(3)位勢(shì)法(4)7/22/202441(3)位勢(shì)法(5)5σ12=c12-(u1+

v2)=7-(-2+4)=57/22/2024425(3)位勢(shì)法(6)5σ13=c13-(u1+

v3)=5-(-2+2)=57/22/202443(3)位勢(shì)法(7)755σ14=c14-(u1+

v4)=3-(-2-2)=77/22/202444(3)位勢(shì)法(8)755σ24=c24-(u2+

v4)=7-(0-2)=997/22/202445(3)位勢(shì)法(9)7559σ31=c31-(u3+

v1)=5-(8+8)=-11-117/22/202446(3)位勢(shì)法(10)7559-11σ32=c32-(u3+

v2)=9-(8+4)=-3-37/22/202447(4)基可行解的改進(jìn)選擇檢驗(yàn)數(shù)絕對(duì)值最大的非基變量為進(jìn)基變量(存在多個(gè)時(shí)任選一個(gè))確定進(jìn)基變量確定離基變量選擇包含進(jìn)基變量的閉回路上距進(jìn)基變量奇次的變量中運(yùn)量最小的基變量為離基變量。運(yùn)量調(diào)整重復(fù)上述步驟直至所有檢驗(yàn)數(shù)大于零，即獲得最優(yōu)解。7/22/2024489755-11-3確定進(jìn)基變量選擇檢驗(yàn)數(shù)絕對(duì)值最大的非基變量為進(jìn)基變量7/22/2024499755-11-3確定閉回路7/22/2024509755-11-3確定離基變量7/22/2024519755-3調(diào)整運(yùn)量6x31=6,x21=8-6=2,x23=6+6=127/22/202452-2-4558進(jìn)一步優(yōu)化(0)117/22/202453-2-4558進(jìn)一步優(yōu)化(1)11x13

進(jìn)基，x34離基。7/22/20245424558進(jìn)一步優(yōu)化(2)11所有非基變量的檢驗(yàn)數(shù)均大于零，即為最優(yōu)解。7/22/202455(1)產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例：有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。等量化肥在這些地區(qū)使用效果相同。相關(guān)數(shù)據(jù)如下表，試分析總運(yùn)費(fèi)最節(jié)省的化肥調(diào)運(yùn)方案。需求地區(qū)化肥廠B1B2B3B4產(chǎn)量（萬(wàn)噸）A11613221750A21413191560A3192023---50最低需求（萬(wàn)噸）最高需求（萬(wàn)噸）3050707003010不限運(yùn)價(jià)：萬(wàn)元/萬(wàn)噸6.4其他運(yùn)輸問(wèn)題7/22/202456分析：這是一個(gè)產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題，總產(chǎn)量為160萬(wàn)噸，四個(gè)地區(qū)的最低需求為110萬(wàn)噸，最高需求為無(wú)限。根據(jù)現(xiàn)有產(chǎn)量，地區(qū)B4每年最多能分配到60萬(wàn)噸，這樣最高總需求為210萬(wàn)噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷(xiāo)平衡表中增加一個(gè)虛擬的化肥廠D，其年產(chǎn)量為50萬(wàn)噸。由于各個(gè)地區(qū)的需要量包含兩部分，如地區(qū)B1，其中30萬(wàn)噸是最低需求，故不能由虛擬的化肥廠D供給，令其相應(yīng)的運(yùn)輸價(jià)格為M（任意大正數(shù)），而另一部分20萬(wàn)噸滿足或不滿足均可，因此可以由虛擬的化肥廠D供給，并令其相應(yīng)的運(yùn)輸價(jià)格為0（沒(méi)有發(fā)生的運(yùn)輸）。對(duì)凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個(gè)地區(qū)看待。這樣可以建立這個(gè)問(wèn)題的產(chǎn)銷(xiāo)平衡表——7/22/202457產(chǎn)銷(xiāo)平衡表A1A2A3DB'1B''1B2B3B'4B''4

產(chǎn)量銷(xiāo)量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M13152050M7/22/202458產(chǎn)銷(xiāo)平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232M-19162217171415191920MMM0M160302020307/22/202459產(chǎn)銷(xiāo)平衡表

A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M167/22/202460產(chǎn)銷(xiāo)平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M102007/22/202461產(chǎn)銷(xiāo)平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M10103020407/22/202462產(chǎn)銷(xiāo)平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM167/22/202463產(chǎn)銷(xiāo)平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj1613502217171414132019151015301930192020230MMM0M030M02016008-1511111315151555722334-1M-23M-23M+44M+2M2030302007/22/202464產(chǎn)銷(xiāo)平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj135013201510153019301920200030020007-15121213151515447222241M-22M-22M+33M+2M1622171714141923MMM0MM167/22/202465產(chǎn)銷(xiāo)平衡表A1A2A3D1613502217171414132019151015301930192020023MMM0M030M0205060505030207030105016B'1B''1B2B3B'4B''4

產(chǎn)量

銷(xiāo)量7/22/202466(2)有轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題在上面所討論的問(wèn)題中，我們都假定物品是由產(chǎn)地直接運(yùn)送到目的地的，沒(méi)有經(jīng)過(guò)任何中間轉(zhuǎn)運(yùn)。然而，在實(shí)際當(dāng)中常常會(huì)遇到一種情形：需要先將物品由產(chǎn)地運(yùn)到某個(gè)中間轉(zhuǎn)運(yùn)站（可能是另外的產(chǎn)地、銷(xiāo)地或中間轉(zhuǎn)運(yùn)倉(cāng)庫(kù)），然后再轉(zhuǎn)運(yùn)到目的地。有時(shí)，可能經(jīng)過(guò)轉(zhuǎn)運(yùn)比直接運(yùn)到目的地更加經(jīng)濟(jì)。因此，在決定運(yùn)輸方案時(shí)有必要把轉(zhuǎn)運(yùn)也考慮進(jìn)去。這樣，將使運(yùn)輸問(wèn)題更加復(fù)雜。例：已知A1、A2、A3三個(gè)工廠生產(chǎn)同一種產(chǎn)品，用相同的價(jià)格供應(yīng)B1、B2、B3三個(gè)銷(xiāo)售點(diǎn)，有2個(gè)轉(zhuǎn)運(yùn)站T1、T2。允許產(chǎn)品在各工廠、銷(xiāo)售點(diǎn)和轉(zhuǎn)運(yùn)站間轉(zhuǎn)運(yùn)，已知各工廠、銷(xiāo)售點(diǎn)、轉(zhuǎn)運(yùn)站之間的單位運(yùn)價(jià)和產(chǎn)銷(xiāo)量如下表所示。試求最經(jīng)濟(jì)運(yùn)輸方案。7/22/202467產(chǎn)地轉(zhuǎn)運(yùn)站銷(xiāo)地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A1862-410830A2851395910A3654228720轉(zhuǎn)運(yùn)站T12148463T2-328232銷(xiāo)地B149242-5B2105863-4B38973254銷(xiāo)量1535107/22/202468解：將此轉(zhuǎn)運(yùn)問(wèn)題化為等價(jià)的運(yùn)輸問(wèn)題需作如下處理：將所有的產(chǎn)地、轉(zhuǎn)運(yùn)站和銷(xiāo)地都作為產(chǎn)地與銷(xiāo)地，則此問(wèn)題轉(zhuǎn)化為8個(gè)產(chǎn)地與8個(gè)銷(xiāo)地運(yùn)輸問(wèn)題；對(duì)擴(kuò)大的運(yùn)輸問(wèn)題建立運(yùn)價(jià)表，沒(méi)有運(yùn)輸路線的運(yùn)價(jià)設(shè)為M，自我運(yùn)輸?shù)倪\(yùn)價(jià)為0；所有轉(zhuǎn)運(yùn)站的產(chǎn)量等于銷(xiāo)量，且為最大可能調(diào)運(yùn)量，即均為60；在擴(kuò)大的運(yùn)輸問(wèn)題中，由于原產(chǎn)地與銷(xiāo)地均具有轉(zhuǎn)運(yùn)功能，所以原產(chǎn)地的產(chǎn)量?jī)捎谠N(xiāo)地的銷(xiāo)量均需加上最大可能調(diào)運(yùn)量，即在原數(shù)值上加上60。擴(kuò)大的運(yùn)輸表如下表所示。7/22