物流运输系统规划设计ppt课件.ppt

管管 理理 运运 筹筹 学学1 1、物流系统规划之运输线路选择（1）问题提出 运输问题确定了物资调运的方向、具体实施涉及运输路线选择。 运输路线的确定会直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。 当运输费用是以吨-千米来计算时，运输路线的长短就直接关系着运输费用的多少。因此运输路线的选择也是物资调运规划的一个重要内容。 在物资调运中，把某项物资从各发点调到各收点，调运方案很多，如何找出使用运输力量最小的方案？ 管管 理理 运运 筹筹 学学2（2）问题描述 某项物资从m个产地或仓库(统称为发点)，调运到n个需要地(称为收点)，在指定调运方案时，要先画一个示意的交通图，表明收发点的大致位置、收发量、交通路线长度(不必与实际长度成比例)。 在交通图上，发点用“”表示，并将发货量记在里面，收点用“口表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。然后作调运物资的流向图。物资调运的方向(流向)用表示，并把按调运方向画在交通线的右边，把调运物资的数量记在的右边，并加上括号，以表示和交通线长度区别，这样就构成下图的物资调运流量图。管管 理理 运运 筹筹 学学3管管 理理 运运 筹筹 学学4 3）相关概念 a) 对流 即同一物资在同一线路上的往返运输，如图1。将某物资l0吨，从A1运到B2，而又有同样的物资10吨，在同一期间从A2运到B1，于是间就出现了对流现象。 管管 理理 运运 筹筹 学学5 图1 出现对流的调运流量图 管管 理理 运运 筹筹 学学6 如果把调运流量图改成如图2所示，即将A1的l0吨运到B1,而将A2的10吨运到B2就消灭了对流，可以节省运输力量21040=800吨千米。 图2 消灭了对流的调运流量图管管 理理 运运 筹筹 学学7 b)迂回 在交通图成圈的时候，由于表示调运方向的箭头，要按调运方向，画在交通线的右边，因此，流向图中，有些流向就在圈外，称为外圈流向。如图3；有些流向就在圈内，称为内圈流向，如图4。 如果流向图中，内圈流向的总长(简称内流长)或外圈流向的总长(简称外流长)超过整个圈长的一半，就称为迂回运输。 管管 理理 运运 筹筹 学学8 图3 迂回运输图图4 无迂回运输图管管 理理 运运 筹筹 学学9 如果改成图4，就消灭了迂回，可以节省运输力量（56）-（54）=l0吨千米。管管 理理 运运 筹筹 学学10迂回流向图示例图5 迂回运输 内流长7大于全圈长13的一半，是迂回运输。 管管 理理 运运 筹筹 学学11 调整： 如果调整内圈长(在内圈各流量中减去内圈的最小流量10)。在外圈各流量中增加内圈的最小流量10，同时在没有流量的线段上新添上外圈流量10(即内圈的最小流量)，便得出新的流向圈，如图6。 图6 无迂回运输 管管 理理 运运 筹筹 学学12 4）运输线路选择图上作业法 物资调运问题的图上作业法，就是为了消灭运输中对流和迂回，节省运输力量。 一般步骤： 先找出一个没有对流的方案，再检查有没有迂回？如果没有迂回，这方案已是最优方案。如果有迂回，则调整这一方案，直至消灭迂回为止。管管 理理 运运 筹筹 学学13 在物资调运中，运输路线可分为两种情况：一是交通路线不成圈，一是交通路线成圈。下面分别介绍这两种情况物资调运的方法。 a) 交通路线不成圈 例3 物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7(单位：万吨)，运往B1，B2，B3，B4，收量分别为8，1，3，5(单位：万吨)，收发量是平衡的，它的交通路线如图7所示，问应如何调运，才使运输吨千米最小。管管 理理 运运 筹筹 学学14图7 交通路线图 管管 理理 运运 筹筹 学学15 解： 作一个没有对流的流向图。作法：由各端点开始，由外向里，逐步进行各收发点之间的收发平衡。 把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。管管 理理 运运 筹筹 学学16图 8 调运流向图 根据上面流向图的作法，所得的没有对流现象的流向图是惟一的，再根据对流现象是不合理的运输，所以这惟一没有对流的流向图就是惟一的最优方案的流向图。 有时同一流向图，可以编制各种不同的调运方案。例中，B3需要的3万吨，除A4供给的2万吨外，其余1万吨可以由给A3，也可以由给A2，也可以由A2，A3，共同给。这些方案所用的运输力是一样的，调运时可以结合其他条件，选择其中一个。 管管 理理 运运 筹筹 学学17 b)交通路线成圈 例：有某物资7万吨，由发点A1，A2，A3 发出，发量分别为3，3，1(万吨)，运往收点B1，B2，B3，B4，收量分别为2，3，1，1(万吨)，收发量平衡，交通图如图9所示，问应如何调运，才使吨千米最小。管管 理理 运运 筹筹 学学18图9 交通路线图管管 理理 运运 筹筹 学学19解： 1)作一个没有对流的流向图，用“去线破圈”的方法：去一线破一圈，有几个圈去掉几条线，把有圈的交通图，化为不成圈的交通图。一般是先去掉长度最长的交通线，比如，去掉A1-B4(7千米)，破A1-B1-B2-A3-B4圈，再去掉线A3-B3(4千米)，破圈B2-A2-B3-A2。这样，原来有圈的交通图，变成了不成圈的交通图如图9所示。 然后先从各个端点开始，在图9上作一个没有对流的流向图。 管管 理理 运运 筹筹 学学20图9 调运流量图破圈管管 理理 运运 筹筹 学学21 2)检查有无迂回。方法是对流向图中的各圈进行检查，看看有无迂回。如果没有迂回，这个初始方案就是最优方案，如果其中某一圈有迂回，这个方案就不是最优方案，需要改进。管管 理理 运运 筹筹 学学22 在图9中，圈A1-B1-B2-A3-B4的总长为23千米，外流长为5+4+3=12千米，大于圈长的一半，因而需要调整。再看圈B2-A2-B3-A3，其总长为13千米，圈中内流长为3千米，外流长为2千米，都小于圈长的一半，因此，此圈不必调整。管管 理理 运运 筹筹 学学23 3）调整 对圈的调整方法是：在外圈的各流量中，减去外圈的最小流量1万吨；然后在内圈的各流量中加上1万吨；另外，再在无流量的线段上，新添上内圈流量1万吨，这样得出新的流量图，如图10所示。管管 理理 运运 筹筹 学学24 图10 调整后的流量图管管 理理 运运 筹筹 学学25 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吨千米。管管 理理 运运 筹筹 学学26 物流系统规划之最短路 （1） 最短路线描述 例：某家运输公司签定了一项运输合同，要把A市的一批货物运送到B市。该公司根据这两个城市之间可选择的行车路线的地图，绘制了图11的公路网络。图中，圆圈也称结点，代表起点、目的地和与行车路线相交的其他城市。箭矢或称为分支，代表两个结点之间的公路，每一条公路上都标明运输里程。 管管 理理 运运 筹筹 学学27 图11 公路网络管管 理理 运运 筹筹 学学28 可以看出，从A市出发到达B市，可以有很多条路线可供选择。但是如何选择运输路线，才能使总路程的长度最短呢? 该公司的目的就是要找出从A市到B市的最短路线。 这就是运输规划中的最短路问题。管管 理理 运运 筹筹 学学29 解：最短路线的计算方法为： 1)从终点开始逐步逆向推算，与终点10联接的有两个结点，即9和8，B市先从9开始计算。9到10只有一条路线，因此没有选择的余地，9-10就是最短的路线，它的里程为100，记为(9-10)100。同样8-10也只有一条路线，最短路线为8-10，里程为150，也按相同方式记为(8-10)150。管管 理理 运运 筹筹 学学30 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。 管管 理理 运运 筹筹 学学31 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 管管 理理 运运 筹筹 学学32 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。管管 理理 运运 筹筹 学学33 作业：P144,第6题管管 理理 运运 筹筹 学学34物流系统规划之最大流 1、问题提出 当我们要把货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。这就要在有一个起点和个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。 管管 理理 运运 筹筹 学学35 2、例题 美国北卡罗来纳州杜哈姆市周围从北到南的交通，平时是利用85号公路通行的。后来，有两个星期因为85号公路要进行路面维修，车辆不能行驶，因而北卡罗来纳州公路委员会的工程技术人员需要查明，穿过杜哈姆市区的几条路线，是不是有把握让每小时6 000辆汽车穿过，这些汽车在正常情况下，是利用85号公路南驶的。 问题：要求出从点到点的公路网络所能通过的最大流量。管管 理理 运运 筹筹 学学36 图12标出了穿过该市从北往南的几条路线。结点旁边的数字指明以每小时千辆汽车为单位的该行车道的流量能力。 如1-2支线(行车道)上的6字表明这条行车道通往结点2的流量能力为每小时6千辆。3-5支线上的5字表示每小时可以有5千辆汽车从3向5开去。管管 理理 运运 筹筹 学学37 图12 交通路线图管管 理理 运运 筹筹 学学38 解： (1)任意选择一条从起点到终点的路线，例如，我们选择路线l-2-5-6。首先找出这条路线上流量能力最小的支线，即5-6支线，其流量能力为2。这就表明，沿1-2-5-6支线南驶的汽车，其每小时的最大流量只能是2干辆，因为5-6支线限制了全线的车流量。管管 理理 运运 筹筹 学学39 （2）其次把这条路线上每条支线的流量能力减去2，差数则表示该支线剩余的流量能力，将其写在原来的流量能力的旁边，并把原来的流量划掉。把减数2写在每条支线的终点，在减数2的右下角注上(1)，如2(1)，表示第一条路线的流量能力为2千辆。标注方式如图13所示。管管 理理 运运 筹筹 学学40 图13 最大流量计算图管管 理理 运运 筹筹 学学41 (3)另选一条从起点到终点的路线，如1-4-6，以该路线上最小的流量能力3为减数，来减各条支线上的流量能力，其差数、减数的记入方法同上。在差数3的右下角注上(2)，表示第二条路线的流量能力为3千辆。管管 理理 运运 筹筹 学学42 (4)再选一条从起点到终点的路线，如1-3-4-6，以该路线上最小的流量能力3为减数来减各条支线上的流量能力，其差数、减数的记入方式同上。但4-6支线的流量能力已经只剩下4，再减去3，差数为1，接续写在4的旁边，表示4-6支线的流量能力只剩余1千辆，同时划掉4，再记入本路线的差数3(3)，表示第三条路线的流量能力为3千辆。 管管 理理 运运 筹筹 学学43（5）结论： 已经求得了这个网络的最大流量，即第一条路线上的2千辆，第二条路线上的3千辆，第三条路线上的3千辆，共为8千辆。计算结果表明，穿过杜哈姆市区的几条路线，要让每小时6千辆汽车通过，是绰绰有余的。管管 理理 运运 筹筹 学学44（6）分析： 从起点到终点，已找不到这样一条路线，在这条路线上，所有各条支线的流量能力全为正数。 如1-2-3-5-6路线，其中1-2、2-3、3-5支线，都还有流量能力4千辆、7千辆、5千辆，但5-6支线已经没有剩余的流量能力，因而成为整线路的瓶颈，限制了全线的流量，使这条路线的流量能力等于0。在这个交通网络中，成为瓶颈的还有1-4、3-4支线，要想提高整个网络的流量能力，就必须改进这些薄弱环节的状况。管管 理理 运运 筹筹 学学453、应用范围 最大流量算法，对规划铁路、公路运输以及城市交通流量等很有用处。 管管 理理 运运 筹筹 学学463、运输问题 一般运输问题就是要解决把某种产品从若干个产地调运到若干个销售地，在每个产地的供应量与每个销售量的需求量已知，并知道各个地点之间运输单价的前提下，如何确定一个使得总的运输费用最小的方案问题。 一类特殊的多元线性规划问题 各个地点之间运输单价的影响因素？管管 理理 运运 筹筹 学学4747 引例：引例：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每d单位物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产 量A1646200A2655300销 量150150200管管 理理 运运 筹筹 学学48 看图表可知道： 总产量=销售量 产销平衡问题，把A1，A2的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。管管 理理 运运 筹筹 学学49 解：解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： B1B2B3产 量A1x11x12x13200A2x21x22x23300销 量150150200管管 理理 运运 筹筹 学学50从表可以写出此数学模型：满足产地产量的约束条件：满足销地销量的约束条件： x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200管管 理理 运运 筹筹 学学51使运输费用最小，即：所以此运输问题的线性规划模型如下： Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）管管 理理 运运 筹筹 学学52 产销地之间的供需联系的确定是以运输费用最低为前提的，因此，在这种情况下，物资调运问题的数学模型，物资调运规划（又称运输问题可表述为：（1）一般物流调运规划模型）一般物流调运规划模型管管 理理 运运 筹筹 学学53管管 理理 运运 筹筹 学学5454一般运输模型：一般运输模型：产销平衡 A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型： m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 管管 理理 运运 筹筹 学学55（2）产销平衡运输问题求解 表上作业法：1首先依据问题列出调运物资的供应需求平衡表以及运价表；其次确定一个初始的调运方案（当然不一定是最优方案）；2然后根据一个判定法则，判定初始方案是否是最优方案。3当判定初始方案不是最优方案时，再对这个方案进行调整。4每调整一次得到的新的方案，运输费用比前一个方案要少些。管管 理理 运运 筹筹 学学56 实例：某公司下属三个存储某种物资的料库，供应四个工地的需要。三个料库的供应量和四个工地的需求量以及由各料库到各工地调运单位物资的运价（元/吨）由下表给出：管管 理理 运运 筹筹 学学57 工地运价（元/吨）料库B1B2B3B4供应量供应量（t）A1311310700A21928400A374105900需求量（需求量（t）3006005006002000某公司物资供应状况表试求运输费用最少的合理调运方案。管管 理理 运运 筹筹 学学58解： （1）列出调运物资平衡表和运价表 首先列出被调运物资的供需平衡表和运价表，平衡表和运价表是表上作业法的基本资料和运算的依据。表上作业法就是利用运价表在平衡表上进行求解。管管 理理 运运 筹筹 学学59供需平衡表供需平衡表 需供B1B2B3B4供应量供应量（t）A1700A2400A3900需求量（需求量（t） 3006005006002000管管 理理 运运 筹筹 学学60运价表运价表工地运价（元/吨）料库B1B2B3B4A1311310A21928A374105管管 理理 运运 筹筹 学学61 （2）标记 为了叙述和考虑问题方便，通常把上面的平衡表看作为矩阵，并把表中的方格记为（i, j）的形式。如（2，3）表示第三行第四列的方格；（1，4）代表第一行第四列的方格；此外，如果在平衡表的（2，1）方格中填入300，即表示由A2仓库调运300单位物资供应给B1工地，此时简记为（2，1）=300，而空格表示供销双方不发生调运关系。管管 理理 运运 筹筹 学学62（3）编制初始调运方案）编制初始调运方案物资调运规划其总的目的是寻求一个运费用最小的最优运输方案。一般最优方案是由初始方案经过反复调整得到的。最好的方案就是运输费用最少的方案。最小元素法：考虑运价因素来制定初始调运方案的方法，即按运价表依次挑选运费小的供-需点尽量优先安排供应的调运方法。管管 理理 运运 筹筹 学学63具体作法具体作法： 1在运价表中找出最小的数值（当此数不唯一时，可任意选择一个），方格（2，1）数值是1，最小，参考A2尽可能满足B1 工地的需要，于是在平衡表中有（2，1）=300，即在空格（2，1）中填入数字300。此时，由于工地B1已经全部得到满足，不再需要 A1、A3仓库供应。供应表中第一列数字已不起作用，因此将原运价表的第一列划去，并标注。管管 理理 运运 筹筹 学学64 2在运价表未划去的各行、列中，再选取一个最小的数值，即（2，3）=2，让A2料库尽量供应满足B3工地的需要。由于A2库中储量400吨已经供应给B1工地300吨了，所以最多只能供给B3工地100吨。于是在平衡表（2，3）空格填入100。相应的由于仓库A2所储物资已全部供应完毕，因此，在运价表中与A2同行的运价也不再起作用，所以也将它们划去，并标注。管管 理理 运运 筹筹 学学653依照上述方法进行。4最后，在运价表中只有方格（1，4）处的运价没有划掉，而B4尚有300t的需求，为了满足供需平衡，在最后的平衡表中应填入300。 这样就得到最初调运方案。管管 理理 运运 筹筹 学学66 工地运价（元/吨）料库B1B2B3B4供应量供应量（t）A13113，40010700A21，30092，1008400A374，600105，300900需求量（需求量（t）3006005006002000表5 某公司物资供应状况表管管 理理 运运 筹筹 学学67初始方案初始方案 需供B1B2B3B4供应量供应量（t）A1400300700A2300100400A3600300900需求量（需求量（t） 3006005006002000管管 理理 运运 筹筹 学学68计算初始调运方案运输费：S=1*300+4*600+3*400+2*200+10*300+5*300=8600（元）管管 理理 运运 筹筹 学学69（4）编制初始方案说明 1应用最小元素法编制的初始调运方案，就整体考虑而言，运输费用不一定是最小的。 2在初始方案中，填入数字的方格总数应该是应该是供应点个数m加上需求点个数n再减1，即（m+n-1). 3如不满足上述条件，需要在未填有数字且未划去需要在未填有数字且未划去的方格中填上一个的方格中填上一个0，将它和其他发生供需关系的方格同样对待，而不能看作空格，以满足（m+n-1)的要求。管管 理理 运运 筹筹 学学70（5）初始方案的调整初始方案的调整 在制定初始方案之后，需要对它进行检验，如果判定初始调运输方案不是最优方案，需要对其进行调整直到获得最优调运方案。 1）闭回路 闭回路是以空格为起点，沿同一行或同一列前进，遇上圈格可转90度继续前进，按此方法进行下去，直到回到始点的一个封闭折线。 以始点为第0个点，依次给闭回路上的每一个顶点编号。其中奇序数对应的为奇顶点，偶数对应的为偶顶点。管管 理理 运运 筹筹 学学71每个闭回路具有下列性质：闭回路是一条封闭折线，每一条边都是水平或垂直的；每一行（列）若有闭合回路的顶点，则有两个；只有从空格出发，其余各转角点所对应的方格内均填有数字时，所构成的闭合回路才是我们所说的闭回路；任何过一空格的闭合回路不仅是存在的，而且是惟一的。管管 理理 运运 筹筹 学学72 闭回路如图（a）、（b）、（c）等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。闭回路示意图 管管 理理 运运 筹筹 学学73 表表7给定的初始调运方案为例，说明闭回路给定的初始调运方案为例，说明闭回路的性质。表的性质。表7中给出了空格中给出了空格(1，1)和和(3，1)所所形成的闭回路：形成的闭回路： (1，1) (1，3) (2，3) (2，1) (1，1)管管 理理 运运 筹筹 学学74 需供B1B2B3B4供应量供应量（t）A1400300700A2300100400A3600300900需求量（需求量（t） 3006005006002000表表7 闭回路示意图闭回路示意图管管 理理 运运 筹筹 学学752） 检验数a) 在调运方案内的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运输费用是增加还是减少。b) 把所计算出来的每个闭回路上调整单位运量而使运费发生变化的增减值，称为检验数。c) 如果检验数小于零，表示在该空格的闭回路上调整运输量使运费减少；相反，如果检验数大与零，则会是使运费增加。d) 对于求运费最小的物资调运问题来说，如果所有空格的检验数都小于零，那么如果再对调运方案进行任何调整，都会增加运输费用。管管 理理 运运 筹筹 学学76 3）调运方案是否是最优的判定准则是： 初始调运方案，如果它所有的检验数都是非负的，那么这个初始调运方案一定是最优。否则，这一调运方案不一定是最优的，需要调整。管管 理理 运运 筹筹 学学774) 求检验数方法求检验数方法位势法位势法 管管 理理 运运 筹筹 学学78管管 理理 运运 筹筹 学学79 用该调运问题的相应运价减去表5-14中的数值，那么对初始方案中每个填有运量数值的方格来说，都会满足 而对于每个空格来说，相应得到的数值就是该空格的检验数，即0)(jiijvucjiijijvucx管管 理理 运运 筹筹 学学80运价表运价表工地运价（元/吨）料库B1B2B3B4A1311310A21928A374105管管 理理 运运 筹筹 学学81管管 理理 运运 筹筹 学学82 用位势法求检验数的公式计算初始调运方案的检验数，计算结果列表构成该初始调运方案的检验数表： 需供B1B2B3B4A112A21-1A31012 由于检验数出现负值，依照最优方案判定准则，可知该初始调运方案不一定是最优的需要进行调整。管管 理理 运运 筹筹 学学83 5）调运方案的调整 当判定一个初始调运方案不是最优调运方案时，就要在检验数出现负值的该空格内进行调整。 如果检验数是负值的空格不只一个时，一般选择负检验数绝对值大的空格作为具体的调整对象。 由初始调运方案的检验数表发现，空格的X24检验数是负数因此对其进行调整.管管 理理 运运 筹筹 学学84 需供B1B2B3B4供应量供应量（t）A1400300700A2300100400A3600300900需求量（需求量（t）30060050060020000123管管 理理 运运 筹筹 学学85管管 理理 运运 筹筹 学学86 需供B1B2B3B4供应量供应量（t）A1500200700A2300100400A3600300900需求量（需求量（t）3006005006002000管管 理理 运运 筹筹 学学87 (6)新调运方案运输费 新方案是否是最优方案，还需要对它再进行检验。经计算，该新方案的所有检验数都是非负的，说明这个方案已经是最优调运方案了。 按新方案计算调运物资的运输费用为：8500 管管 理理 运运 筹筹 学学88(7)表上作业法基本步骤小结 综上所述，采用表上作业法求解平衡运输问题的物资调运最优方案，其计算步骤可以归纳如下：列出调运物资的供需(产销)平衡表及运价表；按最小元素法建立初始调运方案；采用位势法计算初始方案每个空格的闭回路的检验数检查检验数，如所有检验数大于等于0，说明方案是最优的，已经得到我们想要的方案，结束求解；如果有某个或某几个为负数，则选择负检验数中绝对值最大的闭回路进行调整，建立新的方案；重复35步，直至获得最优调运方案。管管 理理 运运 筹筹 学学89 运输问题及其模型运输问题及其模型某公司经销一种产品，它下设三个工厂、四个销某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：售部。三个工厂的日产量分别为：A17吨，吨，A24吨，吨，A39吨；各销售部的日销量分别为：吨；各销售部的日销量分别为：B13吨，吨，B26吨，吨，B35吨，吨，B46吨。各厂到吨。各厂到各销售部的单位产品的运价如右表。问该公司应各销售部的单位产品的运价如右表。问该公司应如何调运产品，才能完成运输任务而使运费最省。如何调运产品，才能完成运输任务而使运费最省。 销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 A A1 1 A A2 2 A A3 3 3 3 1 1 7 7 1 1 1 1 9 9 4 4 3 3 3 3 1 1 0 0 1 1 0 0 8 8 5 5 管管 理理 运运 筹筹 学学90 用线性规划法处理此问题。用线性规划法处理此问题。设由产地设由产地i到销地到销地j的运量为的运量为xij，模型为：模型为：min z= 3x11+11x12+3x13+10 x14 +x21 +9x22 +2x23 +8x24 +7x31 +4x32+10 x33+5x34 x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6 xij0 (i=1,2,3; j=1,2,3,4) 运输问题一般用表上作业运输问题一般用表上作业法求解，需建立表格模型：法求解，需建立表格模型：单位运价表单位运价表销地销地 产地产地 B B1 1 B B2 2 B B3 3 B B4 4 产量产量 A A1 1 A A2 2 A A3 3 7 7 4 4 9 9 销量销量 3 3 6 6 5 5 6 6 产销平衡表产销平衡表 销地销地 产地产地 B B1 1 B B2 2 B B3 3 B B4 4 A A1 1 A A2 2 A A3 3 3 3 1 1 7 7 1111 9 9 4 4 3 3 3 3 1010 1010 8 8 5 5 管管 理理 运运 筹筹 学学91表上作业法表上作业法 表上作业法的步骤表上作业法的步骤: (1)给出初始调运方案。给出初始调运方案。 (2)检验方案是否最优检验方案是否最优,若是最优解若是最优解,则停止计算则停止计算;否则转下一步。否则转下一步。 (3)调整调运方案，得新的方案。调整调运方案，得新的方案。 (4)重复重复(2),(3)直到求出最优方案。直到求出最优方案。管管 理理 运运 筹筹 学学922.2.1 给出初始调运方案最常用的方法给出初始调运方案最常用的方法最小元素法最小元素法 表上作业法要求，调运方案的数字格必须为m+n-1个 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 销销地地产产地地B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 33 31 17 71 11 19 94 43 32 21 10 01 10 08 85 5314633管管 理理 运运 筹筹 学学93 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4u ui i A A1 1 A A2 2 A A3 3 1 1 4 4 3 3 2 2 1 10 0 5 5 v vj j 位势表10219-48（2） （9）（8）（9）（-3）（-2） 销销地地产产地地B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 33 31 17 71 11 19 94 43 32 21 10 01 10 08 85 5检验数表若所有检验数非负则是最优解最优性检验的方法最优性检验的方法位势法位势法 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 3 3 6 6 4 4 1 1 3 3 3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 销销地地产产地地B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 31 11 10 02 21 11 12 2- -1 1管管 理理 运运 筹筹 学学94（1）从一个检验数为负数且最小的空格出发，和其它）从一个检验数为负数且最小的空格出发，和其它数字格构成闭回路。可证，此闭回路存在且唯一。数字格构成闭回路。可证，此闭回路存在且唯一。（2）在闭回路上进行运量调整，使选定空格处的运量）在闭回路上进行运量调整，使选定空格处的运量尽可能地增加。尽可能地增加。 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 3 3 6 6 4 4 1 1 3 3 3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 3 3 6 6 5 5 0 0 2 2 1 1 3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6（3）运量调整后，必然使某个数字格变成零。把一个）运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。变成零的数字格抹去，得新的调运方案。方案调整的方法方案调整的方法闭回路法闭回路法管管 理理 运运 筹筹 学学95 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 1 1 4 4 3 3 1 10 0 8 8 5 5 销销量量 位势表10128-37（3） （9）（7） （1）（-2）（-2） 销销地地产产地地B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 33 31 17 71 11 19 94 43 32 21 10 01 10 08 85 5检验数表 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 3 3 6 6 5 5 2 2 1 1 3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 销销地地产产地地B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 30 09 92 22 21 11 12 2表上作业法表上作业法 (续续)检验数都非负，得最优解。管管 理理 运运 筹筹 学学96作业作业 运输问题及其解法运输问题及其解法某公司经销甲产品，它下设三个加工厂，每日的产量分别为某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A1-40吨，吨，A2-40吨，吨，A3-90吨。该公司把这些产品分别运吨。该公司把这些产品分别运往四个销售点，各销售点每日销量为：往四个销售点，各销售点每日销量为：B1-30吨，吨，B2-40吨，吨，B3-60吨，吨，B4-20吨吨, B5-20吨。已知从各工厂到各销售点的单吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少足各销售点需求量的前提下，使总运费为最少 销地 产地B1B2B3B4B5产量（万吨）A171086440A259712640A336581190销量（万吨）3040602020管管 理理 运运 筹筹 学学97 课堂练习：97 例例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产 量A1646200A2655300销 量150150200管管 理理 运运 筹筹 学学98要求：（1）运用最小元素法求出初始调运方案。（2）计算初始调运方案的运输费用。（3）请问还有其他使得运输费用更小的调运方案没有？管管 理理 运运 筹筹 学学99作业2 某公司有三个工厂B1、B2、B3，生产中需要同一种原料，另有三个仓库A1、A2、A3可供应这种原料，由于供需双方两两间的相对位置不同因而运价不同，有关数据如下表： B1 B2 B3 产量 A1 4 8 8 56 A2 16 24 16 82 A3 8 16 24 77 销 量 72 102 41 215问应如何安排运输才能使总运费为最小？管管 理理 运运 筹筹 学学100要求：（1）写出本运输问题的线性规划模型。（2）运用最小元素法求出初始调运方案。（3）计算初始调运方案的运输费用。（4）请问还有其他使得运输费用更小的调运方案没有？管管 理理 运运 筹筹 学学101练习练习3：运输问题及其模型：运输问题及其模型某公司经销一种产品，它下设三个工厂、四个销售某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：部。三个工厂的日产量分别为：A17吨，吨，A24吨，吨，A39吨；各销售部的日销量分别为：吨；各销售部的日销量分别为：B13吨，吨，B26吨，吨，B35吨，吨，B46吨。各厂到各销售部的单吨。各厂到各销售部的单位产品的