第四章运输问题优秀课件.ppt

《第四章运输问题优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四章运输问题优秀课件.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章运输问题第四章运输问题第1页，本讲稿共61页第一节第一节 运输问题运输问题 及其数学模型及其数学模型 运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶变量与原问题检验数的关系。第2页，本讲稿共61页运输问题n典型背景单一物资运输调度问题 设某种物品有:m个产地：产量：n个销地：销量：从产地 到销地 的单位运价是 。求总运费最小的调度方案。第3页，本讲稿共61页运输问题n决策变量 表示由 到 的物品数量。销地产地销量产量第4页，本讲稿共61页运输问题n产销平衡问题总产量=总销量 即n产销不平衡问题总产量=总销量第5

2、页，本讲稿共61页运输问题产销平衡问题的数学模型第6页，本讲稿共61页运输问题运输问题数学模型的特点n运输问题有有限最优解n运输问题约束条件的系数矩阵（下页）约束条件系数矩阵每一列只有两个1，其余为0；对产销平衡问题约束条件均为等式，且产量之和=销量之和；约束条件的独立方程最多有m+n-1个，即第7页，本讲稿共61页运输问题mn第8页，本讲稿共61页运输问题ij其中第9页，本讲稿共61页运输问题运输问题的对偶问题对偶变量与原问题检验数的关系 对产销平衡运输问题，若用 分别表示前m个约束等式相应的对偶变量，用 分别表示后n个约束等式相应的对偶变量，即对偶变量为第10页，本讲稿共61页运输问题运输

3、问题的对偶问题可写为运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系第11页，本讲稿共61页运输问题线性规划问题变量 的检验数为运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系变量 的检验数为第12页，本讲稿共61页运输问题设运输问题的一个基可行解的变量为由于基变量的检验数为零，故有运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系第13页，本讲稿共61页运输问题方程组含有m+n-1个方程，m+n个变量可证明方程组有解，且不唯一。求出方程组的解解解解（称为位势位势）

4、则变量 的检验数为运输问题的对偶问题运输问题的对偶问题对偶变量与原问题检验数的关系对偶变量与原问题检验数的关系求运输问题检验数的一种方法第14页，本讲稿共61页第二节第二节 运输问题的运输问题的 表上作业法表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法表上作业法。第15页，本讲稿共61页运输问题n表上作业法是单纯形法在求解运输问题的一种简便方法。n单纯形法与表上作业法的关系：（1）找出初始基可行解 （2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同第16页，本

5、讲稿共61页运输问题换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否第17页，本讲稿共61页运输问题举例说明表上作业法例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地第18页，本讲稿共61页运输问题第一步：确定初始基可行解 最小元素法、伏格尔法n最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。第19页，本讲稿共61页运输问题最小元素法举例4122854396111110销量产量销地产地

6、822010100614868000060第20页，本讲稿共61页运输问题最小元素法举例4122854396111110销量产量销地产地82101468最小元素法缺点：会出现顾此失彼 （运费差额问题）考虑运价差第21页，本讲稿共61页运输问题 罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：;差额大，则不按最小运费调运，运费增加大。差额大，则不按最小运费调运，运费增加大。;差额小，则不按最小运费调运，运费增加不大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。n伏格尔法思路：第22页，本讲稿共61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122

7、854396111110销量产量销地销地产地产地行罚数04-4=0第一次第一次第23页，本讲稿共61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数013-2=1第一次第一次第24页，本讲稿共61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011第一次第一次第25页，本讲稿共61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数4-2=22153第一次第一次第26页，本讲稿

8、共61页运输问题n结合例结合例1说明这种方法。说明这种方法。4122854396111110销量产量销地销地产地产地行罚数011 列 罚 数21531480优先安排销地 ，否则运价会更高下次不考虑该列第一次第一次第27页，本讲稿共61页运输问题第二次第二次n结合例结合例1说明这种方法。说明这种方法。行罚数012 列 罚 数213优先安排销地 ，否则运价会更高84122854396111110销量产量销地销地产地产地148006下次不考虑该行第28页，本讲稿共61页运输问题n结合例结合例1说明这种方法。说明这种方法。行罚数01 列 罚 数21284122854396111110销量产量销地销地产

9、地产地148006下次不考虑该列802第三次第三次第29页，本讲稿共61页运输问题n结合例结合例1说明这种方法。说明这种方法。行罚数76 列 罚 数1284122854396111110销量产量销地销地产地产地1480068024120下次不考虑该列第四次第四次第30页，本讲稿共61页运输问题n结合例结合例1说明这种方法。说明这种方法。行罚数00 列 罚 数24284122854396111110销量产量销地销地产地产地1480068024120000第五次第五次第31页，本讲稿共61页运输问题n例1用伏格尔法得到的初始基可行解4122854396111110销量产量销地销地产地产地48148

