资源描述：
《生产网络流最小费用问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第25卷第2期沈阳师范大学学报(自然科学版)Vol25,No.22007年4月JournalofShenyangNormalUniversity(NaturalScience)Apr.2007文章编号:1673-5862(2007)02-0140-04生产网络流最小费用问题胥晓庆,唐恒永(沈阳师范大学数学与系统科学学院,辽宁沈阳110034)摘要:生产网络流是一种广义的网络流模型,是基于复杂的生产过程,重新建立的一种新模型本文主要讨论了生产网络流的最小费用问题,在研究该问题的基本结构及
2、其对偶性质的基础上给出了该问题的网络单纯形法关键词:生产网络流;最小费用流;网络单纯形法中图分类号:O223文献标识码:A0引言网络流模型在实际生产中有及其广泛的应用,但普通的网络流模型在描述更加复杂的生产过程时[1]有其局限性因此,FANGShucheng和QILiqun在中提出了一个称为生产网络流的广义网络流模型在这个模型中,多种原料通过合成或提炼过程可以生产出多种产品为了更恰当地描述生产的各种过程,在生产网络流模型中引入了六种不同结点:用来转运的普通点O点,用来提供原
3、料的原点S点,用来收集成品的终点T点,用来存储加工中的原料或半成品的存货点C点,用来进行分配或提炼操作的[1]分配点D点,用来进行装配或合成操作的装配点I点由于生产网络的复杂性,在中作者提出了两种简化的模型,即分配网络流模型和装配网络流模型本文综合了分配网络流和装配网络流模型的特点,给出了生产网络流模型我们主要研究生产网络[1,2]流的最小费用问题该问题可以类似,在研究该问题的基本结构及其对偶性质的基础上,给出了解决该问题的网络单纯形法1基本可行图定义1令x是基本可行解,如果
4、一个点没有正的流通过,则称该点为空闲点,否则称为活动点下面给出基本可行解的一些性质:定理1令x是基本可行解,GB是对应于x的基本可行图,则1)点s和点t都是活动点;2)GB是连通的;3)GB的任意一个圈都包含一个C点或一个D点;4)对于每个C点,或者所有与之相连的弧都是基弧,或者只有一条不是基弧在后者情况下,该C点是空闲点;5)对于每个D点,或者所有与之相连的弧都是基弧,或者只有一条不是基弧在后者情况下,该D点是空闲点;6)GB可以看作是的一棵支撑树,根在s,q-t+p-r,有条
5、多余弧t代表松弛变量个数,r代表I点数证明1)由4)及dj>0,jNT可知t是活动点正流自s流出,故s也是活动点收稿日期:20070109基金项目:国家自然科学基金资助项目(10471096)作者简介:胥晓庆(1982-),女,辽宁沈阳人,沈阳师范大学硕士研究生;唐恒永(1943-),男,山东掖县人,沈阳师范大学教授,硕士研究生导师第2期胥晓庆等:生产网络流最小费用问题1412)因为正流来自s,故所有活动点在GB中与s连通,假设某些空闲点在GB中与s不连
6、通,从新排B10列对应于x的基矩阵B的行和列,可以写B=,其中B1对应于与s连通的点和基弧,B2对0B2应于与s不连通的点和基弧由(1)可知,B1不包含s点和t点对应的行这样,B2的一些行完全在M中,使得这样的行和为零这与B是满秩矛盾因此B2一定为空,则GB中的所有点与s连通3)同样,令B是对应于x的基矩阵,B与MN的共同部分一定是列满秩的根据网络单纯形法的理[24]论任意不含C点、D点的子图,不含圈4)对于一个C点,必须包含C点连接的所有弧,或者只有一条不包含其中在后者的
7、情况中,与C点相连的一条弧是非基弧,则该弧上的流值为零,该C点连接的所有的弧上流值都是零,即该点是空闲点5)同上6)由2)及基矩阵的维数即可证明2原问题和对偶问题的基本可行解利用对偶形式和定理1,可以得到该问题的最优条件,令B是最优基,对于弧(i,j)B,表示变量xij是基变量,对于每个C点和D点,我们从中省略一个等式因此,用E!(i)表示E(i)中剩余的入弧点,用L!(i)表示L(i)中剩余的出弧点此外,令LC=!{(i,j)A;jL(i)};EC=!{(i,j)A;jE!(
8、i)};iNjNCCLD=!{(i,j)A;jL!(i)};ED=!{(i,j)A;jE(i)};iNjNDDAO=A(LC!LD!EC!ED!{xs})最优条件包括三部分:对于原问题部分,需要满足xij=0(i,j)∀B(1)ti=0iNT,i∀B(2)xij=kijxi*ijL(i),iND(3)*这里E(i)={i}x*ji=hjixiijE(i),iNC(4)*这里L(i)={i}#xji=#xijiNO(5)jE(i)(i,j)BjL(i)(
