【文章內(nèi)容簡介】 濟(jì)學(xué)家康托洛維奇1938年到1939年，發(fā)表了一系列文章，其中《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》（1939年）是最主要的著作。這部著作產(chǎn)生的實際背景是當(dāng)時蘇聯(lián)正處在第三個五年計劃時期。在完成這個這個任務(wù)時，蘇共中央提出“要廣泛的開展運用最新技術(shù)及科學(xué)的生產(chǎn)組織的工作”，而康托洛維奇正好碰到了屬于生產(chǎn)組織的一系列問題，列如最好地給機(jī)床或機(jī)器分配工作，盡量減少殘料，最好的利用原料、當(dāng)?shù)夭牧?、燃料及運輸能力等問題，而這些問題都可以歸結(jié)為同一極值問題，可是又不能用原有的數(shù)學(xué)方法求解。針對這一問題康托洛維奇提出“解乘子法”，在1940—1941年以及1948—1949年期間康托洛維奇的工作主要在兩個方面，一方面在應(yīng)用中有進(jìn)一步深化，列如下料問題在很多工廠實際應(yīng)用，并且在1951年寫了《工業(yè)材料合理下料計算》一書；另一方面，在計算方法及經(jīng)濟(jì)意義解釋上作了進(jìn)一步工作。值得指出的是，康托洛維奇1943年曾在莫斯科經(jīng)濟(jì)研究所工作過，解乘數(shù)后來發(fā)展成為客觀約束估值，賦予了很多經(jīng)濟(jì)意義，但遺憾的是，四十年代到五十年代美國獨立的，但飛快地發(fā)展出“線性規(guī)劃”這一分支，在蘇聯(lián)未受到重視，一直到五十年代末期，康托洛維奇才寫了一本更為完整的重要著作：《最佳資源利用的經(jīng)濟(jì)計算》（1960），后來康托洛維奇由此獲得了諾貝爾獎。 丹齊克和馮洛伊曼 丹齊克簡介美國數(shù)學(xué)家，美國全國科學(xué)院院士，線性規(guī)劃的奠基人。1914年11月8日生于美國俄勒岡州波特蘭市。在馬里蘭大學(xué)獲數(shù)學(xué)和物理學(xué)學(xué)士學(xué)位。在密歇根大學(xué)獲數(shù)學(xué)碩士學(xué)位。1946年在伯克利加利福尼亞大學(xué)數(shù)學(xué)系獲哲學(xué)博士學(xué)位。1974年丹齊克在總結(jié)前人工作的基礎(chǔ)上創(chuàng)立了線性規(guī)劃，確定了這一學(xué)科的范圍，并提出了解決線性規(guī)劃問題的單純形法。1937—1939年任美國勞工統(tǒng)計局統(tǒng)計員，1941—1952年任美國空軍司令部數(shù)學(xué)顧問、戰(zhàn)斗分析部和統(tǒng)計管理部主任。1952—1960年任美國蘭德公司數(shù)學(xué)研究員，1960—1966年任伯克利加利福尼亞大學(xué)教授和運籌學(xué)中心主任。1966年后任斯坦福大學(xué)運籌學(xué)和計算機(jī)科學(xué)教授。1971年當(dāng)選為美國全國科學(xué)院院士。1975年獲美國科學(xué)獎?wù)潞椭Z伊曼理論獎金。丹齊克還獲馬里蘭大學(xué)、耶魯大學(xué)、瑞典林雪平大學(xué)的以色列理工學(xué)院的名譽(yù)博士學(xué)位。丹齊克是美國運籌學(xué)會和國際運籌學(xué)會聯(lián)合會 （IFORS）的主席和美國數(shù)學(xué)規(guī)劃學(xué)會的創(chuàng)始人。他發(fā)表過100多篇關(guān)于數(shù)學(xué)規(guī)劃及其應(yīng)用方面的論文，1963年出版專著《線性規(guī)劃及其范圍》，這本著作至今仍是線性規(guī)劃方面的標(biāo)準(zhǔn)參考書。 馮洛伊曼簡介（馮諾依曼）馮諾依曼（John von Neumann，19031957），20世紀(jì)最重要的數(shù)學(xué)家之一，在現(xiàn)代計算機(jī)、博弈論、核武器和生化武器等諸多領(lǐng)域內(nèi)有杰出建樹的最偉大的科學(xué)全才之一，被后人稱為“計算機(jī)之父”和“博弈論之父”[[]諾曼麥克雷 范秀華 朱朝暉．天才的拓荒者——馮諾依曼傳，上海科技教育出版社，2008.]。原籍匈牙利。布達(dá)佩斯大學(xué)數(shù)學(xué)博士。先后執(zhí)教于柏林大學(xué)和漢堡大學(xué)。1930年前往美國，后入美國籍。歷任普林斯頓大學(xué)、普林斯頓高級研究所教授，美國原子能委員會會員。美國全國科學(xué)院院士。早期以算子理論、共振論、量子理論、集合論等方面的研究聞名，開創(chuàng)了馮諾依曼代數(shù)。第二次世界大戰(zhàn)期間為第一顆原子彈的研制作出了貢獻(xiàn)。為研制電子數(shù)字計算機(jī)提供了基礎(chǔ)性的方案。1944年與摩根斯特恩（Oskar Morgenstern）合著《博弈論與經(jīng)濟(jì)行為》，是博弈論學(xué)科的奠基性著作。晚年，研究自動機(jī)理論，著有對人腦和計算機(jī)系統(tǒng)進(jìn)行精確分析的著作《計算機(jī)與人腦》。 丹齊克和馮洛伊曼的相識提出“線性規(guī)劃”是在1947年，當(dāng)時與美國的空軍軍事規(guī)劃有關(guān)，在第二次世界大戰(zhàn)期間，英國和美國的軍事小組遇到了廣泛的與軍事有關(guān)的各種各樣的線性規(guī)劃問題。（當(dāng)時并不這樣認(rèn)為）二次世界大戰(zhàn)后不久，美國空軍召集一批科學(xué)家研究把數(shù)學(xué)技術(shù)運用到軍事規(guī)劃的預(yù)算和計劃中去的可能性。廣泛的軍事后勤問題受到重視。喬治丹齊格就是這個研究小組的成員，他最早提出一個大組織的活動之間的相互關(guān)系，可以看做一個線性規(guī)劃的模型。而最優(yōu)規(guī)劃是根據(jù)將一個線性目標(biāo)函數(shù)（單目標(biāo)）最小化來確定的。這個觀點導(dǎo)致了美國空軍組織一個研究小組的產(chǎn)生。命名為SCOOP（scientific Computation of optimum Programs最優(yōu)規(guī)劃的科學(xué)計算）。SOOP計劃開始于1947年6月，同年夏末，丹齊克和他的同事們建立了線性規(guī)劃的一般模型，很可惜，當(dāng)時沒有現(xiàn)成的解法，于是丹齊克自己研究找到了一種解法，由于這種解法中用了特殊的幾何空間形式，這種幾何空間的維數(shù)同規(guī)劃問題中列的維數(shù)一致，而不是同行的維數(shù)，這種幾何形式即為單純形。對于這種單純形為背景的方法，后來即稱為單純形算法，但是開始對它的威力以及進(jìn)一步的理論基礎(chǔ)并不是一下子認(rèn)識的很清楚。丹齊克帶著這個解法拜訪了當(dāng)時的大數(shù)學(xué)家馮洛伊曼，他講了不到一分鐘，而洛伊曼接著講了一個半小時，其中講到了線性規(guī)劃的數(shù)學(xué)理論。事實上前不久，洛伊曼正好寫了一本《競賽論與經(jīng)濟(jì)行為》，里面提到的基本理論正好和線性規(guī)劃的基本理論是等價的。洛伊曼還答應(yīng)進(jìn)一步考慮別的解法，后來果然提出了一種新解法。1952年單純形法和Motgkin 的方法由Hoham 在美國國家標(biāo)準(zhǔn)局里試用過，結(jié)果表明還是單純形法最好[[] 李銀興. 線性規(guī)劃發(fā)展的幾個時期[J]. 寶雞文理學(xué)院學(xué)報:自然科學(xué)版, 1993(2):6872.]。然而，如果我們仔細(xì)觀察很容易發(fā)現(xiàn)馮洛伊曼的《博弈論與經(jīng)濟(jì)行為》中的博弈論和經(jīng)濟(jì)均衡理論均與線性規(guī)劃的對偶模型有緊密的聯(lián)系。馮洛伊曼的著名極小極大定理和經(jīng)濟(jì)均衡理論中的鞍點和公式就是丹齊克線性規(guī)劃理論中的對偶規(guī)劃模型的前身。這就是馮洛伊曼對線性規(guī)劃的貢獻(xiàn)。馮洛伊曼對數(shù)學(xué)規(guī)劃的另一個貢獻(xiàn)就是證明線性不等式的“選擇矩陣定理”。這個著名的定理證明將極大極小定理、經(jīng)濟(jì)均衡理論和輸入輸出模型聯(lián)系起來了。第2章 單純形法的提出與發(fā)展 圖解法線性規(guī)劃可以在一定條件下合理安排人力、 物力等資源，使經(jīng)濟(jì)效果達(dá)到最好。一般來說，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變量、 約束條件、 目標(biāo)函數(shù)是線性規(guī)劃的三要素。然而圖解法不適合解大規(guī)模的線性規(guī)劃的問題，局限性比較大。但對于只有兩個或者三個變量的線性規(guī)劃問題，可以用圖解法求最優(yōu)解，也就是作出約束條件的可行域，利用圖解的方法求出最優(yōu)解，其特點是過程簡潔、圖形清晰，簡單易懂。下面僅做只有兩個變量的線性規(guī)劃問題。只含兩個變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解，步驟如下：（1）以變量x1為橫坐標(biāo)軸，x2為縱坐標(biāo)軸，適當(dāng)選取單位坐標(biāo)長度建立平面坐標(biāo)直角坐標(biāo)系。由變量的非負(fù)性約束性可知，滿足該約束條件的解均在第一象限內(nèi)。（2）圖示約束條件，找出可行域（所有約束條件共同構(gòu)成的圖形）。（3）畫出目標(biāo)函數(shù)等值線，并確定函數(shù)增大（或減?。┑姆较?。（4）可行域中使目標(biāo)函數(shù)達(dá)到最優(yōu)的點即為最優(yōu)解。下面舉出一個實例來說明：例1．某木器廠生產(chǎn)圓桌和衣柜兩種產(chǎn)品，現(xiàn)有兩種木料，第一種有72，第二種有56，假設(shè)生產(chǎn)每種產(chǎn)品都需要用兩種木料，生產(chǎn)一張圓桌和一個衣柜分別所需木料如下表所示。每生產(chǎn)一張圓桌可獲利60元，生產(chǎn)一個衣柜可獲利100元。木器廠在現(xiàn)有木料條件下，圓桌和衣柜各生產(chǎn)多少，才使獲得利潤最多?產(chǎn) 品木料（單位）第 一 種第 二 種圓 桌衣 柜解：設(shè)生產(chǎn)圓桌張，生產(chǎn)衣柜個，利潤總額為元，則由已知條件得到的線性規(guī)劃模型為： ， 72， 這是二維線性規(guī)劃，可用圖解法解，如圖21。圖21先在坐標(biāo)平面上作出滿足約束條件的平面區(qū)域，即可行域，如上圖所示。再作直線，即，把直線平移至的位置時，直線經(jīng)過可行域上點，且與原點距離最遠(yuǎn)，此時取最大值，為了得到M點坐標(biāo)解方程組，得？？？？？？？？？？？？？、于是知點坐標(biāo)為（350，100），從而得到使利潤總額最大的生產(chǎn)計劃，即生產(chǎn)圓桌350張，生產(chǎn)衣柜100個，能使利潤總額達(dá)到最大值31000元。這表明，當(dāng)資源數(shù)量已知，經(jīng)過合理制定生產(chǎn)計劃，可使效益最好，這就是用圖解法解線性規(guī)劃來解決生產(chǎn)計劃安排的問題之一。 單純形算法的發(fā)展 丹齊格的單純形法開始時曾做一個假設(shè)非退化，當(dāng)時他認(rèn)為這是合理的，因為三維空間中四個平面交于一點的概率為零，另外他所遇到的實例也確實沒有發(fā)生過，但是科普曼斯還是希望他進(jìn)一步做些工作，以后他和他的工作者曾提出用對右端項做攝動的辦法，并用字典序方法等采用了避免退化的程序，在實際求解中是否要加上解決退化的程序，至今還有爭論，到1981年發(fā)現(xiàn)即使退化現(xiàn)象不產(chǎn)生，接近退化的概率的仍然很大，這就提示我們在選擇轉(zhuǎn)軸元素的準(zhǔn)則時，應(yīng)該避免退化或接近退化的基本可行解的方向，去尋找可行解，這樣可以減少總的迭代次數(shù)。 從單純形法問世到現(xiàn)在已有很長的歷史，盡管中間有種種修改，但始終是解線性規(guī)劃問題的重要方法。雖然也提出過種種方法，大多數(shù)不如單純形法有效，除過針對一些特殊情況而設(shè)計的算法。 單純形算法給定一個線性規(guī)劃問題（P）： （P） 定義可行解集合：，則下述兩定理成立：定理1：若，則F至少含有一個頂點。定理2：若，而且（P）的最優(yōu)解值不為無限大，那么F至少有一個頂點會是（P）的最優(yōu)解。值得注意的是一般而言，時，它可能為一個有界的多面體，也可能是一個無界的多面集合。但是不論無界還是有界，F(xiàn)都是一個含有有限個頂點的凸集合。至于定理2則指出當(dāng)線性規(guī)劃問題有解時，它的最優(yōu)解可能朝著無界的極值方向發(fā)生而使得最優(yōu)解值變得無限小。如果不是這種情況，那么F的某個頂點一定會是最優(yōu)解之一。根據(jù)定理1和定理2，我們知道當(dāng)時而且（P）的最優(yōu)解值不為負(fù)無限大時，F(xiàn)雖然可能含有非頂點的最優(yōu)解，但至少有一個頂點是最優(yōu)解之一。單形法的基本概念很簡單明了，既然是一個線性規(guī)劃的最優(yōu)解可能出現(xiàn)在F的一個頂點之上，那我們就由某一個容易求得的頂點開始，再檢查所有在F中與它相連接的鄰近頂點。如果有任何一個鄰近頂點的函數(shù)值要求來得更小，那么我們便移動到這個鄰近頂點。接著便以此新的頂點為準(zhǔn)再檢查與它相連接的鄰近頂點來決定向何處移動。因為F的頂點個數(shù)個數(shù)有限，最后我們終于會找到一個頂點使他的函數(shù)值要比所有鄰近頂點都來得低或至少相當(dāng)，或者我們可以發(fā)現(xiàn)到此頂點有一個極值方向會使函數(shù)值降到無限小。據(jù)此便可以判斷出現(xiàn)有的頂點為（P）的最優(yōu)解或者（P）的最優(yōu)解值為無限大。我們可以將單行法的重要步驟勾勒如下：步驟一：找一個F的頂點，使得。如果找不到，則表示而且（P）無解。設(shè)定指標(biāo)k=1。步驟二：決定由現(xiàn)有頂點通往鄰近頂點或極值的各個方向。（i）方向走，均會增加目標(biāo)函數(shù)值，則已是（P）的最優(yōu)解。（ii）若沿著某一個方向走，會減少目標(biāo)函數(shù)值，則做下一步驟。步驟三：測試沿著方向走能遠(yuǎn)而不離開（F）（亦即步長）。（i）若步長可為無限大，則通往極值方向，而且（P）的最優(yōu)解值為負(fù)無限大。（ii）若步長有其上限，則沿通往較之鄰近頂點：重新設(shè)定指標(biāo)，轉(zhuǎn)步驟二。 上述的三個步驟僅是個概述，至于細(xì)節(jié)則需要參考其他資料。一般而言，步驟一中常用[BigM]法或者[TwoPhase]法來找第一個頂點。步驟二中的可能移動方向則由所謂的基矩陣（Fundamental Matrix）來決定。至于步驟三中的步長則由最小比例測試（Minimum Ratio Test）來決定。由圖22可以看出“單純行法”沿著可行解集合F的邊界由一個頂點移動到另一個頂點的情形，也就是因為這個原因，單純形法被歸類于“邊界鄰近法”。圖22 單純行法搜索路徑Fig 整體而言，單形法的表現(xiàn)相當(dāng)不錯。對于一個有個變數(shù)以及個約束條件的線性規(guī)劃問題，平均起來，單形法只需要移動經(jīng)過大約這么多個頂點，便能求得最優(yōu)解。但是GMinty和VKlee 兩位學(xué)者在1971年提出實例來驗證單形法在最差情況下的表現(xiàn)非常不好，對于一個維空間里的特殊線性規(guī)劃問題，單形法要移動經(jīng)過個頂點才能達(dá)到最優(yōu)解。因為這個數(shù)目隨著的增長而做指數(shù)形式成長，所以成長速度非?？欤脝渭冃畏▉斫鉀Q超大型的線性規(guī)劃問題確實有值得考慮的地方。大家可以想象便知道有多大。也就是因為這個隱患，所以學(xué)者專家們一直希望能找出一個解法不需要經(jīng)過那么多次計算便能達(dá)到最優(yōu)解。最好是隨著與的增長，總共的計算量僅做多項式函數(shù)的增加，而非指數(shù)式增加。這也就是一般所謂在“多項式時間”（polynomialtime）內(nèi)解線性規(guī)劃問題。 丹齊克的單純形法的運輸問題的應(yīng)用幾年前美國空軍在Leontief的工作下，使其適用于高度動態(tài)的情況下，Hitchoeck和Koopmans提出了是一個有趣的特殊情況：由個源點開始運輸一種貨物到n個收貨點，其中第i個源點貨物供應(yīng)量為個單位（i=1，2，……，m），第j個目的點需要量為個單位（j=1，2，……，n），且有，0。從i點運往j點的運輸成本為，問題為確定從源點運至目的點的運輸方案要使得總運輸成本為最小。如表23：表23很明顯在表23中，必須滿足以下的基本關(guān)系 關(guān)注最小化（或最大）線性規(guī)劃問題的非負(fù)變量的一個線性方程組的線性不等式。通常在實踐中遇到這個問題在上面的標(biāo)準(zhǔn)中，即，最小化線性形式的非負(fù)線性等式的一個方程組。 線性規(guī)劃的理論研究 線性規(guī)劃問題及單純形法提出后，大量的關(guān)于它們的理論和算法研究涌現(xiàn)。 對偶單純形法1954年美國數(shù)學(xué)家萊姆基提出對偶單純形法[[] ]。單純形法是從原始問題的一個可行解通過迭代轉(zhuǎn)到另一個可行解，直到檢驗數(shù)滿足最優(yōu)性條件為止。對偶單純形法則是從滿足對偶可行性條件出發(fā)通過迭代逐步搜索原始問題的最優(yōu)解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。