线性规划计算（上）
2012-4
科学出版社
潘平奇
284
《运筹与管理科学丛书12：线性规划计算（上）》论述与线性规划实际计算有紧密联系的理论、方法和实现技术，既包括这一领域的基础和传统内容，也着力反映最新成果和进展。本书分为上、下两卷。上卷以基础和传统内容为主：线性规划模型、可行域几何、单纯形法、对偶原理和对偶单纯形法、单纯形法实现技巧、原始和对偶主元规则、原始和对偶I阶段法、灵敏度分析、大规模问题分解法、Kamlarkar算法、原始和对偶仿射尺度算法及路径跟踪算法等。所有算法都尽可能配以例题。
《运筹与管理科学丛书12：线性规划计算（上）》可作为数学及相关专业高年级本科生和研究生教材，也可供决策管理人员、科研和工程技术人员参考。作为教材时，可视具体情况决定内容取舍。
序
前言
符号表
第1章 导论
1.1 线性规划源起
1.2 从实际问题到数学模型
1.3 线性规划模型实例
1.4 标准线性规划模型
1.5 高斯一若尔当消去
1.6 浮点运算误差
第2章 可行域几何
2.1 多面凸集和可行域
2.2 可行域的几何结构
2.3 最优界面和最优顶点
2.4 最优解的启发式特征
2.5 可行方向和积极约束
第3章 单纯形法
3.1 单纯形表
3.2 表格单纯形法
3.3 单纯形法的启动
3.4 退化和循环
3.5 有限主元规则
3.6 修正单纯形表
3.7 单纯形法
3.8 计算复杂性
第4章 对偶原理和对偶单纯形法
4.1 对偶线性规划问题
4.2 对偶原理
4.3 最优性条件和对偶的经济解释
4.4 表格对偶单纯形算法
4.5 对偶单纯形算法
4.6 最优解集的获取
4.7 注记
第5章 主元规则
5.1 部分计价
5.2 最陡边规则
5.3 近似最陡边规则
5.4 最大距离规则
5.5 嵌套规则
5.6 最大距离嵌套规则
5.7 简约价格的计算
第6章 对偶主元规则
6.1 对偶最陡边规则
6.2 近似对偶最陡边规则
6.3 对偶最大距离规则
6.4 对偶嵌套规则
第7章 I阶段法
7.1 不可行和法
7.2 单人工变量法
7.3 最钝角列规则
7.4 简约价格摄动法
第8章 对偶I阶段法
8.1 对偶不可行和法
8.2 对偶单人工变量法
8.3 最钝角行规则
8.4 右端列摄动法
第9章 单纯形法的实现
9.1 概述
9.2 预处理：调比
9.3 稀疏Lu分解
9.4 Lu分解校正
9.5 初始基：闯入策略
9.6 Harris实用行规则和容限扩展
9.7 线性规划问题的等价变形
9.7.1 简约问题
……
第10章 灵敏度分析
第11章 大规模问题分解法
第12章 内点法
附录A MPS文件
附录B 线性规划试验问题
参考文献
《运筹与管理科学丛书》已出版书目
第1章 导论 人类的智慧之一在于其进行活动有预定目标.早期人们单凭经验判断和行事以达目标，而现代人则借助先进的软硬件科学手段进行决策，所获效益与之前自是不可同日而语. 所谓“最优化”，简言之即以尽可能小的代价达成尽可能好的结果.如怎样分配有限的资源(人力、金钱、物资等)使获益最大化，或以最小的代价达成一定目标等.人们根据所占有的信息和数据，将实际问题用数学语言，如数字、方程或函数等恰当表述，即建立数学模型；然后用最优化数学方法求解模型，从而为决策提供科学可靠的定量依据.这种将问题数学化并用数学手段加以解决的方法因电子计算机的使用而具有无可估量的革命性意义. 线性规划模型具有非常简单的数学结构，其中所涉及的函数或方程均为线性.不过其规模却可以很大，涉及成千上万个变量或方程已习以为常，而其求解也并非易事.借助计算机，目前线性规划计算技术已有能力求解很大规模的问题.包含数十个甚至数百个约束条件和变量的只算是小问题，有成千上万约束条件和变量的可算中等规模问题，而有数十万或数百万以上也许才算是大规模问题.20世纪90年代初，美国运筹学家成功地求解了一个有一千多万个变量的线性规划问题，为一家航空公司乘务人员的工作安排提供了最佳方案(Bixby，1992).然而随着全球化趋势日益明显，为追求大系统整体效益而建立的线性规划模型越来越大，对算法和软件的效率及稳定性等提出了更高的极具挑战性的要求. 本书旨在从实用的角度介绍线性规划的理论、方法和实现技术，既包括这一领域的基础和传统内容，也着力反映最新研究成果和进展. 1.1线性规划源起 对线性规划的源起和发展作一个简要回顾是有益、富有情趣和给人启迪的. 线性规划的萌芽可以追溯到19世纪20年代.法国数学家J.B.J.Fourier(因其冠名的级数而著名)于1823年、比利时数学家V.Poussin于1911年分别写过一篇涉及线性规划的论文，然而这些孤立的工作没有产生任何影响. 1939年，前苏联数学家L.Kantorovich在其《生产组织与计划的数学方法》一书中提出“解乘数法”，已经涉及线性规划模型及其求解，可惜未引起当局注意，在国际学术界也鲜为人知.F.L.Hitchcock于1941年发表了一篇很好的有关运输问题的论文，但一直未受关注，直到40年代末50年代初被重新发现，已是单纯形法问世之后. 人类的实践活动是一切科学理论和方法的原动力.第二次世界大战给人类带来了巨大的损失、伤亡和灾难，然而战事的需求也极大地推动了科学技术的发展，催生了许多新兴学科.而怎样运用现有条件(如人员和装备等)取得最大战场利益的现实需求催生了最优化和运筹学. GeorgeB.Dantzig1946年获得博士学位后，成为第二次世界大战期间美国空军审计部门的一位数学顾问.他研究如何借助当时的计算工具更快地完成计划工作.在第11届国际数学规划大会(Bonn,1982)上Dantzig回忆当时的情形时，他给出一个有趣例子： 如何将70件不同的工作分派给70个人去做？ 尽管只有有限多个指派方案(70!>10100)，但要逐一比较从中找出最优方案却不现实，因为那是个天文数字.设想用每秒运算100万次的计算机从150亿年前宇宙大爆炸开始计算，能在1990年给出答案吗？答案是不能.即使用每秒可比较10亿种方案的计算机，答案也是不能.甚至将地球装满这种计算机且进行并行计算，答案仍然是否定的.假如将太阳和1040个地球都装满这种计算机，从宇宙大爆炸开始进行并行计算，那么也许要到太阳变冷才能得到结果.这个例子说明了1947年以前人们在选择最优方案时面临的困境.当时只能以上司、权威人士的经验或判断订立若干基本原则，设法得到一个可以接受的方案.如果用单纯形法处理上述指派问题，在IBM370-168上只需一秒钟即得最优方案，更不用说使用当前更先进的计算机. Dantzig于1947年夏天提出了线性规划模型和单纯形法，一般被认为标志着一个新学科的诞生.当年10月3日，他拜访了科学家J.vonNeumann，向他介绍了这些结果.Neumann很快就抓住了方法的基本思想，并指出与自己正在研究的对策论存在可能的内在联系，让Dantzig获益匪浅.1948年，Dantzig参加了一个在Wisconsin召开的计量经济学会议，参加者包括当时一些非常著名的统计学家和数学家，如vonNeumann和H.Holelling及著名的经济学家，如T.C.Koopmans.年轻的Dantzig报告了线性规划和单纯形法后，会议主席请大家提问.会上先是“死一般的沉寂”，接着Hotelling站起来说：“但是，我们都知道世界是非线性的.”在一群大人物面前，当时还名不见经传的Dantzig一时不知所措.幸好vonNeumann在征得同意后为他解了围：“报告人命题为‘线性规划’并详细论述了他的原理.如果实际问题满足这些原理就好好应用，否则不去用它就是.”当然Hotelling说的没错，世界的确是高度非线性的；然而幸运的是，现实中的非线性关系常常可用线性关系近似. 20世纪40年代电子计算机的问世给世界带来了巨大的变化，称之为划时代和革命性的一点也不为过.计算机以其无与伦比的穿透力，深刻地改变了(并还正在改变着)几乎所有学科的面貌，也使线性规划如虎添翼、迅速发展.单纯形法的计算机实现发端于美国标准局(NationalBureauofStandards).1952年前后，美国标准局的A.Ho?man团队将单纯形法在一些试验问题上进行了试算，与当时流行的T.Motzkin的方法进行比较大获全胜.1953到1954年间，W.Orchard-Hays开始了他开创性的工作，基于单纯形法编制了第一个商业性软件，在早期的计算机上求解线性规划问题.他的实现技术随后被M.A.Saunders和R.E.Bixby等许多学者应用和发展，使单纯形法从理论变为强有力的工具，激发了整个领域的快速发展.不少诺贝尔经济学奖的获奖工作与线性规划的应用密切相关，如上面提到的L.V.Kantorovich和T.C.Koopmans因对资源最优配置理论的贡献分享1975年诺贝尔经济学奖.单纯形法的应用也带来了巨大的经济和社会效益，美国物理研究所和IEEE计算机学会刊物“科学和工程计算”(ComputinginScienceandEngineering)2000年第1期选出对20世纪科学和工程的实践与发展影响最大的十个算法(Cipra,2000)，单纯形法名列其中.历史一再表明，正是实践的沃土使理论和方法之树根深叶茂、硕果累累. 然而，人们不久发现单纯形法具有指数时间复杂性(KleeandMinty,1972)，而一般认为具有多项式时间复杂性才是“好”算法(见3.8节).实际上，单纯形法甚至不具有限性，不能保证有限步终止(Beale,1955;Ho?man,1953).1979年，前苏联数学家L.G.Khachiyan(1979)提出了求解线性规划问题的第一个多项式时间算法(椭球方法)，实现了一次重大的理论突破.可惜发现其实际效果不佳，远不如单纯形法.实际上，所谓\多项式时间"只是最坏情形复杂性；而较为适当的是平均时间复杂性.K.H.Borgward(1982a,b)证明，使用某个主元规则的单纯形法求解原始数据服从一定分布的线性规划问题，所需迭代次数的数学期望不超过O(n4m).S.Smale(1983a,b)也给出类似结果.这些结果表明单纯形法具有平均多项式时间复杂性，与其杰出的实际表现相吻合. 1984年，印度数学家N.Karmarkar提出一个具多项式时间复杂性的内点法，比椭球法具更低的多项式阶，且在随后的数值试验中表现不凡，引起学术界广泛关注，迅速激发内点法热，涌现了一批出色的研究成果.以致不少学者一度认为内点法在求解大规模稀疏线性规划问题上超越了单纯形法. 另一方面，单纯形法也未止步不前.P.M.J.Harris(1973)首次成功地试验了近似最陡边主元规则.J.J.H.Forrest和D.Goldfarb(1992)给出了最陡边规则的若干变形和相应的递推公式，报告了极好的数值试验结果，促成了单纯形法与内点法伯仲难分的态势. 基本上，算法的评估是个实践问题.一个算法的价值，其效率、精度、可靠性或稳定性最终取决于实际表现.太拘泥于理论并非明智之举.实际上，有限性或复杂性甚至有误导之虞；毕竟，有限或多项式时间算法的表现一般远不及非有限或非多项式时间算法，而迄今应用中的主角也是后者而非前者.鉴于此，作者以实践作为本书的着眼点和内容取舍的依据，着力于同实际计算密切相关或行之有效的算法、理论和实现技术.而在描述算法的同时，尽可能配以例题演示. 1.2从实际问题到数学模型 由实际问题入手建立数学模型是应用线性规划的第一步.而好的模型的建立，需要充分了解实际情况并占有详实数据，再加上知识、智慧、经验和技巧.详细讨论这方面的论题已超出本书的范围.为让读者对此有个基本了解，不妨先看下面的简单例子. 例1.2.1某公司有1100吨原木，按合约规定要为一企业加工某种规格的板材470吨.在加工过程中的损耗为6%.现在公司的决策者面临的情况是，板材的售价在签约后没变化但生产成本却上升了，实际上原木作为原材料出售更赚钱.那么如何在遵守合约的前提下获利最大呢？ 这样的问题可用简单的代数方法解决.设作为原材料出售的原木为x吨，用于加工板材的原木为y吨.用于加工板材的y吨原木中有6%要在生产过程中损耗掉，故板材的实际产量为y-0:06y，而产量必须等于合约规定的470吨，即 y-0:06y=470: 另一方面，加工后还余下1100?y吨原木，将其全部出售显然获利最大，于是又有 1100-y=x: 由上面两个等式联立得二元一次方程组 y-0:06y=470; 1100-y=x;(1.1) 仅有唯一解 x=600;y=500: 换言之，该公司只有唯一的决策方案，即将500吨原木用于生产板材，而将其余600吨出售. 然而更大量的问题并非如此，通常存在多个(甚至无限多)方案供决策者选择，如下面这个例子. 例1.2.2某公司生产两种玩具，小狗和小熊.每只玩具狗的利润为2元，每只玩具熊的利润为5元.若公司的设备能力都投入使用的话，每天可生产玩具狗60000只或者玩具熊40000只.由于某种颜料有限，每天最多可供30000只玩具熊的生产.另外该公司仅有每天50000只玩具的包装能力.经营者每天应安排生产多少玩具狗和玩具熊才能获得最大利润？ 设每天应生产x万只玩具狗和y万只玩具熊，总共可获得f(x;y)=2x+5y万元利润.变量x和y的一组取值代表一个决策，而函数f的对应值即为采用该决策所获利润.这里需要确定变量x和y的值使函数f(x;y)取最大值，或着说使其“极大化”. 显然，如果对两种玩具的生产没有限制的话，可获得任意大的利润.当然情况并非如此.客观条件的限制如下：从公司的设备能力来看，生产玩具狗和玩具熊的平均速率分别为6万/天和4万/天，可推出变量x和y所应满足的不等式为 x 6 +y 461; 即 2x+3y612: 从包装能力看又有 x+y65; 而从颜料供应的情况有 y63: 另外，按实际背景还应有x;y>0的限制(为简单计，这里忽略了玩具个数为整数的限制). 上述分析结果可归纳为如下问题： maxf(x;y)=2x+5y; s:t:?2x-3y>?12; ?x-y>?5; ?y>?3; x;y>0: (1.2) 这就是例1.2.2的数学模型.其中x和y为决策变量；f(x;y)为目标函数；其余各行不等式为加于决策变量的限制，称为约束条件；满足约束条件的每对变量值称为可行解，而可行解的全体称为可行集或可行域.使目标函数达到最大值的可行解称为最优解.所谓求解一个模型就是寻找它的最优解，从而找到决策者所应采取的最优策略.(1.2)仅涉及线性函数，称之为线性规划问题(模型).这类问题是本书的讨论对象. 例1.2.1只有一个可行解，也为其最优解，完全由方程组(1.1)确定，因而无需任何优化方法就能解决.而例1.2.2不同.其可行域可表示为 P=f(x;y)j2x+3y612;x+y65;y63;x>0;y>0g: 该集合包含无限多个可行解.几何上，由于实数对与平面直角坐标系中的点一一对应，可行域P可用与之对应的一个区域来表示.如图1.2.1所示，x坐标轴表示玩具狗的数量，y坐标轴表示玩具熊的数量，以万为单位.每个约束不等式都对应一个闭半平面，图上标明了其边界直线的方程.所有这些闭半平面的交集，即它们的公共部分即对应P，其中每一点都对应一个可行解. 图1.2.1例1.2.2的可行域 现在问题归结为如何从区域P中找到对应函数f(x;y)=2x+5y最大值的点，即所谓“最大点”.因为该区域包含无限多个点，用穷举的方法，即取出所有的可行点一一比较显然行不通.而大规模问题的求解则更为困难和具挑战性.线性规划方法是处理这些问题的有力工具. 现实中通常存在大量方案供决策者选择，不同方案可能导致大相径庭的结果，这在激烈的竞争中可能生死攸关，也为决策者们提供了尽显其聪明才智的舞台.但毫无疑问，单凭经验决策不能与借助线性规划方法同日而语. 1.3线性规划模型实例 线性规划的应用十分广泛，几乎涉及所有需要进行决策或管理的领域.这些领域中产生的线性规划模型形形色色，本节给出一些典型例子.严格地说，其中部分例子涉及的变量取值必须为非负整数，但这里将忽略这个限制. 例1.3.1(生产计划问题)某公司生产A，B，C三种产品.其生产过程都需经过零件加工、电镀和装配三道工序.各工序每天的生产能力折合成有效工时。
喜欢，第一本使用蒋介石日记作为材料的传记，给我们看到一个深受儒家思想影响的蒋介石。蒋介石与毛泽东其实都是强烈的爱国者，出发点一点，只是建设国家的路径不同而已，历史不容假设，爱党爱国爱伟人了。。。。