第7章运筹学运输问题PPT课件

.#，1，7章运输问题，1运输模型2运输问题的计算机3运输问题的解决应用4*运输问题的表操作方法，#，2，实例1，两个原产地A1，A2将物料运输到三个插针B1，B2和B3的公司生产，每个销售，以及将每个原产地运输到各个销售地点的每个物料的运费如下表所示：如何最大限度地降低总运输成本？解决方案：生产和市场营销平衡问题：总销售数量=生产数量=生产地点Ai至销售渠道Bj设置xij运输数量，以获得以下发运指标：minf=6x 114 x 12 6x 135 x 225 x23 s . t . x11x 12x 3=200 x21x 23=300 x11x 21=150 x12x 2=150 x13x 23=200 xij0(I=)J=1、2、3)，1发运模型，#、3、1发运模型；一般发运模型：生产和市场营销平衡A1、A2、Am表示物料的m个原产地。B1、B2、Bn表示物质的n个针脚。Si表示产地Ai的生产；Dj表示销Bj的销售。Cij表示货物从原产地Ai运输到土地Bj的单位运费。将xij设置为从原产地Ai到pin Bj的运输量，以获得以下常见运输量问题的模型：mnm INF=cijxiji=1j=1ns . t . xij=sii=1，2，mj=1mx ij=djj=1，2，ni=1xi j 0 (I=1，2，m；J=1，2，n)更改：1)目标函数有时会查找最大值。如果要查找最大收益或最大销售额，则2)某些运输线的能力受到限制，请直接向模型添加约束(等式或不等式约束)。3)销售不平衡时，可以添加虚拟生产地(销售大于生产时)或销售地(生产大于销售时)。#，4，2发运问题的计算机解决方案。实例2，如果公司将物料从两个原产地A1，A2发运到三个插针B1，B2，B3，则每个原产地生产、每个销售以及每个原产地发运到每个发货方的每个物料的运费如下表所示：如何最大限度地降低总运输成本？解决方案：0，#，5，2增加运输问题的计算机解法。实例3，一家公司将物料从两个原产地A1、A2发运到三个插针B1、B2和B3。将每个产地的生产、每个销售和每个产地运输到每个售货处的运费如下表所示：如何最大限度地降低总运输成本？解决方案：1、销售不平衡的原产地运输成本0、#，6，3运输问题的应用，1，生产和营销不平衡运输问题实例4，石家庄北部研究所1，2，3个地区。分别需要煤3000，1000，2000吨，由河北临城、山西玉县两个煤矿供应，价格、质量相同。供应能力分别为1500，4000吨，秋季为供应。需求大于供应，一个地区的供应才能减少0-300吨，两个地区都要满足需求，三个地区的供应超过1500吨，决定寻求总成本最低的运输方案。解决方案：按照问题的意思制作生产和营销平衡和运单。其中m表示将相应的x31、x33、x34值强制为0的大正数。#，7，3运输问题的应用，一是生产和营销不平衡运输问题的实例5，a，b，c 3化肥厂供应1，2，3，4个地区的农业化肥。假设相同的效果，相关资料如下。总费用要想办法分配最低肥料。解决方案：按问题制定生产和营销平衡和运输表：由于必须满足最低要求，因此相应的虚拟原产地发货费为m，最大要求和最低要求的差异为0，以便根据需要进行排列。相应的4的销售50是考虑到问题本身而适当采取的数值，根据生产和营销平衡要求，d的产量定为50。#，8，3运输问题的应用，第二，生产和存储问题是6，工厂合同上应在相应季度末分别提供10，15，25，20个相同规格的柴油机。这个工厂的季度生产力和各柴油机生产成本已知，如右图所示。制造的柴油引擎如果本季度不交货，每积压一季度的存储、维护等需要0.1万韩元。请把本厂的年生产总费用做成合同完成时最低的决策方案。，#，9，3运输问题的应用，解决：将xij设置为第一季度制造的j季度交付的柴油机数，必须满足以下条件：交货：x11=10生产：X11 x112x3x 14；25x 12x 2=15x 23x 24；35x 113 x 23x 33=25x 34；30x14x24x44=将20x4x4x4x4x4x4x4x4x44第一季度制造的柴油机数报告为I生产工厂的生产；将j季度交付的柴油机数视为j销售点销售。将成本、储存、维护等费用视为运费。生产和市场营销平衡问题可以配置为：目标函数：minf=10.8 X11 10.95 x12 11.1 x13 11.25 x14 11.1x 22 11.25 x23 11.4 x24 11.0 x33 11.15 x34 11.3 x44，#，10，3运输问题的应用，2，生产和存储问题案例7，灯具工厂生产计算机绣线机生产。从1月到6月，每月生产能力、合同销售、电脑刺绣机1台平均生产成本见下表。据悉，截至去年年底，储备了103台绣花机，如果本月生产机器不能在该月交货，就要运输到分店仓库，每台运输费用为0.1万韩元，每台机器每月平均储存费，保管费为0.2万韩元。7-8月销售淡季，工厂停工一个月，6月销售合同完成后，仍有80台库存。加班生产机器每台增加了1万元的费用。要将运输、仓库、维护等总生产成本降至最低，应该如何准备1-6月的生产？#，11，3运输问题的适用，解决：此生产存储问题可以视为运输问题。考虑：每月生产和交货分别为原产地和销售1) 1-6月的总能力(包括去年年末的存储量)为743台，销售额为707台。将虚拟销售销售设置为36。2)去年年末库存103台，仅仓库费和运输费显示为零行；3)6月需求70台除销售外，80台库存的需求70 80=150台；(4) 1-6表示1-6月正常生产情况，1-6 表示1-6月加班生产情况。生产和营销平衡和运输表：#，12，3运输问题的应用，使用“管理运营研究”软件获得的结果如下。1-6月的最低生产成本为8307.5万韩元，每月销售安排见下表。#，13，3运输问题的应用，3，运输问题：在原始运输问题中添加多个转运点。运输方式包括原产地转运站、转运站销售地、原产地、原产地、出口地、销售地等。例8、起飞电子仪表公司在大连和广州两个分厂生产相同的仪器，大连分厂一个月生产400台，广州分厂一个月生产600台。该公司在上海和天津有两家销售公司，负责南京、济南、南昌和青岛四个城市的仪器供应。另外，由于大连更接近青岛，公司同意大连分厂直接供应青岛，运输费用为图片，单位100元。问如何运输仪器才能使总运输成本最低。图1-广州，2-大连，3-上海，4-天津，5-南京，6-济南，7-南昌，8-青岛。#，14，3运输问题的应用，解决：将xij从I设置为j的运输量，获得具有以下特征的线性编程模型：目的函数：Minf=所有可能的运输成本(运输单价与运输量的乘积)约束：原产地(发货方)I:出口量-输入量=产量对在途量(在途地点):输入量-出口量=0对销(接收点)j(续)目的函数：minf=2x 13 3x 314 3x 24 x28 2x 35 6x 37 6x 338 4x 454 x46 6x 4545 x48限制：s.t.x13 x14600(广州工厂供货限制)x23 x24 x28，#，15，3运输问题的应用，使用“管理操作研究”软件获得的结果：x13=550x11 X23=0x24=100x28=300X35=200x36=0 x37=350x8=0X45=0 x46=150 x47=0 x48=0。最低运输成本为4600元。实例9，公司有A1、A2、A3三个分厂，分别由B1、B2、B3和B4个地区的销售公司销售。假定质量相同，相关数据如下表所示：请设法制定总费用最低的运输方案。假设：1。各工厂的物资不一定直接运送到销售地，可以在那几个生产地一起运输。2.运往各个销售地的物资可以先运到其中几个销售地，然后再运到其他销售地。3.除了生产生产和销售处外，还有几个中继站，在生产地之间、销售地之间或生产地和销售地之间转移。#，16，3运输问题的适用，运费为：解决：将此运输问题转换为一般运输问题：1、所有产地、土地、转运站均视为产地和销售地；2、在运输表单上，不可能的运费为m，对自己的运费为0。3、Ai:生产20原始生产，销售20；t:生产、销售均为20；Bi:生产20，销售20原始销售，其中20是在每个地点可以更改的最大流。4，在最佳方案中，其中XII是自己的运输量，实际上不起作用。#，17，3运输问题的应用，扩展运输问题生产和营销平衡和运输表：#，18，4 *运输问题的表操作法，表操作法是解决运输问题的特殊方法，其本质是简单的方法。有运输问题的最佳解决方案。计算流程(假定生产和市场营销平衡):1。寻找初始预设可执行解决方案。对于生产和营销平衡问题，有关于产量的m个约束方程和关于销售的n个约束方程。由于生产和市场营销平衡，该模型最多只有m n-1个单独约束方程。换句话说，运输问题有m n-1个基本变量。Mn的生产和市场营销平衡表给出了m n-1个数字，其调整值是默认变量的值。2.查找每个非基本变量的检查数。也就是说，确定上述m n-1基准变量以外的空格的检查数是否达到最佳解决方案，如果已经达到最佳，则停止计算，否则继续下一步。3.确定默认变量和默认变量，并找到新的默认可能解决方案。由表格中的封闭回路方式控制。重复2、3，直到获得最佳解决方案。#，19，4 *运输问题的表操作方法，实例10。斜食公司有三家生产面包的分厂A1、A2、A3、4家销售公司B1、B2、B3、B4，各分店工厂的日产量、各销售公司的日产量、各分店到各销售公司的单位运输价格，如表所示，表格中的产量和销售单位为吨，售价单位为百元/询问公司如何运输总运费最低的产品，同时满足销售地点特定需求。生产销售是平衡的运输问题，没有必要重新建立虚拟生产地或销售地。#，20，4 *确定运输问题的表操作方法，第一，确定初始默认可行解决方案将初始默认可行解决方案与运费区分开来，将运费率放在每个列的右上角，然后在每个列的中间创建初始默认可行解决方案(调整)。1.西北角法：首先，从位于表左上角(即西北角)的变量X11开始分配运输量，然后取X11可能的大值x11=min(7，3)=3，则x21和x31等于0。B1的销售量和A1的产量都减去3，把销售量和产量合计起来，得出原来的销售量和产量。同样，您可以获得剩馀的初始可行解决方案。3，11，3，10，8，5，10，2，9，4，7，1，#，21，4 *运输问题的表格作业方式，2 .最小元法西北角法是对北角的变量分配运输量，最小元法是最近的供应，是对单位运费的最小变量分配运输量。在表格中寻找单位售价最低的x21，将x21=min(4，3)=3，A1的产量变更为1，B1的销售量变更为0，然后划下B1。与在剩下的33矩阵中查找最小运费一样，可以得到其他基本的可行解。一般来说，用最小单元法求的早期基本可行解小于用西北角法求的总运费。这可能需要较少的迭代次数，从通过最小元素方法获得的初始基本可行解决方案中寻找最佳解决方案。，3，11，3，10，8，5，10，2，9，4，7，1，#，22，4 *运输问题的表工作法查找初始基本可执行解决方案时需要注意的两个问题：1。设置xij值会导致Ai的产量和Bj的销售额都更改为0。在这种情况下，只能跨越Ai行或Bj列，但不能同时跨越Ai行和Bj列。2.使用最小单元法时，可能会出现只剩下一列或一列的所有空格未填充或未填充的情况。此时，不能将此行或列中填充的数字减去，全部填零，留空。这样，填充的或为零的单元格将为m n-1。也就是说，默认变量的数量为m n-1。#，23，4 *运输问题的表操作法，第二，最佳解决方案的判别1。闭合环方法所谓闭合环从给定运输系统中表示非默认变量的一个空间水平或垂直方向出发，只有表示默认变量的实心数字的单元继续向左或向右90度(当然方向不能改变)，直到返回出发的那个空位为止。由此产生的闭合线称为闭合环。空格有其自己的闭合环。闭路方法是对表示非基本变量的空格(调整为0)，其调整量为1，因为生产营销的平衡，我们要在这个空格的闭路顶点的调整量中增加或减少1。最后，我们计算了这些变化给整个运输计划的总运输成本带来的变化。如果表示非基本变量中空格的所有检查数(即非基本变量中的检查数)大于0，则得到最佳解决方案。否则，继续迭代以找到最佳解决方案。#，24，4 *运输问题的表格处理方法从非标准变量X11开始，查找上表所示的闭合回路。循环有四个顶点(X11除外)，其他顶点是默认变量。目前X11的运输量从0增加到1吨，运费也增加了3元，为了平衡A1产量，x13需要减少到1吨，运费需要减少到3元。为了平衡B3的销售，x23需要增加1吨，运费需要增加2元。同样，将x21减少1吨，运费减少1韩元。调整后总运费增加3-3 2-1=1元。说明X11是默认变量时，运费增加，X11的检验数增加1，添加1以区分调整量。您可以使用相同的方法查找所有空格(即非默认变量)的检查数。3、11、3、10、8、5、10、2、9、4、7、