5.1 通用模型

线性规划的故事有个经典的开头：1939年，年轻的George Dantzig在美国加州大学伯克利分校读研究生一年级。有一天，他上课迟到了，这门课的授课教师是Jerzy Neyman。Dantzig进了教室，看到黑板上写了两道题目，便匆匆忙忙抄下来，几天后把解答交了上去。“长话短说，我把黑板上那两道题目当成作业做完了，可是它们实际上却是统计学领域著名的未解难题。”¹这一周的辛苦研究真不赖。那两道“作业题”的解答最后成为了他的博士毕业论文的主要内容。

^{1. Albers and Reid (1986).}

Dantzig从伯克利毕业时，正值第二次世界大战。二战期间，他一直供职于美国空军研究规划问题。尽管“规划”的英文是program，与“程序”相同，但是在军事环境中，这个词指的并非一系列计算机指令，而是“针对作战单元的军事训练、后勤供应与调度部署而提出的行动计划”。²Dantzig逐渐成为了该领域的专家，谙熟如何用台式计算器处理各种报表系统提供的数字，从而给出此类规划。

^{2. Dantzig (1991).}

战争结束时，美国国防部向Dantzig提供了一个优越的职位，让他继续留在五角大楼。这份工作薪资丰厚，但限定了研究方向。国防部的Dal Hitchcock和Marshall Wood指明要他实现军队规划流程的机械化。Dantzig素来直面挑战，这次也不例外。他迎难而上，发明了一种规划理论。这种理论称为线性规划（linear programming，简称LP），具有深远的意义。

5.1.1 线性规划

20世纪30年代，Wassily Leontief曾经创立一种经济模型，其中指明了生产过程的输入与输出之间的平衡。Dantzig对于线性规划的研究很大程度上受到了这一成果的影响。他提出对经济活动中的选择加以限制，把原来局限于生产平衡的思想拓展为一般理念。

图5-1　George Dantzig（Mukund Thapa供图）

在Dantzig的线性规划模型中有三大核心要素。第一，他的约束条件不限于相抵的等式，也可以包括不等式（inequality），用来限定一个量至少应该和另一个量一样大。这种新特色常常用来声明某物质的数量至少也应该是零，Dantzig请出疯帽匠帮他解释这一点。¹

