6/26/2025第11章大數據時代的運籌學1CONTENTS目錄6/26/202511.1大數據時代的運籌學11.2大數據背景下的運籌優化

問題求解11.3數據驅動的運籌優化案例211.1大數據時代的運籌學6/26/202511.1.1“數據-預測-決策”模式4現實世界中的很多決策問題，往往包含許多不可控的不確定或未知因素。例如，在庫存管理問題中，商品的需求是不確定的；在投資組合問題中，資產的未來收益是不確定的。這些帶有不確定參數的決策問題往往可以寫作如下形式：

11.1.1“數據-預測-決策”模式

6/26/2025511.1.1“數據-預測-決策”模式數據例如，電子商務平臺記錄我們的購物喜好，社交媒體公司分析我們的互動行為，而應用軟件則通過生成日志文件來改善用戶體驗。平臺通過收集用戶的搜索記錄、購買歷史、位置信息，以及商品評價和客戶服務反饋，能夠更加精確地了解客戶需求，提高運營效率，適應市場發展的變化，并為用戶提供更加滿意的服務。數據搜集與管理構成了構建決策模型的基礎和首要步驟。數據收集覆蓋了從各種來源獲得信息的過程，而數據管理關注的是如何有效地組織、存儲和維護這些數據。在數據收集的過程中，需充分考慮數據的完整性、準確性和時效性，以確保所收集到的數據具有較高的質量和可靠性。6/26/2025611.1.1“數據-預測-決策”模式預測決策者經常面臨未來不確定性的挑戰（例如，模型參數或隨機變量分布的未知性）。預測旨在通過利用歷史數據和模式，采用統計學習或機器學習等方法，預測未知的情況或趨勢，估計未知參數或分布。問題解決的基本流程包括：數據集的準備、特征工程、模型的選擇和訓練、模型評估以及模型優化。6/26/20257以“華為云盤古氣象大模型”為例，其應用了深度學習技術，使用了從1979年至2021年、以小時為單位采樣的氣象數據，并從中提取了有效信息，進而訓練了多個模型，實現了對全球氣象的秒級預報，其中的預測結果包括溫度、濕度、風速等多個指標。11.1.1“數據-預測-決策”模式6/26/20258在不同場景中，選擇適當的模型或算法可以為我們的決策提供可靠的基礎。常見的機器學習算法通常分為有監督學習、無監督學習和強化學習。有監督學習和無監督學習的主要區別在于輸入數據是否包含標簽，而強化學習則聚焦于一種動態的學習過程。11.1.1“數據-預測-決策”模式6/26/20259強化學習訓練過程的主要目標是使智能體獲取最大的累計獎勵。強化學習中的智能體并無直接的監督，僅能從環境中獲取反饋信號，并依據該信號調整自身的行為。強化學習的基本流程：定義環境明確智能體的行為制定收益函數（以評估智能體行為的效果）實施學習過程（即依據收益函數的反饋不斷優化智能體的行為）11.1.1“數據-預測-決策”模式決策

6/26/202510在央視與中科院合辦的節目《機智過人（第二期）》中，智能機器人“少女詩人”小冰順利通過了三位分別來自牛津、北大和復旦的優秀青年詩人的最強檢驗，她的創作還在詩壇引發了一場討論，最終小冰所作的詞曲成功戰勝歌手付博，機智過人。據悉機器人小冰學習了自1920年以來的519位詩人的作品，如徐志摩的詩就讀了2000余篇（數據），總結了做詩的規律（預測與信息提取），從而能夠根據問題做出詩歌（決策）。小冰的過人表現，體現了“數據-預測-決策”模式的顯著優勢。

“少女詩人”小冰在“數據-預測-決策”模式中，決策者將預測與決策分為獨立的兩部分，在預測階段只關注預測的準確性而忽略了預測結果對決策產生的影響，僅將預測階段的輸出結果作為決策階段的輸入。“聯合預測與決策”模式在訓練預測模型時會考慮后續階段的決策誤差，將預測與決策耦合在一起。6/26/202511.1.2聯合預測與決策11考慮帶有不確定參數的優化問題6/26/202511.1.2聯合預測與決策121）“智慧預測后決策”框架

在“智慧預測后決策”框架下，預測階段我們不再關心預測準確度，而是以決策質量為目標產生預測結果，即我們考慮如下的損失函數

6/26/202511.1.2聯合預測與決策13

6/26/202511.1.2聯合預測與決策14下面以線性規劃為例，具體闡述SPO框架的整個過程。考慮如下優化問題

6/26/202511.1.2聯合預測與決策15由于SPO損失函數非凸，我們可以考慮用如下的SPO+損失函數來替代。

