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

Chapter3运输规划

(TransportationProblem)运输规划问题的数学模型表上作业法不平衡的运输问题运输问题的应用本章主要内容：

学习要点：掌握运输问题的数学模型及其系数矩阵的特殊结构。掌握表上作业法及其在产销平衡问题求解中的应用。掌握产销不平衡运输问题的求解方法。了解应用LINGO求解运输问题的方法。

运输问题可用单纯形法来求解。由于运输问题数学模型具有特殊的结构，存在一种更简便的计算方法。表上作业法——实质仍是单纯形法。从运输问题的解决及表上作业法的理论解释，我们可更充分体会到单纯形法的魅力。运输问题(TheTransportationProblem,TP)是一类特殊而且极其典型的线性规划问题。

3.1运输问题的数学模型

一、运输问题的数学模型某公司从三个产地A1，A2，A3将物品运往四个销地B1，B2，B3，B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3B4产量A1291079A213425A384257销量3846运输问题的数学模型

解：本问题是产销平衡的，即总产量等于总销量：运输问题的数学模型解：本问题是产销平衡的，即总产量等于总销量：9+5+7=3+8+4+6=21令xij表示从Ai到Bj的调运量，B1B2B3B4产量A1x11x12x13x149A2x21x22x23x245A3x31x32x33x347销量3846B1B2B3B4产量A1291079A213425A384257销量3846

满足产销平衡要求的调运方案把各个产地的产量都能调运完，保障供给，即1对于A3成立2对于A2成立3对于A1成立4满足产销平衡要求的调运方案要求各个销地的销量都能满足，即5对于B1成立6对于B2成立7对于B3成立8对于B4成立9运输问题的数学模型10

另外从Ai到Bj运输物资的调运量不能为负，即01调运方案的总费用为02综合上述分析，得到本案例的数学模型03运输问题的数学模型

运输问题的数学模型

运输问题的数学模型运输问题一般表述：设某种物资有m个产地A1,A2,…,Am,生产量分别为a1，a2,…,am;n个销地B1,B2,…,Bn，销售量分别为b1,b2,…,bn;cij表示i地往j地的单位运价。在产销平衡条件下，求总运费最小的调运方案。bn…b2b1销量amcmn…cm2cm1Am………………a2c2n…c22c21A2a1c1n…c12c11A1产量Bn…B2B1

运输问题的数学模型变化：1）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。bn…b2b1销量amcmn…cm2cm1Am………………a2c2n…c22c21A2a1c1n…c12c11A1产量Bn…B2B1

运输问题的数学模型二、运输问题数学模型的特点约束方程的增广矩阵

特点一：D是一个稀疏矩阵;D中没有写数的地方的数都是01特点二：D的前m行之和恰好等于后n行之和,即D的行向量是线性相关的(说明约束方程组含有多余方程)2运输问题的数学模型

特点三：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个方程，运输模型中共有m×n个决策变量；约束方程组含有一个多余方程，即前m方程之和等于后n方程之和；运输问题的每个基可行解中有m+n-1个基变量。

01设A表示约束方程组的系数矩阵，它可从D去掉最后一列得出。02约束矩阵的列向量：03第m+j行04第i行05用Pij表示A的对应于xij的列向量,显然：06Ａ=07运输问题的数学模型