吉林大学本科运筹学课件-运输问题[精选].ppt

清华大学出版社 第3章 运输问题 第1节 运输问题的数学模型 第2节 表上作业法 第3节 产销不平衡的运输问题及其求解方法 第4节 应用举例 第1节 运输问题的数学模型 第1节 运输问题的数学模型 第1节 运输问题的数学模型 第1节 运输问题的数学模型 第2节 表上作业法  表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为： (1) 找出初始基可行解。即在(m×n)产销平衡表上用西北角法或最小元素法、Vogel法给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。 (2) 求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。 (3) 确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。 (4) 重复(2)，(3)直到得到最优解为止。 第2节 表上作业法  例1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。 第2节 表上作业法 解：先作出这问题的产销平衡表和单位运价表，见表3-3，表3-4 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.1 确定初始基可行解 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.2 最优解的判别 2.3 改进的方法——闭回路调整法 2.3 改进的方法——闭回路调整法 2.3 改进的方法——闭回路调整法 2.4 表上作业法计算中的问题 2.4 表上作业法计算中的问题 2.4 表上作业法计算中的问题 2.4 表上作业法计算中的问题 2.4 表上作业法计算中的问题 2.4 表上作业法计算中的问题 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 第4节 应 用 举 例 当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表3-18得(2，4)为调入格。以此格为出发点，作一闭回路，如表3-19所示。 (2，4)格的调入量θ是选择闭回路上具有(-1)的数字格中的最小者。即θ=min(1,3)=1(其原理与单纯形法中按θ规划来确定换出变量相同)。然后按闭回路上的正、负号，加入和减去此值，得到调整方案，如表3-20所示。 对表3-20给出的解，再用闭回路法或位势法求各空格的检验数，见表3-21。表中的所有检验数都非负，故表3-20中的解为最优解。这时得到的总运费最小是85元。 1. 无穷多最优解 2. 退化 1. 无穷多最优解 在本章2.1节中提到，产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多最优解? 判别依据与第1章3.3节讲述的相同。即某个非基变量(空格)的检验数为0时，该问题有无穷多最优解。表3-21空格(1，1)的检验数是0，表明例1有无穷多最优解。可在表3-20中以(1，1)为调入格，作闭回路 (1，1)+-(1，4)--(2，4)+-(