运筹学运输问题PPT课件

1 运筹学 OperationsResearch 上海海事大学 20131009 任课教师 邓伟 邮箱 dengwei1663 2 运输问题 例8 1某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 3 运输问题 解 产销平衡问题 总产量 总销量设xij为从产地Ai运往销地Bj的运输量 建立如下的模型 Minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 4 运输问题 一般运输模型 产销平衡问题 A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物质的n个销地 ai表示产地Ai的产量 bj表示销地Bj的销量 cij表示把物资从产地Ai运往销地Bj的单位运价 设xij为从产地Ai运往销地Bj的运输量 得到一般运输量问题的模型 5 运输问题 运输表 6 运输问题 注 1 有时目标函数求最大 如求利润最大或营业额最大等 2 当某些运输线路上的能力有限制时 在模型中直接加入约束条件 等式或不等式约束 3 产销不平衡时 可加入假想的产地 销大于产时 或销地 产大于销时 7 运输问题 运输问题是一类特殊的线性规划问题 具有如下性质 1 运输问题的模型中包含mn个变量 m n个约束方程 且在约束系数中各变量的系数或者是1或者是0 变量为双下标变量 2 运输问题的基本可行解中基变量的个数为m n 1个 此矩阵的秩为4 2 3 1 m n 1 而不是m n 而基变量的个数与秩数相等 8 运输问题 定义 闭回路从运输表的某个格子出发 沿水平或垂直方向前进 在另一个格子处转90度 继续前进 重复此过程 直到回到出发时的格子 由此形成一条封闭的折线 称为闭回路 转角处的格子称为闭回路的顶点 9 运输问题 3 以运输问题的基本可行解的m n 1个基变量为顶点 不会形成闭回路 4 运输问题的一个可行解中 如果非零分量的个数为m n 1个 并且以这些非零分量为顶点 不会形成闭回路 5 在运输问题的一个可行解中 如果非零分量的个数为m n 1个 并且以这些非零分量为顶点不会形成闭回路 则这个解为一个基本可行解 6 若所有ai bj皆为整数 则基本可行解的各分量值也为整数 10 表上作业法 表上作业法时单纯形法在求解运输问题时的一种简化方法 其实质是单纯形法 但具体计算和术语有所不同 表上作业法的求解过程包含3个阶段 确定初始基本可行解 进行最优性检验 以决定继续求解还是停止 迭代求解新的基本可行解 此方法要求模型是产销平衡的 11 表上作业法 例8 2某食品公司下属A1 A2 A3三个食品厂生产食品 3个厂每个月的生产能力分别为7吨 4吨 9吨 食品运送到B1 B2 B3 B4四个销售点 它们对于食品的月需求量分别为3吨 6吨 5吨 6吨 试制定最优运送方案 解这是一个产销平衡的运输问题 12 表上作业法 1 确定初始的基本可行解 由于运输问题的特殊性 在找初始基本可行解时 不用引入人工变量 可以直接在表上给出基本可行解 将所有cij写在格子的左上角 将每个基变量的数值填在表中相应格子的右下角 右下角没有填数字的格子 空格对应非基变量 1 西北角法从西北角的格子开始填数 给x11尽可能大的值 令x11 min a1 b1 min 7 3 3由于销售点B1已满足要求 故不再向B1运送食品 即表中第1列中其他变量x21 x31皆为非基变量 即为空格 13 表上作业法 将已满足要求的列称为饱和列 将饱和列 第1列 划掉 再对于剩下的西北角的格子中填尽可能大的数 逐渐划去饱和行 列 除最后一个格子外 每划掉一条线对应一个饱和行 列 最后一个格子同时使行和列饱和 因此最后一个格子划掉两条线 14 表上作业法 2 最小元素法从运价取最小值的格子开始 在这个格子中填尽可能大的数 划去饱和行 列 在剩下的格子中选取运价取最小值的格子 对其赋值 依次划去饱和行 列 15 表上作业法 比较一下上面两种方法初始基本可行解所对应的目标函数值 西北角法 f1 135最小元素法 f2 86 由此可以看出 采用最小元素法 更接近最优目标函数值 收敛速度更快 注 在应用西北角或最小元素法时 应遵循 除最后一个元素外 填一个数只划掉一行 或一列 当填一个数后 如果所在行和列同时饱和 也只划掉一行 或一列 只是接着填下一个数时 要在没划掉的饱和行 饱和列 上的某个没划过的空格子中 填上一个数字0之后 再划去该行 该列 16 表上作业法 这个0不同于其他空格 表明该变量为基变量 是起占位子作用的 表明当前基本可行解是退化的 某个基变量取值为0 其占位子是为了保证基变量的个数为m n 1个 如下例所示 可以证明 用西北角法或最小元素法得到的解确为基本可行解 只需证明填数字的格子为m n 1个 并且这m n 1个格子不构成闭回路即可 可由反证法证明 17 表上作业法 3 Vogel法最小元素法的缺点是 为了节省一处的费用 有时造成其他处要花费更多的运费 Vogel法考虑到 如果一产地的产品加入不能按最小运费就近供应 就考虑减少运费 这就有一个差额 差额越大 说明不能按最小运费调运时 运费增加越多 因此 对差额最大处 就应当采用最小费用调运 18 表上作业法 第一步 计算各行和各列的最小运费和次最小运费的差额 并填入该表的最右列和最下行 19 表上作业法 第二步 从行或列差额中选出最大者 选择它所在行或列中的最小元素 在上表中B2列是最大差额所在列 B2列中最小元素为4 可确定A3的产品先供应B2的需要 如下表所示 同时将运价表中的B2列数字划去 20 表上作业法 第三步 对上表中未划去的元素再分别计算出各行 各列的最小运费和次最小运费的差额 并填入该表中的最右列和最下行 重复第一 二步 直到给出初始解为止 用此法给出初始解如下表所示 21 表上作业法 从以上可以看到 Vogel法同最小元素法除去在确定供求关系的原则上不同外 其余步骤相同 Vogel法给出的初始解比用最小元素法给出的初始解更接近最优解 西北角法 f1 135最小元素法 f2 86Vogel法 f3 85 22 表上作业法 2 最优解的判别 1 位势 由于运输问题的目标函数为求极小 所以当全部检验数小于等于零时 对应的解为最优解 满足方程的解称为基本可行解对应的位势 其中为基变量对应的单价 显然 上面的位势方程中包含m n 1个方程 m n个变量 因此有1个变量为自由未知量 故位势不是唯一的 23 表上作业法 2 利用位势求检验数 最优性条件为 当检验数时 当前解为最优解 例8 3对于上面给出的初始基可行解 计算解对应的检验数 将检验数和位势添加到运输表中 称为扩充的运输表 24 表上作业法 其中 扩充的运输表中的每个格子形式如下 基变量格 非基变量格 25 表上作业法 在表格中 第2行第4列的检验数为 1 因此当前解不满足最优性条件 需要继续迭代 26 表上作业法 3 迭代求新的基本可行解 1 选出负检验数中的最小者 确定为进基变量 2 在运输表上找一条包含为顶点的闭回路 这条闭回路上的其他顶点皆为基变量 格 在此闭回路上以作为第一个顶点 沿一个方向对其他顶点有一次顺序标号 这样 闭回路上的顶点格被分为奇点格和偶点格 3 计算确定xpq为出基变量 所在格子调整为空格 4 在闭回路上各个奇点变量值均加上 各个偶点格均减去 而不在闭回路上的各个变量值不变 这样便完成了一次迭代 27 表上作业法 在上面的扩充的运输表中 故取x24进基 找一条包含x24在内的闭回路 其中除了x24外 其余格子均取基变量格子 28 表上作业法 迭代后的表格为 表中各检验数已大于零 因此当前解为最优解 最优目标函数值为f 85 注 若某个非基变量的检验数 空格 为0 则该问题有无穷多个最优解 29 表上作业法 产销不平衡的运输问题 在上面的运输问题模型中 均假设 即产销平衡的运输问题 实际上 在现实问题中往往存在供大于求或者供小于求的情况出现 为了仍然能用表上作业法求解 需要将它们转化为产销平衡的运输问题 30 表上作业法 产销不平衡的运输问题 当供大于求时 引入一个虚设的销售地 并假设它的销售量为 实际上这个差值是在产地储存的 当供小于求时 引入一个虚设的产地 并假设它的生产量为 实际上这个差值是不能满足的 由于虚设的产地是不存在的 所以从这个虚设的产地到各个销售地的运费为零 类似的 从各个产地到一个虚设的销售地的运价也为零 31 表上作业法 例8 4今有2个化肥厂供应3个地区B1 B2 B3的化肥 运输表如下 试决定运费最小的调运方案 32 表上作业法 解引入虚拟的