选择特殊符号
选择搜索类型
请输入搜索
运输问题是一类常见而且极其典型的线性规划问题。因此从理论上讲,运输问题也可用单纯形法来求解。但是由于运输问题数学模型具有特殊的结构,存在一种比单纯形法更简便的计算方法一表上作业法。表上作业法的实质仍是单纯形法。
表上作业法的计算步骤如下:
(1)用西北角规则或最小元素法确定初始基本可行解;
(2)用位势法求检验数;
(3)用闭回路调整法调整基本可行解。
定义1:将变量
所谓闭合回路,就是指在调运方案表中,从一个空格出发,沿水平或垂直方向前进,遇到一个适当的有数字的格子时,转90°继续前进,直到回到起始空格为止,形成一条由水平线段和垂直线段所组成的封闭折线 。
定义2:若一组格点经过适当的排序后,能写成以下形式:
则称这组格点构成了闭合回路。
如下图1中(1,1), (1,2),(3,2), (3,1)构成一个闭合回路。
闭回路调整法是借助图表作业方式,计算比较两种(或两种以上)变量值,以调整部分经济指标实现优化经营提高管理效益的管理统计方法。
用表上作业法求解运输问题时,可仿照一般的单纯形法,检验这个解的各个非基变量(对应运输表中是的空格)的检验数是否都是正数。若有某空格
为了计算出运输表中空格(非基变量)的检验数,引入闭回路的概念,使用闭回路可以直观地为满足约束条件换入变量增值后,再从原来的某一基变量中减去相应数值,变成数值为零的换出变量,完成换入换出即运量的调整。
下面举例说明闭回路调整法的计算步骤。下图2是一个产销平衡的运输问题的运输表并且已使用最小元素法填入了基变量。
蓝色方框中的是运价,橙色数字是基变量的值。如(A2,B1)表示从产地A2运送8个单位的货物到销地B1,其运价为2个单位。
首先考虑表中的空格(A1,B1),设想由产地A1供应1个单位的物品给销地B1,为使运入销地B1的物品总数量不大于它的销量,就应该将产地A2运到B1的物品数量减去一个单位,即将格子(A2,B1)中填入的数字8改为7;为了使由产地A2运出的物品正好等于它的产量,且保持新的到的解仍为基可行解,需将x23由原来的2增加1,改为3。然后将x13由10减去1,即变为9,以使运入销地B3的物品数量正好等于它的销量,同时使由A1运出的物品数量正好等于它的产量。显然,由于x11的的调整将影响到x21、x23、x13这三个变量的取值,即(A1,B1),(A2,B1),(A2,B2),(A1,B3)这四个格子中填入的数据。在运输表中,每一个空格都可以和一些有数字的格子用水平线段和垂直线段交替连接在一闭合回路上,而且这种闭合回路是唯一的。而且,运输问题的检验数的定义是产地到销地供给1个单位物品所引起的总运费的变化。非基变量或者说空格(A1,B1)的检验数σ11即由此引起的总运费变化是:σ11=c11-c21 c23-c13=4-2 3-4=1。可以看出在计算检验数时,符号在起点时为正,任意时针往下到下个顶点,此时符号为负,由此正负交替直到所有顶点包括进去。
检验方案的数据指标,编排各个闭合回路,这样的工作熟练可以在。现再看空格(A2,B2),它的闭回路的顶点由以下各格组成:(A2,B2),(A3,B2),(A3,B4),(A1,B4),(A1,B3),(A2,B3),最后再回到(A2,B2)。
在实际操作中由于涂改不便,熟练则可以不用编制各个闭合回路,在心中假想即可,其检验数为σ22=c22-c32 c34-c14 c13-c23=10-5 6-11 4-3=1。检验数为正数,表明修改这个基变量只会增加总运费,因此观察其他空格的检验数。
按照同样的方法,可得表中其他的非基变量的检验数如下:
σ12=c12-c32 c34-c14 c13=12-5 6-11=2
σ24=c24-c14 c13-c23=9-11 4-3=-1
σ31=c31-c21 c23-c13 c14-c34=8-2 3-4 11-6=10
σ33=c33-c34 c14-c14 c13=11-6-11 4=12
由于σ24=-1<0,故知表中的解不是最优解。
用上述闭回路法算出的初始调运方案中各个空格的检验数,表示在下图3的检验数表中。
若最优性检验时某非基变量
解改进的具体步骤为:
(1)
(2)以空格(Ai,Bj)为第一个奇数顶点,沿闭回路的顺(或逆)时针方向前进,对闭回路上的顶点依次编号;
(3)在闭回路上的所有偶数顶点集合L(e)中,找出运输量最小
(4)以
然后,再对得到的新解进行最优性检验,如不是最优解,就重复以上步骤继续进行调整,一直到得出最优解为止 。2100433B
1建设背景
1.建设背景 为全面贯彻中共中央《建立健全惩治和预防腐败体系 2000-2012 年工作规 划》、国务院《关于加强市县政府依法行政的决定》和《国务院办公厅转发监察 部等部门关于深入推进行政审批制度改革意见的通知》 (国办发 [2008]115 号) 精神要求,根据市委市政府关于《关于开展行政权力公开高效运行工作的意见》 (合发 [2008]25 号)精神,进一步深化行政审批制度改革,不断提高行政审批 工作效能,加大行政执法工作的透明性、公正性,促进服务型政府、透明政府、 廉洁型政府、绩效型政府的建设,结合合肥市的实际,特制定本需求方案。 2.电子政务现状 合肥市具备政务外网建设, 行政服务中心原有系统使用合肥市政务外网, 政 务外网的铺设已经到达各区和街道, 是党政机关公共业务网络, 与互联网逻辑隔 离,主要满足各级政府部门进行社会管理、 公共服务等面向社会服务的需要, 通 过将各局纳入政
两化融合背景下的工业结构调整和优化升级
工业机构作为组成经济结构的重要部分,经济结构得以进行调整的动力与发展方式是实现工业结构优化和升级重要内容。基于信息化和工业化融合发展的背景下,信息技术在优化和升级工业结构的过程中所产生的影响十分深刻,进而还能够成为整个工业结构得以进行持续化优化和升级的重要动力。
闭回路((loop)求解运输问题时产生的闭合回路。
在调运方案表中,从一个空格出发,沿水平或垂直方向前进;遇到一个适当的有数字的格子,则转90。前进;这样必会又遇到一个适当的有数字的格子,同样再转90“向前进.经若干次后,必然会回到出发的那个空格.这样形成一条由水平线与垂直线 构成的封闭折线,称为一个闭回路.2100433B
网孔分析法是回路分析法的特殊情况,即所选回路恰好是电路的网孔
使用回路法时回路的选取是个难点,所选择的回路必须是相互独立的,就是说用最少的回路数,能把每一条支路都包含在内,这样才能用最少的式子把所有的未知量包含在内。
一个电路的网孔恰好就是一组相互独立的回路,所以通常情况下我们都选用网孔来列回路电流方程。
选择非网孔的回路来使用回路法也有它的应用,比如某一处于两个网孔中间的支路,情况较复杂或数据很难算,如果用网孔法可能要把这个支路使用两遍,这时可以把其中一个网孔换成其它回路来避开它。2100433B
由于回路电流的选择有较大灵活性,当电路存在m个电流源时,假如能够让每个电流源支路只流过一个回路电流,就可利用电流源电流来确定该回路电流,从而可以少列写m个回路方程。网孔分析法只适用平面电路,回路分析是更普遍的分析方法。