第四章运输问题优秀PPT.ppt

第四章运输问题第四章运输问题第一页，本课件共有61页第一节第一节 运输问题运输问题 及其数学模型及其数学模型 运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶变量与原问题检验数的关系。第二页，本课件共有61页运输问题n典型背景单一物资运输调度问题 设某种物品有:m个产地：产量：n个销地：销量：从产地 到销地 的单位运价是 。求总运费最小的调度方案。第三页，本课件共有61页运输问题n决策变量 表示由 到 的物品数量。销地产地销量产量第四页，本课件共有61页运输问题n产销平衡问题总产量=总销量 即n产销不平衡问题总产量=总销量第五页，本课件共有61页运输问题产销平衡问题的数学模型第六页，本课件共有61页运输问题运输问题数学模型的特点n运输问题有有限最优解n运输问题约束条件的系数矩阵（下页）约束条件系数矩阵每一列只有两个1，其余为0；对产销平衡问题约束条件均为等式，且产量之和=销量之和；约束条件的独立方程最多有m+n-1个，即第七页，本课件共有61页运输问题mn第八页，本课件共有61页运输问题ij其中第九页，本课件共有61页运输问题运输问题的对偶问题对偶变量与原问题检验数的关系 对产销平衡运输问题，若用 分别表示前m个约束等式相应的对偶变量，用 分别表示后n个约束等式相应的对偶变量，即对偶变量为第十页，本课件共有61页运输问题运输问题的对偶问题可写为运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系第十一页，本课件共有61页运输问题线性规划问题变量 的检验数为运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系变量 的检验数为第十二页，本课件共有61页运输问题设运输问题的一个基可行解的变量为由于基变量的检验数为零，故有运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系第十三页，本课件共有61页运输问题方程组含有m+n-1个方程，m+n个变量可证明方程组有解，且不唯一。求出方程组的解解（称为位势位势）则变量 的检验数为运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系求运输问题检验数的一种方法第十四页，本课件共有61页第二节第二节 运输问题的运输问题的 表上作业法表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法表上作业法。第十五页，本课件共有61页运输问题n表上作业法是单纯形法在求解运输问题的一种简便方法。n单纯形法与表上作业法的关系：（1）找出初始基可行解 （2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同第十六页，本课件共有61页运输问题换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否第十七页，本课件共有61页运输问题举例说明表上作业法例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地第十八页，本课件共有61页运输问题第一步：确定初始基可行解 最小元素法、伏格尔法n最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。第十九页，本课件共有61页运输问题最小元素法举例4122854396111110销量产量销地产地822010100614868000060第二十页，本课件共有61页运输问题最小元素法举例4122854396111110销量产量销地产地82101468最小元素法缺点：会出现顾此失彼 （运费差额问题）考虑运价差第二十一页，本课件共有61页运输问题 罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：;差额大，则不按最小运费调运，运费增加大。差额大，则不按最小运费调运，运费增加大。;差额小，则不按最小运费调运，运费增加不大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。n伏格尔法思路：第二十二页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数04-4=0第一次第一次第二十三页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数013-2=1第一次第一次第二十四页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011第一次第一次第二十五页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数4-2=22153第一次第一次第二十六页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数21531480优先安排销地 ，否则运价会更高下次不考虑该列第一次第一次第二十七页，本课件共有61页运输问题第二次第二次n结合例结合例1说明这种方法。说明这种方法。行罚数012 列 罚 数213优先安排销地 ，否则运价会更高84122854396111110销量产量销地销地产地产地148006下次不考虑该行第二十八页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。行罚数01 列 罚 数21284122854396111110销量产量销地销地产地产地148006下次不考虑该列802第三次第三次第二十九页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。行罚数76 列 罚 数1284122854396111110销量产量销地销地产地产地1480068024120下次不考虑该列第四次第四次第三十页，本课件共有61页运输问题n结合例结合例1说明这种方法。说明这种方法。行罚数00 列 罚 数24284122854396111110销量产量销地销地产地产地1480068024120000第五次第五次第三十一页，本课件共有61页运输问题n例1用伏格尔法得到的初始基可行解4122854396111110销量产量销地销地产地产地48148122目标函数值目标函数值用最小元素法求出的目标函数z=246 一般说来，伏格尔法得出的初始一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问解的质量最好，常用来作为运输问题最优解的近似解。题最优解的近似解。第三十二页，本课件共有61页运输问题第二步：解的最优性检验n闭回路法 思路：计算空格（非基变量）的检验数 若令则如何求检验数？分析：运费的增量即 增加1个单位 的检验数=相应的运费增量第三十三页，本课件共有61页运输问题4122854396111110销量产量销地产地82101468从初始表分析：要保证产销平衡，则 称为闭回路+1-1+1-1第三十四页，本课件共有61页运输问题4122854396111110销量产量销地产地8210146821第三十五页，本课件共有61页运输问题检验数表4122854396111110销量产量销地产地82101468211-11012表中的解不是最优解。第三十六页，本课件共有61页运输问题第三步：解的调整 调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。4122854396111110销量产量销地产地82101468-1（-2）（-2）（+2）（+2）第三十七页，本课件共有61页运输问题n调整后的解为：4122854396111110销量产量销地产地821214482209112此时的解为最优解。有无穷多最优解第三十八页，本课件共有61页运输问题几点说明：n当检验数为的负的变量超过两个，选择最小者对应的变量换入；n在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；n迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。第三十九页，本课件共有61页运输问题讨论内容：n初始调运方案（初始基可行解）西北角法n解的最优性检验对偶变量法（或称位势法）还有其它还有其它的方法吗的方法吗？根据第一节运输问题对根据第一节运输问题对根据第一节运输问题对根据第一节运输问题对偶问题与原问题的检验偶问题与原问题的检验偶问题与原问题的检验偶问题与原问题的检验数的关系数的关系数的关系数的关系第四十页，本课件共有61页第三节第三节 运输问题的运输问题的 进一步讨论进一步讨论 上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论：二、有转运的运输问题二、有转运的运输问题一、产销不平衡的运输问题一、产销不平衡的运输问题并附有运输问题的思考题及练习题第四十一页，本课件共有61页运输问题一、产销不平衡的运输问题n（）若总产量大于总销量，即令假象销地的销量为：第四十二页，本课件共有61页运输问题决策变量 表示由 到 的物品数量。销地产地销量产量注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。第四十三页，本课件共有61页运输问题原产大于销平衡问题的数学模型第四十四页，本课件共有61页运输问题修改后产大于销平衡问题的数学模型第四十五页，本课件共有61页运输问题n（）若总产量小于总销量，即令假象产地的销量为：一、产销不平衡的运输问题仿照上述类似处理。第四十六页，本课件共有61页运输问题举例说明n某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地第四十七页，本课件共有61页运输问题二、有转运的运输问题n中间转运站产地、销地、中转站。n建模思路：从发送及接受角度考虑。产地 转运 销地 发送量产地转运销地接受量第四十八页，本课件共有61页运输问题应用问题举例n例1、水泥调运的产销不平衡情况及运价如下表，求最好的调运方案。21110783592143销量产量销地产地第四十九页，本课件共有61页运输问题最优方案为：21110783592143销量产量销地产地000第五十页，本课件共有61页运输问题n例2、某农场有土地900亩，分为三类，计划种植三种作物，情况如下表，求使作物总产量最多的布局方案。500销量产量销地产地700700850480600300400500第五十一页，本课件共有61页运输问题n解：目标函数最大，可用最大元素法，即是按产量高的优先安排的原则。500销量产量销地产地700700850480600300400500100300100400050第五十二页，本课件共有61页运输问题调整：500销量产量销地产地7007008504806003004005001002002004000可验证此时为最优解。第五十三页，本课件共有61页运输问题运输问题讨论第五十四页，本课件共有61页运输问题一、概念题（判断）1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含（m+n-1）个非零的 ，且满足 就可以作为一个初始基可行解。第五十五页，本课件共有61页运输问题3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。6、如果.分别乘上一个常k,.不会发生变化。第五十六页，本课件共有61页运输问题二、运输问题的对偶问题 某一实际的运输问题可以叙述如下：有n个地区需要某种物资，需要量分别为 ，这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别为 ，已知从 i地区工厂至第j个需要地区单位物资的运价为 ，又 试阐述其对偶问题，并解释对偶变量的经济意义。第五十七页，本课件共有61页运输问题三、运输问题的灵敏度分析已知某运输问题的供需关系及单价表如下表，销量产量销地产地245353312要求（1）用表上作业法找出最优调运方案。（2）分别讨论 使最优方案不变 的变化范围第五十八页，本课件共有61页运输问题四、求解线性规划问题可转化为可转化为运输问题运输问题来求解来求解第五十九页，本课件共有61页运输问题练习：n下表给出一个运输问题及它的一个解，411374611562销量产量销地产地853231第六十页，本课件共有61页运输问题n试问：（1）表中给出的解是否为最优解？（2）若 由1变为3，所给的解是否仍为最优解？若不是，求出新的最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？（4）若所有价值系数均增加1，最优解是否改变？为什么？（5）写出该问题的对偶问题，并给出其对偶问题的最优解。第六十一页，本课件共有61页