首页 > 图书中心 >图书详情

线性规划

作者:卢开澄、卢华明
定价:29.50
印次:1-1
ISBN:9787302182207
出版日期:2009.02.01
印刷日期:2009.01.16

全书共9章,分单纯形法和几个专题两部分。 第一部分单纯形法,包括数学模型、单纯形法、改善的单纯形法、单纯形法的补充、对偶原理与对偶单纯形共5章。第二部分几个专题,包括运输问题及其他、内点法简介、目标规划、整数规划共4章。 第一部分是基本内容;第二部分供各取所需选择内容,概括了线性规划的各个方面,算例丰富是其特点。本书可作为计算机系、数学系、经济管理学院本科生及研究生的教材。

more >

计算机科学组合学丛书序 电子计算机的出现是20世纪的大事,它改变了我们这个世界的面貌。可以毫不夸张地说,它的影响遍及所有角落,几乎无处不感觉到它的存在。数学更不例外。严格地说,电子计算机本身就是近代数学的辉煌成就。将计算机与数学割裂开来,既不合理也不可能。组合学也就是在计算机科学蓬勃发展的刺激下而崛起的,从而成为近若干年来最活跃的数学分支。它研究的问题有的可追溯到Euler和Hamiltan等18世纪的数学家,但它成为新的分支还是近若干年的事。它从与计算机科学相结合中获得了广阔的发展空间,从而也为计算机科学奠定了理论基础。 什么是计算机科学呢?有的学者将它定义为研究算法的一门学科。研究算法无疑是计算机科学的重要领域,也是本丛书的核心内容,贯穿始终。组合学家在20世纪70年代初建立的算法复杂性“NP理论”,至今仍然令无数计算机科学工作者与数学工作者为之折腰。 计算机科学里的组合学内容十分广泛。本丛书涉及组合分析、图论、组合算法、近代密码学、组合优化、编码理论及算法复杂性等7部分。 组合分析是算法的理论基础。组合分析之与组合算法犹如数学分析之与计算数学,众所周知,前者是后者的理论根基。 图论原本是组合数学这个“家族”的主要成员,只因它已成长壮大,故自立门户独立出去。 算法复杂性的NP理论是近三十年的一大成就。研究表明对于一类叫做NPC类的困难问题,至今都没找到有效算法,但它们难度相当,只要其中任何一个找到多项式解法,则全体都获得解决;或证明它们根本不存在有效办法。不论是前者还是后者都还看不见露到海平面上的桅杆塔,它吸引了众多的有志之士。密码学是其中十分引人入胜的分支。如若设计好的密码,对它的破译等价于某一NPC类困难问题,无疑这样的密码将是牢不可破的。 在计算机网络深入普及的信息时代,信息本身就是时间,就是财富。信息的传输通过的是脆弱的公共信道,信息储存于“不设防”的计算机系统中,如何保护信息的安全使之不被窃取及不至于被篡改或破坏,已成为当今被普遍关注的重大问题。密码是有效而且可行的办法。在计算机网络的刺激下,近代密码学便在算法复杂性理论的基础上建立起来了。密码作为一种技术,自从人类有了战争,不久便有了它。但作为一门学科则是近二十多年的事。甚至于它已成为其他学科的基础。密码也从此走出“军营”,进入百姓家。 实际中的“优化”问题是大量的,半个多世纪以来它曾经几度辉煌。近来在计算机科学的影响下,又出现了若干闪光点,十分耀眼,引人注目。 实际上密码也是一种编码。如果说密码学研究的编码是保证通信的保密与安全,则编码理论研究的是通信中如何纠错与检错。计算机纠错码是既实用、理论上又饶有趣味的分支。 本丛书是作者在清华大学计算机科学与技术系长期工作的总结。它不是一部“长篇”记述,而是互相关联又彼此相对独立,因此难免有少量交叉。它们涉及的面如此之广,囿于作者的水平,缺点和错误在所难免,敬请读者不吝指正。 作 者前 言 线性规划最初是美国军方为解决其运输等后勤问题而提出来的。自从1947年G.B.Dantzig公开了他的单纯形法以来,其应用范围日益扩大,几乎遍及经济规划、工业生产和商业活动等各个方面。单纯形法始终扮演着光彩夺目的角色。线性规划也作为运筹学的主要内容受到普遍重视,以至于许多高等院校的数学系、经济管理系以及系统工程等专业都把它列为一门必修课。 线性规划在其发展过程中有几件事值得一提,一方面是受到管理思维的影响,经济活动已不是像“经济人”那样一味地追求“利润极大”、“开支极小”,代之以决策时考虑“普遍感到满意”,目标规划就是在这个基础上被提出来的。它还属线性规划的范畴,但比传统的单目标规划灵活,值得大力推动以扩大其应用。 另一方面随着计算机科学的蓬勃发展,计算复杂性理论新军兴起,引人入胜,单纯形法虽然表现甚佳,但它的复杂性究竟如何?这时Minty和Klee举出一个例子证明单纯形法在最坏情况下属于指数型算法。20世纪70年代末,前苏联数学家Xaчиян提出线性规划的椭球算法,从理论上证明了线性规划属于多项式型问题,然而椭球算法的实际效果极差,徒有理论价值。不久Bell实验室的Karmarkar又提出一个新的多项式算法理论,并证明其复杂性分析能力比Xaчиян的椭球算法要好。但人们相信该算法还有进一步改善的潜力,经20世纪80年代以来多人的努力,似乎由此形成的“内点法”在超大型问题方面解题速度要快于单纯形法。 线性规划中的整数规划,其难度要大得多,其中有不少涉及NP理论的命题,本书将适当介绍。 本书主要由卢华明执笔。囿于作者的水平,缺点和错误在所难免,敬请指正! 编者2008年7月

