第0章最優(yōu)化理論與算法起因和發(fā)展

1最優(yōu)化理論與算法教師：唐明偉專(zhuān)業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)職稱：教授學(xué)位：工學(xué)博士聯(lián)系電話mail:tmw@歡迎同學(xué)咨詢與合作！2最優(yōu)化的發(fā)展歷程費(fèi)馬:1638皮耶·德·費(fèi)馬（PierredeFermat）是一個(gè)17世紀(jì)的法國(guó)律師，也是一位業(yè)余數(shù)學(xué)家。之所以稱業(yè)余，是由于皮耶·德·費(fèi)馬具有律師的全職工作。費(fèi)馬最后定理在中國(guó)習(xí)慣稱為費(fèi)馬大定理，西方數(shù)學(xué)界原名“最后”的意思是：其它猜想都證實(shí)了，這是最后一個(gè)。著名的數(shù)學(xué)史學(xué)家貝爾（E.T.Bell）在20世紀(jì)初所撰寫(xiě)的著作中，稱皮耶·德·費(fèi)馬為”業(yè)余數(shù)學(xué)家之王“。貝爾深信，費(fèi)馬比皮耶·德·費(fèi)馬同時(shí)代的大多數(shù)專(zhuān)業(yè)數(shù)學(xué)家更有成就。3最優(yōu)化的發(fā)展歷程牛頓,1670他在1687年發(fā)表的論文《自然定律》里，對(duì)萬(wàn)有引力和三大運(yùn)動(dòng)定律進(jìn)行了描述。提出牛頓運(yùn)動(dòng)定律，發(fā)明了反射望遠(yuǎn)鏡和發(fā)展出微積分學(xué)。提出了“牛頓法”以趨近函數(shù)的零點(diǎn)和金本位制度4最優(yōu)化的發(fā)展歷程歐拉,1755Minf(x1x2···xn)

f(x)=0萊昂哈德·歐拉，瑞士數(shù)學(xué)家、自然科學(xué)家。1707年4月15日出生于瑞士的巴塞爾，1783年9月18日于俄國(guó)圣彼得堡去世。16歲獲得碩士學(xué)位。歐拉是18世紀(jì)數(shù)學(xué)界最杰出的人物之一，他不但為數(shù)學(xué)界作出貢獻(xiàn)，更把整個(gè)數(shù)學(xué)推至物理的領(lǐng)域。他是數(shù)學(xué)史上最多產(chǎn)的數(shù)學(xué)家，平均每年寫(xiě)出八百多頁(yè)的論文，還寫(xiě)了大量的力學(xué)、分析學(xué)、幾何學(xué)、變分法等的課本，《無(wú)窮小分析引論》、《微分學(xué)原理》、《積分學(xué)原理》等都成為數(shù)學(xué)界中的經(jīng)典著作。歐拉對(duì)數(shù)學(xué)的研究如此之廣泛，因此在許多數(shù)學(xué)的分支中也可經(jīng)常見(jiàn)到以他的名字命名的重要常數(shù)、公式和定理。[1]

此外歐拉還涉及建筑學(xué)、彈道學(xué)、航海學(xué)等領(lǐng)域。5歐拉，拉格朗日：無(wú)窮維問(wèn)題，變分學(xué)柯西：最早應(yīng)用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m-6-線性規(guī)劃發(fā)展的歷史法國(guó)數(shù)學(xué)家J.B.J.傅里葉(JosephFourier)和C.瓦萊－普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家Л.В.康托羅維奇(Kantorovich)在《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書(shū)中提出線性規(guī)劃問(wèn)題，也未引起重視。

TPSHUAI71930年代，康托諾維奇：線性規(guī)劃1940年代，丹齊格Dantzig：?jiǎn)渭冃畏椒?，馮.諾依曼：對(duì)策論1950年代，Bellman：動(dòng)態(tài)規(guī)劃，最優(yōu)性原理；

