运筹学概论 第3章 运输问题.pptVIP

* 第三章 运输问题 运输问题及其数学模型 用表上作业法求解运输问题 运输问题的进一步讨论 某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的产量，各销地的销量以及各工厂到各销地的单位运价示于下表中，要求研究产品如何调运才能使总运费最小？ 第一节 运输问题及其数学模型 解： 设xij表示由第i个产地运往第j个销地的产品数量，数学模型如下： ●有m个产地生产某种物资，有n个地区需要该类物资 ●令a1, a2, …, am表示各产地产量， b1, b2, …, bn表示各销地的销量，?ai=?bj 称为产销平衡 ●设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位运费。 一、运输问题的一般数学模型 bn … b2 b1 需求量 Bn B2 B1 销地 产地 Am A2 A1 am a2 a1 供应量 cmn cm2 cm1 c2n c22 c21 c1n c12 c11 … … … … 如何建立供需搭配，使总的运输费用最小？ 供需平衡表 设从Ai到Bj的物资运量为xij ， 产销平衡运输问题的数学模型： Ai的产品全 部供应出去 Bj的需求全部得到满足 二、运输问题数学模型的特点 1．运输问题有有限最优解 其中 （1） 则(1)就是运输问题的一个可行解；另一方面，运输问题的目标函数有下界，目标函数值不会趋于-∞，由此可知，运输问题必存在有限最优解。 若令变量 2.运输问题约束条件的系数矩阵 系数列向量的结构 m行 n行 产销平衡问题的所有约束条件都是等式约束。 各产地产量之和等于各销地销量之和。 3.运输问题的解 根据运输问题的数学模型求出的运输问题的解 X=(xij)，代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。 运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，再进行解的最优性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直至得到最优解为止。 为了保证运输问题的每步得到的解xij都是基可行解，要求: (1) 解X必须满足模型中的所有约束条件； (2) 基变量对应的约束方程组的系数列向量线性无关； (3) 解中非零变量的个数不能大于(ｍ+ｎ-1)个，原因是运输问题中虽有(m+ｎ)个约束条件，但由于总产量等于总销量，故只有(ｍ+ｎ-1)个结构约束条件是线性独立的； (4) 为使迭代顺利进行，基变量的个数在迭代过程中保持为(ｍ+ｎ-1)个。 平衡表、运价表合二为一 第三章 运输问题 运输问题及其数学模型 用表上作业法求解运输问题 运输问题的进一步讨论 一、计算步骤： (1)按某种规则(最小元素法、西北角法)找出一个初始解（初始调运方案）。即在(m×n)产销平衡表上给出m+n-1个数字格。 (2)对现行解作最优性判别，即求检验数(闭回路法)。如是最优解，则停止计算，否则转到下一步。 (3)对方案进行改善，找出新的调运方案(表上闭回路法调整) 。 (4) 重复(2)、(3)，直到求得最优调运方案。 第二节 用表上作业法求解运输问题 例 1 运输问题供需平衡表和运价表如下，求最优调运方案。 20 6 5 6 3 需求量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 供应量 B4 B3 B2 B1 销地 产地 二、举例 （1） 最小元素法 该方案总运费： Z=4×3+3×10+3×1+1×2+6×4+3×5=86 找出初始调运方案 3 1 4 6 3 3 1 2 4 6 3 5 6 6 2 3 2 4 3 （2） 西北角法 优先满足运输表中西北角(即左上角)上空格的供销需求 该方案总运费： Z=3×3+4×11+2×9+2×2+3×10+6×5=132 2.最优解的判别 （位势法） 标准型运输问题的对偶问题是： 由原问题与对偶问题解的相互关系知，变量xij的检验数为： 3 1 4 6 3 3 位势法 令v1=0, 由c21=1= u2 +v1，得 u2=1 0 1 1 2 0 1 1 2 8 -3 7 位势表 2 9 8 9 -3 -2 检验数 (空格中数字为ui+vj ) 0 1 1 2 8 -3 7 检验数表 1 2 1 -1 10 12 ?24=-1＜0，当前方案 不是最优方案。 3.闭回路调整法改进方案 pq ij j , i ) ( min ? ? = 0 xpq 为换入变量 从(p,