《运筹学基础(第2版)何坚勇 运输问题》由会员分享，可在线阅读，更多相关《运筹学基础(第2版)何坚勇 运输问题（125页珍藏版）》请在金锄头文库上搜索。
1、运输问题是线性规划问题，由于其约束条件的特殊性，产生了特殊的解法。,第五章 运输问题,例:,从3个发点A1，A2,，A3，向4个收点B1， B2， B3， B4发送某种货物。Ai 供应量为14，27，19。 Bj 收点的收量为22，13，12，13。 由Ai 运往Bj 单位货物的运费为Cij， 由Ai 运往Bj 货物的运量为Xij。 问如何调配，才能使运费最省？,2,3,2,1,3,4,1,运输问题网络图,s2=A2,s3=A3,B1,B2,B3,B4,s1=A1,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,B1,运输问题线性规划模型,供应地约束,需
2、求地约束,5.1运输问题数学模型和特点,5.1.1产销平衡问题的数学模型,问题的提出 从m个发点A1, A2, Am向n个收点B1, B2 Bn发送某种货物。 Ai发点的发量为ai， Bj收点的收量为bj。 由Ai 运往Bj 单位货物的运费为Cij， 由Ai 运往Bj 货物的运量为Xij。 问如何调配，才能使运费最省？,当发点的发量总和为 ai，收点的收量总和为 bj相等时，称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。若没有特别说明，均假定运输问题为平衡的运输问题。,续,Min Z= cijxiji j xij =ai (i=1,2m) xij =bj (j=1,2n)xij
3、 0 (i=1,2m; j=1,2n),5.1.1运输问题的数学模型,m,n,j,i,n,m,运输问题的数学模型： 其中 ai 0, bj 0, cij 0 且共有 m+n 个约束方程。 并成立： ai = bji j,m,n,X=(X11 ，X12，X1n，X21，X22， X2n，Xm1，Xm2，Xmn)T C= (C11，C12，C1n，C21，C22，C2n，Cm1，Cm2，Cmn) A=(P11，P12，P1n，P21，P22，P2n，Pm1，Pm2，Pmn),由于 ai = bj成立其m+n个约束方程并不是独立的。实际上只有m+n-1个是独立的。即约束方程系数矩阵的秩为m+n-1。
4、,运输问题解的结构,n,m,i,j,Pij,Pij=ei+em+j (i=1，.，m，j=1，n),ei为第i个分量为1其余分量为0的m+n维向量。 em+j为第m+j个分量为1其余分量为0的m+n维分量。,运输问题矩阵描述,min CX； S.T AX=b （5.1.3）x0,其中A为,A(m+n)(mn),X11 X12 X1n X21 X22 X2n. Xm1 Xm2 Xmn1 . 11 1 1 .1 1 11 11 1 11 1 1,A=,n,a1 a2am b1 b1 . bn,5.1.2运输问题数学模型的特点,(1),有m n列，每列有(m+n)个元素，其中有两个1，其余为0。 对
5、于列Pij来说，两个1的位置为i与m+j个分量 Pij=ei+e m+j ei为第i个分量为1其余分量为0的m+n维单位向量 e m+j为第m+j分量为1，其余分量为0的m+j分量为0的m+n维单位向量。,如,（2）,A有(m+n)行，每行前m行有n个1并连在一起，其余为零。,E 0 . 0 0 E . 0 0 0 E I I I,A=,E=(1，1，1，）,（3）运输问题有最优解,证明由于 ai = bj=d成立,令Xij= ai bj/d 5.1.6 I=1，2，m J= 1，2，n 代入5.1.1,n,m,i,j,续,Xi j = ai bj/d = bj (ai /d ) = ai (
6、 i=1，2，m) Xi j = ai bj/d = ai (bj /d ) = bj (j=1，2，n)ai 0，bj0，所以Xij 0,n,j=1,n,j=1,n,j=1,m,m,m,i=1,i=1,i=1,xu,5.1.6是运输问题的 可行解。由定理2.4.6可得运输问题必有基本可行解。 由Xi j 的定义知， Xi j min(ai ，bj）可行域是有界的。必有最优解。,（4）矩阵A的秩为（m+n-1）,A是一个（m+n）（ m*n）型矩阵 一般来说： （m+n）（ m*n） 因此秩最大为（m+n） 又前m方程与后n个方程和相等。 故r（A） ，实际是等于（m+n-1）。,A(m+n)
7、(mn),X11 X12 X1n X21 X22 X2n. Xm1 Xm2 Xmn1 . 11 1 1 .1 1 11 11 1 11 1 1,A=,n,a1 a2am b1 b1 . bn,A(m+n)(mn),p11 p 12 p 1n p 21 p 31 p m1 0 0 . 0 1 1 .1 1 1 . 11 1,A=,证明,p11 p 12 p 1n p 21 p 31 p m1 线性无关，而p ij与 p ij 只差一个分量。 由向量相关理论可知：一组线性无关向量组在相同的位置上加相同多的分量后得到的新向量也线性无关。 因此 p11 p 12 p 1n p 21 p 31 p m1
8、也线性无关。 r(A)= (m+n-1),5.2表上作业法,由于运输问题的特殊性，因此求解运输问题往往不用单纯形法。而用表上作业法。 1、用西北角法或最小元素法确定基本可行解。 2、用位势法求解检验数 3、用闭回路调整法求最优解,调运表,发点,收点,例5.2.1表5.3,收点,发点,5.2运价表,收点,发点,1、西北角法,(I，j)， 从（1，1）开始，比较a1，b1。 X11=min（a1，b1）=b1=3,表5.3,收点,发点,表5.4,X11=min（a1，b1）=b1=3 X12=min（a1，b2）= a1 =4 X22=min（a2，b2）= b2 =2 X23=min（ a2 ，
9、b3）= min（ 2 ，5）= a2 =2 X33=min（ a3 ，b 3）= min（ 9 ，3）= b3 =3 X34=min（ a3 ，b4）= 6,表5.5,Z=33+ 411+ 29+ 22+ 310+ 65=133(万),2、最小元素法(表5.6-7),3,6,4,1,3,3,C21=1，X21=min（a2，b1）=b1=3 C23=2， X23=min（a2，b3）= min（ 1，5）= a2 =1 C13=3， X13=min（a1，b3） = min（ 7，4）= b3 =4 C32=4， X32=min（ a2 ，b2）= b2 =6 C34=5， X34=min（
10、 a3 ，b 4）= min（ 3 ，6）= a3 =3 C14=10， X14=min（ a 1 ， b4 ）= a1= b4=3 Z=43+ 310+ 31+ 12+ 64+ 35=86(元),5.2.2位势法求检验数,ij=Cij-Zij= Cij-CBB-1 Pij 5.2.1 (i=1，2m； j=1，2n),Max f= aiui+ bjvj st ui+ vj Cij (i=1，2m) (j=1，2n)ui， vj 无正负,W=(u1，um，v1，vn） 5.2.3 Ui=(xi1,xi2,xi3,xi4xin), vj=(x1j,x2j,xxmj),m,I=1,j=1,n,Mi
11、n Z= cijxiji j xij =ai (i=1,2m) xij =bj (j=1,2n)xij 0 (i=1,2m; j=1,2n),5.1.1运输问题的数学模型,m,n,j,i,n,m,运输问题线性规划模型,供应地约束,需求地约束,5.2.3代5.2.1,ij=Cij-WPij= Cij- (u1，um，v1，vn)( ei+e m+j)=Cij- (ui+vj） 5.2.4(i=1，2m；j=1，2n),A=,n,X11 X12 X1n X21 X22 X2n. Xm1 Xm2 Xmn1 . 11 1 1 .1 1 11 11 1 11 1 1,基变量的 : Cij- (ui+vj
12、）=0 （i，j）JB （5.2.5） 因为为已知，而（ 5.2.5）有（m+n）个未知量 令 Vn=0 （5.2.6） 非基变量检验数: ij= =Cij- (ui+vj） (i，j）JN （ 5.2.7）,A、公式求检验数,表5.5,Z=33+ 411+ 29+ 22+ 310+ 65=133(万),5.2.1例表5.5,基变量: X11 ， X12 ，X22 ， X23 ， X33 ， X34 C11- (u1+v1）=0 C12- (u1+v2）=0 C22- (u2+v2）=0 C23- (u2+v3）=0 C33- (u3+v3）=0 C34- (u3+v4）=0 V4=0,代入Cij,3- (u1+v1）=0 11- (u1+v2）=0 9- (u2+v2）=0 2- (u2+v3）=0 10- (u3+v3）=0 5- (u3+v4）=0 V4=0 解出： u1 =-1 ， u2 =-3 ， u3 =5 ， v1 =4 ， v2 =12 ， u3 =5 ，,
