第四章运输问题

第四章运输问题第1页，共61页，2023年，2月20日，星期三第一节运输问题及其数学模型

运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶变量与原问题检验数的关系。第2页，共61页，2023年，2月20日，星期三运输问题典型背景——单一物资运输调度问题设某种物品有:m个产地：产量：

n个销地：销量：从产地到销地的单位运价是。

求总运费最小的调度方案。第3页，共61页，2023年，2月20日，星期三运输问题决策变量表示由到的物品数量。销地产地销量产量第4页，共61页，2023年，2月20日，星期三运输问题产销平衡问题——总产量=总销量即产销不平衡问题——总产量=总销量第5页，共61页，2023年，2月20日，星期三运输问题产销平衡问题的数学模型第6页，共61页，2023年，2月20日，星期三运输问题运输问题数学模型的特点运输问题有有限最优解运输问题约束条件的系数矩阵（下页）约束条件系数矩阵每一列只有两个1，其余为0；

对产销平衡问题约束条件均为等式，且产量之和=销量之和；约束条件的独立方程最多有m+n-1个，即第7页，共61页，2023年，2月20日，星期三运输问题mn第8页，共61页，2023年，2月20日，星期三运输问题ij其中第9页，共61页，2023年，2月20日，星期三运输问题运输问题的对偶问题

——对偶变量与原问题检验数的关系对产销平衡运输问题，若用分别表示前m个约束等式相应的对偶变量，用分别表示后n个约束等式相应的对偶变量，即对偶变量为第10页，共61页，2023年，2月20日，星期三运输问题运输问题的对偶问题可写为运输问题的对偶问题

——对偶变量与原问题检验数的关系第11页，共61页，2023年，2月20日，星期三运输问题线性规划问题变量的检验数为运输问题的对偶问题

——对偶变量与原问题检验数的关系变量的检验数为第12页，共61页，2023年，2月20日，星期三运输问题设运输问题的一个基可行解的变量为由于基变量的检验数为零，故有运输问题的对偶问题

——对偶变量与原问题检验数的关系第13页，共61页，2023年，2月20日，星期三运输问题方程组含有m+n-1个方程，m+n个变量可证明方程组有解，且不唯一。求出方程组的解（称为位势）则变量的检验数为运输问题的对偶问题

——对偶变量与原问题检验数的关系求运输问题检验数的一种方法第14页，共61页，2023年，2月20日，星期三第二节运输问题的表上作业法由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。第15页，共61页，2023年，2月20日，星期三运输问题表上作业法是单纯形法在求解运输问题的一种简便方法。单纯形法与表上作业法的关系：（1）找出初始基可行解（2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同第16页，共61页，2023年，2月20日，星期三运输问题换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否第17页，共61页，2023年，2月20日，星期三运输问题举例说明表上作业法例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地第18页，共61页，2023年，2月20日，星期三运输问题第一步：确定初始基可行解

——最小元素法、伏格尔法最小元素法思路：从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。第19页，共61页，2023年，2月20日，星期三运输问题最小元素法举例4122854396111110销量产量销地产地822010100614868000060第20页，共61页，2023年，2月20日，星期三运输问题最小元素法举例4122854396111110销量产量销地产地82101468最小元素法缺点：会出现顾此失彼（运费差额问题）考虑运价差第21页，共61页，2023年，2月20日，星期三运输问题

罚数（即差额）=次小运价-最小运价罚数（或差额）的解释：差额大，则不按最小运费调运，运费增加大。差额小，则不按最小运费调运，运费增加不大。对差额最大处，采用最小运费调运。伏格尔法思路：第22页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①04-4=0第一次第23页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①013-2=1第一次第24页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①011第一次第25页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①011列罚数4-2=22153①第一次第26页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。4122854396111110销量产量销地产地行罚数①011列罚数2153①1480优先安排销地，否则运价会更高下次不考虑该列第一次第27页，共61页，2023年，2月20日，星期三运输问题第二次结合例1说明这种方法。行罚数②012列罚数213②优先安排销地，否则运价会更高84122854396111110销量产量销地产地148006下次不考虑该行第28页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。行罚数③01列罚数212③84122854396111110销量产量销地产地148006下次不考虑该列802第三次第29页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。行罚数④76列罚数12④84122854396111110销量产量销地产地1480068024120下次不考虑该列第四次第30页，共61页，2023年，2月20日，星期三运输问题结合例1说明这种方法。行罚数⑤00列罚数2⑤4284122854396111110销量产量销地产地1480068024120000第五次第31页，共61页，2023年，2月20日，星期三运输问题例1用伏格尔法得到的初始基可行解4122854396111110销量产量销地产地48148122目标函数值用最小元素法求出的目标函数z=246一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。第32页，共61页，2023年，2月20日，星期三运输问题第二步：解的最优性检验闭回路法思路：计算空格（非基变量）的检验数