KKT條件；1960年代：Zoutendijk,Rosen,Carroll,etc.非線性規(guī)劃算法，Duffin，Zener等幾何規(guī)劃，Gomory，整數(shù)規(guī)劃,Dantzig等隨機(jī)規(guī)劃

60-70年代：Cook等復(fù)雜性理論，組合優(yōu)化迅速發(fā)展

電子計(jì)算機(jī)----------最優(yōu)化2006/08-8-線性規(guī)劃發(fā)展的歷史利奧尼德·康托洛維奇(L.V.Kantorovich,1912—1986)，蘇聯(lián)數(shù)學(xué)家，出生于俄國(guó)圣彼得堡的一個(gè)醫(yī)生家庭.1930年畢業(yè)于列寧格勒大學(xué),1934年成為該校最年輕的數(shù)學(xué)教授,1935年獲該校數(shù)學(xué)博士學(xué)位.1948—1960年任列寧格勒科學(xué)院數(shù)學(xué)所研究室主任,1958年當(dāng)選為蘇聯(lián)科學(xué)院通訊院士,并于1964年成為蘇聯(lián)科學(xué)院院士.-9-線性規(guī)劃發(fā)展的歷史1960—1971年任蘇聯(lián)科學(xué)院西伯利亞分院數(shù)學(xué)所副所長(zhǎng),1971—1976年任蘇聯(lián)國(guó)家科學(xué)技術(shù)委員會(huì)管理研究所室主任.1976年任蘇聯(lián)科學(xué)院系統(tǒng)分析所所長(zhǎng).他曾于1949年獲斯大林?jǐn)?shù)學(xué)獎(jiǎng),1965年獲列寧經(jīng)濟(jì)學(xué)獎(jiǎng).康托洛維奇對(duì)經(jīng)濟(jì)學(xué)的貢獻(xiàn)主要在于,他建立和發(fā)展了線性規(guī)劃方法,并運(yùn)用于經(jīng)濟(jì)分析,對(duì)現(xiàn)代經(jīng)濟(jì)應(yīng)用數(shù)學(xué)的重要分支——線性規(guī)劃方法的建立和發(fā)展做出了開(kāi)創(chuàng)性貢獻(xiàn).他把資源最優(yōu)利用這一傳統(tǒng)的經(jīng)濟(jì)學(xué)問(wèn)題,由定性研究和一般的定量分析推進(jìn)到現(xiàn)實(shí)計(jì)量階段,對(duì)于在企業(yè)范圍內(nèi)如何科學(xué)地組織生產(chǎn)和在國(guó)民經(jīng)濟(jì)范圍內(nèi)怎樣最優(yōu)地利用資源等問(wèn)題做出了獨(dú)創(chuàng)性的研究.康托洛維奇的主要著作包括:《生產(chǎn)組織和計(jì)劃中的數(shù)學(xué)方法》(1939年),《經(jīng)濟(jì)資源的最優(yōu)利用》(1959年),《經(jīng)濟(jì)最優(yōu)決策》(1972年,合著),《最優(yōu)規(guī)劃文集》(1976年)等.因在創(chuàng)建和發(fā)展線性規(guī)劃方法以及革新、推廣和發(fā)展資源最優(yōu)利用理論方面所做出的杰出貢獻(xiàn)，與美籍荷蘭經(jīng)濟(jì)學(xué)家?guī)烨×帧?kù)普曼斯(T.C.Koopmans,1910—1985)一起分享1975年度諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng).2006/08---第1章線性規(guī)劃----10-喬治·伯納德·丹齊格（Dantzig）（G.B.Dantzig，1914—2005），美國(guó)數(shù)學(xué)家.因創(chuàng)造了單純形法，被稱為“線性規(guī)劃之父”.他在去世之前擁有3個(gè)院士頭銜(國(guó)家科學(xué)院，國(guó)家工程院和美國(guó)科學(xué)院).1947年,美國(guó)數(shù)學(xué)家G.B.丹齊克提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問(wèn)題的通用方法──單純形法，為這門(mén)學(xué)科奠定了基礎(chǔ)。線性規(guī)劃發(fā)展的歷史2006/08---第1章線性規(guī)劃----11-中斷丹齊格的伯克利研究生學(xué)習(xí).他成了美國(guó)空軍管理部統(tǒng)計(jì)控制戰(zhàn)斗分析處主任，處理供應(yīng)鏈的補(bǔ)給和管理成千上百的人員和物資.線性規(guī)劃發(fā)展的歷史第二次世界大戰(zhàn)-12-據(jù)史料記載，到1945年,美軍總兵力達(dá)到1050萬(wàn)人二戰(zhàn)結(jié)束時(shí)，美國(guó)陸軍有89個(gè)師，600多萬(wàn)人；海軍有各型艦船10759艘，總噸位1382萬(wàn)噸，總兵力為385萬(wàn)，其中海軍陸戰(zhàn)隊(duì)50萬(wàn)人其軍事工業(yè)的規(guī)模已經(jīng)發(fā)展到可以年產(chǎn)飛機(jī)4萬(wàn)架,坦克2萬(wàn)輛的水平,二戰(zhàn)時(shí)美國(guó)共生產(chǎn)8萬(wàn)輛坦克,有進(jìn)4萬(wàn)輛是位于底特律的克萊斯特工廠生產(chǎn)的M4謝爾曼坦克.線性規(guī)劃發(fā)展的歷史第二次世界大戰(zhàn)美國(guó)兵力2006/08---第1章線性規(guī)劃----13-1946年，丹齊格獲得伯克利的博士學(xué)位，仍回到美國(guó)空軍管理部.丹齊格的上司伍德（M.Ｗo(hù)od）和希奇赫克（D.Hitchock）要他解決如何使計(jì)劃過(guò)程機(jī)械化的問(wèn)題.具體任務(wù)是：尋找一個(gè)方法能更快地計(jì)算出分時(shí)間段的調(diào)度、訓(xùn)練和后勤供給的方案.當(dāng)時(shí)計(jì)算這些問(wèn)題，都是依靠經(jīng)驗(yàn)總結(jié)出的優(yōu)先準(zhǔn)則，而不是當(dāng)成一個(gè)大系統(tǒng)來(lái)考慮，也沒(méi)有一個(gè)明確的目標(biāo)函數(shù).丹茲格深入研究了這個(gè)問(wèn)題以后，提出了目標(biāo)函數(shù)的概念，并提出了單純形求解方法(1947年).這個(gè)方法在線性規(guī)劃領(lǐng)域沿用多年，至今還在發(fā)揮作用.線性規(guī)劃發(fā)展的歷史第二次世界大戰(zhàn)后-14-1947年，美國(guó)數(shù)學(xué)家VonNeumann諾伊曼提出對(duì)偶理論,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。線性規(guī)劃發(fā)展的歷史-15-1951年美國(guó)經(jīng)濟(jì)學(xué)家T.C.庫(kù)普曼斯(Koopmans)把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對(duì)偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問(wèn)題，1956年A.塔克提出互補(bǔ)松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。