6/26/202511.1.2聯合預測與決策16在金融服務業中，從業者需要從數據中估計潛在的投資回報，其可能受多個特征的影響，如歷史回報、新聞、經濟因素和社交媒體。投資組合優化的目標是在受到總體風險或方差約束的情況下，找到回報最高的投資組合。這里我們考慮如下的投資組合選擇問題：

例11.2：投資組合選擇問題6/26/202511.1.2聯合預測與決策17若使用常規方法（如最小二乘法）對參數c進行預測，則方法更注重估計價值更高的投資，即使相應的風險可能過高而導致結果并不理想。而SPO框架致力于生成預測以實現在所需風險水平下的高績效投資，即在訓練預測模型時直接考慮了每項投資的風險，從而避免出現回報良好但風險超出承受能力的情況發生。

例11.2：投資組合選擇問題6/26/202511.1.2聯合預測與決策182）端到端框架和先預測再決策這一傳統方法不同，端到端（EndtoEnd）框架依據輸入特征直接輸出決策，而不需要任何中間步驟。端到端模型在訓練過程中是將所有預測和決策模塊綁定在一起，當成一個整體來訓練的。從輸入端（輸入數據）到輸出端會得到一個預測結果，與真實結果相比較會得到一個誤差，這個誤差會在模型中的每一層傳遞，每一層的參數都會根據這個誤差來做調整，直到模型收斂或達到預期的效果才結束。6/26/202511.1.2聯合預測與決策19

例11.3：端到端庫存管理問題6/26/202511.1.2聯合預測與決策20

例11.3：端到端庫存管理問題6/26/202511.1.2聯合預測與決策21例11.3：端到端庫存管理問題

11.2大數據背景下的運籌優化問題求解6/26/202511.2.1常用求解器簡介231）商用求解器①

IBMCPLEX：CPLEX是運籌優化領域中最流行和強大的求解器之一，是一種用于線性規劃、整數規劃、混合整數規劃、非線性規劃和混合整數非線性規劃的高性能求解器。它可以高速求解大規模問題，具有穩健的算法和優秀的可擴展性、可靠性，能夠處理大量的變量和約束，確保了解決實際問題的準確性和效率，因此被廣泛應用于生產調度、網絡優化、制造計劃、金融分析等領域。②

Gurobi

：Gurobi是GurobiOptimization公司開發的一種快速、高效、可靠的數學規劃求解器，在運籌優化領域中擁有很高的聲譽，可以解決線性規劃、整數規劃、二次規劃等問題，并且支持并行計算和分布式計算。Gurobi的優勢在于其高性能和高效率。它的求解速度快，能夠處理大規模復雜問題，并且提供了豐富的可視化和交互功能，便于用戶進行建模和調試。Gurobi的應用非常廣泛，常見的應用場景包括資源分配、物流運輸、能源規劃、金融分析等。6/26/202511.2.1常用求解器簡介241）商用求解器③MOSEK：MOSEK可以用于解決各種線性規劃、混合整數規劃和二次規劃等問題，是公認的求解二次規劃、二階錐規劃和半正定規劃問題最快的求解器之一。MOSEK的求解算法基于內點法和分支定界法，支持多線程求解，可以方便地與各種編程語言集成，具有高效性和可擴展性，能夠處理大型、復雜的優化問題。MOSEK在運籌優化領域的應用十分廣泛，特別是在金融、制造業和物流等領域。④LINGO：即LinearInteractiveandGeneralOptimizer，是交互式的線性和通用優化求解器，用于求解線性、非線性、整數規劃、混合整數規劃和非線性整數規劃等各種復雜的數學優化問題，還能夠處理離散、連續、混合變量，以及約束優化問題。LINGO內置建模語言，提供直觀的用戶界面，具備強大的數據可視化工具，允許用戶在建模和求解過程中進行交互式操作，并自動生成詳細的報告。LINGO廣泛應用于生產運營管理、金融和投資、工程制造、能源資源管理和運輸物流等領域。6/26/202511.2.1常用求解器簡介252）開源求解器①

SCIP：SCIP是目前求解混合整數規劃和混合整數非線性規劃最快的非商業求解器之一。可用于解決各種復雜的優化問題，也是一個用于約束整數規劃、分支定界以及分支定價的框架，具有快速求解能力、可擴展性和可定制性。與大多數商業求解器不同，SCIP允許用戶對求解過程進行完全控制，并允許用戶訪問求解器內部的詳細信息。②

GLPK