若令则如何求检验数？分析：——运费的增量即增加1个单位的检验数=相应的运费增量第33页，共61页，2023年，2月20日，星期三运输问题4122854396111110销量产量销地产地82101468从初始表分析：要保证产销平衡，则称为闭回路+1-1+1-1第34页，共61页，2023年，2月20日，星期三运输问题4122854396111110销量产量销地产地8210146821第35页，共61页，2023年，2月20日，星期三运输问题检验数表4122854396111110销量产量销地产地82101468211-11012表中的解不是最优解。第36页，共61页，2023年，2月20日，星期三运输问题第三步：解的调整

调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。4122854396111110销量产量销地产地82101468-1（-2）（-2）（+2）（+2）第37页，共61页，2023年，2月20日，星期三运输问题调整后的解为：4122854396111110销量产量销地产地821214482209112此时的解为最优解。有无穷多最优解第38页，共61页，2023年，2月20日，星期三运输问题几点说明：当检验数为的负的变量超过两个，选择最小者对应的变量换入；在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。第39页，共61页，2023年，2月20日，星期三运输问题讨论内容：初始调运方案（初始基可行解）

——西北角法解的最优性检验——对偶变量法（或称位势法）还有其它的方法吗？根据第一节运输问题对偶问题与原问题的检验数的关系第40页，共61页，2023年，2月20日，星期三第三节运输问题的进一步讨论上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论：二、有转运的运输问题一、产销不平衡的运输问题并附有运输问题的思考题及练习题第41页，共61页，2023年，2月20日，星期三运输问题一、产销不平衡的运输问题（Ⅰ）若总产量大于总销量，即令假象销地的销量为：第42页，共61页，2023年，2月20日，星期三运输问题决策变量表示由到的物品数量。销地产地销量产量注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。第43页，共61页，2023年，2月20日，星期三运输问题原产大于销平衡问题的数学模型第44页，共61页，2023年，2月20日，星期三运输问题修改后产大于销平衡问题的数学模型第45页，共61页，2023年，2月20日，星期三运输问题（Ⅱ）若总产量小于总销量，即令假象产地的销量为：一、产销不平衡的运输问题仿照上述类似处理。第46页，共61页，2023年，2月20日，星期三运输问题举例说明某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地第47页，共61页，2023年，2月20日，星期三运输问题二、有转运的运输问题中间转运站——产地、销地、中转站。建模思路：从发送及接受角度考虑。产地转运销地发送量产地转运销地接受量第48页，共61页，2023年，2月20日，星期三运输问题应用问题举例例1、水泥调运的产销不平衡情况及运价如下表，求最好的调运方案。21110783592143销量产量销地产地第49页，共61页，2023年，2月20日，星期三运输问题最优方案为：21110783592143销量产量销地产地000第50页，共61页，2023年，2月20日，星期三运输问题例2、某农场有土地900亩，分为三类，计划种植三种作物，情况如下表，求使作物总产量最多的布局方案。500销量产量销地产地700700850480600300400500第51页，共61页，2023年，2月20日，星期三运输问题解：目标函数最大，可用最大元素法，即是按产量高的优先安排的原则。500销量产量销地产地700700850480600300400500100300100400050第52页，共61页，2023年，2月20日，星期三运输问题调整：500销量产量销地产地7007008504806003004005001002002004000可验证此时为最优解。第53页，共61页，2023年，2月20日，星期三运输问题讨论第54页，共61页，2023年，2月20日，星期三运输问题一、概念题（判断）1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含（m+n-1）个非零的，且满足

就可以作为一个初始基可行解。第55页，共61页，2023年，2月20日，星期三运输问题3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。6、如果…...分别乘上一个常k,…...不会发生变化。第56页，共61页，2023年，2月20日，星期三运输问题二、运输问题的对偶问题

某一实际的运输问题可以叙述如下：有n个地区需要某种物资，需要量分别为