6-1运输问题模型及表上作业法.pptVIP

典型背景——单一物资运输调度问题 设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 。 求总运费最小的调度方案。 运输问题数学模型的特点 运输问题有有限最优解 表上作业法是单纯形法在求解运输问题的一种简便方法。 单纯形法与表上作业法的关系： （1）找出初始基可行解 （2）求各非基变量的检验数 （3）判断是否最优解 换基： （4）确定换入变量和换出变量找出新的基可行解。 （5）重复（2）、（3）直至求出最优解。 举例说明表上作业法 例1、某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表： 第一步：确定初始基可行解 ——最小元素法、伏格尔法 最小元素法思路： 从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。? 第二步：解的最优性检验 第三步：解的调整 思考： 讨论内容： 初始调运方案（初始基可行解） ——沃格尔法 ——西北角法 解的最优性检验——对偶变量法（或称位势法） *运输问题——表上作业法 * 第一节 运输问题 及其数学模型 运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶变量与原问题检验数的关系。 决策变量 表示由 到 的物品数量。 销地 产地 销量 产量 产销平衡问题——总产量=总销量 即 产销不平衡问题——总产量=总销量 产销平衡问题的数学模型 第二节 运输问题的 表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。 计算表中空格检验数 表上给出m+n-1个数字格 判断方法相同 表上调整（闭回路调整） （运输问题必有最优解） 停止 最优解 ？ 是 否 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 最小元素法举例 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 2 0 10 10 0 6 14 8 6 8 0 0 0 0 6 0 最小元素法举例 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 闭回路法 思路：计算空格（非基变量）的检验数 若令 则 如何求检验数？ 分析： ——运费的增量 即 增加1个单位 的检验数=相应的运费增量 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 从初始表分析： 要保证产销平衡，则 称为闭回路 +1 -1 +1 -1 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 2 1 检验数表 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 2 1 1 -1 10 12 表中的解不是最优解。 调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 -1 （-2） （-2） （+2） （+2） 调整后的解为： 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 12 14 4 8 2 2 0 9 1 12 此时的解为最优解。 有无穷多最优解 当供应量和需求量为整数时，最优解为整数？ 产销不平衡？ 是！这是很好的性质。 供不应求，添加虚拟产地； 供过于求，添加虚拟销地。 还有其它的方法吗 ？ 根据第一节运输问题对偶问题与原问题的检验数的关系 *运输问题——表上作业法 * * * *