（应用数学专业论文）支付调度的旋转算法.pdf

摘要 摘要 物流业是衡量一个国家或地区经济发展水平、产业发展环境、企业竞争力 的重要标志之一。我国现代物流的发展，正在一项项的物流工程建设和各个层 次物流系统运营中实现。 本文以物流工程的建设为背景，讨论了在大规模复杂的物流工程投资和调 度上，如何在满足工程项目的预定目标下使工程项目的建设成本达到最小。首 先对物流工程与项目的财务评价作了介绍，建立支付调度问题的数学模型，这 是一个非线性规划，具有线性约束和非凹目标函数，证明了该问题可以变换为 等价的线性规划，最后给出模型的有效求解方法一旋转算法。 关键词：支付调度现金流净现值线性规划旋转算法 a b s t r a c t a b s t r a c t l o g i s t i c si so n eo ft h ei m p o r t a n tm a r k so fw e i g h t i n gt h ee c o n o m i cd e v e l o p m e n t l e v e l ，t h ei n d u s t r i a ld e v e l o p m e n ts u r r o u n d i n ga n dt h ee n t e r p r i s ec o m p e t i t i o no fo n e c o u n t r yo ra r e a h o w e v e rt h ed e v e l o p m e n to fc h i n e s em o d e r nl o g i s t i c sr e l i e so nt h e c o n s t r u c t i o no fe v e r yl o g i s t i e sp r o j e c tg r a d u a l l ya n dt h eu s eo fe a c hl e v e l l o g i s t i c s s y s t e m t h i sp a p e rf o c u s e so nt h ed i s c u s s i o no ft h ei n v e s t m e n ta n ds c h e d u l i n go fl a r g e s c a l ec o m p l e xl o g i s t i c sp r o j e c ti nw h i c hh o wt om i n i m i z et h ec o n s t r a i n tc o s t , w i t ht h e s a t i s f y i n go ft h es c h e d u l ea i mb a s e do nt h ec o n s t r u c t i o no fl o g i s t i c sp r o je c t f i r s t l y , w eg i v ea l lo v e r v i e wo fl o g i s t i c sp r o j e c ta n dp r o j e c tf i n a n c e s e c o n d l y , w em a d et h e m a t h e m a t i cm o d e lo ft h ep a y m e n ts c h e d u l i n gp r o b l e m ，w h i c hi sn o n l i n e a rp r o b l e m w i t hl i n e a rc o n s t r a i n ta n dn o n - c o n c a v eo b j e c t i v ef u n c t i o n t h i sp a p e rp r o v e dt h e p r o g r a mc a nb et r a n s f o r m e di n t ol i n e a rp r o g r a me q u a li nv a l u e a tt h ee n dw e g i v ea n e f f e c t i v em e t h o d r o t a t i o na l g o r i t h mt os o l u t et h em o d e la t t a c h e da s p e c i f i ce x a m p l e k e y w o r d s ：p a y m e n ts c h e d u l i n gc a s hf l o w sl i n e a rp r o g r a mr o t a t i o na l g o r i t h m i i 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 守承啦局 加9 年，月叩日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：彳寸弗哺 竺翌三上羔一丑昱一 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月 日 各密级的最长保密年限及书写格式规定如下： r j 内部5 年( 最长5 年，可少于5 年) ! 秘密l o 年( 最长1 0 年，可少于1 0 年) ：机密2 0 年( 最长2 0 年，可少于2 0 年) ； 第一章预备知识 第一章预备知识 第一节引言 支付调度是具有相互联系活动的大规模复杂工程中，定义了每个事件的 发生及发生次序，持续时间，同时在每个事件发生时，又己知的现金额需要 交换( 收入或支出) 由于这种大型工程的复杂性，经常需要绘制出工程图， 通过对工程图的深入研究来控制整个工程 本文讨论的是在物流工程中，已知某项目的工程图( c p m 或p e r t 型) ， 求一个调度即工程图中的一棵树，使得收入或支出得净现值达到最大值 该问题是一个非线性规划，具有线性约束和非凹目标函数本文的主要结果 是证明该调度问题等价与线性规划并且对该问题提出求解方法一旋转算法 第二节物流与物流工程 何为物流? 顾名思义为“物的流通”( p h y s i c a lo i s t r i b u t i o n ) 或者可以说 是物品从生产地至消费者或使用地点的整个物流过程根据g b t1 8 3 5 4 2 0 0 1 物 流术语的定义“物流是指物质实体从供应者向需求者的物理移动，由一系列 创造时间价值和空间价值的经济活动组成，包括运输、保管、配送、包装、装 卸、流通加工及物流信息处理等多项基本活动”因此随着时代的演变，物的流 通( p h y s i c a ld i s t r i b u t i o n ) 观念逐渐被物流( l o g i s t i c s ) 观念所取 代l o g i s t i c s 原意为军事上的后勤补给，在商业应用方面则指行销后勤，强调 运输、仓储、装卸等作业处于行销通路的重要地位又由于近年来电脑及信息 科技的发展，使得物流信息逐渐迈向全球化的目标值此时期由“工业经济时代” 转变为“知识经济时代，商业界意识到信息管理的重要性，其经营策略也从“供 应连管理”发展至“全球运筹管理 而知识经济时代最明显的特征就是信息化 的网络经济，而网络经济的杰出代表就是电子商务，因此可以说，现今的时代 就是电子商务时代电子商务时代的来临给全球的物流带来了新的发展契机，也 使现代物流具备了一些新的特点现代物流的发展趋势是信息化、自动化、网络 化、智能化、柔性化物流系统是在一定的时间和空间里，由所需输送的物料之 第一章预备知识 间和包括有关设备、输送工具、仓储设备、人员以及通信联系等若干相互制 约的动态要素构成的具有特定功能的有机整体物流工程是指在物流管理中从 物流系统的整体利益出发，把物流与信息流融为一体，运用系统工程的理论和方 法，为物流系统的规划、管理和控制选择最优方案，以最低的物流费用、最好的 服务质量，提高社会经济效益的综合性组织管理技术物流工程急需解决的问题 就是怎样使物流活动适应现代化生产的需要，实现合理化、系统化，选择什么样 的物流方案才能取得最佳的经济效益除此之外，物流工程还包括运输、配送、 保管、装卸、流通加工及物流信息处理等多项基本活动这一系列的物流课题的 研究和解决，都需要运用现代化的管理和方法才能实现 随着我国改革开放逐步深入，国民经济和对外贸易迅猛发展，并越来越快地 融入到世界经济体系当中，如何加速发展与国际接轨的现代综合物流业，成为我 国面对的一个时代课题而中国现代物流的发展，需要依靠一项一项的物流工程 建设，依靠各个层次物流系统的运营来实现物流工程包括：物流基础工程、物流 设施工程、物流管理工程、物流技术工程及物流运营工程特别是物流基础工程， 其主体是国家物流基础工程网络是实现物流的重要生产力要素，它集中了物流 系统的主要设备、设施、技术人员、管理人员、劳动人员这些生产力要素配置 在由物流据点和物流线路所构筑的实物物流中物流基础工程又分为物流运营 基础工程、物流信息基础工程、物流基础性支持工程物流运营基础工程主要由 国家创建，如铁路线路建设工程、物流基地建设工程、物流中心建设工程、货运 站场建设工程、货运公路建设工程、高速公路建设工程、货运枢纽建设工程、 港口码头建设工程、货运航空港建设工程等，并且对物流的运营起到平台支持的 作用而在现代物流的发展过程中物流基础设施平台决定着整个物流系统的水 平一个能够有效共用的、高技术水平的、标准化的平台，对提升物流运作水平 有着非常重要的意义全国物流中心之一，环渤海地区的物流基础设施平台建设 已经全面展开，如天津港集装箱物流中心，总投资6 8 亿，预计2 0 1 0 年前完工，这 是环渤海物流区域非常具有影响的工程本文从大规模复杂的物流工程投资和 调度方面出发，研究投资主体在满足工程项目的预定目标条件下如何使工程项 目的建设成本达到最小，并为物流工程项目投资与管理提供了可行的有效方法 第三节项目的财务评价 2 第一章预备知识 1 3 1 工程项目的概念 项目是一项有待完成的专门任务，在一定组织机构内，在限定的资源条件下， 在计划的时间里，满足一定的性能，要求，质量，数量而完成的一次性任务 根据投资项目对投资决策过程的影响，我们可以将其分为三类：独立项目、 互斥项目和依存项目独立项目是指人们拒绝或接受该项目时对其他项目的决策 不会造成直接影响的项目；两个或者更多不能同时存在的项目成为互斥项目；依 存项目是指一个项目的拒绝或接受必须取决于一个或多个其他项目的拒绝或接 受 工程项目是由相互联系，相互制约的研究、技术、生产、管理活动所组成 这些活动具有优先关系工程中每项活动也称为一项任务，完成需要时间与资源 工程项目是唯一保证或努力完成又可以划分为个别子任务的活动，而且每项活动 均需要时间和稀缺资源才可以完成 1 3 2 项目现金流的概念和原则 在决策一个项目之前，最重要最复杂的过程是对计划的投资项目进行财务评 价而现金流的评价是其中最重要的起始阶段因为很容易用现金流来度量项目 对公司财富的作用 现金流是指在某特定时点上公司的收入和支出其中，某些现金流是现金流 出，如资本支出；而另外一些现金流是现金流入，如销售收入等净现金流量是 给定时期内的现金流入减去现金流出的值 净现值是指预期的净现金流量的折现总和 获得现金流的时间越长，投资者就会认为现金流的净现值越小同样，获得 某现金流的风险越大，投资者就会认为这个现金流的净现值越小 为了评价一个项目，人们必须对该项目的现金流进行识别简单说，项目的 相关现金流是指引起公司总的现金流的变化量，公司以此作为决定是否接受该 项目的直接依据因此，项目相关现金流是公司现有现金流的变化量或增量，通 常被称为增量现金流或边际现金流 项目评价是建立在增量现余流的基础之上的增量现金流是指给定项目未来 的现金流入和流出，它将随着项目的消失而消失增量现金流可以通过比较公司 在有或没有这个项目时的现金流之间的差值来衡量分析比较这两种情况就能 得到现金流的边际量或叫增量 3 第一章预备知识 根据用途可以将现金流分为两类：固定资产的现金流和运营的现金流通常 情况下，最大的一笔资本流量是初始投资，也叫做初始资本支出或资本开支初 始资本支出通常是指在一个项目开始时所需的现金输出，这些资金用来购买或 置备资产并使其处于正常运行状态“初始”代表了现金流出的时间当初始投 资过程完成之后，项目开始投入运营我们期望项目能够在整个经济寿命周期中 产生现金流这种现金流就是运营现金流，包括销售现金流入、广告和营销的现 金流出、支付工人工资、能源和照明费用以及原材料采购费用等在项目经济寿 命周期的最后阶段还有一项资本流动，即项目的期木现金流 估计和识别相关现金流量时应遵循的原则有： ( 1 ) 独立项目的原则该原则指人们将完全根据项目提案自身的价值来评估该 项目 ( 2 ) 间接或协同效应项目现金流量的计算应该包括所有的间接或协同效应的 计算项目的协同效应可以是积极的也可以是消极的若一个项目提案是引进一 种新的产品或服务，而该产品或服务与公司现有的某项产品或服务互补，这样 就会增加现有产品的销售额考虑这些间接影响的基本原理都是以机会成本原 则为基础的 ( 3 ) 机会成本原则在投资预算中，机会成本指在投资一个项目时为此而放弃 的所有替代项目方案中收益最高的那个项目的价值在计算项目现金流时应该 充分考虑其机会成本 ( 4 ) 沉入成本原则沉入成本就是过去发生的与项目有关的费用，现在无法将 其收回，而且也不能通过当前的项目决策去弥补沉入成本是过去发生的和不可 改变的，所以它与项目提案的接受或拒绝无关，因此不应将其纳入项目现金流 之中 ( 5 ) 一般管理费用管理原则在项目评价中，不是将一般管理费用分摊给生产 单位，而是识别新增加的一般管理费用一般来说，上马或不上马一个项目都会 发生一般管理费用，这部分费用并不是由于接受或者拒绝一个项目带来的在项 目分析中，应该按照机会成本和沉入成本的原则，将一般管理费用分摊到项目 提案的现金流中只有当一般管理费用的变化引起增量现金流时，才能将其包括 在项目评价中 ( 6 ) 对流动资本、税金、折旧、投资津贴、财务资金流的处理原则 ( 7 ) 现金流的年内时间价值原则投资预算的标准惯例是假设资本支出发生在 4 第一章预备知识 年初，而其他现金流则发生在年末为了保持计算的一致性，现金流的时点 被设定在上一年的年末 ( 8 ) 在通货膨胀时期现金流的确定原则通货膨胀会影响项目的预期现金流， 无论是现金流入或现金流出一般情况下，当预期通货膨胀率很高时市场利率 ( 如利息率和资产回报率) 将会上升随着市场利率的上升，投资要求的回报率 也将上升为了能恰当地处理通货膨胀，项目分析必须考虑到预测未来现金流时 预期的通货膨胀的情况，并采用能够反映投资者对未来通货膨胀预期的折现率 通货膨胀会对现金流的不同组成部分产生不同的影响，因为名义利率考虑了通 货膨胀，而实际利率没有考虑通货膨胀，所以用名义利率进行现金流的预测比 用实际利率预测准确的多项目折现现金流分析的一致性要求：如果一个项目的 现金流在名义科目里就应该用名义利率来折现，如果一个项目的现金流在实际 科目里就应该用实际利率来折现实际科目和名义科目是不能混同的 1 3 3 项目评价中的基本公式 在财务分析中最重要的一个原则就是资具有时间价值。我们必须将在不同时 间发生的现金流转化成同一时间的现金流，才能判断现金流入是否大于现金流 出。 利率就是单位时间的资金价值增值部分与原来资金( 本金) 的比值。实际利 率厂是指货币在一段时间后实际购买力的增长率；名义利率尺是指货币在一段时 间后表面价值的增长率。 利率分为单利和复利，单利是指资金在增值过程中，本金数与计息周期无关 的计算方法，公式为 f v = p v ( 1 + n r ) ， 其中p v 为本金( 原投资额) ，为计息期内利率， 之和。 复利计息时，反映了资金的时间价值，公式为 f v = p v ( 1 + r ) 4 ， 其中p v 为本金( 原投资额) ，为计息期内利率， 之和。 在实际计息中通常采用复利计算公式。 i 1 为计息周期数，f y 为本利 n 为计息周期数，f y 为本利 连续时间复利计算。假设时间t r 0 是连续的，投资或交易可以在 5 第一章预备知识 v t r 0 上进行，则利息可按复利连续计算。例如，初始投资额为尸， 则f 年将增利到p v o ( 1 + ，) ，其中，| 为年利率。若每年按复利计算n 次，则在f 年 内，p 增长到p v o ( 1 + 厂) “。于是，连续复利计算公式： 。 厂。 ，f + = + 一r ) - r - 一：il i m ( 1 + - - r ) r l i m ( 1 l i r a ( 1l i m ( 1l ：p ，。+ 二- ) “=+ 一) r= li = p 玎。 n - - o o 刀 ”。 胛 l n - + o o n j 因此f 矿= p v ( 1 + ，) ”可以写成 ，v = 尸y e t r 0 设f y 为终值，则 f 圪= p p ”， 其中p 为资金现值( 现期) ，圪为第r l 期资金终值。根据f 圪= p v o e ”式有 尸z o = f v e 一” 这表示第，z 期的资金终值贴现到期初为f v e ，其中e 州为折现公式，为折现 率。 设c 。，c ：，c 。为投资序列( 流) ，则，z 期总收益的现值为尸矿= c ，p 一。 设投资流为c ( f ) c o ，f 0 ，丁】，则在时段 o ，r 】上的总收益的现值为 p v = 【c ( t ) e d t 。 1 3 4 常用的项目评价指标 项目评价的方法有两大类：折现的现金流分析( d c f ) 和为未折现的现金流 分析( n d c f ) 。第一类包括净现值( p y ) 和内部收益率( x r r ) 。第二类包括投资 回收期( p p ) 和投资报酬率( a r r ) 这里使用第一类 一 净现值( n p v ) 项目的净现值( n p v ) 是用现金流入的现值减去现金流出的现值而得到的。 如果资本输出只发生在第一年年初即e o y o ，那么它就已经是现值，没有必要再 进行折现。这种情况下的n p v 公式为： 脚2 善南一c o智( 1 + 厂) 2 c n 是第一年年初的资本输出，这里t = 0 。 如果资本输出发生在不同的年份，相应的公式为： 6 第一章预备知识 p y ：j l 一争旦 删2 善南一善尚鲁( 1 + ，) 智( 1 + 厂) 7 判断法则： 若n p v 0 ，项目予以接受，n p v 0 ，项目被拒绝。 二项目周期无限迭代的净现值 当互斥项目的寿命不等时，我们不能直接用净现值来比较项目。这种情况下 适合计算n p k ，它只不过是同样项目在重复无穷多次后得到的现金流的净现 值。一个永续周期净现值所用的公式，是一个普通永续年金的净现值再加上一 个初始的净现值： 御一一+ 群尚 茸中 、l p 圪表示项目周期无限迭代的所有现金流的净现值； 尸k 表示项目周期初次迭代的现金流的净现值； n p 圪表示项目周期迭代玎次后的净现值； l ( 1 + ，) ”一1l 表示项目寿命期利率。 判断法则： 若肿0 ，项目予以接受，胛 0 ，项目被拒绝。 三 内部收益率 对项目进行评价时，另外一个可选的方法是计算项目的内部收益率。它计 算的是当n p v 等于。时的收益率厂( 折现率c o = c ，p 州) 值，一般用脚表示。 士c ； 缶面葡邓o ， 其中c 为各期现金流入量，c 0 为期初投资资金总额。在项目评价中，这个 比率必须等于或大于接受该项目的临界收益率即若i r r 资本成本，项目被接 受；i r r 资本成本，项目被拒绝。 净现值和内部收益率承认资金的时间价值，都是相对较好的标准。然而内 部收益率方法具有概念和计算上的一些缺陷，因此也不应作为最主要的决策标 准。只有净现值方法涉及现金流的时间价值，是最优的投资决策标准。在某些 特殊或有约束的情况下，人们也可以使用内部收益率法。 折现率是从国家角度对资金机会成本和时间价值进行度量的评价指标。采 7 第一章预备知识 用适当的社会折现率对项目进行投资评价，有助于合理使用项目资金，引导资 方向，调控投资规模，促进资金在全社会范围内的合理配置。 8 第二章支付调度问题 第二章支付调度问题 第一节模型建立 设变量乃是事件f ( f - 1 , 2 ，柳的发生时间，对于i n ，z 是常数，它是 鼻的初始事件时间，活动( f ，) 在i + 岛完成，规定活动在所有f 只均完 成时才能开始代数上为： 乃一互c 0 ， _ ，= 2 ，n ，i e 工程周期为巧一互，即丁；一瓦d ，通常假定互= 0 ，并称一1 维向量 t = ( 正，瓦) 为一个调度最后的约束条件化为万 设e 是节点一弧关联矩阵，它的元素按如下规则取值 f 1 ， ( f ，) 么， e u = 一1 ， ( j ，f ) a ， l0 ， 否则， 因为该网络有n 个节点，l a l 条弧，所以e 是n xa i 矩阵于是调度约束为 t e d ，其中t = 阢，疋，瓦】 若视见为距离，那么从1 到的最长路径便是工程周期设民是周期， ( 矿，彳，d ) 表示8 0 万事件f 的最早开始是它可能的最早时间，它等于1 到i 的最长 路径事件i 的最迟开始时间是与巧= 6 0 的最迟时间相一致例如，设邯j 是f 的 最早开始时间，s 是f 的最迟开始时间，贝, 1 e s i2 m 浃a x 爿( e s ，+ 弓) ，其中e 位事 件歹的工时，l s ，2 m ，j i n 彳( l s ，一只) ，其中p 为事件f 的工时 在时刻正，用于交易的货币和为q ，q ，是收入为正，支出为负货币的折现 率为口这样，在互的时刻交易的现值为q ，e x p ( 一嵋) 假设q ，= 0 任何调度r 的 现值是 厂( 7 ) = q ，e x p ( - a t j ) ， i = 1 因此，支付调度问题的数学模型可以表示成如下形式 m a x ( r ) s t t e d( i ) 对这个模型作如下几点说明： 。 9 第二章支付调度问题 问题( i ) 有可行解瓯万； 若万= + o o ( 工程无时间限定) ，则不可能达到最大值； 当譬j 变号目标函数不是凹的( 或拟凸的) ，局部最大值存在 第二节支付调度问题变换为线性规划 线性规划是一种当决策者在一些限制或约束因素下进行决策时，用来从一系 列可供选择的项目方案中选出最优组合的数学方法。目标函数和约束可以用一 系列线性方程来表示，它们是由决策变量和输入参数来定义。输入参数是用来 描述系统特征的，他们是由决策者确定的。 定义向量 y = ( y l ，y 2 ，y ，) ， 其中 y f = e x p ( 一嵋) 或 正= 等郫) 则非负向量丁和正向量y 具有1 1 对应关系y = y ( t ) ，因此问题( i ) 的目标函数 厂( 丁) = q ，e x p ( - a t ，) 变换为 y ( r ) q = y q 定义常数 k 移= e x p ( a d f ) ，( f ，j ) a 于是 k 打1 ( ( f ，j ) ( n ，1 ) ) ， 而0 k j v l 1 则问题( i ) 的约束 t e d 即 乃一正d f ，( f ，j ) a ， 其中互= 0 ，变换为 1 0 第二章支付调度问题 y ，k 扩一y fs0 ，( f ，j ) a ， 其中y 。= 1 因此，问题( i ) 变换为线性规划 1 1 m a x 己y i q i i = l s t y ，k 1 ，1j e ( i i ) y ，k 盯一y ， 0 ，f _ 2 ，n ；j e y j v 一k | v 1 定理1问题( i ) 和问题( i i ) 是等价的，即 o ) t 是( i ) 的一个可行解y ( t 1 是( i i ) 的一个可行解； ( 2 ) 丁是最优的y ( t ) 是最优的 证明：由于f ( t ) = y ( t ) q ，则( 2 ) 的成立易从( 1 ) 成立得到 设y = y ( t ) ，则t 满足( i ) 的约束 z l n ( y i ) 岛，_ ，互 ( 一口) 。 1 石i n ( y ) 一祟彬2 ，；，鼻 ( 一口)( 川) 。“ 掣甄巧6 ( 川) 一 约束司以化为 h a y ，一a d l ，= l n x ( ，j 曩 i n ( 孚) = l n y ，一i n y f - 0 ，则i n u l l n u 2 ”l u 2 ，于是推 出约束条件等价于 y ，粝1 ， j 互 y _ y z ，昏江2 ，；j f 第二章支付调度问题 y k l ， 上式乘以适当的系数，得到( i i ) 的约束条件 口 由于问题( i i ) 中约束条件的表达形势相对复杂，可以引入矩阵g 和行向量 c 进行化简 设g 是一个nxi a i 的矩阵，其元素与矩阵e 的对应关系是 l 0 ， 当勺= 0 ， g ，= - 1 ， 当e 扩= - 1 ，f = 1 ，2 ，；= 1 ，2 ，h 【e x p ( a d 扩) ，当p = 1 ， 可以看出，矩阵g 和矩阵e 的关系是由定理1 所确定的 设c 是定义在么上的行向量，具有h 个元素，c 1 = 1 ，歹互，c ，= 一k v 。， 否则c ，= 0 于是问题( i i ) 化为 m a x y 。q s t y g c ( i i7 ) 在我们假定如果项目的净现值为正的话，就可以实现最大化。 第三节求解方法 前面已经证明，支付调度问题变换为线性规划问题，我们可以用线性规划的 一种以旋转运算为基础的解法一旋转算法来求解这个问题 2 3 1 基本概念和相关定理 线性规划是在一个线性不等式组的解集中找一个解，使得某个线性函数取得 最小值或最大值其数学模型为 m i nz = c x s t 口j x = b i ， i = 1 , 2 ，z ； 口f x b i ， f = z + 1 ，z + 2 ，m ( 3 1 1 ) 或 m a xz = c x ， s t 口f x = 岛，i = 1 , 2 ，z ； 口f x b i ，i = z + 1 ，+ 2 ，m ( 3 1 2 ) 其中c 是n 维行向量，x 是n 维未知列向量，口；是以维行向量，b i 是标量， 12 第二章支付调度问题 汪1 , 2 ，m c x 称为目标函数，各等式和不等式称为约束条件如果所有约束条 件构成的不等式组有解，称其解为可行解所有可行解的集合称为可行域 设s 是可行域，如果存在x s ，使得对于任何x s ，有cx cx ，则称 x 为线性规划( 3 1 1 ) 的最优解，z = c x 称为最优目标( 函数) 值同样，如 果存在z s ，使得对于任何x s ，有cx 。ox ，则称x + 为线性规划( 3 1 2 ) 的最优解，z = c x 称为最优目标值 口。，口：，口。中一个最大线性无关组称为线性规划的基，基中的量称为基向 量，其余向量称为非基向量基向量对应的等式或不等式约束称为基约束，其余 约束为非基约束所有基约束构成的不等式组称为基本不等式组基本不等式组 对应的方程组的解称为基本解 从几何上看，基本不等式组的解集是一个锥，由于它与一组基向量对应，称 为基锥，其顶点便是集本解。对于最小化线性规划( 3 1 1 ) ，如果一个基锥的 所有点均在半空间c x 一m 内，则称为正基锥，这里m 是一个充分大的数。同 样，对于最大化线性规划( 3 1 2 ) ，如果一个基锥的所有点均在半空间麟m 内， 则称为正基锥。如果一个正基锥的顶点是最有解，称其为最优正基锥。最优正 基锥对应的向量称为最优基向量。 2 3 2 线性规划的旋转算法 从几何上看，线性规划的旋转算法开始于一个正基锥。若其顶点如工( 1 是可 行解，则x ( 1 是最优解。否则存在一个违反不等式( 或等式约束) ，如口，z 阮使 得口，z ( 1 o ，i j 2 j ， 则口，入基 规则2 一最大距离规则： 在所有偏差为正数的非基不等式中，以距离当f j i 基本解最远的违反不等式 入基即若 南= m 南：咿叫厶) ， 则口，入基 规则3 一最小下标规则： 在所有偏差为正数的非基不等式中，以编号最小者入基：在取得最小比值的 基不等式中，以编号最小者出基即若 ，= m i n i1 2 ：g 0 ， 则口，入基：若 一n 陋6 移。- - - 1 - k = t g , k 1 1 ，【j 其中 秒一 詈：妒。，叫， 则口。出基 2 3 3 支付调度问题的旋转算法 本文要研究的支付调度问题实质上是一个整数线性规划，在一个线性规划 问题中，如果要求全部或部分变量取整数值，则称为整数线性规划，其数学模型 可写为 s t 口j 工= b i ， i = 1 , 2 ，： 口f 石b i ， i = ，+ 1 ，+ 2 ，m 工i 为整数，j ， ( i ) m a xz = c x ， s t 口j x = b f ，i = 1 , 2 ，l ； 1 8 第二章支付调度问题 口，z b i ，f = ，+ 1 ，+ 2 ，m x ，为整数，j ， ( i i ) 其中 c ，口l ， 是，z 维行向量，2 j 1 ，6 2 ，屯是标量，x = g 。，x 2 ，) ，是 1 ，2 ，z ) 的子 集，0 ，m 变量取整数的限制称为整数约束解一般整数规划的常用方法有一种称为 分枝定界法，另一种称为割平面法这两种方法实际求解的是一系列具有越来越 多线性约束的松弛问题即整数规划中去掉整数约束添加线性不等式后得到的线 性规划。本文分别讨论旋转算法在分枝定界法及割平面法中的应用 旋转算法在分枝定界法中的应用： 设厶是整数规划( i ) 或( i i ) 的松弛问题，其最优解为 i = 瓴，夏，瓦) ， 如果要求变x k 取整数值，但瓦不是整数，就在厶中分别添加不等式约束 k 】+ 1 和以阮】， 构成两个线性规划厶和乞，其中k 】表示不大于瓦的最大整数即可行域中满足 【瓦j o , j 1 1 2 m 诬 詈，吾，三) = j 1 ， p ，出基，旋转运算结果列表3 2 ： q p 2 9 c 虿 1 l e 3 一一2 1 6 3 一i 06 0 7 口3 2 3 。 2 5 表3 2 中仅口，的偏差是负数，入基。由于 m i n 朦h 吃出基，得第二次旋转运算结果列表3 3 2 0 第二章支付调度问题 e 1口3 1 01 c 33 2 1 7 巳 3 33 j i 0 6 二 712 5 p 2 63j 在表3 3 中，以e ，入基，e ，出基，得第三次旋转结果列表3 4 e 3口3 c5 2 31 7 白 222 933 4 4 4 711 7 巳 444 至此所有非基向量偏差非负，松弛问题的最优解为x = ( 三，导，。) ，最优目 标值z = 2 6 。 一 一l1 但_ = 三，x z = 了不是整数，不妨以为分枝变量在问题1 中分别添加约束 而4 和一x l 一3 构成两个子问题，记为问题1 1 和问题1 2 。 首先解问题1 1 ，五4 关于最优解的偏差为三2 4 = 一三1 ，将表3 4 中e 1 的 偏差由三改为一圭，得表3 5 ( 1 u - i n l 1 ( 1 ) ) e 3口3 c52 3 11 e 1 2 2 2 933 444 711 7 e 2 444 2 1 第二章支付调度问题 在表3 5 中以p 。入基p ，出基，旋转运算得表3 6 ( 问题1 1 ( 2 ) ) e 1口3 l o1 c 33 211 e 3 33j 3 口2 一互0 o 7111 p 2 6 3 j 此表所有非基向量偏差非负，得问题1 1 的最优解x = ( 4 ，竽， ) 7 ，最优目 标值z = 2 7 - 。 x ：婴不是整数，以工：为分枝变量，分别在问题1 1 中添加约束x ：4 和 一x 2 一3 构成两个子问题，记为1 1 1 和1 1 2 以下求解问题1 1 1 ：恐4 的偏差为芸一4 ：一昙，将表3 6 中的p ：的偏差 改为一三，得表3 7 ( 问题1 1 1 ( 1 ) ) e 1口3 1 01 c 33 2 11 巳 333 3 吃 2 。0 0 7 1 l e 2 6 3 j 2 2 第二章支付调度问题 在表3 7 中以e ：入基，a 3 出基，旋转运算得表3 8 ( f - jn1 1 1 ( 2 ) ) qp 2 9 c 。2 1 1 白 一一2 1 0 3 2 0 0 凼为a 3 x 岛是几余的，已经去捭，所以返是i 叫题1 1 1 的最优表，最优解为 z = ( 4 ，4 ，o ) r ，各分量均是整数，其最优目标值z = 2 8 是整数规划的上界。 以下解问题1 1 2 ，接表3 6 ，由于该表最优解为 工= 悖扩 不等式一x ：- 3 的偏差为 一导一c 一3 ，= 一詈， n n 3 6 中的乞换为一p ：，将偏差竽换为一弓，将该行其余数字反号，得表3 9 ( 1 h - 题1 1 20 ) e l 口3 l o1 c 33 211 e 3 333 3 一i 0o 二 7 + 12 一p 2 6 33 在表3 9 中以一e ：, k n ；e 。出基，运算结果得表3 1 0 ( f - j 题1 1 2 ( 2 ) ) 一p 2口3 2 09 c 77 415 巳 777 93 6 777 2 3 第二章支付调度问题 由于表3 1 0 中口2 的偏差是负数，开且i 司仃所有糸数也为负，l 司题1 1 2 尢司 行解。 下面解问题1 2 ：接表3 4 ，表3 4 的最优解为 x = ( 弹。卜 一x 1 - 3 的偏差为 一五7 一( 一3 ) = 一三， 将表3 4 中的p 。换为一p 。，将偏差三换为一三1 ，将该行其余数字反号，得表3 1 1 ( 问 题1 2 ) e 3口3 c5 2 311 一e 1 222 933 444 71 1 7 9 2 444 由一e 行可见，此问题无可行解。 所以问题1 1 1 的最优解x = ( 4 ，4 ，o ) 7 是原整数规划的最优解。 旋转算法在割平面法中的应用： 割平面法是一种解整数规划的一般方法，这种方法利用整数条件构造一些 不等式逐步添加到松弛问题中，每个添加的不等式去掉可行域中不含整数解的 一部分，称之为割平面法。下面介绍在旋转算法的框架下用割平面法解