運籌學如何入門? | 知乎問答精選

 

A-A+

運籌學如何入門?

2018年05月30日 知乎問答精選 暫無評論 閱讀 24 ℃ 次

【王一葦的回答(35票)】:

首先,請你不要一上來就對著書按著順序學

運籌學是一個子方向很多的學科,線性規劃,整數規劃,非線性規劃,隨機過程,隨機規劃,存儲量,博弈論,魯棒優化,最優控制。。。每一個方向裡面全是數學,有淺一點的,有很深的,一大堆符號,要都學,學很久,而且也會學得很痛苦,因為他們之間雖然有關係,但是關係不密切。剛開始,我覺得有必要知道這門學科的靈魂

-------------對不起,上一陣在忙proposal,我錯了,繼續寫------------

上面強調說不要一上來就去鑽,例如一上來就學最最基本的線性規劃,是因為如果這麼學,其實你學的是優化部分的應用數學,不是運籌學。運籌學不僅僅包括優化。優化只是理論部分。例如線性規劃是一種刻畫某些現實問題的模型,如果只關注於線性規劃本身,那其實有很大一部分是在關注線性規劃的數學理論。解線性規劃裡面的數學理論就多了去了:線性不等式的代表性,對偶理論,各種單純性法,橢圓法和各種內點法,現在還在發展。裡面每一個理論都不是隨便看看就能通的,特別對於數學基礎不算很好的同學而言。有些教授對裡面的數學還講一些high level的想法,但是國內教科書一般就直接上定義XXX,定理XXX,兩下就可以暈了。。。運籌學現在很受關注,很多社科和工科學生都在接觸,花太多時間在數學理論部分上,對他們而言挺可惜的。

關鍵是,對大多數人,裡面的數學壓根不需要學,我們有軟件解!有不少還是開源的!這個自己搜搜就好,其它回答也提到一些了。現在運籌學領域的專家們都給我們把各種解法自動化了,何必不好好利用,還自己慢慢理解算法?再慢慢編程?

所以如果只是入門,最重要是看看這一大堆運籌學裡面不同的理論都是幹什麼的,哪些模型好解,哪些難解,現在很多我們接觸到的模型都有定論的。

運籌學裡面其實更重要的是建模。換言之,就是看現實問題和數學語言是怎麼對應的。這個因為考試的原因,太容易被忽略了其重要性。

建模這事情說難不難說易不易。易在好像就是定義幾個變量,定義一下變量之間的關係和目標函數。難在

1. 對現實問題要看透:什麼才是問題裡面的最重要的因素,抓住重點

2. 找到最合適的數學語言和它對應,

3. 模型要盡量容易解

第一點是因問題而異的,沒法聊。第二點是可以通過瞭解各種模型適用於刻畫具有什麼結構的問題來達到。運籌學裡面有很多模型。舉幾個例子:

1. 線性規劃能表示所有有線性結構的問題,例如做採購,我們知道了每家供應商的固定價格和最大供應量,我們希望最小化成本,那總成本=單價×數量,這個就是這個問題裡面的線性關係。

2. 整數規劃能處理一些線性規劃處理不了的問題。例如還是採購,假如選了某家供應商,每選定一個供應商,還要增加一個固定成本,於是我們就要多設一個變量來代表是不是選了這個供應商,這時候就需要整數限制。不然那個變量解出來等於0.5,我們只選半個它?

3. 當現實問題涉及多個參與者,每個參與者都有自己優化的東西,這時候就涉及互動,就可以將博弈論派上用場了。

4. 如果見到一個系統是隨時間變化的,就可以考慮用最優控制。

等等等等。

懂了對自己身邊的具體問題建模,再拿個軟件解一下模型,對大部分人就夠了。所以要看書或者看視頻自學的話,第一步是,每一章只看前面講建模(modeling或者formulation)那一節。夠用了。

但是對於要更深入地去懂運籌學還不夠。

做得好的運籌學問題都是這樣的:

1. 深刻認識現實問題

2. 用數學語言描述問題(建模)

3. 用數學工具研究模型

4. 再把研究出來的成果從數學語言翻譯成我們能看懂的語言(例如漢語,英語。。。)