線性規(guī)劃發(fā)展的歷史-16-1971年，KLee和Murty提出一個(gè)例子，在這個(gè)例子中單純形法需要迭代2n-1步，說(shuō)明單純形算法不是一種好算法。1979年蘇聯(lián)數(shù)學(xué)家L.G.Khachian(哈奇揚(yáng))提出解線性規(guī)劃問(wèn)題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法。

線性規(guī)劃發(fā)展的歷史-17-1984年，美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡(Karmarkar)提出解線性規(guī)劃問(wèn)題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問(wèn)題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。線性規(guī)劃發(fā)展的歷史-18-1998年Smale（斯梅爾）提出21世紀(jì)數(shù)學(xué)的18個(gè)數(shù)學(xué)難題，其中線性規(guī)劃被列為第九個(gè)難題。1.Riemann假設(shè)2.Poincare猜想

（已經(jīng)完全解決）

4.多項(xiàng)式的整數(shù)零點(diǎn)

5.丟番圖曲線高度的界

6.天體力學(xué)中相對(duì)平衡態(tài)數(shù)目的有限性7.2維球面上點(diǎn)的分布8.把動(dòng)力學(xué)引進(jìn)經(jīng)濟(jì)理論中9.線性規(guī)劃問(wèn)題

10.封閉引理

