（系统分析与集成专业论文）企业管理创新数量分析中的线性优化逆问题.pdf

大连理工大学硕士学位论文 摘要 企业管联创新即是用新的更有效的方式方法来整合组织资源，以更有效地达成组织目 标与责任的一种刨造性活动。管理刨新的作用和影响是非常巨大的，从泰勒制到全蕊质量 管理，再舞鼹争强受重视的供应链管理等，这些管理裁新的成栗都极大地改善7 产晶蒺量， 提高了生产效率，增强了众业的竞争能力。 从当前的国内外研究现状来看，国内现有的管理创新研究主要集中在案例研究和模式 分析等实证研究方瑶，丽黧多 更多关注的是对创新的管理孺不是管理创新。尽管创掰管理 和管理创新有一定豹联系，匿二者在研究内容、研究方法等方面黼褒着较大的差舅。因 此总体上讲，茸前国内外关于管理创新般化思路和方法的理论研究还比较少，而对能够 给出定量化创新方向与策略的方法研究则厦是不多见。 针对这释情形，本论文研究基于企业生产经营豹线馕经济系统假设，尝试将逆优化的 理论引入管理创新的分析一围绕熊彼特“刨新”概念与企业线性瓶划模型两者之润的内 在联系，从管理创新的实践出发，分别对逆线性规划与线性规划逆最优值问题这两类线性 优化逆问题进行系统研究。通过对它们问题的引申、扩展和重新定义，一方面为企业管理 奄4 新方囱与其体策珞的靠订提供了一弹数量化分辑方法与技术工具；勇一方覆，也枣富了 现有逆优化研究的内容，拓展了其应用实践的领域范围。并在对两类线性优化逆问题自身 局限性进彳亍讨论的基础上，研究提出了衣线性规划最优解结构不变的前提下，通过调整技 术系数参数实现目标函数馕进一步改善和优化的种方法，且赋予了其企业管理创新的内 在涵义。 关键词：管理刨新；线性规划；优化：逆问越 塞堡垒绺篁型型缝主塑鲨垡丝塑囊 i n v e r s el i n e a ro p t i m i z a t i o np r o b l e m sf o rt h eq u a n t i t a t i v ea n a l y s i so f m a n a g e m e n t i n n o v a t i o n a b s t r a c t m a n a g e m e n ti n n o v a t i o ni sac r e a t i v ea c t i v i t yt om - o r g a n i z et h eo r g a n i z a t i o n sr e s o u r c e si nan e w e r a n dm o r ee f f c i o n tw a y , s oa st or e a l i z et h eg o 出a n d r e s 9 0 n s i b i l i f i e sm u c hm o r ee f f e c t i v e l y i nf a c t , i tp l a y s 飘i m p o r t a n tr o l ea n dh a sv e r yl a r g ei m p a c t sd u r i n gt h ec o m p a n y sd e v e l o p m e n t f r o m t a y l o r ss c i e n t i f i cm a n a g e m e n tt ot h et o t a lq u a l i t yc o n t r o l , a n dt h e nt ot h es u p p l yc h a i n m a n a g e m e n tt h a t h a sb e e np a i dm u c hm o r ea t t e n t i o nt ot i l l n o w , f o re x a m p l e a l lt h e s e m a n a g e m e n ti n n o v a t i o nr e s u l t sh a v eg r e a t l yi m p r o v e dt h ev r o d u mq u a i i t ya n dh e j g b t e n e dt h e p r o d u c t i o ne f f i c i e n c y ，a n ds os m m g t h e n o d t h ec o m p a n y sc o m p e t i t i v ea b i l i t i e s f r o mt h ep r e s e n ts t a t u sa th o m ea n da b r o a d , w ek n o wt h a tt h ed o m e s t i cr e s e a r c ho ft h e m a n a g e m e n ti n n o v a t i o ni sm a i n l yo nt h ed e m o n s t r a t i o n ss u c ha st h ec 搿s t u d i e sa n dm o d e a n a l y s i se ta ；h o w e v e r , t h eo v a 嚣e 8 sc o n c a ：地i sm o r ea b o u tt h ei n n o v a t i o nm a n a g e m e n t , b u tn o t t h em a n a g e m e n ti n n o v a t i o n a l t h o u g ht h e r ea $ o r l ed e f i n i t er e l 撕o n sb e t w e e nt h e s et w o c o n c e p t s , t h e yh a v eo b v i o u s l yd i f f e r e n tc o n t e n t sa n dm e t h o d s ，f o ri n s t a n c 世t h e r e f o r e , w ec a r l c o n c l u d et h a tt h e r ea r es t i l lf e wc o l l c f f m sw i t ht h eg e n e r a lt h e o r i e so f t h em a n a g e m e n ti n n o v a t i o n a 穗v 瓶e s ，s a yn o t h i n go ft h o s et h a t 锄d o o r n eq u a n t i t a t i v ea n a l y s i sa b o u tt h ei n n o v a t i o n s t r a t e g i e sa n do r i e n t a t i o na sw e l l 缸蛔t h i s ，i nt h et h e s i s , w et r yt dh a t r o d o c et h ei n v e r s eo p t i m i z a t i o n 弱搿i n t ot h ea n a l y 癜g p r o c e s s e so f m a n a g e m e n ti n n o v a t i o nb a s e do nt h ee n t e r p r i s e s l i n e a re c o n o m i cs y s t e m sh y p o t h e s i s s u r r o u n d i n gt h ei n n e rr e l a t i o n s h i p sb e 押旧s c h u m p e t e r si n n o v a t i o nc o n c e p ta n dt h e l i n e a r p r o g r a m m i n g m o d e l so ft h ee n t e r p r i s ea n ds t a r t i n go f ff r o mt h em a n a g e m e n ti n n o v a t i o n s p r a c t i c eb a c k g r o u n d , t w ok i n d so f t h ei n v e r s el i n e a ro p t i m i z a t i o np m b l e g n s t h es t a n d a 坩i n v e r s e l pa n dt h ei n v e r s eo p t i m a lv a l u ep r o b l e mo fl p a 您s t u d i e dr e s p e c t i v e l y b y 向葑逝a n d e x t 删i n gt h e s em e t h m a t i c a im o d e l s , o nt h eo n eh a n d , w eo f f e raq u a n t i t a t i v em e t h o da n d t e c h n i q u et o o l sf o rd r a w i n gt h em a n a g e m e n ti n n o v a t i o n so r i e n t a t i o na n di t sc o n c r e t es t r a t e g i e s ； o nt h eo t h e rh a n d , w ee n r i c ht h ec u r r e n te x t e n t so f t h ei n v e r s eo p t i m i z a t i o nr e s e a r c h ，a n de x p a n d t h ea r e a so fi t sa p p l i c a t i o n s a n dt h r o n g ht h ed i s c u s s i o no ft h e i rl o c a l i z a t i o n s , am e t h o di sp u t f o r w a r dt oi m p r o v et h eo p t i m a lv a l u eo ft h eo b j e c t i v ef u n c t i o nf u r t h e rb ya d j u s t i n gt h el p s t e c h n i q u ec o e f f i c i e n t sb u tn o tc h a n g i n gt h eo p t i m a ls o l u t i o n ss t r u c t u r e ，a n dt h em o d e li se n d o w e d w i t ht h ei n h e r e n tm e a n i n g so f m a n a g e m e n ti n n o v a t i o na sw e l l ， k e yw o r d s ：m a n a g e m e n ti n n o v a t i o n ；l i n e a r p r o g r a m m i n g ；o p t i m i z a t i o n ；i n v e r s ep r o b l e m i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作及 取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他入已经发表或撰写豹研究成栗，也不包含为获得大连理工大学或者其 他单位的学位绒证书所使用过的材料。与我一同工作的同志对本研究所做的贡 献均已在论文中做了明确的说明并表示了谢意。 作者签名：杰鲣 日期：诬五么盆 大连理工大学磺士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用规 定”，同意大连瑷工大学保馨弗肉国家有关部门或枫孛每送交举位论文的复印佯和电子舨， 允许论文被查阅和借阅。本人授衩大连理工大学可以将本学位论文的全部域部分内容编入 有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：刍鱼珲一一 导师签名： 擘罐巳爷取月么日 大连理工大学硕士学位论文 1 绪论 1 1 引言 1 1 1 本论文研究的背景 本论文的选题源自国家自然科学基金资助项目：企业管理创新的系统分析及量化方法 研究( 项目批准号7 0 3 7 1 0 5 5 ) 。 美籍奥地利经济学家约瑟夫熊彼特( j o s e p hs c h u m p e t e r ) 于1 9 1 1 年首次提出了“创新” ( i n n o v a t i o n ) 的概念。在以后的著作中，熊彼特完善了他的创新理论并且给出了创新的五 种主要形式【j 】。在他看来，创新可以理解为一个过程，在此过程中企业家引入一种新的生产 函数，实现一种“生产要素的新的组合”并获得超常收益。之后，受新古典增长理论特别 是索洛( s o l o ) 等人关于技术对经济增长作用研究的影响，以弗里曼( f r e e m a n ) 等为代表 的熊彼特的追随者们把创新研究的重点转向了技术创新1 2 ，以至于一提到熊彼特人们就立刻 想到技术创新这个概念。如今关于技术创新的研究已经从对创新机制和过程的研究转向了 更高层次的创新管理方法和国家、区域以及企业创新系统的研究【3 】。 事实上，熊彼特的创新概念是一种广义的创新概念，它不仅包括倍受重视的技术创新 ( t e c h n o l o g yi n n o v a t i o n ) ，也包括管理创新( m a n a g e m e n ti n n o v a t i o n ) 、组织创新( o r g a n i z a t i o n i n n o v a t i o n ) 和随着制度经济学的兴起而日益引起人们重视的制度创新( s y s t e m s i n n o v a t i o n ) 等内容。 关于管理创新，芮明杰教授在其管理创新一书中指出：管理创新是指创造一种新 的更有效的资源整合范式，这种范式既可以是新的有效整合资源以达到企业目标和责任的 全过程式管理，也可以是新的具体资源整合及目标制订等方面的细节管理【4 】。从这个意义上 讲，熊彼特创新概念的原始含义也许更接近于今天人们所熟知的管理创新。特别是在当前 知识经济时代的大背景下，可以说整个管理的过程在本质上也即是一个不断创新的过程。 管理创新的作用和影响是非常巨大的，从泰勒制( 又称为科学管理原理，s c i e n t i f i c m a n a g e m e n t ) 到全面质量管理( t o t a lq u a l i t yc o n t r 0 1 ) ，再到目前倍受重视的供应链管理 ( s u p p l yc h a i nm a n a g e m e n t ) 、客户关系管理( c u s t o m e rr e l a t i o n s h i pm a n a g e m e n t ) 等， 这些管理创新的成果都极大地改善了产品质量，提高了生产效率，增强了企业的竞争能力。 但是，与技术创新相比，管理创新迄今仍没有引起人们足够的重视，究其原因，一方面是 因为管理创新并非创新研究的主流；另一方面则是因为管理创新在一定意义上说比技术创 新更困难。由于总有大量的新技术、新工艺等可供用于技术创新，企业家往往不需要自己 去搞发明创造，但是他们却通常要找出新的管理方法来解决生产经营中所遇到的各种实际 菇德华：企业篱理e 日新数量分析中的线性优亿逆澜题 问题。遗撼的是面对千羡万别的管理实践，可供企业家套用的域成管理方法非常少。因此 研究管疆创新的一般方法就显得十分必要和重要? 。 1 1 2 本论文研究的意义 “创新是一个鼹姨的灵魂，是嚣家进步发达的不蝎动力”。管理创新是创新理论研究 酶主要淘容。企业雅为社会经济游动的微观主体，整个衽会豹发展莘匪翅新在报大程度上又 是由企业内部的创新实践所推动的。研究企业管理创新的般化方法，借助予逆优化的技 术工具，从定量分析的角度探求企业管理创新的战略与方向，这不仅有利于提高企业的运 作效率，促使其宅4 薪瓣标的实现，麓时也有尊予改变重前普遍夺在的企业管璎刨薪无从下 手的被动状态，减少众业管理创薪的盲蟊性，降f 氐试错成本，提高企业的综合竞争能力， 从而对于处在转型期的中国经济特另g 是大中型国脊企业改革、隧域经济发展乃至整个国民 经济的宏观调控等都穰具有非常藁要的理论价值和现实意义。 1 2 基于线性优亿逆阊题分极企建管理剑颟的理论依据 1 2 1 众业管理创新的基本概念 熊被特在饱1 9 1 2 年出舨豹经济发展理论一书中首次给如了“色q 新”这一概念的定 义，并将其纳入经济发疑理论之中，论证了剑薪在缀济发展过稷中的重大作用【l l 。熊彼特认 为，创新就是“生产手段的新组合”，“生产意昧着把我们所能志配的原材料和力量组合 起来”，这一创新概念包含了如下的五种形式： 1 ) 采用一魏新的产品，也就是游费者还不熟悉豹产爵或一嵇产品的种新的特 性； 2 ) 采用一种新的生产方法，也就是在有关的制造部门中尚未通过经验检定的方法， 这种方法决不需要建立在科学的发现的慕础上，并且也可以存在于商业上处理一 转产品的新豹方式之中： 3 )开辟一个新的市场，也就是有关国家的菜一制造部门以前不曾进入的市场，不管 这个市场以前是否存在过； 舢掠取或控制原材料或半制品的一种新的供应来源，也不问这种来源是已经存在 的，还是第一次创造出来的； 5 )实现任何一种工业的新的组织，比如造成一种垄断地位，或打破一种垄断地位。 熊彼特所指创新概念的这五个方面，实质上魑含有了刨造全新的资源配置方式方法的 内在岔义。这样，壹鼙熙款创毵妨燕度来考察经济发展，整个经济的发震过程茏嚣是“不断 大连理工大学硕士学位论文 的技术创新和观念更新导致的资源配置方式方法不断产生，导致资源配置效率提高，从而 逼近帕累托最优的过程”【4 】。熊彼特的创新概念，事实上已经有了管理创新的部分内涵。 之后，随着现代科学技术革命的蓬勃发展，创新理论向着两个不同的方向延展： 一个是技术创新方向。2 0 世纪6 0 年代初期，分别涌现出曼斯菲尔德( e d w i n m a n s f i e l d ) 的技术创新的扩散、卡曼( m o r t o ni k a r a i e n ) 和施瓦兹( n a n c yl s c h w a r t z ) 的技术创新与 市场结构、弗里曼( r o n a l df r e e m a n ) 的技术创新与企业规模假说、列文( l e w i n ) 的技术 创新与行业进入、尼尔森( r i c h a r d & n e l s o n ) 和温特( s i d n e yg w i n t e r ) 等的技术创新与 不确定性等理论，对技术创新做了进一步的研究，形成了技术创新经济学这一新的分支。 另个是制度创新的方向。2 0 世纪7 0 年代初，戴维斯( l a n c ed a v i s ) 和诺斯( d o u g l a s s n o r t h ) 等人将熊彼特的创新理论和以科斯( r o n a l d i - lc o a s e ) 为代表的制度学派结合起来， 研究现存制度的变革在促进企业获得追加利益中的作用，以及起作用的机制等问题，由此 形成了制度创新经济学。 而最早将“创新”概念引入管理领域的，当推美国著名的管理学家德鲁克( p e t e rf d r u c k e r ) 自上个世纪5 0 年代所做的工作。但长期以来，对管理创新韵研究仍仅是停留在组 织的微观经营层次，理论界迄今也还没有就管理创新在创新体系中的地位给予科学的定位。 这在一定程度上弱化了管理的整合能力在创新体系中的综合作用同。 从国内现有文献来看，当前对管理创新的定义比较有代表性的观点主要有以下几种： 管理创新是指新的方式方法的引入。常修泽等人认为，管理创新是指“一种更有效 而尚未被企业采用的新的管理方式或方法的引入”，是“组织创新在企业经营层次上的辐 射” 6 2 。其主要目标是试图设计一套规则和服从程序以降低交易费用。 管理过程就是创新过程。于中宁认为，“产品创新和应变环境都是管理创新”，企 业管理创新就是“不断根据市场和社会变化，重新整合人才、资本和科技要素，以创造和 适应市场，满足市场需求，同时达到自身的效益和社会责任的目标的过程，【”。由于这一过 程也是管理过程本身，因此，管理过程就是一个创新的过程。 管理创新是“用新的更有效的方式方法来整合组织资源，以期更有效地达成组织的 目标和责任”。芮明杰认为，“管理创新是创造一种新的更有效的资源整合范式，这种范 式既可以是新的有效整合资源以达到企业目标和责任的全过程式管理，也可以是新的具体 资源整合及目标制订等方面的细节管理”。并根据这一概念给出了管理创新包括的五种情 况，即：“提出一种新的经营思路并加以有效实施”；“创设一个新的组织机构并使之有 效运转”：“提出一个全新的管理方式方法”；“设计一种新的管理模式”，或者“进行 一项制度的创新”等【4 】。其中，新经营思路和新管理模式要求对所有的企业而言都是新的， 而且所有的这些刨新都必须是可行的并有助于资源的有效整合。等等。 高德华：企业管理创新数量分析中的线性优化逆问麒 应该说，上述这些定义从不同的角度进行描述，在一定程度上都反映了管理创新的本 质和特征【鼢。本文茏意参与遮种定义上的争论。但作者认为，熊彼特奄4 新概念魄孱始涵义霹 鼹是更接近于今天人们所熟知的管理刽新。并以眈作为全文论述的一个重要基本点。 2 2 愈北管理刽瓤与缭i 生佬纯遂问题的关联 在对企业管理剑新概念作了全面认识租深亥4 理解的藻础上，杨德权等基于线性缀济系 统假设。研究提出了管理创新的数量方法 1 0 1 ，并给出熊彼特五种主要创新形式在线性规划 模型中的对应转亿关系如下： 1 )引进新产品薪产品的弓l 入将增加系统模型中来知变爨的个数，弓l 起目标函数 和约寨条俘的目眵变化，如果新产品的生产需要鞭的资源，舅么约索条传盼个数 和资源向量也将发生变化； 2 ) 弓i 用新技术将引起技术系数矩阵的改变； 3 ) _ 开辟薪蠢琚将弓i 起目标函数系数离量豹改变； 4 ) 发现和控制原材料新供应来源将改变资源向量； 5 ) 实现新工监维织将弓l 起模型豹总体改变。 根据他们的着法，管理就是创新，企业管理创新的嗣的在于“使系统向着有利于突现 其目标的方向转化”。管联剁新体现在线性规划模型中，也就是人们通过改变模型的相关 系数参数和约束条件使某给定生产方案得叛蕺优化实现，或者使窝标函数的最优傻褥到 进一步改善的过程。事实上，这正是线性优化逆问题所关注的内容。因此，考虑引入线性 优纯逆闻趣的瑾论，并结会念业管理意新的实黢簿景霹茭作进一步深入研究，有望为线性 经济系统假设下企煦管理创新的具体实施提供一种数量亿策略分析方法与技术工具。 1 3 纷陡优化遂澜题国内外研究瑰状综述 逆翘霹方法( i n v e r s ef r o b l e mt h e o r y ) ，又称为反演瑷论。对王程逆问题的关注，最单 开始于蟪球物理学家。a t a r a n t o l a 在文献【ll 】中对其住? 如下的攒述：设s 代表一个物理 系统( 例如整个宇宙，或一个羼系，或个量子粒子等) ，假设能够定义组完全描述s 的 模型参数，这些参数可能并不都是可蛊接测最的，我们w 以在计算上定义一些可观测参数， 希望饱稻的实舔值依赖于貘黧参数篷。求勰芷鼹疆就是对绘定的铥意摸銎参数毽颡粳l 可观 测的参数值，而求解逆问题贝g 是根据给定的可观测参数的观测值来推断模型参数的债。 自1 9 9 2 年由d b 蝴辍p hl t 孙i n t 等硬究挺出逆爱缝路阂题( i n v e a s h o r t e s tp a t h s p r o b l e m ) 及其求解算法之斌豫1 3 1 ，近年来，人们将逆问题方法引入到运筹优化领域，相继 绘出了：狭义逆优化( i n v e a s eo p t i m i z a t i o ni nt h en a r r o ws e n s e ) ；部分受限逆润题( i n v e a s e p r o b l e m sw i t hp a r 删yg i v e ns o l u t i o n ) ：边界约隶逆闻趱( r e v e r s ep r o b l e m sw i t hb u d g e t 大连理工大学硬士学位论文 c o n s t r a i n t s ) ；阻及给定嚣标函数取值范匿躲递阀题( r e v e r s ep r o b l e m sw i t hp r e s c r i b e d o b j e c t i v e f u n c t i o n r a n g e s ) 等一系列问题的描述和定义，对他们的求解算法与应用等展汗研 究；并针对不同的应用背景，分别探讨了：逆最短路问题( i n v e r s es h o g e s tp a t h sp r o b l e m , d b u r t o na n dp h l t o i 鸸1 9 9 2 ；m 。c c a ia n dx g y a n g , 1 9 9 5 ；j _ z h a n g , z m aa n dc y a n g ， 1 9 9 5 ) ：逆指派霹题( i n v 嚣s c a s s i g n m e n t p r o b l e m , 王z h a n g a n d z 。l 枫1 9 9 6 1 9 9 9 ；r t 耗a h u j a a n d j b 0 d i n 2 0 0 1 ；x y a n g , 2 0 0 1 ) ：逆最小费用流问题( i n v e r s e m i n i m u m c o s t f l o w p r o b l e m , j z h a n ga n dz l i u , 1 9 9 6 ，2 0 0 2 ；i t 砭a h u j aa n dj b o r l i n ，2 0 0 1 ) ：逆最小生成树问题( i n v e r s e m i n i m l 勰s p a n n i n gt r e ep r o b l e m , j 2 抽舀s x ua n dz 。v i a , 1 9 9 7 ) ；逆中心选址问题( r e v e r s e c a n t e rl o c a t i o np r o b l e m , j 盈龇嚷x y a n ga n dm c c a i , 1 9 9 9 ；j z h a n g , z l i ua n dz m a , 2 0 0 0 ) ；逆d e a 问题( i n v e r s ed e ap r o b l e m , j 龇1 9 9 6 ；q w e i ，j z h a n ga n dxs z h a n g ，2 0 0 0 ； h y a h , q w e i a n d g h a o ，2 0 0 2 ) ；等等 逆优化研究正受到墨濒广泛的关注，在诸如运输流量均衡、网络选址以及多准则优化 等众多领域取樗了些理论和应用成就【1 4 嘲。 本论文主要从企业管理创新的实践背景出发，围绕针对最优解的逆线性规划问题和针 对目标函数值的线性规划逆最优值问题( t h ei n v d s c 铆咖l a lv a l u ep r o b l e mo f l p ) 这两类逆 海露来晨开。为了叙述上豹方便，本文将二考统称为线经优佬逆闻鼹( i n v e r s el i n e a r o p t i m i z a t i o np r o b l e m s ) 。 1 3 1 逆线性规划问题 逆线性规划，即所谵的线性规划典型遂闽题。其一般提法魁嘲：给定莱线蛙援剃一个 可行但非最优的解z o ，要求在某种范数下，通过对目标函数中价值系数参数作尽可能少地 调熬，使之转化成为新问题的最优解。显然，由于这里改变价值系数参数并不影响问题的 可行域，因此要求给定的解x o 必须是可行的。该类逆问题最初的主要应用在于：在某些情 况下，尽管建立了线性规划模溅，僵目标函数中豹份僮系数参数攮难精确给定，如果根据 经验或实验，能得到所需要的最优解，人们希望运用这些已知的信息来尽可能小地调熬价 值系数，以获得满意的结果。 王z h a 茧g 和z l i u 等最早对此类问题进行了研究，并证明了在工l 一范数下，一般形式的 逆线性规划可以通过转换成为一类线性规划问题来解决。能们给出了逆线性规划的一般形 式( t h eg e n e r a li n v e r s el pp r o b l e m ) ，根据最小费用流问题及指派问题的组合性质，分别给 出了求解其相威逆问题的一类强多项式时间算法，并提出了指派问题的限制逆问题( t h e r e s t r i c t e di n v e r s ea s s i g n m e n tp r o b l e m ) 以瑟稠用组合性囊得到的求解方法 1 6 】；对风络流规划 商德馨：企业管理创新数蠡分析中的线性优化逆问题 与组合优化中常见的o - l 规划问题的逆问题邀行了深入研究，给出了在三l 一范数与l 一范 数下逆线性规划的一般模型及算法f 】刀。 刁在筠、关秀翠替探讨了一般形式逆线性规划问题在各种范数下的求解，基于求解凸 二次规划的源对偶内点算法( t h e p r i m a l - d u a l i n t e r i o r p o i m a l g o r i t h m ) ，给出了一个o ( n 3 l 1 算法和一个实用算澍1 8 l ；基于线性规划问题的最优性条件( 甄出n 小l c k 条彳牛) ，将厶一范数 下的逆线性规划问题转换成为仅带有变量非负约束的凸：次规划问题，并利用具有二阶收 敛性的予校正内点法( t h e p r e d i c t o r - c o r r e c t i n t e r i o r p o i n t m e t h o d ) 来求解嘲；针对逆线性规 划弼题的价值向量0 7 中有黢分量不允许调整的恃嚣，提出了一般线性规划的限制逆闻题 ( t h e r e s t r c t e d i n v e r s e g e n e r a l i n e a r p r o g r a a m 血g p r o b l e m ) ，结合线性规划的最0 幽- f e e ， 得出了其在三。一范数、厶一范数和工，一范数下的数学模型分剐对应为线性规划和二次规划 的结论刚；证明了由限制逆润题豹可桎解帮最优解可相应逡得到逆线往规划离题的可行解 和最优解，并进而给出了逆线性规划问题的一种简化模型( as i m p l em o d e lo ft h ei n v e r s e l i n e a rp r o g r a m m i n gp r o b l e m ) f 2 ”。 舄停蕃、杨超、j z 酗n g 等将该类逆闰题归结为一组统一豹线性规划目题模型，研究提 出了计算求解的一类列生成算法( t h ec o l u m ng e n e r a t i o nm e t h o d ) 与椭球算法( t h ee l l i p s o i d m e t h o d ) 簖- 2 4 。前者通过生成列的方法，运用单纯形法进行迭代求解；后者则提供了一种 多项式时褥痒剜算法( a p o l y n o m i a l o l d e l a l g o r i l h m ) 。 3 2 线噬怒蜷l 逆最挠信闻题 与前述逆线性规划“给定某一可行但非最优的解，希望遴过改变模型参数的值，将其 转变成为磺优解，同时确使这一改焚量尽可虢地小”不相阉，在另类逆优化问题( r e v e r s e o p t i m i z a t i o n ) 中，疆n 并没有过多j 氇考虑决策变量，丽是盥稠重予如何使得髫标溺数最优值 与给定的预期期塑数傻最接近，或者说如何使给定的目标数值能够得到最优化实现，同时 对价值系数参数总的调整量尽可能地小的问题瞄】。当前，关于该类逆优化的研究主要围绕 诸如最短路问题( t h es h o r t e s t - p a t hp r o b l e m ) 、阚络遗址闷题( t h en e t w o r kl o c a t i o np r o b l e m ) 等一些具体的嬲络淀与组合最优化阀题来展开 2 s - 2 s 】。 而逆最优值问题则仅是将被调整的价值系数参数限制在某一约束集合内，其概念和基 本思想最早体现在o b x m n 等对一类藏小一最大( 中心) 选址问题模黧( am i n i - m a x ( c e n t e r ) l o c a t i o nm o d e l ) 的研究中鲫。s 。趾n e d 苇口y c _ a l a n 等对该类逆目题给出了统一的 数学描述，他们的研究结果表明 加 ，当给定价值系数的约束条件集合为非空紧凸集，且线 性规划可行域亦是非空时，相应逆最优值问题满于一类加，一h a r d 问题；并在一塑给定g d 串- 大连理工大学硕士学位论文 下，得出了线性规划逆最优值问题可通过转换成为一类凸优化问题来解决并且是多项式可 解的结论。 1 3 3 当前研究中尚存在的问题与不足之处 综合对现有文献资料的分析，不难发现当前线性优化逆问题领域的研究中尚存在如下 的几点问题与不足之处，有待于进一步地发展与完善： 首先，当前关于逆优化问题的研究工作仍仅是局限在针对组合优化中的一些具体问题 的逆问题进行建模，并运用组合优化的某些理论和方法对其进行计算求解，对一般形式线 性规划逆问题亦只是停留在理论探讨的阶段而缺乏实践的背景，大规模的工程实际应用还 没有深入开展。 而对于线性规划逆最优值问题的研究，其相关文献当前仍并不多见。该类逆优化问题 在具体工程与企业生产经营中的实际应用，也尚处于初步探讨的阶段，有待于进一步的深 入研究。 其次，现有文献对逆线性规划与线性规划逆最优值问题的一般提法，也仅限于对目标 函数中价值系数参数的调整，尚未涉及到其他的模型参数( 如可行域等) 。 但在实际问题中，尤其是对于逆线性规划，由于现有的研究只是涉及目标函数中价值 系数参数的调整而并不改变问题的可行域。为了确保逆优化问题模型解的存在和有意义， 要求所给定的解必须是可行的( 并且本文的研究认为，若要保证问题最优解的唯一性，还 要求给定解为可行域上的某个极点) 。这在很大程度上限制了逆线性规划得以广泛深入应 用的领域和范围。 特别是当把线性规划模型赋予了企业管理创新的丰富的内涵与现实意义，对逆优化问 题的研究除了调整价值系数参数之外，调整约束条件中的某些参数( 亦即改变可行域) 也 将是必要的。例如，在企业生产运营的线性规划模型中，由于约束条件中的技术系数矩阵 与右边项向量等参数分别代表了企业一定的生产条件、技术水平和资源约束，对它们的调 整也就意味着某种管理创新具体方式方法的引入。因此，无论是逆线性规划，还是线性规 划的逆最优值问题，都很有必要在现有理论研究成果的基础上做进一步的引申和扩展，使 之在进行计算求解的过程中，对其中模型参数的改变都至少包括了如下的三种途径或者它 们的组合： 改变目标函数中的价值系数参数； 改变约束条件右边项参数； 改变约束条件中的技术系数参数。 离德华：企渡篱理翎薪数量分析中豹线侄优像遴婀题 这里，由于途径中不改变阍题盼可行域，医此要求给定解必须跫可行的；而对予途 径和来说，可行域亦随之发生了变化，所以绘定解既可以魁可行的，也可以是不可行 豹。 这里为了便于将其运用到企业管理创新的数量分析中来，本论文结合对已有研究成果 的综述狂分捉，提出了逆线性嫂划瓣引申与扩展翔题，并对线性规划逆爱优馕闰题豹定义 作邋当的修正，将其中的约束集会具体亿，这既是可行豹，也怒镊有必簧的。所存这些， 构成了本文研究的一个重要组成部分。 最后，前述的两类逆闯题( 氛括本论文中结台企业管理翻掰豹实戢挺出进行定义引审、 扩展籁敛出修厦的模型在内) 分男0 侧重于对线性规划模型最优解( 决策变燕组合) 和目标 函数最优数德( 颈订目标) 豹强调，而无法二耆兼顾。反映在企业管理剑新的实践中，特 别是当预订目标( 或生产方案缀合) 不甚合理时，往往可能得出有悖予实际的结果，而对 企业臀理创新没有任何现实的指导意义。 锋对这种情况，徐戏龙、昊建每等结食影子价臻豹技术意义，基予最优单纯形表提出 了在不改变原线性规划问题最优解结构的条件下，使目标酯数值得到进一步改善和优化的 种方法阱】，给作者以商益酶庭秀 。 1 4 本文的内容与主要工作 零论文研究的内容和主要工体毽括以下四个方瑟： a )在线性经济系统假设下，根据熊彼特“创新”概念与线性优化逆问题的关联，将 逆绽化阀题的理论；i 入企娆管理龟q 薪的麓珞分拆，以期为企业管理宅4 薪的具体安 践提供一释数墨化分析方法与技术工具( 第一章文献综述部分) ； b )结合企业开展管理创新活动的具体背景和需簧，针对逆线性规划与线性规划逆最 优傻问题这鼹类线性优化逆问题进行研究，分另对它靠】定义的接述、求躲算法以 及相关模型的引申、扩鼹与修正等作了分析讨论( 第二章和第三章) ； c ) 基予线性规划的对偶定理，研究提出了在不改变原线性规划阀题最优解结构的前 提下，使目标函数值得到进一步敬善与优化的一种方法，且赋予其企业管理创新 的内在涵义( 第四章) ； 国综合全文懿论述，分另9 舒砖三类英髂翘蘧给出数壤募例上豹分折与检验，羯辩巍 为将线性优化逆问题理论运用于奄业管理创新的分析做了实证上的初步探讨( 第 二、三、靼章中的冀倒分橇与检验部分) 。 念文的基本结构如下图1 1 所永： 文连理工大学硬士学位论文 第二章逆线性规划闻题研究 逆线性规划问题与求解算法 逆线性规划的引申与扩展 对逆线性规划求解算法的撵讨 算倒分析与检验1 第兰章线性规划逆最优值问题研究 线性规划逆最优值问题表述 线性规划逆最优值问题再定义与求 解算法研究 广义线性规划逆最优值问题描述 算例分析与检验2 第四章基于对偶定理的线性规划技术系数参数优化方法 问题的提出 基于对偶定理的线性规划技术系数参数优化方法的构造 基于对偶定理的线性规划技术系数参数优化方法在企业 管理创新分析中的实旖流程 算例分析与检验3 圈1 1 本文的内容和主要工作 f i g 1 - tt h oc o n t e n t sa n d n m i n j o b s o f t h e t h e s i s 9 - 一一一醚塑丝筻堡型堑墼堂生墼煞塑垡避 2 逆线性规划问题研究 2 1 逆线性规划问题匈求解算法 2 。1 ，1 逆线性麓翅翡基零概念 为了表述上的方便，并且为了确使这里对于逆优化问题的论述更其宥一般性，本论文 中仅黢于考察如下的般形式线性靓划问题( 企业生产经彗的线性经济系统假设与蒸予约 束理论所建立的企业生产缎蒋的线性规划模型及其简化模型，参见附录一部分) ： m i nc t x 。i 血b ( 2 1 ) 叫0 s x s j 冀中：x 一决策变爨，x r 4 ；c 一目标函数价值系数向量，c e r 4 ；b 一约束条件右边 项，6 e r “；r 、d 一边界约束向量，r ，d e 最“；a 一技术系数矩阵，a r 。 根据文献【l 书1 国所绘如豹数学擒述，_ 黢形式的逆线往觏剜闼蹶定义如下： 定义2 1 绘定线性规划问题( 2 1 ) 的一个可行但非最优的解扩，耍求在某工。一范数下( 本 文盼沦述仅限于工。一范数，以下罔) ，通过谶氅价值系数参数c ，健之转交成为稳威新闻题 的最优解，并使得这一调熬量尽可能地小。亦即： 竣调整詹豹价篷系数为0 ，势记： 翼g 有逆线性规划问题： 丁( c ，一，b ，力= n 粤叠7 爿血6 ，r s x s d ( 2 2 ) 哦则。、 s z 7 = ? 0 ，b ，x ) 。 显然，由予这里对份饭系数参数c 的调整弗不影响原线性规划问联( 2 1 ) 的可行域， 因忿要求给定盼解p 必须燕可彳亍的，也就是： 工。e 扛l 彳x 6 ，r s x s d 并且，本文的研究表明，问题( 2 3 ) 存在唯一最优解当且仅当给定的解妒为其可行域( 单 纯形) ：f = z t a x - b , r s x s 矗 上的某个顶点。 大连理工大学硕士学位论文 2 1 2 基于线性规划的求解算法 写出线性规划( 2 1 ) 的对偶问题： m a x b r y 7 口一d r p s 一彳7 y + 盯一p 2 c ( 2 - 4 ) 【弘口，p 0 根据线性规划的k l 山n m l c k 盯条件嗍，显然： 引理2 1 给定线性规划问题( 2 1 ) ，当且仅当存在向量工和( h 以p ) ，满足 a x b r 工d a 7 y + 盯一p = c ，只盯，p 0 y r ( a x 一6 ) = 0( 2 5 ) 盯7 ( z 一，) = 0 ( d x ) = 0 时，向量z 是其最优解。并且在此种情况下，向量c n 口，力为对偶问题( 2 4 ) 的最优解， 给定问题( 2 1 ) 的可行但非最优的解p ，令序数集：，= l ，2 ，m ，= 1 ，2 ，n ) 。 各紧约束条件的下标