物流运输系统规划设计

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1、物流系统规划之运输线路选择,（1）问题提出,运输问题确定了物资调运的方向、具体实施涉及运输路线选择。,运输路线的确定会直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。,当运输费用是以吨-千米来计算时，运输路线的长短就直接关系着运输费用的多少。因此运输路线的选择也是物资调运规划的一个重要内容。,在物资调运中，把某项物资从各发点调到各收点，调运方案很多，如何找出使用运输力量最小的方案？,1,（2）问题描述,某项物资从m个产地或仓库(统称为发点)，调运到n个需要地(称为收点)，在指定调运方案时，要先画一个示意的交通图，表明收发点的大致位置、收发量、交通路线长度(不必与实际长度成比例)。,在交通图上，发点用“”表示，并将发货量记在里面，收点用“口表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。然后作调运物资的流向图。物资调运的方向(流向)用表示，并把按调运方向画在交通线的右边，把调运物资的数量记在的右边，并加上括号，以表示和交通线长度区别，这样就构成下图的物资调运流量图。,2,3,3）相关概念,a) 对流,即同一物资在同一线路上的往返运输，如图1。将某物资l0吨，从A1运到B2，而又有同样的物资10吨，在同一期间从A2运到B1，于是间就出现了对流现象。,4,图1 出现对流的调运流量图,5,如果把调运流量图改成如图2所示，即将A1的l0吨运到B1,而将A2的10吨运到B2就消灭了对流，可以节省运输力量21040=800吨千米。,图2 消灭了对流的调运流量图,6,b)迂回,在交通图成圈的时候，由于表示调运方向的箭头，要按调运方向，画在交通线的右边，因此，流向图中，有些流向就在圈外，称为外圈流向。如图3；有些流向就在圈内，称为内圈流向，如图4。,如果流向图中，内圈流向的总长(简称内流长)或外圈流向的总长(简称外流长)超过整个圈长的一半，就称为迂回运输。,7,图3 迂回运输图,图4 无迂回运输图,8,如果改成图4，就消灭了迂回，可以节省运输力量（56）-（54）=l0吨千米。,9,迂回流向图示例,图5 迂回运输,内流长7大于全圈长13的一半，是迂回运输。,10,调整：,如果调整内圈长(在内圈各流量中减去内圈的最小流量10)。在外圈各流量中增加内圈的最小流量10，同时在没有流量的线段上新添上外圈流量10(即内圈的最小流量)，便得出新的流向圈，如图6。,图6 无迂回运输,11,4）运输线路选择图上作业法,物资调运问题的图上作业法，就是为了消灭运输中对流和迂回，节省运输力量。,一般步骤：,先找出一个没有对流的方案，再检查有没有迂回？如果没有迂回，这方案已是最优方案。如果有迂回，则调整这一方案，直至消灭迂回为止。,12,在物资调运中，运输路线可分为两种情况：一是交通路线不成圈，一是交通路线成圈。下面分别介绍这两种情况物资调运的方法。,a),交通路线不成圈,例3 物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7(单位：万吨)，运往B1，B2，B3，B4，收量分别为8，1，3，5(单位：万吨)，收发量是平衡的，它的交通路线如图7所示，问应如何调运，才使运输吨千米最小。,13,图7 交通路线图,14,解：,作一个没有对流的流向图。作法：由各端点开始，由外向里，逐步进行各收发点之间的收发平衡。,把A1的5万吨给A2，A2成为有发量7万吨的发点。由A3调1万吨给B2，A3剩2万吨，由A4调5万吨给B4，A4剩2万吨。将A2的7万吨全部调给B1，将A3剩余的2万吨，先调1万吨给B1，余下的1万吨调给B1，剩余的2万吨全部调给B3，调运流向图如图8。,15,图 8 调运流向图,根据上面流向图的作法，所得的没有对流现象的流向图是惟一的，再根据对流现象是不合理的运输，所以这惟一没有对流的流向图就是惟一的最优方案的流向图。,有时同一流向图，可以编制各种不同的调运方案。例中，B3需要的3万吨，除A4供给的2万吨外，其余1万吨可以由给A3，也可以由给A2，也可以由A2，A3，共同给。这些方案所用的运输力是一样的，调运时可以结合其他条件，选择其中一个。,16,b)交通路线成圈,例：有某物资7万吨，由发点A1，A2，A3 发出，发量分别为3，3，1(万吨)，运往收点B1，B2，B3，B4，收量分别为2，3，1，1(万吨)，收发量平衡，交通图如图9所示，问应如何调运，才使吨千米最小。,17,图9 交通路线图,18,解：,1)作一个没有对流的流向图，用“去线破圈”的方法：去一线破一圈，有几个圈去掉几条线，把有圈的交通图，化为不成圈的交通图。一般是先去掉长度最长的交通线，比如，去掉A1-B4(7千米)，破A1-B1-B2-A3-B4圈，再去掉线A3-B3(4千米)，破圈B2-A2-B3-A2。这样，原来有圈的交通图，变成了不成圈的交通图如图9所示。,然后先从各个端点开始，在图9上作一个没有对流的流向图。,19,图9 调运流量图破圈,20,2)检查有无迂回。方法是对流向图中的各圈进行检查，看看有无迂回。如果没有迂回，这个初始方案就是最优方案，如果其中某一圈有迂回，这个方案就不是最优方案，需要改进。,21,在图9中，圈A1-B1-B2-A3-B4的总长为23千米，外流长为5+4+3=12千米，大于圈长的一半，因而需要调整。再看圈B2-A2-B3-A3，其总长为13千米，圈中内流长为3千米，外流长为2千米，都小于圈长的一半，因此，此圈不必调整。,22,3）调整,对圈的调整方法是：在外圈的各流量中，减去外圈的最小流量1万吨；然后在内圈的各流量中加上1万吨；另外，再在无流量的线段上，新添上内圈流量1万吨，这样得出新的流量图，如图10所示。,23,图10 调整后的流量图,24,4）分析,新的流量图中，在A1-B1-B2-A3-B4圈内，内流长为：4+7=11千米，外流长为：5千米，都不超过全圈长(23千米)的一半；,在B2-A2-B3-A3圈内，内流长为3千米，外流长为4+2=6千米，也都没有超过全圈长(13千米)的一半，因此，这个流向图没有迂回现象，是本问题的最优调运方案。,5）总运输力为：17+25+14+23+21=29吨千米。,25,物流系统规划之最短路,（1） 最短路线描述,例：某家运输公司签定了一项运输合同，要把A市的一批货物运送到B市。该公司根据这两个城市之间可选择的行车路线的地图，绘制了图11的公路网络。图中，圆圈也称结点，代表起点、目的地和与行车路线相交的其他城市。箭矢或称为分支，代表两个结点之间的公路，每一条公路上都标明运输里程。,26,图11 公路网络,27,可以看出，从A市出发到达B市，可以有很多条路线可供选择。但是如何选择运输路线，才能使总路程的长度最短呢? 该公司的目的就是要找出从A市到B市的最短路线。,这就是运输规划中的最短路问题。,28,解：最短路线的计算方法为：,1)从终点开始逐步逆向推算，与终点10联接的有两个结点，即9和8，B市先从9开始计算。9到10只有一条路线，因此没有选择的余地，9-10就是最短的路线，它的里程为100，记为(9-10)100。同样8-10也只有一条路线，最短路线为8-10，里程为150，也按相同方式记为(8-10)150。,29,2)再看结点6，与6联接的只有一个结点9，因此最短路线为6-9，6至9的里程为200。而9至终点10的最短里程为100，因此6至终点的最短里程为200+100=300。记入方式同上：(6-9-10)300。,3)再看结点5，与5联接的结点有9、8两个，5至9再至终点的最短里程为400+100=500，5至8再至终点的最短里程为250+155=400。400500，所以5至终点的最短里程为400，记为(5-8-10)400。,结点7至终点的最短里程为125+150=275，记入方式同上：(7-8-10)275。,30,4)再看结点4，与4联接的结点有5、6、7三个。4至6再到终点的最短里程为200+300=500，4至5再到终点的最短里程为175+400=575，4至7再到终点的最短里程为275+275=550。三个里程中以500为最小，所以结点4至10的最短里程记为(4-6-10)500。,5）用同样的方法，算出结点2到终点的最短里程为600。结点3到终点的最短里程也为600。记入的方式同上：(2-6-9-10)600；(3-5-8-10)600,31,6)最后看结点1。与结点1联接的路线有3条：1至2再到终点的最短里程100+600=700，路径为1-2-6-9-10；1至4再到终点的最短里程150+500=650，路径为l-4-6-9-10。1至3再到终点的最短里程175+600=775，路径为1-3-5-8-10。,三个里程中以650为最小，这就是从A市到B市的最短里程，而对应的最短路线为1-4-6-9-10。,32,作业：P144,第6题,33,物流系统规划之最大流,1、问题提出,当我们要把货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。这就要在有一个起点和个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。,34,2、例题,美国北卡罗来纳州杜哈姆市周围从北到南的交通，平时是利用85号公路通行的。后来，有两个星期因为85号公路要进行路面维修，车辆不能行驶，因而北卡罗来纳州公路委员会的工程技术人员需要查明，穿过杜哈姆市区的几条路线，是不是有把握让每小时6 000辆汽车穿过，这些汽车在正常情况下，是利用85号公路南驶的。,问题：要求出从点到点的公路网络所能通过的最大流量。,35,图12标出了穿过该市从北往南的几条路线。结点旁边的数字指明以每小时千辆汽车为单位的该行车道的流量能力。,如1-2支线(行车道)上的6字表明这条行车道通往结点2的流量能力为每小时6千辆。3-5支线上的5字表示每小时可以有5千辆汽车从3向5开去。,36,图12 交通路线图,37,解：,(1)任意选择一条从起点到终点的路线，例如，我们选择路线l-2-5-6。首先找出这条路线上流量能力最小的支线，即5-6支线，其流量能力为2。这就表明，沿1-2-5-6支线南驶的汽车，其每小时的最大流量只能是2干辆，因为5-6支线限制了全线的车流量。,38,（2）其次把这条路线上每条支线的流量能力减去2，差数则表示该支线剩余的流量能力，将其写在原来的流量能力的旁边，并把原来的流量划掉。把减数2写在每条支线的终点，在减数2的右下角注上(1)，如2(1)，表示第一条路线的流量能力为2千辆。标注方式如图13所示。,39,图13 最大流量计算图,40,(3)另选一条从起点到终点的路线，如1-4-6，以该路线上最小的流量能力3为减数，来减各条支线上的流量能力，其差数、减数的记入方法同上。在差数3的右下角注上(2)，表示第二条路线的流量能力为3千辆。,41,(4)再选一条从起点到终点的路线，如1-3-4-6，以该路线上最小的流量能力3为减数来减各条支线上的流量能力，其差数、减数的记入方式同上。但4-6支线的流量能力已经只剩下4，再减去3，差数为1，接续写在4的旁边，表示4-6支线的流量能力只剩余1千辆，同时划掉4，再记入本路线的差数3(3)，表示第三条路线的流量能力为3千辆。,42,（5）结论：,已经求得了这个网络的最大流量，即第一条路线上的2千辆，第二条路线上的3千辆，第三条路线上的3千辆，共为8千辆。计算结果表明，穿过杜哈姆市区的几条路线，要让每小时6千辆汽车通过，是绰绰有余的。,43,（6）分析：,从起点到终点，已找不到这样一条路线，在这条路线上，所有各条支线的流量能力全为正数。,如1-2-3-5-6路线，其中1-2、2-3、3-5支线，都还有流量能力4千辆、7千辆、5千辆，但5-6支线已经没有剩余的流量能力，因而成为整线路的瓶颈，限制了全线的流量，使这条路线的流量能力等于0。在这个交通网络中，成为瓶颈的还有1-4、3-4支线，要想提高整个网络的流量能力，就必须改进这些薄弱环节的状况。,44,3、应用范围,最大流量算法，对规划铁路、公路运输以及城市交通流量等很有用处。,45,3、运输问题,一般运输问题就是要解决把某种产品从若干个产地调运到若干个销售地，在每个产地的供应量与每个销售量的需求量已知，并知道各个地点之间运输单价的前提下，如何确定一个使得总的运输费用最小的方案问题。,一类特殊的多元线性规划问题,各个地点之间运输单价的影响因素？,46,47,引例：,某公司从两个产地A,1,、A,2,将物品运往三个销地B,1,、B,2,、B,3,，各产地的产量、各销地的销量和各产地运往各销地每d单位物品的运费如下表所示，问：应如何调运可使总运输费用最小？,47,看图表可知道：,总产量=销售量,产销平衡问题，把A1，A2的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。,48,解：,产销平衡问题： 总产量 = 总销量,设,x,ij,为从产地A,i,运往销地B,j,的运输量，得到下列运输量表：,49,从表可以写出此数学模型：,满足产地产量的约束条件：,满足销地销量的约束条件：,x,11,+,x,12,+,x,13,= 200,x,21,+,x,22,+,x,23,= 300,x,11,+,x,21,= 150,x,12,+,x,22,= 150,x,13,+,x,23,= 200,50,使运输费用最小，即：,所以此运输问题的线性规划模型如下：,Min f = 6,x,11,+ 4,x,12,+ 6,x,13,+ 6,x,21,+ 5,x,22,+ 5,x,23,Min f = 6,x,11,+ 4,x,12,+ 6,x,13,+ 6,x,21,+ 5,x,22,+ 5,x,23,s.t.,x,11,+,x,12,+,x,13,= 200,x,21,+,x,22,+,x,23,= 300,x,11,+,x,21,= 150,x,12,+,x,22,= 150,x,13,+,x,23,= 200,x,ij, 0 ( i = 1、2；j = 1、2、3）,51,产销地之间的供需联系的确定是以运输费用最低为前提的，因此，在这种情况下，物资调运问题的数学模型，物资调运规划（又称运输问题可表述为：,（1）一般物流调运规划模型,52,53,54,一般运输模型：,产销平衡,A,1,、 A,2,、 A,m,表示某物资的m个产地； B,1,、B,2,、B,n,表示某物质的n个销地；s,i,表示产地A,i,的产量；,d,j,表示销地B,j,的销量；,c,ij,表示把物资从产地A,i,运往销地B,j,的单位运价。,设,x,ij,为从产地A,i,运往销地B,j,的运输量，得到下列一般运输量问题的模型：,m n,Min f =, ,c,ij,x,ij,i = 1 j = 1,n,s.t.,x,ij,=,s,i,i = 1,2,m,j = 1,m,x,ij,=,d,j,j = 1,2,n,i = 1,x,ij, 0 (i = 1,2,m ; j = 1,2,n),54,（2）产销平衡运输问题求解,表上作业法：,1首先依据问题列出调运物资的供应需求平衡表以及运价表；其次确定一个初始的调运方案（当然不一定是最优方案）；,2然后根据一个判定法则，判定初始方案是否是最优方案。,3当判定初始方案不是最优方案时，再对这个方案进行调整。,4每调整一次得到的新的方案，运输费用比前一个方案要少些。,55,实例：某公司下属三个存储,某种,物资的料库，供应四个工地的需要。三个料库的供应量和四个工地的需求量以及由各料库到各工地调运单位物资的运价（元/吨）由下表给出：,56,工地,运价（元/吨）,料库,B,1,B,2,B,3,B,4,供应量（t）,A,1,3,11,3,10,700,A,2,1,9,2,8,400,A,3,7,4,10,5,900,需求量（t）,300,600,500,600,2000,某公司物资供应状况表,试求运输费用最少的合理调运方案。,57,解：,（1）列出调运物资平衡表和运价表,首先列出被调运物资的供需平衡表和运价表，平衡表和运价表是表上作业法的基本资料和,运算的依据。表上作业法就是利用运价表在平衡表上进行求解。,58,供需平衡表,需,供,B,1,B,2,B,3,B,4,供应量（t）,A,1,700,A,2,400,A,3,900,需求量（t）,300,600,500,600,2000,59,运价表,工地,运价（元/吨）,料库,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,60,（2）标记,为了叙述和考虑问题方便，通常把上面的平衡表看作为矩阵，并把表中的方格记为（i, j）的形式。如（2，3）表示第三行第四列的方格；（1，4）代表第一行第四列的方格；此外，如果在平衡表的（2，1）方格中填入300，即表示由A2仓库调运300单位物资供应给B1工地，此时简记为（2，1）=300，而空格表示供销双方不发生调运关系。,61,（3）编制初始调运方案,物资调运规划其总的目的是寻求一个运费用最小的最优运输方案。一般最优方案是由初始方案经过反复调整得到的。最好的方案就是运输费用最少的方案。,最小元素法：考虑运价因素来制定初始调运方案的方法，即按运价表依次挑选运费小的供-需点尽量优先安排供应的调运方法。,62,具体作法,：,1在运价表中找出最小的数值（当此数不唯一时，可任意选择一个），方格（2，1）数值是1，最小，参考A,2,尽可能满足B,1,工地的需要，于是在平衡表中有（2，1）=300，即在空格（2，1）中填入数字300。此时，由于工地B,1,已经全部得到满足，不再需要 A,1,、A,3,仓库供应。供应表中第一列数字已不起作用，因此将原运价表的第一列划去，并标注。,63,2在运价表未划去的各行、列中，再选取一个最小的数值，即（2，3）=2，让A2料库尽量供应满足B3工地的需要。由于A2库中储量400吨已经供应给B1工地300吨了，所以最多只能供给B3工地100吨。于是在平衡表（2，3）空格填入100。相应的由于仓库A2所储物资已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注。,64,3依照上述方法进行。,4最后，在运价表中只有方格（1，4）处的运价没有划掉，而B4尚有300t的需求，为了满足供需平衡，在最后的平衡表中应填入300。,这样就得到最初调运方案。,65,工地,运价（元/吨）,料库,B,1,B,2,B,3,B,4,供应量（t）,A,1,3,11,3，400,10,700,A,2,1，300,9,2，100,8,400,A,3,7,4，600,10,5，300,900,需求量（t）,300,600,500,600,2000,表5 某公司物资供应状况表,66,初始方案,需,供,B,1,B,2,B,3,B,4,供应量（t）,A,1,400,300,700,A,2,300,100,400,A,3,600,300,900,需求量（t）,300,600,500,600,2000,67,计算初始调运方案运输费：,S=1*300+4*600+3*400+2*200+10*300+5*300,=8600（元）,68,（4）编制初始方案说明,1应用最小元素法编制的初始调运方案，就整体考虑而言，运输费用不一定是最小的。,2在初始方案中，填入数字的方格总数应该是应该是供应点个数m加上需求点个数n再减1，即（m+n-1).,3如不满足上述条件，,需要在未填有数字且未划去的方格中填上一个0,，将它和其他发生供需关系的方格同样对待，而不能看作空格，以满足（m+n-1)的要求。,69,（5）,初始方案的调整,在制定初始方案之后，需要对它进行检验，如果判定初始调运输方案不是最优方案，需要对其进行调整直到获得最优调运方案。,1）闭回路,闭回路是以空格为起点，沿同一行或同一列前进，遇上圈格可转90度继续前进，按此方法进行下去，直到回到始点的一个封闭折线。,以始点为第0个点，依次给闭回路上的每一个顶点编号。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。,70,每个闭回路具有下列性质：,闭回路是一条封闭折线，每一条边都是水平或垂直的；,每一行（列）若有闭合回路的顶点，则有两个；,只有从空格出发，,其余各转角点所对应的方格内均填有数字时,，所构成的闭合回路才是我们所说的闭回路；,任何过一空格的闭合回路不仅是存在的，而且是惟一的。,71,闭回路如图（,a,）、（,b,）、（,c,）等所示。,从每一个空格出发一定存在并且可以找到唯一的闭回路。,闭回路示意图,72,表7给定的初始调运方案为例，说明闭回路的性质。表7中给出了空格(1，1)和(3，1)所形成的闭回路：,(1，1) (1，3) (2，3) (2，1) (1，1),73,需,供,B,1,B,2,B,3,B,4,供应量（t）,A,1,400,300,700,A,2,300,100,400,A,3,600,300,900,需求量（t）,300,600,500,600,2000,表7 闭回路示意图,74,2） 检验数,a) 在调运方案内的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运输费用是增加还是减少。,b) 把所计算出来的每个闭回路上调整单位运量而使运费发生变化的增减值，称为检验数。,c) 如果检验数小于零，表示在该空格的闭回路上调整运输量使运费减少；相反，如果检验数大与零，则会是使运费增加。,d) 对于求运费最小的物资调运问题来说，如果所有空格的检验数都小于零，那么如果再对调运方案进行任何调整，都会增加运输费用。,75,3）调运方案是否是最优的判定准则是：,初始调运方案，如果它所有的检验数都是非负的，那么这个初始调运方案一定是最优。否则，这一调运方案不一定是最优的，需要调整。,76,4) 求检验数方法位势法,77,78,用该调运问题的相应运价减去表5-14中的数值，那么对初始方案中每个填有运量数值的方格来说，都会满足,而对于每个空格来说，相应得到的数值就是该空格的检验数，即,79,运价表,工地,运价（元/吨）,料库,B,1,B,2,B,3,B,4,A,1,3,11,3,10,A,2,1,9,2,8,A,3,7,4,10,5,80,81,用位势法求检验数的公式计算初始调运方案的检验数，计算结果列表构成该初始调运方案的检验数表：,需,供,B1,B2,B3,B4,A1,1,2,A2,1,-1,A3,10,12,由于检验数出现负值，依照最优方案判定准则，可知该初始调运方案不一定是最优的需要进行调整。,82,5）调运方案的调整,当判定一个初始调运方案不是最优调运方案时，就要在检验数出现负值的该空格内进行调整。,如果检验数是负值的空格不只一个时，一般选择负检验数绝对值大的空格作为具体的调整对象。,由初始调运方案的检验数表发现，空格的X24检验数是负数因此对其进行调整.,83,需,供,B,1,B,2,B,3,B,4,供应量（t）,A,1,400,300,700,A,2,300,100,400,A,3,600,300,900,需求量（t）,300,600,500,600,2000,0,1,2,3,84,85,需,供,B,1,B,2,B,3,B,4,供应量（t）,A,1,500,200,700,A,2,300,100,400,A,3,600,300,900,需求量（t）,300,600,500,600,2000,86,(6)新调运方案运输费,新方案是否是最优方案，还需要对它再进行检验。经计算，该新方案的所有检验数都是非负的，说明这个方案已经是最优调运方案了。,按新方案计算调运物资的运输费用为：8500,87,(7)表上作业法基本步骤小结,综上所述，采用表上作业法求解平衡运输问题的物资调运最优方案，其计算步骤可以归纳如下：,列出调运物资的供需(产销)平衡表及运价表；,按最小元素法建立初始调运方案；,采用位势法计算初始方案每个空格的闭回路的检验数,检查检验数，如所有检验数大于等于0，说明方案是最优的，已经得到我们想要的方案，结束求解；,如果有某个或某几个为负数，则选择负检验数中绝对值最大的闭回路进行调整，建立新的方案；,重复35步，直至获得最优调运方案。,88,运输问题及其模型,某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：A,1,7吨，A,2,4吨，A,3,9吨；各销售部的日销量分别为：B,1,3吨，B,2,6吨，B,3,5吨，B,4,6吨。各厂到各销售部的单位产品的运价如右表。问该公司应如何调运产品，才能完成运输任务而使运费最省。,89,用线性规划法处理此问题。设由产地i到销地j的运量为x,ij,，模型为：,min z= 3x,11,+11x,12,+3x,13,+10x,14,+x,21,+9x,22,+2x,23,+8x,24,+7x,31,+4x,32,+10x,33,+5x,34,x,11,+x,12,+x,13,+x,14,=7,x,21,+x,22,+x,23,+x,24,=4,x,31,+x,32,+x,33,+x,34,=9,x,11,+x,21,+x,31,=3,x,12,+x,22,+x,32,=6,x,13,+x,23,+x,33,=5,x,14,+x,24,+x,34,=6,x,ij,0 (i=1,2,3; j=1,2,3,4),运输问题一般用表上作业法求解，需建立表格模型：,单位运价表,产销平衡表,销地,产地,B,1,B,2,B,3,B,4,A,1,A,2,A,3,3,1,7,11,9,4,3,3,10,10,8,5,90,表上作业法,表上作业法的步骤:,(1)给出初始调运方案。,(2)检验方案是否最优,若是最优解,则停止计算;否则转下一步。,(3)调整调运方案，得新的方案。,(4)重复(2),(3)直到求出最优方案。,91,2.2.1 给出初始调运方案最常用的方法,最小元素法,表上作业法要求，调运方案的数字格必须为m+n-1个,3,1,4,6,3,3,92,位势表,1,0,2,1,9,-4,8,（2）,（9）,（8）,（9）,（-3）,（-2）,检验数表,若所有检验数非负则是最优解,最优性检验的方法,位势法,93,（1）从一个检验数为负数且最小的空格出发，和其它数字格构成闭回路。可证，此闭回路存在且唯一。,（2）在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。,（3）运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。,方案调整的方法,闭回路法,94,位势表,1,0,1,2,8,-3,7,（3）,（9）,（7）,（1）,（-2）,（-2）,检验数表,表上作业法 (续),检验数都非负，得最优解。,95,作业 运输问题及其解法,某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A,1,-40吨，A,2,-40吨，A,3,-90吨。该公司把这些产品分别运往四个销售点，各销售点每日销量为：B,1,-30吨，B,2,-40吨，B,3,-60吨，B,4,-20吨, B,5,-20吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少,销地,产地,B1,B2,B3,B4,B5,产量（万吨）,A1,7,10,8,6,4,40,A2,5,9,7,12,6,40,A3,3,6,5,8,11,90,销量（万吨）,30,40,60,20,20,96,课堂练习：,97,例1、,某公司从两个产地A,1,、A,2,将物品运往三个销地B,1,、B,2,、B,3,，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,97,要求：,（1）运用最小元素法求出初始调运方案。,（2）计算初始调运方案的运输费用。,（3）请问还有其他使得运输费用更小的调运方案没有？,98,作业2,某公司有三个工厂B,1,、B,2,、B,3,，生产中需要同一种原料，另有三个仓库A,1,、A,2,、A,3,可供应这种原料，由于供需双方两两间的相对位置不同因而运价不同，有关数据如下表：,B,1,B,2,B,3,产量,A,1,4 8 8 56,A,2,16 24 16 82,A,3,8 16 24 77,销 量 72 102 41 215,问应如何安排运输才能使总运费为最小？,99,要求：,（1）写出本运输问题的线性规划模型。,（2）运用最小元素法求出初始调运方案。,（3）计算初始调运方案的运输费用。,（4）请问还有其他使得运输费用更小的调运方案没有？,100,练习3：运输问题及其模型,某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：A,1,7吨，A,2,4吨，A,3,9吨；各销售部的日销量分别为：B,1,3吨，B,2,6吨，B,3,5吨，B,4,6吨。各厂到各销售部的单位产品的运价如右表。问该公司应如何调运产品，才能完成运输任务而使运费最省。,101,要求：,（1）写出本运输问题的线性规划模型。,（2）运用最小元素法求出初始调运方案。,（3）计算初始调运方案的运输费用。,（4）请问还有其他使得运输费用更小的调运方案没有？,102,三、产销不平衡的运输问题,（1）问题提出,1、产销不平衡问题更加普遍,在应用表上作业法制订物资调运方案时，要求有产销(供需)平衡的条件。可是在实际中常常会碰到产销不平衡的情况。譬如，常常发生供过于求的情况，有时也会发生供不应求的现象。碰到这种情况，我们不仅要对产销供需的规划问题进行考虑，同时还必须找出哪些供应点的库存过多，多多少；哪些需求地的供应不足，缺口又是多少。,这样的问题，不能直接应用表上作业法，但经过适当的处理后，还是可以化成供需平衡问题来应用表上作业法，使之获得圆满解决。,2、表上作业法的推广,103,1）产大于销，即,此时增加一个假想的销地n+1，该销地的销量为 ，而各产地到假想销地的单位运价定为0，就转化成产销平衡的运输问题。,实际上，这就相当于在某个供应点的仓库里，将多余部分的供应量储存起来。,表上作业法是以产销平衡为前提的，即当实际问题产销不平衡时，需要转化为产销平衡的运输问题，具体来说有两种情况：,104,由于虚设的需求并没有参加实际的调配运输，因此可视它的相应运价为零。实际上不会对整个物资调运问题最小运输费用值的结果产生影响。,由于引入了一个需求点，其需求量刚好等于多余的供应量，从而使不平衡的调运问题转化为供销平衡的运输问题，可以应用前面介绍的表上作业法求出它的物资调运最优方案。,105,2）销大于产，即,此时增加一个假想的产地m+1，该产地的产量为 ，而假想产地到各销地的单位运价定为0，就转化成产销平衡的运输问题。,相当于在某个需求点内设立一个仓库，假设需求不足部分的物资已经通过另找出路供应，预先储备起来了。因此，这一部分需求量对该调运问题来说，也不存在运输问题，所以同样可设它的相应运价为零，从而也不会影响到最小运输费用的值。,106,107,例1、,某公司从两个产地A,1,、A,2,将物品运往三个销地B,1,、B,2,、B,3,，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,解,：增加一个,虚设的销地,运输费用为0,（2）,产销不平衡,运输模型,107,108,例2、,某公司从两个产地A,1,、A,2,将物品运往三个销地B,1,、B,2,、B,3,，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,解,：增加一个,虚设的产地,运输费用为0,108,例3 计算实例,某建筑公司有三个储砂仓，供应四个拌合场的混凝土搅拌机所需用砂。各拌合场估计需砂量和储砂仓的供应能力以及由第 砂仓运往第 拌合场的单位运价为 (元吨),该公司要求找出一个运费最小的供砂调运方案。这是一个供销不平衡的调运问题。,109,供砂状况表,拌和场,砂仓,B1,B2,B3,B4,供应量,A1,0.12,0.10,0.08,0.11,5000,A2,0.09,0.11,0.11,0.13,10000,A3,0.10,0.14,0.13,0.03,12000,需求量,5000,4000,7000,8000,1）总供应量27000t，大于总需求量2400t。,产销不平衡，供过于求。,我们虚拟一个需求量为27000-24000=3000t的需求点，构成新的供需平衡表。,110,拌和场,砂仓,B1,B2,B3,B4,D0,供应量,A1,0.12,0.10,0.08,0.11,0,5000,A2,0.09,0.11,0.11,0.13,0,10000,A3,0.10,0.14,0.13,0.03,0,12000,需求量,5000,4000,7000,8000,3000,虚拟供砂平衡表,111,2）运用表上作业法进行求解，如表所示,拌和场,砂仓,B1,B2,B3,B4,D0,供应量,A1,5000,5000,A2,4000,4000,2000,10000,A3,1000,8000,3000,12000,需求量,5000,4000,7000,8000,3000,最优调运方案,112,113,4）最优调运方案（省略检验数计算）,114,