運(yùn)籌說第34期丨運(yùn)輸問題發(fā)展應(yīng)用及領(lǐng)域風(fēng)云人物
一、運(yùn)輸問題發(fā)展簡史與應(yīng)用
發(fā)展簡史
#1941年，美國學(xué)者希奇柯克(Hitchcock)在研究生產(chǎn)組織和鐵路運(yùn)輸方面的線性規(guī)劃問題時(shí)提出運(yùn)輸問題的基本模型。
#從上世紀(jì)40年代早期開始，列奧尼德·康托羅維奇(Leonid V. Kantorovich)圍繞著運(yùn)輸問題作了大量的研究，因此運(yùn)輸問題又稱為希奇柯克問題或康脫洛維奇問題。
#1947年，柯普曼(Koopmans)獨(dú)立地提出運(yùn)輸問題并詳細(xì)地對此問題加以討論。
#1951年，丹齊格(George Bernard Dantzig)提出的單純形法作為求解運(yùn)輸問題的最初單純形方法(Primal Simplex Transpotation Method.PSTM)。
#1954年，亞伯拉罕·查恩斯(Abraham Charnes)與威廉·庫珀(William W. Cooper)發(fā)展了逐級算法(Stepping-Stone Method, SSM)，該算法提供了決定單純形方法信息的可選擇途徑。
運(yùn)輸問題應(yīng)用實(shí)例
運(yùn)輸問題是特殊的線性規(guī)劃問題，它是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個(gè)例子。運(yùn)輸問題不僅代表了物資合理調(diào)運(yùn)、車輛合理調(diào)度等問題，有些其他類型的問題經(jīng)過適當(dāng)變換后也可以歸結(jié)為運(yùn)輸問題。運(yùn)輸問題是極具實(shí)際意義的研究。
運(yùn)輸問題中最有名的一個(gè)實(shí)例是羅馬尼亞薪柴配送問題。當(dāng)時(shí)的研究條件相當(dāng)艱苦，整個(gè)羅馬尼亞只有一臺計(jì)算機(jī)和兩位程序員。在沒有計(jì)算機(jī)的幫助下，巴拉斯硬是和八名學(xué)生一起通過手算的方式，利用線性規(guī)劃技術(shù)成功解決了當(dāng)時(shí)羅馬尼亞交通領(lǐng)域的大難題——薪柴配送問題，為整個(gè)羅馬尼亞節(jié)約了8%的運(yùn)輸成本，這在當(dāng)時(shí)引起了極大轟動(dòng)。小有成就后，巴拉斯進(jìn)入了木材工業(yè)設(shè)計(jì)院工作，領(lǐng)導(dǎo)院里的線性規(guī)劃小組。
二、運(yùn)輸問題奠基人——列奧尼德·康托羅維奇
生平事跡
#1912年1月出生于俄國彼得堡。
#1926年考入列寧格勒大學(xué)數(shù)學(xué)系。
#1930年于列寧格勒大學(xué)畢業(yè)后留校從事教學(xué)工作。
#1934年升任列寧格勒大學(xué)教授。
#1935年蘇聯(lián)恢復(fù)學(xué)位制度時(shí)，他獲得博士學(xué)位。
#第二次世界大戰(zhàn)中，為服從衛(wèi)國戰(zhàn)爭的需要，他擔(dān)任海軍工程學(xué)院教授。
#1944年又回到列寧格勒大學(xué)任教。
#1945～1960年任蘇聯(lián)科學(xué)院數(shù)學(xué)研究所列寧格勒分所高級研究員、研究部主任。
#1960～1971年先后擔(dān)任新西伯利亞數(shù)學(xué)研究所副所長、所長。
#1971～1976年任莫斯科全國經(jīng)濟(jì)管理所研究室主任。
#1976年以后任蘇聯(lián)國家科學(xué)技委員會(huì)國民經(jīng)濟(jì)管理研究所經(jīng)濟(jì)問題研究室主任和國民經(jīng)濟(jì)最優(yōu)核算法委員會(huì)主席等職。
主要貢獻(xiàn)
資源最優(yōu)利用
康托羅維奇把資源最優(yōu)利用這一傳統(tǒng)的經(jīng)濟(jì)學(xué)問題，由定性研究和一般的定量分析推進(jìn)到現(xiàn)實(shí)計(jì)量階段，對現(xiàn)代經(jīng)濟(jì)應(yīng)用數(shù)學(xué)的重要分支——線性規(guī)劃方法的建立和發(fā)展，做出了開創(chuàng)性的貢獻(xiàn)。
解乘數(shù)法
在對現(xiàn)實(shí)經(jīng)濟(jì)學(xué)的思考中，康托羅維奇于1938年首次提出求解線性規(guī)劃問題的方法——解乘數(shù)法。這是對現(xiàn)代應(yīng)用數(shù)學(xué)的一個(gè)首創(chuàng)性貢獻(xiàn)。利用解乘數(shù)法求解線性規(guī)劃問題，具有廣而重要的應(yīng)用意義。他把這一方法推廣運(yùn)用于一系列實(shí)踐。在一些國家的數(shù)學(xué)和經(jīng)濟(jì)學(xué)書刊中，常把這類模型稱為“康托羅維奇問題數(shù)學(xué)模型”。
客觀制約估價(jià)
他在研究企業(yè)之間以及整個(gè)國民經(jīng)濟(jì)范圍內(nèi)如何運(yùn)用線性規(guī)劃方法時(shí)，提出的客觀制約估價(jià)，可以實(shí)現(xiàn)全社會(huì)范圍的資源最優(yōu)分配和利用。這時(shí)，在現(xiàn)有資源條件下，全社會(huì)能夠以最小的勞動(dòng)消耗，獲得最大限度的生產(chǎn)量。由此得出的生產(chǎn)計(jì)劃叫做最優(yōu)計(jì)劃。有時(shí)把客觀制約估價(jià)稱為最優(yōu)計(jì)劃價(jià)格。這是他革新、推廣和發(fā)展資源最優(yōu)利用理論的具體表現(xiàn)。
主要榮譽(yù)
#1949年，因在數(shù)學(xué)研究工作中的成就獲斯大林獎(jiǎng)金，同年獲蘇聯(lián)榮譽(yù)勛章
#1958年和1964年先后被選為蘇聯(lián)科學(xué)院通訊院士和院士
#1965年，因其在經(jīng)濟(jì)分析和計(jì)劃工作中應(yīng)用數(shù)學(xué)方法的成績而獲列寧獎(jiǎng)金
#1975年，獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)，成為第一個(gè)獲此殊榮的前蘇聯(lián)經(jīng)濟(jì)學(xué)家
#1949年、1950年、1975年先后三次獲勞動(dòng)紅旗勛章
?三、國內(nèi)運(yùn)輸問題奠基人——萬哲先與越民義
建國初期的努力
建國初期，全國工業(yè)與抗美援朝導(dǎo)致鐵路交通運(yùn)輸資源十分緊張，運(yùn)輸方案的制定越來越復(fù)雜，運(yùn)輸部門為了比較兩個(gè)方案，往往需要通宵達(dá)旦地計(jì)算。在大量實(shí)踐的基礎(chǔ)上，形成了一些經(jīng)驗(yàn)性的“圖上作業(yè)法"。萬哲先等人專門去運(yùn)輸部門研究如何應(yīng)用和推廣線性規(guī)劃，萬哲先對"圖上作業(yè)法"給出了理論證明，并進(jìn)行了推廣應(yīng)用。另外，數(shù)學(xué)家越民義對國外提出的“表上作業(yè)法"也給了理論證明。
萬哲先
#1927年11月，萬哲先出生于山東淄川，原籍湖北沔陽（后稱仙桃）。
#1948年，畢業(yè)于清華大學(xué)數(shù)學(xué)系，獲得理學(xué)學(xué)士學(xué)位，并留校任助教。
#1950年，調(diào)入中國科學(xué)院系統(tǒng)科學(xué)研究所，歷任助理員、助理研究員、副研究員。同年在華羅庚教授指導(dǎo)下從事典型群的研究，并在1963年與華羅庚合著《典型群》一書 。
#1964年，出版《李代數(shù)》一書，該書于1975年在英國出版英譯本。
#1978年，晉升為研究員。
#1991年，當(dāng)選為中國科學(xué)院學(xué)部委員（院士），隸屬于數(shù)學(xué)物理學(xué)部。
主要榮譽(yù)
#1978 年，三次全國科技大會(huì)重大科技成果獎(jiǎng)
#1986年，中國科學(xué)院科技進(jìn)步一等獎(jiǎng)
#1987年，全國自然科學(xué)獎(jiǎng)三等獎(jiǎng)
#1995年，獲得第二屆華羅庚數(shù)學(xué)獎(jiǎng)
#1996年，光華科技成果獎(jiǎng)一等獎(jiǎng)
#1997年，中國科學(xué)院自然科學(xué)獎(jiǎng)一等獎(jiǎng)
越民義
求學(xué)歷程
1940年，越民義考入浙江大學(xué)數(shù)學(xué)系。當(dāng)時(shí)的浙江大學(xué)匯集了國內(nèi)許多著名學(xué)者，中國現(xiàn)代數(shù)學(xué)史上兩名大師級人物陳建功教授和蘇步青教授就在浙大任教。那時(shí)，抗日烽火燒遍了大半個(gè)中國，坐落在貴州湄潭秀麗的山水之間的浙江大學(xué)還算相對安定。越民義在浙江大學(xué)的4年里，在陳建功、蘇步青兩位大師的言傳身教下研讀了大量數(shù)學(xué)著作，為日后的工作打下了堅(jiān)實(shí)的基礎(chǔ)。
大學(xué)期間，和優(yōu)異的成績齊名的是越民義的任性，天資聰穎加上大師的厚愛使他不自覺地產(chǎn)生了少年人的自負(fù)，越民義對學(xué)校的規(guī)章制度很不在意，他認(rèn)為鍛煉身體不必拘泥于形式，于是便不去上體育課，結(jié)果被老師記為零分。按照學(xué)校的規(guī)定，4年大學(xué)讀完，越民義沒有拿到畢業(yè)證。第二年，他只好回浙江大學(xué)補(bǔ)考體育。經(jīng)過他再三要求，學(xué)校終于同意他在不進(jìn)行考前訓(xùn)練的情況下參加補(bǔ)考，但是考試的方式是：除了吃飯睡覺，連續(xù)游泳3天。越民義只好答應(yīng)，并且說到做到。當(dāng)然他終于拿到了遲到的畢業(yè)證。連續(xù)3天游泳，看似懲罰，卻包含著老師的苦心。此事錘煉了越民義的毅力，老師“成大事者是不能松散地對待生活中的任何事情的”的叮囑讓他受益終生。
主要貢獻(xiàn)
M/M/n排隊(duì)系統(tǒng)的瞬時(shí)性態(tài)概率分布
這些研究成果在以后為我國的應(yīng)用數(shù)學(xué)事業(yè)贏得了國際榮譽(yù)，1977年美國純粹數(shù)學(xué)和應(yīng)用數(shù)學(xué)家訪華代表團(tuán)在所出版的報(bào)告中對我國應(yīng)用數(shù)學(xué)領(lǐng)域的兩項(xiàng)成果作出高度評價(jià)，其中一項(xiàng)就是越民義領(lǐng)導(dǎo)的“排隊(duì)論”研究，報(bào)告中說：“中國的‘排隊(duì)論’研究十分迅速地進(jìn)行到這一領(lǐng)域的最前沿。”這一研究成果在1978年全國科學(xué)大會(huì)上獲得大會(huì)獎(jiǎng)，并獲得中科院重大成果獎(jiǎng)。
非線性最優(yōu)化的既約梯度法及收斂性
既約梯度法是非線性最優(yōu)化的一類經(jīng)典方法，具有重要的應(yīng)用價(jià)值，它最早由美國著名學(xué)者沃爾夫（Wolfe）于1962年提出，但是沃爾夫的方法不具備全局收斂性。1979年，越民義和韓繼業(yè)提出了新的既約梯度法，并在很弱的條件下證明了它具有全局收斂性以及其他重要性質(zhì)。這一成果解決了自問題提出以來將近20年尚未解決的既約梯度收斂性問題，被國外譽(yù)為“方法新奇”，是“首先解決了既約梯度法對非凸函數(shù)類的全局收斂性問題”。
裝箱問題“Multifit算法”猜想的證明
關(guān)于這一算法的近似度，1978年美國著名學(xué)者科夫曼（Coffman）和約翰遜等提出了一個(gè)著名的猜想：最小擴(kuò)張因子r=13/11。1990年，越民義終于證明了這一猜想。1991年越民義又用較簡短的篇幅巧妙地證明了關(guān)于FFD近似算法的性能比FFD（L）≤（11/9）OPT（L）+1。這一結(jié)果從整數(shù)角度已是最佳估計(jì)。越民義的成果被德國波恩大學(xué)離散數(shù)學(xué)研究所所長B.科泰（Korte）教授和奧地利運(yùn)籌學(xué)會(huì)主席R.E.布卡德（Burkard）譽(yù)為重要成果，受到國際上的廣泛重視。
—————————————————————————————————
作者 | 劉文志 張文雪 林若唯
責(zé)編 | 何洋洋
審核 | 徐小峰