^{1. Carroll, L. 1865. Alice's Adventures in Wonderland. Project Gutenberg Edition.}

三月兔诚心诚意地对爱丽丝劝道：“再多喝点儿茶吧。”

“我还一点儿都没喝呢，”爱丽丝不高兴地答道，“所以我没法再多喝点儿。”

“你是想说不能再少喝吧，”疯帽匠说，“因为要喝得比‘没有’多是很容易的。”

疯帽匠说得很对。有些物质的量只有取非负数²的值才有意义，比如爱丽丝喝下了多少茶，因此，如果用变量T代表她喝的茶的量，就要限制T至少为零，简单记为T≥0，其中≥是大于等于号，代表前面的数大于或等于后面的数。

^{2. 请注意“非负数”不同于“正数”，因为正数是严格大于0的数。}

线性规划的第二个核心要素就是对约束条件加以限制，要求它们都是线性的。William Safire曾在他的“论语言”（On Language）专栏上阐述他对“线性”一词的看法，“线性思维往往具有贬义，意思等同于‘缺乏想象力’或者‘过分逻辑化’，然而线性规划却力图处理系统各部分之间的持续相互作用。”³在Dantzig的理论里，他假定活动消耗的资源正比于活动的强度。如果爱丽丝喝一杯茶要放两块方糖，那么我们就认为她喝两杯茶时会放四块方糖，也就是说，活动强度加倍，则资源也应加倍。本例的表达式为S=2T，即S−2T=0，其中S是糖的量。你会发现S−2T=0是一条直线的方程，“线性”正是因此得名。

^{3. Safire, W. 1990. “On Language”. New York Times, February 11.}

模型用一组变量表示不同活动的强度和物质的数量，一般每个约束条件从这组变量中选取若干个相互加减，从而将它们组合在一起。所以如果在一个线性规划模型中有变量A～Z，那么可能有下面的约束条件：

A+B+C+D≥100

2E+8G−H=50

1.2Y−3.1X+40Z≥0

约束条件里不能出现变量之间的乘积，比如XY≥0，也不能出现根号之类花哨复杂的运算，尽管你可能想用它们。这条限制确实大大束缚了我们，但是从计算角度来看，线性规划模型正是靠这样的线性约束条件才能实现协同运作。

线性规划模型的第三大要素则是明确的目标，这为评估不同解的优劣提供了依据。Dantzig要求目标明确，从而迫使管理人员准确描述预期目的，他本人认为这一点是自己最大的实用成就之一。在指明目标时，我们假定活动的价值正比于其强度，因此要求目标函数是模型中各变量的线性表示，并在活动强度取尽所有可能值时求出目标函数的最大值或最小值。目标函数取得所求最值时，相应各变量的赋值就是线性模型的最优解。

线性规划的整体思路大致就是这样，但是这尚不足以解决Hitchcock和Wood提出的挑战。在建立问题模型之后如何给出其最优解？Dantzig还需要一种方法。这一次，他同样交上了答卷：单纯形算法（simplex algorithm）。这种计算方法吃进去的是数据，挤出来的是最优解。无论是一般应用还是专门解决TSP，单纯形算法都实在是太重要了，三言两语肯定讲不完，因此讨论就留到下一节再详细展开吧。

5.1.2 引入产品

前面介绍了许多概念和定义，因此现在举个简单的例子可能会有好处，这道小例题可以演示清楚这一切是如何组合作用的。产品是经济学家的心头最爱，我们也在模型中引入这一概念。为简便起见，假设只生产三种产品，分别称为产品A、产品B和产品C，它们的量也分别相应使用变量A、B、C表示。生产产品需要输入两种原料，这里假设它们是镍和钢，库存量分别为100磅（约45千克）和200磅（约91千克）。生产产品A需要消耗3磅镍和4磅钢，B需要3磅镍和2磅钢，C则需要1磅镍和8磅钢。

整个生产销售过程创造的总利润为10A+5B+15C，换言之，每单位产量的产品A盈利10美元，单位产量的B盈利5美元，单位产量的C则盈利15美元。试问，怎样安排三种产品的生产量，才能在不超出原料库存量的情况下赚到最多的钱？比如，假如我们集中生产最赚钱的产品，也就是C，那么产量到达25个单位时就把钢用完了，这样总利润就是375美元。不过线性规划可以告诉我们怎样才能赚得更多。这道题的线性规划模型如下所示，其中≤是小于等于号。

目标：10A+5B +15C取最大值

约束条件：

3A+3B+1C≤100 （镍）

4A+2B+8C≤200 （钢）

A≥0,B?≥0, C≥0

第一个约束条件保证我们的生产方案有充足的镍原料，第二个则保证有充足的钢原料。

这个线性规划模型的最优解是生产30个单位的产品A和10个单位的C，完全不生产B，这样总利润是450美元。这个结果相当简单，就算不用单纯形算法也能解出来。但是实际的生产问题复杂得多，变量和约束条件的数目可以多达几十万，这种情况下你绝对不会靠心算求出答案。

5.1.3 线性的世界

1948年，在威斯康星大学的一场会议上，Dantzig公开了通用线性规划模型及其求解所用的单纯形算法。这是他人生的决定性时刻。后来，他对这场报告津津乐道，经常说起当时的情形。翻来覆去地讲同一个经典故事，便可能导致不少细节在岁月里变味，这段往事也不例外。不过所有的讲述版本都抓住了故事的精髓：在一大群德高望重的数学家和经济学家面前，他是个前途无量的年轻后生，而他内心却忐忑不安。¹在报告后的讨论环节，Harold Hotelling站起身来，只说了一句话：“可我们都知道世界不是线性的。”无论从学术水平还是从身材上看，他都算是重量级人物。面对这么狠的批评，Dantzig一下子无言以对。²

^{1. Cottle, R. W. 2006. Math. Program. 105, 1–8.}

^{2. Dantzig (1991).}

突然听众中又有一人举起了手，那是冯·诺依曼。他说：“主席，主席，如果报告者不介意的话，我愿意替他回答。”我当然求之不得。他接着说：“报告者把题目定为‘线性规划’，陈述原理的时候也很谨慎。你的应用要是满足他的原理，那就用他的模型；要是不满足，那就不用呗。”

这尽管是个复杂的世界，但是很幸运，线性模型确实可以详尽描述多数复杂之处。据Dantzig在斯坦福大学的同事表示，他的办公室外面挂了一幅漫画，生动地总结了Dantzig、Hetelling和冯•诺依曼的这段往事。³漫画主角是《花生漫画》（Peanuts）人物Linus（莱纳斯），他攥着小毯子，吮吸着大拇指，摆出他的经典造型。配图文字写道：“幸福就是假设世界是线性的。”⁴

^{3. Gill, P. E., et al. 2008. Discrete Optim. 5, 151–158.}

^{4. 这句话化用了漫画中的著名台词。原句为“Happiness Is A Warm Puppy”（幸福就是一只温暖的小狗），同时也是该系列第一本书的书名，小狗指的是《花生漫画》中的著名角色史努比。——译者注}

5.1.4 应用

Linear Programming and Extensions（《线性规划及其推广》）是George Dantzig的经典著作，开篇第一句话写道：“检验一个理论的终极标准是它解决原始背景问题的能力。”¹接下来是厚达600页的长篇大论，这真是开门见山。60年的实践已经反复证明，他的线性规划理论和相应的单纯形算法非常完满地通过了终极检验。

^{1. Dantzig (1963).}

线性规划在工业界用途极广，令人惊叹，你说得上来的任何部门几乎都有它的用武之地。显然，通过线性规划安排生产，每天能节省数不清的自然资源，不过没有办法量化。线性规划也能省钱，Gina Kolata在《纽约时报》上撰文指出：“解决工业上的线性规划问题，是涉及每年上百亿美元的大事业。”²Hotelling教授，这话您听见没？

^{2. Kolata, G. 1989. New York Times, March 12.}

至于如何用线性约束条件捕捉问题的实质，读者如果有兴趣了解，可以阅读Paul William的Model Building in Mathematical Programming（《数学规划中的建模》）³。这是一本好书，书里的例子有食品加工、精炼厂最优化、机票定价、种地、采矿、发电……五花八门，无所不包。

^{3. Williams, H. P. 1999. Model Building in Mathematical Programming. John Wiley & Sons, Chichester, UK.}