《运筹学 运输问题 (2)精选PPT.ppt》由会员分享，可在线阅读，更多相关《运筹学 运输问题 (2)精选PPT.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学 运输问题第1页，此课件共44页哦 运输问题 运输问题（运输问题（Transportation Problem，简记为，简记为TP）是一类常见而且极其特殊的线性规划问题是一类常见而且极其特殊的线性规划问题.它最早是从它最早是从物资调运工作中提出来的，是物流优化管理的重要的物资调运工作中提出来的，是物流优化管理的重要的内容之一内容之一 。从理论上讲，运输问题也可用单纯形法来求解，从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简便的计算方法种比单纯形法更简便的计算方法 表上作业法表上作业法，
2、用表上作业法来求解运输问题比用单纯形法可节约计用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用算时间与计算费用.但表上作业法的实质仍是单纯形法但表上作业法的实质仍是单纯形法 第2页，此课件共44页哦1 运输问题及其数学模型1 1 运输问题及其数学模型运输问题及其数学模型 设某种物资共有设某种物资共有 m 个产地个产地 A1，A2，Am，各各产地的产量分别是产地的产量分别是a1，a2，am；有有n 个销地个销地 B1，B2，Bn，各销地的销量分别为各销地的销量分别为b1，b2，bn.假定从产地假定从产地Ai（i=1，2，m）向销地向销地Bj（j=1，2，n）运输单位物资的运价是运输
3、单位物资的运价是cij，问怎样调运才能，问怎样调运才能使总运费最小？使总运费最小？一、运输问题的数学模型一、运输问题的数学模型 加速物资流转加速物资流转 降低流通费用降低流通费用 第3页，此课件共44页哦 运输问题 销地销地产地产地 B1 B2 Bn产量产量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am销量销量 b1 b2 bn 运输表运输表1 1、产销平衡问题、产销平衡问题即即 设设 xij 表示产地表示产地 Ai 运往销地运往销地 Bj(i=1,2,m;j=1,2,n)的运量的运量.销地销地产地产地 B1 B2 Bn产量产量 A1 x11c
4、11 x12c21 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am销量销量 b1 b2 bnNote:cij 在左下角在左下角 xij 在右上角在右上角 第4页，此课件共44页哦1 运输问题及其数学模型2 2、产销不平衡问题、产销不平衡问题当当当当第5页，此课件共44页哦 运输问题二、运输问题数学模型的特点二、运输问题数学模型的特点讨论产销平衡问题讨论产销平衡问题定理定理 1 平衡运输平衡运输问题必有可行解，也必有最优解问题必有可行解，也必有最优解.证明证明定理定理 2 平衡运输问题的约束方程系数矩阵平衡运输问题
5、的约束方程系数矩阵 A 和增广矩和增广矩阵阵 的秩相等，且等于的秩相等，且等于 m+n-1.即即 定理定理2 说明：说明：基可行解包含基可行解包含m+n-1个基变量个基变量.定理定理 3 平衡运输问题的约束方程系数矩阵平衡运输问题的约束方程系数矩阵 A 的所有的所有各阶子式只取各阶子式只取 0，1 或或-1 三个值三个值.定理定理 4 如果平衡运输问题中的所有产量如果平衡运输问题中的所有产量 ai 和销量和销量 bj都是整数，那么，它的任一基可行解都是整数解都是整数，那么，它的任一基可行解都是整数解.证明证明note第6页，此课件共44页哦定理定理 1 1 的证明的证明Proof:则取则取显然
6、有显然有 ，又又所以所以 ，是问题的一个可行解，是问题的一个可行解.又因为又因为 ，对于任一可行，对于任一可行解有目标函数值解有目标函数值 ，对于求极小化问题，目标，对于求极小化问题，目标函数函数值有下界，则必有最优解值有下界，则必有最优解.第7页，此课件共44页哦1 运输问题及其数学模型Note:平衡运输问题有平衡运输问题有 个变量，个变量，个约束个约束条件，规模很大。条件，规模很大。Go back第8页，此课件共44页哦定理定理 4 的证明的证明Proof:设设 x 是是 Ax=b 的任一基可行解，的任一基可行解，B 为对应的基矩阵，则为对应的基矩阵，则 其中其中 Bt 是用是用 b 中对
7、应的中对应的 m+n-1元素替换元素替换 B 的第的第t 列列元素得到的矩阵元素得到的矩阵.显然显然，由定理，由定理 3 知，知，det Bt 是个整数，是个整数，det B=，因此，因此，都是整数都是整数.其基变量为其基变量为第9页，此课件共44页哦 运输问题定义定义 1 1（其中（其中 互不相同，互不相同，互不相同）互不相同）形式的变量集合，称为一个闭回路，其中诸变量称为形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点这个闭回路的顶点.B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32
8、 x33 x34 x35 A4 x41 x42 x43 x44 x45如：如：变量集合变量集合变量集合变量集合2、每一行（或列）若有闭回路的顶点，则有两个每一行（或列）若有闭回路的顶点，则有两个顶点；顶点；3、每两个顶点格子的连线都是水平的或垂直的；每两个顶点格子的连线都是水平的或垂直的；4、闭回路中顶点的个数必为偶数闭回路中顶点的个数必为偶数.闭回路的几何特征：闭回路的几何特征：1、每一个顶点格子都是每一个顶点格子都是 90转角点；转角点；凡是能排列成凡是能排列成凡是能排列成凡是能排列成第10页，此课件共44页哦1 运输问题及其数学模型闭回路的代数性质：闭回路的代数性质：性质性质 1 构成闭
9、回路的变量组对应的列向量组构成闭回路的变量组对应的列向量组必线性相关必线性相关.证明证明性质性质 2 分组分组构成闭回路，则该变量组对应的列向量组构成闭回路，则该变量组对应的列向量组是线性相关的是线性相关的.推论推论 1 若变量组对应的列向量组线性无关，则该变若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路量组一定不包含闭回路.若变量组若变量组 中有一个部中有一个部Go on第11页，此课件共44页哦性质性质 1 的证明的证明Proof:由直接计算可知由直接计算可知故该向量组线性相关故该向量组线性相关.第12页，此课件共44页哦 运输问题在变量组在变量组 中，若有某中，若有某一个变量
10、一个变量 xij 是它所在的行（第是它所在的行（第 i 行）或列（第行）或列（第 j 列）列）中出现于中出现于（*）中的唯一变量，则称该变量中的唯一变量，则称该变量 xij 是该变量是该变量组的一个孤立点组的一个孤立点.定义定义 2闭回路的特征闭回路的特征性质性质 3 没有孤立点没有孤立点 若一变量组中不包含任何闭回路，则该变量组若一变量组中不包含任何闭回路，则该变量组必有孤立点必有孤立点.反证反证孤立点不会是孤立点不会是闭回路上的点闭回路上的点定理定理 5 变量组变量组 对应的列向量组线性无关的充对应的列向量组线性无关的充要要条件是该变量组中不包含任何闭回路条件是该变量组中不包含任何闭回路.
11、证明证明第13页，此课件共44页哦定理定理 5 的证明的证明Proof:用反证法用反证法设变量组设变量组（*）对应的列向量）对应的列向量组线性无关，但该变量组包含一个以其中某些变量为顶组线性无关，但该变量组包含一个以其中某些变量为顶点的闭回路，点的闭回路，则由性质则由性质 2 知，这些变量对应的列向量必知，这些变量对应的列向量必线性相关，与假设矛盾线性相关，与假设矛盾.定理定理 5 变量组变量组 对应的列向量组线性无关的充要对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路条件是该变量组中不包含任何闭回路.设有一组数设有一组数 使得使得 由于变量组由于变量组（*）中不包含任何闭回路，
12、由性质中不包含任何闭回路，由性质 3 可知其中必有孤立点，可知其中必有孤立点，不妨设不妨设 为孤立点，为孤立点，又不妨设又不妨设 是（是（*）在第）在第i1 1行上唯一的变量，这时由行上唯一的变量，这时由p pijij的特征，（的特征，（1 1）的左端第）的左端第i1个分量和为个分量和为k1，而右端为，而右端为0，在第在第 j1列上的唯一变列上的唯一变量如何？量如何？但但 仍不包含闭回路，其中仍不包含闭回路，其中还有孤立点还有孤立点,与前面类似分析可证与前面类似分析可证 k2=0.同理得同理得 k3=k4=kr=0这就证明了向量组这就证明了向量组（*）线性无关线性无关.第14页，此课件共44页
13、哦1 运输问题及其数学模型推论推论 2 2 平衡运输问题中的一组平衡运输问题中的一组 m+n-1 个变量个变量能构成基变量的充要条件是它不包含任何闭回路能构成基变量的充要条件是它不包含任何闭回路.该推论给出了运输问题的基可行解中基变量的一该推论给出了运输问题的基可行解中基变量的一个基本特征：基变量组不含闭回路个基本特征：基变量组不含闭回路.这就是基可行解这就是基可行解在表上的一个表现，利用它来判断在表上的一个表现，利用它来判断 m+n 1 个变量个变量是否构成基变量组，就看它是否包含闭回路是否构成基变量组，就看它是否包含闭回路.这种方法简便易行，它比直接判断这些变量对应这种方法简便易行，它比直
14、接判断这些变量对应的列向量是否线性无关要简便得多的列向量是否线性无关要简便得多.利用基变量的这个特征，将可以导出求平衡运输利用基变量的这个特征，将可以导出求平衡运输问题的初始基可行解的一些简便方法问题的初始基可行解的一些简便方法.第15页，此课件共44页哦2 运输问题的表上作业法2 2 运输问题的表上作业法运输问题的表上作业法 表上作业法（又称运输单纯形法）是根据单纯形表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点，设计的一种在表上运算法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法的求解运输问题的简便而有效的方法.主要步骤：主要步骤：1、求一
15、个初始调运方案（初始基可行解）；求一个初始调运方案（初始基可行解）；2、判别当前方案是否为最优，若是则迭代停止，否则判别当前方案是否为最优，若是则迭代停止，否则 转下一步；转下一步；3、改进当前方案，得到新的方案（新的基可行解），改进当前方案，得到新的方案（新的基可行解），再返回再返回 2。第16页，此课件共44页哦 运输问题一、初始方案的确定一、初始方案的确定1、西北角法西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex.1 50 已知某商品有三个产地已知某商品有三个产地A1、
16、A2、A3和四个销地和四个销地B1、B2、B3、B4 ，产量、销量及单位运价如表，产量、销量及单位运价如表.问应问应如何调运，在满足各销地需要的情况下，使总的运费如何调运，在满足各销地需要的情况下，使总的运费支出为最少？支出为最少？解：解：5101020235规则规则:从运输表的西从运输表的西北角开始北角开始,优先安排优先安排编号小的产地和销地编号小的产地和销地的运输任务的运输任务.填了几个数字？填了几个数字？Note:在填入一个数时，如果行和列同时饱和，在填入一个数时，如果行和列同时饱和，规定只划去一行或一列规定只划去一行或一列 BjAi B1 B2 B3 B4 ai A110 5 2 3
17、50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15500第17页，此课件共44页哦2 运输问题的表上作业法2、最小元素法最小元素法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15规则规则:优先安排单位运价最小的产地与销地之间的运输优先安排单位运价最小的产地与销地之间的运输 任务任务.40102551010Note:在某行（或列）填入最后一个数时，如果行和在某行（或列）填入最后一个数时，如果行和列同时饱和，规定只划去该行（或列）列同时饱和，规定只划去该
18、行（或列）BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了几个数字？填了几个数字？第18页，此课件共44页哦 运输问题定理定理 6 用西北角法或最小元素法得到的初始解是用西北角法或最小元素法得到的初始解是平衡平衡运输问题的基可行解，运输问题的基可行解，m+n-1 个个填入数字的格子对应的填入数字的格子对应的是基变量是基变量.Proof:首先，得到的初始解首先，得到的初始解 为可行解是显然的为可行解是显然的.其次，由于行列数共有其次，由于行列数共有 m+n，而按填数字的
19、方法，而按填数字的方法,除填最后一个数时，划去一行一列外，每填一个数划去除填最后一个数时，划去一行一列外，每填一个数划去一行或一列一行或一列.因此因此,共填共填 m+n-1 个数个数.最后，证明所填最后，证明所填 m+n-1 个数对应的变量组不含闭回路个数对应的变量组不含闭回路.用反证法用反证法若含有闭回路若含有闭回路 不妨设此闭回路如右不妨设此闭回路如右（其他情形同理可证）（其他情形同理可证）不妨设填不妨设填 后划去行，故后划去行，故 必须较必须较 先填，先填，且填后划去的是列，从而且填后划去的是列，从而 必须较必须较 先填，且填后划先填，且填后划去的是行，而这又说明去的是行，而这又说明 必
20、须较必须较 先填，且填后划先填，且填后划去的是列，这又得到去的是列，这又得到 必须较必须较 先填，且填后划去的先填，且填后划去的是行，这样就得到了矛盾，所以，填数的是行，这样就得到了矛盾，所以，填数的 m+nm+n-1-1 个格个格子对应的变量组不含闭回路，从而，证得了本定理子对应的变量组不含闭回路，从而，证得了本定理.第19页，此课件共44页哦2 运输问题的表上作业法关键关键1、填一个数字划去一行或一列填一个数字划去一行或一列 不产生闭回路；不产生闭回路；2、填一个数字填一个数字只只划去一行或一列划去一行或一列 填满填满m+n-1-1个数个数.BjAi B1 B2 ai A1 8 2 5 A
21、2 3 1 4 bj 6 3 差额差额 6 2 差额差额 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 按最小元素法按最小元素法3423、Vogel 法法 (元素差额法元素差额法)规则：计算各行各列的最小元素与次小元素的差额，规则：计算各行各列的最小元素与次小元素的差额，优先安排差额最大的所优先安排差额最大的所在行或列的单位运价最在行或列的单位运价最小的产地与销地之间的小的产地与销地之间的运输任务运输任务第20页，此课件共44页哦 运输问题二、最优性检验二、最优性检验 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3
22、 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010定理定理 7 设设 是平衡运输问题的是平衡运输问题的一组基变量，一组基变量，是非基变量，则在变量组是非基变量，则在变量组 中存在唯一的闭回路中存在唯一的闭回路.1、闭回路法闭回路法+1-1+1-1 BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6第21页，此课件共44页哦2 运输问题的表上作业法2、位势法（对偶变量法）位势法（对偶变量法）求检验数的方求检验数的方法法约束方程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n-1x0必为基变量必为基变量,x0=0约束方
23、程的系数矩阵的秩为约束方程的系数矩阵的秩为m+n对任意的对任意的 a0，与原问题等价与原问题等价由于由于xj 的检验数的检验数 设：为基变量，由于基变量设：为基变量，由于基变量的检验数等于零的检验数等于零有解，不唯一有解，不唯一ui 称为行位势称为行位势，vj 称为行位势称为行位势第22页，此课件共44页哦 运输问题 BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4 vj BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6-2-120273见见 Ex.1 最小元素法得
24、到的初始基可行解最小元素法得到的初始基可行解10053-12-5 若若 ，则此时的运输方案为最优的，则此时的运输方案为最优的第23页，此课件共44页哦2 运输问题的表上作业法三、基可行解的改进三、基可行解的改进 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6选择进基变量选择进基变量则取非基变量则取非基变量 xst 为进基变量为进基变量确定出基变量确定出基变量调整量调整量则基变量则
25、基变量 xkl 出基（运量擦去）出基（运量擦去）调整方法：在该闭回路上，奇点运量加调整方法：在该闭回路上，奇点运量加 ，偶点减去，偶点减去 能转运多少？能转运多少？153010 6 5 4 2010 1-5 6 520 6 6 4 5 6 因为因为 ，所以此运输方案为最优，所以此运输方案为最优方案方案Note:若在闭回路上有几个偶点处的运量等于若在闭回路上有几个偶点处的运量等于 ，则，则可任取其中一个作为出基变量（运量擦去），其余几可任取其中一个作为出基变量（运量擦去），其余几个点的值调整后变为个点的值调整后变为0.(0.(但应填入，说明这些变量还但应填入，说明这些变量还在基内，这时就出现了退
26、化在基内，这时就出现了退化)问：问：从从A2到到B4的单位运价的单位运价c24在什么范围变化时，所得在什么范围变化时，所得最优调运方案不变最优调运方案不变.c12在什么范围变化呢？在什么范围变化呢？第24页，此课件共44页哦四、四、踏石法踏石法1)、找入变量、找入变量l从从 中找最小者，对应中找最小者，对应 xij 就是入变量就是入变量2)、以、以 非基变量非基变量xij 为起点，寻找由原基变量构成的为起点，寻找由原基变量构成的闭合回路闭合回路l该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量因此
27、，闭合回路中必有偶数个变量(包括包括 xij)，且回路中每行每列只有，且回路中每行每列只有两个变量两个变量3)、求入基变量、求入基变量 xij 的最大值及新基变量的解的最大值及新基变量的解l从从 xij出发，沿任一个方向对回路拐角上的基变量依此标出发，沿任一个方向对回路拐角上的基变量依此标“”和和“+”，表，表示示“”和和“+”xij，从而迭代后仍满足分配的平衡，从而迭代后仍满足分配的平衡l标有标有“”的变量中最小者就是的变量中最小者就是出基变量出基变量，对应，对应xij*的值就是所的值就是所求入基求入基变量变量 xij 的最大值。的最大值。l标有标有“”的变量减去的变量减去 xij*，标有标
28、有“+”的变量加上的变量加上 xij*4)、用位势法求新基变量的检验数、用位势法求新基变量的检验数l若所有若所有 ，则达到最优，算法停，则达到最优，算法停止；止；否则返回否则返回 1）。）。第25页，此课件共44页哦 补充补充 例题例题 踏石法，以最低费用法所得初始解开始（注意：对基踏石法，以最低费用法所得初始解开始（注意：对基变量变量xij有：有：cij=ui+vj，任取一个任取一个ui或或vj=0，计算出，计算出ui、vj)所有所有 cij (ui+vj)=0，达到最优。，达到最优。答：最优解如上分配表，答：最优解如上分配表，OBJ=98OBJ=121OBJ=101第26页，此课件共44页
29、哦五、五、运输问题迭代中的一些具体问题运输问题迭代中的一些具体问题 1)闭合回路的画法闭合回路的画法l从从入基入基变量变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用深探法变量，则返回上一拐角，换一个方向走，采用深探法l闭合回路不一定是矩形闭合回路不一定是矩形 2)产销不平衡产销不平衡l供过于求，即供过于求，即 ai bj，增加一个虚收点增加一个虚收点Dn+1，bn+1=ai-bj,令令 wi,n+1=0,i=1,2,ml供小于求，即供小于求，即 ai bj，增加一个虚发点增加一个
30、虚发点Wm+1，am+1=bj-ai,令令 wm+1,j=0,j=1,2,n 3)关于退化问题关于退化问题(1)、初始解退化初始解退化。即初始基变量的个数少于。即初始基变量的个数少于m+n 1。必须补足基变量的个数，。必须补足基变量的个数，否则不能正常解出否则不能正常解出m+n个个ui和和 vjl所补基变量的值为所补基变量的值为 0，补充的原则：，补充的原则：(1)尽量先选运费小的实变量；尽量先选运费小的实变量；(2)补充补充后不能有某个基变量独占一行一列后不能有某个基变量独占一行一列第27页，此课件共44页哦六、六、关于退化问题关于退化问题(2)、迭代过程中出现退化迭代过程中出现退化l闭合回
31、路中标有闭合回路中标有“”的基变量同时有多个达到最小的基变量同时有多个达到最小l变换后，有多个原基变量变为变换后，有多个原基变量变为 0，选运费最大者为出，选运费最大者为出基基变量，其余保留变量，其余保留在新的基础解中在新的基础解中l退化较严重时，可能会出现多次迭代只有值为退化较严重时，可能会出现多次迭代只有值为 0 的基变量在转移。此时，一的基变量在转移。此时，一要耐心，二要正确选择出变量要耐心，二要正确选择出变量踏石法迭代中需注意的问题：踏石法迭代中需注意的问题：(1)、错误地将分配表中基变量的解代入到运费表中、错误地将分配表中基变量的解代入到运费表中(2)、不能正确画闭合回路、不能正确画
32、闭合回路(3)、初始解退化，未能补足基变量的个数初始解退化，未能补足基变量的个数。因此在位势法中多次。因此在位势法中多次令某个令某个ui或或 vj为为 0；(4)、在位势法中只能令一个在位势法中只能令一个 ui 或或 vj 为为 0；若不能求出全部；若不能求出全部 ui和和 vj，说明基变量未选够数或未选对，说明基变量未选够数或未选对第28页，此课件共44页哦 运输问题七、七、补充：运输问题的图上作业法补充：运输问题的图上作业法 图上作业法是在交通图上进行物资调运方案编制和图上作业法是在交通图上进行物资调运方案编制和调整的一种科学方法。在铁路特别是公路运输中使用很调整的一种科学方法。在铁路特别
33、是公路运输中使用很多且有很好的效果。多且有很好的效果。在交通图中，用在交通图中，用表示表示产地（发点），并将产量记产地（发点），并将产量记在圆圈内；用在圆圈内；用表示销地表示销地（收点），并将销量记在方（收点），并将销量记在方框内。框内。206040402463目标：吨公里数目标：吨公里数(费用费用)最小的调运方案最小的调运方案 .物资调运的流向用与交通线平行的箭线表示，规定物资调运的流向用与交通线平行的箭线表示，规定画在前进方向的右边，调运量加括号记在箭线的右边。画在前进方向的右边，调运量加括号记在箭线的右边。(20)(20)(40)第29页，此课件共44页哦补充：运输问题的图上作业法203
34、03020243对流：物资在同一线路上往返运输对流：物资在同一线路上往返运输.(20)(20)(30)(30)(10)这是对流这是对流20303020243(20)(20)(30)(30)106030(10)(20)1、无圈无圈的交通的交通图图2020502010 对于无圈图，每条对于无圈图，每条边都是割边，去掉它网边都是割边，去掉它网络将不连通，所以，每络将不连通，所以，每条边上的运量是不得不条边上的运量是不得不只要每条边上不产生对流，即为最优方案只要每条边上不产生对流，即为最优方案第30页，此课件共44页哦 运输问题206040402463(20)(20)(40)2、有一个圈的交通图有一个
35、圈的交通图圈长：圈上每一条边的长度之和（记为圈长：圈上每一条边的长度之和（记为 l）l=15 先用先用“丢边破圈丢边破圈”方法，得到无圈图，再产生一个方法，得到无圈图，再产生一个没有对流的方案。没有对流的方案。内圈长内圈长 l内内：流向在圈内的边的长度之和：流向在圈内的边的长度之和l内内=8外圈长外圈长 l外外：流向在圈外的边：流向在圈外的边的长度之和的长度之和l外外=4是最优解码？是最优解码？称为迂回称为迂回调整方案：调整方案：对内圈各流量中最小调运量，进行反向调运对内圈各流量中最小调运量，进行反向调运(40)(20)(20)结论：结论：内外圈长都小于圈长的一半的无对流的调运方案内外圈长都小
36、于圈长的一半的无对流的调运方案 为最优方案为最优方案第31页，此课件共44页哦补充：运输问题的图上作业法3、有多个、有多个圈圈的交通的交通图图106030202050203020有几个圈？如有一个圈的情形，对每一个圈先用如有一个圈的情形，对每一个圈先用“丢边破圈丢边破圈”方方法，得到无圈图，再产生一个没有对流的方案。再进行法，得到无圈图，再产生一个没有对流的方案。再进行检查、调整。检查、调整。只需检查13个圈吗？会循环吗？一般不够！因为对一个圈进行调整后，会对已检一般不够！因为对一个圈进行调整后，会对已检查的圈有影响查的圈有影响.不会！因为每次目标不会！因为每次目标函数下降值大于一个固定函数下
37、降值大于一个固定值（如值（如 1）第32页，此课件共44页哦 运输问题4、产销不平衡运输问题、产销不平衡运输问题当当Note:通常建立运输模通常建立运输模型指的是平衡运输模型型指的是平衡运输模型可以虚设一个产地可以虚设一个产地 Am+1,其产量为其产量为 并假设产地并假设产地 Am+1 运往各销地的单运往各销地的单位运价为位运价为 cm+1,j=0(j=1,2,n).则原问题可转则原问题可转化为平衡运输问题：化为平衡运输问题：产大于销，可通产大于销，可通过虚设销地，类似过虚设销地，类似建立平衡运输模型建立平衡运输模型第33页，此课件共44页哦2 运输问题的表上作业法Ex.2已知运输问题由表给出
38、，试建立运输模型已知运输问题由表给出，试建立运输模型.Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 bj 8 7 14解解:Bj Ai B1 B2 B3 ai A14 25 10 A2638 15 A3000 4 bj 8 7 14本题产量为本题产量为25，销量为，销量为29，是销大于产问题，是销大于产问题 虚设一个产地虚设一个产地 A3，由于并没有生产，所以运价为，由于并没有生产，所以运价为零，得运输模型零，得运输模型.如果各销地不满足时，单位缺货费为如果各销地不满足时，单位缺货费为 4，3，7，则，则运输模型为运输模型为437第34页，此课件共44页哦 运输问题
39、 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最低最低需求量需求量 10 10 10Ex.3 已知运输问题由表给出，如果产地已知运输问题由表给出，如果产地 Ai 的产量的产量必须运走必须运走，试建立运输模型试建立运输模型.BjAi B1 B2 B3 B4 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 15解解:这是一个产大于销的运输问题这是一个产大于销的运输问题.234虚设一销地虚设一销地 B4,销量销量 b4=15.BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 最
40、低最低需求量需求量 10 10 10 最高最高需求量需求量 20 10不限不限 BjAi B1 B2 B3 ai A14 23 10 A2564 15 A3345 20 bj 10 10 10 443B3B15351015A4M100MM0 三个销地的最低需求为三个销地的最低需求为 30，最高需求不限最高需求不限.根据根据现有产量，现有产量，B3 至多能得到至多能得到 25.建立运输模型建立运输模型 .2说明什么？说明什么？第35页，此课件共44页哦 运输问题3 运输问题应用举例运输问题应用举例Ex.4 (生产调度问题生产调度问题)某制冰厂每年某制冰厂每年1 4 季度必须供季度必须供应并块应并
41、块 15、20、25、10（千吨）（千吨）.已知该厂各季度冰已知该厂各季度冰 块的生产能力及冰块的单位成本如表块的生产能力及冰块的单位成本如表.如果生产出来如果生产出来的冰块不在当季度使用，每千吨冰块存储一个季度的冰块不在当季度使用，每千吨冰块存储一个季度费用为费用为4（千元）（千元）.又设该制冰厂每年第又设该制冰厂每年第3季度末对贮季度末对贮冰库进行清库维修冰库进行清库维修.问应如何安排冰块的生产，可使问应如何安排冰块的生产，可使该厂全年生产、该厂全年生产、存储费用最少？存储费用最少？季季 度度 生产能力（千吨）生产能力（千吨）单位成本（千元）单位成本（千元）1 25 5 2 18 7 3
42、16 8 4 15 5第36页，此课件共44页哦3 运输问题应用举例季季 度度 生产能力（千吨）生产能力（千吨）单位成本（千元）单位成本（千元）1 25 5 2 18 7 3 16 8 4 15 5 Bj Ai B1 B2 B3 B4 ai A1 25 A2 18 A3 16 A4 15 bj 15 20 25 10 解：解：5B54913M0MMMMM0005118179137第37页，此课件共44页哦 运输问题Ex.5 (运量有界的运输问题运量有界的运输问题)6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A
43、1 B3 B2 B1 dij表表 2 2 表表1 给出一个运输问题给出一个运输问题.现在规定产地现在规定产地 Ai 至销地至销地 Bj 的运量不能超过的运量不能超过 dij,由表由表 2 2 给定给定.试建立运输问题试建立运输问题 .解解：虚设虚设 Dij(i=1,2;j=1,2,3)6 6个点，个点，Dij 既作产地，既作产地，又作销地，其产量、销量都为又作销地，其产量、销量都为 dij .产地产地 Ai 的物资只可的物资只可运送给运送给 Dij,而而 Dij 的物资只可运送给的物资只可运送给 Bj,或送给自身或送给自身.第38页，此课件共44页哦3 运输问题应用举例 BjAi D11 D1
44、2 D13 D21 D22 D23 B1 B2 B3 ai A1 D11 D12 D13 A2 D21 D22 D23 bj 6 5 7 bj 10762 A2 84 53 A1 ai B3 B2 B1 BjAi表表 1 1 5 2 4 A2 3 3 4 A1 B3 B2 B1 dij表表 2 2 8 104330000305040000206074334254257563321303124244214第39页，此课件共44页哦 运输问题Ex.6 (空车调度问题空车调度问题)某航运公司承担六个港口城市某航运公司承担六个港口城市 A、B、C、D、E、F 的四条固定航线的物资运输任的四条固定航线的
45、物资运输任务务.已知各条航线的起点、终点城市及每天航班数见已知各条航线的起点、终点城市及每天航班数见表表1，假定各条航线使用相同型号的船只，又各城市间，假定各条航线使用相同型号的船只，又各城市间的航程天数见表的航程天数见表2.又知每条船只每次装卸货的时间各又知每条船只每次装卸货的时间各需一天，则该航运公司至少应配备多少条船，才能满足需一天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？所有航线的运货需求？航航线线起点起点城市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C2301555D14
46、131501720E7851703F7852030表表2 2第40页，此课件共44页哦3 运输问题应用举例解解：该公司所需配备船只分两部分该公司所需配备船只分两部分.1 1、载货航程需要的周转船只数、载货航程需要的周转船只数航航线线起点起点城市城市终点终点城市城市每天航班每天航班数数1ED32BC23AF14DB1表表1 1 到到从从ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030表表2 2 如航线如航线1，在港口，在港口E 装货装货1 天，天，E 至至 D 航程航程17天，天，在在D 卸货卸货1天，总计天，总计19天天.每天
47、每天3 航班，故该航线周转航班，故该航线周转船只需船只需5757条条.航线航线装货天数装货天数航程天数航程天数卸货天数卸货天数小计小计航班数航班数需周转船只数需周转船只数11171193572131521031719194113115115累计共需周转船只数累计共需周转船只数91条条.第41页，此课件共44页哦 运输问题2 2、各港口间调度所需船只数、各港口间调度所需船只数港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01-1B12-1C202D312E03-3F101 港口每天到达与需要的船只不同，如表港口每天到达与需要的船只不同，如表.为使配备船只数最少，应做到周转的空船数
48、为最少为使配备船只数最少，应做到周转的空船数为最少.建立运输模型，建立运输模型，C、D、F 为空船的产地为空船的产地，A、B、E 为销地，单位运价为相应各港口之间的船只航程天数为销地，单位运价为相应各港口之间的船只航程天数.港港 口口 A B E每天多余船只每天多余船只 C2 35 2 D141317 2 F783 1每天缺少船只每天缺少船只 1 1 311111 用表上作业法用表上作业法求出空船的最优调求出空船的最优调度方案度方案.最少需周转的最少需周转的空船数为空船数为40条条.所以，在不考虑维修、储备等情况下，该公司至所以，在不考虑维修、储备等情况下，该公司至少应配备少应配备131条船条
49、船.第42页，此课件共44页哦3 运输问题应用举例Ex.7 (运输问题悖论运输问题悖论)paradox 在运输问题中，有一种在若干个产销地运价不变的在运输问题中，有一种在若干个产销地运价不变的情况下，当调运量增加了，总运费反而会下降的奇怪现情况下，当调运量增加了，总运费反而会下降的奇怪现象象 .Bj Ai B1 B2 B3 B4 B5 ai A11415 61314 7 A2169221316 18 A3851145 6 A412418910 15 bj 4 11 12 8 11746851510 如下面的运输问题，总调运量如下面的运输问题，总调运量46单位，最优总费单位，最优总费用用444单位单位.现在总产量和总销量各增加现在总产量和总销量各增加10单位，单位单位，单位运价不变，运价不变，总费用将总费用将如何？如何？12112112 46 8011150运量为运量为56,最优总费用最优总费用为为409单位单位.怎么会产生呢？怎么会产生呢？产生负费用路产生负费用路多品种物资运输问题、转运问题、车多品种物资运输问题、转运问题、车(船船)调度问题等调度问题等第43页，此课件共44页哦 运输问题 运输问题运输问题 完完第44页，此课件共44页哦