點(diǎn)擊上方 關(guān)注我們

經(jīng)過前面的學(xué)習(xí)，相信大家已經(jīng)對運(yùn)籌學(xué)的目標(biāo)規(guī)劃有了更加全面的了解，接下來小編將帶你學(xué)習(xí)新一章的內(nèi)容，先來看看整數(shù)規(guī)劃的發(fā)展簡史，然后再帶你領(lǐng)略該理論先驅(qū)的傳奇一生！

引例

EQT能源（Eqt Corporation）總部位于賓夕法尼亞州匹茲堡，已有130余年的歷史，是美國最大的天然氣生產(chǎn)商。 EQT的主要業(yè)務(wù)包括頁巖地層勘探，天然氣開采，以及天然氣市場交付。頁巖氣是蘊(yùn)藏于頁巖層中的天然氣。過去十年內(nèi)，頁巖氣已成為美國一種日益重要的天然氣資源，同時也得到了全世界其他國家的廣泛關(guān)注。

然而頁巖氣井可產(chǎn)生不同質(zhì)量的天然氣。傳統(tǒng)上區(qū)分為干氣和濕氣。而生產(chǎn)商將天然氣輸送給客戶時，不同客戶對天然氣的組成和熱值（heating value）都有不同的要求，通常為一個區(qū)間。面對這些情況時，EQT通常需要做出以下決策：1）根據(jù)市場價格預(yù)測，選擇開采哪個頁巖氣井；2）何時并且如何混合干濕氣以滿足客戶需求；3）如何決定提純凈化產(chǎn)量。

EQT 公司為了提高運(yùn)營效率，節(jié)約生產(chǎn)成本，與位于卡內(nèi)基梅隆大學(xué)（CMU）的CAPD中心（Center for Advanced Process Decision-making）展開了長期合作。在2016年，由Markus G. Drouven（馬庫斯·德魯文）率領(lǐng)的EQT優(yōu)化工程團(tuán)隊(duì)通過建立混合整數(shù)規(guī)劃模型（Mixed-integer Programming）來規(guī)劃阿巴拉契亞盆地的頁巖氣開采、處理和輸送過程。最終，優(yōu)化后的凈現(xiàn)值達(dá)到了2.14億美元，而優(yōu)化前的凈現(xiàn)值只有8千萬美元。

一、整數(shù)規(guī)劃發(fā)展簡史

簡史

20世紀(jì)50年代，運(yùn)籌學(xué)創(chuàng)始人和單純形法發(fā)明者George Bernard Dantzig（喬治·伯納德·丹齊格）首先發(fā)現(xiàn)可以用變量來刻畫最優(yōu)化模型中的固定費(fèi)用、變量上界、半連續(xù)變量和非凸分片線性函數(shù)等。他對旅行售貨員問題（TSP）的研究成為后來分支定界法（branch and bound）和現(xiàn)代混合整數(shù)規(guī)劃算法的開端。

1958年IBM高級副總裁Ralph Gomory（拉爾夫·戈莫里）發(fā)表了題為《Outline of an algorithm for integer solutions to linear programs》的論文，介紹了使用單純形法求解整數(shù)規(guī)劃問題的割平面算法，奠定了整數(shù)規(guī)劃的理論基礎(chǔ)。因此，在整數(shù)規(guī)劃領(lǐng)域，1958年被視為具有開創(chuàng)意義的一年。

后來，丹齊格一沃爾夫分解算法（Dantzig-Wolfe）和列生成算法（Column Generation）的提出使一系列交通規(guī)劃調(diào)度和其他領(lǐng)域中的大規(guī)模整數(shù)規(guī)劃問題得以求解或近似求解，并在各種應(yīng)用軟件和系統(tǒng)中實(shí)現(xiàn)。

了解了整數(shù)規(guī)劃的簡史，想必讀者們對其奠基人充滿好奇，整數(shù)規(guī)劃的奠基人Gomory曾擔(dān)任 IBM Research 數(shù)學(xué)科學(xué)部主席、IBM 研究總監(jiān)、Alfred P. Sloan 基金會主席和紐約大學(xué) Leonard N. Stern 商學(xué)院研究教授。接下來，小編將對其進(jìn)行詳細(xì)介紹。

二、Gomory的一生

傳奇一生

?1929年5月7日出生于紐約布魯克林。

?1950年畢業(yè)于威廉姆斯學(xué)院。之后，在劍橋大學(xué)進(jìn)修了一年。

?1954年在普林斯頓大學(xué)獲得數(shù)學(xué)博士學(xué)位。

?1954-1957年作為一名軍官加入了美國海軍。

?1959年加入IBM新成立的研究部門，成為研究數(shù)學(xué)家。

?1964年被評選為IBM Fellow，這是科學(xué)家、工程師或程序員在公司所能獲得的最高榮譽(yù)。

?1970年被任命為研究總監(jiān)。

?1973年當(dāng)選IBM副總裁。

?1985年當(dāng)選IBM高級副總裁。

?1986年，當(dāng)選為美國國家工程院理事會和美國哲學(xué)學(xué)會理事會成員。

?1987年，成為外交關(guān)系委員會成員、哈佛大學(xué)應(yīng)用科學(xué)部訪問委員會主席、總統(tǒng)高溫超導(dǎo)咨詢委員會主席。

?1989年從IBM退休，成為艾爾弗雷德·斯隆基金會的總裁。

三、主要榮譽(yù)

榮譽(yù)

?1963年獲運(yùn)籌學(xué)學(xué)會蘭徹斯特獎

