专题二 运输规划问题建模

专题二运输规划问题建模第一页，共五十六页，编辑于2023年，星期六1煤炭、钢铁、木材、粮食等物资,在全国有若干生产基地，据已有交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。这类问题可用以下数学语言来描述：假设有m个生产地点，可以供应某种物资(以后称为产地)，用Ai表示，i=1,2,,m；有n个销售地，用Bj表示，j=1,2,,n；产地的产量和销售地的销售量分别为ai,i=1,2,,m和bj，j=1,2,,n，从Ai到Bj运输单位物资的运价为cij，这些数据可汇总于如表。1.1运输问题数学模型第二页，共五十六页，编辑于2023年，星期六2销地产地B1B2Bn产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量b1b2bn第三页，共五十六页，编辑于2023年，星期六3要求使总运费最小的调运方案。如果运输问题的总产量等于其总销量，即则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。建立在产销平衡情况下的运输问题的数学模型。解:假设xij

表示从Ai到Bj

的运量,则所求的数学模型为:第四页，共五十六页，编辑于2023年，星期六4目标函数表示运输总费用，要求其极小化；第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；第二个约束条件表示由某一产地运往销地的物品数量之和等于该产地的产量；第三个约束条件表示变量的非负条件。第五页，共五十六页，编辑于2023年，星期六5设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂1234供应总计12397612359796711506050需求总计40406020第六页，共五十六页，编辑于2023年，星期六6供求平衡的运输问题：供：50+60+50=160

需：40+40+60+20=160数学模型第七页，共五十六页，编辑于2023年，星期六7设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，80，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂1234供应12397612359796711508050需求40406020供应量＝180，需求量＝160，供需不平衡，供大于求。第八页，共五十六页，编辑于2023年，星期六8供大于求的情况数学模型第九页，共五十六页，编辑于2023年，星期六9特点与处理办法特点处理办法：设置一个虚销售点n+1，使且，因而化为平衡问题。第十页，共五十六页，编辑于2023年，星期六10设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，80，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂12345供应总计12397612359796711000508050需求总计4040602020供应量＝180，需求量＝180，供需平衡。第十一页，共五十六页，编辑于2023年，星期六11设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，70，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂1234供应总计12397612359796711506050需求总计40706020供应量＝160，需求量＝190，供需不平衡，需求大于供应。第十二页，共五十六页，编辑于2023年，星期六12求大于供数学模型第十三页，共五十六页，编辑于2023年，星期六13特点与处理办法特点处理办法：增加一个虚产地m+1，使且，化为平衡问题。第十四页，共五十六页，编辑于2023年，星期六14设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：50，60，50，供应四个门市部，日销售量分别是：40，70，60，20台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。门市部工厂1234供应总计123497601235097906711050605030需求总计40706020供应量＝190，需求量＝190，供需平衡。第十五页，共五十六页，编辑于2023年，星期六15这就是运输问题的数学模型，它包含mn个变量，m+n个约束条件，是一个线性规划问题。如果用单纯形法求解，首先应在每个约束条件上加入一个人工变量(以便求出初始基可行解)。即使是m=4，n=5这样的简单问题,变量个数就有29个之多，利用单纯形法进行计算是非常复杂的。有必要针对运输问题的某些特点，来寻求更为简单方便的求解方法。第十六页，共五十六页，编辑于2023年，星期六16约束方程组的系数矩阵具有如下特点：（1）在该矩阵中，它的元素等于0或1；（2）每列只有两个元素为1，其余都是0；（3）对应于每一个变量，在前m个约束方程中只出现一次，在后n个约束方程中也只出现一次。根据这个特点，在单纯形法的基础上，下面设计出一种专门用来求解运输问题的方法，称为表上作业法。1.2表上作业法第十七页，共五十六页，编辑于2023年，星期六17第十八页，共五十六页，编辑于2023年，星期六18运输问题的解代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。运输问题的解X必须要满足模型中的所有约束条件；基变量对应的约束方程组的系数列向量必须是线性无关的；解中基变量应由m+n-1个变量组成(即基变量的个数=产地个数+销售地个数–1)，原因是在运输问题中虽有m+n个约束条件，但由于总产量等于总销量，有m+n-1个约束条件是线性独立的。怎样的m+n-1个变量会构成一组基变量？第十九页，共五十六页，编辑于2023年，星期六19表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法，可归纳为：（1）找出初始基可行解；（2）求各非基变量的检验数；（3）确定换入变量和换出变量，找出新基可行解。（4）重复（2）、（3）步，直到求得最优解为止。第二十页，共五十六页，编辑于2023年，星期六20（1）确定初始基可行解最小元素法：最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。第二十一页，共五十六页，编辑于2023年，星期六21初始可行解（最小元素法）门市工厂1234供应123403020301030506050需求40306030就近供应的思想：从单位运价表中选取最低运价的空格开始供求分配。供应量大于需求量，取值为需求量，划去该空格的列；供应量小于需求量，取值供应量，划去该空格的行。根据划去一列或行的单位运价表，再选择最小运价的空格进行。门市工厂1234供应12397612359796711506050需求40306030第二十二页，共五十六页，编辑于2023年，星期六22两种特殊情况：一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到最小，这时从这些最小元素中任意选择一个作为基变量；二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。这时在产销平衡表相应的位置填上一个数，同时划去一行和一列，需要在同时划去的行或列的任一空格位置添上一个“0”。第二十三页，共五十六页，编辑于2023年，星期六23某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表所示。利用最小元素法，求该公司的初始调运方案。销地产地B1B2B3B4产量A1531049A216964A32010577销量3584第二十四页，共五十六页，编辑于2023年，星期六24门市工厂1234供应123317119432101085749需求2657门市部工厂1234供应12392612359796711506050需求总计40703020第二十五页，共五十六页，编辑于2023年，星期六25（2）最优解的判别判别的方法是计算非基变量即空格的检验数。当所有的非基变量检验数全都大于等于0时为最优解。①方法一：闭回路法在给出调运方案的计算表上，从每一空格出发，找一条闭回路。它是以空格为起点，用水平线或垂直线向前划，每碰到一数字格就转90度后继续前进。直到回到起始空格处为止，(A1,B1)空格与(A1,B4)、(A2,B4)和(A2,B1)三个有数字的格构成一闭回路，如此等等。

