《运输问题》PPT课件

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

1、运输问题运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论例1：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为t）以及各工厂到各销售点的单位运价（元/t）示于下表中要求研究产品如何调运才能使总运费最小4.1运输问题及其数学模型单位销地运价产地产量2910291342584257销量3846A2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供应量供应地运价需求量需求地2910213428425运输问题网络图产量约束销量约束运输问题的一般提法是

2、：设某种物资有个产地各产地的产量是有个销地各销地的销量是假定从产地到销地运输单位物品的运价是，问怎样调运这些物品才能使总运费最小？销地产地产量销量运价表当产销平衡时，其模型如下：当产大于销时，其模型是：当产小于销时，其模型是：1、平衡运输问题必有可行解，也必有最优解；运输问题数学模型的特点证明记则令则为运输问题的一个可行解。事实上：又因所以故是一组可行解。又因为总费用不会为负值（存在下界）。这说明，运输问题既有可行解，又必然有下界存在，因此一定有最优解存在。2、运输问题约束条件的系数矩阵运输问题数学模型的特点对运输问题数学模型的结构约束加以整理，可知其系数矩

3、阵具有下述形式：m行n行1．运输问题是一个具有m×n个变量和n+m个等型约束的线性规划问题。（4－1）2．运输问题约束方程组的系数矩阵是一个只有0和1两个数值的稀疏矩阵,其中1的总数为2×m×n个。3、约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次4、约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总数是m+n-1证明：因A的前m行对应元素的和与后n行对应元素的和相等，恰好都是：所以A的行向量是线性相关的。从而r(A)≤m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1阶子式所

4、以r(A)=m+n-1.对于产销平衡运输问题，除了上述特点外，还有以下特点：1所有结构约束条件都是等式约束2各产地产量之和等于各销地销量之和3、运输问题的解运输问题数学模型的特点运输问题是一种线性规划问题。前面讲述的单纯形法是求解线性规划问题十分有效的一般方法，因而可用单纯形法求解运输问题。但是当用单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，这样一来，即使对于m=3、n=4这样简单的运输问题，变量数目也会达到19个之多。因此，我们利用运输问题数学模型的特点，引入了表上作业法来求解运输问题4.2用表上作业法求解运输问题表上作业法的基本思想：先

5、设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。初始化最优性检验迭代（Iteration）最优？yesSTOPno这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。例1某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2中，问如何调运才能使总运费最小？销地产地产量4124111621039108511622销量814121448表4-2该运输问题的数学模型为：可以证明：约束矩阵的秩r(A

6、)=m+n-1.基变量的个数为m+n-1.表上作业法计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2表上作业法计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2下面介绍三种常用的方法。一、给出运输问题的初始可行解（初始调运方案）最小元素法西北角法沃格尔(Vogel)法1。最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地产量4124111610398511622销量14121448表3-2①销地产地产量412411162109108511622销量8141448表3-2①②销地产地产量4121121091

7、08511622销量814121448表3-2①②③销地产地产量4121182109108116销量8121448表3-2①②③④销地产地产量412118210910811销量81248表3-2①③④⑤②销地产地产量4128210910811销量81248表3-2①③④⑤⑥⑥②此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).⒉西北角法西北角法是优先满足运输表中西北角（左上角）上空格的供销需求。销地产地产量412411210391085116

8、22销量14121448表3-2销地产地产量4124