?1964年評為IBM院士

?1984年獲美國信息處理學(xué)會聯(lián)合會哈里·古德紀(jì)念獎和約翰·馮·諾依曼理論獎

?1985年獲工業(yè)研究學(xué)會獎?wù)?/p>

?1988年獲IEEE工程領(lǐng)導(dǎo)力認(rèn)可獎和國家科學(xué)獎?wù)?/p>

?1993年獲國家工程院的阿瑟·布科獎

?1998年獲亨氏技術(shù)、經(jīng)濟(jì)和就業(yè)年度獎

?1999年獲普林斯頓大學(xué)麥迪遜獎?wù)?/p>

?2000年獲耶魯大學(xué)工程學(xué)院謝菲爾德獎學(xué)金

?2005年入選國際運(yùn)籌學(xué)協(xié)會聯(lián)合會名人堂

?2006年獲運(yùn)籌學(xué)學(xué)會哈羅德·拉蘭德獎

?2021年獲范內(nèi)瓦·布什獎

? 在Gomory所獲榮譽(yù)中發(fā)現(xiàn)，運(yùn)籌學(xué)伴隨了其一生。那么接下來小編為大家分享Gomory與運(yùn)籌學(xué)的不解之緣。

四、Gomory與運(yùn)籌學(xué)的不解之緣

興趣初始

在Gomory的學(xué)生時代，他一直從事非線性微分方程的研究。在海軍服役期間，他第一次真正了解到了運(yùn)籌學(xué)，并對其產(chǎn)生了濃厚的興趣。在回到普林斯頓授課期間，Gomory在華盛頓參加了Alan H. Goldman教授（艾倫·戈德曼）的夜間課程，學(xué)習(xí)了線性規(guī)劃。與此同時，Gomory還在海軍運(yùn)籌學(xué)小組擔(dān)任顧問。在海軍運(yùn)籌學(xué)小組時，他遇到了一個問題，即使用線性規(guī)劃設(shè)計一支海軍特遣部隊(duì)。部隊(duì)中有一艘航空母艦時，必須同時配備驅(qū)逐艦及一些其他設(shè)施，所以海軍方面需要了解船只的數(shù)量以及它們能走多遠(yuǎn)。當(dāng)他們使用線性規(guī)劃來最小化工作組的成本和工作組的組成方式時，得出的答案是二又四分之一艘航空母艦。這個答案雖然的確是最優(yōu)解，但在現(xiàn)實(shí)問題中并非可行解。因此，戈莫里經(jīng)過不斷思考，最終研究出了Gomory割平面法，并花了一個月的時間證實(shí)了它的收斂性。

造紙廠問題

在IBM任職期間，Gomory還遇到了另一個問題——造紙廠制作出巨大的紙卷，但之后他們不得不把紙卷切成人們可以使用的大小，在這個過程中就難免會出現(xiàn)浪費(fèi)。這種情況可以被看作一個線性規(guī)劃問題，但減少浪費(fèi)的方法存在數(shù)億種。因此，線性規(guī)劃公式涉及數(shù)億列，人們無法將它們一一列舉出來，就更不用說在計算機(jī)上運(yùn)行了。所以Gomory與Paul Gilmore（保羅·吉爾摩）開發(fā)出了一種叫做列生成的算法，然后在計算機(jī)上實(shí)現(xiàn)。這種算法被發(fā)明出來后，被當(dāng)時的很多家造紙廠使用。同時，Gomory也在這個過程中獲得了大量的造紙數(shù)據(jù)。通過這些數(shù)據(jù)，Gomory和Paul發(fā)現(xiàn)一旦紙卷滾動到一定的寬度，它就會以某種方式重復(fù)，這種現(xiàn)象可以用群論來解釋。因此兩人基于這種現(xiàn)象，寫出了名為《Some?polyhedra related?to?combinatorial problems》的論文，并在學(xué)術(shù)上獲得了巨大的成功。

? 在了解Gomory之后，相信大家對整數(shù)規(guī)劃已經(jīng)有了豐富的興趣。為此，小編還為大家?guī)砹苏麛?shù)規(guī)劃領(lǐng)域其他的一些著名研究者。

五、整數(shù)規(guī)劃歷史人物拾零

分支定界法的創(chuàng)始人

? ? ? ??

? ? ? ??

total unimodularity（全幺模）概念提出者

????? ?

? ? ??

Dantzig-Wolfe（丹齊格一沃爾夫分解算法）提出者

George Bernard Dantzig

相信到這里，大家已經(jīng)了解了整數(shù)規(guī)劃的由來，敬請持續(xù)關(guān)注，接下來小編將帶你學(xué)習(xí)整數(shù)規(guī)劃的知識點(diǎn)~

資料來源：

https://www.informs.org/Explore/History-of-O.R.-Excellence/Biographical-Profiles/Gomory-Ralph-E

https://www.zhihu.com/question/303989306/answer/554835814

https://mp.weixin.qq.com/s/uoHo_E5DsopMNALbyT-tsw

孫小玲, 李端. 整數(shù)規(guī)劃新進(jìn)展[J]. 運(yùn)籌學(xué)學(xué)報, 2014, 18(1): 39-68.

END

作者 | 劉文志? ?林若唯

責(zé)編 | 劉文志

審核 | 徐小峰

?·YUNCHOUSHUO·?

· 知乎｜運(yùn)籌說 ·

· 簡書｜運(yùn)籌說 ·

· CSDN | 運(yùn)籌說 ·