运筹学章3运输问题(增补).ppt

1、运输问题,第一节 运输问题的基本理论,运输问题通用模型 决策变量列的特点 表上作业法（重点）,运输问题的实例,某大米销售公司有2个仓库，3个商店。根据3个店的订货需求，供货方已经把大米运到了2个仓库。公司希望以最小的总运费把大米运走满足三个商店的需求，问应该如何确定运输方案。数据如表所示：,2个产地，3个销地。在产销平衡的条件下，确定最小运费运输方案。,单位运价：从某仓库到某商店，每吨大米的运价,从仓库A2到商店B2，每吨大米的运价是5（千元）,运输问题的一般描述,m个产地，各地产量为ai。 n个销地，各地销量为bj。 总需求=总供给 最小运费方案？,实例的线规模型,Xij产地i到销地j的运量

2、,3 4 2 3 5 3,x11 x12 x13 x21 x22 x23,供给的要求，大米都运走 x11+x12+x13=10 x21+x22+x23=4,需求的要求，大米都运到 x11+x21=3 x12+x22=5 x13+x23=6,运价最低 MINZ= 3x11+4x12+2x13 +3x21+5x22+3x23,MINZ= 3x11+4x12+2x13 +3x21+5x22+3x23 供x11+x12+x13=10 x21+x22+x23=4 需 x11+x21=3 x12+x22=5 x13+x23=6 多余约束？ 秩（2+3-1）=(m+n-1),运输问题通用模型,秩为(m+n-

3、1),Xij列向量特点,Z= 3x11+4x12+2x13+3x21+5x22+3x23,x11 + x12 + x13,=10,x21+ x22+ x23=4,x11,+ x21,=3 =5 =6,x12,+ x22,x13,+ x23,每列只有两个1,第一个1在第i行,第二个1在第m+j行,第1行,第2+3行,设某运输问题有m个产地，n个销地。 每个Xij的列向量只有两个1 第一个在第i行 第二个在第m+j行,运输问题的表上作业法,运输问题总是有解，且总是有最优解。 找初始解：最小元素法，差额元素法。 求检验数：闭回路法，位势法。 判优：无负检验数 调整：闭回路法。返回,求初始解：最小元素

4、法,从运价最小的地方开始运。,1,3,1,2,3,4,6,3,3,每填一个数，或划掉一行，或划掉一列。最后既划掉一行又划掉一列。因此一共有M+N-1个,求初始解：差额元素法,计算每行、列的最低和次低运价差。 以此作为罚数 罚数意味着，如果不用最低运价，而用次低运价会遭受的损失。 因此应从罚数最大处起运。,求初始解：差额元素法,首先计算行列差额：次小 减 最小,0 1 1,2 1 3,5,从差额最大处的最小运价处起运,否则将受到惩罚,4,(6),重新计算行列差额，填下一个数,0 1 2,(3),判优：闭回路法,闭回路的特点： 是以单元格为顶点的封闭回路 每行、列有且仅有两个顶点 顶点对应的系数列

5、向量线性相关。 闭回路可能的图形如教材图3-1,练习，寻找闭回路,从空格出发（非基变量）,以数字格（基变量）为顶点。总能找到唯一的闭回路。,用闭回路计算检验数,表中黑色数字为单位运价，红色数字为初始调运方案。计算检验数不要用运量，应该用运价,+,+,-,-,(1),(2),(1),(-1),(10),(12),判优：位势法,位势法原理,对应产地的方程有m个，分别对应U1到Um 对应销地的方程有n个，分别对应V1到Vn,先引入对偶变量,对偶变量取值为 CBB-1 于是有,CBB-1=(U1,U2,Um;V1,V2,Vn),可知检验数ij=Cij-CBB-1Pij =Cij-CBB-1(ei+em

6、+j) = Cij-(Ui+Vj),于是问题转化为求Ui和Vj,如何求得Ui和Vj,利用基变量检验数为零的特点 基变量Xij检验数=0，则有 Cij-(Ui+Vj)=0 这样的方程有M+N-1个，而对偶变量有M+N个。因此解不唯一。 常令U1或V1=0来求解。,位势法举例:令U1=0,0,3,10,-1,2,-5,9,12=C12-(U1+V2)=11-(0+9)=2,(2),改进：闭回路法,对负检验数单元格，沿闭回路调整。,(1),(2),(1),(10),(12),(-1),+,+,-,-,显然调整量只能为1,1,4,3,1,5,2,表上作业法的问题,无穷多最优基： 某一非基变量检验数为零

