【教学课件】第四章运输问题.ppt

《【教学课件】第四章运输问题.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第四章运输问题.ppt（61页珍藏版）》请在三一办公上搜索。

1、,第四章 运输问题,4.1 运输问题4.2 运输问题的表上作业法4.3 运输问题的进一步讨论,第一节 运输问题 及其数学模型,运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶变量与原问题检验数的关系。,典型背景单一物资运输调度问题 设某种物品有:m个产地：产量：n个销地：销量：从产地 到销地 的单位运价是。求总运费最小的调度方案。,决策变量 表示由 到 的物品数量。,产销平衡问题总产量=总销量 即产销不平衡问题总产量=总销量,产销平衡问题的数学模型,运输问题数学模型的特点,运输问题有有限最优解运输问题约束条件的系数矩阵

2、（下页）约束条件系数矩阵每一列只有两个1，其余为0；对产销平衡问题约束条件均为等式，且产量之和=销量之和；约束条件的独立方程最多有m+n-1个，即,i,j,其中,运输问题的对偶问题对偶变量与原问题检验数的关系,对产销平衡运输问题，若用 分别表示前m个约束等式相应的对偶变量，用 分别表示后n个约束等式相应的对偶变量，即对偶变量为,运输问题的对偶问题可写为,运输问题的对偶问题对偶变量与原问题检验数的关系,线性规划问题变量 的检验数为,运输问题的对偶问题对偶变量与原问题检验数的关系,变量 的检验数为,设运输问题的一个基可行解的变量为,由于基变量的检验数为零，故有,运输问题的对偶问题对偶变量与原问题检

3、验数的关系,方程组含有m+n-1个方程，m+n个变量可证明方程组有解，且不唯一。求出方程组的解（称为位势）,则变量 的检验数为,运输问题的对偶问题对偶变量与原问题检验数的关系,第二节 运输问题的 表上作业法,由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法表上作业法。,表上作业法是单纯形法在求解运输问题的一种简便方法。单纯形法与表上作业法的关系：（1）找出初始基可行解（2）求各非基变量的检验数（3）判断是否最优解,换基：,（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。,停止,举例说明表

4、上作业法,例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：,第一步：确定初始基可行解 最小元素法、伏格尔法,最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。,最小元素法举例,8,2,2,0,10,10,0,6,14,8,6,8,0,0,0,0,6,0,最小元素法举例,最小元素法缺点：会出现顾此失彼（运费差额问题）,考虑运价差,罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。,对差额最大处，采用最小运费调运。,伏格尔法思路：,结合例1说明这种方法。

5、,0,4-4=0,第一次,结合例1说明这种方法。,1,3-2=1,第一次,结合例1说明这种方法。,1,第一次,结合例1说明这种方法。,4-2=2,2,1,5,3,第一次,结合例1说明这种方法。,14,8,0,优先安排销地，否则运价会更高,下次不考虑该列,第一次,第二次,结合例1说明这种方法。,优先安排销地，否则运价会更高,8,0,6,下次不考虑该行,结合例1说明这种方法。,下次不考虑该列,8,0,2,第三次,结合例1说明这种方法。,4,12,0,下次不考虑该列,第四次,结合例1说明这种方法。,4,2,0,0,0,第五次,例1用伏格尔法得到的初始基可行解,目标函数值,用最小元素法求出的目标函数z

6、=246,一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。,第二步：解的最优性检验,闭回路法 思路：计算空格（非基变量）的检验数,若令则,如何求检验数？,分析：,即 增加1个单位 的检验数=相应的运费增量,从初始表分析：,要保证产销平衡，则,称为闭回路,+1,-1,+1,-1,2,1,检验数表,2,1,1,-1,10,12,表中的解不是最优解。,第三步：解的调整,调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。,（-2）,（-2）,（+2）,（+2）,调整后的解为：,此时的解为最优解。,有无穷多最优解,几点说明：,当检验数为的负的变量超过两个，选择

7、最小者对应的变量换入；在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。,讨论内容：,初始调运方案（初始基可行解）西北角法解的最优性检验对偶变量法（或称位势法）,还有其它的方法吗？,根据第一节运输问题对偶问题与原问题的检验数的关系,第三节 运输问题的 进一步讨论,一、产销不平衡的运输问题,（）若总产量大于总销量，即,令假象销地的销量为：,决策变量 表示由 到 的物品数量。,注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。,原产大于销平衡问题的数学模型,修

8、改后产大于销平衡问题的数学模型,（）若总产量小于总销量，即,令假象产地的销量为：,一、产销不平衡的运输问题,仿照上述类似处理。,举例说明,某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：,二、有转运的运输问题,中间转运站产地、销地、中转站。建模思路：从发送及接受角度考虑。,产地 转运 销地 发送量产地转运销地接受量,应用问题举例,例1、水泥调运的产销不平衡情况及运价如下表，求最好的调运方案。,最优方案为：,2,11,10,7,8,3,5,9,2,1,4,3,销量,产量,销地,产地,0,0,0,例2、某农场有土地900亩，分为三类，计划种植三种作物，情况如下表，求使作物总产量

9、最多的布局方案。,解：目标函数最大，可用最大元素法，即是按产量高的优先安排的原则。,50,调整：,可验证此时为最优解。,运输问题,讨论,一、概念题（判断）,1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含（m+n-1）个非零的，且满足 就可以作为一个初始基可行解。,3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。6、如果.分别乘上一个常k,.不会发

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