中国矿业大学：《运筹学》课程教学课件（讲稿）Chapter 3 运输规划（Transportation Problem）

运筹学Chapter3运输规划(Transportation Problem)本章主要内容：运输规划问题的数学模型表上作业法不平衡的运输问题运输问题的应用-1-￥China University of Mining and Technology

-1- China University of Mining and Technology 运 筹 学 Chapter3 运输规划 ( Transportation Problem ) 运输规划问题的数学模型 表上作业法 不平衡的运输问题 运输问题的应用 本章主要内容：

运筹学学习要点：1.掌握运输问题的数学模型及其系数矩阵的特殊结构。2.掌握表上作业法及其在产销平衡问题求解中的应用。3.掌握产销不平衡运输问题的求解方法。4.了解应用LINGO求解运输问题的方法。-2-米China University of Mining and Technology

-2- China University of Mining and Technology 运 筹 学 学习要点： 1. 掌握运输问题的数学模型及其系数矩阵的特殊 结构。 2. 掌握表上作业法及其在产销平衡问题求解中的 应用。 3. 掌握产销不平衡运输问题的求解方法。 4. 了解应用LINGO求解运输问题的方法

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

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

运筹学3. 1运输问题的数学模型4-?China University of Mining and Technology

-4- China University of Mining and Technology 运 筹 学 3.1 运输问题的数学模型

运筹学运输问题的数学模型一、运输问题的数学模型某公司从三个产地A1，A2，A,将物品运往四个销地B，引例1B2，B3，B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3B4产量927910Al1325A2X8257A3438销量64-5-X下页后退退出主页上一页China University of Mining and Technology

-5- China University of Mining and Technology 运 筹 学 一、运输问题的数学模型 某公司从三个产地A1，A2，A3将物品运往四个销地B1， B2，B3，B4， 各产地的产量、各销地的销量和各产 地运往各销地每件物品的运费如下表所示，问：应如 何调运可使总运输费用最小？ B1 B2 B3 B4 产量 A1 2 9 10 7 9 A2 1 3 4 2 5 A3 8 4 2 5 7 销量 3 8 4 6 引例1 运输问题的数学模型

运筹学运输问题的数学模型解：本问题是产销平衡的，即总产量等于总销量：9+5+7=3+8+4+6=21令xi表示从A到B，的调运量BiB2B3B4产量9A1X11X12X13X145A2X21X22X23X247A3X33X31X32X343864销量BiB2B4B3产量279109A113254A282574A33684销量-6-王下页后退退主页上页出China University of Mining and Technology

-6- China University of Mining and Technology 运 筹 学 解：本问题是产销平衡的，即总产量等于总销量： 9+5+7=3+8+4+6=21 令x i j 表示从A i到B j 的调运量， B1 B2 B3 B4 产量 A1 x11 x12 x13 x14 9 A2 x21 x22 x23 x24 5 A3 x31 x32 x33 x34 7 销量 3 8 4 6 运输问题的数学模型 B1 B2 B3 B4 产量 A1 2 9 10 7 9 A2 1 3 4 2 5 A3 8 4 2 5 7 销量 3 8 4 6

运筹学运输问题的数学模型min z = 2xu + 9x12 +10xi3 + 7x14 + X21 + 3x22 + 4x232X24 +8X31 + 4X32 + 2X33 + 5X34X11 + X12 + Xi3 + X14 = 9X21 + X22 +X23 + X24 = 5X31 + X32 + X33 + X34 = 7Xi11 +X21 + X31 = 3X12 +X22 + X32 = 8Xi3 + X23 + X33 = 4X14 + X24 + X34 = 6X, ≥0 i=1,2,3; j=1,2,3,49.X主页上一页5银China University of Mining and Technology

-9- China University of Mining and Technology 运 筹 学 运输问题的数学模型                                                    0 1,2,3; 1,2,3,4 6 4 8 3 7 5 9 2 8 4 2 5 min 2 9 10 7 3 4 1 4 2 4 3 4 1 3 2 3 3 3 1 2 2 2 3 2 1 1 2 1 3 1 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 2 4 3 1 3 2 3 3 3 4 1 1 1 2 1 3 1 4 2 1 2 2 2 3 x i j x x x x x x x x x x x x x x x x x x x x x x x x x x x x x z x x x x x x x i j

运筹学运输问题的数学模型ZZ运输问题一般表述：minz=CjXiji=1 j=1""i=1,.,mXi, =a;s.tj=b,j=l,.,nXij≥ 0,i=1,...,m;j=l,...,nXijBiB2Bn产量AAa)C11C12CinanC21C22Can.....A(mCmlCmnCm2mb2Za,-Ebbibn销量-10-?后退退出主页上一页下一页China University of Mining and Technology

-10- China University of Mining and Technology 运 筹 学 运输问题一般表述： 设某种物资有m个产地 A1 ,A2 ,.,Am , 生产量分别为a1，a2,.,am ; n个销地 B1 ,B2 ,.,Bn，销售量分别为b1 ,b2 ,., bn ; cij 表示 i 地往 j 地的单位运价。 在产销平衡条件下，求总运费最小的调运方案。 运输问题的数学模型 销量 b1 b2 . bn Am cm1 cm2 . cmn am . . . . . . a2 c . 2n c22 c A2 21 a1 c . 1n c12 c A1 11 B1 B2 . Bn 产量    j i a b

运筹学运输问题的数学模型变化：1) 有时目标函数求最大。如求利润最大或营业额最大等2)当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束）：3）产销不平衡时，可加入假想的产地或销地(销大于产时)(产大于销时）ZZminzCijXij=BiB2B.产量...i=l j=1AaC1lC12Cini=1,.,m=aiXijA2C21a2C22Cans.tXi, =b,j=1,,nCmlCm2a...m1i=l销量bib2bnX, ≥0,i=1,...,m;j=l,...,n-11-页主页一页后退退出NChina University of Mining and Technology

-11- China University of Mining and Technology 运 筹 学 变化： 1）有时目标函数求最大。如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，在模型中直接加入约 束条件（等式或不等式约束)； 3）产销不平衡时，可加入假想的产地（销大于产时）或销地 （产大于销时）。 销量 b1 b2 . bn Am cm1 cm2 . cmn am . . . . . . a2 c . 2n c22 c A2 21 a1 c . 1n c12 c A1 11 B1 B2 . Bn 产量 运输问题的数学模型

运筹学运输问题的数学模型m二运输问题数学模型的特点Z=b=aiXii-1-约束方程的增广矩阵xXm2XmlXinX21Xo..X22...XmnaazD=ambb,b,-12-米退出主页贝1K广China University of Mining and Technology

-12- China University of Mining and Technology 运 筹 学 11 12 21 22 1 2 1 2 1 2 1 2 . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 n n m m mn m n x x x x x x x x x a a D a b b b        约束方程的增广矩阵 二、运输问题数学模型的特点 运输问题的数学模型 j m i ij n j xij  ai x  b 1 1