资源描述：
《运筹学运输问题精品管理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划运输问题的典例例1.某食品公司经销的主要产品之一是糖果.它下面设有三个加工厂,每天的糖果产量分别为:A1-7t,A2-4t,A3-9t.该公司把这些糖果分别运往四个地区的门市销售,各地区每天的销售量分别为：B1-3t,B2-6t，B3-5t,B3-6t.已知从每个加工厂到各销售门市部每吨的运价如表所示，问该食品公司应如何调运,在满足各门市部销售需要的情况下，使得总的运费支出为最少.8291A251
2、047A3103113A1B4B3B2B1门市部加工厂表3-1单位：元/t运输问题的一般提法现有一批货物,从m个供应地运往n个销售地,Ai(i=1,‥‥,m)处有货物ai吨，Bj(j=1,‥‥,n)处需货物bj吨,已知从Ai到Bj的运价为cij元/吨.问如何安排，既可以满足各销地需要，又使总费用最小？A1A2Am︰︰B1B2Bn︰︰a1a2am︰︰b1b2bm︰︰供应量需求地供应地需求量调运量xij运输问题的框图表示产销表运输问题的数学模型单位运价表运输问题的数学模型运输表（运价，运量）作业表销量产量销地产地产销平衡条件下设xij为从产地Ai运往销地Bj的物
3、资数量(i=1,…m;j=1,…n）从Ai运出的物资总量应等于Ai的产量ai，xij应满足：运到Bj的物资总量应该等于Bj的销量bj，xij还应满足：运输问题的数学模型总运费为：运输问题的数学模型运输问题的数学模型1.约束条件都是等式约束2.总产量＝总销量产销平衡的运输问题的特点与性质3.系数矩阵是一个结构特殊的稀疏矩阵将约束方程组展开约束方程组共包含m×n个变量，(m+n)个约束条件产销平衡的运输问题的特点与性质产销平衡的运输问题的特点与性质系数矩阵A：m行n行矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；将矩阵分块,特点是:前m行构成
4、m个m×n阶矩阵,而且第k个矩阵只有第k行元素全为1,其余元素全为0（k=1,…,m）;后n行构成m个n阶单位阵。A的秩一般为m+n-1m行n行为什么？第i行第m+j行运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划表上作业法作业表（产销平衡表）：将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。表上作业法是单纯形法求解运输问题的一种简化方法，实质是单纯形法。但是具体计算和术语有所不同。销量产量销地产地运输问题
5、中寻找可行解1023206563销量95634748292171011433产量销地产地填有数字的格:对应运输问题解中的基变量取值，这里为3+4-1=6个空格：对应解中非基变量表上作业法的基本思想是:先设法给出一个初始方案(如典例所示),然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。表上作业法确定初始方案(初始基可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案——求解思路图表上作业法1.最小元素法2.沃格尔（Vogel）法(一)初始方案的给定给定初始方案的方法很
6、多(如前例)，一般来说，希望方法简便易行，并能给出较好的方案。减少迭代次数。这里介绍1.最小元素法基本思想：就近供应，即优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。销地产地产量311310719284741059销量3656203－3－31－1－1－4－4-6－66433－3－3-3-3销地产地产量311310719284741059销量365620316433Z=4*3+3*10+3*1+1*2+6*4+3*5=86最小元素法的说明退化现象：部分产量和＝部分销量和在迭代过程中，可能出现一行和一列同时被划去。销地产地产量311457
7、77384121069销量36562034－4－4－1－1-6－6616－3－3－6-60为使迭代过程中基变量的个数恰好为(m+n-1)个，应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量。以便当做有数字的格看待。销地产地产量31145777384121069销量365620346160基本思想：优选考虑最大差额（最小运价优势）方案行（列）差额（罚数）=次小运价系数-最小运价系数2.沃格尔（Vogel）法(差额法)行罚数列罚数1023206563销量95474891710113产量销地产地0112513()62200713
8、12121162()33()521108()1023
