（应用数学专业论文）工程调度与算法.pdf

摘要 摘要 工程调度问题可以描述为：在满足资源和时间受限的情况下，各种约束关系 的活动遵循目标函数的最优排序。由于工程的概念很广泛，工程调度问题在工业 制造，生产调度，资源分配等很多领域都有着相当广泛的应用。本文研究的动态 规划算法是在“最优化原理”的基础上，建立起来的数学规划新分支，也是解决工 程调度问题的一种特殊途径。在许多问题上利用动态规划甚至比线性规划等算法 更有成效。但是动态规划方法没有明确的模型和方法，对于不同的模型，在算法 设计上都有所差异，技巧性也很强。本文主要研究了一维排序问题中的动态规划 算法。在对原有的一维排序问题模型进行了些许改进的同时，给出了传统的动态 规划求解方法和改进后的嵌入状态空间的动态规划方法。在文章的最后讨论了大 规模和多维的扩展排序问题，为企业提升生产，管理效率提供可行的方法与技术。 关键词：工程调度排序问题最优化原理 a b s t r a c t a b s t r a c t p r o j e c ts c h e d u l i n gp r o b l e m c a r lb ed e s c r i b e da s ：t h ea c t i v i t yo fd i v e r s i f i e dc o n - s t r a i n t sf o l l o w st h eo p t i m a ls e q u e n c i n go fo b j e c t i v ef u n c t i o nw i t hl i m i t e dr e s o u r c ea n d t i m e b e c a u s eo ft h eb r o a dc o n c e p t i o no fp r o j e c t ，p r o j e c ts c h e d u l i n gp r o b l e mc a nb e w i d e l yu s e di nt h ei n d u s t r i a lm a n u f a c t u r e ，s c h e d u l i n ga n dd i s t r i b u t i o no fr e s o u r c e t h ed y n a m i cp r o g r a m m i n gr e s e a r c h e di nt h i sp a p e ri san e wb r a n c ho fm a t h e - m a t i c a lp r o g r a m m i n gb a s e do nt h e o p t i m i z a t i o nt h e o r y a n di sa l s oas p e c i a lw a yt o h a n d l ep r o j e c ts c h e d u l i n gp r o b l e m i ti sm o r ee f f e c t i v et ou s ed y n a m i cp r o g r a m m i n g t h a nl i n e a ro n ei nm a n ya s p e c t s h o w e v e r , t h e r ei sn o tf i x e dm o d e ln o ra l g o r i t h mf o r d y n a m i cp r o g r a m m i n gt h ed e s i g no fd y n a m i cp r o g r a m m i n ga l g o r i t h mn e e d ss p e c i f i c s k i l lf o rd i f f e r e n tm o d e l t h i sp a p e rc o n c e n t r a t e so nt h ed y n a m i cp r o g r a m m i n go fo l l e - d i m e n s i o n a ls e - q u e n c i n gp r o b l e m i tg i v e st h em e t h o do fb o t ht r a d i t i o n a ld y n a m i cp r o g r a m m i n ga n d i m b e d d e ds t a t e ss p a c ed y n a m i cp r o g r a m m i n ga n di m p r o v e st h eo r i g i n a lm o d e lo fo n e - d i m e n s i o n a ls e q u e n c i n gp r o b l e ma tt h es a m et i m e i nt h ee n d ，t h i sp a p e rd i s c u s s e st h e l a r g e c a p a c i t ya n dm u l t i - d i m e n s i o n a le x p a n s i o np r o b l e m ，w h i c hp r o v i d e st h ep r a c t i c a l m e t h o da n dt e c h n o l o g yf o rt h ee n t e r p r i s et oi m p r o v et h ee f f i c i e n c yo f p r o d u c ta n dm a n - a g e m e n t k e yw o r d s ：p r o j e c ts c h e d u l i n g ，s e q u e n c i n gp r o b l e m ，o p t i m i z a t i o nt h e o r y 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：僻 1 州8 年f 月力1 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：嘭扣寿、 训8 年r 月je t 第一章引言 第一章引言 二十世纪五十年代初，人们根据多阶段决策问题的特性，提出了解决这类决 策问题的“最优化原则”。所谓最优化，通常指的是从备选方案组合中，找出某问 题的最优解，是种广泛的实用科学，在工业制造，生产调度，资源分配，以及设 备布局等方面都有着相当广泛的应用。 动态规划最早和最重要的工作是由b e l l m a n 1 3 】完成的。主要是在提出了 “最优化原则”【1l 】的基础上，研究了许多实际问题和数学模型，建立起来的数学 规划新分支，也是解决最优化问题的一种特殊途径。在许多问题上，利用动态规 划要比用线性规划或非线性规划更有成效，这也是本篇论文选题的出发点之一。 动态规划( d y n a m i cp r o g r a m m i n g ) 是最优化中的一种特殊“方法”。它不象丹 特采哥( d a n t z i g ) 简化算法那样构成一种解决线性规划问题的，有明确定义的一 组规则 1 3 】。动态规划是求解某些类型最优化问题的一种方法，实际上是考察一 个问题的途径。动态规划没有固定的模型和解法，在寻找解法上技巧性也很强。 原理上，这种问题包含大量的相关决策变量，使得此问题可以转化为由一系列问 题组成的多阶段决策问题。更进一步说，我们要考虑的就是如何把解礼变量的问 题，转化为解仃个较简单的单变量的问题。 我们可以看到，在解决变量数目较大的问题上，动态规划方法是有其独特的 优势的。动态规划还有另外一个特点是泛函方程的“嵌入”特性，在之后的章节 我们会具体的讨论。嵌入状态空间的动态规划将会对计算量做进一步的简化。 但是动态规划也有它的缺点和限制，目前动态规划没有明确的模型和算法， 在实际应用中，不同的问题必须针对实际情况对原有模型加以修正和改进。对于 不同的模型在算法的设计上技巧性也比较强。本文主要研究工程调度中的生产力 扩展排序问题的动态规划方法。 工程调度是指需要时间和资源保障其任务或活动实施的系统，同时有一个期 望实现的目标( 例如：工期最短，资源消耗最少，净现值最大等) ，此外，在活动执 行期间还需要考虑它们之间的优先关系。由于工程的概念有着很广泛的解释，因 此工程调度问题在许多实际应用中都有所体现，包括建筑业，新产品的研发与生 产，资本市场的中长期投资，服务系统，软件包，现代企业的中长期规划，紧急情 第一章引言 况应对等。排序问题，即j o b s h o p 调度问题是类重要的组合优化问题，本文在 第三章给出了一维排序问题的模型，并对模型进行了改进，在目标函数中引入了 贴现的概念。由于动态规划方法针对不同的模型，算法设计上差别很大，技巧性 也很强。本文主要研究一维排序问题的动态规划方法，并在后面给出了改进后的 嵌入状态空间的动态规划方法，与常规的算法相比大大的提高了计算效率。在文 章的最后讨论了大规模排序问题和多维排序问题的动态规划方法 8 。通过“降低 维数”的求解方法，使得这类高维数问题用计算机计算和存储成为可能。 2 第二章动态规划概述 第二章动态规划概述 多阶段决策过程是指这样一类特殊的活动过程，过程可以按时间顺序分解成 若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个 决策序列。动态规划方法是解决多阶段决策过程最优化问题的一种常用方法，难 度比较大，技巧性也很强。动态规划方法的基本思想是：将待求解的问题分解成 若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的 解。动态规划方法将问题的解决方案视为一系列决策的结果，还要考察每个最优 决策序列中是否包含一个最优决策子序列，即问题是否满足最优化原理。 2 1常用术语 动态规划问题通常是用下列术语来表达的，一个系统或过程可以视为是按一 系nj i l 页序的级而向前发展的。在每一级，过程可用一相对来说较小的参数组来描 述或表征，这些参数称为状态变量或状态。在每一级，不管过程处于什么状态，都 要做出一次或多次决策。这些决策可依赖于级，或者状态，或者两者均依赖。当 做了一次决策后，会得到一个收益，同时过程经历一次变换或转移，到达下一级。 收益是由作用到当前状态的决策的已知单值函数决定的。按级发展的过程的总目 标就是使状态和决策变量决定的某个收益函数极大或极小化。 涉及动态规划问题的关键元素是级、状态、决策、变换和收益。下边我们将 更准确地定义这些术语。 级( 阶段) 为便于求解，将一个问题的全过程恰当地分为若干个相互联系的子过程( 阶 段) ，这些阶段就称为级或阶段。我们用这些级来表示决策的次序，最常遇到的级 变量是离散的。一般用自然整数1 ，2 ，3 来顺序的编号。 状态 第s 级的状态是指过程在该阶段所处的各种可能的情况。描述过程在第s 级 状态的变量，称为状态变量。状态变量用a 表示。全部过程可能存在的状态变量 的全体，称为状态空间，记为q 。显然q 仍，且a q 。 决策 3 第二章动态规划概述 当系统或过程处于级s ，状态入，从该状态演变成第8 + 1 阶段可利用的一种 选择称为决策或者决策变量，记为z 。( a ) 。对于每个a q ，可能做出的决策所构 成的非空集合弘称为a 的决策集合。 变换 动态规划问题中，所研究的是由一级变换到另一级的过程。过程从级s ，状 态入移动到其中的另一个状态所选择的决策( 入) 确定的状态集合t ( a ，( 入) ) 称 为一个变换函数，或称变换算子，它确定系统由一个状态到另一个状态的演变过 程。 策略 策略是一个按顺序排列的决策集合。由过程的第一阶段初始状态入1 开始，逐 阶段演变至终止状态a + 1 的过程称为问题的全过程。由每阶段的决策如( 入) ( s = 1 ，2 ，组成的序列 z 1 ( a 1 ) ，x 2 ( a 2 ) ，z ( a ) 】称为策略，用符号7 表示。所 有可能的策略集合就构成一个策略空间，记为r 。 收益 动态规划问题是一个最优化问题，因而有一个目标函数用来对某一给定的策 略进行评价。由于动态规划的嵌入性质( 这个我们将在后面章节具体讨论) ，我们 希望在不同于最终状态的其他状态上评价目标函数。所以，我们将定义收益函数 ( 或目标函数) 1 ( a ) ，它依赖于状态入和策略，y 。若过程起始于状态入，并且决策取 决于过程进行中通过的每一个状态的策略7 ，则1 ( 入) 是我们所得到的收益( 目 标函数相关的部分值) 。总收益( 入) 是级收益的某个组合( 即和或乘积) ，它是 当过程由一个状态到另一个状态( 一级到另一级) 移动的累积。我们将级收益记 为s ( 入，饥) 。 在动态规划问题中，所遇到的收益或目标函数，最简单和最常用的类型是相 加型的，其中总收益就是过程通过的每个状态的收益之和。但是，关于收益函数 应作一些假设，使得其满足递推的性质。这些假设可以有多种形式，但应保证收 益函数具有下述特性。 若。为某算于( 可为加或乘，但不仅限于这两种) 。 啪) = 袋裂q 蚺。) 若t ( a 1 ，讥。) o 若t ( a i ，饥。) = 入2 上式说明，在状态a 1 采用策略7 的总收益是下述两种收益运用算子。的结 果，它们分别是在状态入1 采用决策似。的级收益s ( a - ，似。) ，和在状态a 2 采用决 4 第二章动态规划概述 策弧。的总收益1 ( 入2 ) 。状态入2 是由入1 选择决策似。得到的，即t ( 入1 ，讥。) = a 2 2 2 最优化原理及条件 动态规划问题都可以构造一组特殊类型的泛函方程，称为递推关系。这些关 系使我们能以更简单的方式由前一级最佳收益推导出下一级的最佳收益。下面我 们来讨论包含极小化的泛函方程。 泛函方程 设有一个佗级问题，记级s = 1 ，2 ，3 ，n ，令k 为级8 包含状态变量的 向量。假定进行极小化的目标函数为乃( 巧) ，其他形式也是可以的，我们这里 仅讨论了一种形式。若共有8 个级，状态变量给定时，最佳收益可用下式给出： 幽( a s ) - r a 何i n 厶( 九) 有时称9 s ( 入。) 为状态函数，乱( 入。) 则表示在级8 上可供选择的所有决策变量 的向量。注意，决策变量与状态变量的值有关。 一旦九和z 7 ( 入。) 被选定，剩余s 一1 级的状态变量的向量可用及a ，( a ) ) 给 出一组典型的递推关系，或包含极小化的泛函方程如下： 夕。( 入。) = m i n f 。 , k 。，x s ( a 。) 】+ g s 一1 | 【t 【a 。，z 。( 入。) 】) ) ( 2 1 ) g l ( ：h ) = m i n f l a t ，z 1 ( a 1 ) 】) ( 2 2 ) 山l 其中，8 = 2 ，3 ，佗对于一维极小化问题就可以按照递推公式逐次求解了。 最优化原理是多级决策过程导出泛函方程所依赖的原理，通常称为 b e l l e m a n 最优化原理 一个最优策略( z 1 ，z 2 ，) 所具有的性质是，不论初状态a o 和初决策 x l ( a o ) 如何，由初始决策x l ( a o ) 产生的状态入1 之后的那个一1 ) 级过程 选择的剩余决策( z 2 ，z 3 ，z n ) 也构成一个最优策略。 为了能引用最优化原理，导出递推关系，从而有效地应用动态规划，有两个 条件必须满足，它们是： ( 1 ) 目标函数的可分性； ( 2 ) 状态可分性。 下面依次讨论这两个条件： 5 第二章动态规划概述 目标函数的可分性 目标函数的可分性是指，对于所有k ，一个礼级过程的最后k 级对目标函数 的作用，仅取决于状态k 一七和最后k 个决策x n - 七+ 1 ，一k + 2 ，。我们可以看 到式的( 2 1 ) 递推关系在任何级s 对收益函数的影响，仅取决于入。一1 和决策。 所以式( 2 1 ) 和( 2 2 ) 就是可分性的“相加型。同理，我们也可以得到“相乘”型 的可分函数，这里暂且略过。 状态的可分性质 状态可分性又称马尔可夫性，是指在级s + l 选择决策x 。+ 1 之后，得到的状态 a 卧1 仅取决于入。和z 卧l ，而与以前的状态a 1 ，a 2 ，a 。一l 无关。在式中，我们可以 看到入外1 只与z 卧1 和吼( a 。) 有关，所以满足状态的可分性，有时也称马尔可夫 状态性质。这个性质说明，当我们做决策z 。+ 1 时，需要用到的关于过去状态的信 息包含在a 。之中，而与先前状态没有直接关系。或者说在任何级，状态只取决于 当前的状态和当前的决策，而不用理会导致当前状态的所有过去的状态和决策。 在求解动态规划问题时，我们常遇到的困难就是怎样定义这个问题状态和级， 使得我们有一个计算上有用的表达式。但是理论上动态规划的模型总是可以用如 下方法求出最优化问题的一种表达式。 假设我们希望求解的问题目标函数是： m i n z = 厂( z 1 ，x 2 ，x n ) 约束为 h i ( x l ，x 2 ，z n ) 0( i = 1 ，2 ，3 ，佗) 我们定义状态变量y 。为： y 。= ( x l ，x 2 ，z n )( 8 = l ，2 ，3 ，n ) 约束h i ( x l ，x 2 ，z n ) 0 ，可代之以下列形式的一些关系式： x l r 1 ，x 2 兄2 ( z 1 ) ，x a r s ( z l ，x 2 ，x s - 1 ) ，z n r n ( x l ，x 2 ，x n - 1 ) 6 区一 某 的内在 岔包示表 、i j ， 以 现现“ r 定给 经 已o 现研 中 。 其域 第二章动态规划概述 当我们已经确定待解决的问题需要用动态规划算法求解时，通常可以按照以 下步骤设计动态规划算法： 1 、分析问题的最优解，找出最优解的性质，并刻画其结构特征； 2 、递归地定义动态规划递推方程及边界条件； 3 、采用自底向上的方式计算问题的最优值； 4 、根据计算最优值时得到的信息，构造最优解。 1 3 步是动态规划算法解决问题的基本步骤，在只需要计算最优值的问题 中，完成这三个基本步骤就可以了。如果问题需要构造最优解，还要执行第4 步； 此时，在第3 步通常需要记录更多的信息，以便在步骤4 中，有足够的信息快速 地构造出最优解。 7 第三章排序问题及其动态规划方法 第三章排序问题及其动态规划方法 3 1 排序问题的一些基本概念 排序问题，即j o b s h o p 调度问题，是一类重要的组合优化问题，一直在工厂 生产，企业物流管理中有着相当广泛的应用，下面简单的举出几种计划调度问题： 1 在维修车间用设备( 机器) 修理汽车( 工件) 的调度； 2 在学校里把各班级( 工件) 安排到各个教室( 机器) 上课的计划； 3 安排病人( 工件) 进行检验( 机器) 的计划； 4 在海港安排船舶( 工件) 在各个泊位停泊的调度； 等等。 对于排序问题，总是由佗个工件和m 台机器构成的，当己知每个工件加工 的机器次序和每个工件在每台机器上的加工时间，需要确定每台机器上的各个工 件的起始加工时间，使得给定的目标函数值达到最优，这样的优化问题就是排序 问题。 设一个工件要在m 台机器上依次加工，且每台机器只加工一次。若工件i 依 次在机器尬舰心，舰咖上加工，这里( i i 口2 ，i 帆) 是( 1 ，2 ，m ) 的一 个排列，则我们用互= ( i i q 2 ，i 饥) 来表示工件i 的次序，以互作为第i 行 的n m 矩阵t 的第i 行，其中t 称为j o b s h o p 问题的( 机器) 次序矩阵。如果 对于所有的工件次序都相同，即乃= 乃，v i ，j ，则此问题称为f l o w s h o p 调度问 题。 工件i 在机器尬上加工称为一个工序，记为i 。工序岛所需用的时间用只，g 表示。则工件i 的加工时间向量只= ( 只 1 只2 ，只，m ) 构成一个以只为第i 行 的n m 矩阵尸，称为j o b s h o p 问题的加工时间矩阵。 通过介绍以上的记号，n 个工件在m 台机器上的加工排序问题也可以描述 成：已经给定次序矩阵和加工时间矩阵，要在每台机器尬( 口= 1 ，2 ，m ) 上确 定所有工件的加工次序( 即机器耽上的工件次序) 和每个工序的开始时间，以使 得某个目标函数达到最优。机器鸩上的工件次序用向量8 口= ( q i ，1 ，q i ，2 ，吼，n ) 表示，则8 口构成第g 行的佗xm 矩阵的第g 行，s 口称为一个序列( s e q u e n c e ) 。 8 第三章排序问题及其动态规划方法 我们可以看到j o b s h o p 问题的关键就是要确定它的序列。而对于f l o w s h o p 问 题，佗m 矩阵序列的每一行都是相同的，它的一个序列实际上就是( 1 ，2 ，n ) 的一个排列。 对于n 个工件，m 台机器的排序问题，如果给定了次序矩阵和加工时间矩 阵，则要确定一个序列( 由每一台机器上的工件次序组成) 和各工序加工的起始 时间。序列和各工序加工开始时间表就称为该问题的一个调度( s c h e d u l e ) ，记为 s n o 定义3 1 一个序列中给出的各工序的先后次序关系和已知的次序矩阵给出的 工序先后次序关系是相等的，则该序列是可行的。 在排序论中，我们常常要借助和讨论网络图，下面简单的介绍一下网络的概念。 网络图主要由点和连接各点的矢线( 也称弧) 组成，我们常用点来表示工程 项目中的活动，或称工件，任务等，用弧来表示他们之间的关系。 定义3 2 设x 为顶点的集合，a 为顶点的有序偶集合，则( x ，a ) 构成图。当 图中的弧规定了方向，则称该图为有向图。 有向图中弧的方向可以用来表示工件执行的先后次序。具体的介绍可以参见文献 4 】 定理3 1 在一般的排序问题中，一个序列是可行序列，当且仅当由给定的次 序矩阵和序列作出的有向图不包含任一回路。 证明如果有次序矩阵和序列作出的有向图中存在一个回路，那么处于回路 上的任何两个工序有两种相反的次序关系，因而序列是不可行的。反之，如不存 在回路，那么任何一个工序可在某个加工时间按图上给出的优先关系实现，因而 序列是可行的。 口 推论3 2f l o w - s h o p 调度问题的任一个序列是可行的。 证明对于f l o w s h o p 调度问题所有工件的机器次序都相同，而按照序列画 出的有向连线只有垂直方向的先后次序，且在同- n 不构成回路，因此图中不存 在任何回路。 口 9 第三章排序问题及其动态规划方法 3 2 一维排序问题的模型 在基础建设投资管理中，生产设备规划，资源规划调度等方面常会遇到一类 特殊的排序问题一一含容量扩展的排序问题，它是一维排序问题的推广。之后我 们研究的排序问题主要是指这类含容量扩展的问题。这里的容量是指“工程”的 载量，生产力，能量，产量等等满足需求的“能力”。下面我们将介绍这类问题的 模型，主要以生产力扩展问题为主，并在之后的章节介绍通常的动态规划和扩展 的动态规划方法寻求这类问题的最优化解法。 在工程建设项目中，一个工程由若干个子工程组成，每个阶段的子工程提供 的生产能力是有限的，我们将研究如何合理的安排每个工程提供的生产能力，使 得在任何时候都能满足需求，且使得这些工程的目标函数，也就是花费的费用最 小。为了导出此问题的数学模型，先引入如下记号：设为可行子工程的数目；g 为第i 项子工程在完成时的基本成本( 投资成本) ；q t 为第i 项子工程提供的生 产能力；d ( t ) 是时刻t 工程的需求；t 为工程的工期( 计划周期) 。 对工程项目具有如下特征： 1 g 在工期内为常数； 2 子工程i 完成后达到全部的生产能力q t ( 满容量) ； 3 在工期内，子工程i 产生的生产能力一直存在； 4 各种操作和分配的费用是与实际生产能力成比例的，且比例系数对于所有 子工程都相同； 5 当前的生产必须满足需求； 总生产能力q 。是由初始生产能力与子工程在t 时刻提供的生产能力之和。 于是问题归结为求时间变量( t 1 ，亡2 ，抽) 使得费用最小。 一维排序问题可以建立如下模型： m i n a ( t ) ( 3 1 ) 扛= 1 1 1 , s t q i ( t ) = d t ，v t 0 ，卅 上述模型不仅含有关于q i 的子工程选择决策，还含有关于t 的子工程投产 1 0 第三章排序问题及其动态规划方法 时间决策，为了将该问题化为一维的调度问题，设 s 1 ( p m ，蜀2 】，p z 1 ) ，p t , j 1 ，2 ，) 且p f 司p o j ，v i ，j = 1 ，2 ，l 。于是8 1 表示一个l 一工程序列，1 n 。这样问题 转化为求序列 ( 蜀1 】，1 ) ，( 蜀2 1 ，2 ) ，( 蜀1 1 ，如) ) 满足以下模型： m i nf k l e s i 2 e 。k l s t i k t g ( t )( 3 2 ) q ( t ) d t ，v t 【0 ，卅 其中【】表示工程在序列中的位置，缸为长度为zf i 2 - f 程序列。5 为( j ：7 ) f ! 个可能序列中的个或较少的工程集合。在这里，从个工程中选z 项，则有 ( 7 ) 种，再考虑工程的排列问题，则有( 7 ) z ! 个长度为2 的工程选择序列。于是可 以构造出所有的工程序列，最优化问题转化为求( ? ) z ! 个序列中最优的一个的 l = o 、。 一维排序问题。 因为b 作为在时间t 的生产力需求，在 0 ，t 】上是单调非减的，则一维调度 问题就可以化为一维排序问题，且总满足 d ( t ) ( q t ，驯 ( 3 3 ) i e k n 一1i e k n 其中k n 一1c 硒，且是工程序列。事实上，对于一个给定的- 工程调 度：q 1 ，q 2 ，q m 其中 q ( t ) = d t ，v t 【o ，卅 l = 1 不一定是最优的，我们需要考虑该调度的所有可能的! 个置换调度。下一节的 定理我们将证明排序问题如果存在一个可行解，那么所有的! 个置换调度都是 可行的，且至少有一个置换调度是最优的。这样由于q 的先后执行，约束方程可 以写成 q i ( t ) d t ，v t 【o ，卅 = l 同时为了使得d ( t ) q t ，q 】总是成立，就必须有f = n ，这样就得 到一维排序问题。问题也转化为求置换调度的最优性。其中置换调度问题可行解 集是由! 个工程序列构成的集合。 第三章排序问题及其动态规划方法 下面考虑将上述模型改进一下，将原目标函数中的基本成本改进成贴现成 本。经济学中，货币是具有时间价值的。现在的货币可以进行投资，在未来获得 收益，所以它的价值要高于未来货币的价值。贴现值的引入将未来货币的价值折 算到现在来衡量。这样更贴近实际的情况。 设r 为年利率。新的模型为： m l n k t e 5 s 七 g ( ) ( 1 + r ) _ d 一1 ( 咖) ( 3 1 0 ) 我们先来讨论第一种情况。 j - ij 一1 若凶 d - i ( 锄) ，n d 1 ( q i , i ) d ( t 己】) 由图( 3 2 ) 可以看出， j - i 当t ( d 一1 ( q 【司) ，t 0 】) 时， f = 1 j - 1 有d 一1 ( q 【引) d ( t ) i = 1 因而岛是不可行的。当然也不是最优的。 再讨论第二种情况。不失一般性，令d 】= p ，由( 3 1 0 ) 式有；a一 力 +q q + ，p a一 力 + 0q ：l | | 瓯 矿p 哆 譬 哆 譬 一 ，+ ， ， 0 ，使得 q = q ，v i 圣j 根据定理3 3 我们知道最优调度一定可以在置换调度中找到。设s n 为最优的置 换调度。同时假设& 不满足定理的结论，也就是说在踟中至少存在一对工程 【l 】 【k 】奶，使得 t i t t l k ，c t t q i t i 】 根据假设t i t t i k ，q 司q f j 】 g ， 1 7 第三章排序问题及其动态规划方法 因而有 ( 1 + r ) 一 ( 1 + r ) 一 所以p v ( s j v ) p y ( 品) ，且等号只有在 = 时成立。由此可见，当 时，踟不是最优调度，与假设矛盾。故定理结论正确。 口 1 8 第四章多维排序问题的动态规划方法 第四章多维排序问题的动态规划方法 我们所说的“多维”是指工程i 需要满足酝= ( q n ，q 协，q l m ) 的多目标 需求。比如一个汽车生产厂商，他不会只生产同一型号的汽车，他可能同时生产 轿车，大型客车，货车等等，这样工程项目一级中具有多于个状态变量的问题， 就是多维排序问题。 一般来说，对于高维数的状态变量和决策变量，最优化原理可以直接应用。 但是有些问题其每一级的状态变量或决策变量多于一个时，所需的存储量和计算 量就会大大增大，使问题变得难以处理。粗略的晚，动态规划算法仅限于维数小 于6 的问题，否则的话，计算和存储对计算机的要求将无法满足。 下面我们将探讨一下多维数的生产力扩展排序问题及其动态规划方法。在沿 用之前大部分记号的基础上，我们再引入或者修改如下一些记号； ( 1 ) = 1 ，2 ，) 是多目标工程集合，其中每一项工程i 的容量向量为 q i = ( q ，q 滔，q t m ) ，q ，是工程i 用来满足第歹项需求的生产力。 ( 2 ) d j ( t ) 表示t 时刻的第j 项需求( j = l ，2 ，m ) 。 对给定的皿，r ( 连续的利率) ，g ( 多目标工程i 的主要建造费用) ，q 巧，b ( t ) ，t ， 其中i = 1 ，2 ，n ；j = 1 ，2 ，m ，若工程满足3 2 节的假设1 5 ，那么此m 维容量扩展排序问题的一个调度鼬是根据皿构成的有序且相互关联的一个序 列项工程。设防 = i ，用来表示工程标号i 皿是踟中的第j 位。一个调度 鼬是由序列8 和该序列中每项工程的完成时间构成的。 即： 鼬= ( q 1 】，t i l l ) ，( 蜀】，q 】) ( 4 1 ) 其中，序列8 n = ( 鼻1 】，蜀m ) 多维排序问题可以如下描述：求一个调度踟，使得 觚r a i n s g e 州 曲醪急 ( 4 2 ) 成立。其中g 为多目标工程中第i 项工程的基本成本。r 为连续利率，我们默认 任何工程的完成时间都是从计划期开始的，即从t = 0 时刻开始，令t t 为第i 项 1 9 第四章多维排序问题的动态规划方法 工程的完成时间。5 表示满足需求的所有调度踟构成的空间。 5 = s 1 q 巧( t ) d j ( t ) ，v t 【o ，t 】，j = 1 2 m ) ( 4 3 ) i 田 其中q 巧是第i 项多目标工程满足第歹种需求的生产力。d j ( t ) 表示在时间t 的第 j 种需求；t 为计划期。 由于s 含有无穷多个点，用传统的动态规划方法求解会造成困难，下面我们 考虑用嵌入状态空间的动态规划方法。 定义多目标工程的工程时间函数，类似于( 3 7 ) 式定义妒( 口) ，有 7 ( g ) 2 删r a i ，n 以s 删u p ( t j l q j 、_ 儿m a x p ( ) ( 4 4 ) 其中q = ( q l ，9 2 ，q m ) 为流通容量向量，劬为满足第j 种需求的总累积生产力。 若所有的功( t ) 是不减函数，则( 4 4 ) 可以简化为 7 ( g ) 2j ：唑m 淋s u 0 p ，刀( t j l q j b ( 伽 ( 4 5 ) 若所有的b ( ) 均为连续且严格单增函数，则它的逆函数存在 巧1 ( 劬) = t j 且这是唯一的。则( 4 4 ) 进一步简化为 丁( g ) 2j ：器粤，m 【丐1 ( 劬) 】 有礼个工程组成的置换调度是满足以下性质的调度& ，第i 个位置上工程 i 】i 的 完成时间为 即在一个置换调度中，第i 个工程完成前一刻的流通容量为前i 1 个工程的生产 力之和。所以每一项工程的建造在置换调度中相对于需求来说是尽可能推迟的。 类似于一维排序问题，可以证明；所有置换调度是可行的，且至少有一个置换调 度是晟优的。 嵌入状态空间q 竹是由佗个工程组成的所有( ! ) 个置换调度的累计容量向量 的集合，其元素记为9 1 ，9 2 ，g ( ：) 。设w n ( q 。) c 皿表示由q 。= ( q l , ，畦，g k ) 64n2l = m七q 脚 七q 胁 膏q “脚 丁 = 第四章多维排序问题的动态规划方法 决定的，恰好提供容量为q 。的竹工程序列的集合；设n 为( n n ) 个不同的n 一- v 程集合。则状态向量q 。q n 与佗工程集合皿n 的元素是l - 1 对应的。即： g l q nhu n ( g f ) c 皿竹 设厶( g i ，必，g ) 为可以产生状态向量( g i ，畦，g ) 的礼一工程的最小贴现成 本。则嵌入状态空间的函数方程递推公式为： 厶( q i ，吐，也) = m 矧i n c i e r f g i q 1 也一q m + 厶一( g i q m ，g 乞一q ) ) 0 7 ) 一二，忍，( ：) 或者写成： 厶( g i ，吐，q ) = 曾1 【g e - r r ( g 一q + 厶一- ( q l q d ( 4 8 ) 佗：1 ，2 i ，f ：1 1 2 ，f ，、1 其中i = u n ( q 2 ) 一o j n 一1 ( g f q t ) ) ，即i ( 9 1 ) ，且i 粤0 j n 一，( 矿一q i ) = ( ( q 。) 一i ) 。厶一l ( q 。一q ) 是提供( q i q m ，q l m q m ) 的( 礼一1 ) 一工程置换调 度的最小贴现成本。( ( 9 1 ) 一i ) 皿n l 恰好的产生状态向量( 矿一q i ) q n 一1 。 由于q o = _ 【( o ，o ) ) 而且岫( 0 ，0 ) = 仍，故递推公式的边界条件是； 如( o ，0 ) = 0 ( 4 9 ) 从以上计算公式可以看出，在多维问题的嵌入状态空间动态规划中，虽然对每一 个q 2 计算厶( 口1 ) 时计算量比一维情况大，但对于n ，q n 的元素数目仍为( n n ) 个， 所以计算时间和存储量随着m 的增长，增长幅度不大，这样就解决了“维数灾 难”。 多维问题常在基础投资规划，水利工程( 水坝，水库等) ，交通干线规划等领 域得到广泛的应用，而且还可以解决贷款管理问题。比如水资源调度问题【1 8 ， 我国虽然淡水资源丰富，但是人均可利用的淡水资源却很少，而且分布很不均匀。 大量淡水资源集中在南方，北方淡水资源只有南方水资源的1 4 。据统计全国 6 0 0 多座城市中，已有4 0 0 多个城市存在供水不足问题，目前我国城市供水以地 2 1 第四章多维排序问题的动态规划方法 表水或地下水为主，或者两种水源混合使用，有些城市因地下水过度开采，造成 地下水位下降，有的城市形成了几百平方公里的大漏斗，使海水倒灌数十公里。 而且由于工业废水的肆意排放，导致8 0 以上的地表水、地下水受到不同程度的 污染。在这样的背景下，水资源的合理分配和统筹规划就显得尤