：GLPK（GNULinearProgrammingKit，GNU線性編程工具）是GNU計劃的一部分，主要用于建立大規模線性規劃和混合型整數規劃模型，并對模型進行求解。GLPK支持線性規劃、整數規劃、混合整數規劃、二次規劃和一般整數規劃等多種數學規劃問題，可在Windows、Linux、Unix、macOS等各種平臺上運行。GLPK的特點是易于使用，具有良好的可移植性和高度的靈活性。雖然GLPK的求解速度可能不如商業求解器，但是其開源、易用、靈活等特點使得它在一些特定的應用場景中具有優勢。同時，GLPK的源代碼也為研究人員和學生提供了一個優秀的學習和研究平臺。6/26/202511.2.1常用求解器簡介262）開源求解器③IPOPT：IPOPT（InteriorPointOPTimizer）是一種非線性優化求解器，由CarlD.Laird開發，采用C++編寫，可用于求解具有大量約束的大規模非線性優化問題，例如，帶等式約束和帶不等式約束的優化問題，帶非線性約束的凸優化問題等。此外，IPOPT還支持求解帶整數變量的混合整數非線性規劃問題。IPOPT在運籌優化中的應用同樣非常廣泛，特別是在工業界和學術界。許多商業公司和學術機構都使用IPOPT來解決其非線性優化問題，例如，瑞士IBM研究中心、德國大眾汽車集團、荷蘭電力公司等。另外，IPOPT也經常被應用于各種科學研究領域，如化學、物理、生物等。11.2.2CVX/YALMIP的使用規范6/26/202527在實際應用中，可以將建模軟件與優化求解器相結合，簡化建模過程，從而更快速高效地求解優化問題。CVX和YALMIP是兩種應用較為廣泛的建模軟件。CVX由斯坦福大學的一組研究人員開發，是一個用于凸優化問題建模的開源軟件包，旨在簡化和加速凸優化問題的建模和求解。它允許用戶通過一種簡潔直觀的方式來描述優化問題，并自動將這些問題轉化為數學模型，傳入外部優化求解器進行求解。主要應用領域包括：信號處理中的稀疏信號重建、機器學習中的支持向量機（SVM）和正則化問題等。11.2.2CVX/YALMIP的使用規范6/26/2025281）CVX的使用范圍

11.2.2CVX/YALMIP的使用規范6/26/2025292）CVX的基本語法CVX定義優化問題的基本格式如下：cvx_begin定義決策變量（variable）定義目標函數（minimize，maximize）定義約束條件（subjectto）cvx_end11.2.2CVX/YALMIP的使用規范6/26/2025302）CVX的基本語法右表給出了一些常用的定義決策變量、目標函數和約束條件的示例：更多詳細的CVX操作說明，請讀者參考CVX官網文檔：/cvx/doc/

。

示例含義決策變量variablex實數變量variableycomplex復數變量variablezinteger整數變量variablewbinary0-1變量variablep(n)n維向量variableq(n)integern維整數向量variabler(n)integern維0-1向量variableA(n,m)n*m維矩陣variableB(n,m,k)多維矩陣目標函數minimize(norm(x,1))maximize(geo_mean(x))約束條件l<=x<=uA*x<=bX==semidefinite(n)11.2.2CVX/YALMIP的使用規范6/26/2025313）CVX的使用實例以整數規劃問題和最小范數問題為例，展示CVX的上機使用。例11.4：整數規劃問題在MATLAB中，使用CVX建立優化模型的代碼如下：cvx_beginvariablex1integervariablex2integermaximize(8*x1+5*x2)subjecttox1+x2<=69*x1+5*x2<=45cvx_end11.2.2CVX/YALMIP的使用規范6/26/202532例11.5：最小范數問題在MATLAB中，使用CVX建立優化模型的代碼如下：m=20;n=10;p=4;A=randn(m,n);b=randn(m,1);C=randn(p,n);d=randn(p,1);e=rand;cvx_beginvariablex(n)minimize(norm(A*x–b,2))subjecttoC*x==dnorm(x,Inf)<=ecvx_end11.2.3大規模問題的算法設計6/26/202533隨著大數據時代的到來，以及運籌優化技術的不斷進步，現實中所面臨的優化難題日益復雜，且計算成本不斷升高。這主要表現為優化問題的規模擴大。在實際操作中，我們可能會遇到涉及約束和變量個數高達百萬級的復雜優化問題。盡管可能僅有有限的幾個維度會對目標函數產生顯著影響，然而解決此類問題的挑戰主要源于搜索空間的巨大化。直接應用傳統的優化算法框架會導致計算成本的極大增加，且常用的求解器往往無法承受如此龐大的計算負擔。11.2.3大規模問題的算法設計6/26/202534（1）隨機優化算法在大數據時代，現有的確定性優化算法在效率上遭遇了顯著的瓶頸。對于較為復雜的模型（如神經網絡）以及更高階的優化策略（如二階方法），確定性優化策略的計算負擔都會隨之增加。盡管面臨海量的數據和龐大的數據維度，然而通過隨機采樣樣本及其維度，我們仍有可能有效地估計或替代更新量。因此，借助于確定性優化算法，我們得以研發出諸多的隨機優化算法，包括但不限于隨機梯度下降法、隨機坐標下降法、隨機方差縮減梯度法，以及隨機（擬）牛頓法等。11.2.3大規模問題的算法設計6/26/202535現介紹常用求解大規模優化問題隨機算法：隨機梯度下降算法（StochasticGradientDescent，SGD）。考慮優化問題：

