山东大学 运筹学课件及课后解答3第三章 运输问题(新)a.ppt

《山东大学 运筹学课件及课后解答3第三章 运输问题(新)a.ppt》由会员分享，可在线阅读，更多相关《山东大学 运筹学课件及课后解答3第三章 运输问题(新)a.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作业：作业：P99100 3.1 表表3-35 3.2 3.3第三章第三章 运输问题运输问题 第一节第一节 运输问题的数学模型运输问题的数学模型有某种物资需要调运，已知有有某种物资需要调运，已知有m个产地（产地个产地（产地用用Ai表示，表示，i=1，2，m)供应该种物资，产地供应该种物资，产地Ai的产量为的产量为ai；有；有n个销地（销地用个销地（销地用Bj表示，表示，j=1，2，n)需要该种物资，销地需要该种物资，销地Bj的销量为的销量为bj，从第从第i个个产地到第产地到第j个销地的单位物资运价为个销地的单位物资运价为cij，要求：制定要求：制定一个调运方案，在满足供需关系的条件下，使总运一

2、个调运方案，在满足供需关系的条件下，使总运费最少。费最少。（上述资料见下面的产销平衡表和单位运价表，（上述资料见下面的产销平衡表和单位运价表，也可将两表合并起来，见后）也可将两表合并起来，见后）解：设为解：设为xij表示从产地为表示从产地为Ai给销地为给销地为Bj的运输量。的运输量。则有则有运输问题的系数矩阵 下面先讨论产销平衡的运输问题的解法，下面先讨论产销平衡的运输问题的解法，对产销不平衡的运输问题，只需化为产销平衡对产销不平衡的运输问题，只需化为产销平衡问题，即可求解。问题，即可求解。产销平衡运输问题数学模型的特征：产销平衡运输问题数学模型的特征：1.产地：产地：m个；个；2.销地：销地

3、：n个；个；3.变量：变量：mn个；个；4.约束条件：约束条件：m+n个；个；5.约束矩阵具有：分布稀疏性，排列规律性，约束矩阵具有：分布稀疏性，排列规律性，数据单一性（数据单一性（0或或1）；）；6.约束矩阵的秩：约束矩阵的秩：r=m+n1;7.基变量个数：基变量个数：m+n1；8.非基变量个数：非基变量个数：mn(m+n1)。定理定理1.1.运输问题的数学模型必有最优解。定理定理2.2.若运输问题中产量和销量皆为整数，则必有整数最优解。第二节第二节 求解运输问题的表上作业法求解运输问题的表上作业法表上作业法的步骤：表上作业法的步骤：1.1.将运输问题化为产销平衡的问题将运输问题化为产销平衡

4、的问题（供过于求：增加假设销地；供不应求，增加假设（供过于求：增加假设销地；供不应求，增加假设产地）；产地）；2.2.确定初始调运方案（最小元素法，西北角法，确定初始调运方案（最小元素法，西北角法，vogelvogel法）；法）；3.3.最优性检验（闭回路法，位势法）；若所有非基最优性检验（闭回路法，位势法）；若所有非基变量的检验数都有变量的检验数都有ijij 0 0，则得最优方案，结束则得最优方案，结束计算。否则，转计算。否则，转4 4；4.4.调整方案（闭回路法），转调整方案（闭回路法），转3 3。例例1.已知运输问题见表已知运输问题见表销销地地产产地地B1B2B3B4产产量量A1A2A3

5、311310192874105749销销量量3656202-1 2-1 初始方案的确定初始方案的确定1.1.最小元素法（就近供应的思想）最小元素法（就近供应的思想）在单位运价表中的最小运价处确定供销关系，在单位运价表中的最小运价处确定供销关系，划去满足的行或列，以此类推，直至给出一个完划去满足的行或列，以此类推，直至给出一个完整的调运方案。整的调运方案。初始调运方案见下，总运费为初始调运方案见下，总运费为z=86z=86销销地地产产地地B1B2B3B4产产量量A1A2A3433163749销销量量365620特殊情况：若运价表为特殊情况：若运价表为:销销地地产产地地B1B2B3B4产产量量A1

