運(yùn)輸問題及其數(shù)學(xué)模型

運(yùn)輸問題及其數(shù)學(xué)模型第1頁，課件共25頁，創(chuàng)作于2023年2月第一節(jié)運(yùn)輸問題的典例和數(shù)學(xué)模型第2頁，課件共25頁，創(chuàng)作于2023年2月例1產(chǎn)地A1A2A3三產(chǎn)地四銷地,同類可互換產(chǎn)品，單位運(yùn)價(jià)(元/t),如何調(diào)運(yùn)，運(yùn)費(fèi)最少？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ù)學(xué)模型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é)運(yùn)輸問題及其數(shù)學(xué)模型一、運(yùn)輸問題數(shù)學(xué)模型產(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)銷平衡運(yùn)輸問題數(shù)學(xué)模型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個(gè)方程中只有m+n-1個(gè)方程是獨(dú)立的,

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

…

x1nxm1

xm2

…

xm

n

…

x21x22

…

x2n

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

i

個(gè)

第(m+

j)個(gè)

111…

111…

111

…

............m+n個(gè)方程中只有m+n-1個(gè)方程是獨(dú)立的,

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

(1)找出初始基可行解(2)求各非基變量的檢驗(yàn)數(shù)(3)確定換入變量和換出變量(4)重復(fù)(2),(3)步，直到求得最優(yōu)解為止第8頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1最小元素法產(chǎn)地A1A2A33銷地34361初始調(diào)運(yùn)方案(初始基可行解)3198231110374510B1B2B4B3134386元第9頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1最小元素法產(chǎn)地A1A2A33銷地4361初始調(diào)運(yùn)方案(初始基可行解)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)性檢驗(yàn)-閉回路法1此空格為入基變量。由一個(gè)空格和若干個(gè)有數(shù)字的水平和垂直連線包圍成的封閉回路。第12頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1閉回路法調(diào)整產(chǎn)地A1A2A33銷地4361非基變量（空格）的檢驗(yàn)數(shù)198231110374510B1B2B4B3386元＋－＋－，min(3,1)=1從空格出發(fā)沿封閉回路前進(jìn),順時(shí)逆時(shí)均可.檢驗(yàn)數(shù)8-2+3-10=-1，需調(diào)整第13頁，課件共25頁，創(chuàng)作于2023年2月銷量6635794產(chǎn)量例1產(chǎn)地A1A2A33銷地536初始調(diào)運(yùn)方案(初始基可行解)198231110374510B1B2B4B3286元＋－＋－，min(3,1)=1從空格出發(fā)沿封閉回路前進(jìn),順時(shí)逆時(shí)均可.185元第14頁，課件共25頁，創(chuàng)作于2023年2月vj910230-5-1ui二、解的最優(yōu)性檢驗(yàn)

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

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

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

ij

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

1

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

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

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