第二次--运输问题.doc

第二次 运输问题1运输问题的一般提法 设有个产地，将生产的物资联合运往个销地；各产地的产量为，各销地的销量为；从产地到销地的单位运价为，问如何组织运输，可使总的运费最少？ 如果总的产量总的销量，则称它为产销平衡运输问题2产销平衡运输问题的数学模型 引入决策变量：用表示从产地运到销地的物资数量确定目标函数：使总运输费用最少 写出约束条件：从产地运出的物资数量应等于产地的物资供应量 即 运到销地的物资数量应等于销地的需求量 即 取值非负。说明： 运输问题是一线性规划问题； （其中）是运输问题的一个可行解，从而它有基本可行解； 又，故运输问题的任一可行解都是有限的，即可行域有界；因此运输问题必有有限最优解且最优解同样可在基本可行解处得到。 针对个产地个销地的产销平衡运输问题，其约束条件中共有个方程，但这 个方程中，任一方程都可以通过其余方程得到。因此真正有效的方程个数是个，我们可以将多余的一个方程划掉。这样以来，运输问题的基本可行解 中只含个基变量。 当和取值较大时，引入的决策变量较多，采用表格单纯形法计算量较大，通常采用表上作业法求解运输问题。3求初始调运方案（初始基本可行解）1）左上角方法：从表格中左上角方格所对应的决策变量开始分配运输量，分配时让它取尽可能大的取值。2）最小元素法：从表格中最小单位运价所对应的决策变量开始分配运输量，分配时让它取尽可能大的取值。 3）沃格尔（Vogel）法： （）首先计算每一行和每一列的次小单位运价与最小单位运价之间的差值，并分别称之为相应的行罚数和列罚数； （）将各行的行罚数写在运输表格的右侧一列，将各列的列罚数写在运输表格下侧一行； （）确定最大罚数值所在的行或列，从该行或该列最小单位运价所对应的决策变量开始分配运输量，分配时让它取尽可能大的取值。 销地产地供应量2910791342584257需求量38462121 分配完之后，划掉表格中的一行或一列，得新的运输表格，再重复上述步骤。 用以上三种方法得到的初始基本可行解，它们对应的目标函数值，以沃格尔法为最小，最小元素法次之，以左上角方法为最大。4最优方案的判别及调运方案的改进（1） 闭回路概念 凡是能排成如下形式的变量集合 （其中互不相同，也互不相同）就称为一个闭回路。 闭回路中出现的变量称为闭回路的顶点，相邻两个顶点的连线称为闭回路的边。 现将闭回路的顶点在运输表格中画出来，同时将相邻顶点用直线段连接起来，就可以得到一条封闭折线。 闭回路的特点：）表中的各行各列至多只有闭回路的两个顶点； ）闭回路的边要么是水平的，要么是铅直的。（2） 用闭回路方法计算非基变量的检验数 以非基变量所在的方格为起点，作一闭回路；（除起点之外，要求闭回路的 其它顶点必须是基变量）然后在闭回路上作运输量是一个单位的调整，并计算由此引起 的总运费的改变量。 该改变量称为非基变量的检验数。 销地产地供应量2910791342584257需求量38462121（3） 最优调运方案的判别准则 如果所有非基变量的检验数全都，则此时的调运方案便是最优方案。（4） 调运方案的改进 以最小负检验数所在的方格为起点，作一闭回路(除起点之外，要求闭回路的 其它顶点必须是基变量)；然后在闭回路上作运输量尽可能大的调整（调整量为负号格中的最小运输量）。5用位势法计算非基变量的检验数 对于个产地个销地的运输问题（1） 引入个待定变量和，并将写在产地的左边，将写在销地的上方；（2） 待定变量和的取值满足如下方程组 基变量所在方格的单位运价 该行的行位势该列的列位势 由于基本可行解中只有个基变量，故方程组中只有个方程，但却有 未知量，因此方程组有无穷多组解，一般我们取的这组解。 （3）非基变量的检验数6产销不平衡运输问题 （1）总产量大于总销量 处理方法：）虚设一个销地；）虚设销地的需求量等于总产量减去总销量； ）各产地到虚设销地的单位运价设为零。（属于物资就地存储） （2）总产量小于总销量处理方法：）虚设一个产地；）虚设产地的供应量等于总销量减去总产量； ）虚设产地到各销地的单位运价设为零。（属于缺货情形）7需求分两种情形的运输问题 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区的使用效果相同，已知各化肥厂的年产量、各地区的需求量以及各化肥厂到各地区的运价如下表：试决定使总运费最省的化肥调拨方案。 需求地区化肥厂 产量（万吨）ABC16 13 22 1714 13 19 1519 20 23 506050最低需求量（万吨）最高需求量（万吨）30 70 0 10 50 70 30 不限 （1）第地区每年最多可以分到的化肥数量 三个化肥厂每年的总产量为160万吨，其它三个地区每年的最低需求必须得到满足， 所以第地区每年最多可以分到的化肥数量为万吨； （2）按最高需求量建立产销平衡运输问题，此时最高需求量为总产量 160万吨，所以要虚设一个产地D，虚设产地的产量为万吨； （3）有两种需求的地区当做两个地区来对待。其中第一地区的需求量为最低需求部分，它必须 得到满足，故它不能由虚设产地D供应，因此产地D到它的单位运价设为M（M是一个 很大的正数）。 第二地区的需求量为该地区的额外需求部分（最高需求量减去最低需求量），有条件 时可以得到满足，产地D到它的单位运价定为零。 销地产地产量A1616135022171750B14141320191510153060C1930192020 023MM50虚设DM0M030M02050需求量302070301050 2102108可化为运输问题的其它线性规划问题 由于表上作业法比单纯形算法简单，所以人们常常尽可能地将线性规划问题转化成运输问题。例1 生产计划问题 某厂按合同规定须于每个季度末分别完成10，15，25，20台同一规格柴油机。已知该厂各季度生产能力及生产每台柴油机成本如下表。又如果生产出来的柴油机当季度不交货，每台每积压一个季度需储存、维护费用万元。要求在完成合同的条件下，制定使该厂全年生产、储存和维护费用为最少的决策方案。季 度生产能力（台）25353010单台成本（万元）10.811.111.011.3线性规划模型： 用表示第季度生产用于第季度交货的柴油机台数 由于每季度生产能力的限制，有约束 由合同要求，必须满足 第季度生产用于第季度交货的每台柴油机，它的实际成本是由生产成本和储存维护费用两部分组成，具体数值如下表 ij10.810.9511.111.2511.111.2511.411.011.1511.3 目标函数为： 从上述模型可以看到，在保证的条件下，上述模型类似于总产量大于总销量的产销不平衡运输问题的线性规划模型。 销地产地虚设10.810.9511.111.250M11.111.2511.40MM11.011.150MMM11.30例2 自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应。四个区每天必须得到保证的基本生活用水量分别为30，70，10，10千吨，但由于水源紧张，三个水库每天最多只能分别供应50，60，50千吨自来水。由于地理位置的差别，自来水公司从个水库向各区送水所需付出的引水管理费不同（见下表，其中C水库与丁区之间没有输水管道），其他管理费用都是450元/千吨。根据公司规定，各区用户按照统一标准900元/千吨收费。此外，四个区都向公司申请了额外用水量，分别每天50，70，20，40千吨。该公司应如何分配供水量，才能获利最多？为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加多少？引水管理费（元/千吨）甲 乙 丙 丁A160 130 220 170B140 130 190 150C190 200 230 /问题分析：（1）分配供水量就是安排从三个水库向四个区送水的方案，目标是获利最多。（2）从题目给出的数据可知，三个水库的供水量为160千吨； 四个区的基本生活用水量与额外用水量之和为300千吨，所以自来水公司的水能全部卖出并能获利。（3）自来水公司的总收入为 元-与送水方案无关 公司每天的其它管理费用为 元-与送水方案无关（4）想使利润最大，只需使引水管理费最小。模型建立：引入决策变量：用表示水库向区的日供水量。 由于C水库与丁区之间没有输水管道，故写出约束条件：约束条件有两类（一类是水库的供应量限制，另一类是各区的需求量限制） 由于供水量能全部卖出，故有如下供水量限制：A水库供给四个区的总供水量应等于A水库的日供应量50千吨 需求量限制可表示为 所有决策变量的非负限制 确定目标函数：引水管理费用最小。 用LINDO求解得：A水库向乙区供水50千吨；B水库向乙、丁区分别供水50，10千吨； C水库向甲、丙分别供水40、10千吨。 引水管理费用为 24400元讨论：如果A、B、C三个水库每天的最大供水量都提高一倍，则公司总供水能力为每天320千吨，大于每天的总需求量300千吨，此时水库供水量不能全部卖出，因而不能将获利最多问题转化成引水管理费用为最少的问题。为此我们首先计算A、B、C三个水库分别向甲、乙、丙、丁四个区供应每千吨水的净利润，即从收入900元中减去其它管理费用450元，再减去引水管理费，得下表净利润（元/千吨）甲 乙 丙 丁A290 320 230 280B310 320 260 300C260 250 220 /目标函数为： 由于供水量不能全部卖出，所以供水量限制改为： 用LINDO求解得：A水库向乙区供水100千吨；B水库向甲、乙、丁区分别供水30，40，50千吨； C水库向甲、丙分别供水50、30千吨。 总利润为 88700元注意：由于每个区的供水需求量都能完全满足，故需求量限制可改为 例3 货机装运问题某架货机有三个货舱：前舱、中舱、后舱。三个货舱所能装载的最大重量和体积都有限制。为了保持飞机的平衡，三个货舱中实际装载货物的重量与其最大容许重量成比例。前舱 中舱 后舱重量限制（吨）10 16 8体积限制（） 6800 8700 5300现有四类货物供该货机本次飞行装运，其有关信息如下表。重量（吨） 空间（） 利润（）货物118 480 3100货物2 15 650 3800货物3 23 580 3500货物4 12 390 2850应如何安排装运，使该货机本次飞行获利最大？模型假设：1）每种货物可以分割成任意小；2）每种货物可以在一个或多个货舱中任意分布；3）多种货物可以混装，并保证不留空隙。模型建立：引入决策变量：用表示第种货物装入第个货舱的重量确定目标函数：