（理论物理专业论文）线性离散规划及其应用.pdfVIP

博士学位论文 d o c t o r a ld i s s e r t a l l o n 摘要 线性离散规划是一个离散函数在组线性约束条件下的最优化问题现代工农业生 产中诸如经济与环境、工业与污染、有限资源的保护与利用等等问题都与线性离散规划 有关本文试图建立线性离散规划的理论体系，以期适应社会经济集约型可持续发展的 需要 全文分为四个部分 第一章给出了线性离散规划的数学模型及其标准型、有关定义和解的基本性质给 出了两种不同的求解方法即拟目标规划法和直接法基于拟目标规划法给出j 线性离 骰规划的对偶单纯形算法和灵敏度分析作为线性离散规划的特殊情况，还讨论了线性 离散运输问题和线性离散指派问题 第二章是线性离散规划在一些特殊的规划问题中的应用这些特殊的问题都是与资 源、环境有关的问题b 线性规划是研究在保护环境控制污染或充分利用有限资源的前 提下优化经济效益的规划问题b 运输问题是研究在保证货物尽快运抵目的地的前提下 使总运费最少的运输问题b 指派问题是研究在保证尽快完成所有任务的前提下使完成 任务总效率最高的指派问题c 运输问题是指对总运输量有数摄限制的运输问题c 指 澡问题是指实际要分配的任务数不超过总人数也不超过总任务数妁指派问题。上述问题 都与线性离散规划有关，并可借助线性离散规划求解 第三章给出了线性离散规划在矩阵对策中的一个应用面对一个经济对策问题绝 大多数决策人在他们的计划，至少在他们的心中有一个得失的底线，既所谓的成本而 根据传统的对策理论对于在现实生活中偶尔碰到的对策问题，局中人即使是严格按照 最优混合策略来选择自己的行动方案。也不能保证实际赢得就大于成本，甚至不能保证 实际赢得就一定大予某个很小的支付值我们把在尽量避免实际赢得可能低于成本的前 提条件下争取最大利益的对策问题称为b 对策b 矩阵对策可以转化为线性离散规划求 解这和传统矩阵对策可以转化为线性规划求解完全一致 第四章是两个特殊的线性离散规划问题 博士学位论文 d o c t o r a ld i s s e r t a t i o n a b s t r a c t l i n e a rd i s c r e t ep r o g r a m m i n gi sac o l l e c t i o no fp r o c e d u r e sf o rm a x i m i z i n go rm i n i m i z i n g d i s c r e t ef u n c t i o n s s u b j e c t t o g i v e n l i n e a r c o n s t r a i n t s m a n y o ft h e p r o b l e m sn o r m a l l y e n c o u n t e r e di nt h em o d e mi n d u s t r ya n da g r i c u l t u r e ，s u c ha s e c o n o m ya n de n v i r o n m e n t ， i n d u s t r ya n dp o l l u t i o n ，p r o t e c t i n ga n du t i l i z i n gf i n i t er e s o u r c e s ，e t c ，a r ec o n c e r n e dw i t ht h e l i n e a rd i s c r e t e p r o g r a m m i n g t h i s t h e s i sw i l le s t a b l i s ht h e t h e o r y o fl i n e a rd i s c r e t e p r o g r a m m i n g s oa st os a t i s f yt h en e e d so f s u s t a i n e de c o n o m i c g r o w t h t h i st h e s i si so r g a n i z e di nf o u rp a r t s i nc h a p t e r1 ，t h em a t h e m a t i c a lm o d e lo ft h el i n e a rd i s c r e t ep j 。o g r a m m i n g ，s o m ed e f i n i t i o n s a n dt h e o r e m sa r eg i v e n ；q u a s i g o a ：tp r o g r a m m i n ga n dd i r e c ta l g o r i t h m sa r ep r e s e n t e d w ea l s o p r e s e n tt h ed u a ls i m p l e xa l g o r i t h mf o rs o l v i n gl i n e a rd i s c r e t ep r o g r a m m i n g a n d p o s to p t i m a l i t y a n a l y s i s b a s e d0 nt h eq u a s i g o a l p r o g r a m m i n ga l g o r i t h m t h et r a n s p o r t a t i o np r o b l e m sf o r r u s h i n gt o d e a lw i t ha l l e m e r g e n c ya n dt h ea s s i g n m e n tp r o b l e m sf o rr u s h i n gt or e p a i ra r e s p e c i a le x a m p l e so fl i n e a r d i s c r e t ep r o g r a m m i n g ；h e n c e ，w ed e v e l o pm u c hm o r ee f f i c i e n t a l g o r i t h m s t oh a n d l et h e p r o b l e m s i nc h a p t e r2 ，w ep r e s e n tt h ea p p l i c a t i o n so fl i n e a rd i s c r e t ep r o g r a m m i n gt os o m es p e c i a l m a t h e m a t i c a lp r o g r a m m i n g p r o b l e m s t h e s es p e c i a lp r o b l e m sd e a lw i t ht h ee n v i r o n m e n ta n d r e s o u r c e s m a i n l y l i n e a rb p r o g r a m m i n g d e a l sw i t ht h e p r o g r a m m i n gp r o b l e m s f o r m a x i m i z i n gb e n e f i to nt h ep r e m i s eo fp r o t e c t i n gt h ee n v i r o n m e n ta g a i n s tp o l l u t i o no rm a k i n g f u l lu s eo f t h ef i n i t er e s o u r c e s b - t t a n s p o r t a t i o np r o b l e mi st or a i n i m i z et o t a lt r a n s p o r t a t i o nc o s t s u b j e c tt ot h a ta l lo f t h eg o o d ss h o u l db et r a n s p o r t e df r o me a c hs o u r c et oe a c hd e s t i n a t i o na s q u i c k l ya sp o s s i b l e b - a s s i g n m e n tp r o b l e m i st oo p t i m i z et o t a le f f i c i e n c ys u b j e c tt ot h a ta l lo f t h ej o b ss h o u l db e c o m p l e t e da sq u i c k l y a s p o s s i b l e ac t r a n s p o r t a t i o np r o b l e m i sa t r a n s p o r t a t i o np r o b l e mi n w h i c ht h ea m o u n tt r a n s p o g e df r o r aa l lt h es o u r c e st oa l lt h e d e s t i n a t i o n si ss u b j e c tt oag i v e nn u m b e r ac - a s s i g n m e n tp r o b l e mi sa na s s i g n m e n tp r o b l e mi n w h i c ht h ej o b sw i l lb ea s s i g n e di sl e s st h a no re q u a lt ot h et o t a lp e r s o n sa n dt o t a lj o b s l i n e a r d i s c r e t ep r o g r a m m i n gm a yb ea p p l i e dt os o l v et h e s ep r o b l e m s 博士学位论文 d o c t o i ld l s s e r t a 下l o n c h a p t e r3c o n c e n t r a t e so na na p l ) l i c a t i o no f l i n e a rd i s c r e t ep r o g r a m m i n g t ot h em a t r i xg a m e s f a c i n gag a m ep r o b l e mt h a t d e a l sw i t ht h eg a i na n dl o s s 。a no v e r w h e l m i n gm a j o r i t yo f d e c i s i o n - m a k e r sh a v ea n e x p e c t a t i o n o fm i n i m u mw i n n i n g s h i s g a m ec o s t a p p l y i n g t r a d i t i o n a lg a m et h e o r yt oag a m ep r o b l e mo c c a s i o n a l l ye n c o u n t e r e di nt h er e a lw o r l d ，t h e p l a y e rw o u l d n o ta s s u r et h a th i sr e a lw i n n i n g si si ne x c e s so f t h eg a m ec o s te v e ni f h ec h o o s e s h i so p t i m a ls t r a t e g ys t r i c t l y ，a l s ow o u l dn o ta s s u r et h a th i sr e a lw i n n i n g si sl a r g e rt h a nav e r y s m a l lp a y o f f ag a m e p r o b l e m ，i nw h i c h e a c hp l a y e rn i e sf o rm a x i m a lp r o f i t so nt h ep r e m i s eo f a v o i d i n gh i sr e a lw i n n i n g sm a y b el e s st h a nh i sg a m ec o s tg f a ra sp o s s i b l e ，i ss a i dt ob eab g a m ep r o b l e m a m a t r i x b - g a m ep r o b l e mm a yb e t r a n s f o r m e di n t oal i n e a rd i s c r e t e p r o g r a m m i n gp r o b l e m i t i ss i m i l a rt ot h a tat r a d i t i o n a lm a r i xg a m ep r o b l e mm a yb e t r a n s f o r m e di n t oal i n e a rp r o g r a m m i n gp r o b t e m c h a p t e r 4i st w o p a r t i c u l a rp r o b l e m s o f l i n e a rd i s c r e t ep r o g r a m m i n g - 博士学位论文 d o c t o r a ld i s s e r t t i o n 致谢 从考学到三年求学生涯我的母校。我的老师，我的同学给了我太多的关怀、鼓励 和帮助，让我永志不忘我深深地感到这一本薄薄的论文凝聚了许多人的心血特借这 方寸之地，向他们表示万分的感激和真诚的谢意 首先要感谢刘连寿教授及粒子物理研究所的全体老师他们在华中师范大学粒子所 营造了良好的学术环境。为我们提供了和谐、宽松、优越的学习条件他们所取得的学 术成就、他们孜孜不倦献身科学和教育事业的精神，是我们永远学习的榜样他们的善 良与宽厚使我们时时感到温暖 感谢邓引斌教授和数学系的老师们对我学业的关心和指导数学系良好的学术氛围 使我受益匪浅频繁的学术活动让我有更多的机会见识国内外学者、接收前沿数学思想 的熏陶使我开阔了视野，增长了知识，为顺利完成毕业论文打下了良好的基础感谢 他们对我在学习和生活上的关照 感谢路钢教授长期以来对我的关怀和指导他言传身教，不仅教我知识，还教我如 何做人他不断地鼓励我、鞭策我，使我对自己不敢有半点松懈正是他的严格要求， 我才能在今天顺利完成这篇论文 感谢毛经中教授对我的关心、支持和指导，他为我完成学业付出了辛勤的劳动在 我毕业论文的撰写过程中，他更是尽心指导，在百忙之中安排时间审阅，提出了大量指 导性的修改意见毛经中教授治学严谨，对事业的高度责任感深深地感染我，使我终生 受益 感谢汪更生老师、刘伟安老师、胡智全老师、陈世荣老师对我的指导和帮助 感谢我的同学康东升、黄建华、李书钢、王丽娟、向建林等对我的帮助 感谢我的家人对我的理解和支持 最后把我真诚的谢意送给所有关爱我的人 博士学位论文 d o c t o r a ld i s s e r t a l l o n 引言 线性规划( l i n e a rp r o g r a m m i n g ) 讨论的是个线性目标函数在一组线性约束条件下 的最优化问题”早在2 0 世纪3 0 年代前苏联数学家k o n t e r o v i t c h 在解决工业 生产组织和计划问题时，就提出了类似于线性规划的模型，并给出了“解乘数法”的求 解方法但是直到1 9 4 7 年美国数学家g b ，d a n t z i g 提出了求解一般线性规划问题的方 法一单纯形法之后，这门学科：才_ 在理论上趋向成熟1 9 7 2 年美国学者k l e e 与m i n t y t 6 1 发现单纯形法的时间复杂性是指教阶的1 9 7 9 年前苏联青年数学家k h a c h i y a n ? 1 找到了求 解线性规划问题的多项式算法一椭球法( 也称k h a c h i y a n 方法) 对于数学规划或整个 运筹学来说，线性规划是形成最早、最成熟的个分支它也是数学规划以及运筹学其 它些分支的重要基础 线性规划的数学模型可以表示为： 晶 m i n f 2 乞o ，x ， j t i s t 嘞x j = b f ( f = 1 , 2 , - - - , 朋) ( 1 ) 产l 工。0 ( 歹= l ，2 ，竹) 。 其中x l ，x 2 ，h 称为决策变量一：d e c i s i o nv a r i a b l a s ) f ( x l ，屯，x ) = c j x j 称为日 产l 标函数( o b j e c t i v ef u n c t i o n ) 常数c 1 ，c 2 ，c 称为费用系数( c o s t c o e f f i c i e n t s ) x = b i ( f = 1 , 2 ，m ) 及一 - 0 ( = l ，2 ，n ) 称为约束条件( c o n s t r a i n t j l c o n d i t i o n s ) 约束条件中x 0 ( ，= 1 ，2 ，托) 也称为非负约束( 6 1 ，6 2 ，b m ) 7 称为 右端向量( r i g h t - h a n d - s i d ev e c t o r ) 线性规划的基本性质包括；任何一个线性规划问题的可行孵( f e a s i b l es o l u t i o n ) 集合 ( 如果不是空集的话) 是个凸集i 线性娥划闯题的基本可行解( b a s i cf e a s i b l es o l u t i o n ) 对应于可行域的极点；如果线性规划阎题有可行解，则必有基本可行解；如果线性规划 问题有最优解( o p t i m a ls o l u t i o n ) ，则存在一个萋本可行解是最优解等等 博士学位论文 d c ) c q o r ld i s s e r t a r l o n 还有另外一些优化问题，其目标函数和( 或) 约束条件不能用线性函数表达我们 把目标函数或约束条件中包含有非线性函数的规划问题称为非线性规划( n o n l i n e a r p r o g r a m m i n g ) ，在g b 。d a n t z i g 提出线性规划单纯形方法的：第二年，也就是1 9 4 8 年，a ， t u c k e r t 等人就开始了对非线性规划问题的研究这一理论的初步形成约在1 9 5 1 年，其 标志是与f r i t z j o h n 条件( 1 9 4 8 ) 相关的k u h n t u c k e r 条件的提出8 非线性规划问题可以表示为： m i n ，( x ) s t g 。( x ) = o( j = 1 , 2 ，m )( 2 ) h ，( x ) 0 ( _ ，= l ，2 ，竹) 其中x e ”为决策变量，f ( x ) 为目标函数，( x ) 和h a x ) 为约束函数( c o n s t r a i n t f u n c t i o n ) ，这些函数中至少有个是非线性函数 对于非线性规划问题的研究分为两个方面：一是研究最优解的性质，二是设计有效 的算法来获得问题的最优解根据可行域是否等于e “，非线性规划问题又分为无约束 最优化问题和约束最优化问题求解无约束问题的一般方法有一维搜索法、解析法、直 接法等：求解约束最优化问题的一般方法有可行方向法、罚函数法、逐步二次规划法等 il l 3 1 【8 】【9 】一般说来，解非线性规划问题比解线性规划问题要复杂得多，没有一个象线 性规划中单纯形法那样的通用算法，通常是根据不同问题的不同特点给出不同的解法 所以1 f 线性规划研究的进展在很大程度上依赖于分析工具的进展对于一般非线性规划 模型的研究常常是困难的。对于一些特殊类型的模型进行研究形成了一些特殊的分支问 题，并取得了更为深刻的研究成果。这些分支问题主要有二次规划、几何规划、分式规 划以及更一般的概念凸规划等 整数规划( i n t e g e rp r o g r a m m i n g ) 是一类要求决策变量取整数值的数学规划若在 线性规划中，要求变量取整数值，则称为线性整数规划( 1 i n e a ri n t e g e rp r o g r a m m i n g ) ； 若要求变量只取0 或l ，则称为0 - - 1 规划( 0 - - 1p r o g r a m m i n g ) ；若要求部分变量取整 数则称为混合接数规划( m i x e di n t e g e rp r o g r a m m i n g ) 1 9 5 4 年，g b d a n l z i g ，d r f u l k e r s o n 和s m j o h n s o n 在研究推销商问题( t r a v e l i n gs a i e s m a np r o b l e m ) 时首先提 出了破子圈方法和将问题分解成几个子问题之和的思想，这就是整数规划中两大类基本 方法一割平面( c u t l i n gp l a n ) 法和分支定界( b r a n c ha n db o u n d ) 法的萌芽“5 1 9 5 8 年，r e g o m o r y 创立了一般线性整数规划的割平面算法；1 9 6 0 年，a h l a n d 和a g d o i g 首先对推销商问题提出了个分解算法，紧接着e b a l a s 等人将其发展成求解一般 线性整数规划翔题的分支定界法，从丙彤成了独立的整数规划分支：z 】”1 从计算复杂性 ( c o m p t e x i t y ) 的角度来看几乎所有的整数规划问题都属于困难问题“，很少有精确 的多项式算法( p o l y a o m i a la l g o d t h m ) 2 博士学住论文 d o c t o r a ld i s s s r t a 1 1 i o n 事实上，传统的线性规划、非线性规划和整数规划都可以用如下数学模型描述： m i n ，o ) s t g f ( x ) = 0 ( f i )( 3 ) ，( x ) 0 ( ，) 当目标函数厂( x ) 和约束函数g 0 ) ( i = 1 , 2 ，删) 为线性函数，且h j ( x ) = x ， ( j = 1 , 2 ， ) 时，模型( 3 ) 表示线性规划；当目标函数f ( z ) 、约束条件o ) = 0 ( f e i ) 和h ，( x ) 0 ( ，j ) 中至少有一个是非线性函数时模型( 3 ) 表示非线性规划 一般地说，在传统线性规划和非线性规划中，对决策变量没：有取整数值的规定口】如果 对决策变量增加取整数值的规定。那就是所谓的整数规划对决策变量增加取整数值的 规定相当于在模型( 3 ) 的约束条件中有一些离散型约束：并取整数值虽然从形式上 看，线性整数规划只是在线性规划中多了一些决策变量取整数值的离散型约束，但是线 性整数规划比线性规划要复杂得多，至今还没有一种有效的多项式算法如果模型( 3 ) 中 目标函数厂( x ) 是一个离散函数，那又是一个什么样子的规划问题呢? 这正是本文所要研 究的问题我们把这一类问题称为离散目标规划，或简称离散规划( d i s c r e t e p r o g r a m m i n g ) 本文主要研究线性离散规划( 1 i n e a r d i s c r e t ep r o g r a m m i n g ) ，即研究一个离散 目标函数在一组线性约束条件下的最优化问题 随着社会经济的不断发展，只追求经济效益的粗放型发展模式已经过时，人们越来 越重视保护环境、控制污染和有限资源的合理开发事实上，现代工农业生产中诸如经 济与环境、工业与污染、有限资源的保护与利用等等问题都与线性离散规划有关本文 试图建立线性离散规划的理论体系，以期适应社会经济集约型可持续发展的需要 博士学位论文 d o c t o r a ld i s s e r t a t i o n 第章线性离散规划 传统数学规划，般以追求最佳经济效益为目标，但是在下面的一些问题中经济 效益并不是最主要的 1 某工厂用两种原材料生严四种产品其中第一种原材料含有某种毒素由于工 艺、设备等技术原因，该原材料用于生产备种产品时，毒素的净化率不尽相同，没有被 净化的有毒物质仍然残留在产品之中要求四种产品的总产量不低于某个计划数，应如 何安排生产使毒性最大的产品中有毒物质含量最低? 2 在发生自然灾害的情况下运输救灾物质、战争时期运输军需物质，首要问题是 如何尽快地将紧急物资( 包括人员等) 如数运抵目的地 3 在一供电系统中，有数处发生故障急需停电检修，且供电系统只有在所有故障 排除以后才能恢复供电，应如何分派检修任务使供电系统停电检修时间最短? 类似于上述与资源环境、抢险抢修有关的问题还可以列举许多事实上，这一系列 的问题都与一个离散型目标函数在一组线性约束条件下的最优化问题有关我们把一个 离散目标函数在一组线性约束条件下的最优化问题称为线性离散规划离散函数的形式 很多，也很复杂在线性规划的约束条件中加上一些决策变量取整数值的离散型约束就 使问题变得复杂起来，可以想象得到，线性离散规划是一个复杂的问题我们在这里只 讨论“m i n m a x ”( 或“m a x m i n ”) 型离散目标函数在一组线性约束条件下的最优化问 题这一类线性离散规划的大部分性质和线性规划的性质非常相似，如，可行解集合是 一个凸集；如果可行域非空，则其最优解集合是一个凸集；如果可行域非空且有界，则 存在一个基本可行解是最优解等等，也有类似于单纯形法的求解方法线性离散规划在 国防、科技、环境工程、抢险救灾、社会经济等领域都有7 。泛应用 4 博士学位论文 d o c t o d i s s e r t a l i o n 1 1 线性离散规划问题 1 1 1 线性离散规划问题及其数学模型 在一些与资源、环境有关的问题中，我们经常碰到一个离散型线性函数在一组线性 约束条件卜的优化问题下面就是一个例子 铡1 1 ，1 某二i _ ：厂用原材料a 、b 生产i 、i i 、i 、v 五种产品，原材料的储备 量以及生产单位产品的需要量等如表l1 1 所示 产品ii iu l i vv ( 原材料) 量 原材料 a233241 2 0 b345421 8 0 其中原材料a 含有某种毒素，由于工艺、设备等技术原因，用于生产产品i 、i 、 、v 时毒素的净化率分别为8 、8 9 、8 8 、8 5 、9 1 没有被净化的有毒物质 仍残留在产品之中如果要求五种产品的总产量不少于4 8 ，应如何安排生产使所有产品 中毒性最大的产品有毒物质含量擐低? 设计划期内产品i 、i 【、i i i 、v 的产量分别为墨、x 2 、屯、x 4 、z s ，则上述 问题可用如下数学模型描述： r a i n f = m a x e ，f x ，0 ，e l = 0 3 8 ，e 2 = o 3 3 ，e 3 = o 3 6 ，e 4 = o 3 0 ，岛= o 3 6 s t 2 x l + 3 x 2 + 3 而+ 2 x 4 + 4 1 2 0 3 x l + 4 x 2 + 5 x 3 + 4 x 4 + 2 x ，s 1 8 0 ( 1 i 1 ) x i + x 2 + x 3 + x 4 + x 5 4 8 工，0 ( ，= l ，2 ，3 ，4 ，5 ) 其中e l = 2 ( i - 8 1 ) = o 。3 8 ，e 2 = 3 ( i - 8 9 9 6 ) - - - - 0 。3 3 等等 模型( 1 - 1 1 ) 表示求一组满足约束条件的变量而，x 2 ，而，x 4 ，屯。使函数 f ( x ) = m a x e ，1x ，0 ，岛= o 3 8 ，e 2 = o 3 3 ，e 3 = o 3 6 ，p 4 = o 3 0 ，岛- - 0 3 6 博士学位论文 d o c t o r a ld i s s e r t a l i o n 到达最小 某些原材料在生产加工的过程中会排放有毒物质，那么从环境保护的角度出发，也 有类似的问题由于科学技术、工艺设备等原因，我国大部分矿产资源的有效开采率和 有效利用率还不是很高，而我国又是一个矿产资源比较贫乏的国家，所以在矿产资源的 开发与利用，尤其是在稀有矿产资源、不可再生资源的开发与利用方面，也有类似的问 题在工农业生产中还有许多这一类型的问题，如抢险( 如何尽快地将抢险物资如数运 抵各灾区) 、抢修( 如何尽快地排除系统中所有故障) 等等一般地，上述问题都可归结 为如r 数学模型： m i n f = m a x e ix ，o ，= 1 , 2 ，。，n ) ( 或m a x f = m i n e ，ix ，o ，j = 1 , 2 ，竹 ) s t 唧_ = 岛 ( 或抚；或匆) ( ，= 1 ，2 , - - - , 所) ( 】2 ) j - 1 x 0 ( j = 1 , 2 ，n ) 其中，f = m a x e ，| x ，o ，j = 1 , 2 ，一，h 或f = m i n e ix j o ，j = 1 , 2 ，”) 称为 目标函数( o b j e c t i v ef u n c t i o n ) 。其它定义，如决策变量、约束条件、右端向量等与传统线 性规划的相关定义相同 我们把目标函数是“m i n m a x ”( 或“m a x m i n ”) 型离散函数，约束仍然是线性函数 的最优化问题( 1 1 2 ) 称为线性离散规划，并约定以后提到的线性离散规划问题都是指 这一类型的问题线性离散规划不同于线性规划、整数规划及其它传统形式的规划问题 不能用传统的方法求解 1 1 2 线性离散规划问题的标准形式 线性离散规划问题的标准形式为： m i n f = m a x e j l x j o ，_ ，= 1 , 2 ，n ) 其中e 0 ，_ ，= 1 , 2 ，。，n ；b ；0 ，i 2 1 , 2 ，m - 实际碰到的各种目标是“r a i n m a x ”( 或“m a x r a i n ) 型线性离散规划问蹶的数学模 型都可以变换为标准型关于不等式约束和自由变量的标准化与传统线性规划问题处理 的方法完全一样。其它的可按如下方法进行 1 若存在8 i 一 。州t ts 博士学位论文 d c c t 0 & a ld i s s e k t a t i o n = = = = = = = ! ! = = = = = ! = ! = ! ! = = = = ! ! = = ! ! = ! ! ! ! ! ! ! ! = ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竺苎竺! ! ! ! 竺! ! ! 苎 m i n e 2 t - 0 解将线性离散规划问题( 1 1 4 ) 化为标准型的步骤为： 1 在第一到第四个约束不等式中分别减去剩余变量南，x 6 ，而，x 8 ； 不等式中加入松弛变量x 。，把不等式约束变为等式约束 2 因为 m a x 忸jij = 1 , 2 ，3 4 = 3 ， 令 毛= 3 一口i 2 0 ， e 2 = 3 一2 1 ， 岛= 3 一a 3 = l ， e 4 = 3 一吼= 2 ， 把求“m a x r a i n ”改为求“r a i n m a x ” ( 1 1 4 ) 在第五个约束 7 博士学位论文 d o c t o r 札d i s s e r t 兀o n g 得到该问题的标准型为 m i n f = m a x e ix j o ，p 】= 0 , e 2 = 1 ，e 3 = l ，p 4 = 2 s t 3 x i + 7 x 2 + 5 x 3 + 3 x 4 一如。1 6 x l + 2 x 2 + ：7 x 3 + 一2 1 5 + 4 x 2 + 2 x 3 + 6 x 4 一x 7 = 1 3 x l + 5 x 2 + 4 x 3 + 9 x 4 一x b 2 1 x i + x 2 + x 3 + x 4 + x 9 = o 2 5 x l ，x 2 ，x 3 。x 4 ，x 5 ，x 6 ，x 7 ，x s ，x 9 0 博士学位论文 d o c t o 姚d i $ s e r r n o n 1 2 线性离散规划的基本定理 我们约定线性离散规划的可行解、基、基可行解等定义与传统线性规划1 的有 关定义相同，且把满足 r a i n f ( x ) 一f ( x o ) 的可行解x o 称为最优解显然，任何一个线性离散规划问题的可行域( 如果不空的话) 是 一个凸集由于零解没有任何实际意义，而对于有零解的线性离散规划问题只需要加上 适当的约束条件就可以避免出现零解，为了叙述方便，不妨假设以后提到的解都是指非 零解 线性离散规划问题( 1 1 3 ) 是对目标函数 f ( x ) 2 m a x e ix j o ，= 1 , 2 ，n ) 求最小值显然对于每一个可行解x ，f o ) 存在且等于某一个8 ，所以f ( 砷的值域是 一个有限集可见，如果可行域非空，则( 1 1 3 ) 一定有解 定理1 2 1 如果线性离散规划问题存在可行解，则一定存在最优解 定理1 2 ，2 把线性离散规划问题( 1 1 3 ) 的目标函数f ( x ) 中的系数e l ，屯，e 。 同时加上或同时减去同一个数，晟优解不变 定理1 2 ，3 如果线性离散规划问题( 1 1 3 ) 的可行域非空，则其最优解集合是一 个凸集 证明根据定理1 2 1 。不妨假设线性离散规划问题( 1 1 3 ) 的最优值 m i n f = f o 记线性离散规划( 1 1 3 ) 的最优解集合为玩，可行解集合为d ，则 d b = x i x d ，f ( x ) = r 1 现在证明若x d o ，矿d o ，则对于任意的口，0 s 口1 成立 口一+ ( i - - 口) x 2 d o 因为d 是一个凸集，所以 口膏1 + ( 1 一掰) 工2 ed 设 m a x e jl 冀；o ，= l ，2 ，捍) 。8 ， 由f ( x 1 ) = e = r 可知x i o 。而且对于任意的_ ，e i8 j r ，e l ，g 。 ， x ：= 0 9 博士学位论文 d o c t o r a ld i s s 五r t t i o n 设 m a x t jjx j o , j = 1 , 2 ，九) = ， ， 由f ( x 2 ) 2 p h 2r 可知x ，2 ： 0 ，而且对于任意的，( l p j r ，e l ，e 2 ，p 。 x 2 j = 0 因为0 a 1 ，如果j 】= i ，2 ，则 盘x r i ( 1 一口) x 2 ： o ； 如果l j 2 ，则不等式 口x j ，+ ( 1 一口) o 口吐+ ( 卜g ) x j 2 ： o 至少有一个成立，而且当 ji e j f o ，e l ，p 2 ，e 。) 时， 口x 1 ，+ ( 1 一口) x 2 ，= o t 0 + ( 1 一a ) o = o 所以 f ( c 。+ ( 1 一a ) x 2 ) = r 所以线性离散规划问题( l1 3 ) 的最优解集合d o 为凸集 口 定义1 2 1 设集合 b ( 气) 2 ( 1 ，2 ，z 一 _ ，le e 如，e 1 ，e 2 ，e 。 ， g = c j x j 是个任意给定的线性函数，则把线性规划问题 m i n g = c j x ， i e b ( e m ) s t d 口工j = b i ( f _ l ，2 ，肌) ( 1 2 1 ) x j 0 ( ，b ( e ) 称为关于线性离散规划( 1 i 3 ) 的线性口( 气) 规划，或简称丑( e 。) 规划 定理 2 4 设e m e l , e 2 ，g n ) 如果线性离散规划问题( 1 1 3 ) 的可行域非 空，则m i n f = 8 厶的充分必要条件是： 1 ) b ( e 。) 规划存在可行解 2 ) 对于任意的e i ：e l 气，丑( 巳) 规划无可行解 证明因为线性离散规划问题( 1 1 3 ) 的可行域非空，所以一定存在最优解 设x o 是b ( p ，。) 规划的一个可行解，令 扣悸名搿小啦， 则x 1 = ( x ：，x 0 ，工：) 7 是线性离散规划问题( 1 1 3 ) 的一个可行解，且 1 0 所 显然8 m l n f ) 规划存在可行解，如果m i n ， ：“时苒，o = o ，既当_ ，正曰( e 。) 时z ，o = o ，“品8 0 k ) 规划存在可行解 假如对于某一个：气c f ，曰和 ) 规划存在可行解z ，； ”。 杉2 括0j 名搿川乩：， 。 l仨曰( 口。) “。川如 则( 。1 i 。；，) 7 是线性离散规划问题( 1 1 3 ) 的一个可行解，且 刖m a x e , j ，产1 2 ，磅。蚴蚓一旭_ ，g 魄) e e a 这与r a i n f = e 。矛盾 “ “ p ) 毗e e 旷p 1 ，e 2 ，e 。) 时 x ；= x ；= 0 踊为 ，= 1 ，t 。0 ( ，= l ，2 ，k ) 所以至少存在某一个基本可彳亍解满足： 0 ，当歹 歹 g ， p 自，口i ，p 2 ，# 一) 时 x 。= 0 即 f ( x ) = f ( x 9 ) ， 口 1 2 博士学位论文 d o c t o r a ld i s s e r t a t f o n 1 3 线性离散规划的求解 显然不能用传统的方法直接求解线性离散规划本节将介绍求解线性离散规划的 两种方法即拟目标规划法和直接法拟目标规划法是根据线性离散规划的基本性质和 目标规划( g o a lp r o g r a m m i n g ) 的基本思想“”构造的一种表上求解线性离散规划的方法 基于拟目标规划法也有线性离散规划的对偶单纯形算法直接法是根据线性离散规划的 基本性质直接求解线性离散规划的一种方法直接法简单直观，也可以在表上实现，但 是在求解的过程中会丢失很多倍息，不宜作优化后分析 3 1 拟目标规划法 目标按划可以看作是一种特殊的多目标规划( m u l f i o b j e c t i v ep r o g r a m m i n g ) ，它是美 国学者c h a m e s 等在1 9 5 2 年提出来的目标规划的主娶特点是对各个目标分级加权、 逐步优化。这符合人们处理问题要分轻重缓急、保证重点的思维方式目标规划的数学 模型可以袭示为 lf r a i n z = ( w g d 。+ 以n ) i - 1l 一1 s t g x = 也( f _ l ，2 ，坍) ( 1 3 1 ) 产f g ：c 目_ + 以一p i = g i ( j = 1 , 2 ，k ) j - i x 0 ( ，= 1 , 2 ，一) d 0 ，p i 0 ( t = 1 , 2 ，k ) 这里月，最，最为优先因子，