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