线性规划计算（上）_潘平奇著_9787030336163_湖南知新文化传播有限公司读者荐购服务

全书分为上、下两卷。上卷以基础和传统内容为主: 线性规划模型、可行域几何、单纯行法、对偶原理和对偶单纯行法、单纯行法实现技巧、原始和对偶主元规则等。

更多科学出版社服务，请扫码获取。

第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 年代初被重新发现，已是单纯形法问世之后.

人类的实践活动是一切科学理论和方法的原动力. 第二次世界大战给人类带来了巨大的损失、伤亡和灾难，然而战事的需求也极大地推动了科学技术的发展，催生了许多新兴学科. 而怎样运用现有条件(如人员和装备等) 取得最大战场利益的现实需求催生了最优化和运筹学.

George B. Dantzig 1946 年获得博士学位后，成为第二次世界大战期间美国空军审计部门的一位数学顾问. 他研究如何借助当时的计算工具更快地完成计划工作. 在第11 届国际数学规划大会(Bonn, 1982) 上Dantzig 回忆当时的情形时，他给出一个有趣例子：

如何将70 件不同的工作分派给70 个人去做？

尽管只有有限多个指派方案(70! > 10100)，但要逐一比较从中找出最优方案却不现实，因为那是个天文数字. 设想用每秒运算100 万次的计算机从150 亿年前宇宙大爆炸开始计算，能在1990 年给出答案吗？答案是不能. 即使用每秒可比较10 亿种方案的计算机，答案也是不能. 甚至将地球装满这种计算机且进行并行计算，答案仍然是否定的. 假如将太阳和1040 个地球都装满这种计算机，从宇宙大爆炸开始进行并行计算，那么也许要到太阳变冷才能得到结果. 这个例子说明了1947 年以前人们在选择最优方案时面临的困境. 当时只能以上司、权威人士的经验或判断订立若干基本原则，设法得到一个可以接受的方案. 如果用单纯形法处理上述指派问题，在IBM370-168 上只需一秒钟即得最优方案，更不用说使用当前更先进的计算机.

Dantzig 于1947 年夏天提出了线性规划模型和单纯形法，一般被认为标志着一个新学科的诞生. 当年10 月3 日，他拜访了科学家J. von Neumann，向他介绍了这些结果. Neumann 很快就抓住了方法的基本思想，并指出与自己正在研究的对策论存在可能的内在联系，让Dantzig 获益匪浅. 1948 年，Dantzig 参加了一个在Wisconsin 召开的计量经济学会议，参加者包括当时一些非常著名的统计学家和数学家，如von Neumann 和H. Holelling 及著名的经济学家，如T. C. Koopmans. 年轻的Dantzig 报告了线性规划和单纯形法后，会议主席请大家提问. 会上先是“死一般的沉寂”，接着Hotelling 站起来说：“但是，我们都知道世界是非线性的.”在一群大人物面前，当时还名不见经传的Dantzig 一时不知所措. 幸好von Neumann在征得同意后为他解了围：“报告人命题为‘线性规划’并详细论述了他的原理. 如果实际问题满足这些原理就好好应用，否则不去用它就是.”当然Hotelling 说的没错，世界的确是高度非线性的；然而幸运的是，现实中的非线性关系常常可用线性关系近似.

20 世纪40 年代电子计算机的问世给世界带来了巨大的变化，称之为划时代和革命性的一点也不为过. 计算机以其无与伦比的穿透力，深刻地改变了(并还正在改变着) 几乎所有学科的面貌，也使线性规划如虎添翼、迅速发展. 单纯形法的计算机实现发端于美国标准局(National Bureau of Standards). 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 计算机学会刊物“科学和工程计算”(Computing in Science andEngineering)2000 年第1 期选出对20 世纪科学和工程的实践与发展影响最大的十个算法(Cipra, 2000)，单纯形法名列其中. 历史一再表明，正是实践的沃土使理论和方法之树根深叶茂、硕果累累.

然而，人们不久发现单纯形法具有指数时间复杂性(Klee and Minty, 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 所应满足的不等式为

+ y

4 6 1;

即

2x + 3y 6 12:

从包装能力看又有

x + y 6 5;

而从颜料供应的情况有

y 6 3:

另外，按实际背景还应有x; y > 0 的限制(为简单计，这里忽略了玩具个数为整数的限制).

上述分析结果可归纳为如下问题：

max f(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) j 2x + 3y 6 12; x + y 6 5; y 6 3; 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 三种产品. 其生产过程都需经过零件加工、电镀和装配三道工序. 各工序每天的生产能力折合成有效工时. 各产

你还可能感兴趣

我要评论