《运筹学运输问题解析》由会员分享，可在线阅读，更多相关《运筹学运输问题解析（50页珍藏版）》请在金锄头文库上搜索。
1、第四章 运输问题第一节 运输问题及其数学模型 第二节 表上作业法第三节 产销不平衡问题第一节 运输问题及其数学模型一、运输问题的典型形式及其数学模型1.引例求最小运费的运输方案销地产地B1B2B3产量A1645300A2655200销量150150200minZ = 6x11 + 4x12+5x13+6x21 +5x22 +5x23x11 +x12+x13 = 300 x21+x22+x23 = 200 x11 +x21 = 150 x12 +x22 = 150 x13 +x23 = 200xij 0A1AmB1B2Bna1cijA2a2ambnb2b1求最小运费的运输方案2. 典型的运输问题
2、：销地 产地B1B2Bn产量A1a1A2a2Amam销量b1b2bnc11c12cm1c21c22c2nc1ncmncm2销地产地B1B2Bn产量A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam销量b1b2bnc11c12cm1c21c22c2nc1ncmncm2minZ = 6x11 + 4x12+5x13+6x21 +5x22 +5x23x11 +x12+x13 = 300 x21+x22+x23 = 200 x11 +x21 = 150 x12 +x22 = 150 x13 +x23 = 200xij 03. 运输问题的数学模型i=1,2j =1, 2, 3
3、xij 0i=1,2,mj =1, 2, ,nxij 0典型运输问题的数学模型 产销平衡问题为等式约束。 产销平衡问题中各产地产量之和与各销 售地点的销量之和相等。二、运输问题数学模型的特点：1. 运输问题一定有最优解；2. 运输问题约束条件的系数矩阵：x11 +x12+x13 = 300x21+x22+x23 = 200 x11 + x21 = 150x12 +x22 = 150x13 +x23 = 200xij 0x11 x12 x13 x21 x22 x23 1 1 11 1 11 1 1 11 12个3个x11 +x12+ +x1n =a1x21+x22+ +x2n =a2 xm1+x
4、m2+ +xmn =am x11 + x21 + xm1 =b1x12 +x22 + xm2 =b2 x1n +x2n + xmn=bnxij 0x11 x12 x1n x21 x22 x2n xm1 xm2 xmn1 1 11 1 1 1 1 11 1 11 1 1 1 1 1mn系数矩阵的特点：（1）约束条件的系数矩阵的元素只有两个： 0、1。（2）元素 xij 对应于每一个变量在前m个约 束方程中(第i个方程中)出现一次，在后n个约 束方程中（第m+j 个方程中）也出现一次。3. 运输问题基变量的个数：m+n-1个 返回第二节 表上作业法一、表上作业法的基本思想和步骤：1.基本思想：同单
5、纯形法的基本思想基本可行解是否为最优解换基结束YN2. 表上作业法的步骤（1）寻找初始基可行解；西北角法、最小元素法、vogol法（2）求出非基变量检验数（空格检验数 ），判断是否为最优解；闭回路法、位势法（3）换基改进，找到新的基可行解闭回路调整法（4 ）重复（2）（3）销地产地B1B2B3B4产量A116A210A322销量8141214484125210391146811（一）西北角法二、确定初始基可行解求运费最小的运输方案。 销地产地B1B2B3B4产量A116A210A322销量814121448412521039114681180886060448080141400销地产地B1B2
6、B3B4产量A18816A26410A381422销量8141214484125210391146811（一）西北角法运费为 372元返回销地产地B1B2B3B4产量A116A210A322销量8141214484125210391146811（二）最小元素法：销地产地B1B2B3B4产量A116A210A322销量8141214488041252103911468112201010061408860600销地产地B1B2B3B4产量A110616A28210A314822销量8141214484125210391146811（二）最小元素法运费为 246元返回（三）vogol法1.罚数=次小
7、费用-最小费用2.找出最大的罚数行或列所对应的最小 费用优先安排。3.重复计算步骤1和2。4125210391146811销地 产地B1B2B3B4产量行罚 数 A116 A210 A322 销量814121448列罚数2140151381 28 060280276120411942092销地产地B1B2B3B4产量A112416A28210A314822销量8141214484125210391146811运费为 244元（三）vogol法有数字的格/空格比较三种方法的运费的大小：返回三、最优解的判别（计算空格检验数）(一)闭回路法闭回路：从空格出发，遇到数字格 可以旋转90度，最后回到空格
8、所构成的 回路。原理：利用检验数的经济含义4125210391146811销地 产地B1B2B3B4产量A110616 A28210 A314822销量81412144811=4-4+3-2=111=4-4+3-2=1 12=12-11+6-5=222=10-3+4-11+6-5=1 24=9-11+4-3= -131=8-2+3-4+11-6=10 33=11-6+11-4=1222=10-3+4-11+6-5=1 返回(二)对偶变量法（位势法）1.基本原理i=1,2,mj =1, 2, ,nxij 0x11 +x12+ +x1n =a1x21+x22+ +x2n =a2 xm1+xm2+
9、+xmn =am x11 + x21 + xm1 =b1x12 +x22 + xm2 =b2 x1n +x2n + xmn=bnxij 0minZ = c11x11 + c12x12+ +c1nx1n + +cm1xm1 +cm2xm2 + +cmnxmn设对偶变量向量为Y=(u1,u2, ,um, v1, v2, ,vn)对偶规划为 ui+vjciji=1,2,3 mj=1,2,3 nj = C j - CBB-1 Pj = Cj - Y Pj ij = C ij - CBB-1 Pij = Cij - Y Pij = Cij - (u1,u2, ,um, v1, v2, ,vn) Pij
10、= Cij - ( ui+ vj )当xij 为基变量时ij = Cij - ( ui+ vj )=0由此，任选一个对偶变量为0，可求出 其余所有的ui， vj 。再根据ij = Cij - ( ui+ vj )求出所有非基 变量的检验数。销地 产地B1B2B3B4产 量uiA110616u1= A28210u2= A314822u3=销量814121448vjv1=v2=v3=v4=4125210391146811v1+u2=2v2+u3=5v3+u1=4v3+u2=3v4+u1=11v4+u3=6令u1=0，则有： v3=4v4=11u2=-1u3=-5v1=3v2=10销地 产地B1B2
11、B3B4产 量uiA110616 u1= 0 A28210 u2= -1 A314822 u3= -5销量814121448vjv1= 3 v2=10 v3= 4 v4=11412521039114681111=4-(3+0) =1 12=12-(10+0)=222=10-(10-1)=1 24=9-(11-1)=-131=8-(-5+3)=10 33=11-(-5+4)=12 返回四、解的改进闭回路调整法销地 产地B1B2B3B4产量A110616 A28210 A314822销量814121448当表中出现负的检验数时，用闭回路法进行调整销地 产地B1B2B3B4产量A110+2 6-216 A28 2-2+210 A314822销量814121