11.一維動(dòng)力學(xué)是否通常是雙曲的12.微分同胚的中心化子

13.Hilbert第十六問(wèn)題14.Lorenz吸引子

15.Navier-Stokes方程16.Jocobi猜想17.解多項(xiàng)式方程組18.智能的極限。線性規(guī)劃發(fā)展的歷史19最優(yōu)化理論與算法起因和發(fā)展線性規(guī)劃主要有兩個(gè)方面的研究?jī)?nèi)容，一是規(guī)劃。二是計(jì)算方法。線性規(guī)劃的目標(biāo)函數(shù)和約束函數(shù)都是線性函數(shù)，線性規(guī)劃這個(gè)名稱也是由此而演變形成的。線性規(guī)劃研究者的主要目的在于如何制定計(jì)劃，而不在于執(zhí)行或?qū)嵤┯?jì)劃?？梢园堰@些有關(guān)學(xué)問(wèn)所形成的整個(gè)領(lǐng)域稱做＂規(guī)劃＂，在于著重強(qiáng)調(diào)極大化或極小化問(wèn)題時(shí)候，還可稱做最優(yōu)規(guī)劃。簡(jiǎn)單的說(shuō)，線性規(guī)劃所考慮的問(wèn)題是如何按照最佳可能的（最優(yōu)）方式來(lái)計(jì)劃一項(xiàng)各種相互關(guān)聯(lián)的活動(dòng)的集合體。單純形法是求解線性規(guī)劃問(wèn)題的方法之一。20線性規(guī)劃的起因主要由馮．諾伊曼的博弈論研究、一般經(jīng)濟(jì)均衡理論研究和線性不等式的發(fā)展研究，李昂鐵夫的投入－產(chǎn)出研究，希奇柯克的運(yùn)輸問(wèn)題研究和斯蒂格勒的營(yíng)養(yǎng)問(wèn)題研究等。線性規(guī)劃形成的主要標(biāo)志有兩個(gè)：一個(gè)是線性規(guī)劃模型的建立，另一個(gè)是創(chuàng)建求解線性規(guī)劃問(wèn)題的單純形法。線性規(guī)劃模型建立以后，線性規(guī)劃的發(fā)展主要體現(xiàn)在單純形法的發(fā)展上。最優(yōu)化理論與算法起因和發(fā)展21線性規(guī)劃的起因最優(yōu)化理論與算法起因和發(fā)展由馮．諾伊曼的博弈論研究一般經(jīng)濟(jì)均衡理論研究和線性不等式的發(fā)展研究李昂鐵夫的投入－產(chǎn)出研究希奇柯克的運(yùn)輸問(wèn)題研究斯蒂格勒的營(yíng)養(yǎng)問(wèn)題研究22單純形法是由丹齊格創(chuàng)建的，單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃的誕生。丹齊格曾經(jīng)說(shuō)：“如果我被要求說(shuō)出對(duì)線性規(guī)劃的最重要的貢獻(xiàn)，我會(huì)說(shuō)一下三點(diǎn)：１．認(rèn)識(shí)到（丹齊格作為戰(zhàn)爭(zhēng)年代的親身經(jīng)歷者和實(shí)際規(guī)劃的操作者所獲取的經(jīng)驗(yàn)）具體規(guī)劃中最實(shí)用的關(guān)系可用線性不等式系統(tǒng)來(lái)表示。２．使用目標(biāo)函數(shù)來(lái)明確規(guī)劃的目標(biāo)，而不是用該領(lǐng)域有權(quán)威的人士的經(jīng)驗(yàn)來(lái)選擇最優(yōu)方案。３．創(chuàng)造了求解線性規(guī)劃問(wèn)題的單純形方法。單純形法是在探討經(jīng)濟(jì)理論的一個(gè)有用方法的過(guò)程中產(chǎn)生的，是人們對(duì)大型復(fù)雜系統(tǒng)做出實(shí)際計(jì)劃的強(qiáng)大工具。最優(yōu)化理論與算法起因和發(fā)展23線性規(guī)劃和博弈論之間關(guān)系是由塔克教授的科研團(tuán)隊(duì)來(lái)研究完成，然而我們一直把博弈論和線性規(guī)劃的關(guān)系歸功于由馮．諾伊曼。一、博弈論研究是線性規(guī)劃的一個(gè)起因最優(yōu)化理論與算法起因和發(fā)展這是為什么呢？24在二次世界大戰(zhàn)期間，馮.諾伊曼軍事動(dòng)員和相關(guān)軍事科學(xué)的發(fā)展上發(fā)揮了顯著作用，戰(zhàn)后在軍內(nèi)他開(kāi)展了各種咨詢職位。1947年10月，丹齊格在普林斯頓高級(jí)研究所拜訪馮.諾伊曼時(shí)，線性規(guī)劃與博弈論么間的關(guān)聯(lián)被認(rèn)可［丹齊格，1982,1988]。一、博弈論研究是線性規(guī)劃的一個(gè)起因最優(yōu)化理論與算法起因和發(fā)展25在［丹齊格，1982］丹齊格中講述了他是如何想起這次會(huì)議，回味著馮.諾伊曼的話：“我［馮.諾伊曼］不想讓你［丹齊格］以為我像魔術(shù)師似得從袖子中拉出來(lái)這一切。我與奧斯卡.摩根斯坦最近剛剛完成了一本關(guān)于博弈論的書(shū)。我正做的事情是猜測(cè)這兩個(gè)問(wèn)題（線性規(guī)劃的對(duì)偶理論和博弈論的極大極小理論）是等價(jià)的。你概述的有關(guān)問(wèn)題的理論是我們開(kāi)發(fā)的模巧游戲?！币?、博弈論研究是線性規(guī)劃的一個(gè)起因最優(yōu)化理論與算法起因和發(fā)展26馮？諾伊曼還寫(xiě)了一個(gè)注釋?zhuān)藗兯较聜鏖啞?947年11月15－16日，標(biāo)題為“討論一個(gè)最大值的問(wèn)題”。1991年，關(guān)于送個(gè)紙條哈羅德.庫(kù)恩寫(xiě)道：“馮.諾伊曼私下傳閱的簡(jiǎn)短打印的注釋在15年后首次發(fā)表。該注釋說(shuō)明建立了線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，并給了一個(gè)最優(yōu)目標(biāo)價(jià)值觀為基礎(chǔ)的不均勻無(wú)效表單上的平等法卡斯引理有缺陷的證明。［庫(kù)恩，1991，第85頁(yè)］一、博弈論研究是線性規(guī)劃的一個(gè)起因最優(yōu)化理論與算法起因和發(fā)展271948年6月，丹齊格訪問(wèn)普林斯頓大學(xué)時(shí)，會(huì)見(jiàn)了Ａ．塔克教授。從此，塔克的團(tuán)隊(duì)（塔克及他的學(xué)生庫(kù)恩和戈?duì)柕龋╅_(kāi)始對(duì)博弈論、非線性規(guī)劃和對(duì)偶理論研究作了很多有歷史意義的工作。多年來(lái)，大家公認(rèn)馮.諾伊曼是對(duì)偶理論的創(chuàng)始人，然而戈?duì)?、?kù)恩和塔克則是最早發(fā)表對(duì)偶定理嚴(yán)格證明的人。所以（公正的講，對(duì)線性規(guī)劃對(duì)偶理論的建立過(guò)程中塔克教授團(tuán)隊(duì)的工作是有目共睹的，然而博弈論和線性規(guī)劃的關(guān)系方面首創(chuàng)性的工作依然屬于丹齊格和馮.諾伊曼。一、博弈論研究是線性規(guī)劃的一個(gè)起因最優(yōu)化理論與算法起因和發(fā)展28綜上博弈論對(duì)線性規(guī)劃問(wèn)題的最大的影響在于建立對(duì)線性規(guī)劃問(wèn)題及相關(guān)理論。一、博弈論研究是線性規(guī)劃的一個(gè)起因最優(yōu)化理論與算法起因和發(fā)展29丹齊格在美國(guó)勞工統(tǒng)計(jì)局工作時(shí)的同事，也是他的好友埃文斯將李昂鐵夫的一篇關(guān)于美國(guó)經(jīng)濟(jì)結(jié)構(gòu)的論文介紹給他。從此單齊格開(kāi)始研究李昂鐵夫的文章。丹齊格認(rèn)為：李昂鐵夫的成就在于他建立了定量模型，從而能夠從一系列錯(cuò)綜復(fù)雜的產(chǎn)業(yè)鏈關(guān)系中，衡量出國(guó)家政策和消費(fèi)趨勢(shì)對(duì)生產(chǎn)的影響。李昂鐵夫精確地使用＂經(jīng)驗(yàn)?zāi)Ｐ停⒏拍畲媪耍⒓兇庑问侥Ｐ停?。二、投入－產(chǎn)出間題研究是建立線性規(guī)劃模型的維形最優(yōu)化理論與算法起因和發(fā)展30李昂鐵夫在收集數(shù)據(jù)和推廣成果時(shí)顯示出非凡的組織活動(dòng)才能。所有這些都使得丹齊格對(duì)李昂鐵夫敬仰不己。他曾經(jīng)說(shuō)過(guò)：＂李昂鐵夫一人為應(yīng)用數(shù)學(xué)的創(chuàng)立創(chuàng)造了所有的必要條件。丹齊格被李昂鐵夫的工作（即被他稱之為＂國(guó)際投入－產(chǎn)出模型的美國(guó)經(jīng)濟(jì)＂）迷住了。李昂鐵夫已經(jīng)成功的應(yīng)用了必要的3個(gè)步驟：１．制定產(chǎn)業(yè)模式。２．在美國(guó)經(jīng)濟(jì)大蕭條期間收集輸入的數(shù)據(jù)。３．信服決策者使用輸出。二、投入－產(chǎn)出間題研巧是建立線性規(guī)劃模型的維形最優(yōu)化理論與算法起因和發(fā)展31二、投入－產(chǎn)出間題研巧是建立線性規(guī)劃模型的維形1973年，李昂鐵夫因投入－產(chǎn)出模型而獲得諾貝爾獎(jiǎng)。然而＂李昂鐵夫的模型是穩(wěn)態(tài)（靜態(tài)）的，我想要的高度動(dòng)態(tài)模型，隨著時(shí)間的推移而變化的模型，空軍希望得到一個(gè)高度動(dòng)態(tài)的模型，隨著事件發(fā)生變化的模型＂。對(duì)照李昂鐵夫和單齊格兩個(gè)人的工作很容易看出，是丹齊格推廣了李昂鐵夫的模型，并引進(jìn)了目標(biāo)函數(shù)。李昂鐵夫投入產(chǎn)出思想是第一個(gè)關(guān)于＂規(guī)劃＂思想，這個(gè)規(guī)劃思想就是單齊格線性規(guī)劃的模型中的線性約束條件的前身。當(dāng)然，更重要的是丹齊格創(chuàng)建了單純形法。最優(yōu)化理論與算法起因和發(fā)展32三、運(yùn)輸問(wèn)題是建立線性規(guī)劃問(wèn)題的典型例子希奇柯克的關(guān)于運(yùn)輸問(wèn)題的思想是送樣的：把一部分物資從凡個(gè)不同的地區(qū)往幾個(gè)不同的地區(qū)運(yùn)送，怎么安排才能運(yùn)送費(fèi)用最??？這里希奇柯克建立了一個(gè)運(yùn)輸問(wèn)題的模型，并給出一個(gè)求解方法。希奇柯克這個(gè)模型既有線性目標(biāo)函數(shù)又有線性約束條件，是最早建立的線性規(guī)劃模型。然而是一個(gè)靜態(tài)的模型，丹齊格建立的是動(dòng)態(tài)的線性規(guī)劃模型。希奇柯克這些思想無(wú)疑對(duì)丹齊格線性規(guī)劃思想的來(lái)源。最優(yōu)化理論與算法起因和發(fā)展33三、運(yùn)輸問(wèn)題是建立線性規(guī)劃問(wèn)題的典型例子丹齊格曾經(jīng)說(shuō)：“1941年希奇柯克寫(xiě)一篇關(guān)于交通問(wèn)題方面的優(yōu)秀論文……＂。與此同時(shí)，丹齊格最早應(yīng)用單純形法的具體問(wèn)題就是運(yùn)輸問(wèn)題。更值得一提的是單齊格第一次應(yīng)用單純性正是在希奇柯克提出的運(yùn)輸問(wèn)題中。最優(yōu)化理論與算法起因和發(fā)展34四、營(yíng)養(yǎng)問(wèn)題是第一個(gè)動(dòng)態(tài)模型斯蒂格勒營(yíng)養(yǎng)問(wèn)題的思想是怎樣花最少的成本獲取最大營(yíng)養(yǎng)。斯蒂格勒的工作是一個(gè)指導(dǎo)性的最低營(yíng)養(yǎng)成本的意見(jiàn)，這個(gè)意見(jiàn)做不到精確，也不可能精確。原因是同類(lèi)食物由于產(chǎn)地和生產(chǎn)時(shí)間的不同而其所含營(yíng)養(yǎng)成分也不同。既然同類(lèi)產(chǎn)品的營(yíng)養(yǎng)成分的不同將導(dǎo)致斯蒂格勒最佳營(yíng)養(yǎng)組合方案的誤差。但是這個(gè)方案在很大程度上能夠提供相當(dāng)科學(xué)的、保持身體健康的、最低成本的食物。最優(yōu)化理論與算法起因和發(fā)展35四、營(yíng)養(yǎng)問(wèn)題是第一個(gè)動(dòng)態(tài)模型斯蒂格勒的工作中雖然沒(méi)有解析式的線性約束和先行目標(biāo)函數(shù)，但是有明確的行動(dòng)目標(biāo)和實(shí)施方案。雖然在形式上跟線性規(guī)劃不同，但是內(nèi)涵上與線性規(guī)劃一致，是早期的線性規(guī)劃思想的體現(xiàn)。動(dòng)態(tài)的思想。斯蒂格勒的營(yíng)養(yǎng)問(wèn)題有明顯的目標(biāo)，然而不是代數(shù)形式的，是第一個(gè)動(dòng)態(tài)模型。斯蒂格勒動(dòng)態(tài)的思想是丹齊格動(dòng)態(tài)線性規(guī)劃需要借鑒的思想。最優(yōu)化理論與算法起因和發(fā)展36五、線性規(guī)劃的形成線性規(guī)劃主要有兩個(gè)方面的內(nèi)容：一是做出一個(gè)好的計(jì)劃，另一個(gè)是找到一個(gè)簡(jiǎn)捷有效的計(jì)算方法。線性規(guī)劃中規(guī)劃的意思就是要做好一個(gè)計(jì)劃，這里需要強(qiáng)調(diào)的是眾多學(xué)者的目標(biāo)在于如何制定計(jì)劃，而不在于如何執(zhí)行或?qū)嵤┯?jì)劃。人們把這些有關(guān)學(xué)問(wèn)所形成的整個(gè)領(lǐng)域成為“規(guī)劃”；進(jìn)一步著重考慮極大化或極小化問(wèn)題時(shí)用最優(yōu)規(guī)劃這個(gè)名稱。數(shù)學(xué)規(guī)劃所考慮的問(wèn)題是如何按照最好可能（最優(yōu)）的方式計(jì)劃一系列相互關(guān)聯(lián)的活動(dòng)的集合體。最優(yōu)化理論與算法起因和發(fā)展37五、線性規(guī)劃的形成從全文能夠看到，線性規(guī)劃研究主要做了兩個(gè)方面工作。一是線性規(guī)劃模型建立歷原因，二是求解線性規(guī)劃問(wèn)題的單純形法的創(chuàng)建與發(fā)展進(jìn)程。最優(yōu)化理論與算法起因和發(fā)展這個(gè)數(shù)學(xué)規(guī)劃的目標(biāo)函數(shù)和約束函數(shù)全部是線性函數(shù)時(shí)候稱這個(gè)規(guī)劃為線性規(guī)劃。對(duì)于求解線性規(guī)劃來(lái)說(shuō)，經(jīng)典的求最值方法是無(wú)能為力的，因此求解線性規(guī)劃問(wèn)題顯得非常重要。故求解線性規(guī)劃問(wèn)題的單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃的誕生。385.1、線性規(guī)劃模型的建立線性規(guī)劃模型的建立主要起因有幾個(gè)方面：一是線性不等的系統(tǒng)理論的發(fā)展；二是博弈論研究和均衡理論興起；三是投入－產(chǎn)出問(wèn)題研究；四是解決運(yùn)輸問(wèn)題和營(yíng)養(yǎng)問(wèn)題的需求。歸根結(jié)底，數(shù)學(xué)的內(nèi)在發(fā)展達(dá)到一定程度后，社會(huì)需求是產(chǎn)生一個(gè)新學(xué)科的最大的動(dòng)力。我們己經(jīng)看到單純形法是由丹齊格創(chuàng)建的，單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃的誕生。最優(yōu)化理論與算法起因和發(fā)展395.2、單純形法的創(chuàng)建是線性規(guī)劃問(wèn)題誕生的標(biāo)志單純形法是1947年由丹齊格創(chuàng)建的，單純形法的創(chuàng)建標(biāo)志著線性規(guī)劃的誕生。正因?yàn)榇斯ぷ鞯R格享有線性規(guī)劃之父之美譽(yù)。單純形法是在探討經(jīng)濟(jì)理論的一個(gè)有用方法的過(guò)程中產(chǎn)生的，是人們對(duì)大型復(fù)雜系統(tǒng)做出實(shí)際計(jì)劃的強(qiáng)大工具。單純形法在運(yùn)輸問(wèn)題中的應(yīng)用看到，單純形法是求解線性規(guī)劃問(wèn)題的嶄新的、先進(jìn)的方法。最優(yōu)化理論與算法起因和發(fā)展405.2、單純形法的創(chuàng)建是線性規(guī)劃問(wèn)題誕生的標(biāo)志最優(yōu)化理論與算法起因和發(fā)展415.2、單純形法的創(chuàng)建是線性規(guī)劃問(wèn)題誕生的標(biāo)志

最優(yōu)化理論與算法起因和發(fā)展425.2、單純形法的創(chuàng)建是線性規(guī)劃問(wèn)題誕生的標(biāo)志

最優(yōu)化理論與算法起因和發(fā)展435.2、單純形法的創(chuàng)建是線性規(guī)劃問(wèn)題誕生的標(biāo)志如果用標(biāo)準(zhǔn)的單純形軟件，在IBM370-168計(jì)算機(jī)上去