6、A2A331131791812105749销销量量365620销销地地产产地地B1B2B3B4产产量量A1A2A3016433749销销量量365620在未被划掉的运价对应的空格处补在未被划掉的运价对应的空格处补0，然后划掉，然后划掉该行和该列。该行和该列。2.2.西北角法西北角法 在单位运价表中的左上角（西北角）处确定供销在单位运价表中的左上角（西北角）处确定供销关系，划去满足的行或列，以此类推，直至给出一个关系，划去满足的行或列，以此类推，直至给出一个完整的调运方案。完整的调运方案。对例对例1 1，已知单位运价表为，已知单位运价表为销销地地产产地地B1B2B3B4产产量量A1A2A3311

7、310192874105749销销量量365620初始调运方案见下，总运费为初始调运方案见下，总运费为z=111z=111销销地地产产地地B1B2B3B4产产量量A1A2A3342236749销销量量3656203.vogel3.vogel法法 从运价表上分别找出每行与每列的最小的从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量，划去运价最小运价确定供需关系和供需数量，划去运价表中对应的行或列，然后重复上述步骤。表中对应的行或列，然后重复上述步骤。销销地地产产地地B1B2B3B4产产量量A1A2A

8、3523163749销销量量365620初始调运方案为见下，总运费为初始调运方案为见下，总运费为z=85z=852-2 2-2 最优性检验最优性检验 1.1.进行最优性检验的闭回路法进行最优性检验的闭回路法 闭回路：在调运方案中，从一个空格处出闭回路：在调运方案中，从一个空格处出发，以有数字格为顶点（或拐点），沿水平或发，以有数字格为顶点（或拐点），沿水平或垂直连线又回到空格处所形成的封闭回路。垂直连线又回到空格处所形成的封闭回路。定理定理3.3.对调运方案中的任一个空格，有且仅有对调运方案中的任一个空格，有且仅有一个以有数字格为顶点的闭回路。一个以有数字格为顶点的闭回路。推论：运输问题中推论

9、：运输问题中n+m-1n+m-1个变量能构成基变量的充个变量能构成基变量的充要条件是他们不构成闭回路。要条件是他们不构成闭回路。通过闭回路计算空格处的检验数通过闭回路计算空格处的检验数ijij，若，若ijij00（因为是求因为是求min z)min z)，则得最优调运方案，则得最优调运方案，否则，转否则，转2-32-3。这里定义：闭回路上空格顶点的编号为这里定义：闭回路上空格顶点的编号为0，其余按其余按1，2，3.类推。类推。闭回路的可能形状：闭回路的可能形状：11=c11-c13+c23-c21=3-3+2-1=131=7-1+2-3+10-5=10.2-3 2-3 调整方案，然后转调整方案

10、，然后转2-22-2令调整量令调整量=闭回路上奇数顶点的最小运量。闭回路上奇数顶点的最小运量。调整方法：闭回路上偶数顶点运量调整方法：闭回路上偶数顶点运量 +闭回路上奇数顶点运量闭回路上奇数顶点运量 -因所有检验数因所有检验数ijij 0 0，故得最优方案。故得最优方案。MinzMinz=85=85作业作业 P99 3.1 P99 3.1 表表3-363-36（位势法）（位势法）P101 3.4 3.5P101 3.4 3.52.2.进行最优性检验的位势法进行最优性检验的位势法 运输问题的对偶问题数学模型为运输问题的对偶问题数学模型为对约束条件加松弛变量，得对约束条件加松弛变量，得 已知运输问

11、题的基变量有已知运输问题的基变量有m+n-1m+n-1个，因此，上个，因此，上式是一个具有式是一个具有m+nm+n个变量，个变量，m+n-1m+n-1个等式的方程组，个等式的方程组，由于变量数多于方程数，故有无穷多解。由于变量数多于方程数，故有无穷多解。对以上问题，可先选定任意一个变量的取值，对以上问题，可先选定任意一个变量的取值，然后就可计算出其它变量的值。然后就可计算出其它变量的值。(变量变量u ui i也称为行位也称为行位势，势，v vj j称为列位势。称为列位势。)有了有了u ui i和和v vj j，就，就可计算非基变可计算非基变量的检验数量的检验数 ijij=c cijij (u

12、ui i+v+vj j)。对例对例1 1，可先令，可先令v v1 1=1=1，根据根据c cijij 就可求出其它的就可求出其它的u ui i，v vj j ，从而可计算出检验数。从而可计算出检验数。销销地地产产地地B1B2B3B4产量产量A1A2A3311310192874105749销销量量365620例例 ：求解下列运输问题：求解下列运输问题销销地地产产地地B1B2B3B4B5产产量量A1A2A3101520204020401530303035405525506090销销量量2535601070200销销地地产产地地B1B2B3B4B5产产量量A1A2A32525600101070506