10、122目标函数值目标函数值用最小元素法求出的目标函数z=246 一般说来，伏格尔法得出的初始一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问解的质量最好，常用来作为运输问题最优解的近似解。题最优解的近似解。第32页，本讲稿共61页运输问题第二步：解的最优性检验n闭回路法 思路：计算空格（非基变量）的检验数 若令则如何求检验数？分析：运费的增量即 增加1个单位 的检验数=相应的运费增量第33页，本讲稿共61页运输问题4122854396111110销量产量销地产地82101468从初始表分析：要保证产销平衡，则 称为闭回路+1-1+1-1第34页，本讲稿共61页运输问题41228543

11、96111110销量产量销地产地8210146821第35页，本讲稿共61页运输问题检验数表4122854396111110销量产量销地产地82101468211-11012表中的解不是最优解。第36页，本讲稿共61页运输问题第三步：解的调整 调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。4122854396111110销量产量销地产地82101468-1（-2）（-2）（+2）（+2）第37页，本讲稿共61页运输问题n调整后的解为：4122854396111110销量产量销地产地821214482209112此时的解为最优解。有无穷多最优解第38页，本讲稿共61页运输问题

12、几点说明：n当检验数为的负的变量超过两个，选择最小者对应的变量换入；n在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；n迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。第39页，本讲稿共61页运输问题讨论内容：n初始调运方案（初始基可行解）西北角法n解的最优性检验对偶变量法（或称位势法）还有其它还有其它的方法吗的方法吗？根据第一节运输问题根据第一节运输问题根据第一节运输问题根据第一节运输问题对偶问题与原问题的对偶问题与原问题的对偶问题与原问题的对偶问题与原问题的检验数的关系检验数的关系检验数的关系检验数的关系第4

13、0页，本讲稿共61页第三节第三节 运输问题的运输问题的 进一步讨论进一步讨论 上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论：二、有转运的运输问题二、有转运的运输问题一、产销不平衡的运输问题一、产销不平衡的运输问题并附有运输问题的思考题及练习题第41页，本讲稿共61页运输问题一、产销不平衡的运输问题n（）若总产量大于总销量，即令假象销地的销量为：第42页，本讲稿共61页运输问题决策变量 表示由 到 的物品数量。销地产地销量产量注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。第43页，本讲稿共61页运输问题原产大于销平衡问题的数学模型第44页，本讲稿共61页运输问题修

14、改后产大于销平衡问题的数学模型第45页，本讲稿共61页运输问题n（）若总产量小于总销量，即令假象产地的销量为：一、产销不平衡的运输问题仿照上述类似处理。第46页，本讲稿共61页运输问题举例说明n某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地第47页，本讲稿共61页运输问题二、有转运的运输问题n中间转运站产地、销地、中转站。n建模思路：从发送及接受角度考虑。产地 转运 销地 发送量产地转运销地接受量第48页，本讲稿共61页运输问题应用问题举例n例1、水泥调运的产销不平衡情况及运价如下表，求最好的调运方案。21110783592

15、143销量产量销地产地第49页，本讲稿共61页运输问题最优方案为：21110783592143销量产量销地产地000第50页，本讲稿共61页运输问题n例2、某农场有土地900亩，分为三类，计划种植三种作物，情况如下表，求使作物总产量最多的布局方案。500销量产量销地产地700700850480600300400500第51页，本讲稿共61页运输问题n解：目标函数最大，可用最大元素法，即是按产量高的优先安排的原则。500销量产量销地产地700700850480600300400500100300100400050第52页，本讲稿共61页运输问题调整：500销量产量销地产地700700850480

16、6003004005001002002004000可验证此时为最优解。第53页，本讲稿共61页运输问题运输问题讨论第54页，本讲稿共61页运输问题一、概念题（判断）1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含（m+n-1）个非零的 ，且满足 就可以作为一个初始基可行解。第55页，本讲稿共61页运输问题3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变

17、化。6、如果.分别乘上一个常k,.不会发生变化。第56页，本讲稿共61页运输问题二、运输问题的对偶问题 某一实际的运输问题可以叙述如下：有n个地区需要某种物资，需要量分别为 ，这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别为 ，已知从 i地区工厂至第j个需要地区单位物资的运价为 ，又 试阐述其对偶问题，并解释对偶变量的经济意义。第57页，本讲稿共61页运输问题三、运输问题的灵敏度分析已知某运输问题的供需关系及单价表如下表，销量产量销地产地245353312要求（1）用表上作业法找出最优调运方案。（2）分别讨论 使最优方案不变 的变化范围第58页，本讲稿共61页运输问题四、求解线性规划问题可转化为运可转化为运输问题来求输问题来求解解第59页，本讲稿共61页运输问题练习：n下表给出一个运输问题及它的一个解，411374611562销量产量销地产地853231第60页，本讲稿共61页运输问题n试问：（1）表中给出的解是否为最优解？（2）若 由1变为3，所给的解是否仍为最优解？若不是，求出新的最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？（4）若所有价值系数均增加1，最优解是否改变？为什么？（5）写出该问题的对偶问题，并给出其对偶问题的最优解。第61页，本讲稿共61页