运输问题及其数学模型

运输问题及其数学模型第一页，共二十五页，2022年，8月28日第一节运输问题的典例和数学模型第二页，共二十五页，2022年，8月28日例1产地A1A2A3三产地四销地,同类可互换产品，单位运价(元/t),如何调运，运费最少？794产量x

21x

22x

23x

24x

11x

12x

13x

14x

31x

32x

33x

34销量6635198231110374510B1销地B2B4B3第三页，共二十五页，2022年，8月28日=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)数学模型i=13min

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

x24=4x12+

x22+x32=6x31+x32+x33+

x34=9x13+

x23+x33=5x14+

x24+x34=6第四页，共二十五页，2022年，8月28日第一节运输问题及其数学模型一、运输问题数学模型产地A1A2Am...B1销地B2Bn…销量…b

2b

nb

1a1...ama2产量x

11x

12x

1n…x

21x

22x

2n…x

m1x

m2x

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

11c

12c

1n…c

21c

22c

2n…c

m1c

m2c

mn……………第五页，共二十五页，2022年，8月28日产销平衡运输问题数学模型i=1mmin

Z

=∑∑cijxijj=1n平衡(产=销)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个分量第六页，共二十五页，2022年，8月28日1.运输问题有有限最优解2.运输问题约束条件的系数矩阵二、运输问题数学模型的特点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个之和第七页，共二十五页，2022年，8月28日§2表上作业法

(1)找出初始基可行解(2)求各非基变量的检验数(3)确定换入变量和换出变量(4)重复(2),(3)步，直到求得最优解为止第八页，共二十五页，2022年，8月28日销量6635794产量例1最小元素法产地A1A2A33销地34361初始调运方案(初始基可行解)3198231110374510B1B2B4B3134386元第九页，共二十五页，2022年，8月28日销量6635794产量例1最小元素法产地A1A2A33销地4361初始调运方案(初始基可行解)198231110374510B1B2B4B3基变量取值，0也是取值386元空格为非基变量第十页，共二十五页，2022年，8月28日销量6635794产量例1沃格尔(Vogel)法

产地A1A2A31销地34225

(初始基可行解)行罚数311103B1B2B4B320列罚数1982745101342551301121321201201363322532121217600两最小元素之差两最小元素之差第十一页，共二十五页，2022年，8月28日二解的最优性检验-闭回路法1此空格为入基变量。由一个空格和若干个有数字的水平和垂直连线包围成的封闭回路。第十二页，共二十五页，2022年，8月28日销量6635794产量例1闭回路法调整产地A1A2A33销地4361非基变量（空格）的检验数198231110374510B1B2B4B3386元＋－＋－，min(3,1)=1从空格出发沿封闭回路前进,顺时逆时均可.检验数8-2+3-10=-1，需调整第十三页，共二十五页，2022年，8月28日销量6635794产量例1产地A1A2A33销地536初始调运方案(初始基可行解)198231110374510B1B2B4B3286元＋－＋－，min(3,1)=1从空格出发沿封闭回路前进,顺时逆时均可.185元第十四页，共二十五页，2022年，8月28日vj910230-5-1ui二、解的最优性检验

-位势法2产地A1A2A33销地4361198231110374510B1B2B4B3386元121-110127个变量6个方程需补充一个方程u1=0基变量的检验数为0第十五页，共二十五页，2022年，8月28日vj910230-5-1ui二、解的最优性检验-位势法产地A1A2A33销地4361198231110374510B1B2B4B3386元121-11012调整量：min(3,1)=1找出非基变量的检验数为负空格的闭回路第十六页，共二十五页，2022年，8月28日vj910330-5-2ui二、解的最优性检验-位势法产地A1A2A33销地4361198231110374510B1B2B4B3386元185元52调整量：min(3,1)=1找出非基变量的检验数为负空格的闭回路第十七页，共二十五页，2022年，8月28日vj910330-5-2ui二、解的最优性检验-位势法产地A1A2A33销地2362198231110374510B1B2B4B3086元185元52非基变量的检验数无负值，最优方案！1219最优解不唯一第十八页，共二十五页，2022年，8月28日表上作业法一.给出运输问题的初始基可行解（初始调运方案）三.解的改进1.最小元素法二.解的最优性检验2.位势法(Dualvariablemethod)1.闭回路法2.Vogel法a.闭回路；b.每个空格都唯一存在一条闭回路

闭回路；第十九页，共二十五页，2022年，8月28日表上作业

计算框图分析问题列出产销平衡表及单位运价表确定初始调运方案求检验数(闭回路法或位势法)所有检验数≥0对绝对值最大的负检验数用闭回路法调整，得出新调运方案得到最优方案算出总运价是否第二十页，共二十五页，2022年，8月28日四.几点说明1.多个空格(非基变量)的检验数为负通常取σ

ij

<0中最小者为换入变量.3.退化补0,基变量个数恰好为(m+n-

1

)有多重最优解某空格填入一量时,同时划去一行一列,2.若某非基变量检验数为0，(产销恰好等量)4.产销不平衡增加一假想少的一方,运费为零。第二十一页，共二十五页，2022年，8月28日五.供求不平衡运输问题

例2B1B2B3B4产量A1211347A2103595A378127销量2346[7+5+7]-[2+3+4+6]=4产>销填一个虚拟的销地第二十二页，共二十五页，2022年，8月28日供求不平衡运输问题—供求平衡问题

B1B2B3B4B5产量A12113407A21035905A3781207销量23464填一个虚拟的销地B5，运价为0第二十三页，