第三章运输问题

表示运输问题的表格表示运价运量检验数σij运输表中一个基必须具备特点 运输表中一个基必须具备的特点 1、一个基应占表中的m+n-1格; 2、构成基的同行同列格子不能构成闭回路; 3、一个基在表中所占的格子应包括表的每行和每列。 运输表中一个基必须具备特点null基在运输表中的表示null运输表中同行同列的变量组成回路三、初始基础可行解的求法三、初始基础可行解的求法1、西北角法 2、最小元素法1、西北角法1、西北角法813131466null2、最小元素法（1）null最小元素法（2）null最小元素法（3）null最小元素法（4）null最小元素法（5）null最小元素法（6）1、检验数的求法：闭回路法闭回路——从调运方案的某一空格出发，沿水平或垂直的方向前进，遇到一个适当的数字格便按与前进方向垂直的路径前进。经过若干次后，再回到原来出发的那个格，由此形成的封闭折线称为闭回路。 闭回路的性质： 以空格出发的闭回路存在且唯一； 不存在所有顶点都为数字格的闭回路。 四、最优解的获得1、检验数的求法：闭回路法null-5非基变量xij的检验数zij-cij—闭回路法(1)算法：空格（i,j)的检验系数σij可表示为：由空格所作出的闭回路中所有偶数格对应的单位运价之和减去所有 奇数格对应的单位运价之和的差。 σ12=z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5null-5σ13=z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5闭回路法(2)null-5z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7-7-5闭回路法(3)null-5z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9-9-5-7闭回路法(4)null-5z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11+11-5-7-9闭回路法(5)null-5z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3+3-5-7-9+11闭回路法(6)2、进基和离基变量的选择2、进基和离基变量的选择（1）将具有最大正检验数的变量作为入基变量； （2）由入基变量出发，找出一条闭合回路，在其偶数号中，取值最小的变量为出基变量； （3）运输量的调整，对所有奇数号的变量都加上调整量的值，所有偶数号的变量减掉调整量的值； （4）在新的基础可行解的基础上重新计算检验数，直到所有的检验数都小于零。例题，入基变量与进基变量的选择x31进基, min{x21,x33}=min{8,6}=6, x33离基+3-5-5-7-9+11例题，入基变量与进基变量的选择null调整运量,重新计算检验数,确定进基、离基变量x14进基, min{x11,x34}=min{14,13}=13, x34离基-11-5-5+4+2-8null调整运量, 重新计算检验数所有zij-cij<0,得到最优解。 Min z=6×1+3 ×13+8 ×2+4 ×13+2 ×12+5 ×19=142-11-5-5-4-8-2五、几种特殊的运输问题（一）产销不平衡的运输问题1、供大于求解决问题的思路：产销不平衡→产销平衡五、几种特殊的运输问题null供大于求，则虚设收地，运价为零,这样就把供求不平衡问题转化为供求平衡问题。7004在新问题中，新得到的问题的最优解，实际上就是各发地存储多少、运出多少、运往何地，使总运价最低。不平衡问题如左图，相应的平衡问题如右图不平衡问题如左图，相应的平衡问题如右图 15 251212310101032412100利用西北角法给出初始解利用西北角法给出初始解15 10 002510-2-5+6X21进基，x22离基X21进基，x22离基15 10 002510+4+1-6X13进基，x11离基X13进基，x11离基15 10 002510-4-3-2null2、供不应求null供不应求，则虚设发地，运价为零310000null（二）无运输通路如：Ａ２至Ｂ３无运输通路null无运输通路，则运价为MM例题，从发点2到收点2没有路线，虚设一条通路，并设c22=M例题，从发点2到收点2没有路线，虚设一条通路，并设c22=M8-MX12进基，x22离基X12进基，x22离基X13进基，x11离基X13进基，x11离基（三）运输问题的退化基础可行解：基变量的个数小于m+n-1（三）运输问题的退化基础可行解：基变量的个数小于m+n-1 为了使基变量的个数保持m+n-1个，需要增加一个xij=0的基变量，但不能构成闭回路。null确定初始基础可行解西北角法最小元素法求非基变量的检验数闭回路法确定进基变量确定离基变量得到新的基础可行解运输问题单纯形法沿回路调整运量null35638422530z=1428例题：用西北角法得到初始基础可行解null-3z12-c12=(c11-c21+c22)-c12=(8-9+10)-12=-3z=1428用闭回路法求各非基变量的检验数null35638422530-3-2用闭回路法求各非基变量的检验数null35638422530-3-2-9用闭回路法求各非基变量的检验数null35638422530-3-2-9-11用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9+4用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9+4+2用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9+4+2x32进基，x33离基null356162622530-3-2+5+3-9-14-5-10-12重新用闭回路法计算非基变量的检验数null356162622530-3-2+5+3-9-14-5-10-12x14进基，x34离基null3011112627530-3-2-5-2-9-140-5-7重新计算各非基变量的检验数已获得最优解。x11=30，x14=5，x21=11，x22=11，x23=26，x32=27，x44=30，min z=1095null问题：从A1到B1的运价C11=8，从A1到B2的运价C12=12 在什么范围内变化，以上最优解保持不变？ 物流配送案例物流配送案例腾飞电子仪器厂在大连和广州有两个分厂生产同一种仪器 。大连分厂每月生产400台．广州分厂每月生产600台。该公司在上海和天津有两个物流配送服务网点，负责对南京、济南、南昌、青岛四个城市的仪器进行配送供应。另外，因为大连距离青岛较近，公司同意大连分厂向青岛直接供货。 这些城市间的每台仪器的运输费用标在两个城市间的弧上，单位为百元。公司应该如何调运仪器可使总运输费用最低? 广州 600南昌 350天津南京 200济南 150大连 400青岛 300上海2446362561433