前面我們只聊到1,2和一點點3,真正的美出現在4。4的重要意義在於如果我們把一個問題解出來了,但是看不懂解出來的是什麼,那麼我們對這個問題其實是沒有增加多少認識的。有些時候還會導致其他問題,例如你在解決某個現實問題的時候,你把一個計算機解出來給你的解拿來用了,發現現實情況不像你想像中那樣,那怎麼辦?是計算機算解錯了嗎?還是你的模型沒建好嗎?如果有人給你投資做一個某些方面的優化系統,人家能信得過這樣靠建個模型解個解得出的方案嗎?大多數不懂你在做什麼的人是不會信的。所以好的解可以提供insight!(能讓人讀懂的現實含義)

例如Kelly Gambling,假如已知有n匹馬,他們勝率分別是b_i,跑第一的話投1塊錢能贏o_i塊錢,你總共有100塊錢(你可以當成一百萬,具體數目不重要,關鍵是比例),投到第i匹馬的錢是100p_i。假如你要買馬買無數次,那應該怎麼分配你的錢到各匹馬上去?這個問題的解就是p_i和b_i成比例。給我們的insight就是,獲勝幾率大的多放點錢,幾率小的少放點錢,就是這麼簡單。這個model的解給了我們分散投資的idea。

這是最簡單的情況,馬和馬之間是indepedent的,如果是投資股票,股票之間可能有相關性,如果這個相關性很重要,建模的時候就把它也考慮進去,得到考慮了相關性的解,再試圖去interpret你的解。如果相關性不太重要,就沒必要把模型搞複雜。

能得到給我們insight的解難嗎?當然難!

要想4出現,前面的1,2,3一定要簡潔而深刻。模型既能抓住問題的重點,還要足夠簡單,不然最後出來的結果怎麼可能讓人看得懂。這裡頭需要的可不僅是紮實的數學基礎,數學只是描述問題的一種語言,更重要的還是對具體問題的認識和對建出來的模型的預判。

對於一個現實問題,建立一個簡單好解又能較好地描述現實情況的模型,是一種藝術。這是數學界甚至科學界追求的美的原則:simple and elegant.

【常軼凡的回答(76票)】:

學運籌學之前,在知乎查過運籌學入門方面的問題,沒有得到想要的答案。現在過運籌學了,自己提問,自己回答。

涉及到專業入門書籍、資料的推薦,因為蘿蔔青菜各有所愛,難以保證所推薦的適合大多人。僅供參考。

說到運籌學入門書籍,似乎離不開 FrederickS. Hillier 和 Gerald J. Lieberman 的《Introduction to Operations Research》(Introduction to Operations Research (豆瓣)),在國內由清華大學的胡運權翻譯成《運籌學導論》(運籌學導論 (豆瓣)),但是只是截取了部分章節,重點選取了線性規劃的章節。這本書英文版網上有電子書,百度或者谷歌一下 「Introduction to Operations Research pdf 」就沒問題的。

我谷歌百度了一下運籌學入門書籍,無論是英文搜索還是中文搜索,大多都提到《運籌學導論》這本書,因此最開始是使用的這本書作為入門。另外,自己偏愛 Coursera,因此選了 Coursera 上科羅拉多大學波德分校開設的《線性和整數規劃》(Coursera.org)作為主要教學視頻。

一般而言,對於專業課,教材加教學視頻,外加不懂時谷歌搜索,就可以很好地自學了。

非常可惜的是,這本書和這個視頻都不適合用於入門,對於我。《運籌學導論》在學生還沒入門的時候講了太多運籌學的複雜運用,對於最基本的單純形法講解跳躍性太大,行文還不加介紹直接使用「超平面」、「凸集」等等概念,反覆看都難以理解。此書基本內容都難以理解,作者卻還同時介紹 MPL、LINGO、LINDO 編程,Excel解決線性規劃問題,如果能力沒有達到這樣水平,只會越學越沒有興趣。順帶提一句,如果中英文對照著看的人,會發現這本書翻譯瑕疵太多,部分地方直接影響閱讀(比如第九版第165頁將「Corner-Point Infeasible Solution」 翻譯成「角點可行解」)。

另外要補充說明,我在讀《運籌學導論》非單純形法介紹部分,即運輸問題、指派問題、整數規劃、動態規劃、決策分析的時候,覺得讀的很順,而且有實際運用的介紹,感覺學習非單純形法部分用這本書作為第一教材,確實合適。

再說說 Coursera 上的《線性和整數規劃》,此教學視頻最大的優勢在於有視頻教學和課後習題搭配,加之介紹了 Excel 和 Python 解決線性規劃問題,另外有 Python 代碼,有興趣的可以學習一下。不過課程由兩人講授,其中一人講得是印度口音英語,他還是主講,實在讓人難受。