more >
扫描二维码
下载APP了解更多

同系列产品more >

组合数学(第5版)

卢开澄、卢华明
定 价:45元

查看详情
信息安全的数学基础

卢华明
定 价:29.90元

查看详情
组合数学(第4版)习题解答

卢华明
定 价:33元

查看详情
椭圆曲线密码算法导引

卢开澄、卢华明
定 价:19元

查看详情
组合数学(第4版)

卢开澄
定 价:32元

查看详情
图书分类全部图书
more >
  • 第一部分 单 纯 形 法

    第1章 数学模型3

    1.1 引言3

    1.2 问题的提出4

    1.3 标准形式与矩阵表示8

    1.4 几何解释9

    习题一12

    第2章 单纯形法15

    2.1 凸集15

    2.1.1 凸集概念15

    2.1.2 可行解域与极方向概念16

    2.2 凸多面体17

    2.3 松弛变量18

    2.3.1 松弛变量概念18

    2.3.2 松弛变量的几何意义19

    2.4 单纯形法的理论基础21

    2.4.1 极值点的特性21

    2.4.2 矩阵求逆22

    2.4.3 可行解域无界的情况23

    2.4.4 退化型举例25

    2.5 单纯形法基础26

    2.5.1 基本公式26

    2.5.2 退出基的确定与进入基的选择27

    2.5.3 举例29

    2.6 单纯形法(续)31

    2.6.1 基本定理31

    2.6.2 退化型概念32

    2.6.3 单纯形法步骤33

    2.6.4 举例34

    2.7 单纯形表格40

    习题二49

    第3章 改善的单纯形法52

    3.1 数学准备52

    3.2 改善的单纯形法54

    3.2.1 改善的单纯形法的步骤54

    3.2.2 举例55

    3.3 改善的单纯形法表格60

    3.3.1 表格的介绍60

    3.3.2 复杂性分析63

    习题三64

    第4章 单纯形法的补充66

    4.1 二阶段法66

    4.2 大M法74

    4.3 变量有上下界约束问题79

    4.3.1 下界不为零的情况79

    4.3.2 有上界的约束79

    4.4 退化情形87

    4.4.1 退化形问题87

    4.4.2 出现循环举例与防止循...

精彩书评more >

标题

评论

版权所有(C)2023 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802042911号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