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 一些信息，無論是
在統計和算法匹配上都會得到優勢。
我原來也想獨立做其中的一項，不是很難，回報力應該比較高。但是可能沒有機會
和精力了。人的命運到底不是自己可以預測和掌握的。