《运筹学教学资料》运筹学第3章第1节.ppt

《《运筹学教学资料》运筹学第3章第1节.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第3章第1节.ppt（16页珍藏版）》请在三一办公上搜索。

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成立,对于A1成立,满足产销平衡要求的调运方案要

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

4、在模型中直接加入约束条件（等式或不等式约束)；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表示约束方程组的系数矩阵，它可从D去掉最后一列得出。,约束矩阵的列向量：,第m+j行,第i行,用Pij表示A的对应于xij的列向量,显然：,=,运输问题的数学模型,