1. 項(xiàng)目概述為什么線性規(guī)劃是數(shù)學(xué)建模的“第一塊基石”如果你剛開始接觸數(shù)學(xué)建模或者正準(zhǔn)備參加相關(guān)的競賽那么“線性規(guī)劃”這個概念你大概率是繞不開的。它常常被放在各類教程的第一章不是沒有道理的。很多人第一次看到“線性規(guī)劃”這四個字可能會覺得它高深莫測充滿了復(fù)雜的數(shù)學(xué)符號和抽象的理論。但在我十多年的建模和教學(xué)經(jīng)驗(yàn)里線性規(guī)劃恰恰是連接現(xiàn)實(shí)問題與數(shù)學(xué)模型最直接、最有效的一座橋梁。你可以把它理解為數(shù)學(xué)建模工具箱里那把最趁手、最通用的“瑞士軍刀”。簡單來說線性規(guī)劃要解決的核心問題就是在一組線性等式或不等式的約束條件下尋找一個線性目標(biāo)函數(shù)的最大值或最小值。這句話聽起來有點(diǎn)繞我舉個例子你就明白了。想象你是一個工廠的生產(chǎn)經(jīng)理手上有有限的原材料、機(jī)器工時和工人你需要決定生產(chǎn)A、B兩種產(chǎn)品各多少才能在資源有限的情況下讓總利潤達(dá)到最高。這里的“利潤”就是你的目標(biāo)函數(shù)你想讓它最大“原材料、工時”的限制就是約束條件而“生產(chǎn)A、B各多少”就是你需要決策的變量。當(dāng)利潤和所有資源消耗都與產(chǎn)量成簡單的正比關(guān)系時這個問題就是一個典型的線性規(guī)劃問題。為什么說它是“基石”因?yàn)楝F(xiàn)實(shí)世界中大量的問題在初次抽象時都可以近似為線性關(guān)系。從物流公司的運(yùn)輸路線優(yōu)化到投資組合的風(fēng)險(xiǎn)收益平衡再到廣告投放的預(yù)算分配其底層邏輯往往都能用線性規(guī)劃來刻畫。掌握了它你就掌握了將一團(tuán)亂麻的現(xiàn)實(shí)問題梳理成清晰數(shù)學(xué)結(jié)構(gòu)的基本能力。更重要的是線性規(guī)劃有成熟、高效的求解算法如單純形法這意味著一旦你建立了模型幾乎總能有可靠的工具幫你算出最優(yōu)解。這種“建模-求解-得到答案”的完整閉環(huán)對于建立建模信心至關(guān)重要。所以無論你是學(xué)生、工程師還是數(shù)據(jù)分析師花時間啃下線性規(guī)劃這一章絕對是一筆高回報(bào)的投資。2. 線性規(guī)劃的核心要素與標(biāo)準(zhǔn)形式拆解要玩轉(zhuǎn)線性規(guī)劃首先得把它拆解清楚明白每個部分代表什么。一個完整的線性規(guī)劃模型離不開三個核心要素決策變量、目標(biāo)函數(shù)和約束條件。我們繼續(xù)用上面那個工廠的例子來把這三個要素具象化。2.1 決策變量問題的“方向盤”決策變量就是你能夠控制、需要做出決定的因素。在我們的例子里就是“產(chǎn)品A的產(chǎn)量”和“產(chǎn)品B的產(chǎn)量”。我們通常用 x?, x?, ..., x? 來表示它們。這些變量有一個非常重要的特征連續(xù)性。在標(biāo)準(zhǔn)的線性規(guī)劃中我們假設(shè)可以生產(chǎn)3.5個產(chǎn)品或者投資127.83元錢。也就是說決策變量在可行域內(nèi)可以取任何實(shí)數(shù)值當(dāng)然非負(fù)約束是常見前提。這一點(diǎn)和后續(xù)要學(xué)的整數(shù)規(guī)劃有本質(zhì)區(qū)別。確定決策變量是建模的第一步也是最關(guān)鍵的一步它直接定義了你的“決策空間”。2.2 目標(biāo)函數(shù)你要去的“目的地”目標(biāo)函數(shù)描述了你要優(yōu)化的那個指標(biāo)。對于工廠經(jīng)理目標(biāo)就是最大化總利潤。假設(shè)生產(chǎn)一個A產(chǎn)品利潤是5元一個B產(chǎn)品利潤是4元那么總利潤 Z 5x? 4x?。我們的目標(biāo)就是最大化 Z即 max Z 5x? 4x?。當(dāng)然目標(biāo)也可以是成本最小化、時間最短化等對應(yīng)的就是 min 目標(biāo)函數(shù)。目標(biāo)函數(shù)必須是決策變量的線性組合這是“線性”二字的根本體現(xiàn)意味著變量之間沒有相乘、相除也沒有平方、開方等非線性關(guān)系。2.3 約束條件路上的“交通規(guī)則”你不可能無限地生產(chǎn)因?yàn)橘Y源是有限的。這些限制就是約束條件。比如生產(chǎn)每個A產(chǎn)品需要2小時機(jī)時每個B產(chǎn)品需要1小時機(jī)時而每天總機(jī)時只有8小時那么約束條件可以寫為2x? 1x? ≤ 8。同樣原材料、市場需求、政策規(guī)定等都可以轉(zhuǎn)化為類似的線性不等式或等式。約束條件共同劃定了決策變量的可行域也就是所有可能解的集合。你的最優(yōu)解必須落在這個可行域之內(nèi)。注意初學(xué)者最容易犯的錯誤就是把非線性的關(guān)系強(qiáng)行線性化或者遺漏了關(guān)鍵的約束條件。比如如果產(chǎn)量大到一定程度單位產(chǎn)品的利潤可能會因?yàn)槭袌鲲柡投陆到?jīng)濟(jì)學(xué)中的邊際效應(yīng)遞減這就不是線性關(guān)系了。在建模初期需要仔細(xì)審視問題背景判斷線性假設(shè)是否合理。2.4 標(biāo)準(zhǔn)形式統(tǒng)一的“語法”為了便于理論分析和軟件求解我們通常把線性規(guī)劃模型寫成標(biāo)準(zhǔn)形式。標(biāo)準(zhǔn)形式主要有兩個約定目標(biāo)函數(shù)統(tǒng)一為求最小值min。如果是求最大值max只需將目標(biāo)函數(shù)系數(shù)全部乘以-1即可轉(zhuǎn)化為求最小值。例如max Z 5x? 4x? 等價(jià)于 min -Z -5x? -4x?。所有約束條件統(tǒng)一為等式且右端常數(shù)項(xiàng)非負(fù)。對于不等式約束我們需要引入松弛變量或剩余變量來將其化為等式。對于“≤”約束如 2x? x? ≤ 8我們加上一個松弛變量 ss ≥ 0變成 2x? x? s 8。s 可以理解為未被利用的剩余資源。對于“≥”約束如 x? x? ≥ 4我們減去一個剩余變量 ee ≥ 0變成 x? x? - e 4。e 可以理解為超額完成的部分。此外標(biāo)準(zhǔn)形式通常還隱含了決策變量非負(fù)的約束即 x? ≥ 0, x? ≥ 0。這是符合大多數(shù)實(shí)際場景的產(chǎn)量、投資額不能為負(fù)。所以一個標(biāo)準(zhǔn)形式的線性規(guī)劃模型看起來是這樣的min c?x? c?x? ... c?x? subject to: a??x? a??x? ... a??x? b? a??x? a??x? ... a??x? b? ... ... a??x? a??x? ... a??x? b? x?, x?, ..., x? ≥ 0 (松弛/剩余變量也 ≥ 0)其中c? 是目標(biāo)函數(shù)系數(shù)a?? 是約束系數(shù)矩陣中的元素b? 是右端常數(shù)項(xiàng)通常要求 b? ≥ 0。3. 圖解法和單純形法從幾何直觀到代數(shù)通用理解了模型接下來就是怎么求解。對于只有兩個決策變量的問題我們可以用一種非常直觀的方法——圖解法。而對于任意多個變量的問題則需要依靠強(qiáng)大的代數(shù)算法——單純形法。3.1 圖解法二維世界里的“尋寶游戲”圖解法是理解線性規(guī)劃幾何意義的絕佳工具。我們以這個簡單問題為例max Z 5x? 4x? s.t. 2x? x? ≤ 8 x? 2x? ≤ 6 x?, x? ≥ 0第一步繪制約束區(qū)域。在 x?-O-x? 坐標(biāo)系中將每個不等式先當(dāng)作等式畫出直線。直線 2x? x? 8過點(diǎn) (0,8) 和 (4,0)。直線 x? 2x? 6過點(diǎn) (0,3) 和 (6,0)。 然后根據(jù)不等式確定直線的哪一側(cè)是滿足條件的。例如對于 2x? x? ≤ 8取原點(diǎn)(0,0)測試0≤8成立所以包含原點(diǎn)的那一側(cè)直線左下側(cè)是可行域。對所有約束都這么操作這些半平面的交集再加上非負(fù)象限就構(gòu)成了一個凸多邊形區(qū)域這就是可行域。本例中可行域是一個四邊形頂點(diǎn)分別為 O(0,0), A(0,3), B(?, ?), C(4,0)。其中B點(diǎn)是兩條直線 2x? x?8 和 x? 2x?6 的交點(diǎn)聯(lián)立方程解得 B(10/3, 4/3)。第二步尋找最優(yōu)解。目標(biāo)函數(shù) Z 5x? 4x? 可以改寫為 x? - (5/4)x? Z/4。這是一組斜率為 -5/4 的平行線Z 的不同值對應(yīng)直線的不同截距Z/4。我們的目標(biāo)是最大化 Z也就是尋找一條斜率為 -5/4 且與可行域有交點(diǎn)的直線使其截距最大。 沿著目標(biāo)函數(shù)梯度方向即系數(shù)向量(5,4)的方向垂直于目標(biāo)函數(shù)等值線平移這條直線。你會發(fā)現(xiàn)當(dāng)這條直線平移到剛好經(jīng)過可行域的某個頂點(diǎn)時再往外平移就將離開可行域。這個最后接觸的頂點(diǎn)就是最優(yōu)解。在本例中這個頂點(diǎn)就是 B(10/3, 4/3)。代入目標(biāo)函數(shù)得到最大利潤 Z_max 5*(10/3) 4*(4/3) 66/3 22。圖解法的啟示可行域是一個“凸集”集合內(nèi)任意兩點(diǎn)的連線仍在集合內(nèi)。最優(yōu)解如果存在必然在可行域的某個“頂點(diǎn)”或稱“極點(diǎn)”上達(dá)到。這個結(jié)論是單純形法的理論基礎(chǔ)?？赡苡袩o窮多最優(yōu)解當(dāng)目標(biāo)函數(shù)直線與可行域的一條邊重合時也可能無解可行域?yàn)榭占部赡芙鉄o界可行域朝目標(biāo)函數(shù)增長方向無限延伸。實(shí)操心得圖解法雖然只適用于二維但它是檢驗(yàn)?zāi)銓€性規(guī)劃基本概念可行域、目標(biāo)函數(shù)等值線、頂點(diǎn)最優(yōu)理解程度的試金石。在初期哪怕問題變量很多也建議嘗試構(gòu)造一個二維簡化版本來畫圖理解這對培養(yǎng)建模直覺非常有幫助。3.2 單純形法高維空間的“頂點(diǎn)導(dǎo)航儀”當(dāng)變量和約束增多圖解法就無能為力了。這時就需要單純形法。你可以把單純形法想象成一個在高維凸多面體可行域的頂點(diǎn)之間智能跳躍的導(dǎo)航儀。它從一個初始的可行頂點(diǎn)基本可行解出發(fā)沿著多面體的棱從一個頂點(diǎn)移動到相鄰的另一個頂點(diǎn)每次移動都保證目標(biāo)函數(shù)值不下降求min時或不上升求max時直到找到最優(yōu)頂點(diǎn)為止。單純形法的核心步驟化為標(biāo)準(zhǔn)形并建立初始單純形表引入松弛變量將問題化為標(biāo)準(zhǔn)形。松弛變量和原始變量中一部分被選為“基變量”其值由等式約束直接決定且非負(fù)另一部分為“非基變量”暫時設(shè)為0。將方程組和目標(biāo)函數(shù)用非基變量表示填入一張表格單純形表。最優(yōu)性檢驗(yàn)查看目標(biāo)函數(shù)行檢驗(yàn)數(shù)行。對于最大化問題如果所有非基變量的檢驗(yàn)數(shù)都 ≤ 0說明當(dāng)前頂點(diǎn)已是最優(yōu)算法停止。否則選擇一個檢驗(yàn)數(shù) 0 的非基變量作為“入基變量”讓它從0增加能使目標(biāo)函數(shù)增長。確定離基變量根據(jù)最小比值法則確定哪個基變量會隨著入基變量的增加而最先降到0這個變量就是“離基變量”。樞軸變換旋轉(zhuǎn)運(yùn)算以入基變量和離基變量交叉點(diǎn)的元素為“樞軸元”進(jìn)行行變換使得入基變量對應(yīng)的列變?yōu)閱挝幌蛄吭撛貫?同列其他元素為0。這相當(dāng)于代數(shù)上完成了基變量的更替幾何上就是從當(dāng)前頂點(diǎn)移動到了相鄰頂點(diǎn)。迭代得到新的單純形表回到第2步進(jìn)行最優(yōu)性檢驗(yàn)直至找到最優(yōu)解。單純形表示例接上圖解法例子化為標(biāo)準(zhǔn)形后初始問題max Z 5x? 4x?, s.t. 2x?x?≤8, x?2x?≤6, x?,x?≥0。 引入松弛變量 s?, s? ≥ 0化為標(biāo)準(zhǔn)形max Z 5x? 4x? 0*s? 0*s? s.t. 2x? x? s? 8 x? 2x? s? 6 x?, x?, s?, s? ≥ 0初始時令非基變量 x?0, x?0則基變量 s?8, s?6。這是一個明顯的可行頂點(diǎn)(O點(diǎn))。建立初始單純形表基變量右端項(xiàng)x?x?s?s?s?82110s?61201Z0-5-400第一輪迭代檢驗(yàn)數(shù)x?列(-5), x?列(-4)。因?yàn)榍髆ax負(fù)檢驗(yàn)數(shù)表示增加該變量能使Z增加。選擇檢驗(yàn)數(shù)絕對值最大的 x?-5作為入基變量通常選最負(fù)的稱為Dantzig規(guī)則收斂快。比值計(jì)算s?行 8/24s?行 6/16。最小比值是4對應(yīng)s?行所以s?為離基變量。樞軸變換以第一行第一列的元素2為樞軸元將該行除以2并用行變換將x?列其他元素包括檢驗(yàn)數(shù)行消為0。 變換后新表基變量右端項(xiàng)x?x?s?s?x?411/21/20s?203/2-1/21Z200-3/25/20此時基變量為 x?4, s?2非基變量為 x?0, s?0。對應(yīng)頂點(diǎn)C(4,0)。目標(biāo)值Z20。第二輪迭代檢驗(yàn)數(shù)行x?列(-3/2)仍為負(fù)故選擇x?入基。比值計(jì)算x?行 4/(1/2)8s?行 2/(3/2)4/3。最小比值是4/3對應(yīng)s?行所以s?離基。樞軸變換以第二行第二列元素3/2為樞軸元。 變換后新表基變量右端項(xiàng)x?x?s?s?x?10/3102/3-1/3x?4/301-1/32/3Z220021此時檢驗(yàn)數(shù)行全部非負(fù)對于max問題已是最優(yōu)性條件。最優(yōu)解為 x?10/3, x?4/3, s?0, s?0最大目標(biāo)值 Z22。這與圖解法結(jié)果完全一致。注意事項(xiàng)單純形法在理論上不是多項(xiàng)式時間算法存在讓單純形法遍歷幾乎所有頂點(diǎn)的“病態(tài)”問題但在實(shí)際應(yīng)用中它異常高效通常能在O(mn)次迭代內(nèi)收斂?，F(xiàn)代優(yōu)化軟件如MATLAB的linprog、Python的scipy.optimize.linprog內(nèi)部都實(shí)現(xiàn)了高度優(yōu)化的單純形法或更先進(jìn)的內(nèi)點(diǎn)法。4. 對偶理論每一個線性規(guī)劃問題都有一位“影子伴侶”這是線性規(guī)劃理論中最精妙、也最具實(shí)用價(jià)值的部分之一。每一個線性規(guī)劃問題稱為原問題都伴隨著另一個與之緊密相關(guān)的線性規(guī)劃問題稱為它的對偶問題。它們就像一枚硬幣的兩面。如何寫出對偶問題有一個簡單的規(guī)則以對稱形式為例 原問題 (P):min c?x s.t. Ax ≥ b x ≥ 0其對偶問題 (D):max b?y s.t. A?y ≤ c y ≥ 0這里x是原問題的決策變量y是對偶問題的決策變量稱為對偶變量或影子價(jià)格。如果原問題約束是不等式≥那么對偶變量 y ≥ 0如果是等式約束則對偶變量 y 無符號限制。對偶理論的核心定理與應(yīng)用弱對偶定理對于任意可行解x原問題和y對偶問題總有 c?x ≥ b?y。即原問題的最小值總是不小于對偶問題的最大值。強(qiáng)對偶定理如果原問題和對偶問題之一有有限最優(yōu)解那么另一個也有有限最優(yōu)解并且兩者的最優(yōu)值相等。互補(bǔ)松弛定理在最優(yōu)解處要么原問題的約束是緊的取等號要么對應(yīng)的對偶變量為0反之亦然。這為檢驗(yàn)最優(yōu)性提供了條件。對偶變量的經(jīng)濟(jì)解釋——影子價(jià)格這是對偶理論最閃光的應(yīng)用。在對偶問題中變量 y? 代表了原問題第 i 種資源對應(yīng)第 i 個約束的邊際價(jià)值。具體來說y?* 表示在原問題最優(yōu)解附近第 i 種資源每增加一個單位所能帶來的目標(biāo)函數(shù)最優(yōu)值的改進(jìn)量對于min問題是減少量對于max問題是增加量。回到工廠例子原問題是最大化利潤約束是資源機(jī)時、工時上限。其對偶問題就是在求解每種資源的“真實(shí)內(nèi)部價(jià)值”。假設(shè)我們求得最優(yōu)對偶變量 y?* 1對應(yīng)機(jī)時約束y?* 2對應(yīng)工時約束。這意味著在當(dāng)前最優(yōu)生產(chǎn)計(jì)劃下如果機(jī)器工時能增加1小時總利潤最多能增加1元。如果工人工時能增加1小時總利潤最多能增加2元。 這個信息對管理者極其重要它告訴你哪種資源是瓶頸影子價(jià)格高增加哪種資源對提升利潤最有效。如果市場上租用一小時機(jī)器工時的成本低于1元那么租用就是劃算的如果高于1元則不應(yīng)增加。影子價(jià)格為資源分配和采購決策提供了精確的量化的依據(jù)。實(shí)操心得在利用軟件求解線性規(guī)劃后一定要查看并解讀對偶變量的值影子價(jià)格。它往往比最優(yōu)解本身蘊(yùn)含更多的管理洞察。例如在投資組合優(yōu)化中影子價(jià)格可以告訴你每單位風(fēng)險(xiǎn)承受能力的增加能帶來多少預(yù)期收益的提升在物流配送中它可以告訴你每個倉庫容量或每條路徑帶寬的邊際價(jià)值。5. 靈敏度分析當(dāng)世界發(fā)生變化時你的最優(yōu)解還穩(wěn)健嗎我們建立模型時使用的數(shù)據(jù)目標(biāo)函數(shù)系數(shù)c?、約束右端常數(shù)b?、約束系數(shù)a??往往是估計(jì)值或預(yù)測值。市場價(jià)格會波動資源供應(yīng)會變化工藝會改進(jìn)。靈敏度分析要回答的問題是當(dāng)這些參數(shù)在多大范圍內(nèi)變動時當(dāng)前求得的最優(yōu)基即哪些變量是基變量保持不變最優(yōu)基不變意味著最優(yōu)解的結(jié)構(gòu)哪些變量取正值哪些為0不變盡管其具體數(shù)值可能會變。靈敏度分析主要關(guān)注三類參數(shù)的變化目標(biāo)函數(shù)系數(shù) c? 的變化這會影響檢驗(yàn)數(shù)。對于非基變量c?的變化不能使其檢驗(yàn)數(shù)從非最優(yōu)變?yōu)樽顑?yōu)對于max問題不能從≤0變?yōu)?。對于基變量c?的變化會影響所有非基變量的檢驗(yàn)數(shù)需要保證它們?nèi)詽M足最優(yōu)性條件。軟件報(bào)告會給出每個c?的“允許增加量”和“允許減少量”。約束右端常數(shù) b? 的變化這會影響基變量的取值但不會直接影響檢驗(yàn)數(shù)只要對偶變量y不變。b?的變化必須保證所有基變量的值仍為非負(fù)可行性條件。軟件會給出每個b?的“允許增加量”和“允許減少量”。在這個范圍內(nèi)最優(yōu)基不變但最優(yōu)解的值會變并且目標(biāo)函數(shù)最優(yōu)值的變化量等于影子價(jià)格 y?* 乘以 b? 的變化量這就是對偶變量的意義。約束系數(shù)矩陣 A 的變化增加一個新變量或一個新約束。這相當(dāng)于改變了問題的維度。對于增加新變量可以計(jì)算其“縮減成本”相當(dāng)于檢驗(yàn)數(shù)如果滿足最優(yōu)性條件則當(dāng)前解仍最優(yōu)否則需要將新變量納入基中重新迭代。對于增加新約束需要檢查當(dāng)前最優(yōu)解是否滿足該新約束如果滿足則仍最優(yōu)否則需要將該約束引入并繼續(xù)求解。靈敏度分析報(bào)告解讀示例基于工廠例子的軟件輸出假設(shè)軟件求解后除了給出最優(yōu)解 (x?10/3, x?4/3)還給出了如下靈敏度報(bào)告目標(biāo)函數(shù)系數(shù)范圍x?的系數(shù)5允許增加 3允許減少 1。即系數(shù)在 [4, 8] 內(nèi)變化時最優(yōu)基x?和x?是基變量不變。x?的系數(shù)4允許增加 2允許減少 2。即系數(shù)在 [2, 6] 內(nèi)變化時最優(yōu)基不變。約束右端項(xiàng)范圍機(jī)時約束右端8允許增加 4允許減少 4。即機(jī)時資源在 [4, 12] 小時內(nèi)變化時最優(yōu)基不變。工時約束右端6允許增加 6允許減少 2。即工時資源在 [4, 12] 小時內(nèi)變化時最優(yōu)基不變。這份報(bào)告極具管理價(jià)值。它告訴管理者產(chǎn)品A的利潤在4元到8元之間波動時最優(yōu)的生產(chǎn)組合生產(chǎn)A和B策略不需要改變。如果機(jī)器工時在4到12小時之間我們不需要調(diào)整生產(chǎn)哪種產(chǎn)品的決策但具體產(chǎn)量會變增加的利潤可以用影子價(jià)格1元/小時來估算。注意事項(xiàng)靈敏度分析給出的范圍是“最優(yōu)基不變”的范圍而不是“最優(yōu)解不變”的范圍。在范圍內(nèi)最優(yōu)解的具體數(shù)值通常會隨著參數(shù)變化而線性變化。同時這些范圍是單個參數(shù)變化時的獨(dú)立范圍。如果多個參數(shù)同時變化情況會復(fù)雜得多可能需要使用“百分之百法則”進(jìn)行粗略判斷或者直接重新求解模型。6. 線性規(guī)劃建模實(shí)戰(zhàn)與軟件求解理論最終要服務(wù)于實(shí)踐。我們用一個更綜合的例子來走一遍完整的線性規(guī)劃建模與求解流程。問題描述營養(yǎng)配餐問題某食堂需要為學(xué)生配餐要求每份餐食至少提供熱量2000千卡蛋白質(zhì)55克鈣800毫克?，F(xiàn)有六種食材可供選擇其每千克營養(yǎng)成分、價(jià)格及每日可用上限如下表食材價(jià)格(元/kg)熱量(kcal/kg)蛋白質(zhì)(g/kg)鈣(mg/kg)最大可用量(kg)大米53500801000.5面粉43400100300.3雞蛋815001206000.2牛奶66004011000.5牛肉302000200500.1菠菜2250209000.4請問如何搭配這些食材才能在滿足營養(yǎng)需求的前提下使每份餐食的成本最低6.1 模型建立決策變量設(shè)每份餐食中各種食材的使用量千克為 x?大米, x?面粉, x?雞蛋, x?牛奶, x?牛肉, x?菠菜。目標(biāo)函數(shù)最小化總成本。min Z 5x? 4x? 8x? 6x? 30x? 2x?。約束條件營養(yǎng)需求約束至少熱量3500x? 3400x? 1500x? 600x? 2000x? 250x? ≥ 2000蛋白質(zhì)80x? 100x? 120x? 40x? 200x? 20x? ≥ 55鈣100x? 30x? 600x? 1100x? 50x? 900x? ≥ 800食材可用量約束上限x? ≤ 0.5, x? ≤ 0.3, x? ≤ 0.2, x? ≤ 0.5, x? ≤ 0.1, x? ≤ 0.4非負(fù)約束x?, x?, ..., x? ≥ 0。6.2 軟件求解以Python SciPy為例import numpy as np from scipy.optimize import linprog # 目標(biāo)函數(shù)系數(shù) (min) c np.array([5, 4, 8, 6, 30, 2]) # 不等式約束矩陣 A_ub * x b_ub # 我們有兩種不等式營養(yǎng)需求是 食材上限是 。需要統(tǒng)一為 形式。 # 對于營養(yǎng)需求 兩邊乘以 -1 變?yōu)?。 A_ub np.array([ [-3500, -3400, -1500, -600, -2000, -250], # 熱量 2000 - -熱量 -2000 [-80, -100, -120, -40, -200, -20], # 蛋白質(zhì) 55 [-100, -30, -600, -1100, -50, -900], # 鈣 800 [1, 0, 0, 0, 0, 0], # x1 0.5 [0, 1, 0, 0, 0, 0], # x2 0.3 [0, 0, 1, 0, 0, 0], # x3 0.2 [0, 0, 0, 1, 0, 0], # x4 0.5 [0, 0, 0, 0, 1, 0], # x5 0.1 [0, 0, 0, 0, 0, 1] # x6 0.4 ]) b_ub np.array([-2000, -55, -800, 0.5, 0.3, 0.2, 0.5, 0.1, 0.4]) # 變量邊界 (x 0)默認(rèn)就是0到正無窮所以不用特別指定但這里我們顯式寫出下界。 x_bounds [(0, None)] * 6 # 下界為0上界為None無窮 # 求解 res linprog(c, A_ubA_ub, b_ubb_ub, boundsx_bounds, methodhighs) # highs是推薦的內(nèi)點(diǎn)法求解器 print(優(yōu)化狀態(tài):, res.message) print(最小成本 (元):, round(res.fun, 2)) print(最優(yōu)食材用量 (kg):) ingredients [大米, 面粉, 雞蛋, 牛奶, 牛肉, 菠菜] for i, name in enumerate(ingredients): print(f {name}: {res.x[i]:.4f})運(yùn)行結(jié)果可能類似于優(yōu)化狀態(tài): Optimization terminated successfully. 最小成本 (元): 12.86 最優(yōu)食材用量 (kg): 大米: 0.0000 面粉: 0.3000 雞蛋: 0.2000 牛奶: 0.5000 牛肉: 0.0000 菠菜: 0.40006.3 結(jié)果分析與解讀根據(jù)求解結(jié)果最優(yōu)配餐方案使用面粉0.3kg雞蛋0.2kg牛奶0.5kg菠菜0.4kg。不使用大米和牛肉。最低成本約12.86元。約束情況面粉、雞蛋、牛奶、菠菜的用量都達(dá)到了上限說明這些食材因其性價(jià)比高在最優(yōu)解中被用滿。大米和牛肉未被使用可能是因?yàn)樵跐M足營養(yǎng)約束下它們的“營養(yǎng)-成本”比不如其他食材。影子價(jià)格分析我們可以從求解器的res對象中獲取對偶變量res.ineqlin.marginals注意SciPy的符號約定。分析這些影子價(jià)格可以知道哪個營養(yǎng)約束是“緊”的恰好滿足其影子價(jià)格表示該營養(yǎng)要求每提高1單位成本至少要增加多少元。哪個食材上限約束是“緊”的其影子價(jià)格表示該食材上限每放松1kg成本能降低多少元。這對于采購決策是否要增加某種食材的采購量有指導(dǎo)意義。實(shí)操心得用軟件求解時務(wù)必檢查求解狀態(tài)res.success和res.message確保模型被正確求解。對于“≥”約束在化為標(biāo)準(zhǔn)形式時處理符號要格外小心。解讀結(jié)果時不僅要看最優(yōu)解和最優(yōu)值更要結(jié)合影子價(jià)格進(jìn)行經(jīng)濟(jì)或管理上的分析這是線性規(guī)劃模型價(jià)值升華的關(guān)鍵一步。7. 常見問題、誤區(qū)與排查技巧在實(shí)際建模和求解中你會遇到各種問題。這里總結(jié)一些典型場景和應(yīng)對策略。7.1 模型無可行解現(xiàn)象軟件提示“infeasible”不可行。原因約束條件相互矛盾不存在同時滿足所有約束的點(diǎn)。比如一個要求 x ≤ 5另一個要求 x ≥ 10。排查仔細(xì)檢查每個約束的邏輯和單位是否一致。檢查是否有“硬性”約束過于嚴(yán)格。例如在營養(yǎng)配餐中如果所有食材的蛋白質(zhì)總量上限都低于需求下限則必然無解?？梢試L試逐步放松某些約束看是否能找到可行解從而定位矛盾的約束組。7.2 模型解無界現(xiàn)象軟件提示“unbounded”無界。對于最大化問題目標(biāo)函數(shù)值可以趨向正無窮對于最小化問題可以趨向負(fù)無窮。原因可行域朝目標(biāo)函數(shù)優(yōu)化的方向是開放的且沒有約束將其限制住。例如max x s.t. x ≥ 0。排查檢查是否遺漏了關(guān)鍵的約束條件特別是限制決策變量增長的上限約束。檢查目標(biāo)函數(shù)系數(shù)的符號是否正確。7.3 存在多重最優(yōu)解現(xiàn)象軟件求出一個最優(yōu)解但你可能發(fā)現(xiàn)目標(biāo)函數(shù)等值線與可行域的一條邊或面重合。判斷在單純形法最終表中如果存在某個非基變量的檢驗(yàn)數(shù)為0則說明存在多重最優(yōu)解。讓這個檢驗(yàn)數(shù)為0的非基變量入基進(jìn)行一次樞軸變換就能得到另一個最優(yōu)頂點(diǎn)解。意義管理者可以在不犧牲目標(biāo)值如利潤、成本的前提下在其他指標(biāo)如風(fēng)險(xiǎn)、穩(wěn)定性、公平性上做出更優(yōu)選擇。7.4 退化與循環(huán)現(xiàn)象在單純形法迭代中基變換后目標(biāo)函數(shù)值沒有改進(jìn)稱為退化極端情況下可能導(dǎo)致無限循環(huán)理論上可能實(shí)踐中極其罕見。應(yīng)對現(xiàn)代求解器都采用了抗退化和防循環(huán)策略如Bland規(guī)則、擾動法。在實(shí)際使用中基本不用擔(dān)心這個問題。7.5 數(shù)值不穩(wěn)定與尺度問題現(xiàn)象模型數(shù)據(jù)量級差異巨大如系數(shù)既有0.0001又有100000導(dǎo)致求解器計(jì)算時出現(xiàn)較大舍入誤差甚至誤判最優(yōu)性。解決縮放在建模階段盡量讓約束矩陣中各系數(shù)的數(shù)量級保持一致?？梢詫π屑s束或列變量進(jìn)行縮放。提高精度使用高精度求解器或調(diào)整求解器的容差參數(shù)如tol。檢查輸入確保輸入數(shù)據(jù)沒有錯誤。7.6 線性假設(shè)不成立現(xiàn)象實(shí)際問題中的關(guān)系并非嚴(yán)格的線性比例關(guān)系。應(yīng)對分段線性化對于某些非線性函數(shù)如帶有固定成本、折扣的價(jià)格函數(shù)可以用分段線性函數(shù)來近似。使用其他模型如果非線性關(guān)系是核心且不可忽略則需要考慮非線性規(guī)劃、整數(shù)規(guī)劃等更復(fù)雜的模型。線性規(guī)劃是第一步的近似其價(jià)值在于快速給出一個基準(zhǔn)解和洞察。給新手的最后建議從線性規(guī)劃開始你的建模之旅重點(diǎn)培養(yǎng)“將文字描述轉(zhuǎn)化為數(shù)學(xué)表達(dá)式”的能力。多練習(xí)從簡單的例子開始親手用圖解法畫一畫用軟件算一算再嘗試解讀影子價(jià)格和靈敏度報(bào)告。當(dāng)你能夠熟練地為一個小型資源分配或計(jì)劃問題建立線性規(guī)劃模型并求解分析時你就已經(jīng)掌握了數(shù)學(xué)建模中最核心、最常用的一套思維工具。這套工具將會在你后續(xù)學(xué)習(xí)更復(fù)雜的整數(shù)規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃時成為你堅(jiān)實(shí)的地基。