運輸問題及其數(shù)學模型

運輸問題及其數(shù)學模型第1頁，課件共25頁，創(chuàng)作于2023年2月第一節(jié)運輸問題的典例和數(shù)學模型第2頁，課件共25頁，創(chuàng)作于2023年2月例1產(chǎn)地A1A2A3三產(chǎn)地四銷地,同類可互換產(chǎn)品，單位運價(元/t),如何調(diào)運，運費最少？794產(chǎn)量x

21x

22x

23x

24x

11x

12x

13x

14x

31x

32x

33x

34銷量6635198231110374510B1銷地B2B4B3第3頁，課件共25頁，創(chuàng)作于2023年2月=3x11+11x12+3x13+10x

14+x21+9x22+2x23+8x24+7x

31

+4x32+10x33+5x34

x11+x12+x13+

x14=7x11+

x21+x31=3xij

≥0,(i=1,2,3;j=1,2,3,4)數(shù)學模型i=13min

Z=∑∑cijxijj=14x21+x22+x23+

x24=4x12+

x22+x32=6x31+x32+x33+

x34=9x13+

x23+x33=5x14+

x24+x34=6第4頁，課件共25頁，創(chuàng)作于2023年2月第一節(jié)運輸問題及其數(shù)學模型一、運輸問題數(shù)學模型產(chǎn)地A1A2Am...B1銷地B2Bn…銷量…b

2b

nb

1a1...ama2產(chǎn)量x

11x

12x

1n…x

21x

22x

2n…x

m1x

m2x

mn…............c

11c

12c

1n…c

21c

22c

2n…c

m1c

m2c

mn……………第5頁，課件共25頁，創(chuàng)作于2023年2月產(chǎn)銷平衡運輸問題數(shù)學模型i=1mmin

Z

=∑∑cijxijj=1n平衡(產(chǎn)=銷)i=1Q=j=1m∑a

i

=∑b

jnxij≥0,(i=1,2,…,m;j=1,2,…,n)(i=1,2,…,m)∑

xij=ai,j=1n(j=1,2,…,n)∑

xij=bj,i=1mm+n個方程中只有m+n-1個方程是獨立的,

∴運輸問題的基本可行解有m+n-1個分量第6頁，課件共25頁，創(chuàng)作于2023年2月1.運輸問題有有限最優(yōu)解2.運輸問題約束條件的系數(shù)矩陣二、運輸問題數(shù)學模型的特點x11x12

…

x1nxm1

xm2

…

xm

n

…

x21x22

…

x2n

111…...111…111…Aij=(0,…,0,1,0,…,0,1,…,0)第

i

個

第(m+

j)個

111…

111…

111

…

............m+n個方程中只有m+n-1個方程是獨立的,

∴運輸問題的基本可行解有m+n-1個分量.n個m個前m個之和等于后n個之和第7頁，課件共25頁，創(chuàng)作于2023年2月§2表上作業(yè)法

(1)找出初始基可行解(2)求各非基變量的檢驗數(shù)(3)確定換入變量和換出變量(4)重復(fù)(2),(3)步，直到求得最優(yōu)解為止第8頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1最小元素法產(chǎn)地A1A2A33銷地34361初始調(diào)運方案(初始基可行解)3198231110374510B1B2B4B3134386元第9頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1最小元素法產(chǎn)地A1A2A33銷地4361初始調(diào)運方案(初始基可行解)198231110374510B1B2B4B3基變量取值，0也是取值386元空格為非基變量第10頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1沃格爾(Vogel)法

產(chǎn)地A1A2A31銷地34225

(初始基可行解)行罰數(shù)311103B1B2B4B320列罰數(shù)1982745101342551301121321201201363322532121217600兩最小元素之差兩最小元素之差第11頁，課件共25頁，創(chuàng)作于2023年2月二解的最優(yōu)性檢驗-閉回路法1此空格為入基變量。由一個空格和若干個有數(shù)字的水平和垂直連線包圍成的封閉回路。第12頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1閉回路法調(diào)整產(chǎn)地A1A2A33銷地4361非基變量（空格）的檢驗數(shù)198231110374510B1B2B4B3386元＋－＋－，min(3,1)=1從空格出發(fā)沿封閉回路前進,順時逆時均可.檢驗數(shù)8-2+3-10=-1，需調(diào)整第13頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1產(chǎn)地A1A2A33銷地536初始調(diào)運方案(初始基可行解)198231110374510B1B2B4B3286元＋－＋－，min(3,1)=1從空格出發(fā)沿封閉回路前進,順時逆時均可.185元第14頁，課件共25頁，創(chuàng)作于2023年2月vj910230-5-1ui二、解的最優(yōu)性檢驗

-位勢法2產(chǎn)地A1A2A33銷地4361198231110374510B1B2B4B3386元121-110127個變量6個方程需補充一個方程u1=0基變量的檢驗數(shù)為0第15頁，課件共25頁，創(chuàng)作于2023年2月vj910230-5-1ui二、解的最優(yōu)性檢驗-位勢法產(chǎn)地A1A2A33銷地4361198231110374510B1B2B4B3386元121-11012調(diào)整量：min(3,1)=1找出非基變量的檢驗數(shù)為負空格的閉回路第16頁，課件共25頁，創(chuàng)作于2023年2月vj910330-5-2ui二、解的最優(yōu)性檢驗-位勢法產(chǎn)地A1A2A33銷地4361198231110374510B1B2B4B3386元185元52調(diào)整量：min(3,1)=1找出非基變量的檢驗數(shù)為負空格的閉回路第17頁，課件共25頁，創(chuàng)作于2023年2月vj910330-5-2ui二、解的最優(yōu)性檢驗-位勢法產(chǎn)地A1A2A33銷地2362198231110374510B1B2B4B3086元185元52非基變量的檢驗數(shù)無負值，最優(yōu)方案！1219最優(yōu)解不唯一第18頁，課件共25頁，創(chuàng)作于2023年2月表上作業(yè)法一.給出運輸問題的初始基可行解（初始調(diào)運方案）三.解的改進1.最小元素法二.解的最優(yōu)性檢驗2.位勢法(Dualvariablemethod)1.閉回路法2.Vogel法a.閉回路；b.每個空格都唯一存在一條閉回路

閉回路；第19頁，課件共25頁，創(chuàng)作于2023年2月表上作業(yè)

計算框圖分析問題列出產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案求檢驗數(shù)(閉回路法或位勢法)所有檢驗數(shù)≥0對絕對值最大的負檢驗數(shù)用閉回路法調(diào)整，得出新調(diào)運方案得到最優(yōu)方案算出總運價是否第20頁，課件共25頁，創(chuàng)作于2023年2月四.幾點說明1.多個空格(非基變量)的檢驗數(shù)為負通常取σ

ij

<0中最小者為換入變量.3.退化補0,基變量個數(shù)恰好為(m+n-

1

)有多重最優(yōu)解某空格填入一量時,同時劃去一行一列,2.若某非基變量檢驗數(shù)為0，(產(chǎn)銷恰好等量)4.產(chǎn)銷不平衡增加一假想少的一方,運費為零。第21頁，課件共25頁，創(chuàng)作于2023年2月五.供求不平衡運輸問題

例2B1B2B3B4產(chǎn)量A1211347A2103595A378127銷量2346[7+5+7]-[2+3+4+6]=4產(chǎn)>銷填一個虛擬的銷地第22頁，課件共25頁，創(chuàng)作于2023年2月供求不平衡運輸問題—供求平衡問題

B1B2B3B4B5產(chǎn)量A12113407A21035905A3781207銷量23464填一個虛擬的銷地B5，運價為0第23