运筹学教学资料运筹学第3章第1节2014

1、Chapter3 运输规划( Transportation Problem ),运输规划问题的数学模型 表上作业法 不平衡的运输问题 运输问题的应用,本章主要内容：,学习要点： 1. 掌握运输问题的数学模型及其系数矩阵的特殊 结构。 2. 掌握表上作业法及其在产销平衡问题求解中的 应用。 3. 掌握产销不平衡运输问题的求解方法。 4. 了解应用LINGO求解运输问题的方法。,运输问题(The Transportation Problem, TP)是一类特殊而且极其典型的线性规划问题。,运输问题可用单纯形法来求解。由于运输问题数学模型具有特殊的结构，存在一种更简便的计算方法。 表上作业法实质仍是

2、单纯形法。 从运输问题的解决及表上作业法的理论解释，我们可更充分体会到单纯形法的魅力。,3.1 运输问题的数学模型,一、运输问题的数学模型,某公司从三个产地A1，A2，A3将物品运往四个销地B1， B2，B3，B4， 各产地的产量、各销地的销量和各产 地运往各销地每件物品的运费如下表所示，问：应如 何调运可使总运输费用最小？,引例1,运输问题的数学模型,解：本问题是产销平衡的，即总产量等于总销量： 9+5+7=3+8+4+6=21 令x i j 表示从A i到B j 的调运量，,运输问题的数学模型,满足产销平衡要求的调运方案把各个产地的产量都能调运完，保障供给，即,对于A3成立,对于A2成立,

3、对于A1成立,满足产销平衡要求的调运方案要求各个销地的销量都能满足，即,对于B1成立,对于B2 成立,对于B3成立,对于B4成立,运输问题的数学模型,另外从Ai到Bj 运输物资的调运量不能为负，即,调运方案的总费用为,综合上述分析，得到本案例的数学模型,运输问题的数学模型,运输问题的数学模型,运输问题一般表述：,设某种物资有m个产地 A1,A2,Am , 生产量分别为a1，a2,am ; n个销地 B1,B2,Bn，销售量分别为b1,b2, bn ; cij 表示 i 地往 j 地的单位运价。 在产销平衡条件下，求总运费最小的调运方案。,运输问题的数学模型,变化： 1）有时目标函数求最大。如求

4、利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,运输问题的数学模型,二、运输问题数学模型的特点,运输问题的数学模型,特点一：D是一个稀疏矩阵; D中没有写数的地方的数都是0,特点二：D的前m行之和恰好等于后n行之和, 即D的行向量是线性相关的(说明约束方程组含有多余方程 ),运输问题的数学模型,特点三：D中存在一个m+n-1阶的非0子式（事实上， D的m+n-1阶非0子式可由D的m+n-1行与所对应的列（共m+n-1 列）的交叉 元素构成）,特点四：D的秩是m+n-1 结论：约束方程组中有m+n-1个独立的约束方程,运输问题的数学模型,运输模型中共有m+n个方程， 运输模型中共有mn个决策变量； 约束方程组含有一个多余方程，即前m方程之和等于后n方程之和； 运输问题的每个基可行解中有m+n-1个基变量。,运输模型的特点：,运输问题的数学模型,设A表示约束方程组的系数矩