做生產(chǎn)計劃、物流調(diào)度這類工作久了你會發(fā)現(xiàn)很多決策問題最后都?xì)w結(jié)成一個老面孔線性規(guī)劃。Excel里的規(guī)劃求解能一鍵給出答案但碰上帶“大于等于”約束的模型直接求解出來的東西往往和教材例題對不上這時候把單純形法大M法在Excel里手動搭一遍反而能幫你把整個求解過程看穿。這篇就聊聊怎么在Excel里用單純形法的大M法求解線性規(guī)劃包括手工搭建表格的“直接求解”路線以及用“規(guī)劃求解”功能一步到位的路線最后比較兩條路線分別適合什么場景。我盡量把表頭、迭代步驟和常見坑都寫清楚推薦給正在學(xué)運籌學(xué)、做課程設(shè)計或者想驗證手算結(jié)果的同學(xué)。1. 先別急著打開Excel把模型寫成標(biāo)準(zhǔn)形單純形法不是拿到什么題都能直接算的它要求線性規(guī)劃模型先轉(zhuǎn)成標(biāo)準(zhǔn)形。我見過太多同學(xué)上來就把表格往Excel里一擺結(jié)果卡在負(fù)系數(shù)、剩余變量這類細(xì)節(jié)上。這一節(jié)我們先花幾分鐘把模型整理干凈后面不管是手算還是用工具都會順很多。1.1 一個帶“”約束的典型題目為了后面好演示我假設(shè)一個小車間要安排兩種產(chǎn)品A和B的生產(chǎn)。產(chǎn)品A每件利潤1萬元產(chǎn)品B每件利潤2萬元。設(shè)備工時有限制約束條件是2x1 x2 ≤ 10同時銷售合同要求兩種產(chǎn)品加起來至少要生產(chǎn)4件也就是x1 x2 ≥ 4這里 x1 和 x2 分別表示A、B產(chǎn)品的產(chǎn)量都是非負(fù)變量。目標(biāo)函數(shù)就是最大化利潤max z x1 2x2這個例子很小但很典型因為它同時包含“小于等于”和“大于等于”約束恰好是為大M法量身定做的題。如果你只想求解不大于約束的問題只需要松弛變量根本用不到大M法一旦出現(xiàn)“≥”或者“”約束初始基變量不好找人工變量就必須登場。1.2 松弛變量、剩余變量、人工變量到底往哪放先把兩個約束改寫成等式。第一個約束“≤”可以加一個松弛變量s1代表沒用完的設(shè)備工時2x1 x2 s1 10第二個約束“≥”要先減去一個剩余變量s2因為左邊比右邊多出來的部分需要扣掉才能相等x1 x2 - s2 4問題是減掉s2之后如果想把s2當(dāng)成基變量它的系數(shù)是-1不是單位向量沒法直接作為初始基。所以還要再加一個人工變量a1x1 x2 - s2 a1 4a1本身沒有任何實際經(jīng)濟含義純粹是湊初始基用的。這樣處理后s1的系數(shù)列是(1,0)a1的系數(shù)列是(0,1)它們構(gòu)成單位矩陣可以直接當(dāng)基變量。目標(biāo)函數(shù)也要跟著改。因為我們在最大化問題里引入了一個“假變量”必須讓它付出代價所以目標(biāo)函數(shù)寫成max z x1 2x2 - M·a1這里的M是一個非常大的正數(shù)代表對人工變量的“懲罰”。如果最優(yōu)解里a1還留在基變量里并且大于0就說明原問題不可行這個后面會再細(xì)說。1.3 大M法的核心思想用懲罰把“假變量”趕走大M法聽起來神秘其實本質(zhì)上就是給人工變量標(biāo)一個極高的“違禁價”。最大化問題里只要模型中還有可行解讓人工變量留在基里就會把目標(biāo)函數(shù)往下拉單純形法會自動優(yōu)先把它們換出基。你可以把這個過程理解成一個獎懲機制人工變量就像一個不應(yīng)出現(xiàn)的臨時工你給它開一個極高的“工資成本”優(yōu)化器為了把利潤做到最大會想方設(shè)法把它辭退。只要最終最優(yōu)解中人工變量等于0說明“臨時工”已經(jīng)被完全清退剩下的解就是原問題的真實最優(yōu)解。反過來如果迭代到最后人工變量仍然是正的基變量說明模型本身可能是矛盾的或者約束條件之間沖突導(dǎo)致無可行解。這是大M法自帶的一種“報警機制”非常有用。2. 手算一遍單純形表把每一步看透很多同學(xué)用Excel規(guī)劃求解直接出結(jié)果但完全不知道數(shù)字怎么來的。我建議至少在練習(xí)階段手算一遍單純形表這樣后面在Excel里搭公式才不會瞎填。下面我用剛才那個模型完整走一遍大M法迭代。2.1 建初始單純形表模型整理之后變量順序為x1、x2、s1、s2、a1。目標(biāo)函數(shù)系數(shù)分別是c [1, 2, 0, 0, -M]基變量先取s1和a1對應(yīng)的基系數(shù)是0和-M。初始單純形表如下基變量基系數(shù)x1x2s1s2a1RHS比值s10211001010a1-M110-1144檢驗數(shù)M1M20-M0-4M這里的檢驗數(shù)行按 cj - zj 計算。以x1列為例zj 2×0 1×(-M) -M所以 cj - zj 1 - (-M) M1。檢驗數(shù)行的右端值是當(dāng)前目標(biāo)函數(shù)值等于 -M×4也就是 -4M。在最大化問題里入基變量選檢驗數(shù)最大正值那一列。M看作一個足夠大的數(shù)顯然M2比M1更大所以x2入基。2.2 第一次迭代確定主元接著看比值。比值的意義是把某個基變量換成入基變量后約束能撐住多少。x2列對應(yīng)的比值第一行10 / 1 10 第二行4 / 1 4選最小正比值也就是第二行出基a1離開基變量。主元位置就在第二行、x2列交叉處主元值是1?，F(xiàn)在做行變換。主元行整體除以主元值也就是不變第一行要消去x2列的第一個元素1。具體操作第一行新值 第一行舊值 - 1×主元行新值因為主元行第二行和第一行在x2列都是1直接用減法就能消元。更新后的單純形表如下基變量基系數(shù)x1x2s1s2a1RHS比值s101011-166x22110-114-4舍去檢驗數(shù)-1002-M-28注意這一輪人工變量a1已經(jīng)順利出基接下來的表格里它的作用已經(jīng)完成了。檢驗數(shù)行里s2列出現(xiàn)正值2說明還有改進(jìn)空間繼續(xù)進(jìn)行下一輪迭代。2.3 第二次迭代收斂到最優(yōu)s2入基?？磗2列的比值第一行6 / 1 6 第二行4 / (-1) -4負(fù)比值必須舍去因為如果采用負(fù)比值會讓基變量變成負(fù)數(shù)違背非負(fù)約束。所以第一行出基s1離開主元位置在第一行、s2列主元值為1。行變換后得到最終表基變量基系數(shù)x1x2s1s2a1RHS比值s201011-16x222110010檢驗數(shù)-30-20-M20檢驗數(shù)行全部小于等于0達(dá)到最優(yōu)。最優(yōu)解是 x210x10目標(biāo)函數(shù)最大值 z20。帶回原約束驗證一下2×01010滿足設(shè)備工時01010≥4滿足合同約束。結(jié)果正確。這里有個小技巧最優(yōu)解中直接看基變量那一列對應(yīng)的RHS就是變量取值非基變量x1、s1等取0。在這個例子中s26意味著剩余變量等于6也就是產(chǎn)量超出了最低合同要求6件。2.4 最優(yōu)解的經(jīng)濟含義單純從數(shù)值看這個車間應(yīng)該把全部產(chǎn)能放在產(chǎn)品B上生產(chǎn)10件B不生產(chǎn)A利潤20萬元。這看起來有點“極端”但線性規(guī)劃的最優(yōu)解往往落在可行域的頂點上頂點通常就是某些變量取0的角點。如果業(yè)務(wù)上不允許出現(xiàn)零產(chǎn)量那就需要額外加下界約束比如x1≥1然后重新求解。這個屬于模型調(diào)整的范疇不在單純形法的核心流程里但值得你在實際應(yīng)用中留意。3. Excel直接求解把單純形表做成可復(fù)用的模板現(xiàn)在進(jìn)入正題怎么在Excel里直接搭建大M法的單純形表。手動在紙上迭代沒問題但在Excel里做的好處是修改系數(shù)后能快速重算還能用公式防止手誤。3.1 工作表怎么布局最順手我試過好幾種布局最后覺得“一行一個基變量、列按變量排開”最直觀。在Sheet中按照下面的結(jié)構(gòu)準(zhǔn)備行內(nèi)容第1行變量名x1、x2、s1、s2、a1、RHS第2行目標(biāo)函數(shù)系數(shù)1、2、0、0、-M第3行第一條約束2、1、1、0、0、10第4行第二條約束1、1、0、-1、1、4第5行基變量名s1、a1第6行基系數(shù)0、-M第二步再往下留兩行放檢驗數(shù)行和比值列。檢驗數(shù)行用公式計算不要手填這樣才能保證每次修改系數(shù)后自動更新。檢驗數(shù)公式可以這樣寫。假設(shè)C列開始放變量系數(shù)基系數(shù)放在B6:B7區(qū)域約束矩陣在C3:H4區(qū)域那么某個變量列的檢驗數(shù)可以表示成目標(biāo)系數(shù) - SUMPRODUCT(基系數(shù), 該列約束系數(shù))例如x1列檢驗數(shù)就是C2 - SUMPRODUCT($B$6:$B$7, C3:C4)拖拽填充整行即可。比值計算就更容易RHS除以入基變量列對應(yīng)系數(shù)只取正數(shù)。3.2 行變換公式只記住兩條規(guī)則每次迭代的核心就是主元運算。新手最容易在這里寫錯公式其實規(guī)則只有兩條。第一條新的主元行等于舊的主元行除以主元值。假設(shè)主元在第4行第D列那么新主元行的任意一個單元格C8可以用C4/$D$4復(fù)制時需要把主元單元格固定用$D$4鎖住行和列。第二條其他行的新值等于舊值減去“舊主元列對應(yīng)元素”乘以“新主元行對應(yīng)值”。假設(shè)第3行是其他行主元列是第4行的D列那么新的第3行任意單元格可以寫C3 - $D$3 * C8這里的$D$3表示第3行在主元列上的舊值C8表示新主元行在變量列上的值。實際操作時我會在表格右側(cè)并排放兩三個表的區(qū)域每個區(qū)域代表一輪迭代。第一輪表在主區(qū)域第二輪表復(fù)制到旁邊修改主元行和公式第三輪繼續(xù)復(fù)制。這樣每一輪都能對照不容易亂。3.3 迭代到什么時候停手單純形迭代的停止條件就一句話檢驗數(shù)行全部小于等于0。對最大化問題來說只要還有正檢驗數(shù)就說明目標(biāo)還能繼續(xù)增大。在Excel里可以用IF函數(shù)做一個自動判斷。比如在檢驗數(shù)行末尾加一個狀態(tài)單元格IF(MAX(檢驗數(shù)區(qū)域)0, 已最優(yōu), 繼續(xù)迭代)如果寫著“繼續(xù)迭代”就去檢查最大的正檢驗數(shù)對應(yīng)哪一列然后計算比值確定出基行再做行變換。熟練后一輪操作大概兩三分鐘小規(guī)模問題不會超過三五個表就能出結(jié)果。3.4 別忘了最后驗證一組約束迭代結(jié)束后我強烈建議你別只看目標(biāo)函數(shù)。把最優(yōu)解代回原來的約束條件在Excel里單獨開一個驗證區(qū)。比如x210x10那么設(shè)備工時約束就是2×01×1010正好等于10合同約束是01010大于等于4。兩個約束都成立目標(biāo)值等于20。如果有任何一條不滿足先回頭檢查標(biāo)準(zhǔn)形轉(zhuǎn)換尤其是剩余變量和人工變量的符號這個環(huán)節(jié)最容易被符號帶溝里。4. 用規(guī)劃求解功能一條龍搞定如果不想一張表一張表地迭代Excel自帶的規(guī)劃求解功能可以直接幫你完成任務(wù)。它的底層算法也包含單純形法但對用戶隱藏了迭代過程只需要把模型單元格擺好。4.1 先把加載項打開很多版本默認(rèn)不顯示規(guī)劃求解按鈕需要手動加載。操作路徑是文件 → 選項 → 加載項 → 轉(zhuǎn)到Excel加載項 → 勾選“規(guī)劃求解加載項” → 確定。加載完成后“數(shù)據(jù)”選項卡右側(cè)會出現(xiàn)“規(guī)劃求解”按鈕。如果找不到這個加載項可能是辦公軟件版本太精簡需要安裝完整的Excel組件。我遇到過有人卡在這里很久其實重新安裝Office就能解決。4.2 建立變量、目標(biāo)、約束單元格規(guī)劃求解需要一個清晰的模型區(qū)。我習(xí)慣這樣布置D2和E2放決策變量x1、x2F2放目標(biāo)函數(shù)公式D2*B2 E2*C2這里B2、C2分別存放目標(biāo)函數(shù)中x1和x2的系數(shù)也就是1和2。再往下建兩條約束對應(yīng)的左側(cè)公式D2*B4 E2*C4表示設(shè)備工時D2*B5 E2*C5表示合同產(chǎn)量B4:C4位置寫第一條約束的系數(shù)2和1右邊約束值是10B5:C5位置寫第二條約束的系數(shù)1和1約束值是4。4.3 設(shè)置規(guī)劃求解參數(shù)打開規(guī)劃求解對話框參數(shù)設(shè)置如下“設(shè)置目標(biāo)”填F2方向選最大值 “通過更改可變單元格”填D2:E2 “添加約束”中加入F4 10F5 4D2:E2 0這里最關(guān)鍵的一步是選擇求解方法。在“選擇求解引擎”下拉菜單里必須選“單純線性規(guī)劃”不能默認(rèn)用GRG非線性。線性規(guī)劃模型用單純形法才能保證找到全局最優(yōu)解GRG非線性雖然也能算線性問題但容易在邊界上出現(xiàn)問題。點擊“求解”Excel會很快給出結(jié)果x10x210目標(biāo)值20和手算完全一致。4.4 保存方案與敏感性報告規(guī)劃求解出結(jié)果之后不只有一個數(shù)字就完了。在“規(guī)劃求解結(jié)果”對話框里Excel允許你保存方案也能生成報告。常見的報告有三種運算結(jié)果報告、敏感性報告、極限值報告。敏感性報告對實際決策很有用它會告訴你每個約束的影子價格以及目標(biāo)系數(shù)在哪個范圍內(nèi)變化不會影響最優(yōu)解結(jié)構(gòu)。比如設(shè)備工時約束的影子價格可以理解為每增加1個單位設(shè)備工時能帶來多少利潤提升。這比單純看一個最優(yōu)產(chǎn)量更貼近管理決策。我建議你每次都勾選生成報告放到單獨工作表里這樣后續(xù)答辯、匯報時可以直接引用。5. 直接求解與規(guī)劃求解怎么選有哪些坑既然兩條路都能求出答案那到底該用哪種說實話我的經(jīng)驗是確認(rèn)答案用規(guī)劃求解學(xué)習(xí)原理用直接求解手算一遍再用規(guī)劃求解驗證兩邊都能對得上這個結(jié)果才敢放心用。5.1 兩條路線的合適場景對比維度直接求解手動迭代規(guī)劃求解教學(xué)理解極高每一步都透明較低黑箱出結(jié)果操作速度慢尤其變量多時快幾秒完成可變規(guī)模小規(guī)模一般50×50以內(nèi)勉強中大規(guī)模也能處理出錯風(fēng)險符號和公式容易錯參數(shù)設(shè)置容易錯是否需要人工變量需要大M法核心不需要工具內(nèi)部處理報表與敏感性分析無靠自己整理自帶報告非常方便如果你的目標(biāo)是搞懂單純形法的來龍去脈直接求解必須做一遍。如果你是做項目、趕報告優(yōu)先用規(guī)劃求解節(jié)約時間。最理想的組合是先用規(guī)劃求解得到答案再用手動表驗證一兩步關(guān)鍵迭代這樣既有速度又有說服力。5.2 我用著最難受的幾個大M坑我在Excel里手算大M法踩過不少坑挑幾個最典型的分享。第一個坑是M值取太大。很多人覺得M越大越保險直接填-1000000000結(jié)果Excel浮點運算出現(xiàn)精度問題檢驗數(shù)全是亂碼。我的做法是讓M比模型最大系數(shù)大100到1000倍就夠了比如這個例子最大系數(shù)是2M取1000都綽綽有余沒必要用天文數(shù)字。第二個坑是負(fù)比值當(dāng)成出基行。比值檢驗只看正數(shù)負(fù)數(shù)說明該約束在當(dāng)前迭代下不支持入基變量增加強行選取會讓基變量為負(fù)。這個錯誤手算時容易犯Excel里也容易選錯行。第三個坑是人工作變量提前出基后還繼續(xù)盯著看。人工變量一旦離開基變量就相當(dāng)于被“開除”了后續(xù)迭代可以直接忽略那一列省很多事。你繼續(xù)算也不會錯但會增加不必要的計算量。第四個坑是忽略退化現(xiàn)象。當(dāng)兩個比值相等時叫退化可能出現(xiàn)基變量為0的情況。如果遇到退化和循環(huán)單純形法可能來回繞。Excel直接求解時我建議如果連續(xù)三輪檢驗數(shù)、目標(biāo)值都沒變化就檢查一下是不是遇到循環(huán)了必要時換成規(guī)劃求解或者兩階段法。5.3 常見問題快速排查表現(xiàn)象可能原因處理辦法最優(yōu)解中人工變量大于0原問題無可行解檢查約束之間是否矛盾檢驗數(shù)一直有正數(shù)但迭代不進(jìn)去比值均為負(fù)或無正主元重新檢查變量符號和模型標(biāo)準(zhǔn)形M太大導(dǎo)致數(shù)值異常浮點精度不足減小M或換用兩階段法規(guī)劃求解提示線性條件不滿足目標(biāo)或約束里用了非線性函數(shù)檢查公式中的乘除和嵌套函數(shù)手算結(jié)果與規(guī)劃求解不一致手算主元行選錯或符號寫錯用規(guī)劃求解結(jié)果反推逐步驗證每一輪表格變量出現(xiàn)負(fù)數(shù)漏了非負(fù)約束在規(guī)劃求解中添加D2:E20最后分享一個我常用的驗證技巧把最優(yōu)解代回原約束檢查剩余量和松弛量是否合理。比如這個例子中s26說明實際產(chǎn)量超過合同要求6件。你在Excel里單獨設(shè)一列自動算剩余變量和松弛變量一眼就能看出模型是否可靠。按這個流程走即使以后遇到幾十個變量的生產(chǎn)計劃問題也不容易被數(shù)字騙過去。