（应用数学专业论文）清江水布垭大坝土石方填筑施工问题的研究与应用.pdf

华中科技大学硕士学位论文 摘要 i 清江水布垭堆石坝是目前在建的世界第一高的堆石坝。其土石方填筑施工的 工期紧，道路窄。在满足建筑物施工控制进度的前提下，要合理安排建筑物开挖 进度与程序，达到其与大坝填筑进度和填料要求相匹配的目的。，一“ 本文首先在概述经典运输问题的模型和方法步骤的基础上，研究了国内外对 运输问题中“多反而少”悖论问题的建模与求解方法，其中详细地研究了悖论的 产生原因及如何避免产生悖论。并对变量约束运输问题和运输变量有上界的运输 问题分别进行了深入细致的分析，提出了它们的模型和求解方法。然后从作者所 参与的清江工程土石方调运系统的实际工作出发，以其中的调度优化模型中的运 输方案生成及优化模型为例，建立和求解能反映实际运输问题特点的大型物流调 运系统运输问题的模型。( 该模型具有如下特点：1 约束变量在一定范围内可以变 动，2 有多个带有库存容量的中转点，3 运输量有上界限制，4 以整个工程及调运 过程的总费用最少为目标，5 考虑到了土石方的开采成本及库存费用。着重讨论 了利用表上作业法求解这种模型的可行性。并就模型的建立、可行解存在的判别 准则、求解矩阵的简化和求解过程提出了具体的步骤与算法。进而对如何优化可 行解进行了详细的证明与论述。同时举出具体的算例证明了该算法的可行性可一 本文为进一步深入研究该问题奠定了良好的基础，且对今后日益发展的水利 工程施工建设与调度具有较高的参考价值。以后的工作是进一步考虑引用随机理 论来仿真一些不确定性因素来解决风险问题。 关键词：运输问壶y 悖论丫表上作业彭变量约隶_ 上界 华中科技大学硕士学位论文 a b s t r a c t q i n g j i a n gr i v e rs t o n ed a m i st h eh i g h e s to h ea tc o n s t r u c t i o ni nt h ew o r l da t p r e s e n t t h et i m ei sl i m i t e da n dt h er o a di sc o n f i n e da n d i ti sn e c e s s a r yt om a k em a t c h t h ep r o g r e s so ft h ed a m c o n s t r u c t i o na n dt h a to f t h ed i g g i n gu n d e rt h ec o n d i t i o nt h a t t h e yc a ns a t i s f y t h ep r o g r e s sa n d p r o c e d u r eo f t h ew h o l ec o n s t r u c t i o n b a s e do nt h es u m m a r i z a t i o no ft h ec l a s s i c a lt r a n s p o r t a t i o np r o b l e m m o d e l i n ga n d a l g o r i t h m s ，t h er e c e n tr e s e a r c ho nm o r e f o r l e s sp a r a d o xi nt r a n s p o r t a t i o np r o b l e mi s d i s c u s s e d ，a n dt h er e a s o nw h yt h e r ei sap a r a d o xa n dt h ew a yt oa v o i di ti ss t u d i e di n d e t a i l v a r i a b l ec o n s t r a i n t t r a n s p o r t a t i o np r o b l e ma n dt r a n s p r o r t a t i o np r o b l e mw i t h u p p e rb o u n d a r ea n a l y s i s e dr e s p e c t i v e l y t h e nt h e i rm o d e l sa n dt h e w a y s t os o l u t et h e m a r eb r o u g h t o u t t a k i n gt h ed i s p a t c h i n gs c h e mo p t i m i z a t i o nm o d e lo fq i n g j i a n gr i v e r d a ma st h eb a c k g r o u n d ，t h i sp a p e rd i s c u s s e sh o wt oe s t a b l i s ha n ds o l v et h em o d e lo f t h ep r a c t i c a lt r a n s p o r t a t i o np r o b l e mi nl a r g e s c a l em a t e r i a ld i s p a t c h i n gs y s t e m n 坨 m o d e li s p r o v i d e d w i t hs e v e r a lc h a r a c t e r i s t i c s 1 t h ec o n s 仃a i n tv a r i a b l ec a nb e f l u c t u a t e di nac e r t a i n r a n g e ，2 ，r e l a y s t a t i o n sh a v et h e i ro w ns t o r a g e s 3 t h e t r a n s p o r t a t i o n v a r i a b l e a sh a v eu p p e r b o u n dl i m i t s 4 t h e g o a l o ft h em o d e li st 1 1 e m i n i m i z a t i o no ft h ew h o l ec o u r s e si nt h ed i s p a t c h i n gs y s t e m 5 ，t h ec o s to f d i 呼n g a n d s t o r a g ei sc o u n t e di n t h ef e a s i b i l i t yo f c o l u m ng e n e r a t i n ga l g o r i t h mi se m p h a s i z e do n a n dac o n c r e t ec a l c u l a t ew a yi s b r o u g h tu dt o s o l v et h ep r o b l e ma n dt oe s t a b l i s ha m o d e l t h ep r o c e d u r e sa n d a l g o r i t h m sa r eb r o u g h to u tt os e tu pam o d e la n ds o l u t ei t a n dt h ew a yt o o p t i m i z et h eb a s i sf e a s i b l es o l u t i o ni sj u s t i f i e d a n da ne x a m p l ei s t a k e nt op r o v et h i sa l g o r i t h m se f f i c i e n c y t h ew o r ko ft h i s p a p e r e s t a b l i s h e dw e l lb a s e m e n tf o r f l l r t h e t - s t u d y a b o u t q i n g j i a n gr i v e rc o n s t r u c t i o n ，a n dh a sag r e a tr e f e r e n c ev a l u ef o rc o n s t r u c t i o na n d s c h e d u l i n go fi n c r e a s i n g l yd e v e l o p i n gw a t e rc o n s e r v a n c yc o n s t r u c t i o n s t h ef o l l o w i n g w o r kw i l lb eh o wt os i m u l a t et h eu n c e r t a i nf a c t o r st os o l u t et h er i s kp r o b l e mi nt h i s t r a n s p o r t a t i o np r o b l e mw i t hr a n d o mt h e o r y k e y w o r d s ：t r a n s p o r t a t i o np r o b l e m ，p a r a d o x ，c o l u m n g e n e r a t i n ga l g o r i t h m v a r i a b l ec o n s t r a i n t ，u p p e rb o u n d 华中科技大学硕士学位论文 1 绪论 1 1引言 运输问题，就是制定最佳运输方案，使一批发点中的货物运送到一批收点时， 所消耗的总运费( 或总吨公里数) 为最少。 运输问题的应用十分广泛，其解法除了主要用于解决交通运输中的线性规划 问题外，还可以用于生产管理等各方面同类型的线性规划问题。把运输问题作为 线性规划问题来描述和求解是线性规划方法最早和最言有成果的应用之一。 随着现代化生产的发展，传统的运输问题渐渐不能满足实际问题的需要，因 此提出了对更为符合实际的运输问题进行深入研究的要求。 1 2 课题背景 我国水利水电工程正以前所未有的规模和速度发展着，特别是堆石坝更是突 出。清江水布垭堆石坝是目前在建的世界第一高的堆石坝。它位于清江上游龙头 电站，处于高山峡谷区，地形地质条件复杂。枢纽由面板堆石坝、溢洪道、引水 式地下电站系统、导流洞、马崖高边坡等建筑物组成。面板堆石坝坝高2 3 3 o m ， 填筑工程量为1 6 6 6 4 万m3 ，是世界上同类坝型的第一商坝。枢纽主要土石方工 程量为：土方开挖3 5 4 5 1 万m3 、石方明挖2 1 2 4 9 5 万m 3 、石方洞挖2 0 1 5 3 万m3 、土石方填筑1 7 4 2 0 3 万i n 3 。工程旖工总工期为9 5 年。 枢纽土石方工程施工具有以下特点：( 1 ) 工期要求。工期总工期限制较紧，但 由于工程复杂，某些工程项目可能因多种原因延误工期。为保证大坝的沉陷与变 形满足设计要求，必须严格控制填筑质量和科学规划填筑程序，填筑质量要求高， 施工计划性强；( 2 ) 多处取料。水布垭面板堆石坝的石料一鄱分来自溢洪道等工程 开挖的石料( 开挖的部分石料用于填筑，在施工中尽量优先采用) ，另一部分来自 几个采石场的开采石料。大坝填筑主要利用溢洪道、引水式地下电站系统、导流 洞、：弓崖边坡等建筑物开挖岩石料，在满足建筑物旌工控制进度的前提下，合理 华中科技大学硕士学位论文 安排建筑物开挖进度与程序，使其与大坝填筑进度与填料要求相匹配，提高建筑 歼挖料利用率和直接上坝率，或以最经济的路线和方式上坝填筑，对降低工程投 资和保证大坝填筑进度、质量意义重大；( 3 ) 中间储备。由于大坝在填筑的不同阶 段所需石料不同，而由于施工的安排某些开挖必须在前，因此开挖的石料不一定 直接用于填筑，需要设立中间储料场；( 4 ) 道路限制。坝址两岸岸坡陡竣，施工道 路布置困难。拟布置道路坡陡、弯多，道路间高差大，运输条件差，是控制建筑 物开挖与大坝填筑的重要因素。施工场地狭窄，施工道路紧张，道路要用于废弃 料的运输、填筑石料到储料场、开挖石料直接到大坝、储料场石料到大坝以及大 坝建设其他设备材料，另外道路有的平直，有的坡度较大，如何组织运输使运输 尽量保证安全，又保证大坝施工要求。 由于上述四个主要原因，在水布垭施工中必须利用现代信息技术，及时向施 工管理部门提供旌工进展情况，并且根据工程的实际进展实时制定最优施工方案。 图1 给出了这一调运系统的“流”描述。 、1 信息流 叶物流 一车流 图中我们可知其中可以分类为三种系统：运输系统( 包含各种道路、车库、 华中科技大学硕士学位论文 大型起重转运设施等) 、库存系统( 包含各种中转储存点、弃料场等) 、各种料场 等( 包括大坝、工程开挖和采石场) 。 i 3 运输问题的“悸论”及实际运输问题的研究 发量和收量确定不变的经典运输问题的建模及求解方法己十分成熟。但是在 更为普遍的实际问题中，发量和收量不确定的情况和运输量受限制的情况越来越 多。另外，在许多大型物流调度运输问题中，都必不可少地存在进行短期库存的 中间转运点。而且，对于一些经典运输问题的最优解，经常会有加大运输量反而 能够使得运输费用减少的运输问题“悖论”。因此，提出一个更为实用、且能够避 免和解决运输问题“悖论”的模型，已成为工程实践对理论提出的一个新问题。 “多反而少”悖论及其相关属性首先是由a c h a m e s 和d k l i n g m a n 在分配问 题模型中提出并研究的f l j 。他们在其他存在类似悖论的规划问题中也进行了相应 解说。1 9 7 1 年，s z a w r c ( 2 i i 正明了一些与线性规划类似的定理。在随后的研究中， m j r y a n t 3 1 通过实例讨论了“多反而少”饽论是可以将原来的分配问题分解为系 列无关的子问题的，并且提出使用退化解法来解决悖论。而a c h a r n e s l 4 1 等人在 1 9 8 0 年的研究证明了这个观点的正确性。 a c h a r n e s 和s d u f f - u a a 5 1 后来将分配问题模型中的“多反而少”悖论逐渐推 广到一般线性规划中来，并对运输问题模型中的悖论问题进行了深入的研究，给 出了产生这种悖论的充要条件。确定了运输变量的分析方法与般优化分析求解 之间的关系，并且对线性规划的悖论进行了经济意义上的解释。g b d a n t z i g 、 c e l e m k c 、m p y a n 、w w c o o p c r 等人分别对悖论问题提出了变量带上界约束的 模型、相应的经济解释及优化决策方程等。d k l i n g m a n 和r r u d d e l l 解决了一种 带变量限制的运输问题。这篇文献对本文要研究的目标函数为运费率、收发量为 变量，并且有带库存的中转储备点的运输问题有一定的借鉴意义【6 】【7 l 【8 i 9 1 i o 】。 葛万斟2 4 ，梁俊国，董成业f 2 5 1 对运输变量有上界的幽问题的探讨和解法， 经作者检验得出前者的用解法较为严谨，她的解法是对一般运输问题的一种补充 与扩展。刘晓华1 4 9 l 对于一般情形的运输问题，考虑到需求量和供应量可以有指定 范围的般情形，建立起运输问题的一般模型，给出了求解此问题的表上作业法， 华中科技大学硕士学位论文 初步解决了经典运输问题“障论”的求解问题。李登峰【5 0 1 1 5 t i 先提出了变量带上界 的运输问题的一种新的对偶算法：又提出了带模糊条件的物资调运系统的概念， 并设计了其数学模型，给出了相应的网络解法。黎青松【3 ”，李温红 3 6 1 的研究对于 清江工程中中转储备点的选取有一定的借鉴意义。石涛口s 】研究了在可存储条件下 如何进行资源有限一工期最短的优化。谢政，多磊等人【4 2 l 阐述了带容量限制和手。 续费用的运输问题。郭郴生【5 2 】、李东f 5 3 】、魏祥云酬研究了如何建立实际运输问题 中的调运模型。他们的研究对清江工程面板堆石坝的土石方调运均产生了一定的 启发。 1 4 本文内容及章节安排 本文共分六章。第一章为绪论，简要阐述了课题和意义( 选题依据) 。第二章 阐述经典运输问题及其求解步骤，转运问题( 转运点无库存) 的模型建立及求解 思路。第三章分析了实际生产生活中存在的运输问题“悖论”，介绍了已有的变量 约束运输问题模型，然后由课题中的实际运输问题提出了适用的数字模型并将该 模型推广到其他实际运输问题中。第四章由推导变量约束且运输量有上界的运输 问题的求最优解的表上作业法的结果，指出该问题无法通过表上作业法求解。引 入奇偶开路的定义，提出两条新的优化求解定理，并对赵新泽提出的利用开路调 整来求近似最优解的方法进行了必要的补充。第五章以此工程的调度方案优化模 型中的运输方案生成及优化模型实际求解为例，将本文提出的实际运输问题的模 型及求解方法实际应用编写成计算机求解应用程序，求出最优解，与经典运输问 题最优解进行比较，得出该算法求解合理、快速、有效的结论。第六章为全文工 作的总结，及对未来工作的展望。 4 华中科技大学硕士学位论文 2 经典运输问题及转运问题 2 1 定义及相关定理 2 1 1 问题描述及模型建立 经典运输问题描述如下： 数量分别为a i , a ：，a 。的同类产品分别从，1 个运输发点a ，( f _ 1 , 2 ，m ) 运出， 由n 个运输收点色( _ ，= 1 , 2 ，甩) 接收，所接收的产品数量分别为b 。，6 ：，b 。对于 所有的组合( f ，) 来说，从第i 个发点到第，个收点运输个单位货物的费用c 。是 己知的。问题是如何确定各个运输途径( f ，) 的运输量x 。，使运输的总费用为极小。 表2 1 1 运输问题运价表 x b j 收点 l2 j n发量 l x l l而2 x l j x l nq 2 x 2 1x 2 2 x 2 x 2 na 2 发 点 t lx 2 x p z m口l x m i工m 2 工州 x n n口m 收量 b lb 2 b ， b 。 为了研究问题的约束条件，我们建立表2 1 1 。从发点i 到收点_ ，的运输量为 _ ；从发点f 运出的数量是q 0 ，由收点，接收的数量是6 j 0 。这里我们暂时 加上一个运输总量等于接收总量的限制，也就是说，口f = 6 f = a 。运输嘞单 位的总费用是勺z f 。因为负的装运量没有实际意义，我们限制每个x f 0 。从表 华中科技大学硕士学位论文 中我们可以得到运输问题的数学描述是下述问题的解 s t = i = 1 2 ，m j - i h = b ， x 。0 ，i = 1 , 2 ，m ；，= 1 , 2 ，n f 2 1 1 ) j ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 方程组( 2 1 2 ) 代表表2 1 1 中的行和，方程组( 2 1 3 ) 代表表2 1 1 中的列 和。为了使方程组( 2 1 2 ) 与( 2 1 3 ) 相容，( 2 1 _ 2 ) 的各方程的总和必须等于( 2 1 3 ) 各方程的总和，即 = = q = b ，= a t * 1 ) - ij - l t = lt = l = l 我们注意方程组( 2 1 1 ) 到( 2 1 4 ) 是一个具有m n 个变量与( m + n ) 个方程 的线性规划问题。 2 1 2 运输问题的相关定理 下面给出该线性规划问题的几个相关定理，有助于对运输问题的理解和算法 推导。 定理1 运输问题有可行解。 定理2 基本可行解的构造。存在一个最多含有r n + n 1 个正的x 。的基本可行 解。 定理3 若和是非负的整数，则每个基本可行解( 即极点解) 取整数值。 引理l 简化的运输问题方程组的每一组m + n 1 个线性无关向量可以重排成 一个三角矩阵。 定理4 有限的极小可行解必定存在。 定理5输送问题及其对偶问题同时存在最优解当且仅当 6 x 勺 。州 ， = z”埘叩 华中科技大学硕士学位论文 a ，o bj o ，y a ；= y b j a 若条件成立，则 “。= l j j ：1 m i n c 。 为原设问题及对偶问题的可行解。根据弱对偶定理，对偶双方同时有最优解。 2 2 求解方法及计算步骤 我们可以直接用单纯形法解运输问题。可是对于m 个发点及n 个收点的问题， 当m 与n 的值不太大时，m + n 1 个方程和r l l n 个变量的线性规划问题的维数也会 变得相当大。因此要研究如何减少计算量的问题。象研究大系统分解问题那样， 应先考察运输问题矩阵的特殊结构，分析这种结构可能会带来什么好处。我们已 经证明基本解有一个三角矩阵结构。利用这一点，结合修正单纯形算法及对偶性 质，来研究单纯形法的一种变形，使这种变形用在运输问题上时，计算更加有效。 我们首先考虑由( 2 1 1 ) 至l j ( 2 1 4 ) 所给出的( m + n ) 个方程的运输问题，把它看成 是非对称原始一对偶问题组的原始问题。对这种问题，考虑由变量( u ，如，, 。) 及变量( v 。，v ：，v 。) 所组成的m + r 1 个对偶变量集w 是方便的，即w = ( 。，“：，u 。，i t i ，v ：，) 它是一个行向量。运输问题的极大化对偶问题可由原始 问题的矩阵用w 左乘而得到。由( 2 1 1 ) 到( 2 1 4 ) 所给出的( m + n ) 个方程的运 输问题，其相应的对偶问题是： m a x 叩，+ 屯v ， i j s - t “+ v 。f ，i = 1 , 2 ，m ；j = 1 , 2 ，n ( 2 2 1 ) ( 2 2 2 ) 设f p p 是原始目标函数值，g ( w ) 是对偶目标函数值，应用原始一对偶问题 中的类似互补松弛性的讨论，对于运输问题，关系式 ( 勺一一v ，如= ( g ) 一9 0 v ) 0 ( 2 2 3 ) 7 盟& = b 华中科技大学硕士学位论文 对满足相应约束条件的任何x 和w 都成立。注意到x 。0 ，所有的 c ，一“一v ，0 ，从而( 2 23 ) 式是非负数的乘积之和。因为m i n 厂( ) m a xg ( 矽) 并且已知运输问题存在有界最优解，所以使( 2 _ 2 3 ) 式等于零的解x 和w 分别是 它们的对应问题的最优解。可以利用这个性质来证明解的最优性。 可以把求解运输问题的步骤归纳如下【4 8 】： 1 ) 利用西北角规则或等价的方法，例如最小元素法，求出初可行解，并列出 解表( x 。) 。4 z 。是目标函数的现行值。 2 ) 求出组合( u ，v ，) 与间接费用表( c 。) ，即通过令“= 0 求出“，和v ，对 在基中的x ，求出c v = “。+ v ，以及对所有的( i ，j ) 计算c 。，= “，+ v ，。 3 ) 若所有的c 。一c 。，0 ，则现行解是最优的。若某个c 。一c 。 o ，对应于 c m c w = m a x ( c 一c ”) o 的非基变量x w 进基。( 因为任何与c 。一c 。 o 对应的 x 。都可选进基，可以利用下文要讲的修正的选择规则。) 4 ) 把代理参数口= x 。放到现行解表( x ) 的( p ，q ) 位置，为了保持行与 列的平衡，对x 口加上或减去目的x 。的位置处确定这些x 。的极小值，这个值等于 0 = x 。，即求满足这组约束条件x 。一0 0 的目的最大值。若p 使不止个约束条 件取等号，则我们得到的是退化解，在这个退化解中有不止一个现行基变量变成 零，为了构造对应的( c 。) 表，我们只去掉一个( 任意一个) 零变量，并保存其 余的以形成新的基本解。目标函数的新值是z = 气一工。( c 。- - c 。) 。 5 ) 然后对新解做第2 到第4 步。若在最优解中对某个非基变量有c 。一c 。= 0 ， 则利用第4 步，让相应的变量进解，并把它当成x 。，就可以求出多个最优解。 2 1 3 特殊情况的处理 在运输问题中经常有些特殊情况，使得问题不完全与我们上述讨论的相同， 因此，再介绍一下如何处理运输问题的特殊情况： 华中科技大学硕士学位论文 2 31 最大目标值问题 当运输问题的c 。考虑为收益时，表现为最大化目标值问题。等于这类问题 只须令m = 朋缸j f 。1 f - 1 , 2 ，m ；j = 1 , 2 ，” ，c g = m q ，i = 1 , 2 ，m j2 1 , 2 一棚。 即转化成关于的最小化目标值问题，从而最小化目标值问题的最优解即为最大化 目标值的最优解，并利用原来的c ，立即可得最大化问题的最优解。 2 3 2 总供应曼不等于总需求量的问题 无非存在两种情况：总供应量大于总需求量，反之，总供应量小于总需求量。 对于前者只须虚拟一个收点，其需求量为总供应量与总需求量的差值，单位运输 成本全部虚拟为零。对于后者只须虚拟一个发点，其供应量为总需求量与总供应 量的差值，虚拟其单位运输成本全为零。如此，全部转化为总供需平衡的运输问 题。 2 3 3 具有不可能运输路线的问题 在运输问题中，往往可能发生由某发点a 。到某收点b ，的运输路线不存在：或 者4 ，的产品不具有b 规格的产品等，称之为具有不可能运输路线。对此，我们只 须在运输表上将不可能运输路线的运输成本都定为比任何可能运输成本c 。都大的 同一数m 时即可。在最大化目标的问题中相应的将不可能的路线的c 。定成一个比 任何可能的c ，都小的数一m 即可。 2 4 转运问题 运输模型的一些固有限制，在现实情况中或许不存在。如果不存在的话，我 们常常能得到一个有显著改进的解( 即总成本的大量减少) 。 为了说明这点，研究图中的问题，在此图中，所有的货物流动都是从发点到 收点。然而，也可以建立这样一个运输路线，它包括发点到发点，收点到收点， 甚至包括收点到发点的运送分配。考虑图，该图增加了一些别的可能途径。如果， 现在有可能将货物从发点a 经过发点b 运送到收点( 即转运) 。 9 华中科技大学硕士学位论文 图2 4 1 运输图( 有向)图2 4 2 转运图 如上所述，网络中包括附加分枝( 即转运路线) 可能意味着能够使成本大为 减少，但是问题的规模却因此而大为扩大。 通过扩充运输问题中使用的符号，转运问题可以转换成一个相当方便的矩阵 模型5 扪。表2 4 1 给出这种模型的一般形式 表2 4 1 一般转运矩阵 ： 发点收点供应量 l i m 1 j n 1a l + u 发 ( 1 ) ( 2 ) - 1 发点到收点子矩阵 发点到收点子矩阵 乳+ u 点 - m a i n + u 1u 收 ( 3 )( 4 ) j 收点到发点子矩阵收点到收点子矩阵 u 点 - nu 需求量 u u u n + u b j + u b n + u 可以看到，转运矩阵由四个子矩阵组成。( 1 ) 发点到发点，( 2 ) 发点到收点， ( 3 ) 收点到收点，( 4 ) 收点到收点。包含在每个子矩阵内的元素表示运输成本和 分配决策。注意子矩阵2 就是等效的运输矩阵( 即仅考虑发点到收点的货物流动) ， 1 0 华中科技大学硕士学位论文 现在它被包围在整个问题内。除了存在更多的路线外，每个方格的运输成本如通 常一样求得每个发点或收点的供应量，不是十分明显的，注意所有边缘供应量和 需求量，都包括一个常数u 。该常数代表任何结点( 发点或收点) 可以流通的货 物数量的上界( 即可能转运的最大量) 。为确定u ，我们首先假设一个平衡问题， 其次，通过任何结点可运量的最大单位数很明显不能超过a l = b ，即总供应 ，l j = l 量或总需求量。因为，如果转运过多货物，其中至少有一个运送量不止一次地通 过同一结点。这样， u = 口f = b ， ( 2 4 1 ) 1 1 ti 华中科技大学硕士学位论文 3 1 经典运输问题悖论 3 实际运输问题 在经典运输问题中，各发点的发量a ，( i = 1 , 2 ，m ) 与各收点的收量 b ，( j = 1 , 2 ，n ) ，都是确定的常数。经典运输问题中往往存在着一种怪现象：在 它的最优解中，若增加运量，或调整某些供需关系后虽然运量不变，反而会使目 标函数变小( 即总运费或总吨公里再减少。) 这种现象在数学上被称为悖论。 那么，为什么会产生这种“悖论”现象? 如何克服这种现象? 如何制定出使 目标函数( 总运费或总吨公里) 真正达到最小的最优运输方案( 最优解) 呢? 这 正是我们所要讨论的实际运输问题所包含的三个特点的第一个：发量和收量为变 量。我们可以称这样的运输问题为变量约束运输问题。 用这种模型求出的最优解，有两个最大的优点： ( 1 ) 更符合实际情况，因此，更有应用价值和实际意义； ( 2 ) 目标函数值更小。 经典运输问题存在的“悖论”表示为：通过发量和收量的适当调整，使得运 量不变而运费减少；增加运量而运费不变；增加运量而运费反而减少。我们可以 通过对数学模型的对比分析进行更为严格的定义。注意，为了方便起见，在下面 的运输问题中均假设产销平衡，即总发量等于总收量。经典运输问题模型为l p l ， 见第二章。 变量约束运输问题模型为： l p 2 ：m i n z = c f i - i ) - i s - b = 口，口is 口口? i = 1 , 2 ，m ( 3 1 + 1 ) 华中科技大学硕士学位论文 x 。= b ，6 j b ，6 j = l ，2 ，n ( 3 1 2 ) t = l x ，0 ，i = t , 2 ，m ；j = 1 , 2 ，r 定义若l p l 和l p 2 的最优值或总运量有一不相等，则称l p l 中存在运输问 题“悖论”现象。 由定义可知，运输问题的“悖论”现象可分为两种情形： 1 ) l p l 和l p 2 的最优值不相等，此时必有l p 2 的最小运费小于l p l 的最小 运费，且最优分配方案不相同，l p 2 的总运量大于l p l 的总运量。 2 ) l p l 和l p 2 的最优值相等但总运量不相等，l p l 的总运量小于l p 2 的总运 量。 可见，运输问题的“悖论”现象是在两种不同的模型下产生的，由于模型l p 2 放宽了l p l 约束条件严格相等的限制，其最优值变小是合理的。故运输问题“悖 论”并不是悖论，而是正常现象。 由于l p 2 的可行域包含了l p l 可行域，因而l p 2 的最优值不大于l p l 的最优 值。所以，只有通过求变量约束的运输模型l p 2 的解才能真正消除运输问题的“悖 论”现象。 3 2 变量约束运输问题模型 我们从这些经典运输问题的“悖论”现象中，能得到什么启发呢? 它显然启 发我们：假若各发点的发量和各收点的收量均为变量( 或各有一部分发、收点为 变量，有一个确定的变化范围) ，则我们可以利用发量与收量的变化范围，进行调 整，消除悖论，求得这样的最优解：使总运量达最大，而总运费( 或总吨公里) 又达最小。综合二者，达运费率最小。 因此，我们可以给出这种变量约束运输问题的描述： 假设某物资有m 个发点a i ( i = l ，2 ，m ) ，其发量为a i ( i _ 1 2 m ) ，而a i 为变 量，变化范围是k i ，口? j ，同时有n 个收点b j ( j = l ，2 ，n ) ，收量为b j ( j = 1 ，2 ，n ) ， 而b 也是变量，变化范围是【6 j ，譬j ，发点a i 到s j 的运价( 或距离) 为e i j 0 = 1 ， m ，j = 1 ，n ) ，运输量为x 。x i j ( i - l ，m ，j = 1 ，n ) 。则简化模型为： 华中科技大学硕士学位论文 删：撕p = 号 毛= q ，口i q d ? ( f _ 1 2 ，m ) j = l x ，= b ，6 j b ，b j ( = l 2 ，n ) x 。0 ，( f _ 1 , 2 ，m ；j = 1 , 2 一 ) ( 3 2 1 ) 其中，目标函数p 为为运费率( 每吨运费或每吨的吨公路) ，u 为总运量，z 为总运费( 或总吨公里) ，即 u = vz = 铲。 j ，l j f f i l t = l ，2 i 规划l p l 中的口。，b ，为约束变量。( c 。，) 。为元素表，表示运价( 或距离) 。 3 3 运输量有上界的运输问题模型 建立带上界约束运输问题数学模型为： n l p 4 m i nz = 铲， t = l j = l s t = q ，i = l 2 ，肌 j i _ = b ，= l 2 ，胛 0 x p 如，i = 1 , 2 ，m ；，= l 2 ，n ( 3 3 1 ) 标准运输问题一定有最优解，但当变量有上界时，可能会发生无可行解的情 况。关于此问题的可行解，显然存在如下结论： 定理1 带上界约束约束问题存在可行解的充分必要条件是： d u 口f ，d - - b ，( f _ 1 , 2 ，川；j = l 2 ，帕 j - i i f f i ! 本文仅就有最优解的情况进行讨论。 若上述l p 3 模型中又由于实际运输能力的限制，计划期内从a 。到b ，的最大允 1 4 华中科技大学硕士学位论文 许运输量为d 即再加上一个约束条件d ，则简化模型为 峭：鼢p = 号 _ = 口，口i q 口? ( f - l 2 ，聊) ， ，= i _ = 6 ，町屯s b ；( - ，= l 2 ) ， 0 x d ，( f = 1 , 2 ，m ；j = 1 , 2 ，n ) 很明显，上式中e d ，口i ，d 。6 j o = 1 , 2 ，m ；j = 1 , 2 ，月) ，否则该模 j ，l i = 1 型无解。 3 4 特殊情况的处理 3 4 1 有附加条件的不平衡规划问题 1 ) 必发或必收的不平衡问题 ( 1 ) 在发量有余，即口f b ，的规划问题中，某个发点的发量，因故又 t = l j - l 必须发完。这种规划处理的方法是，在虚收栏中，对应该发点的元素： 对于最小解问题取m ( m 为充分大的正数) ； 对于最大解问题，取( 一m ) 。 在求初始解、检验数以及调整基可行解时，m 或( 4 d ) 所在的格，均不予考 虑。 而虚收栏中的其他元素仍为零。 ( 2 ) 在发量有余，即q 0 。设第j 个大坝填筑点每个计划期填 筑能力的最大量为6 ；0 = 1 2 n ) ；为了保证大坝填筑施工的计划，每个计划期第i 个填筑工程的填筑量至少为6 i ( j = 1 2 n ) ，其中6 j 6 j 0 。 然后将1 个中转储备点视作1 个开采工程和1 个大坝填筑点。 设第i 个开采工程的开采成本为p ，( i = 1 , 2 ，m ) ，第i 个中转储备点的储存 成本为e ，( f - m + l ，m + 2 ，珊+ ，) 。设在每个计划期中，从第i ( i = 1 , 2 ，m + ，) 个 开采工程直接运送到第j ( j = 1 , 2 ，竹+ f ) 个填筑点的运输量( 运输决策变量) 为x 。， 运价为c 。由此，我们可化简得到从第i ( i = 1 , 2 ，m + ，) 个开采工程直接运送到第 j ( j = 1 , 2 ，n + f ) 个填筑点的运价及其他成本为c c o = c 。+ p 。，( f = 1 , 2 ，m + l ；j = 1 , 2 ， + ，) 并设在每个计划期中，第p 个储料场，最大库存容量为圪，本期期初储量为 r ：，预计本期期末存储量为r ，其中p = l 2 1 。则该运输问题的目标函数( 总运 费率最小化) 如下： 华中科技大学硕士学位论文 c ， m i n p = 号尝：r ( f _ 1 , 2 ，m + l ；j = 1 , 2 ，n + f ) ( 3 51 ) f = ij t l 其中，决策变量为x 。受到下述式( 3 5 2 ) 至( 3 5 7 ) 的条件所限制。其约 柬表达式及意义叙述如下： = a ，口i a ，口? ( i = 1 , 2 ，m ) ( 3 5 2 ) 在每个计划期，对于任一开采工程，其开采量( 发量) 应不少于工程施 工计划的最少开采量，并且受到该点本身的开采能力的限制。 m + f = b j ，町b ，b j ( ，= 1 厶，胆) ( 3 53 ) 在每个计划期，对于任一大坝填筑点，其填筑量( 收量) 应不少于工程 施工计划的最少填筑量，并且受到该点本身的填筑能力的限制。 0 x 。d 。( i = 1 , 2 ，m + l ；j = 1 , 2 ，行+ ，) ( 3 5 4 ) 在每个计划期，对于任一道路，其运输量应受到该道路本身的运输能力 的限制。 i 一，l = j m ( f = m 十1 ，m + 2 ，m + l ；j = n + 1 ，n + 2 ，疗+ ，) ( 3 5 5 ) 对于同一中转储备点，在发点和收点中分别所处的位置( 相应下标) 。 u = ，l + 1 ，疗+ 2 ，n + f ) ( 3 5 6 ) 如果将中转储备点当作收点考虑，则其期末储量由本期期初储量与进料 量、消耗量( 即，作为发点而言的发量) 代数求和得到( 预计量) 。它应不多于该 中转储备点的最大库存容量。 n + lm + l 砰+ x f 一b i 。卜+ = r ，o ( f = m + l ，m + 2 ，r e + 1 ) ( 3 5 7 ) l m l l - t 如果将中转储备点当作发点考虑，则其期末剩余生产能力r 由本期期初 “剩余生产能力”( 即钟，作为收点而言的库存量) 与“新增生产能力”( 即作为 1 9 o 一 足 i l 盯+ _ 吖p x m 州 一 一p x d + 0 ， r 一一 华中科技大学硕士学位论文 收点而言的进料量) 、本期发量代数求和得到( 预计量) 。它应不多于该中转储备 点的“最大生产能力”( 即矿，作为收点而言的最大库存量) 。 注：( 3 5 6 ) ( 3 5 7 ) 式中的r ? 、r ，的实际意义为中转储备点的本期期初储量 与本期期末储量。由时间的连续性可知，本期期末储量即为下期的期初储量。 在其他具有类似特点的大型物流调运系统及实际运输问题中，也可以同样建 立如上所示的运输模型。本系统中的土石方可考虑为发量在一定范围的限制内变 动的发点，大坝填筑系统可考虑为收量在一定范围的限制内变动的收点，而中转 储备点即带有库存容量的转运点，运输量受到各条道路的限制：将基于时序的连续 运输过程离散化为多个计划期。这样，即可建立出与式( 3 5 1 ) 到( 3 5 7 ) 类似 的运输问题模型。具体求解方法我们在第四章与第五章中进行讨论。 2 0 华中科技大学硕士学位论文 4 求解变量约束且运输量有上界的运输问题 4 1 推导最优解法 在某些实际问题中，诸变量不仅有下界，而且有上界，因此要求我们考虑如 下形式的线性规划： a x = a o x 耋d x o c 1 x = m i nz 其中d = ( d - ，d z ，d 。) 为上界变量，d ， 0 。如果某些变量无上界，则认为d ， 充分大即可。可以引进松弛向量y = ( ) ，。，y ：，y 。) ，上面的sd 变为 z + j ，= d ( y 2o ) ，然后用单纯形法求解。但是，这样处理将使变量数增加为2 n ， 方程数增加为m + n ：对于较大的n 来说，计算量的增加是可想而知的。因此我们 应该充分利用x d 的特殊性，以不引进松弛变量为好。 著令彳= l j ( 帅 c = ( c l l c l n c 2 l c 2 c m l c 肌) 7 r = ( x l j x 抽屯】x 2 k j ) r d = ( d r i d 1 d z i d 2 。丸i “) 7 b = ( 口l 口2 口，6 l b 2 6 。) 7 2 i 华中科技大学硕士学位论文 则变量有上界的运输问题即可化为一般的变量有上界的线性规划问题 m j 门c 7 x n 以石= 扫 ( 4 1 1 ) 0 x s d 为叙述方便，我们把指标集合i 按下面的方法分为s 和r 。i s 时，一是基 变量，r 时，z 是非基变量，且将r 再分成r i 和心，j r 。u r 2 = r ，当i r l 时， x 。= 0 ，当i r 2 时，x ，= 盔。 一般的变量有上界的线性规划问题( 4 4 1 ) 的判优法则如下： 设给定了( 4 4 1 ) 的一个基可行解x o ，它对应的典式为 及 一= q 一岛z ，一岛x ，i s j e 月1e 月2 如果z 。的两组检验数满足t 0 ，r 。，五j 0 ，r ：，则x 。是最优解。 显然此判断法则适用于变量有上界的