Combinatorial Problems and Exercises
(http://www.amazon.com/xxxx/obidos/tg/detail/-/044481504X/qid=1100758938/sr=1-
2/ref=sr_1_2/103-7258716-7850206?v=glance&s=books)
，

这本书的作者LASZLO LOVASZ(http://research.microsoft.com/Users/lovasz/)是
1999年WOLF奖(http://www.aquanet.co.il/wolf/wolfpriz.html)的得主，好象在什
么地方除了介绍他对组合数学及图论的贡献，还特意提到了他这本书的影响。最近
MICROSOFT把他请去做搜索算法，要和GOOGLE竞争市场，(这里的媒体一致声讨MICROSOFT
的
贪婪和市场的独占性，但是MICROSOFT到底还知道如何组织人才、谁的份量如何-----象
牙塔里的精英比在学校里仅打过两年滚、被商业社会里造出来的“天才”对人类社
会的贡献大得多！)MICROSOFT的新闻发布特意提到他一天之内就提出了一个算法，
看来他的头脑仍然相当敏锐。

数学的本质不仅仅是严谨细致，更重要的是创造性的思维和想法，动态富有活力的
美在严谨的框架不仅不显得拘束，而更在现实应用和理论猜想中产生巨大威力。
组合和图论的特点是基础知识要求少，上手快，全凭聪明。对于数学训练和教育非
常适合。我看过一个朋友参加奥赛数学班的培训材料，和这本书
比较起来感觉是范围广泛一些，深度和专业化在组合和图论方面稍缺，但在训练的
目的上是一致的------即期许创造性地解决未经涉及的问题。

这本书在每一个专题前最精简地介绍一些充分的准备知识，题目的难度对读者提出
跳跃性的挑战，然而几乎每一题都有较为完备的提示和答案。大约花一两个学期因
人不等就可以做完。对于大多数不能独立解决问题的人即使咬牙读完题解也能做到
开卷有益。经过训练的人基本上具备了组合和图论和部分算法专业PHD课程的基础知
识，再经过读一些PAPER文献和指点就可以直接做毕业论文了。和奥赛班的那些材料
一样，很多题目高中生和本科底年级的学生都可以做。这对于那些望子成龙父母倒
是极好的消息。
(但不知道有没有中译本)

现在很多书都很厚，但大都内容属罗列堆砌，废话一箩。好象作者都假设读者都是
缺乏准备知识的笨蛋，或是在苦口婆心、深入浅出阐述给小学生听。但是在实际上
的效果是阻扰了其他人快速获取信息和知识。我感觉倒是二战以后刚到美国的那批
学者和他(她)们的学生的作品更为简洁精深和富余启发性。比如Emil Artin 写的迦
罗瓦理论的代数小册子和John Milnor
的拓朴，寥寥几笔就把关键问题讲清。大家们并不是把问题弄得玄之又玄，而是把
深刻的道理和微妙的变化谈得简单直观，把激动人心的发现序列有秩分享给大家，
使他人更快地弄清事情的本质和背景，能集中精力畅想而进深(人的精力毕竟有限)。

这本书很厚，所以很贵(一百八十几美刀)。然而，虽然说不上完全是字字矶珠，篇
篇精良，但却是作者逐渐厚积薄发的精华拣选由薄而厚的。有很多题目根本上是OPEN
PROBLEM。可以说这本书的寿命决不会是四、五十年可以结束的。

组合和图论应用很广，在电子线路板的设计、交通线路的规划、邮政分检和编码等看
似毫不相关的领域都有很好的运用。举个例子，现在石油和天然气等能源价格飞涨，
对许多国家和地区经济发展形成了瓶颈作用。除了人们致力于寻找新的能源资源和
有效替代品，发展新的技术(氢电池、油气混合燃料或煤炭液化)，对规划和调度算
法合理使用也可以大大地提高能源利用效率，从而减轻经济对能源的依赖。对于现
实生活的细致观察可以发现，区分车辆的种类加以不同的策略解决油耗问题更为有
效。比方说，家庭用车可以选用4缸或6缸车，对于SUV和8缸车这些MILE/GALLON数底
的车加以限产和限制进口。商业用车虽然数量少，但是每日的公里(MILE)数却大约
是民用车的5-15倍或更多。不能让这些车有很多乱跑和空跑的机会。对这些车辆也
还有更细的分类，短途运输车、出租车和长途运输车策略也不一样。路游问题是经
典的图论问题，在邮政投敌和收拣里有了很好的应用；最短路径问题也在公路设计
和分派中心的定位里发挥了作用。然而这并非问题的完结。不断有新的技术手段的
出现和改变问题的想法对于理论问题的条件和性质提出新的挑战。动态路游(Dynamic
Vehicle Routing) 就是一个例子。对于象WAL-MART，K-MART那样的在同一城市的小
范围DISTRIBUTION要求会很好满足。

考虑问题有不同的侧重，如果仅仅是为了省油，减少空载机会，可以在车辆卸载地
或临近地装载回车。当然，单一的策略不会很好解决问题，因为大多数节点的同一
物品(同一公司、或单位)入流量和出流量并不匹配。 进一步提问：为什么一定要有
同一的限制呢？大多数企业实体的SUPPLY CHAIN的要求只是在规定的时间范围内把
一定数量的货物以一定的价格运输到指定地点。那么，很多运输要求可以得到归并
统一解决，在实际中这一想法也得到部分应用，比如UPS和FEDEX之间就通过CONTRACT相
互利用对方的运载能力弥补自身的局限。如果尽可能扩大这种想法的实行，通过网
络把那些运输要求实时或预定信息地传送到调度中心，在调度和分配车辆的时候就
有更大的自由度。入流量和出流量并不匹配的困难还可以配合让车辆绕圈的办法而
减轻。更具自由的想法是人车分离，司机和运输车辆不一定总要在一起，职业司机
通过CONTRACT工作，到指定地点取车、运载和还车，这尤其在考虑到长途重型大油
耗车辆绕圈回原地的办法失灵的时候，根据不同成本折算的弥补办法。类似的想法
还有车和车厢分离等。

空想这些可能性相当吃力，当你手中没有数据的时候做分析，很多时候是在做无用
功。所以，统计抽样也是不可缺少的部分。有了统计数据，经过不同的分析角度，
比较精确地了解物流的流量、体积、分布、需求和瓶颈，不但可以较为现实地提出
优化的方案，发现一些新的模式(比如在大量动态需求里发现一些静态的固定需求)，
还可以对未来的需求和公路规划提出预测和建议。

在很多东西还很粗糙的情况下，却可以做一些模拟(SIMULATION)了。因为最终决策
的时候，一套灵活的软件和数据可以极为方便和经济的了解算法的适用性和性能，
以及改动的成本和带来的现实利益。这是最后说话的依据和实时调度工具的主干。

现在的议论市场经济里的人很多在谈供给性经济，在有了大量的生产能力下如何刺激
消费呢？很自然地想到，在消费者一方除了有充足的收入，还得有车，才能方便经
济地把较多的东西买回家。在供给方，物流的成本通过价格决定厂家的市场大小。
这一切都有能源的价格和有效利用率的成分。

在国外公路运输量占比重较大，可以这样粗略计算成本：一辆大型运载车的价格在
10万美元左右，有50万MILE的引擎数担保，实际可以跑60、70万MILE。就折算为$0。
2/MILE。柴油算$1。5/GALLLON。每GALLON可以跑10-14MILE。跑1MILE司机的$0。35-$0。
6(JBHUNTER)。那么跑一千MILE车损耗$200，油价约$110-$150，司机得$350-$600。
再加上其他一些因素和平权，算$1000吧。如果把$1000的价格打到每件物品上，在
这里的价格体系里对很多物品价格不算太大压力。(假设有10*10*10一千个小包裹，
每个包裹里有10-100间商品，每件商品价格为$1，单位商品的价格浮动%1-%10)。同
样的条件换到国内，考虑到司机工资底的和油的利用率底情况，算成$500。这似乎
更合算。但是，$1对国外工资收入不算什么，换成人民币后对经济的压力会更大。
同样还可以看到，价格的浮动率随车厢的长度线性递减，而油的MILE数/GALLON却不
是线性递增。这就是为什么烧柴油(马力大)的大型货运车适用于中长途运输而国内
跑得烧汽油的解放大卡不灵。

前两天看了一个WAL-MART的纪录片，里面说SAM WALTON 从五十年代创业以来，最早
成功的一招就是做了当时决大多数MBA不能做的一件事：跑到中国去买和订购廉价的
商品。这是钱给他的决定权的自由，当然
商业上的风险也使其他一些人默默无闻了。人们津津乐道地谈到WAL-MART这个零售
商如何压价控制供应商、它的仓储管理方式、信息交换方式以及市场和消费者心理
分析，总是忽略了美国庞大丰富的公路交通网，相对低廉的油价和较高的燃油利用
率。没有这些，WAL-MART的SUPPLY-CHAIN，WAREHOUSE和LOGISTICS再好，也是无处
凭力。
以前碰到一个印度人，好像在一家很有实力的进出口公司任主管，是芝加哥大学的
MBA，他跟我大谈他们的费里得曼和其他一些数学课。我就直接问他：你所学的这些
理论课在工作中到底用到多少？答案是几乎为零。现实生活就是这样，即便是名校
学经济和工业管理(ISYE)的毕业生，大多情况只是凭名头找个高薪工作，做一些指
定的事务性工作，即使有一些主意，涉及到大量投资的变革，也无权指手划脚。因
此，公路规划和交通调度是政府和巨大规模的实体的经济职能。

我在这里买了一条很好的KING SIZE的床罩，$10。后来降$8。我猜批发价大约$3-$5。
许多从中国来的商品的商品价格及底即使换成国内价也很有市场。一个有巨大生产
能力的国家却不能很好地打开国内市场而外向性经济比重过大，除了价格体系里的
问题，能源紧缺，和需求外汇以外，物流不能说没有问题。虽然学ISYE的人回国的
不少，但是很多问题却不是他们/她们能解决的。照办书本上的和别人的规范会省去
不少精力，但是具体情况、限制条件和变通办法还是要亲自做做HOMEWORK。需要有
人把具体要求及时通过合适的渠道打到合适的人选，给出迅速的解决方案。很多人
常常谈到国外投资回报率高，却给不出高的具体原因。同样的厂子搬过来，就有差
不多同样的生产效率，其他问题出在哪里呢？其实，每一个很小的细节如果涉及到
大批量的运作的时候，优化一点点都会带来很大效益。

我参观过Toys RUS 的WAREHOSE，里面从打包，到出货每一道工序都有数学计算，从
人的因数到机器的强度等都被细细研究。其他零售商和邮政机构的DISTRIBUION CENTER
和WAREHOUSE尽管行业不同，背后的数学应用却大同小异。图论，优化和统计无奇不
用，连TIME SERIAL 这样的东西都被用来计算包裹的流速！

如果有象GPS和电子追踪这些先进的工具，许多算法和想法会更便利地实行。国内头
痛的地方有很多，如高速公路线不发达，邮政编码在寻址上可用性不高(没有用好的
算法)，包装不规范，商品编码不统一，各种交通(公路运输、航运、铁路运输和水
运等)方式数据共享和透明性不高。即使这样，也有很多很土的变通方法，很多事已
经可以做起来了。因为至少有互联网，手机、无线呼叫，和条性码输入。无论是做
软件的，搭网的人，还是做算法和统计的人都有，国外很多同样的事都打到学校里
来让研究生做(AVIS 就曾到MIT 去找学生作算法)。有几个的因为做的较好，给UPS或
KMART等带来很大效益的提了工程院士的人也不是什么大数学家。在实际运用里成功
的人并不都是象费米那样知道撒一把碎纸屑就能推断出原子弹当量级的直觉的人。

即使在国外已经做得很好的情况下还有很多改进。比如，想MARTA这样的固定路线的
交通系统，随着时间和人口的变迁，路线改动了多少呢？即使路线不变的情况下，
如果知道不同季节或实时知道客流量，可以随机加派和选用油耗底的小巴更灵活地
满足需要。在有些富有社区，客流量少到一定数目的情况下，可以仅使用变动路线
的机车等。通过网络、手机、电话或更先进的手段，PRE-FETCH 一些信息，无论是
在统计和算法匹配上都会得到优势。
我原来也想独立做其中的一项，不是很难，回报力应该比较高。但是可能没有机会
和精力了。人的命运到底不是自己可以预测和掌握的。