运筹学中运输问题的分析和应用.ppt

* 答 辩 人： 指导老师： 专 业：数学与应用数学 一、运输问题的基本模型 二、对于产销平衡问题的求解 三、对产销不平衡问题的分析 四、可转化为运输问题的情况 五、运输问题在实际生活中的应用 六、小结 产销平衡的运输问题也是线性规划问题，它的基本模型是： 约束条件 2.1 求解初始基可行解 2.1.1 最小元素法 从运输表中的最小单位运价处开始确定产销关系，尽量满足其供需量，并划去某一行或某一列。然后从剩余的单位运价中选择最小的，依此类推，直到给出初始可行解为止。 2.1.2 伏格尔法 伏格尔法的求解步骤如下： 步骤一：求出每行的行差额（每行单位运价中次小和最小之差）和每列的列差额（每列单位运价中次小和最小之差）。 步骤二：在行差额和列差额中找出差额最大的行和列，给差额最大的行和列的最小运价所在单元格首先填入运量。 步骤三：划去已经满足产量的行或已经满足销量的列，在剩下的运价中重复步骤一和步骤二，直到求得初始的调运方案。 2.2 判断可行解的最优性 2.2.1 用闭回路法判断 验证过程如下：从某一空格出发，沿水平或垂直方向前进，当遇到数字格时可以任意转（也可以穿过数字格）继续前进，直到回到起始点，此时起始空格和拐角上的数字格共同构成闭回路 。然后，求出每个非基变量的检验数，若存在小于零的检验数，则该解不是最优解。 2.2.2 用位势法判断 步骤一：在运输表右端增加一列，称为行位势，记为 在运输表的下面增加一行，成为列位势，记为 。 步骤二：令某一个 或 等于零（或任意有限值），利用基变量的 检验数 ，由基变量的 和其对应的某个已知 行位势 或列位势 ，依次计算出其他行位势或列位势。 步骤三：按 来计算各非基变量的检验数。由运输表 中的每一个非基变量 减去位势表中对应格的行位势和列位势， 得到每个非基变量的检验数（基变量的检验数都为0,为简便可省略不写），形成检验数表。 2.3 用闭回路调整法对非最优解进行调整 步骤1：确定进基变量。一般情况下，当 时，选择 为进基变量。 步骤2：确定出基变量。 （1）以 为起点寻找由原基变量构成的闭回路。 （2）以 为始点，沿任意一个方向对闭回路拐角上的变量（包括 ）依次标“+”和“-”，标有“-”的基变量中运量最小的变量即为出基变量，出基变量的运量记为 。 步骤3：基变换。步骤2中找到的闭回路中标有“-”的格，减去；标有“+”的格加，就得到一个新的基可行解。 步骤4：判断解的最优性。计算新解的非基变量检验数，若所有非基变量，则得最优，否则重复以上步骤。 当产大于销时，即 该运输问题的数学模型可以表示为： 当销大于产时，即 该运输问题的数学模型可以表示为： 4.1 转运问题 转运问题是更实际的一类问题，它是运输问题的一个扩充，其特点是所调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。转运问题的求解通常是设法将其转化为一个等价的产销平衡运输问题，然后用表上作业法求最优调度方案。 4.2 指派问题 在实际工作中经常会遇到这样的问题：有n项不同的任务，需要m个人分别完成一项，但由于任务的性质和个人的专长不同，因此各人去完成不同人物的效率（或花费时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最少）。这类问题成为指派问题或分派问题。 因为工作指派问题的数学模型可以看成是运输规划问题的特殊情况，所以我们可以用求解运输问题的方法来求解指派问题。 4.3 特殊的背包问题 假设每种物品的重量都相等，不妨设为1 ，将背包看成唯一的一个销地，则这种背包问题可转化为销大于产的的运输问题。此时，我们可以转化为平衡运输问题来求解。 4.4 最小费用流问题 在容量网络中，每条弧除了容量限制以外尚有费用指标，它表示单位流量在该弧段通过时所需要的费用。如果有一个指定的流量F从s出发到t，如何安排流量分配使总费用最小。该问题一般可变化为最小费用流模型，用网络流法求解。由分析可知，这也是线性规划中典型运输问题。 下面我们用上述方法求解一道与日常生活相关的运输问题 有甲、乙、丙三个工厂，每年需要煤炭51kt、40kt、