第1章
最優化算法概述
1.1 最優化算法簡介
最優化算法，即最優計算方法，也是運籌學，主要介紹最優化問題的算法及其應用，在第二次世界大戰及戰後經濟恢復期間，一些由多學科專家組成的運籌組織在軍事決策、資源合理利用和提高生產效率等領域做出了很大貢獻，他們的工作促使運籌學逐步形成一門新興的學科，並迅速得到普及和發展。
最優化同運籌學一樣，是利用現代數學、繫統科學、計算機科學及其他學科的最新成果，來研究人類從事的各種活動中處理事務的數量化規律，使有限的人、物、財、時空、信息等資源得到充分和合理的利用，以期獲得盡可能滿意的經濟和社會效果。
最優化算法最早研究經濟活動和軍事活動中能用數量來表達的有關策劃、管理方面的問題。隨著客觀實際的發展，它在生產生活中也得到了廣泛的應用，經常用於解決現實生活中的復雜問題，特別是改善或優化現有繫統的效率。最優化算法本身也在不斷發展，涵蓋線性規劃、非線性規劃、整數規劃、組合規劃、圖論、網絡流、決策分析、排隊論、可靠性數學理論、倉儲庫存論、物流論、博弈論、搜索論和模擬等分支。
當前最優化算法的應用領域如下。
（1）市場銷售：多應用在廣告預算和媒體的選擇、競爭性定價、新產品開發、銷售計劃的編制等方面。如美國杜邦公司在20世紀50年代起就非常重視對廣告、產品定價和新產品引入的算法研究。
（2）生產計劃：從總體確定生產、儲存和勞動力的配合等計劃以適應變動的需求計劃，主要采用線性規劃和仿真方法等。此外，還可用於日程表的編排，以及合理下料、配料、物料管理等方面。
（3）庫存管理：存貨模型將庫存理論與物料管理信息繫統相結合，主要應用於多種物料庫存量的管理，確定某些設備的能力或容量，如工廠庫存量、倉庫容量、新增發電裝機容量、計算機的主存儲器容量、合理的水庫容量等。
（4）運輸問題：涉及空運、水運、陸路運輸，以及鐵路運輸、管道運輸和廠內運輸等，包括班次調度計劃及人員服務時間安排等問題。
（5）財政和會計：涉及預算、貸款、成本分析、定價、投資、證券管理、現金管理等，采用的方法包括統計分析、數學規劃、決策分析，以及盈虧點分析和價值分析等。
（6）人事管理：主要涉及以下6個方面。
①人員的獲得和需求估計。
②人纔的開發，即進行教育和培訓。
③人員的分配，主要是各種指派問題。
④各類人員的合理利用問題。
⑤人纔的評價，主要是測定一個人對組織及社會的貢獻。
⑥人員的薪資和津貼的確定。
（7）設備維修、更新、可靠度及項目選擇和評價：如電力繫統的可靠度分析、核能電廠的可靠度及風險評估等。
（8）工程的最佳化設計：在土木、水利、信息、電子、電機、光學、機械、環境和化工等領域皆有作業研究的應用。
（9）計算機信息繫統：可將作業研究的最優化算法應用於計算機的主存儲器配置，如等候理論在不同排隊規則下對磁盤、磁鼓和光盤工作性能的影響。利用整數規劃尋找滿足一組需求檔案的尋找次序，並通過圖論、數學規劃等方法研究計算機信息繫統的自動設計。
（10）城市管理：包括各種緊急服務救難繫統的設計和運用，如消防車、救護車、警車等分布點的設立。美國采用等候理論方法來確定紐約市緊急電話站的值班人數，加拿大采用該方法研究城市警車的配置和負責範圍，以及事故發生後警車應走的路線等。此外，還涉及城市垃圾的清掃、搬運和處理，以及城市供水和污水處理繫統的規劃等相關問題。
1.2 最優化算法的內容
最優化算法的內容包括：規劃論（線性規劃、非線性規劃、整數規劃和動態規劃）、庫存論、圖論、排隊論、可靠性理論、對策論、決策論、搜索論等，下面將具體介紹這些內容。
1.2.1 規劃論
規劃論（數學規劃）是運籌學的一個重要分支，早在1939年蘇聯的康托羅維奇（Leonid V.Kantorovich）和美國的希奇柯克（F.L.Hitchcock）等人就在生產組織管理和編制交通運輸方案時研究和應用了線性規劃方法。
1947年美國的旦茨格（G.B. Dantzig）等人提出了求解線性規劃問題的單純形法，為線性規劃的理論與計算奠定了基礎，特別是計算機的出現和日益完善，更使規劃論得到迅速的發展，它采用計算機處理成千上萬個約束條件和變量的大規模線性規劃問題，從解決技術問題的最優化，到工業、農業、商業、交通運輸業和決策分析部門都可以發揮作用。
從應用範圍來看，小到一個班組的計劃安排，大至整個部門乃至國民經濟計劃的最優化方案分析都有用武之地，因此，它具有適應性強、應用面廣、計算技術比較簡便的特點。非線性規劃的基礎性工作是在1951年由庫恩（H.W.Kuhn）和塔克（A.W.Tucker）等人完成的，到了20世紀70年代，數學規劃無論是在理論和方法上，還是在應用的深度和廣度上都得到了進一步的發展。
數學規劃的研究對像是計劃管理工作中有關安排和估值的問題，即在給定條件下，按某個衡量指標來尋找安排的最優方案。它可以表示為求函數在滿足約束條件下的極大值或極小值問題。
現代的數學規劃和古典的求極值的問題有本質的不同。古典的求極值方法隻能處理具有簡單表達式和簡單約束條件的情況，而現代的數學規劃中的問題目標函數和約束條件都很復雜，而且要求給出某種精確度的數字解答，因此算法的研究受到了特別的重視。
數學規劃中最簡單的一類問題就是線性規劃。如果約束條件和目標函數都屬於線性關繫就叫線性規劃。要解決線性規劃問題，從理論上講要解線性方程組，因此解線性方程組的方法，以及關於行列式、矩陣的知識，在線性規劃中非常重要。
線性規劃及其解法（單純形法）的出現，對最優化算法的發展起了很大的推動作用。許多實際問題都可以轉化成線性規劃來解決，而單純形法又是一個行之有效的算法，加上計算機的出現，能夠使一些大型復雜的實際問題得以解決。
非線性規劃是線性規劃的進一步發展和延伸。許多實際問題如設計問題、經濟平衡問題都屬於非線性規劃的範疇。非線性規劃擴大了數學規劃的應用範圍，同時也給數學工作者提出了許多基本的理論問題，使數學中的如凸分析、數值分析等也得到了發展。還有一種規劃問題和時間有關，即“動態規劃”，它已經成為在工程控制、技術物理和通信中最佳控制問題的重要工具。
1.2.2 庫存論
庫存論（存貯論）是運籌學中發展較早的分支。早在1915年，哈裡斯（F.Harris）就針對銀行貨幣的儲備問題進行了詳細的研究，建立了一個確定性的存貯費用模型，並求得了最佳批量公式。1934年威爾遜（R.H.Wilson）重新得出經濟訂購批量公式（EOQ公式）。
庫存論真正作為一門理論發展起來是在20世紀50年代。1958年威汀（T.M.Whitin）發表了《存貯管理的理論》，隨後阿羅（K.J.Arrow）等發表了《存貯和生產的數學理論研究》，莫蘭（P.A.Moran）在1959年編寫了《存貯理論》。此後，庫存論成了運籌學中的一個獨立的分支，有關學者相繼對隨機或非平穩需求的存貯模型進行了廣泛深入的研究。
現代化的生產和經營活動都離不開存貯，為了使生產和經營活動能有條不紊地進行，工商企業都需要進行一定數量的物資貯備。例如，工廠為了進行連續生產，就需要貯備一定數量的原材料或半成品；商店為了滿足顧客的需求，就必須有足夠的商品庫存；農業部門為了確保正常生產，就需要貯備一定數量的種子、化肥、農藥；軍事部門為了戰備的需要，就要存貯各種武器彈藥等軍用物品；銀行為了進行正常的業務，就需要有一定的資金貯備；在如今的信息社會，人們又建立了各種數據庫和信息庫，用以存貯大量的信息。
因此，存貯問題是人類社會活動，特別是生產活動中一個普遍存在的問題。物資的存貯，除了用來支持日常生產經營活動，庫存調節還可以滿足高於平均水平的需求，同時也可以防止低於平均水平的供給。此外，大批量物資的訂貨或利用物資季節性價格的波動，也可以得到價格上的優惠。
但是，存貯物資需要占用大量的資金、人力和物力，有時甚至造成資源的嚴重浪費。大量的庫存物資所占用的資金，無論從相對數值還是絕對數值上來看都是十分驚人的。此外，大量的庫存物資還會引起貨物的劣化變質而造成巨大損失，如藥品、水果、蔬菜等，長期存放就會引起變質。特別是在市場經濟條件下，過多地存貯物資還要承受市場價格波動的風險。
那麼，一個企業究竟應存放多少物資最為適宜呢？對於這個問題，很難籠統地給出準確回答，必須根據企業自身的實際情況和外部的經營環境來決定，若能通過科學的存貯管理，建立一套控制庫存的有效方法，從而降低物資的庫存水平，減少資金的占用量，提高資源的利用率，這對企業來講，所帶來的經濟效益無疑是十分可觀的。這正是現代存貯論所要研究的問題。
物資的存貯按其目的的不同可分為以下3種。
（1）生產存貯。它是企業為了維持正常生產而儲備的原材料或半成品。
（2）產品存貯。它是企業為了滿足其他部門的需要而存貯的半成品或成品。
（3）供銷存貯。它是指存貯在供銷部門的各種物資，可直接滿足顧客的需要。
但不論哪種類型的存貯繫統，一般都可以使用如圖1.1所示的形式來表示。
圖1.1 庫存模型
庫存論可以用“供、存、銷”3個字來描述，即一個存貯繫統，通過訂貨和進貨後的存貯與銷售來滿足顧客的需求。或者說，由於生產或銷售的需求，從存貯繫統中取出一定數量的庫存貨物，這就是存貯繫統的輸出；存貯的貨物由於不斷地輸出而減少，必須及時地補充，補充就是存貯繫統的輸入，補充可以通過外部訂貨、采購等活動來進行，也可以通過內部的生產活動來進行。在這個繫統中，決策者可以通過控制訂貨時間的間隔和訂貨量的多少來調節繫統的運行，使得在某種準則下繫統運行能夠達到最優。
因此，庫存論中研究的主要問題可以概括為何時訂貨（補充存貯）和每次訂多少貨（補充多少庫存）這兩個問題。
1.2.3 圖論
自然界和人類社會中的很多事物，以及事物之間的聯繫，都可以用點和線聯繫起來的圖形來描述，如用點表示城市，用點與點之間的連線表示城市之間的道路，這樣就可以描述城市之間的交通。如果在連線旁標明城市間的距離（在網絡圖中稱為權），則形成加權圖，就可以進一步研究從一個城市到另一個城市的最短路徑；或者在連線旁邊標上運輸單價，就可以分析運費最少的運輸方案。用圖來描述事物間的聯繫，不僅直觀清晰，而且網絡的畫法簡單，不必拘泥於比例與曲直。圖論既是拓撲學的一個分支，也是運籌學的重要分支，它是建立和處理離散數學模型的有用工具。
早在1736年，瑞士數學家歐拉（E.Euler）在求解著名的哥尼斯堡七橋難題時，就使用了圖來進行分析論證。19世紀以來，英國數學家哈密頓提出了哈密頓（William Rowan Hamilton）回路和旅行商問題；電路定律創始人德國物理學家基爾霍夫（Gustav Robert Kirchhoff）和英國數學家凱萊（Arthur Cayley）提出了樹的概念，分別用於求解和研究電力線網與化學分析結構，進一步發展了圖論。1736年歐拉發表了關於圖論的第一篇論文《依據幾何位置的解題方法》，同年匈牙利數學家柯尼格（D. Konig）出版了圖論的第一本專著《有限圖與無限圖的理論》。
近年來，隨著計算機科學技術和最優化算法的發展，網絡圖論得到了更進一步的發展，其應用日益廣泛。網絡圖論的分析方法被廣泛應用於電力線網和煤氣管道網的分析、印刷電路與集成電路的布線和測試、通信網絡分析、交通運輸網絡的分析、經濟和管理領域中流行的網絡分析等。
1.2.4 排隊論
排隊論（隨機服務繫統理論）是在20世紀初由丹麥工程師愛爾朗（A. K. Erlang）對電話交換機的效率研究開始的，在第二次世界大戰中為了對飛機場跑道的容納量進行估算，該理論得到了進一步的發展，其相應的學科更新論、可靠性理論等也都發展了起來。
丹麥的電話工程師愛爾朗於1930年以後，開始了關於排隊問題的研究，取得了一些重要成果。1949年前後，他開始了對機器管理、陸空交通等方面的研究，1951年以後，他的理論工作有了新的進展，逐漸奠定了現代隨機服務繫統的理論基礎。排隊論主要研究各種繫統的排隊長度、排隊的等待時間及所提供的服務等各種參數，以便求得更好的服務，它是研究繫統隨機聚散現像的理論。
排隊論的研究目的是要回答如何改進服務機構或組織所服務的對像，使某種指標達到最優的問題。如一個港口應該有多少個碼頭、一個工廠應該有多少名維修人員等。
因為排隊現像是一個隨機現像，因此在研究排隊現像時，主要采用將研究隨機現像的概率論作為主要工具。此外，還涉及微分和微分方程的相關內容。排隊論把它所要研究的對像形像地描述為顧客來到服務臺前要求接待。如果服務臺已被其他顧客占用，那麼就要排隊。或者服務臺時而空閑、時而忙碌，那就需要通過數學方法求得顧客的等待時間、排隊長度等的概率分布。
排隊論在日常生活中的應用非常廣泛，如水庫水量的調節、生產流水線的安排、鐵路運輸的調度、電網的設計等。
