1、运筹学第四讲: 线性规划(三)(2008 年 10 月 7 日)内容提要(1)算法复杂度的概念, (2)线性规划求解的多项式复杂度算法, (3)线性规划求解软件包 (主要以 Maple 为例) 的使用方法, (4)对偶线性规划的基本性质和算法,(5) 影子价格: 对偶线性规划的经济学解释, (6)线性规划的灵敏度分析第一节 算法复杂度的概念衡量一个算法的好坏,计算时间的多少是非常重要的一个标志. 太花费时间的算法总是不手欢迎的. 由于实际的执行时间依赖于计算机的性能,因此算法所用时间指的是它执行的基本运算( 如算术运算, 比较运算)的总次数来衡量的. 当然, 即使用同一个算法计算同一类型的问题
2、时, 由于各问题的数据不同 , 计算快慢也会不同 , 一般用最坏情况下所花的时间来做讨论. 设输入数据的规模为 l, 设在最坏情况下的运算次数为 f(l), 这样的 f(l)可以称为算法的计算复杂度 . 具体看下面的几个例子1 整数的乘法. 若以数字的位数为数据的规模, 10 以内的乘法（九九表）和任意长整数数的加法为基本运算, 则一个 位整数和一个 位mn整数的乘法, 按照我们通常使用的方法 , 需要的运算次数为：乘法为次, 加法的次数为 次, 合起来 . nm1nm1),(nmnf2 排序. 若以输入的数据的个数为规模, 则将 个数 按照从na,21小到大的次序排列, 最容易想到的方法是
3、Inserting Sorting, 这个方法, 其实很多人玩扑克的时候在用, 先把手里 8 的牌扣在桌子上, 然后一个一个地拿起来, 然后插在合适的位置. 如下面的图数字按照这种方法排序的过程, 可以用下面的图来形象地表示. Inserting 排序的计算次数根据输入的数字的情况, 最坏情况下需要的计算（比较）次数是 的一个二次函数, n, cbnaf2)(其中 是与 无关的常数. 当 充分大的时候, 二次函数的大小主, n要决定于二次项, 即, 2)(naf又系数 与 无关, 可写成下面形式)()2nOf这个记号 在分析算法的复杂度的时候非常有用. 如果同一个问题, )(O有两个不同的算法
4、 , 其复杂度都是 , 虽然前面的常数不同, A )(2nO如 ,)(|,)(| 221ncfncfAA 但从复杂度分析的角度来说, 可以看成同一类的, 如果两个算法, 里面的函数的比值, 在 时的极限是 或者 , 则他们的算法)(On0复杂度之间认为有很大差别. 例如, 已知多项式 的各系数和一个011)( axxaxPnn 具体的数值 , 则计算多项式 在 的值 , 可以用下面0 )(P0)(P的两个算法 ., ),1(21;,:120101010210 nQP nxaPxaPAnnnn不不 其复杂度为 ),()1(2)(| 2nOnfA,;,:011201210 nnaxPaxPAnnn
5、 不不其复杂度为 ),(2)(| nOnfA我们说, 的复杂度比 的高. A有些算法的复杂度含有对数 , 有的有指数 等表达式. 例如, )(lognn2设求整数 的最大公因数 , 用下面的 Euclid 递归算法：0bacdbafi baEuclidretnlshbifaEucld)mo,(0),(则该算法的递归次数是 .如果用整数 的位长作为数据规模, )(lgOb则算法复杂度是 . 判断一个整数 是否素数, 如果用下面的方法)naodfibnextslruthaif doatomFIs_Prie| 2)(计算的话, 需要的次数 , 按照 的位数 衡量 , 是 . an)2(/nO具有什么
6、样的复杂度的算法是一个好的算法？目前计算机科学中广为接受的观点是：多项式时间算法, 即 或者, )(,),(32nnf以多项式为上界的算法, 如 等, 是好的算log),l()2Onf法；而指数时间算法, 或以指数式为下界的算法, 则是坏的. 我们可以以下面的故事来感受一下指数增长的恐怖（这可以看成空间复杂度的例子）. 故事说的是很久很久以前. 在古波斯 , 或是印度, 国王的“内阁大学士”Vizier(宰相)发明了一种新游戏. 玩法是在一个分成 64 个红色和黑色小方块的方板上, 移动一些棋子. 最重要的棋子是国王, 其次是宰相 在一位宰相发明的游戏里 , 这是理所当然的. 游戏的目标是捉住
7、对方的国王, 因此这种游戏在波斯语里叫作 shahmat, 其中 shah 的意思是国王, mat 是死. 俄国人仍把它称为 shakhmat, 似乎传达着某种挥之不去的革命气息 . 甚至英语里也仍回荡着这个名字的余音最后的一着叫作 checkmate（将死）. 不用说, 这种游戏就是象棋. 随着时间的流逝, 棋子、棋步、游戏规则都发生了变化 , 例如宰相换成了力量更强的王后. 为什么一个国王会为一个叫做“国王之死”的游戏问世感到高兴, 实在难以理解. 但故事就是这样发展的. 他非常高兴 , 让宰相提出他想要的奖赏 . 宰相早就想好了, 对国王说, 他是个谦逊的人, 只想要一点普通的奖赏 .
8、他指着自己发明的棋盘上的 8 行和 8 列格子说, 希望能在第一个格子里放一粒麦子, 第 2 个格子增加一倍, 第 3 个再增加一倍, 直到所有的格子填满. 国王反对说 , 对这样重要的一桩发明而言 , 这份奖品太寒酸了. 他表示愿意赏赐珠宝、舞姬、宫殿但宰相得体地低眉顺眼, 拒绝了这些：他只想要一小堆麦子 . 国王暗暗对他的谦卑和节制感到惊奇, 同意了他的请求.然而, 皇家仓库的总管开始数麦子时, 国王遇到了一个令人不快的意外 . 麦子的数目开始是很小的：1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 但到第 64 个格子时, 麦粒数目变得极为庞大,
9、 令人错愕 . 事实上, 这个数目将近 1850 亿亿, 见下表. 这位宰相大概非常喜欢高纤维食物. 1850 亿亿粒麦子有多重？如果 100 粒麦子才 1 克, 那么 1 亿粒麦子就是 1 吨, 1850 亿亿粒的麦子加起来可能达到 1850 亿吨 , 远远超过国王的粮仓里所储存的麦子. 事实上, 以目前世界小麦生产水平 , 1 年才能生产 5 亿吨吧, 这样的话, Vizier 要的麦子得 300 多年才能生产出来 . 接下来的事没有流传下来. 究竟是国王自责没学好算术、因而把王位传给了宰相, 或者宰相遭受了一项新游戏 “viziermat”的磨难, 我们就无从得知了. （出自 Cark
10、Sagen: Billions and Billions）现在回到线性规划问题的单纯形解法. 实际计算表明, 单纯形解法一般来说都是相当有效的. 那么, 它是不是多项式时间算法呢？ 1972年, 美国学者 Klee 和 Minty 发现了一个例子, 结论出乎人们预料, 例子说明单纯形方法的时间复杂度是指数阶的. 他们构造的例子是n.1,2j 0xn,12.j ,0x s.t ,10 Maxj 2-ii-jjnjj-这个问题的可行解集合是有一个 n 维长方体做些扰动得到 . 它共有2n 个顶点. 若采用通常的方法, 从它的一个顶点（ 0,0,.,0）（原点）出发, 需要旋转 2n-1 次才能达到
11、最优解. 下面是 n=3 的情况. 这之后, 有一段時期內人們曾不能確定線性規劃問題究竟是否存在任何多项式时间复杂度的解法. 1979 年, 苏联青年数学家 给出线性规划的第一个多项式时间复杂度的算法. 這個算法建基於非線性規劃中 Naum Shor 發明的橢球法, 但在實際應用上 , 的演算法令人失望：一般來說, 單純形演算法比它更有效率 . （1982 年, Borgwards, 1983 年, Smale 证明单纯型方法的平均运算次数是多项式级的）. 算法的重要性在於它鼓勵了對內點算法的研究. 相對於只沿著可行域的邊沿進行移動的單純形算法, 內點演算法能夠在可行域內移動. 1984 年,
12、 Narendra Karmarkar（卡馬卡）提出了投影尺度法. 這是第一個在理論上和實際上都表現良好的算法：它的最壞情況僅為多項式時間, 且在實際問題中它比單純形算法有顯著的效率提升. 當今的觀點是：對於線性規劃的日常應用問題而言, 若算法的實現良好, 基於單純形法和內點法的算法之間的效率沒有太大差別. 第二节 线性规划的多项式计算时间的解法本节主要介绍线性规划问题之椭球算法和内点算法的基本想法. 我们采用赵建中、许绍吉线性规划第十章 “LP 问题的多项式时间的算法”的材料来介绍. 椭球算法先证明：(1)存在求解线性规划问题的多项式时间算法的充分必要条件是存在判定 是否为空集的多项式时间算法；|bAxRPn(2)如果存在一个判定严格不等式组的解集合 是否为|bAxRKn空集的多项式时间算法, 就存在一个判定 是否为空|xP的多项式时间算法. 椭球算法的基本思想是, 首先取一个很大的球 , 它可以取得足够0E大, 如果 , 则可认为 . 然后用一个迭代方法, 依次产KKE0生一系列 , 尺寸越来越小, 但每一个都与 相交. 021E K
