管理运筹学--第七章-运输问题之表上作业法说课讲解

第七章运输问题之表上作业法一、运输问题模型及其求解思路二、确定初始基本可行解三、最优性检验四、方案调整五、几种特殊情况一、运输问题模型及其求解思路1、问题的提出:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问:应如何调运可使总运输费用最小?一、运输问题模型及其求解思路2、产销平衡运输问题模型的特点从模型的建立可知:列数为2(产地数)×3(销地数)=6;行数为2(产地数)+3(销地数)=5;再观察模型的系数矩阵:一、运输问题模型及其求解思路111000200000111300100100150010010150001001200前2行之和=后3行之和一、运输问题模型及其求解思路对于产销平衡的运输问题,若产地为m个,销地为n个,则变量个数为m×n个,线性无关的约束条件个数为m+n-1,故基本解中的基变量个数为m+n-1。一、运输问题模型及其求解思路3、运输问题求解思路——表上作业法由于运输规划系数矩阵的特殊性,如果直接使用线性规划单纯形法求解计算,则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。一、运输问题模型及其求解思路B1B2B3产量A16x114x126x13200A26x215x225x23300销量150150200我们关心的量均在运价表和运量表中,故将两表和为作业表:一、运输问题模型及其求解思路表上作业法的总体思路和单纯形法类似:基本可行解是否最优解结束换基是否每个步骤都充分利用运输表的特点一、运输问题模型及其求解思路例:某食品公司下属的A1、A2、A3,3个厂生产方便食品,要运输到B1、B2、B3、B4,4个销售点,数据如下表,求最优运输方案。B1B2B3B4产量A13113107A219284A3741059销量365620