每个空格都存在唯一的闭回路。第二十六页，共五十六页，编辑于2023年，星期六26闭回路计算检验数的经济解释为：在已给出初始解的表中，可以从任一空格出发，如从(A1,B1)出发，若让A1的产品调1吨给B1，为了保持产销平衡，就要依次作调整：在(A1,B3)处减少1吨，(A2,B3)处增加1吨，(A2,B1)处减少1吨，即构成了以(A1,B1)空格为起点，其它为有数字格的闭回路。可见这一调整方案使运费增加了：(+1)3+(-1)3+(+1)2+(-1)1=1(元)，这表明若这样调整运输方式将增加运费。将“1”填入(A1,B1)格，就是检验数。第二十七页，共五十六页，编辑于2023年，星期六27销地产地B1B2B3B4产量A1437A2314A3639销量3656销地产地B1B2B3B4产量A13113107A219284A3741059销量3656第二十八页，共五十六页，编辑于2023年，星期六28空格闭回路检验数(A1,B1)(1,1)→(1,3)→(2,3)→(2,1)→(1,1)1(A1,B2)(1,2)→(1,4)→(3,4)→(3,2)→(1,2)2(A2,B2)(2,2)→(2,3)→(1,3)→(1,4)→(3,4)→(3,2)→(2,2)1(A2,B4)(2,4)→(2,3)→(3,3)→(1,4)→(2,4)-1(A3,B1)(3,1)→(3,4)→(1,4)→(1,3)→(2,3)→(2,1)→(3,1)10(A3,B3)(3,3)→(3,4)→(1,4)→(1,3)→(3,3)12第二十九页，共五十六页，编辑于2023年，星期六29②方法二：位势法对偶数学模型？第三十页，共五十六页，编辑于2023年，星期六30检验数第三十一页，共五十六页，编辑于2023年，星期六31基变量的方程共有m+n-1个方程，但有m+n个变量，一般令。因此可求得这些变量。称分别为产地位势和销地位势。对于本例：第三十二页，共五十六页，编辑于2023年，星期六32解得：因而可计算得第三十三页，共五十六页，编辑于2023年，星期六33门市工厂1234供应总计191296U1

401027377U23030365911u33020v1v2v3v4第三十四页，共五十六页，编辑于2023年，星期六34门市工厂1234供应总计191296U130

20

27377U22040365911u34010v1v2v3v4第三十五页，共五十六页，编辑于2023年，星期六35③基可行解改进的方法——闭回路调整法取负检验数中绝对值最大的空格作回路。从空格开始依次给回路顶点格标“+”和“-”找出“-”格中运量最小者，作为调整量，将每个“+”格的运量加上该调整量，每个“-”格的运量减去该调整量。即得新的基本可行解。再计算空格检验数和调整基本解，直到检验数非负为止。第三十六页，共五十六页，编辑于2023年，星期六36门市工厂1234供应总计19129650