下面進入正題,運籌學如何入門?

我最推薦的入門視頻:DrSalimian 的線性規劃系列視頻(資源地址:MOOCOR - Masud Salimian's Operations Research Course),講得非常基礎,而且十分清晰,基本上是 Step By Step的講解,為我掃清了好多好多的疑惑。跟著他把線性規劃的各個子內容(Simplex, Big-M Technique, Two-Phase Technique, Matrix Form Simplex, Revised Simplex, Duality)學好了,一步步跟下來是很簡單順暢,基本上Simplex就掌握了。

在學習 Simplex 的時候,DrSalimian的教程是主線,利用《運籌學導論》還有谷歌搜索作為補充。比如聽 Big-M 不太瞭解,就搜索 Big-M Method,然後看看其他大學放在網上的 pdf,這樣效果甚好。

學習完 Simplex 之後,《運籌學導論》就開始發揮作用了,這本書從第10章動態規劃開始,是可以作為第一教材。然後有不太理解的地方,用網上資料,以及 Youtube 上的視頻來補充。

---------------其他一些資源--------------

《LinearProgramming 1: Introduction》, George B. Dantzig, Mukund N. Thapa: 這本書是Simplex Method發明人Dantzig寫的,書,可以在一些問題不懂的時候參考,不過同樣不適合作為入門的第一教材。可能因為Dantzig是數學家,書中思維很嚴謹,很多Lemma,Theorem,Corrolary,以及證明和推倒。

TransportationProblems,一個小專題 pdf,幫我理解了運輸問題,把解法一步步講得很清楚,初始化階段介紹了三個方法:North-West, Russell, Vogel。

印度理工推出的系列視頻,從入門到進階十分詳細,對印度英語不熟悉的同學可能會聽著很難受,Salimian為我們整理了這一系列視頻:Masud Salimian's Operations Research Course。

【週一大馬麗的回答(5票)】:

樓上gatech的 @滴水兄對於運籌學最重要的技能「建模」的講解很贊。

======

一般運籌分兩塊:優化(optimization);概率+隨機(probability+stochastics)

以MIT開的課程為例。

先說優化:

強烈推薦教材《Introduction to Linear Optimization》by D. Bertsimas and J. Tsitsiklis. 這是MIT兩門研究生(博士和碩士)運籌學課程,15.081(6.251)和15.093,的教材。兩位作者都是MIT運籌學中心ORC的教授,其中D.Bersimas是目前ORC的co-director之一,美國工程院院士(運籌優化領域)。這本書講解非常詳細,讀起來比較愉快。

15.093資料鏈接:Optimization Methods

15.081資料鏈接:Introduction to Mathematical Programming

如果希望只是瞭解運籌學的基礎(即入門),15.093是比較合適的課程,覆蓋了線性規劃(modelling, simplex method, duality thoery, network problem)以及簡單的整數規劃,動態規劃和非線性規劃。這門課側重運用,要就是理解算法並且能運用到學術或者實際問題中;是COD項目的必修課。其他答案提到運輸問題,排班問題等都有涉及。這是給非運籌學專業或研究中不需要較深優化理論的學生開的課。這門課比較通俗易懂,老少咸宜。懂基本的線性代數就可以上。讀教材的話一般可以略過證明。

15.081是MIT運籌學博士一年級必修課。我的科研用到優化的理論,故即便不是運籌博士我也選了。這門課主要側重優化理論的搭建,對於定理的講解會深入許多,作業和考試均以證明為主。如果以後有志於做這方面的工作,可以學習這門課。這門課涵蓋的內容略少於15.093,但是深度比較大。如果本科數學基礎比較好(特別是代數)或者像我一樣有學習的必要性的,可以選這門課。這門課也是可以用來入門的,不過如果不是今後有必要,時間成本會比較大。

除了這兩門基礎課,還有較深入的整數規劃(15.083/6.859),網絡優化(15.082)以及近年來興起的魯棒優化(robust optimization,在確定性問題中引入隨機性,15.094)等。非線性優化(15.084)也是優化理論很重要的內容。

概率與隨機:

我主要不是這個領域的,所以選過的都不是以理論為核心的課。

理論課:15.085 Fundamentals of Probability; 以及其他advanced課程

偏應用的:1.203,6.262等等很多,內容主要是隨機過程,排隊論等。

歡迎補充

希望有所幫助。

【顏馨琪的回答(0票)】:

如果是比較習慣中文的教材的話這本書和配套的習題還是不錯的,研究生之前都沒有接觸過運籌學,這個是我們研究生的老師推薦的,仔細看看還是蠻有意思的,依照自己的興趣學習的時候不用給自己太大壓力,隨意一點如果是比較習慣中文的教材的話這本書和配套的習題還是不錯的,研究生之前都沒有接觸過運籌學,這個是我們研究生的老師推薦的,仔細看看還是蠻有意思的,依照自己的興趣學習的時候不用給自己太大壓力,隨意一點

裡面的一些知識點分的很清楚,講的也比較透徹

【知乎用戶的回答(1票)】:

推薦幾本書:

  • Optimization in Operations Research, by Ronald Rardin

  • Introduction to Linear Optimization, by D. Bertsimas and J.Tsitsiklis

  • Convex Optimization, by S. Boyd and L. Vandenberghe (Freeaccess online)

我覺得線性部分的話很多書都差不多,無非就是線性優化(單純型),網絡流之類的,弄懂算法,然後好好打打代碼就八九不離十了;

但對於非線性部分的話不同的書側重點會挺不一樣的,Boyd的那本書是最經典的非線性教材,他本人也是大神鼻祖型人物,數學背景不夠的話謹慎用他的Convex Optimization自虐。

還有一本中文的:最優化算法,袁亞湘。 他本人算國內運籌界第一人了,四十出頭已經是院士了,這本書更加注重計算證明,看起來也應該挺痛苦的。他當時在劍橋的導師也是優化界的鼻祖型人物Powell.

這部分有人更你講各種牛頓法啊、一維搜索啊、梯度下降法的算法什麼的會學起來快很多。開始的時候多注意算法的思想和一些性質,忽略掉證明和計算會輕鬆很多。然後多打代碼是王道。

一樓推薦的couresa的網絡課程好像不錯,也可以看看。

【LI二MAO的回答(1票)】:

樓上推薦的S Boyd的Convex Optimization非常有名,網上有相應的課程資料和視頻,搜索stanford + convex optimization就能找到。

如果想學習數學優化,同時推薦Jorge Nocedal和Stephen Wright的Numerical Optimization (Numerical Optimization (Springer Series in Operations Research and Financial Engineering): Jorge Nocedal, Stephen Wright: 9780387303031: Amazon.com: Books)

【週二的回答(0票)】:

學期中的時候想自學運籌學於是看到了這個帖子,現在也算是完整的看下了一本書,適當的分享一下自己的感受。

首先說明我的數學能力應該是比較差的,理解東西比較費勁。。。第一本隨手抓的書就是下面某用戶分享的 hamdy的那個,但是那本書我從一開始看的就一頭霧水,覺得很多東西講的不到點,有

一些東西根本連最簡單的證明都沒有,導致我大部分都看不懂,看到對偶那塊,終於放棄了。

然後我便開始了累計10小時的找教材時間,期間隨手抓過一本貌似是中科大出的書,也是看到對偶就看不下去了,我說了我的理解力很差 = = 。然後看的一本是胡運權自己寫的一本,大概是哈工程還是哈工大出版社的,我忘了,情況和上邊的差不多。

最後還是看了胡翻譯的那個運籌學導論,且不管他講的如何(我還沒有到那種能看出書有多好的境界),但是這本書我是從頭到尾看完了至少,所以我的結論是:::這本書還是不錯的!至少對數學比較差的人是這樣的。

關於題主說的視頻,有一個打不開我沒看,另一個印度口音的那個線性規劃的,開頭看了幾集,覺得講的有點簡單,有點拖拉就沒有繼續往下看,嗯,就這樣。

【知乎用戶的回答(0票)】:

請學好數學~

【知乎用戶的回答(0票)】:

運籌運籌,又暈又愁!!

這就是我上大學時候最大的感觸。。。。。

【wang思琪的回答(0票)】:

美帝本科第一個運籌課用的課本

Operations Research: An Introduction (9th Edition) Hamdy A. Taha

非常易懂的一本教材 網上找找能搜到PDF和答案 很有助於初期學習運籌

運籌學需要掌握很多數學知識才能充分理解的,我也是在這方面努力哈

Excel的運用也是很重要的,需要學怎麼用solver 來解線性和非線性問題。

標籤:-書籍推薦 -學習 -管理學 -運籌學


相關資源:





給我留言