7、，可沿闭回路调整找到其他解。,表上作业法的问题,退化：保持基变量个数M+N-1不变 求初始解时，填某个数字后既划掉一行，也划掉一列。在划掉的行或列中任意空格处填零。 用闭回路调整时，得到多个零。此时应去掉一个零，保留其他的零。,下课了,若干特殊情况的处理,产销不平衡运输问题,为使产销平衡，可假设一个假的销地，需求为10-7=3。 这3个单位的物资，实际上最后还在仓库里没运走，因此运价应定为：,零。,现举例说明。,产销，例如产=10，销=7。,产销不平衡运输问题,产销，例如产=10，销=7。,添假销地B3,销量为3,单位运价为0。,B3 0 0 3,产销不平衡运输问题,类似可添加假产地，产量10

8、-7=3 这3个单位的物资并不存在，虚假物资当然不用运，因此单位运价为：零。若某销地由假产地供应，则该销地实际供应有缺口。,现举例说明。,销产，例如产=7，销=10。,添加假产地A3，产量3,单位运价0。,A3 0 0 3,现给出调运方案(红字)。,1 1 5 3,可知B2完全满足,B1短缺量3。,假产地运给谁，谁短缺。,不许发生的:单位运价定为M,由于道路施工,A2无法向B2供应物资.那么该处单位运价应定义为M亦即,只要这里有运量,运费就会无穷大。从而避免此处有运量。,某地有多种要求:适当拆分,销地有最低需求和最高需求，应适当拆分。,机动需求 0, 1 4,供给不足,需加假供应地C,供应量1

9、0。,的最低需求和的需求必须满足,不能由C供应,定价为M。,C 10,20,M 0 M,拆分实例：例2,先定不限：50+60+50-(30+70+0)=60,60,不,30,70,50,高,再拆和, 16 14 19 20, 17 15 M 50,合并和的需求,3,最后加假产地D，产量(30+20+70+30+10+50)-(50+60+50)=50 销地 必须满足，不能由D供应，定价M。,D 50,M 0 M 0 M 0,拆分练习,先定A3上限(10+4+6)-(6+7)=7,拆分A1,6a111,6,A1 2 4 3 5,a34,7,拆分A3,4,A3 3 2 4 3,最后添加虚拟销地，销

10、量(6+5+7+4+3)-(10+4+6)=5, 5,A1,A2,A3必须运走,因此不能运给假销地,单位运价应定为M。,M 0 M M 0,转运问题:示例,转运的情形,无,有,设ti为各地转运量,t1,a1+t1,t2,a2+t2,t3,b1+t3,t4,b2+t4,转运问题:平衡方程,A1 A2 B1 B2,更换表头, ,A1 A2 B1 B2, ,换入变量,1 3 4 1 5 2 3 5 6 4 2 6,X12 X13 X14 X21 X23 X24 X31 X32 X34 X41 X42 X43,添加符号,+t2,+t1,t3,t4,t1,t2,+t3,+t4,b1,b2,+ + + =

11、,+ + + =,+ + + =,+ + + =,+ + + ,+ + + ,+ + + ,+ + + ,-t3,-t1,-t2,-t4,+Q,Q,Q,+Q,Q,Q,Q,Q,+Q,+Q,Q,Q,注意供销量的结果,原产地产量ai+Q,原销地销量bj+Q,去掉产销量部分,只看决策变量,为了能用表上作业法要移ti,为使对角线元素不为负要加Q,转运问题:运价表,X21 X31 X41,X14 X24 X34,C1,X12,X32 X42,X13 X23,X43,C21 C31 C41,C32 C42,C12,C13 C23,C14 C24 C34,C43,(Q ),t1,(Q ),(Q ),(Q ),t2,t3,t4,C2,C3,C4,给出单位运价,Ci为i地单位转运费,上表为总运费,Q(Ci)是常数,可去。,去掉决策变量给出运价表,注意对角线,转运问题:最终表,转运问题实例,产地为 销地为 转运地为,内为运量 内为转运价 连线上为运价,请给出 转运表,-4,-1,-3,-3,-5,