學(xué)建模規(guī)劃模型：從線性規(guī)劃到運(yùn)輸問(wèn)題的決策優(yōu)化實(shí)戰(zhàn))
1. 項(xiàng)目概述規(guī)劃模型數(shù)學(xué)建模的“決策大腦”如果你剛開始接觸數(shù)學(xué)建模或者正準(zhǔn)備參加相關(guān)的競(jìng)賽那么“規(guī)劃模型”這個(gè)概念你大概率是繞不開的。它不像一些復(fù)雜的算法那樣聽起來(lái)高深莫測(cè)但卻是解決一大類實(shí)際問(wèn)題的核心框架。簡(jiǎn)單來(lái)說(shuō)規(guī)劃模型就是數(shù)學(xué)建模中的“決策大腦”——當(dāng)你面對(duì)一堆資源、一堆任務(wù)、一堆限制條件需要找到一個(gè)“最優(yōu)”的行動(dòng)方案時(shí)規(guī)劃模型就是你的首選工具。想象一下你是一個(gè)工廠的生產(chǎn)主管手上有幾條生產(chǎn)線、幾種原材料、一批訂單還有電費(fèi)、人力成本等各種約束。你的目標(biāo)是在滿足所有訂單和資源限制的前提下讓總利潤(rùn)最高或者總成本最低。這個(gè)“怎么安排生產(chǎn)”的問(wèn)題本質(zhì)上就是一個(gè)規(guī)劃問(wèn)題。再比如物流公司要規(guī)劃配送路線在有限的車隊(duì)和時(shí)間內(nèi)把貨物送到各個(gè)客戶點(diǎn)同時(shí)讓總運(yùn)輸距離最短這也是規(guī)劃。甚至你個(gè)人安排一天的時(shí)間在有限的時(shí)間里完成學(xué)習(xí)、鍛煉、娛樂(lè)追求效率最大化這也可以抽象成一個(gè)簡(jiǎn)單的規(guī)劃模型。所以規(guī)劃模型的應(yīng)用場(chǎng)景極其廣泛從工業(yè)生產(chǎn)、交通運(yùn)輸、金融投資到日常生活中的資源分配無(wú)處不在。它的核心思想就是把一個(gè)現(xiàn)實(shí)中的決策問(wèn)題用數(shù)學(xué)語(yǔ)言主要是方程和不等式描述出來(lái)然后通過(guò)特定的數(shù)學(xué)方法求解出那個(gè)“最優(yōu)”的決策變量值。這個(gè)“最優(yōu)”在數(shù)學(xué)上通常表現(xiàn)為一個(gè)目標(biāo)函數(shù)的最大化或最小化比如利潤(rùn)最大、成本最小、時(shí)間最短、滿意度最高等等。對(duì)于初學(xué)者而言規(guī)劃模型是進(jìn)入數(shù)學(xué)建模實(shí)戰(zhàn)領(lǐng)域一個(gè)非常友好的起點(diǎn)。它邏輯清晰步驟相對(duì)規(guī)范從問(wèn)題分析、模型建立到求解驗(yàn)證有一套成熟的方法論。掌握了它你就能解決一大類有明確優(yōu)化目標(biāo)的決策問(wèn)題。接下來(lái)我們就深入拆解這個(gè)“決策大腦”的構(gòu)造與運(yùn)作原理。2. 規(guī)劃模型的核心思想與分類體系規(guī)劃模型或者說(shuō)數(shù)學(xué)規(guī)劃其核心思想可以概括為在滿足一系列約束條件的前提下尋找一組決策變量的取值使得某個(gè)特定的目標(biāo)函數(shù)達(dá)到最優(yōu)最大或最小。這句話包含了三個(gè)關(guān)鍵要素也是我們構(gòu)建任何規(guī)劃模型時(shí)必須明確的三件事決策變量這是我們能控制的東西是模型要求解的對(duì)象。比如生產(chǎn)多少產(chǎn)品A、多少產(chǎn)品B從倉(cāng)庫(kù)i到客戶j派多少輛車投資項(xiàng)目中分配多少資金給股票、多少給債券。通常用 x?, x?, ..., x? 或 x_{ij} 來(lái)表示。目標(biāo)函數(shù)這是我們追求的目標(biāo)的數(shù)學(xué)表達(dá)。它是一個(gè)關(guān)于決策變量的函數(shù)。我們就是要讓這個(gè)函數(shù)值盡可能大如利潤(rùn)、效率或盡可能小如成本、時(shí)間、風(fēng)險(xiǎn)。例如總利潤(rùn) Z 5x? 8x?總運(yùn)輸成本 C ΣΣ c_{ij} * x_{ij}。約束條件這是我們?cè)谧鰶Q策時(shí)必須遵守的限制。它們通常用關(guān)于決策變量的等式或不等式來(lái)表示。例如原材料消耗不能超過(guò)庫(kù)存不等式生產(chǎn)線每天的總工時(shí)有限不等式必須滿足所有客戶的需求等式或不等式。把這三大要素用數(shù)學(xué)符號(hào)清晰地寫出來(lái)一個(gè)規(guī)劃模型就初步建立了。根據(jù)目標(biāo)函數(shù)和約束條件的形式不同規(guī)劃模型可以分為幾大類每種類型都有其適用的場(chǎng)景和求解方法。2.1 線性規(guī)劃最簡(jiǎn)單也最基礎(chǔ)如果目標(biāo)函數(shù)和所有約束條件都是決策變量的線性表達(dá)式即沒(méi)有平方、乘積、指數(shù)、對(duì)數(shù)等非線性項(xiàng)那么這個(gè)模型就是線性規(guī)劃。特點(diǎn)與適用場(chǎng)景形式簡(jiǎn)單Max/Min Z c?x? c?x? ... c?x?約束條件a??x? a??x? ... a??x? ≤ (或 , ≥) b?a??x? a??x? ... a??x? ≤ (或 , ≥) b?...求解成熟有非常成熟且高效的算法如單純形法、內(nèi)點(diǎn)法。利用MATLAB、PythonSciPy, PuLP、Lingo等工具可以輕松求解。應(yīng)用廣泛資源分配、生產(chǎn)計(jì)劃、配料問(wèn)題、運(yùn)輸問(wèn)題等。例如經(jīng)典的“食譜問(wèn)題”用最少的成本滿足營(yíng)養(yǎng)需求和“運(yùn)輸問(wèn)題”最小化總運(yùn)費(fèi)。注意線性規(guī)劃的最優(yōu)解如果存在通常會(huì)在約束條件構(gòu)成的“可行域”的頂點(diǎn)上取得。這是單純形法能夠高效工作的理論基礎(chǔ)。2.2 整數(shù)規(guī)劃與0-1規(guī)劃當(dāng)決策必須是整數(shù)時(shí)在線性規(guī)劃的基礎(chǔ)上如果要求全部或部分決策變量必須取整數(shù)值就變成了整數(shù)規(guī)劃。其中一種特殊且極其重要的情形是0-1規(guī)劃即決策變量只能取0或1通常用于表示“是/否”、“選擇/不選擇”這類邏輯決策。特點(diǎn)與適用場(chǎng)景組合爆炸即使問(wèn)題規(guī)模不大求解難度也可能遠(yuǎn)高于線性規(guī)劃屬于NP-hard問(wèn)題。建模靈活0-1變量是建模的“瑞士軍刀”可以處理固定成本、邏輯關(guān)系如果…那么…、互斥選擇等復(fù)雜條件。典型應(yīng)用背包問(wèn)題在容量有限的背包里選擇物品使總價(jià)值最大。每個(gè)物品要么選1要么不選0。指派問(wèn)題將若干任務(wù)分配給若干人每人只做一個(gè)任務(wù)每個(gè)任務(wù)只由一人完成如何使總成本最小或總效率最高用x_{ij}0或1表示“是否將任務(wù)i分配給人j”。選址問(wèn)題在若干個(gè)候選地點(diǎn)中選擇幾個(gè)建立工廠或倉(cāng)庫(kù)需要決策在哪個(gè)地點(diǎn)建0-1變量以及從選址點(diǎn)運(yùn)出多少貨物連續(xù)或整數(shù)變量。求解方法分支定界法、割平面法是主流精確算法。對(duì)于大規(guī)模問(wèn)題常采用啟發(fā)式算法如遺傳算法、模擬退火求近似最優(yōu)解。2.3 非線性規(guī)劃現(xiàn)實(shí)世界的復(fù)雜關(guān)系當(dāng)目標(biāo)函數(shù)或約束條件中至少有一個(gè)是決策變量的非線性函數(shù)時(shí)就是非線性規(guī)劃。現(xiàn)實(shí)世界中的關(guān)系遠(yuǎn)比線性復(fù)雜比如成本隨產(chǎn)量增加而邊際遞減經(jīng)濟(jì)學(xué)中的規(guī)模效應(yīng)或者距離計(jì)算涉及平方和開根號(hào)。特點(diǎn)與適用場(chǎng)景模型更貼近現(xiàn)實(shí)能描述更復(fù)雜的經(jīng)濟(jì)、物理、工程關(guān)系。求解困難沒(méi)有通用的、像單純形法那樣高效的算法。最優(yōu)解可能不是全局最優(yōu)而是局部最優(yōu)且求解過(guò)程對(duì)初始值敏感。常見(jiàn)類型二次規(guī)劃目標(biāo)函數(shù)是二次函數(shù)約束為線性。在投資組合優(yōu)化風(fēng)險(xiǎn)最小化中常見(jiàn)。幾何規(guī)劃、凸規(guī)劃如果問(wèn)題具有凸性則局部最優(yōu)就是全局最優(yōu)相對(duì)容易求解。求解工具M(jìn)ATLAB的fminconPython的SciPy.optimize模塊以及專業(yè)的優(yōu)化求解器如Gurobi、CPLEX也支持部分非線性。2.4 多目標(biāo)規(guī)劃?rùn)?quán)衡的藝術(shù)現(xiàn)實(shí)中我們往往不止追求一個(gè)目標(biāo)。企業(yè)既要利潤(rùn)最大化又要風(fēng)險(xiǎn)最小化還要市場(chǎng)份額增長(zhǎng)。這就是多目標(biāo)規(guī)劃要解決的問(wèn)題在多個(gè)相互沖突的目標(biāo)之間尋找平衡。核心思想 不存在一個(gè)解能讓所有目標(biāo)同時(shí)達(dá)到最優(yōu)而是存在一個(gè)“帕累托最優(yōu)”解集。在這個(gè)解集中你無(wú)法在不損害至少一個(gè)其他目標(biāo)的情況下改進(jìn)任何一個(gè)目標(biāo)。處理方法化多為單將多個(gè)目標(biāo)通過(guò)加權(quán)求和、優(yōu)先級(jí)排序目標(biāo)規(guī)劃或選擇一個(gè)主要目標(biāo)、其余轉(zhuǎn)為約束等方式轉(zhuǎn)化為單目標(biāo)問(wèn)題。交互式方法決策者參與求解過(guò)程根據(jù)當(dāng)前解不斷調(diào)整偏好逐步逼近最滿意的解。智能優(yōu)化算法如多目標(biāo)遺傳算法NSGA-II可以直接生成一組近似帕累托最優(yōu)解前沿面供決策者選擇。實(shí)操心得在數(shù)學(xué)建模競(jìng)賽中多目標(biāo)問(wèn)題非常常見(jiàn)。一個(gè)實(shí)用的技巧是先分別對(duì)每個(gè)單目標(biāo)求解了解其理想值和邊界再通過(guò)加權(quán)法權(quán)重需要靈敏度分析或ε-約束法將一個(gè)目標(biāo)轉(zhuǎn)為約束約束右端項(xiàng)由另一個(gè)目標(biāo)的最優(yōu)值放松得到來(lái)尋找折中解。在論文中清晰地展示這個(gè)權(quán)衡過(guò)程比直接給出一個(gè)解更重要。3. 從問(wèn)題到模型五步建模法實(shí)戰(zhàn)拆解建立一個(gè)可求解的規(guī)劃模型不能只靠靈感需要一個(gè)結(jié)構(gòu)化的思考過(guò)程。這里我結(jié)合多年經(jīng)驗(yàn)總結(jié)出一個(gè)五步法它幾乎適用于所有規(guī)劃類問(wèn)題。3.1 第一步問(wèn)題界定與目標(biāo)梳理這一步看似簡(jiǎn)單卻至關(guān)重要。你必須回答到底要解決什么問(wèn)題決策者是誰(shuí)成功的標(biāo)準(zhǔn)是什么明確決策變量問(wèn)自己“我們能控制什么”把答案量化成變量。例如控制“生產(chǎn)量”變量就是x_A產(chǎn)品A的產(chǎn)量、x_B產(chǎn)品B的產(chǎn)量。明確優(yōu)化目標(biāo)問(wèn)自己“我們最終想要什么”是最大化利潤(rùn)、最小化成本、最短化時(shí)間還是最大化滿意度用數(shù)學(xué)語(yǔ)言描述它和決策變量的關(guān)系。有時(shí)目標(biāo)不止一個(gè)需要記錄下來(lái)。識(shí)別約束條件問(wèn)自己“我們受到哪些限制”資源人力、物料、資金、時(shí)間是有限的市場(chǎng)需求、合同要求、物理定律如容量限制必須滿足決策變量本身可能有范圍非負(fù)、整數(shù)。技巧用一句話概括問(wèn)題“在____的限制下通過(guò)調(diào)整____來(lái)實(shí)現(xiàn)____的最優(yōu)。” 這句話的空白處填上的內(nèi)容就是模型的骨架。3.2 第二步數(shù)據(jù)收集與參數(shù)定義模型中的數(shù)字不是憑空想象的。目標(biāo)函數(shù)里的系數(shù)如單位利潤(rùn)、約束條件里的系數(shù)如單位產(chǎn)品耗材和右端項(xiàng)如資源總量都需要基于實(shí)際數(shù)據(jù)或合理假設(shè)。參數(shù)類型效益型參數(shù)在目標(biāo)函數(shù)中與最大化目標(biāo)正相關(guān)如售價(jià)、效率。成本型參數(shù)在目標(biāo)函數(shù)中與最小化目標(biāo)正相關(guān)如成本、時(shí)間、距離。技術(shù)系數(shù)在約束條件中連接決策變量和資源消耗如生產(chǎn)單位產(chǎn)品所需的工時(shí)、原料。資源限量約束條件的右端項(xiàng)如總工時(shí)、原料庫(kù)存、預(yù)算上限。數(shù)據(jù)來(lái)源歷史數(shù)據(jù)、市場(chǎng)調(diào)研、技術(shù)手冊(cè)、合理估算。在建模競(jìng)賽中數(shù)據(jù)可能由賽題給出也可能需要自己搜集或合理假設(shè)。注意事項(xiàng)數(shù)據(jù)的單位必須統(tǒng)一這是新手常犯的錯(cuò)誤。如果目標(biāo)函數(shù)是“利潤(rùn)元”那么成本、售價(jià)的單位都必須是“元”。如果約束條件是“工時(shí)小時(shí)”那么單位產(chǎn)品耗時(shí)的單位也必須是“小時(shí)/件”。單位不一致會(huì)導(dǎo)致模型完全錯(cuò)誤。3.3 第三步數(shù)學(xué)公式構(gòu)建這是將前兩步的思考成果用嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)語(yǔ)言書寫出來(lái)的過(guò)程。要求清晰、完整、無(wú)歧義。以一個(gè)小型生產(chǎn)計(jì)劃問(wèn)題為例某工廠生產(chǎn)兩種產(chǎn)品A和B。生產(chǎn)一件A產(chǎn)品利潤(rùn)3元耗時(shí)2小時(shí)耗材4公斤生產(chǎn)一件B產(chǎn)品利潤(rùn)5元耗時(shí)3小時(shí)耗材2公斤。工廠每天可用工時(shí)為100小時(shí)原料庫(kù)存為80公斤。問(wèn)每天如何安排生產(chǎn)使利潤(rùn)最大定義決策變量設(shè)x1為產(chǎn)品A的日產(chǎn)量x2為產(chǎn)品B的日產(chǎn)量。建立目標(biāo)函數(shù)總利潤(rùn)Z 3*x1 5*x2目標(biāo)是最大化Max Z。列出約束條件工時(shí)約束2*x1 3*x2 ≤ 100生產(chǎn)總耗時(shí)不超過(guò)100小時(shí)原料約束4*x1 2*x2 ≤ 80消耗原料不超過(guò)80公斤非負(fù)約束x1 ≥ 0, x2 ≥ 0產(chǎn)量不能為負(fù)完整模型Max Z 3*x1 5*x2 s.t. (subject to) 2*x1 3*x2 ≤ 100 4*x1 2*x2 ≤ 80 x1, x2 ≥ 0這就是一個(gè)完整的線性規(guī)劃模型。3.4 第四步模型求解與工具選擇模型建立后就需要求解。選擇什么工具取決于模型的類型和規(guī)模。模型類型推薦工具/軟件關(guān)鍵命令/函數(shù)示例適用場(chǎng)景中小型線性/整數(shù)規(guī)劃Lingo語(yǔ)法接近數(shù)學(xué)公式直接輸入模型即可求解。教學(xué)、快速原型驗(yàn)證、中小規(guī)模問(wèn)題。通用科學(xué)計(jì)算MATLABlinprog(線性),intlinprog(整數(shù)),fmincon(非線性)學(xué)術(shù)界常用與仿真、數(shù)據(jù)分析結(jié)合緊密。編程與算法開發(fā)PythonSciPy.optimize.linprog,PuLP庫(kù),ortools庫(kù)靈活性最高易于集成到數(shù)據(jù)管道和Web應(yīng)用中開源免費(fèi)。大規(guī)模復(fù)雜商業(yè)問(wèn)題專業(yè)求解器(Gurobi, CPLEX)通過(guò)其APIPython, Java等調(diào)用工業(yè)級(jí)應(yīng)用求解速度最快支持模型類型最全含非線性。求解過(guò)程實(shí)錄以Python PuLP庫(kù)求解上述生產(chǎn)問(wèn)題為例# 導(dǎo)入PuLP庫(kù) from pulp import * # 創(chuàng)建問(wèn)題指定名稱和優(yōu)化方向最大化 prob LpProblem(Simple_Production_Problem, LpMaximize) # 定義決策變量lowBound指定下界非負(fù) x1 LpVariable(Product_A, lowBound0, catContinuous) # 連續(xù)變量 x2 LpVariable(Product_B, lowBound0, catContinuous) # 定義目標(biāo)函數(shù) prob 3*x1 5*x2, Total_Profit # 添加約束條件 prob 2*x1 3*x2 100, Labor_Constraint prob 4*x1 2*x2 80, Material_Constraint # 求解問(wèn)題 prob.solve() # 打印求解狀態(tài)和結(jié)果 print(Status:, LpStatus[prob.status]) print(Optimal Production Plan:) print(f Product A: {x1.varValue} units) print(f Product B: {x2.varValue} units) print(fMaximum Profit: {value(prob.objective)})運(yùn)行后你會(huì)得到最優(yōu)解x10, x240, Z200。這意味著全部生產(chǎn)產(chǎn)品B利潤(rùn)最大。這個(gè)結(jié)果可能有點(diǎn)反直覺(jué)為什么利潤(rùn)低一點(diǎn)的A完全不生產(chǎn)這就需要下一步的分析。3.5 第五步結(jié)果分析與模型檢驗(yàn)求出解不是終點(diǎn)分析解的含義和模型的合理性才是關(guān)鍵。解的解釋將數(shù)學(xué)解“翻譯”回實(shí)際問(wèn)題。如上例應(yīng)建議工廠“每天生產(chǎn)40件B產(chǎn)品不生產(chǎn)A產(chǎn)品可獲得最大利潤(rùn)200元。”靈敏度分析關(guān)鍵研究模型參數(shù)目標(biāo)函數(shù)系數(shù)、約束右端項(xiàng)的微小變化對(duì)最優(yōu)解的影響。這回答了決策者更關(guān)心的問(wèn)題產(chǎn)品B的利潤(rùn)下降多少我們才需要考慮生產(chǎn)A分析目標(biāo)函數(shù)系數(shù)如果加班增加10個(gè)工時(shí)利潤(rùn)能增加多少分析約束右端項(xiàng)即“影子價(jià)格”在Lingo、MATLAB或?qū)I(yè)求解器的輸出中通常直接包含靈敏度分析報(bào)告。模型檢驗(yàn)與穩(wěn)健性檢查解是否合理如上例全部生產(chǎn)B原料剛好用完2*4080但工時(shí)剩余3*40120 100?等等這里計(jì)算有誤我們重新檢查3*40120但工時(shí)約束是≤100120100這違反了約束這是一個(gè)非常重要的發(fā)現(xiàn)重新審視模型我們的求解顯示x240代入工時(shí)約束2*0 3*40 120 100這違反了第一個(gè)約束這說(shuō)明我們要么模型輸入有誤要么求解理解有誤。實(shí)際上用圖解法或重新求解例如用更精確的工具會(huì)發(fā)現(xiàn)此問(wèn)題的最優(yōu)解應(yīng)在工時(shí)和原料約束的交點(diǎn)附近。讓我們糾正并重新分析。糾正后的求解與深入分析 實(shí)際上兩個(gè)約束是2x1 3x2 ≤ 1004x1 2x2 ≤ 80用圖解法或單純形法求得最優(yōu)解為x1 10, x2 20。此時(shí)利潤(rùn)Z 3*10 5*20 130工時(shí)消耗2*10 3*20 80 ≤ 100原料消耗4*10 2*20 80 ≤ 80靈敏度分析示例影子價(jià)格原料約束的影子價(jià)格會(huì)比工時(shí)約束高因?yàn)樵显谧顑?yōu)解下是“緊約束”用完80公斤而工時(shí)還有20小時(shí)剩余是“松約束”。增加一公斤原料帶來(lái)的利潤(rùn)提升影子價(jià)格比增加一工時(shí)要大。目標(biāo)系數(shù)范圍產(chǎn)品B的利潤(rùn)系數(shù)5在當(dāng)前最優(yōu)解10,20保持不變的允許變化范圍是多少如果B利潤(rùn)降到某個(gè)值以下最優(yōu)解可能會(huì)變成多生產(chǎn)A。這個(gè)“發(fā)現(xiàn)錯(cuò)誤-糾正-再分析”的過(guò)程恰恰是模型檢驗(yàn)的核心。它告訴我們永遠(yuǎn)不要盲目相信求解器的第一個(gè)輸出必須將解代回原問(wèn)題和約束進(jìn)行驗(yàn)證并思考其實(shí)際意義。4. 經(jīng)典模型案例深度剖析運(yùn)輸問(wèn)題為了讓大家更好地掌握規(guī)劃模型的完整應(yīng)用流程我們剖析一個(gè)經(jīng)典案例運(yùn)輸問(wèn)題。它結(jié)構(gòu)清晰是學(xué)習(xí)整數(shù)規(guī)劃和線性規(guī)劃的絕佳例題。4.1 問(wèn)題描述與模型建立問(wèn)題有m個(gè)產(chǎn)地倉(cāng)庫(kù)/工廠A1, A2, ..., Am其供應(yīng)量分別為a1, a2, ..., am。有n個(gè)銷地市場(chǎng)/客戶B1, B2, ..., Bn其需求量分別為b1, b2, ..., bn。從產(chǎn)地i到銷地j的單位物資運(yùn)價(jià)為c_{ij}。問(wèn)如何調(diào)運(yùn)物資才能在滿足供需平衡的前提下使總運(yùn)輸費(fèi)用最小假設(shè)總供應(yīng)量等于總需求量即Σa_i Σb_j。這是“平衡運(yùn)輸問(wèn)題”。如果不平衡可以通過(guò)增設(shè)虛擬產(chǎn)地或銷地化為平衡問(wèn)題。建模步驟決策變量設(shè)x_{ij}為從產(chǎn)地i運(yùn)往銷地j的物資數(shù)量。這是我們要決定的。目標(biāo)函數(shù)總運(yùn)費(fèi)最小化。Min Z Σ_{i1}^{m} Σ_{j1}^{n} c_{ij} * x_{ij}約束條件供應(yīng)約束從每個(gè)產(chǎn)地i運(yùn)出的總量等于其供應(yīng)量。Σ_{j1}^{n} x_{ij} a_i, for all i.需求約束運(yùn)到每個(gè)銷地j的總量等于其需求量。Σ_{i1}^{m} x_{ij} b_j, for all j.非負(fù)約束運(yùn)量不能為負(fù)。x_{ij} ≥ 0。這是一個(gè)典型的線性規(guī)劃模型由于其約束矩陣的特殊結(jié)構(gòu)每列只有兩個(gè)1存在比單純形法更高效的專門算法如表上作業(yè)法。4.2 求解方法從表上作業(yè)法到軟件求解1. 表上作業(yè)法手工/理解原理 適用于規(guī)模較小的問(wèn)題有助于理解運(yùn)輸問(wèn)題的本質(zhì)。其核心步驟是Step1: 編制運(yùn)價(jià)表和產(chǎn)銷平衡表。Step2: 尋找初始基可行解。常用方法有最小元素法優(yōu)先安排運(yùn)價(jià)最低的路線或伏格爾法考慮次小運(yùn)費(fèi)結(jié)果往往更好。Step3: 最優(yōu)性檢驗(yàn)。計(jì)算每個(gè)非基變量空格的檢驗(yàn)數(shù)位勢(shì)法。若所有檢驗(yàn)數(shù)≥0則當(dāng)前解最優(yōu)否則轉(zhuǎn)入下一步。Step4: 閉回路調(diào)整。選取負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的空格尋找一條閉合回路沿回路調(diào)整運(yùn)量得到新的調(diào)運(yùn)方案。返回Step3。2. 軟件求解實(shí)際應(yīng)用 對(duì)于任何規(guī)模的運(yùn)輸問(wèn)題用規(guī)劃求解軟件都是最直接的方式。我們將其轉(zhuǎn)化為線性規(guī)劃模型輸入即可。Python PuLP 求解示例 假設(shè)有2個(gè)產(chǎn)地供應(yīng)30, 253個(gè)銷地需求20, 15, 20運(yùn)價(jià)表如下運(yùn)價(jià)c_{ij}銷地1銷地2銷地3產(chǎn)地1425產(chǎn)地2364from pulp import * # 定義問(wèn)題 prob LpProblem(Transportation_Problem, LpMinimize) # 供應(yīng)量和需求量 supply [30, 25] demand [20, 15, 20] # 運(yùn)價(jià)矩陣 costs [[4, 2, 5], [3, 6, 4]] # 創(chuàng)建決策變量字典 routes [(i, j) for i in range(2) for j in range(3)] x LpVariable.dicts(Route, (range(2), range(3)), lowBound0, catContinuous) # 目標(biāo)函數(shù)總運(yùn)費(fèi)最小 prob lpSum([x[i][j] * costs[i][j] for (i, j) in routes]) # 供應(yīng)約束 for i in range(2): prob lpSum([x[i][j] for j in range(3)]) supply[i], fSupply_Constraint_{i} # 需求約束 for j in range(3): prob lpSum([x[i][j] for i in range(2)]) demand[j], fDemand_Constraint_{j} # 求解 prob.solve() # 輸出結(jié)果 print(Status:, LpStatus[prob.status]) print(Minimum Total Cost , value(prob.objective)) print(\nOptimal Shipping Plan:) for i in range(2): for j in range(3): if x[i][j].varValue 0: print(f From Plant {i1} to Market {j1}: {x[i][j].varValue} units)運(yùn)行后你會(huì)得到最優(yōu)調(diào)運(yùn)方案和最小總運(yùn)費(fèi)。這個(gè)模型可以輕松擴(kuò)展到幾十上百個(gè)產(chǎn)地銷地。4.3 模型變體與擴(kuò)展運(yùn)輸問(wèn)題是基礎(chǔ)現(xiàn)實(shí)問(wèn)題往往更復(fù)雜由此衍生出許多變體產(chǎn)銷不平衡問(wèn)題供應(yīng)大于需求或需求大于供應(yīng)。處理方法是引入虛擬銷地庫(kù)存或虛擬產(chǎn)地缺貨并賦予相應(yīng)的運(yùn)價(jià)庫(kù)存成本或缺貨損失。轉(zhuǎn)運(yùn)問(wèn)題物資可以從產(chǎn)地直接到銷地也可以經(jīng)過(guò)中間轉(zhuǎn)運(yùn)點(diǎn)。決策變量變?yōu)閤_{ikj}從i經(jīng)k到j(luò)模型會(huì)更大。帶容量限制的運(yùn)輸問(wèn)題某些路線有運(yùn)輸能力上限增加約束x_{ij} ≤ u_{ij}。多商品運(yùn)輸問(wèn)題同時(shí)運(yùn)輸多種貨物共享運(yùn)力。這通常需要更復(fù)雜的建模可能涉及整數(shù)變量來(lái)處理固定成本或邏輯約束。實(shí)操心得運(yùn)輸問(wèn)題及其變體是數(shù)學(xué)建模競(jìng)賽的常客。關(guān)鍵在于準(zhǔn)確識(shí)別問(wèn)題本質(zhì)是不是分配流量有沒(méi)有供需平衡有沒(méi)有中間節(jié)點(diǎn)一旦識(shí)別為運(yùn)輸網(wǎng)絡(luò)流問(wèn)題建模框架就非常固定了。難點(diǎn)往往在于數(shù)據(jù)的處理和模型的規(guī)模控制。對(duì)于大規(guī)模問(wèn)題可以考慮先進(jìn)行聚類如將鄰近的客戶點(diǎn)合并或者利用問(wèn)題的特殊結(jié)構(gòu)設(shè)計(jì)啟發(fā)式算法求初始解。5. 規(guī)劃模型實(shí)戰(zhàn)中的常見(jiàn)陷阱與進(jìn)階技巧掌握了基本流程和經(jīng)典模型后要想在實(shí)戰(zhàn)中游刃有余還需要了解一些常見(jiàn)的“坑”和進(jìn)階技巧。5.1 新手常犯的五個(gè)錯(cuò)誤變量定義不清或冗余決策變量必須能完全控制且相互獨(dú)立。避免定義出可由其他變量計(jì)算得出的變量。例如在排班問(wèn)題中直接定義“第i天第j個(gè)班次的人數(shù)”即可不必再定義一個(gè)“總?cè)藬?shù)”變量。約束遺漏或錯(cuò)誤最容易遺漏的是“非負(fù)約束”或“整數(shù)約束”。更隱蔽的是邏輯約束例如“如果選擇項(xiàng)目A則必須同時(shí)選擇項(xiàng)目B”這需要用0-1變量和x_A ≤ x_B這樣的約束來(lái)表達(dá)。單位不統(tǒng)一如前所述這是致命錯(cuò)誤。建模前先將所有數(shù)據(jù)統(tǒng)一到同一度量體系下。模型不可行或無(wú)界不可行約束條件互相矛盾沒(méi)有解。例如要求產(chǎn)量既大于100又小于50。需要檢查約束條件是否過(guò)嚴(yán)或存在矛盾。無(wú)界目標(biāo)函數(shù)值可以無(wú)限優(yōu)化如利潤(rùn)無(wú)限大。通常是因?yàn)檫z漏了關(guān)鍵的資源約束。例如只追求利潤(rùn)最大化卻沒(méi)限制生產(chǎn)能力。忽略靈敏度分析只給出一個(gè)最優(yōu)解是遠(yuǎn)遠(yuǎn)不夠的。告訴決策者“這個(gè)方案在目前條件下最優(yōu)”的同時(shí)更要說(shuō)明“如果某個(gè)條件變化方案會(huì)如何變化利潤(rùn)會(huì)如何變化”這才是模型價(jià)值的體現(xiàn)。5.2 處理復(fù)雜約束的建模技巧現(xiàn)實(shí)約束往往不是簡(jiǎn)單的線性不等式需要一些技巧將其“線性化”。固定成本問(wèn)題生產(chǎn)某種產(chǎn)品有固定成本如設(shè)備啟動(dòng)費(fèi)只有產(chǎn)量大于0時(shí)才發(fā)生。設(shè)y為0-1變量是否生產(chǎn)x為產(chǎn)量M為一個(gè)足夠大的數(shù)Big-M法。目標(biāo)函數(shù)中加入f * yf為固定成本。添加約束x ≤ M * y。當(dāng)y0時(shí)x必須為0當(dāng)y1時(shí)x可以大于0但受其他約束限制。邏輯約束互斥選擇在多個(gè)選項(xiàng)中至多選一個(gè)。Σ y_i ≤ 1。依賴關(guān)系如果選A則必須選B。y_A ≤ y_B。條件觸發(fā)如果產(chǎn)量x 0則必須支付固定成本。這又回到了固定成本問(wèn)題用Big-M法。分段函數(shù)如運(yùn)費(fèi)有折扣采購(gòu)量不同單價(jià)不同。可以引入多個(gè)0-1變量來(lái)表示處于哪個(gè)區(qū)間并添加相應(yīng)的邏輯約束。5.3 求解失敗怎么辦調(diào)試與簡(jiǎn)化策略當(dāng)模型求解時(shí)間過(guò)長(zhǎng)、報(bào)錯(cuò)或無(wú)解時(shí)可以嘗試以下策略從簡(jiǎn)化模型開始先去掉整數(shù)約束求解線性松弛問(wèn)題。如果松弛問(wèn)題都不可行說(shuō)明約束本身有問(wèn)題。如果松弛問(wèn)題可行且解是整數(shù)那恭喜你它就是原問(wèn)題的最優(yōu)解。檢查Big-M的值如果使用了Big-M法M的值不能太小否則可能割掉可行解也不能太大否則會(huì)導(dǎo)致數(shù)值計(jì)算困難影響求解。M應(yīng)略大于對(duì)應(yīng)變量的理論上限。提供初始解許多求解器允許用戶提供一個(gè)可行的初始解這能大大加快分支定界法的求解速度尤其是對(duì)整數(shù)規(guī)劃。調(diào)整求解器參數(shù)對(duì)于整數(shù)規(guī)劃可以設(shè)置最大求解時(shí)間、相對(duì)/絕對(duì)最優(yōu)間隙Gap。例如設(shè)定在1%的Gap內(nèi)停止可以快速得到一個(gè)高質(zhì)量的近似解而不必追求絕對(duì)最優(yōu)。分解與降維對(duì)于超大規(guī)模問(wèn)題看是否能分解成若干獨(dú)立的子問(wèn)題或者通過(guò)聚合如按區(qū)域合并客戶來(lái)降低問(wèn)題規(guī)模。5.4 從模型到論文如何清晰表達(dá)在數(shù)學(xué)建模競(jìng)賽或項(xiàng)目報(bào)告中模型的表達(dá)和結(jié)果的呈現(xiàn)與建模本身同樣重要。模型部分符號(hào)說(shuō)明表用一個(gè)三列表格清晰列出所有決策變量、參數(shù)和符號(hào)的含義及單位。這是專業(yè)性的體現(xiàn)。公式完整呈現(xiàn)將目標(biāo)函數(shù)和所有約束條件完整、美觀地列出。可以使用公式編輯器。闡述建模思路不要只扔出公式要用文字解釋“為什么這樣建模”特別是處理復(fù)雜約束的邏輯。結(jié)果部分圖表結(jié)合最優(yōu)方案用表格清晰列出。靈敏度分析結(jié)果用圖表展示如參數(shù)變化對(duì)目標(biāo)值的影響曲線。管理摘要在報(bào)告開頭用一兩段話概括問(wèn)題、方法、核心結(jié)論和建議。讓非技術(shù)決策者也能快速抓住重點(diǎn)。討論局限性誠(chéng)實(shí)地指出模型的假設(shè)和局限性如假設(shè)需求恒定、忽略運(yùn)輸時(shí)間等并提出未來(lái)改進(jìn)方向。這體現(xiàn)了思考的深度。規(guī)劃模型是連接數(shù)學(xué)世界與現(xiàn)實(shí)決策的堅(jiān)實(shí)橋梁。它要求我們既有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)思維又能深刻理解實(shí)際問(wèn)題。從看懂一個(gè)簡(jiǎn)單的生產(chǎn)計(jì)劃模型到自己動(dòng)手為復(fù)雜的物流網(wǎng)絡(luò)建立優(yōu)化模型這個(gè)過(guò)程充滿挑戰(zhàn)也極具成就感。記住多練、多思考、多總結(jié)每一次建模都是對(duì)你邏輯思維和解決問(wèn)題能力的一次錘煉。當(dāng)你拿到一個(gè)雜亂的實(shí)際問(wèn)題能迅速抽絲剝繭將其轉(zhuǎn)化為清晰的數(shù)學(xué)語(yǔ)言并求解時(shí)你就真正掌握了這項(xiàng)強(qiáng)大的工具。 數(shù)學(xué)建模規(guī)劃模型：從線性規(guī)劃到運(yùn)輸問(wèn)題的決策優(yōu)化實(shí)戰(zhàn)
1. 項(xiàng)目概述規(guī)劃模型數(shù)學(xué)建模的“決策大腦”如果你剛開始接觸數(shù)學(xué)建模或者正準(zhǔn)備參加相關(guān)的競(jìng)賽那么“規(guī)劃模型”這個(gè)概念你大概率是繞不開的。它不像一些復(fù)雜的算法那樣聽起來(lái)高深莫測(cè)但卻是解決一大類實(shí)際問(wèn)題的核心框架。簡(jiǎn)單來(lái)說(shuō)規(guī)劃模型就是數(shù)學(xué)建模中的“決策大腦”——當(dāng)你面對(duì)一堆資源、一堆任務(wù)、一堆限制條件需要找到一個(gè)“最優(yōu)”的行動(dòng)方案時(shí)規(guī)劃模型就是你的首選工具。想象一下你是一個(gè)工廠的生產(chǎn)主管手上有幾條生產(chǎn)線、幾種原材料、一批訂單還有電費(fèi)、人力成本等各種約束。你的目標(biāo)是在滿足所有訂單和資源限制的前提下讓總利潤(rùn)最高或者總成本最低。這個(gè)“怎么安排生產(chǎn)”的問(wèn)題本質(zhì)上就是一個(gè)規(guī)劃問(wèn)題。再比如物流公司要規(guī)劃配送路線在有限的車隊(duì)和時(shí)間內(nèi)把貨物送到各個(gè)客戶點(diǎn)同時(shí)讓總運(yùn)輸距離最短這也是規(guī)劃。甚至你個(gè)人安排一天的時(shí)間在有限的時(shí)間里完成學(xué)習(xí)、鍛煉、娛樂(lè)追求效率最大化這也可以抽象成一個(gè)簡(jiǎn)單的規(guī)劃模型。所以規(guī)劃模型的應(yīng)用場(chǎng)景極其廣泛從工業(yè)生產(chǎn)、交通運(yùn)輸、金融投資到日常生活中的資源分配無(wú)處不在。它的核心思想就是把一個(gè)現(xiàn)實(shí)中的決策問(wèn)題用數(shù)學(xué)語(yǔ)言主要是方程和不等式描述出來(lái)然后通過(guò)特定的數(shù)學(xué)方法求解出那個(gè)“最優(yōu)”的決策變量值。這個(gè)“最優(yōu)”在數(shù)學(xué)上通常表現(xiàn)為一個(gè)目標(biāo)函數(shù)的最大化或最小化比如利潤(rùn)最大、成本最小、時(shí)間最短、滿意度最高等等。對(duì)于初學(xué)者而言規(guī)劃模型是進(jìn)入數(shù)學(xué)建模實(shí)戰(zhàn)領(lǐng)域一個(gè)非常友好的起點(diǎn)。它邏輯清晰步驟相對(duì)規(guī)范從問(wèn)題分析、模型建立到求解驗(yàn)證有一套成熟的方法論。掌握了它你就能解決一大類有明確優(yōu)化目標(biāo)的決策問(wèn)題。接下來(lái)我們就深入拆解這個(gè)“決策大腦”的構(gòu)造與運(yùn)作原理。2. 規(guī)劃模型的核心思想與分類體系規(guī)劃模型或者說(shuō)數(shù)學(xué)規(guī)劃其核心思想可以概括為在滿足一系列約束條件的前提下尋找一組決策變量的取值使得某個(gè)特定的目標(biāo)函數(shù)達(dá)到最優(yōu)最大或最小。這句話包含了三個(gè)關(guān)鍵要素也是我們構(gòu)建任何規(guī)劃模型時(shí)必須明確的三件事決策變量這是我們能控制的東西是模型要求解的對(duì)象。比如生產(chǎn)多少產(chǎn)品A、多少產(chǎn)品B從倉(cāng)庫(kù)i到客戶j派多少輛車投資項(xiàng)目中分配多少資金給股票、多少給債券。通常用 x?, x?, ..., x? 或 x_{ij} 來(lái)表示。目標(biāo)函數(shù)這是我們追求的目標(biāo)的數(shù)學(xué)表達(dá)。它是一個(gè)關(guān)于決策變量的函數(shù)。我們就是要讓這個(gè)函數(shù)值盡可能大如利潤(rùn)、效率或盡可能小如成本、時(shí)間、風(fēng)險(xiǎn)。例如總利潤(rùn) Z 5x? 8x?總運(yùn)輸成本 C ΣΣ c_{ij} * x_{ij}。約束條件這是我們?cè)谧鰶Q策時(shí)必須遵守的限制。它們通常用關(guān)于決策變量的等式或不等式來(lái)表示。例如原材料消耗不能超過(guò)庫(kù)存不等式生產(chǎn)線每天的總工時(shí)有限不等式必須滿足所有客戶的需求等式或不等式。把這三大要素用數(shù)學(xué)符號(hào)清晰地寫出來(lái)一個(gè)規(guī)劃模型就初步建立了。根據(jù)目標(biāo)函數(shù)和約束條件的形式不同規(guī)劃模型可以分為幾大類每種類型都有其適用的場(chǎng)景和求解方法。2.1 線性規(guī)劃最簡(jiǎn)單也最基礎(chǔ)如果目標(biāo)函數(shù)和所有約束條件都是決策變量的線性表達(dá)式即沒(méi)有平方、乘積、指數(shù)、對(duì)數(shù)等非線性項(xiàng)那么這個(gè)模型就是線性規(guī)劃。特點(diǎn)與適用場(chǎng)景形式簡(jiǎn)單Max/Min Z c?x? c?x? ... c?x?約束條件a??x? a??x? ... a??x? ≤ (或 , ≥) b?a??x? a??x? ... a??x? ≤ (或 , ≥) b?...求解成熟有非常成熟且高效的算法如單純形法、內(nèi)點(diǎn)法。利用MATLAB、PythonSciPy, PuLP、Lingo等工具可以輕松求解。應(yīng)用廣泛資源分配、生產(chǎn)計(jì)劃、配料問(wèn)題、運(yùn)輸問(wèn)題等。例如經(jīng)典的“食譜問(wèn)題”用最少的成本滿足營(yíng)養(yǎng)需求和“運(yùn)輸問(wèn)題”最小化總運(yùn)費(fèi)。注意線性規(guī)劃的最優(yōu)解如果存在通常會(huì)在約束條件構(gòu)成的“可行域”的頂點(diǎn)上取得。這是單純形法能夠高效工作的理論基礎(chǔ)。2.2 整數(shù)規(guī)劃與0-1規(guī)劃當(dāng)決策必須是整數(shù)時(shí)在線性規(guī)劃的基礎(chǔ)上如果要求全部或部分決策變量必須取整數(shù)值就變成了整數(shù)規(guī)劃。其中一種特殊且極其重要的情形是0-1規(guī)劃即決策變量只能取0或1通常用于表示“是/否”、“選擇/不選擇”這類邏輯決策。特點(diǎn)與適用場(chǎng)景組合爆炸即使問(wèn)題規(guī)模不大求解難度也可能遠(yuǎn)高于線性規(guī)劃屬于NP-hard問(wèn)題。建模靈活0-1變量是建模的“瑞士軍刀”可以處理固定成本、邏輯關(guān)系如果…那么…、互斥選擇等復(fù)雜條件。典型應(yīng)用背包問(wèn)題在容量有限的背包里選擇物品使總價(jià)值最大。每個(gè)物品要么選1要么不選0。指派問(wèn)題將若干任務(wù)分配給若干人每人只做一個(gè)任務(wù)每個(gè)任務(wù)只由一人完成如何使總成本最小或總效率最高用x_{ij}0或1表示“是否將任務(wù)i分配給人j”。選址問(wèn)題在若干個(gè)候選地點(diǎn)中選擇幾個(gè)建立工廠或倉(cāng)庫(kù)需要決策在哪個(gè)地點(diǎn)建0-1變量以及從選址點(diǎn)運(yùn)出多少貨物連續(xù)或整數(shù)變量。求解方法分支定界法、割平面法是主流精確算法。對(duì)于大規(guī)模問(wèn)題常采用啟發(fā)式算法如遺傳算法、模擬退火求近似最優(yōu)解。2.3 非線性規(guī)劃現(xiàn)實(shí)世界的復(fù)雜關(guān)系當(dāng)目標(biāo)函數(shù)或約束條件中至少有一個(gè)是決策變量的非線性函數(shù)時(shí)就是非線性規(guī)劃。現(xiàn)實(shí)世界中的關(guān)系遠(yuǎn)比線性復(fù)雜比如成本隨產(chǎn)量增加而邊際遞減經(jīng)濟(jì)學(xué)中的規(guī)模效應(yīng)或者距離計(jì)算涉及平方和開根號(hào)。特點(diǎn)與適用場(chǎng)景模型更貼近現(xiàn)實(shí)能描述更復(fù)雜的經(jīng)濟(jì)、物理、工程關(guān)系。求解困難沒(méi)有通用的、像單純形法那樣高效的算法。最優(yōu)解可能不是全局最優(yōu)而是局部最優(yōu)且求解過(guò)程對(duì)初始值敏感。常見(jiàn)類型二次規(guī)劃目標(biāo)函數(shù)是二次函數(shù)約束為線性。在投資組合優(yōu)化風(fēng)險(xiǎn)最小化中常見(jiàn)。幾何規(guī)劃、凸規(guī)劃如果問(wèn)題具有凸性則局部最優(yōu)就是全局最優(yōu)相對(duì)容易求解。求解工具M(jìn)ATLAB的fminconPython的SciPy.optimize模塊以及專業(yè)的優(yōu)化求解器如Gurobi、CPLEX也支持部分非線性。2.4 多目標(biāo)規(guī)劃?rùn)?quán)衡的藝術(shù)現(xiàn)實(shí)中我們往往不止追求一個(gè)目標(biāo)。企業(yè)既要利潤(rùn)最大化又要風(fēng)險(xiǎn)最小化還要市場(chǎng)份額增長(zhǎng)。這就是多目標(biāo)規(guī)劃要解決的問(wèn)題在多個(gè)相互沖突的目標(biāo)之間尋找平衡。核心思想 不存在一個(gè)解能讓所有目標(biāo)同時(shí)達(dá)到最優(yōu)而是存在一個(gè)“帕累托最優(yōu)”解集。在這個(gè)解集中你無(wú)法在不損害至少一個(gè)其他目標(biāo)的情況下改進(jìn)任何一個(gè)目標(biāo)。處理方法化多為單將多個(gè)目標(biāo)通過(guò)加權(quán)求和、優(yōu)先級(jí)排序目標(biāo)規(guī)劃或選擇一個(gè)主要目標(biāo)、其余轉(zhuǎn)為約束等方式轉(zhuǎn)化為單目標(biāo)問(wèn)題。交互式方法決策者參與求解過(guò)程根據(jù)當(dāng)前解不斷調(diào)整偏好逐步逼近最滿意的解。智能優(yōu)化算法如多目標(biāo)遺傳算法NSGA-II可以直接生成一組近似帕累托最優(yōu)解前沿面供決策者選擇。實(shí)操心得在數(shù)學(xué)建模競(jìng)賽中多目標(biāo)問(wèn)題非常常見(jiàn)。一個(gè)實(shí)用的技巧是先分別對(duì)每個(gè)單目標(biāo)求解了解其理想值和邊界再通過(guò)加權(quán)法權(quán)重需要靈敏度分析或ε-約束法將一個(gè)目標(biāo)轉(zhuǎn)為約束約束右端項(xiàng)由另一個(gè)目標(biāo)的最優(yōu)值放松得到來(lái)尋找折中解。在論文中清晰地展示這個(gè)權(quán)衡過(guò)程比直接給出一個(gè)解更重要。3. 從問(wèn)題到模型五步建模法實(shí)戰(zhàn)拆解建立一個(gè)可求解的規(guī)劃模型不能只靠靈感需要一個(gè)結(jié)構(gòu)化的思考過(guò)程。這里我結(jié)合多年經(jīng)驗(yàn)總結(jié)出一個(gè)五步法它幾乎適用于所有規(guī)劃類問(wèn)題。3.1 第一步問(wèn)題界定與目標(biāo)梳理這一步看似簡(jiǎn)單卻至關(guān)重要。你必須回答到底要解決什么問(wèn)題決策者是誰(shuí)成功的標(biāo)準(zhǔn)是什么明確決策變量問(wèn)自己“我們能控制什么”把答案量化成變量。例如控制“生產(chǎn)量”變量就是x_A產(chǎn)品A的產(chǎn)量、x_B產(chǎn)品B的產(chǎn)量。明確優(yōu)化目標(biāo)問(wèn)自己“我們最終想要什么”是最大化利潤(rùn)、最小化成本、最短化時(shí)間還是最大化滿意度用數(shù)學(xué)語(yǔ)言描述它和決策變量的關(guān)系。有時(shí)目標(biāo)不止一個(gè)需要記錄下來(lái)。識(shí)別約束條件問(wèn)自己“我們受到哪些限制”資源人力、物料、資金、時(shí)間是有限的市場(chǎng)需求、合同要求、物理定律如容量限制必須滿足決策變量本身可能有范圍非負(fù)、整數(shù)。技巧用一句話概括問(wèn)題“在____的限制下通過(guò)調(diào)整____來(lái)實(shí)現(xiàn)____的最優(yōu)。” 這句話的空白處填上的內(nèi)容就是模型的骨架。3.2 第二步數(shù)據(jù)收集與參數(shù)定義模型中的數(shù)字不是憑空想象的。目標(biāo)函數(shù)里的系數(shù)如單位利潤(rùn)、約束條件里的系數(shù)如單位產(chǎn)品耗材和右端項(xiàng)如資源總量都需要基于實(shí)際數(shù)據(jù)或合理假設(shè)。參數(shù)類型效益型參數(shù)在目標(biāo)函數(shù)中與最大化目標(biāo)正相關(guān)如售價(jià)、效率。成本型參數(shù)在目標(biāo)函數(shù)中與最小化目標(biāo)正相關(guān)如成本、時(shí)間、距離。技術(shù)系數(shù)在約束條件中連接決策變量和資源消耗如生產(chǎn)單位產(chǎn)品所需的工時(shí)、原料。資源限量約束條件的右端項(xiàng)如總工時(shí)、原料庫(kù)存、預(yù)算上限。數(shù)據(jù)來(lái)源歷史數(shù)據(jù)、市場(chǎng)調(diào)研、技術(shù)手冊(cè)、合理估算。在建模競(jìng)賽中數(shù)據(jù)可能由賽題給出也可能需要自己搜集或合理假設(shè)。注意事項(xiàng)數(shù)據(jù)的單位必須統(tǒng)一這是新手常犯的錯(cuò)誤。如果目標(biāo)函數(shù)是“利潤(rùn)元”那么成本、售價(jià)的單位都必須是“元”。如果約束條件是“工時(shí)小時(shí)”那么單位產(chǎn)品耗時(shí)的單位也必須是“小時(shí)/件”。單位不一致會(huì)導(dǎo)致模型完全錯(cuò)誤。3.3 第三步數(shù)學(xué)公式構(gòu)建這是將前兩步的思考成果用嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)語(yǔ)言書寫出來(lái)的過(guò)程。要求清晰、完整、無(wú)歧義。以一個(gè)小型生產(chǎn)計(jì)劃問(wèn)題為例某工廠生產(chǎn)兩種產(chǎn)品A和B。生產(chǎn)一件A產(chǎn)品利潤(rùn)3元耗時(shí)2小時(shí)耗材4公斤生產(chǎn)一件B產(chǎn)品利潤(rùn)5元耗時(shí)3小時(shí)耗材2公斤。工廠每天可用工時(shí)為100小時(shí)原料庫(kù)存為80公斤。問(wèn)每天如何安排生產(chǎn)使利潤(rùn)最大定義決策變量設(shè)x1為產(chǎn)品A的日產(chǎn)量x2為產(chǎn)品B的日產(chǎn)量。建立目標(biāo)函數(shù)總利潤(rùn)Z 3*x1 5*x2目標(biāo)是最大化Max Z。列出約束條件工時(shí)約束2*x1 3*x2 ≤ 100生產(chǎn)總耗時(shí)不超過(guò)100小時(shí)原料約束4*x1 2*x2 ≤ 80消耗原料不超過(guò)80公斤非負(fù)約束x1 ≥ 0, x2 ≥ 0產(chǎn)量不能為負(fù)完整模型Max Z 3*x1 5*x2 s.t. (subject to) 2*x1 3*x2 ≤ 100 4*x1 2*x2 ≤ 80 x1, x2 ≥ 0這就是一個(gè)完整的線性規(guī)劃模型。3.4 第四步模型求解與工具選擇模型建立后就需要求解。選擇什么工具取決于模型的類型和規(guī)模。模型類型推薦工具/軟件關(guān)鍵命令/函數(shù)示例適用場(chǎng)景中小型線性/整數(shù)規(guī)劃Lingo語(yǔ)法接近數(shù)學(xué)公式直接輸入模型即可求解。教學(xué)、快速原型驗(yàn)證、中小規(guī)模問(wèn)題。通用科學(xué)計(jì)算MATLABlinprog(線性),intlinprog(整數(shù)),fmincon(非線性)學(xué)術(shù)界常用與仿真、數(shù)據(jù)分析結(jié)合緊密。編程與算法開發(fā)PythonSciPy.optimize.linprog,PuLP庫(kù),ortools庫(kù)靈活性最高易于集成到數(shù)據(jù)管道和Web應(yīng)用中開源免費(fèi)。大規(guī)模復(fù)雜商業(yè)問(wèn)題專業(yè)求解器(Gurobi, CPLEX)通過(guò)其APIPython, Java等調(diào)用工業(yè)級(jí)應(yīng)用求解速度最快支持模型類型最全含非線性。求解過(guò)程實(shí)錄以Python PuLP庫(kù)求解上述生產(chǎn)問(wèn)題為例# 導(dǎo)入PuLP庫(kù) from pulp import * # 創(chuàng)建問(wèn)題指定名稱和優(yōu)化方向最大化 prob LpProblem(Simple_Production_Problem, LpMaximize) # 定義決策變量lowBound指定下界非負(fù) x1 LpVariable(Product_A, lowBound0, catContinuous) # 連續(xù)變量 x2 LpVariable(Product_B, lowBound0, catContinuous) # 定義目標(biāo)函數(shù) prob 3*x1 5*x2, Total_Profit # 添加約束條件 prob 2*x1 3*x2 100, Labor_Constraint prob 4*x1 2*x2 80, Material_Constraint # 求解問(wèn)題 prob.solve() # 打印求解狀態(tài)和結(jié)果 print(Status:, LpStatus[prob.status]) print(Optimal Production Plan:) print(f Product A: {x1.varValue} units) print(f Product B: {x2.varValue} units) print(fMaximum Profit: {value(prob.objective)})運(yùn)行后你會(huì)得到最優(yōu)解x10, x240, Z200。這意味著全部生產(chǎn)產(chǎn)品B利潤(rùn)最大。這個(gè)結(jié)果可能有點(diǎn)反直覺(jué)為什么利潤(rùn)低一點(diǎn)的A完全不生產(chǎn)這就需要下一步的分析。3.5 第五步結(jié)果分析與模型檢驗(yàn)求出解不是終點(diǎn)分析解的含義和模型的合理性才是關(guān)鍵。解的解釋將數(shù)學(xué)解“翻譯”回實(shí)際問(wèn)題。如上例應(yīng)建議工廠“每天生產(chǎn)40件B產(chǎn)品不生產(chǎn)A產(chǎn)品可獲得最大利潤(rùn)200元。”靈敏度分析關(guān)鍵研究模型參數(shù)目標(biāo)函數(shù)系數(shù)、約束右端項(xiàng)的微小變化對(duì)最優(yōu)解的影響。這回答了決策者更關(guān)心的問(wèn)題產(chǎn)品B的利潤(rùn)下降多少我們才需要考慮生產(chǎn)A分析目標(biāo)函數(shù)系數(shù)如果加班增加10個(gè)工時(shí)利潤(rùn)能增加多少分析約束右端項(xiàng)即“影子價(jià)格”在Lingo、MATLAB或?qū)I(yè)求解器的輸出中通常直接包含靈敏度分析報(bào)告。模型檢驗(yàn)與穩(wěn)健性檢查解是否合理如上例全部生產(chǎn)B原料剛好用完2*4080但工時(shí)剩余3*40120 100?等等這里計(jì)算有誤我們重新檢查3*40120但工時(shí)約束是≤100120100這違反了約束這是一個(gè)非常重要的發(fā)現(xiàn)重新審視模型我們的求解顯示x240代入工時(shí)約束2*0 3*40 120 100這違反了第一個(gè)約束這說(shuō)明我們要么模型輸入有誤要么求解理解有誤。實(shí)際上用圖解法或重新求解例如用更精確的工具會(huì)發(fā)現(xiàn)此問(wèn)題的最優(yōu)解應(yīng)在工時(shí)和原料約束的交點(diǎn)附近。讓我們糾正并重新分析。糾正后的求解與深入分析 實(shí)際上兩個(gè)約束是2x1 3x2 ≤ 1004x1 2x2 ≤ 80用圖解法或單純形法求得最優(yōu)解為x1 10, x2 20。此時(shí)利潤(rùn)Z 3*10 5*20 130工時(shí)消耗2*10 3*20 80 ≤ 100原料消耗4*10 2*20 80 ≤ 80靈敏度分析示例影子價(jià)格原料約束的影子價(jià)格會(huì)比工時(shí)約束高因?yàn)樵显谧顑?yōu)解下是“緊約束”用完80公斤而工時(shí)還有20小時(shí)剩余是“松約束”。增加一公斤原料帶來(lái)的利潤(rùn)提升影子價(jià)格比增加一工時(shí)要大。目標(biāo)系數(shù)范圍產(chǎn)品B的利潤(rùn)系數(shù)5在當(dāng)前最優(yōu)解10,20保持不變的允許變化范圍是多少如果B利潤(rùn)降到某個(gè)值以下最優(yōu)解可能會(huì)變成多生產(chǎn)A。這個(gè)“發(fā)現(xiàn)錯(cuò)誤-糾正-再分析”的過(guò)程恰恰是模型檢驗(yàn)的核心。它告訴我們永遠(yuǎn)不要盲目相信求解器的第一個(gè)輸出必須將解代回原問(wèn)題和約束進(jìn)行驗(yàn)證并思考其實(shí)際意義。4. 經(jīng)典模型案例深度剖析運(yùn)輸問(wèn)題為了讓大家更好地掌握規(guī)劃模型的完整應(yīng)用流程我們剖析一個(gè)經(jīng)典案例運(yùn)輸問(wèn)題。它結(jié)構(gòu)清晰是學(xué)習(xí)整數(shù)規(guī)劃和線性規(guī)劃的絕佳例題。4.1 問(wèn)題描述與模型建立問(wèn)題有m個(gè)產(chǎn)地倉(cāng)庫(kù)/工廠A1, A2, ..., Am其供應(yīng)量分別為a1, a2, ..., am。有n個(gè)銷地市場(chǎng)/客戶B1, B2, ..., Bn其需求量分別為b1, b2, ..., bn。從產(chǎn)地i到銷地j的單位物資運(yùn)價(jià)為c_{ij}。問(wèn)如何調(diào)運(yùn)物資才能在滿足供需平衡的前提下使總運(yùn)輸費(fèi)用最小假設(shè)總供應(yīng)量等于總需求量即Σa_i Σb_j。這是“平衡運(yùn)輸問(wèn)題”。如果不平衡可以通過(guò)增設(shè)虛擬產(chǎn)地或銷地化為平衡問(wèn)題。建模步驟決策變量設(shè)x_{ij}為從產(chǎn)地i運(yùn)往銷地j的物資數(shù)量。這是我們要決定的。目標(biāo)函數(shù)總運(yùn)費(fèi)最小化。Min Z Σ_{i1}^{m} Σ_{j1}^{n} c_{ij} * x_{ij}約束條件供應(yīng)約束從每個(gè)產(chǎn)地i運(yùn)出的總量等于其供應(yīng)量。Σ_{j1}^{n} x_{ij} a_i, for all i.需求約束運(yùn)到每個(gè)銷地j的總量等于其需求量。Σ_{i1}^{m} x_{ij} b_j, for all j.非負(fù)約束運(yùn)量不能為負(fù)。x_{ij} ≥ 0。這是一個(gè)典型的線性規(guī)劃模型由于其約束矩陣的特殊結(jié)構(gòu)每列只有兩個(gè)1存在比單純形法更高效的專門算法如表上作業(yè)法。4.2 求解方法從表上作業(yè)法到軟件求解1. 表上作業(yè)法手工/理解原理 適用于規(guī)模較小的問(wèn)題有助于理解運(yùn)輸問(wèn)題的本質(zhì)。其核心步驟是Step1: 編制運(yùn)價(jià)表和產(chǎn)銷平衡表。Step2: 尋找初始基可行解。常用方法有最小元素法優(yōu)先安排運(yùn)價(jià)最低的路線或伏格爾法考慮次小運(yùn)費(fèi)結(jié)果往往更好。Step3: 最優(yōu)性檢驗(yàn)。計(jì)算每個(gè)非基變量空格的檢驗(yàn)數(shù)位勢(shì)法。若所有檢驗(yàn)數(shù)≥0則當(dāng)前解最優(yōu)否則轉(zhuǎn)入下一步。Step4: 閉回路調(diào)整。選取負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的空格尋找一條閉合回路沿回路調(diào)整運(yùn)量得到新的調(diào)運(yùn)方案。返回Step3。2. 軟件求解實(shí)際應(yīng)用 對(duì)于任何規(guī)模的運(yùn)輸問(wèn)題用規(guī)劃求解軟件都是最直接的方式。我們將其轉(zhuǎn)化為線性規(guī)劃模型輸入即可。Python PuLP 求解示例 假設(shè)有2個(gè)產(chǎn)地供應(yīng)30, 253個(gè)銷地需求20, 15, 20運(yùn)價(jià)表如下運(yùn)價(jià)c_{ij}銷地1銷地2銷地3產(chǎn)地1425產(chǎn)地2364from pulp import * # 定義問(wèn)題 prob LpProblem(Transportation_Problem, LpMinimize) # 供應(yīng)量和需求量 supply [30, 25] demand [20, 15, 20] # 運(yùn)價(jià)矩陣 costs [[4, 2, 5], [3, 6, 4]] # 創(chuàng)建決策變量字典 routes [(i, j) for i in range(2) for j in range(3)] x LpVariable.dicts(Route, (range(2), range(3)), lowBound0, catContinuous) # 目標(biāo)函數(shù)總運(yùn)費(fèi)最小 prob lpSum([x[i][j] * costs[i][j] for (i, j) in routes]) # 供應(yīng)約束 for i in range(2): prob lpSum([x[i][j] for j in range(3)]) supply[i], fSupply_Constraint_{i} # 需求約束 for j in range(3): prob lpSum([x[i][j] for i in range(2)]) demand[j], fDemand_Constraint_{j} # 求解 prob.solve() # 輸出結(jié)果 print(Status:, LpStatus[prob.status]) print(Minimum Total Cost , value(prob.objective)) print(\nOptimal Shipping Plan:) for i in range(2): for j in range(3): if x[i][j].varValue 0: print(f From Plant {i1} to Market {j1}: {x[i][j].varValue} units)運(yùn)行后你會(huì)得到最優(yōu)調(diào)運(yùn)方案和最小總運(yùn)費(fèi)。這個(gè)模型可以輕松擴(kuò)展到幾十上百個(gè)產(chǎn)地銷地。4.3 模型變體與擴(kuò)展運(yùn)輸問(wèn)題是基礎(chǔ)現(xiàn)實(shí)問(wèn)題往往更復(fù)雜由此衍生出許多變體產(chǎn)銷不平衡問(wèn)題供應(yīng)大于需求或需求大于供應(yīng)。處理方法是引入虛擬銷地庫(kù)存或虛擬產(chǎn)地缺貨并賦予相應(yīng)的運(yùn)價(jià)庫(kù)存成本或缺貨損失。轉(zhuǎn)運(yùn)問(wèn)題物資可以從產(chǎn)地直接到銷地也可以經(jīng)過(guò)中間轉(zhuǎn)運(yùn)點(diǎn)。決策變量變?yōu)閤_{ikj}從i經(jīng)k到j(luò)模型會(huì)更大。帶容量限制的運(yùn)輸問(wèn)題某些路線有運(yùn)輸能力上限增加約束x_{ij} ≤ u_{ij}。多商品運(yùn)輸問(wèn)題同時(shí)運(yùn)輸多種貨物共享運(yùn)力。這通常需要更復(fù)雜的建模可能涉及整數(shù)變量來(lái)處理固定成本或邏輯約束。實(shí)操心得運(yùn)輸問(wèn)題及其變體是數(shù)學(xué)建模競(jìng)賽的常客。關(guān)鍵在于準(zhǔn)確識(shí)別問(wèn)題本質(zhì)是不是分配流量有沒(méi)有供需平衡有沒(méi)有中間節(jié)點(diǎn)一旦識(shí)別為運(yùn)輸網(wǎng)絡(luò)流問(wèn)題建模框架就非常固定了。難點(diǎn)往往在于數(shù)據(jù)的處理和模型的規(guī)模控制。對(duì)于大規(guī)模問(wèn)題可以考慮先進(jìn)行聚類如將鄰近的客戶點(diǎn)合并或者利用問(wèn)題的特殊結(jié)構(gòu)設(shè)計(jì)啟發(fā)式算法求初始解。5. 規(guī)劃模型實(shí)戰(zhàn)中的常見(jiàn)陷阱與進(jìn)階技巧掌握了基本流程和經(jīng)典模型后要想在實(shí)戰(zhàn)中游刃有余還需要了解一些常見(jiàn)的“坑”和進(jìn)階技巧。5.1 新手常犯的五個(gè)錯(cuò)誤變量定義不清或冗余決策變量必須能完全控制且相互獨(dú)立。避免定義出可由其他變量計(jì)算得出的變量。例如在排班問(wèn)題中直接定義“第i天第j個(gè)班次的人數(shù)”即可不必再定義一個(gè)“總?cè)藬?shù)”變量。約束遺漏或錯(cuò)誤最容易遺漏的是“非負(fù)約束”或“整數(shù)約束”。更隱蔽的是邏輯約束例如“如果選擇項(xiàng)目A則必須同時(shí)選擇項(xiàng)目B”這需要用0-1變量和x_A ≤ x_B這樣的約束來(lái)表達(dá)。單位不統(tǒng)一如前所述這是致命錯(cuò)誤。建模前先將所有數(shù)據(jù)統(tǒng)一到同一度量體系下。模型不可行或無(wú)界不可行約束條件互相矛盾沒(méi)有解。例如要求產(chǎn)量既大于100又小于50。需要檢查約束條件是否過(guò)嚴(yán)或存在矛盾。無(wú)界目標(biāo)函數(shù)值可以無(wú)限優(yōu)化如利潤(rùn)無(wú)限大。通常是因?yàn)檫z漏了關(guān)鍵的資源約束。例如只追求利潤(rùn)最大化卻沒(méi)限制生產(chǎn)能力。忽略靈敏度分析只給出一個(gè)最優(yōu)解是遠(yuǎn)遠(yuǎn)不夠的。告訴決策者“這個(gè)方案在目前條件下最優(yōu)”的同時(shí)更要說(shuō)明“如果某個(gè)條件變化方案會(huì)如何變化利潤(rùn)會(huì)如何變化”這才是模型價(jià)值的體現(xiàn)。5.2 處理復(fù)雜約束的建模技巧現(xiàn)實(shí)約束往往不是簡(jiǎn)單的線性不等式需要一些技巧將其“線性化”。固定成本問(wèn)題生產(chǎn)某種產(chǎn)品有固定成本如設(shè)備啟動(dòng)費(fèi)只有產(chǎn)量大于0時(shí)才發(fā)生。設(shè)y為0-1變量是否生產(chǎn)x為產(chǎn)量M為一個(gè)足夠大的數(shù)Big-M法。目標(biāo)函數(shù)中加入f * yf為固定成本。添加約束x ≤ M * y。當(dāng)y0時(shí)x必須為0當(dāng)y1時(shí)x可以大于0但受其他約束限制。邏輯約束互斥選擇在多個(gè)選項(xiàng)中至多選一個(gè)。Σ y_i ≤ 1。依賴關(guān)系如果選A則必須選B。y_A ≤ y_B。條件觸發(fā)如果產(chǎn)量x 0則必須支付固定成本。這又回到了固定成本問(wèn)題用Big-M法。分段函數(shù)如運(yùn)費(fèi)有折扣采購(gòu)量不同單價(jià)不同。可以引入多個(gè)0-1變量來(lái)表示處于哪個(gè)區(qū)間并添加相應(yīng)的邏輯約束。5.3 求解失敗怎么辦調(diào)試與簡(jiǎn)化策略當(dāng)模型求解時(shí)間過(guò)長(zhǎng)、報(bào)錯(cuò)或無(wú)解時(shí)可以嘗試以下策略從簡(jiǎn)化模型開始先去掉整數(shù)約束求解線性松弛問(wèn)題。如果松弛問(wèn)題都不可行說(shuō)明約束本身有問(wèn)題。如果松弛問(wèn)題可行且解是整數(shù)那恭喜你它就是原問(wèn)題的最優(yōu)解。檢查Big-M的值如果使用了Big-M法M的值不能太小否則可能割掉可行解也不能太大否則會(huì)導(dǎo)致數(shù)值計(jì)算困難影響求解。M應(yīng)略大于對(duì)應(yīng)變量的理論上限。提供初始解許多求解器允許用戶提供一個(gè)可行的初始解這能大大加快分支定界法的求解速度尤其是對(duì)整數(shù)規(guī)劃。調(diào)整求解器參數(shù)對(duì)于整數(shù)規(guī)劃可以設(shè)置最大求解時(shí)間、相對(duì)/絕對(duì)最優(yōu)間隙Gap。例如設(shè)定在1%的Gap內(nèi)停止可以快速得到一個(gè)高質(zhì)量的近似解而不必追求絕對(duì)最優(yōu)。分解與降維對(duì)于超大規(guī)模問(wèn)題看是否能分解成若干獨(dú)立的子問(wèn)題或者通過(guò)聚合如按區(qū)域合并客戶來(lái)降低問(wèn)題規(guī)模。5.4 從模型到論文如何清晰表達(dá)在數(shù)學(xué)建模競(jìng)賽或項(xiàng)目報(bào)告中模型的表達(dá)和結(jié)果的呈現(xiàn)與建模本身同樣重要。模型部分符號(hào)說(shuō)明表用一個(gè)三列表格清晰列出所有決策變量、參數(shù)和符號(hào)的含義及單位。這是專業(yè)性的體現(xiàn)。公式完整呈現(xiàn)將目標(biāo)函數(shù)和所有約束條件完整、美觀地列出。可以使用公式編輯器。闡述建模思路不要只扔出公式要用文字解釋“為什么這樣建模”特別是處理復(fù)雜約束的邏輯。結(jié)果部分圖表結(jié)合最優(yōu)方案用表格清晰列出。靈敏度分析結(jié)果用圖表展示如參數(shù)變化對(duì)目標(biāo)值的影響曲線。管理摘要在報(bào)告開頭用一兩段話概括問(wèn)題、方法、核心結(jié)論和建議。讓非技術(shù)決策者也能快速抓住重點(diǎn)。討論局限性誠(chéng)實(shí)地指出模型的假設(shè)和局限性如假設(shè)需求恒定、忽略運(yùn)輸時(shí)間等并提出未來(lái)改進(jìn)方向。這體現(xiàn)了思考的深度。規(guī)劃模型是連接數(shù)學(xué)世界與現(xiàn)實(shí)決策的堅(jiān)實(shí)橋梁。它要求我們既有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)思維又能深刻理解實(shí)際問(wèn)題。從看懂一個(gè)簡(jiǎn)單的生產(chǎn)計(jì)劃模型到自己動(dòng)手為復(fù)雜的物流網(wǎng)絡(luò)建立優(yōu)化模型這個(gè)過(guò)程充滿挑戰(zhàn)也極具成就感。記住多練、多思考、多總結(jié)每一次建模都是對(duì)你邏輯思維和解決問(wèn)題能力的一次錘煉。當(dāng)你拿到一個(gè)雜亂的實(shí)際問(wèn)題能迅速抽絲剝繭將其轉(zhuǎn)化為清晰的數(shù)學(xué)語(yǔ)言并求解時(shí)你就真正掌握了這項(xiàng)強(qiáng)大的工具。