运输问题和指派问题

《运输问题和指派问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章运输问题和指派问题第一节运输问题的数学模型运输问题的一般描述：某种物质（粮食、棉花、煤等）有若干个产地和销地，现在需要把物质从各个产地运往各个销地，产量总数等于销量总数，调运方案很多。若已知各产地的产量、各销地的销量以及各产地到销地的单位运价（或运输距离）。又假定运费和运输量成正比，问如何调运，才能使总运费最省？第一节运输问题的数学模型设Xij为第i个产地运往第j个销地的数量这是m×n个变量，约束条件为m+n个的线性规划问题。MinZ=CijXijxij=ai（i=1，2，…，m）xij=bj（j=1，2，…，n）xij≥0（i=1，2，…，m；j=1，2，…，n）第一节运输问

2、题的数学模型一、运输问题约束条件系数矩阵A=11…1111…1……………………………………………………11…111…1111……………………………………………………111（m+n）×（mn）第一节运输问题的数学模型二、运输问题的基变量共有m+n-1个三、m+n-1个变量构成基变量的充要条件是它们不构成闭合回路第二节表上作业法表上作业法求解运输问题的思路和单纯形法完全类似。建立作业表①确定初始调运方案②现行方案的最优性检验③现行方案的调整第二节表上作业法一、初始方案的确定：1.西北角法（左上角法）从表的左上角开始，保证产销平衡，每填上一个数划去一行或一列，直到有m+n-1行或列划去即可。填上数

3、字为基变量，从而保证其个数为m+n-1个又不构成闭合回路。第二节表上作业法一、初始方案的确定：2.最小元素法采用“就近供应”的思想。从运输表的运费最小的元素开始，保证产销平衡，每填上一个数划去一行或一列，直到有m+n-1行或列划去即可。填上数字为基变量，从而保证其个数为m+n-1个又不构成闭合回路。第二节表上作业法一、初始方案的确定：3.元素差额法（Vogel近似法）是在最小元素法基础上的改进。①求每行和每列的行罚数和列罚数从行罚数和列罚数最大的行或列的运费最小的元素开始，保证产销平衡，每填上一个数划去一行或一列。③重复①和②直到有m+n-1行或列划去即可。填上数字为基变量，从而保证其个数为

4、m+n-1个又不构成闭合回路。第二节表上作业法二、最优性检验1.闭合回路法：2.位势法：三、调整表上作业法的几点说明：1.若运输问题的某一基可行解有多个非基变量的检验数为负时，在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善，但通常取最小者对应的非基变量进基。2.当迭代到最优解时，有某非基变量的检验数为0时，则问题有无穷多最优解。3.当在表上作业时，同时划去了一行和一列运输价格时，就出现了退化，此时必须在当前划去的运价中某一空格填入一个0，表示该格中的变量是取值为0的基变量。第三节产销不平衡的运输问题一、产大于销的运输问题虚设销地，其需要量为∑ai-∑bj,相应的运费为0，化成产销

5、平衡的运输问题。MinZ=CijXijxij≤ai（i=1，2，…，m）xij=bj（j=1，2，…，n）xij≥0（i=1，2，…，m；j=1，2，…，n）第三节产销不平衡的运输问题一、销大于产的运输问题虚设产地，其产量为∑bj-∑ai,相应的运费为0，化成产销平衡的运输问题。MinZ=CijXijxij=ai（i=1，2，…，m）xij≤bj（j=1，2，…，n）xij≥0（i=1，2，…，m；j=1，2，…，n）第四节指派问题指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i人做第j事的费用为Cij（i，j=1，2，…，n），要求确定人和事之间的一一对应的

6、指派方案，使完成这件事的总费用最少。如任务人员ABCD甲乙丙丁210971541481314161141513914第四节指派问题一、指派问题的标准形式及其数学模型令1当指派第i人完成第j项任务0当不指派第i人完成第j项任务xij=minz=∑∑cijxij∑xij=1，j=1，2，…，n∑xij=1，i=1，2，…，nxij=1或015第四节指派问题二、指派问题的匈牙利解法标准的指派问题是一类特殊的0-1整数规划问题，可以用多种相应的解法来求解。但是，这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.König）的关于

7、矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙利解法。16第四节指派问题二、指派问题的匈牙利解法匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵C=（cij）n×n的某行（或某列）各元素分别减去一个常数k，得到一个新的系数矩阵C’=（c’ij）则以C和C’为系数矩阵的两个指派问题有相同的最优解。17匈牙利解法的一般步骤步骤一：变换系数矩阵。使其每行及每列至少有