32表上作业法.pptx

运输问题第三章第三章 运运输问题输问题前言前言n前两章讨论了一般线性规划问题的求解方法。但在实际工作中，往往碰到一些特殊的线性规划问题，它们的约束方程的系数具有特殊的结构，这样就有可能找到比单纯形法更为简单的求解方法。本章所讨论的运输问题就属于这样一类问题。第一节第一节 运输问题运输问题 及其数学模型及其数学模型 运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性。运输问题n典型背景物资运输调度问题 一般提法为：设某种物品有:m个产地：产量：n个销地：销量：从产地 到销地 的单位运价是 。求总运费最小的调度方案。运输问题n决策变量 表示由 到 的物品数量。销地产地销量产量运输问题n产销平衡问题总产量=总销量 即n产销不平衡问题总产量=总销量运输问题产销平衡问题的数学模型产量产量产量产量约束约束约束约束销量销量销量销量约束约束约束约束具有具有具有具有mnmn个变量，个变量，个变量，个变量，mmn n个等式约束条件的线型规划，可个等式约束条件的线型规划，可个等式约束条件的线型规划，可个等式约束条件的线型规划，可以用单纯形法求解以用单纯形法求解以用单纯形法求解以用单纯形法求解运输问题对产销平衡平衡问题约束条件（不包括非负约束）均为等式；产量之和=销量之和；约束条件的独立方程最多有m+n-1个。（约束条件中，前m行相加之和减去后n行相加之和结果是零向量，说明mn个行向量线性相关。可以证明，mn个约束方程中的任意mn1个方程都是线型无关的。非零变量的个数不大于独立的约束方程的个数，从而在运输表上填有数字的格子数不大于m+n-1个。）第二节第二节 运输问题的运输问题的 表上作业法表上作业法 由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法表上作业法。运输问题表上作业法n表上作业法是单纯形法在求解运输问题的一种简便方法。n单纯形法与表上作业法的关系：（1）找出初始基可行解 （2）求各非基变量的检验数（3）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同运输问题表上作业法换换基：基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否运输问题表上作业法举举例例说说明表上作明表上作业业法法例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地产地运输问题表上作业法第一步：确定初始基可行解第一步：确定初始基可行解第一步：确定初始基可行解第一步：确定初始基可行解 最小元素法、伏格最小元素法、伏格最小元素法、伏格最小元素法、伏格尔尔法法法法n 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目标函数值目标函数值用最小元素法求出的目标函数z246 一般说来，伏格尔法得出的一般说来，伏格尔法得出的初始解的质量最好，常用来作初始解的质量最好，常用来作为运输问题最优解的近似解。为运输问题最优解的近似解。运输问题表上作业法第二步：解的最第二步：解的最优优性性检验检验n闭回路法 思路：计算空格（非基变量）的检验数 若令则如何求检验数？分析：运费的增量即 增加1个单位 的检验数=相应的运费增量运输问题表上作业法4122854396111110销量产量销地产地82101468从初始表分析：要保证产销平衡，则 称为闭回路+1-1+1-1运输问题表上作业法4122854396111110销量产量销地产地8210146821运输问题表上作业法检验数表4122854396111110销量产量销地产地82101468211-11012表中的解不是最优解。运输问题表上作业法第三步：解的第三步：解的调调整整 调整位置（2，4）非空，回路角上的格至少一个为空，且保证数字的非负性。4122854396111110销量产量销地产地82101468-1（-2）（-2）（+2）（+2）运输问题表上作业法n调整后的解为：4122854396111110销量产量销地产地821214482209112此时的解为最优解。最优解不唯一运输问题表上作业法几点几点说说明：明：n当检验数为的负的变量超过两个，选择最小者对应的变量换入；n在最优解的表中，若有检验数=0，则该运输问题有最优解不唯一；n迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。运输问题表上作业法第二节 运输问题的 表上作业法