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