+

4010-273776030-30+3659115030+20

-需求总计40406020第三十七页，共五十六页，编辑于2023年，星期六37产销平衡的运输问题必定存在最优解。有唯一最优解还是无穷多个最优解？依据仍然是看非基变量（即空格处）的检验数是否有为0的。若有，则存在无穷多个最优解；否则，只有唯一最优解。以检验数为0的格为调入格，作闭回路，调整得最优解。第三十八页，共五十六页，编辑于2023年，星期六381.3几种特殊的情况1）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；第三十九页，共五十六页，编辑于2023年，星期六39某供应地不能供应某销地；对策：在对应的运价表格中，运价做+∞处理，（一般用M表示，如何处理呢？）。几种特殊情况的处理第四十页，共五十六页，编辑于2023年，星期六40有一批物资在三个供应点，供应给四个需求点，运价如表所示，第三供应点不能向第四需求点运送该物资，求总运费最少调运方案。1234s1231614191313202219231715M506050d30705010特殊情况1举例第四十一页，共五十六页，编辑于2023年，星期六411）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；对策：在对应供应地和需求地，同时减去A。第四十二页，共五十六页，编辑于2023年，星期六42有一批物资在三个供应点，供应给四个需求点，运价如表所示，第3供应点必须调拨20单位物资给需求点2，求总运费最少的调运方案。1234s123161419131320221923171516506050（30）d3070（50）5010特殊情况2举例第四十三页，共五十六页，编辑于2023年，星期六43某玩具公司生产三种新型玩具（A,B,C），供量分别为：1000，2000，2000件，三个百货公司(甲，乙，丙)销量均为1500件。由于经营等原因，各公司销售盈利额不同（见下表），又丙百货点要求至少供应C玩具1000件，而拒绝进A玩具，求满足盈利额最大的供应方案。甲乙丙供A54-1000B16892000C1210112000第四十四页，共五十六页，编辑于2023年，星期六441）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；对策：供不应求，增加一个虚拟供地。增加一个虚拟销地，其需要量为B。从各产地至其（虚拟销地）的运价与原运价相同，而从虚拟供地至其的运价为+∞

。第四十五页，共五十六页，编辑于2023年，星期六45有甲、乙、丙三个城市，每年煤炭需求320，250，350单位，由A和B两个煤矿负责供应，两矿的产量分别为400和450单位，矿到各城市的运价如下表。经过协商，丙城市必须得到320单位的供应，试求将两矿煤炭分配出去的总运费最低的调运方案。甲乙丙A151822B212526第四十六页，共五十六页，编辑于2023年，星期六46某产地至少运出量A对策：供大于求的情况。该产地分为产地1和产地1’，产地1的产量为A，产地1’的产量C-A。增加虚拟销地，产地1到虚拟销地的运费为M，产地1’到虚拟销地的运费为0。如表所示的运输问题。假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位。求此运输问题的最优解。ABC产112220214540323330销302020第四十七页，共五十六页，编辑于2023年，星期六47供大于求时，存在储存费用如表所示的运输问题，若产地i有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为3，7，5。求此运输问题的最优解（含运输费和储存费）。ABC产112220214540323330销302020第四十八页，共五十六页，编辑于2023年，星期六48供不应求时，存在需求不足的损失费如表所示的运输问题，若需地缺少一个单位物资，则将发生损失费用。假定A，B，C需地单位物资需求不足的损失费用分别为5，3，7。求此运输问题的最优解（含运输费和损失费）。ABC产112220214520323330销303030第四十九页，共五十六页，编辑于2023年，星期六49运输规划问题

灵敏度分析第五十页，共五十六页，编辑于2023年，星期六50已知某运输问题产销平衡，运价表：门市工厂1234供应12397612359796711506050需求40406020求最优运输调运方案；单位运价表中，运价系数cij分别在什么范围之内变化，上面求出的最优调拨方案不变。第五十一页，共五十六页，编辑于2023年，星期六51已知某运输问题的产销平衡表，最优调运方案及单位运价表如下表。由于从产地2到销地B的道路因故暂时封闭，故需调整最优调拨方案，试用尽可能简单的方法重新找出最优调运方案。ABCDE11020591022101030631207104ABCDE产1459244331138销35463第五十二页，共五十六页，编辑于2023年，星期六52运输问题的应用 某厂按合同规定必须当年每个季度末分别提供10，15，25，20台同一规格的机器，该厂生产能力及生产每台机器的成本