专题二-运输规划问题建模-课件

专题二 运输规划问题建模2 2要求使总运费最小的调运方案。如果运输问题的总产量等于其总销量，即则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。建立在产销平衡情况下的运输问题的数学模型。解:假设 xij 表示从Ai到 Bj 的运量,则所求的数学模型为:3 3u目标函数表示运输总费用，要求其极小化；目标函数表示运输总费用，要求其极小化；u第一个约束条件的意义是由各产地运往某一销地的物品数第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；量之和等于该销地的销量；u第二个约束条件表示由某一产地运往销地的物品数量之和第二个约束条件表示由某一产地运往销地的物品数量之和等于该产地的产量；等于该产地的产量；u第三个约束条件表示变量的非负条件。第三个约束条件表示变量的非负条件。4 4 设有三个电视机厂。生产同一种彩色电视机，设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：日生产能力分别是：50，60，50，供应四个，供应四个门市部，日销售量分别是：门市部，日销售量分别是：40，40，60，20台，从各分厂运往个门市部的运费如表所示，台，从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。试安排一个运费最低的运输计划。5 5供求平衡的运输问题：供：供求平衡的运输问题：供：50+60+50=160 需：需：40+40+60+20=160数学模型6 6大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点设有三个电视机厂。生产同一种彩色电视机，日生设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：产能力分别是：50，80，50，供应四个门市部，供应四个门市部，日销售量分别是：日销售量分别是：40，40，60，20台，从各分厂台，从各分厂运往个门市部的运费如表所示，试安排一个运费运往个门市部的运费如表所示，试安排一个运费最低的运输计划。最低的运输计划。供应量供应量180，需求量，需求量160，供需不平衡，供大于求。，供需不平衡，供大于求。8 8供大于求的情况数学模型9 9特点与处理办法特点处理办法：设置一个虚销售点n+1，使且 ，因而化为平衡问题。1010 设有三个电视机厂。生产同一种彩色电视机，设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：日生产能力分别是：50，80，50，供应四个门，供应四个门市部，日销售量分别是：市部，日销售量分别是：40，40，60，20台，台，从各分厂运往个门市部的运费如表所示，试安从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。排一个运费最低的运输计划。供应量180，需求量180，供需平衡。1111 设有三个电视机厂。生产同一种彩色电视机，设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：日生产能力分别是：50，60，50，供应四个门，供应四个门市部，日销售量分别是：市部，日销售量分别是：40，70，60，20台，台，从各分厂运往个门市部的运费如表所示，试安从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。排一个运费最低的运输计划。供应量供应量160，需求量，需求量190，供需不平衡，需求大于供应。，供需不平衡，需求大于供应。1212求大于供求大于供数学模型1313特点与处理办法特点处理办法：增加一个虚产地m+1，使且 ，化为平衡问题。1414 设有三个电视机厂。生产同一种彩色电视机，设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：日生产能力分别是：50，60，50，供应四个门，供应四个门市部，日销售量分别是：市部，日销售量分别是：40，70，60，20台，台，从各分厂运往个门市部的运费如表所示，试安从各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。排一个运费最低的运输计划。供应量供应量190，需求量，需求量190，供需平衡。，供需平衡。1515n这就是运输问题的数学模型，它包含这就是运输问题的数学模型，它包含m n个变量，个变量，m+n个约束条件，是一个线性规划问题。个约束条件，是一个线性规划问题。n如果用单纯形法求解，首先应在每个约束条件上如果用单纯形法求解，首先应在每个约束条件上加入一个人工变量加入一个人工变量(以便求出初始基可行解以便求出初始基可行解)。即使。即使是是m=4，n=5这样的简单问题这样的简单问题,变量个数就有变量个数就有29个个之多，利用单纯形法进行计算是非常复杂的。之多，利用单纯形法进行计算是非常复杂的。n有必要针对运输问题的某些特点，来寻求更为简有必要针对运输问题的某些特点，来寻求更为简单方便的求解方法。单方便的求解方法。1616约束方程组的系数矩阵具有如下特点：约束方程组的系数矩阵具有如下特点：（1）在该矩阵中，它的元素等于）在该矩阵中，它的元素等于0或或1；（2）每列只有两个元素为）每列只有两个元素为1，其余都是，其余都是0；（3）对应于每一个变量，在前）对应于每一个变量，在前m个约束方程中只个约束方程中只出现一次，在后出现一次，在后n个约束方程中也只出现一次。个约束方程中也只出现一次。根据这个特点，在单纯形法的基础上，下面设计根据这个特点，在单纯形法的基础上，下面设计出一种专门用来求解运输问题的方法，称为表上出一种专门用来求解运输问题的方法，称为表上作业法。作业法。1.2 表上作业法表上作业法17171818运输问题的解代表着一个运输方案，其中每一个变运输问题的解代表着一个运输方案，其中每一个变量量xij的值表示由的值表示由Ai调运数量为调运数量为xij的物品给的物品给Bj。运输问题的解运输问题的解X必须要满足模型中的所有约束条件；必须要满足模型中的所有约束条件；基变量对应的约束方程组的系数列向量必须是线性基变量对应的约束方程组的系数列向量必须是线性无关的；解中基变量应由无关的；解中基变量应由 m+n-1个变量组成个变量组成(即基变即基变量的个数量的个数=产地个数产地个数+销售地个数销售地个数 1)，原因是在，原因是在运输问题中虽有运输问题中虽有m+n个约束条件，但由于总产量等个约束条件，但由于总产量等于总销量，有于总销量，有m+n-1个约束条件是线性独立的。个约束条件是线性独立的。怎样的怎样的 m+n-1个变量会构成一组基变量？个变量会构成一组基变量？1919表上作业法是单纯形法在求解运输问题时的一表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法，可归纳为：种简化方法，其实质是单纯形算法，可归纳为：（1）找出初始基可行解；）找出初始基可行解；（2）求各非基变量的检验数；）求各非基变量的检验数；（3）确定换入变量和换出变量，找出新基可）确定换入变量和换出变量，找出新基可行解。行解。（4）重复（）重复（2）、（）、（3）步，直到求得最优解）步，直到求得最优解为止。为止。2020（1）确定初始基可行解）确定初始基可行解最小元素法：最小元素法：u最小元素法的基本思想就是就近供应。即从单位运价表中最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。案为止。u某公司有某公司有3个生产同类产品的工厂，生产的产品由个生产同类产品的工厂，生产的产品由4个销售个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表所示。问该公司应如何调运产各销售点的单位产品运价如表所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。品，在满足各销售点的需要量的前提下，使总的运费为最小。2121初始可行解（最小元素法）就近供应的思想：就近供应的思想：从单位运价表中选取最低从单位运价表中选取最低运价的空格开始供求分配。运价的空格开始供求分配。供应量大于需求量，取值供应量大于需求量，取值为需求量，划去该空格的列；为需求量，划去该空格的列；供应量小于需求量，取值供供应量小于需求量，取值供应量，划去该空格的行。应量，划去该空格的行。根据划去一列或行的单位根据划去一列或行的单位运价表，再选择最小运价的运价表，再选择最小运价的空格进行。空格进行。2222两种特殊情况：两种特殊情况：一是当在中间步骤的未划去的单位运价表中寻找一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到最小，这时从这最小元素时，有多个元素同时达到最小，这时从这些最小元素中任意选择一个作为基变量；些最小元素中任意选择一个作为基变量；二是当在中间步骤的未划去的单位运价表中寻找二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的剩余产量等于该最小元素时，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。这时在产销平衡表相应元素所在列的剩余销售量。这时在产销平衡表相应的位置填上一个数，同时划去一行和一列，需要在的位置填上一个数，同时划去一行和一列，需要在同时划去的行或列的任一空格位置添上一个同时划去的行或列的任一空格位置添上一个“0”。2323某公司有某公司有3个生产同类产品的工厂，生产的产品由个生产同类产品的工厂，生产的产品由4个个销售点销售，各工厂的生产量、各销售点的销售量以销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表所示。利用及各工厂到各销售点的单位产品运价如表所示。利用最小元素法，求该公司的初始调运方案。最小元素法，求该公司的初始调运方案。24242525（2）最优解的判别）最优解的判别判别的方法是计算非基变量即空格的检验数。当所有的非基判别的方法是计算非基变量即空格的检验数。当所有的非基变量检验数全都大于等于变量检验数全都大于等于 0 时为最优解。时为最优解。方法一：闭回路法方法一：闭回路法n在给出调运方案的计算表上，从每一空格出发，在给出调运方案的计算表上，从每一空格出发，找一条闭回路。找一条闭回路。n它是以空格为起点，用水平线或垂直线向前划，它是以空格为起点，用水平线或垂直线向前划，每碰到一数字格就转每碰到一数字格就转 90 度后继续前进。直到回到起度后继续前进。直到回到起始空格处为止，始空格处为止，(A1,B1)空格与空格与(A1,B4)、(A2,B4)和和(A2,B1)三个有数字的格构成一闭回路，如三个有数字的格构成一闭回路，如此等等。此等等。n每个空格都存在唯一的闭回路。每个空格都存在唯一的闭回路。2626闭回路计算检验数的经济解释为：闭回路计算检验数的经济解释为：l在已给出初始解的表中，可以从任一空格出发，如从在已给出初始解的表中，可以从任一空格出发，如从(A1,B1)出发，若让出发，若让 A1 的产品调的产品调 1 吨给吨给B1，为了保持，为了保持产销平衡，就要依次作调整：在产销平衡，就要依次作调整：在(A1,B3)处减少处减少 1 吨，吨，(A2,B3)处增加处增加 1 吨，吨，(A2,B1)处减少处减少 1 吨，即构成了吨，即构成了以以(A1,B1)空格为起点，其它为有数字格的闭回路。空格为起点，其它为有数字格的闭回路。l可见这一调整方案使运费增加了：可见这一调整方案使运费增加了：(+1)3+(-1)3+(+1)2+(-1)1=1(元元)，这表明若这样调整运输方式，这表明若这样调整运输方式将增加运费。将将增加运费。将“1”填入填入(A1,B1)格，就是检验数。格，就是检验数。272728282929 方法二：位势法方法二：位势法对偶数学模型？对偶数学模型？3030检验数3131基变量的方程共有m+n-1个方程，但有m+n个变量，一般令 。因此可求得这些变量。称 分别为产地位势和销地位势。对于本例：3232解得：因而可计算得333334343535 基可行解改进的方法基可行解改进的方法闭回路调整法闭回路调整法取负检验数中绝对值最大的空格作回路。取负检验数中绝对值最大的空格作回路。从空格开始依次给回路顶点格标从空格开始依次给回路顶点格标“+”和和“-”找出找出“-”格中运量最小者，作为调整量，格中运量最小者，作为调整量，将每个将每个“+”格的运量加上该调整量，每个格的运量加上该调整量，每个“-”格的运量减去该调整量。格的运量减去该调整量。即得新的基本可行解。即得新的基本可行解。再计算空格检验数和调整基本解，直到检再计算空格检验数和调整基本解，直到检验数非负为止。验数非负为止。36363737产销平衡的运输问题必定存在最优解。产销平衡的运输问题必定存在最优解。有唯一最优解还是无穷多个最优解？依据有唯一最优解还是无穷多个最优解？依据仍然是看非基变量（即空格处）的检验数仍然是看非基变量（即空格处）的检验数是否有为是否有为0的。若有，则存在无穷多个最优的。若有，则存在无穷多个最优解；否则，只有唯一最优解。解；否则，只有唯一最优解。以检验数为以检验数为0的格为调入格，作闭回路，的格为调入格，作闭回路，调整得最优解。调整得最优解。38381.3 几种特殊的情况几种特殊的情况1）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；3939某供应地不能供应某销地；对策：对策：在对应的运价表格中，运价做在对应的运价表格中，运价做+处理，处理，（一般用（一般用M表示，如何处理呢？）。表示，如何处理呢？）。几种特殊几种特殊情况的处理情况的处理4040 有一批物资在三个供应点，供应给四个需求点，运价如表所示，第三供应点不能向第四需求点运送该物资，求总运费最少调运方案。特殊情况1举例41411）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；对策：在对应供应地和需求地，同时减去对策：在对应供应地和需求地，同时减去A。4242 有一批物资在三个供应点，供应给四个需求点，运价如表所示，第3供应点必须调拨20单位物资给需求点2，求总运费最少的调运方案。特殊情况2举例4343 某玩具公司生产三种新型某玩具公司生产三种新型玩具（玩具（A,B,C），供量分），供量分别为：别为：1000，2000，2000件，三个百货公司件，三个百货公司(甲，乙，丙甲，乙，丙)销量均为销量均为1500件。由于经营等原件。由于经营等原因，各公司销售盈利额不因，各公司销售盈利额不同（见下表），又丙百货同（见下表），又丙百货点要求至少供应点要求至少供应C玩具玩具1000件，而拒绝进件，而拒绝进A玩具，玩具，求满足盈利额最大的供应求满足盈利额最大的供应方案。方案。44441）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；对策：供不应求，增加一个虚拟供地。增加一对策：供不应求，增加一个虚拟供地。增加一个虚拟销地，其需要量为个虚拟销地，其需要量为B。从各产地至其（虚。从各产地至其（虚拟销地）的运价与原运价相同，而从虚拟供地拟销地）的运价与原运价相同，而从虚拟供地至其的运价为至其的运价为+。4545 有甲、乙、丙三个城市，有甲、乙、丙三个城市，每年煤炭需求每年煤炭需求320，250，350单位，由单位，由A和和B两个煤矿负责供应，两个煤矿负责供应，两矿的产量分别为两矿的产量分别为400和和450单位，矿到各城单位，矿到各城市的运价如下表。经过市的运价如下表。经过协商，丙城市必须得到协商，丙城市必须得到320单位的供应，试求单位的供应，试求将两矿煤炭分配出去的将两矿煤炭分配出去的总运费最低的调运方案。总运费最低的调运方案。4646某产地至少运出量某产地至少运出量A对策：供大于求的情况。对策：供大于求的情况。该产地分为产地该产地分为产地1和产地和产地1，产地，产地1的产量为的产量为A，产地，产地1的产量的产量C-A。增加虚拟。增加虚拟销地，产地销地，产地1到虚拟销地到虚拟销地的运费为的运费为M，产地，产地1到虚到虚拟销地的运费为拟销地的运费为0。如表所示的运输问题。假如表所示的运输问题。假定产地定产地2的物资至少运出的物资至少运出38个单位，产地个单位，产地3的物资的物资至少运出至少运出27个单位。求此个单位。求此运输问题的最优解。运输问题的最优解。4747供大于求时，存在储存费用供大于求时，存在储存费用如表所示的运输问题，若产地i有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为3，7，5。求此运输问题的最优解（含运输费和储存费）。4848供不应求时，存在需求不足的损失费供不应求时，存在需求不足的损失费供不应求时，存在需求不足的损失费供不应求时，存在需求不足的损失费如表所示的运输问题，若需地缺少一个单位物资，则将发生损失费用。假定A，B，C需地单位物资需求不足的损失费用分别为5，3，7。求此运输问题的最优解（含运输费和损失费）。4949运输规划问题运输规划问题灵敏度分析灵敏度分析5050已知某运输问题产销平衡，运价表：1.求最优运输调运方案；求最优运输调运方案；2.单位运价表中，运价系数单位运价表中，运价系数cij分别在什么范围之内分别在什么范围之内变化，上面求出的最优调拨方案不变。变化，上面求出的最优调拨方案不变。5151 已知某运输问题的产销已知某运输问题的产销平衡表，最优调运方案平衡表，最优调运方案及单位运价表如下表。及单位运价表如下表。由于从产地由于从产地2到销地到销地B的的道路因故暂时封闭，故道路因故暂时封闭，故需调整最优调拨方案，需调整最优调拨方案，试用尽可能简单的方法试用尽可能简单的方法重新找出最优调运方案。重新找出最优调运方案。5252运输问题的应用运输问题的应用某厂按合同规定必须当年每个季度末分别提供某厂按合同规定必须当年每个季度末分别提供10，15，25，20台同一规格的机器，该厂生产能力及生产每台机器的台同一规格的机器，该厂生产能力及生产每台机器的成本见下表。如果生产出的机器不当季交货，每台每积压成本见下表。如果生产出的机器不当季交货，每台每积压一个季度需要储存和维护费一个季度需要储存和维护费0.15万，要求在完成合同情况万，要求在完成合同情况下，做出使该厂全年生产费用（含储存和维护费）最小的下，做出使该厂全年生产费用（含储存和维护费）最小的决策。决策。5353解：设解：设 xij 表示为第表示为第i季度生产的用于第季度生产的用于第j季度交货的柴油季度交货的柴油机数。根据合同要求，必须满足：机数。根据合同要求，必须满足：x11 =10 x12+x22 =15 x13+x23+x33 =25 x14+x24+x34+x44=20每季度生产的用于当季和以后各季交货的柴油机数不可每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：能超过该季度的生产能力，故又有：x11+x12+x13+x14 25 x22+x23+x24 35 x33+x34 30 x44 10第第 i 季度生产的用于第季度生产的用于第 j 季度交货的每台柴油机的实际成季度交货的每台柴油机的实际成本本 cij 应该是该季度单位成本加上储存、维护等费用。应该是该季度单位成本加上储存、维护等费用。5454设用 ai 表示该厂第 i 季度生产能力，bj 表示第 j 季度的合同供应量，则问题可写成：5555