产销平衡运输问题的表上作业法解法的一个注记20
上亿文档资料，等你来发现
产销平衡运输问题的表上作业法解法的一个注记20
第14卷第4期2005年8月；运筹与管理；OPERATIONSRESEARCHANDMAN；Vol.14,No.4；Aug.2005；产销平衡运输问题的表上作业法解法的一个注记；谢凡荣；(南昌大学数学系,江西南昌330047)；摘要:”,利用该规则可以避免可能存在的多余计算；2manipulationMethodforSo；ProblemWithBalanc
第14卷　第4期2005年8月　运　筹　与　管　理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEVol.14,No.4Aug.2005　产销平衡运输问题的表上作业法解法的一个注记谢凡荣(南昌大学数学系,江西南昌330047)摘　要:”,利用该规则可以避免可能存在的多余计算。,该方法与求解指派问题的常用方法“匈牙利法”相比,。关键词:运筹学;运输问题;;;中图分类号:O157.6　　　)2manipulationMethodforSolvingtheProblemWithBalancedSupplyandDemandXIEFan2rong(MathematicsDepartment,NanchangUniversity,Nanchang330047,China)Abstract:Whilethetable2manipulationmethodisusedtosolvethetransportionproblemwithbalancedsupplyanddemandandthereexisitsthecaseofdegeneration2solution,moreaccuraterules,whichcanavoidthepos2siblyexistingredundantcalculation,arepresentedforfillingzeroincorrespondingblanketofthebalancedtableinthepaper.Themethodandprocedure,bywhichtheimprovedtable2manipulationmethodisusedtosolvetheassignmentproblem,arealsopresentedinthepaper,andthemethodhastheadvantageofmoresim2plicityandconvenienceovertheHungaryMethodoftenusedforsolvingtheassignmentproblemwhilemanualcalculationisadopted.Keywords:thetthetransportionproblemwithbalthetable2manipulationmethod0　引言本文未特别申明的有关概念和记号与文献[1]相同。文献[1]给出了产销平衡运输问题的表上作业法解法,还给出了把产销不平衡运输问题化为产销平衡运输问题的方法。手工计算时,表上作业法是求解运输问题的常用方法。求解产销平衡运输问题的表上作业法的步骤可用框图描述如图1。文献[1](p89290)指出:“用表上作业法求解产销平衡运输问题当出现退化时,在相应空格中一定要填一个‘0’,以此表示为数字格。有以下两种情况:图1　求能产销平衡运输问题表上作业法框图收稿日期:作者简介:谢凡荣(19662),男,湖南邵阳人,南昌大学数学系副教授,硕士,研究方向为运筹学及其计算机应用。第4期　　　　　　　　谢凡荣:产销平衡运输问题的表上作业法解法的一个注记45(1)当确定初始解(初始可行方案)的各供需关系时,若在(i,j)格填入某数字后,出现Ai处的余量等于Bj处的需量。这时在产销平稳表上填一个数,而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格,这时需要添一个,它的位置可在对应同时划去的那行或那列的‘0’任一空格处。(2)在用闭回路法调整时,在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后,得到退化解。这时有一个数字格必填上一个0,表明它是基变量。当出现退化解后,并作改进调整时,可能在某个闭回路上有标记为(-1)的取值为0的数字格,这时应取调整量θ=0。”可以看出,文献[1]并没指出在相应空格填“0”的确切位置([2,3]),这种不确定性有可能造成不必要的多余计算。下面举例加以说明。例1　(取自文献[1]p89):有一个运输问题,、。表1　(产销表)产地A1A3B1B2B342(运价表)74产地　　　　A1A2A3B1B2B3B43114310…586…7…736569销量…1……2…表3　(产销表)销地产地A1A2A3B1B2B3B4表4　(运价表)产量74 96销地产地　　　　A1A2A3B1B2B3B4产量749143366561 336654606销量销量用最小元素法确定初始基可行解(初始可行调运方案):因第一次划去运价表的第一列,剩下最小元素2,其对应的销地B2,需要量为6,而对应的产地A3未分配量也是6。这时在产销(3,2)交叉格中填入6,(2,2)、(3,3)、(3,4)中选一空格添这时在单位运价表1中需同时划去B2列A3行。在表1的空格(1,2)、加一个0,不难发现:(1)选空格(3,4)添加一个0时,得初始可行调运方案如表3,用位势法计算空格(非基变量)的检验数,知所有检验数满足最优准则(≥0),推得表3给出的方案已是最优解(最优方案);(2)选空格(2,2)添加一个0时,得初始可行调运方案如表4,用位势法计算空格(非基变量)的检验数,空格(1,1)的检验数为σ事11=-4,不能推得表4给出的方案已是最优解,按表上作业法的步骤还需要对其调整。实上,表3和表4给出的方案是相同的方案。(3)选空格(3,3)或(1,2)添加一个0时,出现的情况与(2)类(2,2)、(3,3)、(3,4)中最小。似。究其原因,是空格(3,4)对应单位运价在(1,2)、于是,我们得到用表上作业法求解产销平衡运输问题当出现退化时在相应空格填“0”的更为明确的规则如下:规则1　当确定初始解(初始可行方案)的各供需关系时,若在(i,j)格填入某数字后,出现Ai处的余量等于Bj处的需量。这时在产销平稳表上填一个数,而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格,这时需要添一个,它的位置是在对应这时同时划去的那行‘0’或那列的所有空格处中对应单位运价最小的任一空格。规则2　在用闭回路法调整时,在闭回路上出现r(≥2)个具有(-1)标记的相等的最小值。这时只能选择其中一个作为调出格。而经调整后,得到退化解。这时有(r-1)个数字格必填上0,它们的位置是在闭回路上具有(-1)标记的调运量为0的对应单位运价最小的(r-1)个的数字格,表明它们是基变量。当出现退化解后,并作改进调整时,可能在某个闭回路上有标记为(-1)的取值为0的数字格,这时应取调整量θ=0;并把闭回路上标记为(-1)取值为0的数字格中对应单位运价最大的一个数字格变为调出格(空格),其它的数字格不变,调入格填上0。46运　筹　与　管　理　　　　　　　　　　2005年第14卷我们有以下结论:定理1　用表上作业法求解产销平衡运输问题当出现退化时,按规则1和规则2在相应空格填“0”,可以避免可能存在的多余计算。利用定理1和求解产销平衡运输问题的表上作业法,我们有对文献[4]作改进的求解极小化指派问题的表上作业法如下:Step1　把指派问题看作产地数和销地数相等的产销平衡运输问题,人员对应于产地,任务对应于销地,指派问题的效率矩阵(表)对应于运输问题的单位运价矩阵(表),所有产地的产量以及所有销地的销量都为1。Step2　按求解产销平衡运输问题的表上作业法的框图1和规则1和规则2对应的运输问题。此时求得的最优解即对应于指派问题的最优解。对于极大化指派问题,可先按文献[1],。例2　(取自文献)[1]p131例8)求表5表5任务丙丁戊ACDE表6产地甲乙丙丁戊销量ABCDE产量11111128715496126776146109691091111110110001　　　11解　按求解指派问题的表上作业法,先用最小元素法求得初始基可行解(初始可行调运方案)如表6,用位势法计算空格(非基变量)的检验数(见表7),只有空格(1,4)(即(甲,D))的检验数σ14=-2&0,找(1,5)标-1,在空格(1,4)、(2,5)标+1,得闭回路(1,4)→(2,4)→(2,5)→(1,5)→(1,4),在空格(2,4)、求得调整量θ=0,调整后得在表6中空格(1,4)填0,表6中数字格(1,5)的0去掉,重新用位势法计算空格(非基变量)的检验数(见表8),此时所有检验数≥0,因此表6对应的方案即为最优指派方案;由于此时σ这与[1]的结果完全吻合。这个例子表明,用改进23=-0,用闭回路法调整,又可得另一最优指派方案。后的表上作业法求解指派问题,与求解指派问题的常用方法“匈牙利法”相比,具有手工计算更为简便的优点。表7任务人员甲乙丙丁戊vjABCDEui表8任务人员甲乙丙丁戊vjABCDEui128715⑦96127⑨⑥⑨10990-30-3-2128715⑦9612⑥14　　　⑦⑥1490-12-10⑥⑨1097⑥⑦9⑥109④6④4⑥⑦7⑥107参考文献:[1]钱颂迪.运筹学[M].北京:清华大学出版社,1990.[2]魏权龄,胡显佑,黄志民.运筹学简明教程[M].北京:中国人民大学出版社,1996.[3]韩伯棠.管理运筹学[M].北京:高等教育出版社,2000.[4]高俊琦.指派问题的表上作业解法[J].运筹与管理,):64268.包含各类专业文献、文学作品欣赏、行业资料、外语学习资料、高等教育、幼儿教育、小学教育、产销平衡运输问题的表上作业法解法的一个注记20等内容。
　产销平衡时的运输问题。 表上作业法是单纯形在求解产销平衡运输问题的一种既 简单又非常重要的求解方法。因为,运输问题是线性规划问题,可以用线性规划 中的单纯形... 　分 得分:4 产地数与销地数不相等的运输问题,一定不是产销平衡运输问题。 A. 错误 B. 正确 满分:4 5. 分 得分:4 表上作业法可以理解为求解运输问题的单纯... 　在产销平衡运输问题中,设产地为 m 个,销地为 n...() 5、运输问题是一种特殊的线性规划模型,因而求解...3、(15 分)用表上作业法求下表中给出的运输问题... 　表上作业法在物资运输问题中的应用 讨论了产销平衡运输问题的表上作业法,利用 ...求解初始基本可行解的方 法很多 , 最常见的是西北角法 , 最小元素法和差额... 　在表上作业法中,调运方案中有数字的格为( C ) ...求解不平衡的运输问题的基本思想是(设立虚供地或虚...在 产销平衡表上填一个数, 运价表上就要同时划... 　产销平衡的表上作业法 2页 免费表上作...结合运输问题的具体特性须用表上作业的方 法求解。...并分别记为 α i 和β j ( i =1,2,3; j ... 　运筹学的主要内容之一运输问题这种线性规划, 其最主要解法是表上作业法,一般表上作业法求最优 解至少要经历下面几个步骤: 一、根据运输表(即产销平衡与单位运... 　m 个产地, n 个销地的产销平衡运输问题模型中,下列叙述不正确的是( A.有 ...应用表上作业法求解时,运输问题的初始方案必须( A.用最小元素法获得 C.包含 ... 　8. 试给出运输问题的对偶问题(对产销平衡问题) . 9. 如何把一个产销不...4.表上作业法实质上就是求解运输问题的单纯形法. 5.按最小元素法或元素差额...914.3产销不平衡的运输问题
上亿文档资料，等你来发现
914.3产销不平衡的运输问题
运筹学；第四章运输问题；第四章运输问题；§3产销不平衡的运输问题；前面讨论的运输问题的理论和方法，都是以产销平衡，；ai＜?bj?2.供不应求的情况，即i?1j?；与产大于销类似，当销大于产时，可以在产销平衡表中；在产销不平衡问题中，如果某产地不允许将多余物资就；例2设有A1、A2、A3三个产地生产某种物资，其；B2、B3三个销地需要该物资，销量分别为4
运 筹 学第四章 运输问题第四章 运输问题§3 产销不平衡的运输问题前面讨论的运输问题的理论和方法，都是以产销平衡，即 m n ai ? ?bj ? i?1 j?1 为前提的。但是在实际问题中产销往往是不平衡的。对于产销 不平衡的运输问题，可以把它们先转化成产销平衡问题，然后 再用表上作业法求解。 m n a b ? i＞ ? j 1.产大于销的情况，即 i ?1 j?1 由于总产量大于总销量，就要考虑多余的物资在哪些产地就地 贮存问题。将各产地的仓库设成一个假想销地 Bn+1，该地总需 m n 求量为 bn ?1 ? ? ai ? ? b j i ?1 j ?1 再令运价表中各地到虚设销地Bn+1的单位运价Ci,n+1 =0,i=1,2…m ，则该问题就转化成一个产销平衡问题，可以用表上作业法求 解了。在最优解中，产地Ai到虚设销地Bn+1的运量实际上就是 产地Ai就地贮存的多余物资数量。ai ＜ ?bj ? 2.供不应求的情况，即 i ?1 j?1mn与产大于销类似，当销大于产时，可以在产销平衡表中虚设一个产 n m 地Am+1 ，该产地的产量为 am ? 1 ? ?bj ? ?ai j?1 i?1 再令虚设产地Am+1到各销地的单位运价Cm+1,j=0,j=1,2…n，则问题 可以转化为一个产销平衡的运输问题。在最优解中，虚设产地Am+1 到销地Bj的运量实际上就是最后分配方案中销地Bj的缺货量。在产销不平衡问题中，如果某产地不允许将多余物资就地贮存， 或不允许缺货，则要令相应运价Ci,n+1或Cm+1,j=M（M是相当大正数）例2 设有A1、A2、A3三个产地生产某种物资，其产量分别为5，6，8 吨，B1、B2、B3三个销地需要该物资，销量分别为4，8，6 吨，又已知各产销地之间的单 位运价如下表所列，试确定总运费最少的调运方案。 销地 产地 A1 A2 A3 销量 B1 B2 B3 3 4 2 4 1 3 6 2 8 5 8 6 产量 5 6 8解：产地总产量为19 吨， 销地总销量为18 吨，产 大于销。故虚设销地B4， 令其销量b4=1 吨，运价 Ci4=0，i=1,2,3,则问题变 成如下运输问题：销地 产地 A1 A2 A3B1 B2 B33 4 2 1 3 6 2 8 5B4 0 0 0产 量5 6 8销地 产地 A1 A2 A3 vjB1 B2B3B4ui（8） 4（10） 1 0 0 （-4） 6 （-9） 9 4 4 （5）（-7） 7 -5 1 -7 0销量48 61（1）用最小元素法得初始 方案如下表所示：销地 产地 B1 B2 B3 0 4 4 B4 产 量（3）第一次调整量θ=0，调整 后的方案如下表所示：销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 4 4 4 4 6 1 0 1 产 量 5 6 8A1 A2 A3销量44615 6 88 61（2） 用位势法计算检验数 如黄表所示：8 6（4）再用位势法计算检验数 如下表所示：销地 产地 A1 A2 A3 vj B1 B2 B3 B4 ui 销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 3 4 2 4 1 3 6 2 8 5 8 6 0 0 0 1 产 量 5 6 8（8） 4（1） 1 0 （9） （5 ） 6 0 0 （-4）（-7） 7 4 4-5120（5）第二次调整量θ=1，调 整后的方案如下表所示：销地 产地 A1 A2 A3 销量（6）再用位势法计算检验数如 下表所示：销地 产地 A1 A2 A3 vjB1 B2 B3 B45 6 6 0 1 1产 量 5 6 8B1B2 B3B4ui43（8） 5（8）（7） 0 （2） （-2） 6 0 7 4 3（3） 1 7 -5 1 -5 -74 8（7）第三次调整量θ=0， 调整后的方案如下表所示：销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 5 0 3 6 6 产 量 5 6 8 销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 3 4 2 4 1 3 6 2 8 5 8 6 0 0 0 1 产 量 5 6 841 14 8（8）再用位势法计算检验 数如下表所示：销地 产地 A1 A2 A3 vjB1B2 B3B4ui左表中所有检验数均非负。所 以已是最优解。最小总运费： 5×1+6×2+4×2+3×8+1×0 =49（8） 5（6）（7） 0 （4） 0 6 （2） 5 4 3（1） 1 7 -5 1 -3 -7包含各类专业文献、生活休闲娱乐、中学教育、应用写作文书、高等教育、914.3产销不平衡的运输问题等内容。
　Lingo软件解决产销不平衡的运输问题_理学_高等教育_教育专区。Lingo软件解决产销不平衡的运输问题 产销不平衡的运输问题 产地 产量 A1 A2 A3 A4 A5 销量 B1 6... 　能够进行 产销平衡与产销不平衡的运输问题的优化安排。 重点问题 运输问题表上...表 4.3 运输价格表 销地 B1 B2 ? Bn 产量 产地 A1 c11 c12 ? c1n s1 ... 　发现该元素的行和列的产量等于销量,此时, 在产销平衡表上填一个数,此时运价表上就要同时划去一行或一列.(不正确) 13.最小元素法为求运输问题的最优方案的... 　31 已知运输问题的产销平衡表与单位运价表如表3-35至3-_教学反思/汇报_教学研究_教育专区。31 已知运输问题的产销平衡表与单位运价表如表3-35至3-3.1... 　解: 1、无条件运输问题的运输模型(大于产的产销不平衡运输问题) : A 甲乙丙丁 各地销量 0.03 0.03 0.02 -0.01 200 B 0.08 0.02 0.06 0.05 150 ... 　第四次读书报告(运输问题中的产销不平衡问题)一、问题提出:重庆有三家电子厂分别是新普,隆宇和恒华,生产的笔记本电脑 将要运向北京,天津,广东,上海四个城市销售... 　运筹学运输问题补例_社会学_人文社科_专业资料。运筹学运输问题补例一、运输问题是特殊的象形规划问题,其特殊性表现 1、产销平衡运输问题总是存在可行解。 xij ?... 　? ai ? ? b j 即运输问题的总产量不等于总需求量,这样的运输问题称为产销不 i ?1 j ?1 m n 平衡的运输问题。 从题目中可以看出客户的需求量大于产量,... 　运筹学有关于产销平衡的论文_理学_高等教育_教育专区。非常的好,非常的有用产销不平衡的运输问题摘要: 运输问题通俗来讲就是在原料或是成品运往产地或者销售地的...您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
运筹学--运输问题课件.ppt185页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：120 &&
你可能关注的文档：
··········
··········
运输问题 一、运输问题典例与数学模型
典例、线性规划模型、运输表 二、初始基可行解
最小元素法、沃格尔法
三、非基变量的检验数
闭回路法、对偶变量法 四、解的调整
确定进基变量和离基变量，调整运量 五、产销不平衡的运输问题 六、运输问题应用―建模 §1 运输问题的典例与数学模型 一、运输问题典例 实例：广东石化公司从三个石油加工产地进购石油，销往四个加油站。三个加工产地的产量分别为：14千吨、27千吨和19千吨，四个加油站的需求量分别为：22千吨、13千吨、12千吨和13千吨。已知从各加工产地到各加油站的单位运价如下网络图示（单位：千元/千吨），问石化公司如何安排运输方案，使得总运费最少？ 分析此问题：产销平衡问题：总产量
总销量。设Xij为从第i个产地销往第j个加油站的销量，则此问题是一个线性规划问题，我们得到： （一）运输问题网络图（产销平衡） （二）运输问题线性规划模型 二、运输问题的一般提法 步骤： 1、取 0的检验数中最小者对应的空格（即调入格，对应的非基变量为进基变量）作其闭回路； 2、取闭回路上偶转角点处最小运量（称为? ，其对应的变量为出基变量 作为调整量（设空格为第一转角点）； 3、闭回路中在偶转角点处减?，奇转角点处加?,其它地方运量不变，则得到一新的基可行解。
（其原理与单纯形法确定换入与换出变量相同）
4、对新解进行最优性检验，如果不是最优，重复进行调整，直至所有检验数非负为止，得到最优方案。 本章作业 书面作业
3.1、表3.35和3.36
课外练习 3.1、表3.37和3.38 3.2、3.3、3.4、3.5 解:根据题意，作出产销平衡与运价表，取 M 代表一个很大的正数（其作用是强迫相应的 x31、x33、x34取值为0）
正在加载中，请稍后...扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
运筹学论文产销不平衡运输问题.doc
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口运筹学 运输问题_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
文档贡献者
评价文档：
运筹学 运输问题
大小：387.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