11.2.3大規模問題的算法設計6/26/202536隨機梯度算法每輪計算的目標函數為平均樣本誤差，即每次只代入計算一個樣本目標函數的梯度來更新權重，再取下一個樣本重復該過程，直到損失函數值停止下降或小于某個可接受閾值。隨機梯度下降算法具體步驟如下：算法1：隨機梯度下降算法11.2.3大規模問題的算法設計6/26/202537（2）分裂算法分裂算法也是求解大規模問題的算法。分裂是指在算法中將原問題分解為若干個子問題進行求解的過程，如圖11-6所示，而并行/串行是通過利用多個處理單元同時進行計算，提高算法的求解效率。在分裂階段，我們可以通過分裂算法（例如，塊坐標下降法，交替方向乘子法）將初始的大規模優化問題分解為規模相對較小的子問題，每個子問題可以獨立求解；在并行階段，通過不同的處理單元并行地解決這些獨立子問題。通過合理地設計并行算法，我們能最大限度地利用處理單元的計算能力，從而提高算法的求解速度和效率。11.2.3大規模問題的算法設計6/26/202538（2）分裂算法11.2.3大規模問題的算法設計6/26/2025391）塊坐標下降法（BlockCoordinateDescent,BCD）算法2：BCD算法1：初始化變量。2：選擇一個塊（一組相關變量）更新以最小化目標函數。3：若塊內變量的相對改變小于預定閾值或達到預定迭代次數，停止迭代；否則重復步驟2直至滿足停止條件。考慮無約束優化問題如下：塊坐標下降的迭代方程為：

該算法的具體步驟如下：11.2.3大規模問題的算法設計6/26/2025402）交替方向乘子法（AlternatingDirectionMethodofMultipliers,ADMM）算法3：ADMM算法1：初始化原始變量與對偶變量。2：循環迭代更新原始變量、對偶變量與對偶乘子。3：若原始變量與對偶變量的相對改變小于預定閾值或達到預定迭代次數，停止迭代；否則重復步驟2直至滿足停止條件。考慮有約束優化問題如下：ADMM的迭代方程：

其增廣拉格朗日函數為：

11.2.3大規模問題的算法設計6/26/2025413）Benders分解算法4：Benders分解算法Benders分解是一種將復雜的優化問題分解為一個主問題和多個子問題的方法，主要用于求解混合整數規劃問題。在Benders分解中，主問題是一個線性規劃問題，而子問題則是主問題的約束條件之一。主問題的目標函數包括子問題的目標函數的和以及一些固定變量的約束條件。Benders分解算法的具體步驟如下：11.2.3大規模問題的算法設計6/26/2025424）機器學習方法近年來，機器學習方法在解決大規模優化問題的領域引起廣泛關注。目前，主要有兩種機器學習算法被廣泛應用于解決大規模優化問題，它們是監督學習和強化學習。在其中，監督學習方法主要依賴于從已有的優化問題實例中學習獲得的知識，以預測及優化新問題的解決方案；而強化學習方法則更傾向于通過與環境的交互式學習，逐步優化其解決方案的策略。在應對大規模優化問題時，傳統的精確算法和近似算法可能會遭遇計算復雜度上的嚴峻挑戰。相較而言，機器學習方法能夠在一定程度上克服這些挑戰，并能提供一種更為高效的解決方案。11.3數據驅動的運籌優化案例11.3.1中國工商銀行選址問題6/26/202544中國工商銀行（簡稱ICBC）是全球規模最大的上市銀行。2006年，工商銀行在國內的分支機構數超過16,000個，個人客戶超2億，公司客戶在360萬以上。90年代進行了大規模的擴張，片面追求大、廣、全，缺乏遠見，未科學選址，致使網點運營效率低、成本高。大型高效的網點網絡是銀行業務發展的基礎，是其最重要的核心競爭力之一。為了適應多變的市場競爭環境，迎合地方經濟的發展和消費者的需求，ICBC聯合IBM針對全國40多個主要城市，展開了大規模的網點布局與服務能力的優化調整。11.3.1中國工商銀行選址問題6/26/202545提出服務網點網絡重構的目標，整理現有網點的相關數據（描述問題和現狀、采集和整理數據）將城市劃分為不同區域，根據顧客流量和商業價值評估區域的商業潛力（數據分析）通過現有網點的數據和