第一节 运输问题及其数学模型.pptVIP

第一节 运输问题 及其数学模型 运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性。 典型背景——单一物资运输调度问题 设某种物品有: m个产地： 产量： n个销地： 销量： 从产地 到销地 的单位运价是 , 求总运费最小的调度方案。 运输问题 决策变量 表示由 到 的物品数量。 运输问题 销地 产地 销量 产量 运输表 产销平衡问题——总产量=总销量 即 产销不平衡问题——总产量=总销量 即 运输问题 运输问题 产销平衡问题的数学模型: 运输问题 m 行 n 行 运输问题的系数矩阵: （1）约束条件系数矩阵的元素等于1或0； （2）约束条件系数矩阵每一列正好有两个非零元素， 从而，每一个变量在前m个约束方程中出现一 次，在后n个约束方程中也出现一次。 对产销平衡运输问题，除上述两个特点外，还有： （3）约束条件均为等式，且产量之和等于销量之 和； （4）约束条件的独立方程最多有m+n-1个，即 运输问题 运输问题数学模型的特点： 运输问题 i j 其中 运输问题的对偶问题——对偶变量与原问题检验数的关系 运输问题 对产销平衡运输问题，若用 分别表示前m个约束等式相应的对偶变量， 用 分别表示后n个约束等式相应的对偶变量，即对偶变量为 运输问题 运输问题的对偶问题可写为: 运输问题的对偶问题——对偶变量与原问题检验数的关系 运输问题 线性规划问题变量 的检验数为 运输问题的对偶问题——对偶变量与原问题检验数的关系 变量 的检验数为 运输问题 设运输问题的一个基可行解的变量为 由于基变量的检验数为零，故有 运输问题的对偶问题——对偶变量与原问题检验数的关系 运输问题 方程组含有m+n-1个方程，m+n个变量 可证明方程组有解，且不唯一。 求出方程组的解（称为位势） 则变量 的检验数为 运输问题的对偶问题——对偶变量与原问题检验数的关系 求运输问题检验数的一种方法 运输问题 第一节 运输问题 及其数学模型