运筹学课件第三章运输问题(浙江).ppt

2019/8/4,运筹学,1,第三章 运输问题,3.1 运输问题的表示 3.2 初始基础可行解 3.3 非基变量的检验数 3.4 基解的调整 3.5 运输问题的进一步讨论,2019/8/4,运筹学,2,本章学习要求,掌握表上作业法及其在产销平衡运输问题求解中的应用 掌握产销不平衡运输问题的求解方法,2019/8/4,运筹学,3,3.1 运输问题的表示,网络图表示 线性规划模型 运输表,2019/8/4,运筹学,4,某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：,求总运费最低的运输方案。,2019/8/4,运筹学,5,min z=2x11+3x12+5x13+4x21+7x22+8x23 s.t. x11+x12+x13 =35 供应地A1 x21+x22+x23 =25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23 =20 需求地B3 x11, x12, x13, x21, x22, x230,2019/8/4,运筹学,6,运输问题的一般提法：假设有m个生产地点，可以供应某种物资（以后称为产地），用Ai来表示，i=1,m,有n个销地，用Bj来表示，j=1,n，产地的产量和销地的销量分别为ai,bj，从产地Ai到销地Bj运输一个单位物资的运价为Cij，这些数据可汇总于下表，在假设产销平衡的条件下，即ai= bj，问该如何调运物品使总运费最小？,2019/8/4,运筹学,7,建模：设xij表示从Ai到Bj的运量，则所求的数学模型为：,min =cijxij,s.t. xij=ai i=1,m,xij=bj j=1,n,j=1,n,i=1,m,i=1,m,j=1,n,xij0 i=1,m,j=1,n,2019/8/4,运筹学,8,1.运输问题的网络图表示,产地,运价,销地,产量,销量,总产量60吨,总销量60吨,产销平衡的运输问题,2019/8/4,运筹学,9,2.运输问题线性规划模型,产地约束,销地约束,由于前m个产地约束和后n个销地约束是线性相关的，因此运输问题系数矩阵的秩m+n。可以证明，运输问题系数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量，mn-(m+n-1)个非基变量。例如以上问题m=3，n=4，基变量为3416个，非基变量为1266个。,2019/8/4,运筹学,10,3.运输问题的表格表示,2019/8/4,运筹学,11,3.2 初始基可行解,运输问题基的表示 西北角法 最小元素法 沃格尔法,2019/8/4,运筹学,12,1.运输问题基的表示,m个产地、n个销地的运输问题，任何一个基要满足以下三个条件： 基变量的个数为m+n-1； 基变量不能形成闭回路；,2019/8/4,运筹学,13,基在运输表中的表示,2019/8/4,运筹学,14,2.初始基础可行解西北角法,8,13,13,14,6,6,方法：优先满足运输表中左上角空格的供销要求填一个数字只能划去一行或一列,2019/8/4,运筹学,15,3.初始基础可行解最小元素法,12,0,15,13,0,1,13,0,2,19,3,0,1,2,0,2,0,0,方法：按单位运价的大小，决定供应的先后，优先满足单位运价最小者的供销要求（就近供应）,2019/8/4,运筹学,16,4.初始基础可行解沃格尔法,3,2,12,3,2,3,3,1,1,*,3,1,13,行罚数,列罚数,4,1,4,*,13,*,1,2,19,方法：计算出每一行及每一列中单位运价最小和次小的两个元素之间的差值，再从差值最大的行或列中找出单位运价最小者，优先满足其供销关系。,2019/8/4,运筹学,17,3.3 非基变量的检验数,闭回路法 位势法,2019/8/4,运筹学,18,1.非基变量检验数闭回路法(1),方法 求非基变量检验数ij,以该变量为定点，其他顶点为基变量找一个闭回路，从该非基变量定点为“”，“”，“”，“”依次加减其运价，即为检验数。 意义： 以该非基变量充当基变量时单位运量运费的损失。当所有的ij0，则已得运输问题的最有解。即单位物品由i-j引起总运费的变化。,2019/8/4,运筹学,19,8,13,13,14,6,6,1.非基变量检验数闭回路法(1),12 =c12-c22+c21-c11=7-4+8-6=5,5,2019/8/4,运筹学,20,8,13,13,14,6,6,1.非基变量检验数闭回路法(2),5,13 =c13-c23+c21-c11=5-2+8-6=5,5,2019/8/4,运筹学,21,8,13,13,14,6,6,1.非基变量检验数闭回路法(3),5,5,14 =(c14-c34+ c33 - c23 + c21 -c11)=3-6+10-2+8-6=7,7,2019/8/4,运筹学,22,8,13,13,14,6,6,1.非基变量检验数闭回路法(4),5,5,7,12 =c24-c34+ c33-c23=7-6+10-2=9,9,2019/8/4,运筹学,23,8,13,13,14,6,6,1.非基变量检验数闭回路法(5),5,5,7,9,32 =c32-c24+ c23-c33=9-4+2-10=-3,-3,2019/8/4,运筹学,24,8,13,13,14,6,6,1.非基变量检验数闭回路法(6),5,5,7,9,-3,31 =c31-c21+ c23-c32=5-8+2-10=-11,-11,2019/8/4,运筹学,25,2.非基变量检验数位势法,该法也称对偶变量法，我们知道一般标准运输问题的对偶问题为：,Ui,Vj无约束,由LP中ij 的定义： ij =Cij-CBB-1Pij Cij-YPij=Cij-(u1,u2,um,v1,v2,vn)Pij = cij-(ui+vj),对基变量而言： cij=(ui+vj) 由m+n-1个基变量对应m+n-1个线性方程,而LD的变量有m+n个，对偶问题有无穷多解，则可设其中一个最优解为0，而推导出其他分量。从而求出非基变量的检验数。,2019/8/4,运筹学,26,8,13,13,14,6,6,2.非基变量检验数位势法(1),ui,vj,0,6,2,2,0,10,-4,2019/8/4,运筹学,27,8,13,13,14,6,6,2.非基变量检验数位势法(2),ui,vj,0,6,2,2,0,10,-4,5,5,7,9,-13,-3,2019/8/4,运筹学,28,3.4 基解的调整闭回路法,与单纯形法一样，如果所有非基变量检验数ij 0，则该基解为最优解，否则不是最优解，需要进行基变换，换入变量的确定方法一样，设换入变量为lk ，换出变量为sf：,以xlk和基变量为顶点找一个闭回路，分别标号”+”,”-”,”+”,”_”；在标号为”-”的最小的运量为调整量，在闭回路上进行调整，“”的加，“-”的减，当存在xsf为0时，为换出变量，得一新的基可行解，再求检验数。,2019/8/4,运筹学,29,8,13,13,14,6,6,1.基变换-确定换入换出变量,5,5,7,9,-3,-11,-11,-,-,6,2019/8/4,运筹学,30,8,13,13,14,6,6,1.基变换得新的基解,-,-,6,2,12,2019/8/4,运筹学,31,13,13,14,1.基变换得新的基解,6,2,12,2019/8/4,运筹学,32,确定初始基础可行解,西北角法,沃格尔法,求非基变量的检验数,闭回路法,对偶变量法,确定进基变量,确定离基变量,得到新的基础可行解,表上作业法总结,沿闭回路调整运量,最小元素法,2019/8/4,运筹学,33,单纯形法与表上作业法比较,确定初始基变量XB,+松驰变量+（人工变量） XB系数矩阵为I，m个 其余XN,最小元素法、沃格尔法 XB数字格，m+n-1个 XN 空格,检验数,基变量j =0 非基变量j =cj-cBB-1pj,基变量ij=0 非基变量ij =cij-Ui-Vj,调整,进基：minj j 0 出基： minbi/aik，aik0,进基：minij ij0 出基： min闭回路上偶数点xij,2019/8/4,运筹学,34,3.5 运输问题的进一步讨论,一、产销不平衡的运输问题 1）产大于销，即aibj 方法：虚购一销地Bn+1，其销量bn+1= ai-bj Ai运往Bn+1物资的数量xin+1，就是产地就地贮存的物资量，因此，产地到虚销地的单位运价均为0，即cin+1 =0，这样，就转化成了一个产销平衡问题。,2019/8/4,运筹学,35,例：某建筑公司有A1、 A2、 A3三个水泥库，其水泥贮存量分别为30吨、 50吨、 60吨，四个工地B1、 B2、 B3 、 B4需要水泥的数量依次为15吨、 10吨、 40吨、 45吨，已知从各库到各工地运送每吨水泥的费用如下表，求使运费最少的调运方案？,解：计算ai=140，bj =110，aibj 所以要虚构一销地B4，其销量b5=30，而ci5 =0，这样，就转化成了一个产销平衡问题。,2019/8/4,运筹学,36,2）产小于销，即aibj 方法：虚购一产地Am+1，其产量Am+1= bj -ai Am+1运往Bj物资的数量xm+1j，就是各销地缺货的物资量，因此，虚产地到各销地的单位运价均为0，即cm+1j=0，这样，就转化成了一个产销平衡问题。 例如：,2019/8/4,运筹学,37,二、一些变形和推广 1、最大化问题 作法：1）找出单位物资效益表（cij）中的最大元素M，即M=maxcij 2)令bij =M-cij，并视为运价。 3）由bij构成单位运价表，按通常的表上作业法求解，求得最优解后还要把所得结果转换为原问题的答案。 2、销量不确定（有最高需求和最低需求） 设销地Bk的最低需求为bk，最高需求为bk ，这时可把看作Bk和Bk两个销地， Bk需求量bk ， Bk的需求量bk - bk,2019/8/4,运筹学,38,例：设某种材料有A1、 A2、 A3三个生产厂家，其产品供应B1、 B2、 B3 、 B4四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？,解释c34 =M（M是一个无穷大的正数），这意味着不允许从A3运货至B4，或者因为交通不方便等原因，使从A3到B4不可能送货。,2019/8/4,运筹学,39,B1,B1,B2,B3,B4,B4,销量,30,20,70,30,10,50,A1,A2,A3,A4,产量,50,60,50,50,16,14,19,M,16,14,19,0,13,13,20,M,22,19,23,0,17,15,M,M,17,15,M,0,2019/8/4,运筹学,40,3、指定销售问题 如规定销地1的需求量必须由产地4供应，如何处理？ 1）直接令x41=b1 2)令c41=-M，或者c11=c21=c31=M这样销地1的需求量肯定是由产地1供应了。,2019/8/4,运筹学,41,4、缺货损失问题 如下表，设销地1不允许缺货；销地2缺货，单位损失费3元；销地3缺货，单位损失费2元，问如何处理？,A4,40,M,3,2,2019/8/4,运筹学,42,三、生产与存储问题,例：某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的起重机，已知该厂各季度的生产能力及生产每台起重机的成本如表所示，若生产出来的起重机当季不交货，每台每积压一个季度工厂需支付保管及维护费0.15元，试问在按合同完成任务的情况下，工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少？,2019/8/4,运筹学,43,发货点：生产起重机的四个季度 发货量：生产能力 收货点：按合同交付起重机的四个季度 收货量：按合同提供起重机的数量 cij=第i季度每台起重机的生产成本+（j-i）个季度每台起重机的存贮费（ji）,30,10.80,10.95,11.10,11.25,M,11.10,11.25,11.40,M,M,11.00,11.15,M,M,M,11.30,0,0,0,0,2019/8/4,运筹学,44,四、有转运的运输问题,1、运输表的构成 1）产地：原产地、中间转运站、转运物资的销地 2）销地：原销地、中间转运站、转运物资的产地 3）设各转运站转运物资的数量均为 ai 这样专职转运站的产量和销量均为 ai 而原产地Ai的产量均为（ai+ ai） 原销地Bj的销量均为（ bj+ ai） 4)将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用M表示。,2019/8/4,运筹学,45,2、举例：,A、B两个化肥厂每年各生产磷肥900、600万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口C、D、E每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间均有公路相通，且已知单位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？,2019/8/4,运筹学,46,P,发量,收量,2400,2100,1500,1500,1500,1500,1500,2200,1900,1800,100,0,0,0,0,0,2019/8/4,运筹学,47,例：,该问题是一个产销平衡问题，也是求极小化问题，可用表上作业法求解。,2019/8/4,