管理运筹学第七章运输问题之表上作业法.pptxVIP

第七章运输问题之表上作业法一、运输问题模型及其求解思路二、确定初始基本可行解三、最优性检验四、方案调整五、几种特殊情况

问题的提出公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问：应如何调运可使总运输费用最小？一、运输问题模型及其求解思路

一、运输问题模型及其求解思路B1B2B3产量A1646200A2655300销量150150200

产销平衡运输问题模型的特点01从模型的建立可知：02列数为2（产地数）×3（销地数）＝6；03行数为2（产地数）+3（销地数）＝5；04再观察模型的系数矩阵：05一、运输问题模型及其求解思路

一、运输问题模型及其求解思路111000200000111300100100150010010150001001200前2行之和＝后3行之和

对于产销平衡的运输问题，若产地为m个，销地为n个，01则变量个数为m×n个，线性无关的约束条件个数为m+n-1，02故基本解中的基变量个数为m+n-1。03一、运输问题模型及其求解思路

运输问题求解思路——表上作业法01由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。02人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。03一、运输问题模型及其求解思路

运输问题模型及其求解思路我们关心的量均在运价表和运量表中，故将两表和为作业表：B1B2B3产量A16x114x126x13200A26x215x225x23300销量150150200

一、运输问题模型及其求解思路表上作业法的总体思路和单纯形法类似：基本可行解是否最优解结束换基是否每个步骤都充分利用运输表的特点

一、运输问题模型及其求解思路例：某食品公司下属的A1、A2、A3，3个厂生产方便食品，要运输到B1、B2、B3、B4，4个销售点，数据如下表，求最优运输方案。B1B2B3B4产量219284A3741059销量365620

二、确定初始基本可行解西北（左上）角法每次找最西北角的元素，让其运输量尽可能的满足一个约束条件。

二、确定初始基本可行解342236B1B2B3B4产量219284A3741059销量365620

这样得到的初始基本可行解为：01对应的总运费为：03x11=3,x12=4,x22=2,x23=2,x33=3,x34=6，其余均为0。023×3+4×11+2×9+2×2+3×10+6×5＝13504二、确定初始基本可行解

二、确定初始基本可行解最小元素法每次找到剩下的最小运价，让其对应的运输量尽可能的满足一个约束条件。

二、确定初始基本可行解343163B1B2B3B4产量219284A3741059销量365620

1用最小元素法求出的初始基本可行解为：2x21=3,x22=1,x13=4,x32=6,x34=3,x14=3,其余均为0。3对应的总运费为：43×1+1×2+4×3+6×4+3×5+3×10＝86二、确定初始基本可行解

为保证基变量的个数有m+n-1个，注意：每次填完数，只能划去一行或一列，只有最后一个格子例外。用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩下的空格中标上0。（退化的基本可行解）二、确定初始基本可行解

二、确定初始基本可行解353063B1B2B3B4产量219283A3741059销量365620

二、确定初始基本可行解340163B1B2B3B4产量219284A3741059销量365317

检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。运输问题中目标函数值要求最小化，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则不是。下面介绍两种计算检验数的方法：三、最优性检验

闭回路法闭回路：在已给出基本解的运输表上，