[工学]运筹学之运输问题.pptVIP

第三章 运 输 问 题 §1　运输问题及其数学模型 §2　运输问题的表上作业法 §3　产销不平衡问题及其求解 §1　运输问题及其数学模型 运输问题的例子 例3-1 某发电集团设有三个储煤仓库 ， ， 供应其下属四个发电厂 ， ， ， 。三个储煤仓库每月可供应煤炭量，四个发电厂每月需用煤炭以及各储煤仓库运送煤炭到各发电厂的单位运价见表，问在满足发电需要的情况下如何调运才能使总运费最低。 解析：设 表示从产地 到销地 的运量，其目标函数和约束条件可表达为： 产销平衡的运输问题的数学模型及其特点 1. 每个约束条件都是等式 2. 各产地产量之和等于各 销地销量之和，即 3. 模型最多有 个 独立约束方程，最多有 个基可行解 第二节 表上作业法 确定初始调运方案（西北角法:优先满足西北角的供需要求） 1、西北角空格（ ）填20，满足销地 ，划去 列。 2、西北角（ ）填30，满足销地 ，划去 列。 3、西北角（ ）填10 ，产地 销完，划去 行。 4、当西北角空格都被横竖线覆盖，最终得到初始调运方案 ，其余 为零． Z＝20×60＋30×76＋10×80＋30×68＋5×80＋45×56＝9240。 最优解的检验（位势法） 1、计算位势值。原表增加一列一行， 为 位势值 ， 为 位势值．可以证明，单元格（ ）的检验数 填有数字的格对应基变量，其检验数为零，可求出 和 2、计算检验数。各没有填数字的格的检验数。 解的改进（检验数存在负数，调运方案不是最优解，用闭回路法改进 ） 1、选取绝对值最大负数 所在空格作闭回路，并对闭回路顶点顺序编号 2、以 = {偶数顶点的运量}，作为调整量，所有奇数顶点的运量加 ，偶数顶点运量减 ．Z= 8820 3、计算调整后各空格的检验数，若均非负，则已经得到最优解，否则继续用闭回路法调整。 各空格检验数如下，以绝对值最大的负数 所在空格作闭回路。并对闭回路顶点编号 最优方案： 其余 Z＝15×60＋40×80＋5×90＋5×45＋30×50＋45×56＝8795。 四、表上作业法计算中的问题 1、无穷多最优解。 在进行最优解检验时，若某空格检验数为零，则该运输问题有无穷多最优解． 2、退化问题。 在确定初始调运方案时，当在某空格填入一个运量后，出现对应的产地的产量和销地的销量同时得到满足，从而要同时划去该行和列；或者在用闭回路法进行解的改进时，具有偶数编号的顶点调整后有多于一个数字格变为空格，以上两种情况的出现称为退化．解决退化问题的一般方法是：第一种情况下，可在同时化去的行或列的某空格处填入一个0，代表0数字格，为了减少后续的迭代求解次数，填入0时，可选择该行或列中具有最小运价的空格处填入0；第二种情况下，取该闭回路上某偶数顶点为0数字格，得到退化解，在下一步调整运量时，对于0数字格出现在偶数顶点的闭回路，θ取零． §3　产销不平衡的运输问题及其求解方法 产大于销，增加一个虚销地 ，化为产销平衡的运输问题。 当 时，运输问题的数学模型为： 虚销地的销量为产大于销的部分，即 。从 任一产地到虚销地的单位