运输问题表上作业法

运输问题表上作业法Tag内容描述：<p>1、运输问题 表上作业法 问题描述 u已知有m个生产地点Si,i=1,2,m.可供应 某种物资，其供应量分别为ai, i=1,2,m. u有n个销地Dj,j=1,2,n,其需要量（填方） 分别为bj, j=1,2,n。 u从Si到Dj运输的物资量为Xij。 u从Si到Dj运输单位物资的运价（单价）为cij 。 u这些数据可汇总于产销（平衡表）和单位 运价表中 产销平衡表 单位运价表 思考 举例 确定初始调运方案最小元素法 u此方案是否为最优方案（即运费是否最低？） u“最小元素法”的缺点在哪里？有没有更好的方法，使得初 始方案更接近最优方案？ 最优性检验闭回路法 表示什么？ 每个空格都能。</p><p>2、运筹学课程设计报告书专业 班级 学号 姓名 LMZZ 日期 2011.09.01 设计题目：运输问题的表上作业法设计方案：运输问题是一种应用广泛的网络最优化模型，该问题的主要目的是为物资调运、车辆高度选择最经济的运输路线。有些问题，如m台机床加工零件问题、工厂合理布局问题，虽要求与提法不同，经适当变化也可以使用本模型求得最佳方案。运输问题的一般提法：某种物资有m个产地Ai，产量是ai（i1，2,m），有m个销售地Bi，销量(需求量)是bj(j=1,2,m)。若从Ai运到Bi单位运价为dij(i=1,2,m;j=1,2,m),又假设产销平衡，即。</p><p>3、4.2 表上作业法,表上作业法 表上作业法与单纯形法的关系 表上作业法的基本步骤 确定初始基可行解 最小元素法的基本步骤 伏格尔法,三、 运输问题的求解,运输问题的求解采用表上作业法，即用列表的方法求解线性规划问题中的运输模型的计算方法，实质上是单纯形法。,表上作业法是一种特定形式的单纯形法，它与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。,1.表上作业法,2.表上作业法与单纯形法的关系,表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解； 表上作业法中的“位势法”实质上是。</p><p>4、2 运输问题的表上作业法2.1初始解的求法同单纯形法一样，首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常见的是左上角法（或西北角法）、最小元素法和Vogl近似法(VAM)。后两法的效果较好，在此我们仅对最小元素法加以介绍。最小元素法的所谓元素就是指单位运价。此法的基本思想是：运价最便宜的优先调运，现通过例子来说明。例1 设有某种物质要从 三个仓库运往四个销售点 。各发点（仓库）的发货量、各收点（销售点）的收货量以及 到 的单位。</p><p>5、4.2表上作业法,表上作业法表上作业法与单纯形法的关系表上作业法的基本步骤确定初始基可行解最小元素法的基本步骤伏格尔法,三、运输问题的求解,运输问题的求解采用表上作业法，即用列表的方法求解线性规划问题中的运输模型的计算方法，实质上是单纯形法。,表上作业法是一种特定形式的单纯形法，它与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。,1.表上作业法,2.表上作业法与单纯形。</p><p>6、,1,7.4 表上作业法,一、表上作业法迭代步骤 1按某种规则找出一个初始基可行解； 2对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最优解，则停止计算，如不是最优解，则进行下一步骤； 3在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优解。,.,2,图 1运输问题求解思路图,.,3,二、初始基本可行解的确定,例2：甲、乙两个煤矿供应A、B、C。</p>