13、090销销量量2535601070200解解:初始方案初始方案销销地地产产地地B1B2B3B4B5uiA1A2A31015(0)(-15)(35)(15)(30)1530(30)(0)35(0)55250-520vj101520355检验表检验表销销地地产产地地B1B2B3B4B5产产量量A1A2A32525600101070506090销销量量2535601070200一次调整后方案一次调整后方案销销地地产产地地B1B2B3B4B5产产量量A1A2A32515106002070506090销销量量2535601070200检验表销销地地产产地地B1B2B3B4B5uiA1A2A31015(1

14、5)20(35)(0)(15)1530(15)(0)35(15)(15)2501020vj10155205因所有检验数都大于等于零因所有检验数都大于等于零,故得最优方案。故得最优方案。minzminz=4025=4025。2-4 表上作业法总结表上作业法总结1.总结总结2.求最大值问题求最大值问题例：求解下列运输问题例：求解下列运输问题销销地地产产地地B1B2B3B4产产量量A1A2A3376424324385523销销量量323210第三节第三节 产销不平衡的运输问题及应用产销不平衡的运输问题及应用此时，可增加一个销量为供求差额的假设销地，此时，可增加一个销量为供求差额的假设销地，从而化为产

15、销平衡问题。可用表表示如下。从而化为产销平衡问题。可用表表示如下。1.1.当供过于求时，运输问题的数学模型可写成当供过于求时，运输问题的数学模型可写成下式，加松弛变量化为标准形式下式，加松弛变量化为标准形式 销销地地产产地地B1B2BnBn+1产产量量A1A2.Amc11c12c1nc1,n+1c21c22c2nc2,n+1.cm1cm2cmncm,n+1a1a2.am销销量量b1b2bnbn+12.2.当供不应求时，运输问题的数学模型可写成下当供不应求时，运输问题的数学模型可写成下式，加松弛变量化为标准形式式，加松弛变量化为标准形式此时，可增加一个产量为供求差额的假设产地，此时，可增加一个产

16、量为供求差额的假设产地，从而化为产销平衡问题。可用表表示如下。从而化为产销平衡问题。可用表表示如下。销销地地产产地地B1B2Bn产产量量A1A2.AmAm+1c11c12c1nc21c22c2n.cm1cm2cmncm+1,1cm+1,2cm+1,na1a2.amam+1销销量量b1b2bn作业作业 P103 3.7 3.8(a)P103 3.7 3.8(a)例例2.2.已知见表：试决定总运费最少的调运方案。已知见表：试决定总运费最少的调运方案。销销地地产产地地B1B2B3B4产产量量A1A2A321134103597812757销销量量23461915解：这是一个产大于销的运输问题，先将其化

17、为解：这是一个产大于销的运输问题，先将其化为产销平衡问题，然后求解。产销平衡问题，然后求解。最优方案见下表，最小运费为最优方案见下表，最小运费为 min z=35min z=35 销销地地产产地地B1B2B3B4库存库存产产量量A1A2A32323243757销销量量2346419销销地地产产地地B1B2B3B4库存库存产产量量A1A2A321134010359078120757销销量量2346419例例3.3.已知见表，试决定使总运费最省的化肥调已知见表，试决定使总运费最省的化肥调运方案。运方案。解：这是一个产销不平衡的运输问题，将其处理解：这是一个产销不平衡的运输问题，将其处理后可得如下的

18、产销平衡表和单价表。后可得如下的产销平衡表和单价表。最优调运方案见下表，最小运费为最优调运方案见下表，最小运费为min z=2460需求地区需求地区化肥厂化肥厂产产量量ABCD1616132217171414131915151519192023MMM0M0M050605050销销量量302070301050210需求地区需求地区化肥厂化肥厂产产量量ABCD5020103030200302050605050销销量量302070301050210例例4.转运问题转运问题表上作业法与单纯形法表上作业法与单纯形法1.确定初始基本可行解确定初始基本可行解2.最优性检验最优性检验3.确定换入变量确定换入变量4.确定换出变量确定换出变量