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

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