运筹学_运输问题.ppt
2.72.7 运输问题运输问题运输问题运输问题一、运运输问题及其数学模型及其数学模型线性性规划模型、运划模型、运输表表二、初始基本可行解二、初始基本可行解西北角法、最小元素法西北角法、最小元素法三、非基三、非基变量的量的检验数数对偶偶变量法量法四、运四、运输表迭代表迭代典型背景典型背景单一物一物资运运输调度度问题设某种物品有某种物品有:m个个产地：地：产量：量：n个个销地：地：销量：量：从从产地地到到销地地的的单位运价是位运价是。求求总运运费最小最小的的调度方案。度方案。一、运输问题及其数学模型一、运输问题及其数学模型一、运输问题及其数学模型一、运输问题及其数学模型产销平衡问题：产销平衡问题：产销平衡问题：产销平衡问题：总产量总产量总产量总产量=总销量总销量总销量总销量,产销不平衡问题：产销不平衡问题：产销不平衡问题：产销不平衡问题：总产量总产量总产量总产量 总销量总销量总销量总销量典型背景典型背景单一物资运输调度问题单一物资运输调度问题设某种物品有设某种物品有:m个产地：个产地：产量：产量：n个销地：个销地：销量：销量：从产地从产地到销地到销地的单位运价是的单位运价是。求求总运费最小总运费最小的调度方案。的调度方案。产销平衡问题的数学模型产销平衡问题的数学模型产能约束产能约束需求约束需求约束运输问题数学模型的特点运输问题数学模型的特点运输问题数学模型的特点运输问题数学模型的特点1.运运输问题存在有限最存在有限最优解解2.运运输问题约束条件的系数矩束条件的系数矩阵结构构约束条件系数矩阵每一列只有两个约束条件系数矩阵每一列只有两个1，其余为，其余为0；产销平衡平衡问题约束条件均为等式，且产量之和约束条件均为等式，且产量之和=销量之和；销量之和；约束条件的独立方程最多有约束条件的独立方程最多有m+n-1个，即个，即mnim+j其中运输问题的对偶运输问题的对偶运输问题的对偶运输问题的对偶对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系 对产销平衡运输问题，若用对产销平衡运输问题，若用分别表示前分别表示前m个约束等式相应的对偶变量，个约束等式相应的对偶变量，用用分别表示后分别表示后n个约束等式相应的个约束等式相应的对偶变量，即对偶变量为对偶变量，即对偶变量为平衡运输问题的对偶问题可写为平衡运输问题的对偶问题可写为线性规划问题变量线性规划问题变量的检验数为的检验数为对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系变量变量的检验数为的检验数为设运输问题的一个基可行解的变量为设运输问题的一个基可行解的变量为由于基变量的检验数为零，故有由于基变量的检验数为零，故有对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系方程组含有方程组含有m+n-1个方程，个方程，m+n个变量，个变量，可证明方程组有解，且不唯一。可证明方程组有解，且不唯一。求出方程组的求出方程组的解解解解（称为（称为位势位势）则变量则变量的检验数为的检验数为对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系求运输问题检验求运输问题检验数的一种方法数的一种方法运输问题的求解运输问题的求解运输问题的求解运输问题的求解 根据运输问题的数学模型、及其约束方程组的系数矩阵结构，我们可以构造比单纯形法更为简便的求解运输问题的方法运输表迭代方法。运运输表迭代是表迭代是应用用单纯形法求解运形法求解运输问题时得到的一种特殊方法。得到的一种特殊方法。单纯形法形法过程程与与运运输表迭代的表迭代的过程程：（1）找出初始基可行解）找出初始基可行解（2）求各非基）求各非基变量的量的检验数数（3）判断是否最）判断是否最优解解计算表中空格检验数计算表中空格检验数表上给出表上给出m+n-1个运输量个运输量非基变量检验数符号非基变量检验数符号换基：换基：换基：换基：（4）确定换入变量和换出变量找出新的基可行解。）确定换入变量和换出变量找出新的基可行解。（5）重复（）重复（2）（4）直至求出最优解。）直至求出最优解。表上调整（闭回路调整）表上调整（闭回路调整）（运输问题必有最优解）（运输问题必有最优解）停止停止最优解最优解？是是否否A2A3B2A1B3B4B1实例分析运输问题的运输表迭代实例分析运输问题的运输表迭代实例分析运输问题的运输表迭代实例分析运输问题的运输表迭代确定初始基本可确定初始基本可确定初始基本可确定初始基本可行解；计算非基变量检验数；换基迭代。行解；计算非基变量检验数；换基迭代。行解；计算非基变量检验数；换基迭代。行解；计算非基变量检验数；换基迭代。s2=27s3=19d1=22d2=13d3=12d4=13s1=14供供应应量量供应地供应地运价运价需需求求量量需求地需求地6753842759106线性规划模型线性规划模型线性规划模型线性规划模型供供应应地地约约束束需需求求地地约约束束运输表运输表运输表运输表二、初始基本可行解二、初始基本可行解二、初始基本可行解二、初始基本可行解1.1.西北角法：优先满足左上角运输量西北角法：优先满足左上角运输量西北角法：优先满足左上角运输量西北角法：优先满足左上角运输量(350)350)813131466二、初始基础可行解二、初始基础可行解二、初始基础可行解二、初始基础可行解2.2.最小元素法：优先考虑运价最低的运输量最小元素法：优先考虑运价最低的运输量最小元素法：优先考虑运价最低的运输量最小元素法：优先考虑运价最低的运输量2.2.最小元素法：最小元素法：最小元素法：最小元素法：2.2.最小元素法：最小元素法：最小元素法：最小元素法：2.2.最小元素法：最小元素法：最小元素法：最小元素法：2.2.最小元素法最小元素法最小元素法最小元素法：2.2.最小元素法：最小元素法：最小元素法：最小元素法：232232三、检验数的计算三、检验数的计算三、检验数的计算三、检验数的计算对偶变量法：先确定基变量的位势，再据此计算非对偶变量法：先确定基变量的位势，再据此计算非对偶变量法：先确定基变量的位势，再据此计算非对偶变量法：先确定基变量的位势，再据此计算非基变量检验数。基变量检验数。基变量检验数。基变量检验数。三、检验数的计算三、检验数的计算三、检验数的计算三、检验数的计算对偶变量法：先确定基变量的位势，再据此计算非对偶变量法：先确定基变量的位势，再据此计算非对偶变量法：先确定基变量的位势，再据此计算非对偶变量法：先确定基变量的位势，再据此计算非基变量检验数。基变量检验数。基变量检验数。基变量检验数。三、检验数的计算三、检验数的计算三、检验数的计算三、检验数的计算对偶变量法：对偶变量法：对偶变量法：对偶变量法：三、检验数的计算三、检验数的计算三、检验数的计算三、检验数的计算对偶变量法：对偶变量法：对偶变量法：对偶变量法：三、检验数的计算三、检验数的计算三、检验数的计算三、检验数的计算对偶变量法：对偶变量法：对偶变量法：对偶变量法：四、运输表迭代四、运输表迭代四、运输表迭代四、运输表迭代确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。四、运输表迭代四、运输表迭代四、运输表迭代四、运输表迭代确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。四、运输表迭代四、运输表迭代四、运输表迭代四、运输表迭代确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。四、运输表迭代四、运输表迭代四、运输表迭代四、运输表迭代确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回确定包含最大检验数所属变量（即将进基）的闭回路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。路，找出回路中偶数顶点最小运输量，改进运输方案。几点说明：几点说明：几点说明：几点说明：1.当大于零的当大于零的检验数超数超过两个，两个，选择最大最大者者对应的的变量量进基；基；2.在最在最优解的运解的运输表中，若有表中，若有检验数数=0，则该运运输问题有无有无穷多最多最优解；解；3.迭代迭代过程中，若某一格运程中，若某一格运输量增加量增加时，其同行和同列基其同行和同列基变量均出量均出现零，零，则出出现退化。退化。为保保证m+n-1个非空格，需个非空格，需保留一个基保留一个基变量（取量（取值为0）。例例:求有求有6个发点和个发点和8个收点的最小费用运输问题。个收点的最小费用运输问题。产销单位运价如下表。产销单位运价如下表。分析：先建立该运输问题的数学模型分析：先建立该运输问题的数学模型分析：先建立该运输问题的数学模型分析：先建立该运输问题的数学模型xij表示从第表示从第i个发点到第个发点到第j个收点的货物运输量。个收点的货物运输量。记记cij表示从第表示从第i个发点到第个发点到第j个收点的单位货物运价，个收点的单位货物运价，ai表示第表示第i个发点的最大供货量，个发点的最大供货量，dj表示第表示第j个收点的需求量。个收点的需求量。总运输费用最少总运输费用最少决策变量决策变量目标函数目标函数约束条件约束条件各发点运出货物量不超过其产量各发点运出货物量不超过其产量各收点收到货物量等于其销量各收点收到货物量等于其销量决策变量非负限制决策变量非负限制各产、销点的产量和销量约束，决策变量限制各产、销点的产量和销量约束，决策变量限制线性规划模型线性规划模型线性规划模型线性规划模型model:!6发点发点8收点运输问题收点运输问题;sets:!集合段集合段;wh/w1.w6/:ai;vd/v1.v8/:dj;links(wh,vd):C,X;endsetsmin=sum(links:C*X);!目标函数目标函数;for(vd(J):sum(wh(I):X(I,J)=dj(J);!需求约束需求约束;for(wh(I):sum(vd(J):X(I,J)=ai(I);!产量约束产量约束;data:!数据段数据段;ai=60 55 51 43 41 52;dj=35 37 22 32 41 32 43 38;C=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3;enddataend集合段（集合段（Sets-endsets）数据段（数据段（data-enddata）目标函数与约目标函数与约束条件段束条件段Global optimal solution found at iteration:20 Objective value:664.0000 Variable Value Reduced Cost X(W1,V1)0.000000 5.000000 X(W1,V2)19.00000 0.000000 X(W6,V7)3.000000 0.000000 X(W6,V8)0.000000 3.0000002020次次迭迭代代后后得得到到全全局局最优解最优解总费用最少为总费用最少为664664最优运输方案最优运输方案最优解行数太多，略最优解行数太多，略运输问题的进一步讨论运输问题的进一步讨论运输问题的进一步讨论运输问题的进一步讨论前面讨论了产销平衡的运输问题，可前面讨论了产销平衡的运输问题，可以采用表上作业法求解。我们还可以讨论以采用表上作业法求解。我们还可以讨论更多类型的运输问题。如：更多类型的运输问题。如：2.2.有转运的运输问题有转运的运输问题有转运的运输问题有转运的运输问题1.1.产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题1.1.产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题n（）若）若总产量大于量大于总销量量，即，即 假设有一个虚拟销地，其单位运费为假设有一个虚拟销地，其单位运费为0，它的销量为它的销量为：原产大于销运输问题的数学模型修改后产销平衡问题的数学模型（）若）若总产量小于量小于总销量，量，即即 假设有一个虚拟产地，其单位运费为假设有一个虚拟产地，其单位运费为0，它的产量为：它的产量为：1.1.产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题产销不平衡的运输问题仿照上述类似处理。仿照上述类似处理。2.2.有转运的运输问题有转运的运输问题有转运的运输问题有转运的运输问题n中中间转运站运站产地、地、销地、中地、中转站；站；n建模思路：从发送及接受角度考虑。建模思路：从发送及接受角度考虑。最坏计算复杂性的最坏计算复杂性的LP实例实例可行域有可行域有2n个顶点个顶点，如果从，如果从初始顶点初始顶点x=0开始，单纯形法需要开始，单纯形法需要2n-1次迭代次迭代达到最优点。达到最优点。Klee和和Minty在在1972年给出的年给出的LP实例实例 练习练习1 1：某石油公司设有四个炼油厂，某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服它们生产普通汽油，并为七个销售区服务，生产和需求情况如下：务，生产和需求情况如下：从炼油厂运往第从炼油厂运往第j j个销售区每公升汽油个销售区每公升汽油平均运费（单位：平均运费（单位：千元千元/万万公升），应公升），应如何调运，使运费最省如何调运，使运费最省。
