东北大学学根【自然科学版｝JournalofNortheasternUniversity(NaturalScience)2002年1月第23岳第】疵J<in20(I2VuL23.N...I文章编号：1005-3020(2002iOl-0005-03一类转库问题流向优化问题的模型与解法高天1,王步光1.唐立新I、宋建海'门.东北大学信息料学与工程学院、辽宁沈阳110004；2上梅宝山钢怏集岌丨公司/卄算机系统工程有限公司.上降201900J摘要：转库是大型企业物流管理工作中的重要环节•针对企业决策支持系统的子系统-转库作业日计划问题进行了分析、为一类转库流向问题建立了优化猿型••具有特殊约束0-1整数线性规划问题（0-1ILP）.分析了具休问题的性质•为求解这类NP-难问題，给出了一种在实际中行之有效的求解问题的算法-…降维替换算法.以SAS语育为环境，用实际阿题作为计算算列、对这种算法的优点进行了总结：谏算法在实际应用中是切实可行的，在时间上是节约的，尤其适台于大规模的问题.关健词：物流管理「转库流向问题;U-1线性整数规划；NP-难问題：降维替换算法中图分类号：O221.4文献标识码：A在企业的决策支持系统中，大量的问题是数学僅型支持的、这时存在育两个问越：建立合理的数学模型和构造快速的模型求解方法•本文针对某钢铁企业发货岀厂决策支持系统的转库作业日计划问题进行了物流分析、建立了具有特殊系数〔均为非负）的0-1现性整数规划模型.0-1现性整数规划问题，属于NP-难问题（或是\P-完全问题）I，J1,但因其广泛的实用背雄，对其建慣与解法的研究一点倍受关注•目前有关它的解法有两类［3'61:①精确解法，如分支定界法与切割法等；②启发式算法l7-R,.前者在埋论研究中有重要价值，后者在实际应用中有大宦的成功范例卫$・八・2.然而，多数启发式算法的规则依赖于实际问题•而实际问题的千差万别，使这些解法有其局限性•对此，本文以分析这类0-1线性整数规划模型系数的一般规律为基础，构造-•个更为有效的解法-降维替换算法，用现场中的实际教据进行试算，并与分枝定界法计算的结果比较•验证了算法的有效性•目前、本子系统已并入整卜出厂决策支持系统上线运行.效果良好.1转库流向决策的业务现状和实际问题模型及符号说明在奚钢铁企业出厂中心的物流管理中，为保证连续生产、防止涨库及准备出厂•要经常进行转库•转库作业日计划需要确定转库流向和作业吋间安排•该企业转库过程中构成物流运动最小的单位是•'准发''（指准予发货的同类产品的一卜组成单位）•转库流向指“准发”由始点库（生产线末端库）转出到终点库（成品库一一码头.火车站、堆场）入库•其中，每个需转库的准发在一彳、始点库可以向数个终点库转移（由转库作业规程确定）.该企业共有：冷轧末瑞库25个；热轧末瑞库22个；初轧末端库10个;板坯末瑞库6个：筲线禾端库4个；铁路库6个；码头库2个；堆场5,・基于对转库业务的工作现状分析与转库物流分析，对转库流向优化及时间推荐问题到兵体模型描述：5maxXX工丫皿⑷人卩:谚1门/-I疋Kifj圧-护f匕,r=1,2,3,Vt€K心u?l（2）乞YJP円皿<P/jf=1,2、3,Q€丿<3）工ZZR从WDmf=1.2,3rkEK（4}Jr（J工工工yWlVre7?,Vj€J⑸IK收越日期：2WMJ3-UV基金孑目：国家自然科学基金翳助娈口（7Q70UQG.作者简介：庇天（19&0-：••臥音林长春人•乐」匕大学博士研充化；七梦光门牛6亠；•■匕吉妹省吉林市人•东北大学狀择•博导障；唐立新门93i・），勇•黑龙羽绥化人•东北大学教挖.各参数的怠义如卜•：_1,;库第，个准发在第f班转向R库F=O其他⑹疋巳・f=】,2、3其中•人为终点库集合;丿为有转库需求准发的始点库集合汀为全体准发编号的集合；厶为j库需转库的准发集合门为第』库需转库的准发的编号「€/八U7?=I心为i准发转至&终点库之“收益S：为，准发的质量（单位:t）；9,为「准发的权爾系数；％为，准发转向A终点库时占用的终点库库容（单位江）；为怡终点库在第r班的可用库容（单位:为/始点库,准发岀库所需能力（单位：件数）；巳为丿始点库在第r班转库可用的出库能力（单位：件数”/强为i准发转至R终点库所需的入库能力（单位：件数”1?咲为&终点库在第］班转库可用的人库能力（单位：件数）.式（1）是目标函数.意义是追求尽多准发转向最合适的终...