劃單純形法與運輸問題高頻考點匯總)
每年到這個時間點后臺就會收到一波運籌學備考的消息。不是問“線性規(guī)劃單純形法最后一行怎么判最優(yōu)”就是問“運輸問題用最小元素法求完初始解位勢法到底怎么算檢驗數(shù)”。我這份匯總就是把期末試卷和考研真題里反復出現(xiàn)的填空題、計算題按題型剝開把答案和踩坑點一起放出來題目不多但每一道都值得動手做一遍。這份整理適合三類人一是考前突擊、需要快速過一遍考點的同學二是想檢驗自己復習質(zhì)量、專門找題練手的人三是已經(jīng)工作但準備考非全、需要拾起運籌學基礎(chǔ)的朋友。填空題部分覆蓋了概念、圖像性質(zhì)、對偶理論、靈敏度分析、排隊論這些“背了就有分”的點計算題部分則集中在單純形法、對偶問題、運輸問題、指派問題和動態(tài)規(guī)劃這幾個必考大類。每道題我都盡量給出“解題過程答案為什么這么做”不是單純把答案堆在最后讓你自己對。先提醒一句運籌學這門課最忌諱的就是只看不練。你覺得自己看懂了單純形法閉上書試試從建模寫到最優(yōu)解表格大概率在某一列上卡住。下面這些題建議先拿紙筆做一遍再對照答案看差異這樣收獲完全不一樣。1. 試卷結(jié)構(gòu)心里有數(shù)各知識板塊的出題權(quán)重與考察邏輯運籌學考卷雖然學校不同但出題套路相當穩(wěn)定。一般來說填空、選擇這類小題占總分30%左右計算題占60%以上剩下是建模題或簡答題。計算題里線性規(guī)劃純屬必考要么直接考單純形法計算要么考對偶理論加靈敏度分析這塊在多數(shù)試卷里占20到25分。運輸問題緊跟其后大概率考一個產(chǎn)銷平衡的求初始調(diào)運方案加位勢法檢驗15分左右。整數(shù)規(guī)劃、圖論、動態(tài)規(guī)劃、排隊論、存儲論等板塊中學校會根據(jù)課時多少選兩到三個來考。不同知識板塊的考察邏輯也很清晰。填空題側(cè)重概念辨析與公式記憶比如“滿足約束條件和非負條件的解叫什么”“產(chǎn)銷不平衡時要引進什么變量”考的是你對定義是否精準計算題則看你能不能把流程走完比如單純形法從初始可行解開始迭代中間任何一步算錯后面最優(yōu)解必然不對但多數(shù)老師會按步驟給分算出基變量、檢驗數(shù)這些中間結(jié)果也有分所以過程一定不能省。理解出題邏輯對復習方向很有幫助。我的建議是先把線性規(guī)劃和運輸問題這兩塊練到“閉著眼都能算”的程度再花時間背填空考點最后處理其他計算題板塊。因為線性規(guī)劃和運輸問題分值最重、題型最程序化性價比最高。2. 填空小題別忽略背下這些高頻考點就能穩(wěn)拿基礎(chǔ)分填空題分值看似不大但勝在數(shù)量多、覆蓋面廣。很多同學把精力全放在計算題上結(jié)果填空題失分嚴重非?？上АＯ旅孢@些是我從多套真題里篩選出的高頻考點每題都附答案和一句解析。2.1 基礎(chǔ)概念與模型辨析題目1在線性規(guī)劃問題中由所有約束條件和非負條件共同確定的變量取值范圍稱為____。答案可行域或稱可行解集。解析這里注意和“可行解”區(qū)分可行域是集合可行解只是其中的一個點。題目2若線性規(guī)劃問題存在可行解但其目標函數(shù)值無界則稱該問題____。答案有無界解或無最優(yōu)解。解析考試經(jīng)常會寫成“無最優(yōu)解”閱卷時也算對。但嚴格說教材先用“無界解”描述原因再得出結(jié)論“無最優(yōu)解”答題時寫后者更穩(wěn)妥。題目3線性規(guī)劃問題的標準形式中目標函數(shù)一律轉(zhuǎn)化為____形式約束條件一律轉(zhuǎn)化為____且所有決策變量____。答案求最大值等式約束加松弛變量/減剩余變量后非負。解析標準形式的三要素max、等式約束、變量非負這是單純形法計算的前提。如果題目給的是min要轉(zhuǎn)換成max再計算轉(zhuǎn)換方式是令z -z。題目4若線性規(guī)劃問題存在最優(yōu)解則最優(yōu)解必定能在可行域的某個____上達到。答案頂點極點。解析這是線性規(guī)劃基本定理的結(jié)論。圖解法中最優(yōu)解一定在交點處就是頂點。這一條是填空題的釘子戶。題目5線性規(guī)劃問題中若某一基變量取值為零則稱該基本可行解為____。答案退化的基本可行解退化解。解析退化問題在單純形法迭代時可能導致循環(huán)但考試一般只考概念。注意“退化解”是“基本可行解退化”不是“可行解退化”。2.2 對偶理論與影子價格題目6線性規(guī)劃原問題有最優(yōu)解則對偶問題____有最優(yōu)解且兩者最優(yōu)目標函數(shù)值____。答案也一定相等。解析這是對偶理論中的強對偶定理?？荚囂羁疹}經(jīng)常反過來考如果原問題目標函數(shù)無界對偶問題一定不可行。題目7影子價格的經(jīng)濟含義是指在其它條件不變的情況下某種資源每增加一個單位目標函數(shù)最優(yōu)值所____的數(shù)量。答案增加嚴格說是相應增加的量可正可負。解析影子價格等于對偶問題的最優(yōu)解對偶變量對應的是資源的邊際價值。注意如果約束是“≥”類型影子價格的含義有所不同但基礎(chǔ)題一般考察的是“≤”資源約束。題目8若原問題中某個約束條件為“≤”形式則其對偶變量滿足____約束。答案非負≥0。解析對偶變量符號與原問題約束方向有關(guān)。約束為“≤”且目標求max時對偶變量≥0約束為“”時對偶變量無符號限制。2.3 運輸問題與指派問題題目9在運輸問題中當總產(chǎn)量大于總銷量時可以通過增加一個____使其轉(zhuǎn)化為產(chǎn)銷平衡問題。答案虛擬銷地。解析虛擬銷地對應的運價通常設(shè)為0其銷量等于總產(chǎn)量與總銷量之差。虛銷地運量在實際方案中代表某產(chǎn)地沒有運出去的貨物量。題目10運輸問題中用位勢法計算檢驗數(shù)的原理是若所有非基變量的檢驗數(shù)____則當前調(diào)運方案為最優(yōu)方案。答案都大于等于零≥0對于求最小費用問題。解析這是運輸問題最優(yōu)性檢驗的核心結(jié)論。理解成“當前方案沒有改進空間”即可檢驗數(shù)小于0說明還有更省錢的調(diào)整方案。題目11指派問題的標準數(shù)學模型要求每項任務只能由一人完成每人只能承擔____項任務目標為總效率____。答案一最大或最小看題目設(shè)定。解析指派問題的系數(shù)矩陣是方陣如果人數(shù)與任務數(shù)不等需要添加虛擬的人或任務對應效率設(shè)為0。2.4 圖論、排隊論與動態(tài)規(guī)劃題目12在M/M/1排隊模型中第一個M表示到達過程服從____第二個M表示服務時間服從____數(shù)字1表示____。答案泊松流到達間隔為負指數(shù)分布負指數(shù)分布只有一個服務臺。解析這個題每年都有學?？?。需要記住為什么叫“M”是馬爾可夫性的意思說明過程無記憶性。題目13在動態(tài)規(guī)劃中某階段的狀態(tài)變量應具有____性質(zhì)即當前狀態(tài)已能完全決定未來決策與該階段之前的歷史無關(guān)。答案無后效性馬爾可夫性。解析這是動態(tài)規(guī)劃建模最核心的假設(shè)條件也是判斷一個問題能否用動態(tài)規(guī)劃求解的重要依據(jù)。題目14網(wǎng)絡圖中關(guān)鍵線路是總時差為____的工作線路它決定整個工程的工期。答案零。解析關(guān)鍵線路上的工作一點都不能拖延否則總工期延誤。計算題中求關(guān)鍵線路和總工期是重點。這十幾道填空題基本覆蓋了期末考試的高頻概念。你如果能把每道題涉及的章節(jié)都展開復習一遍填空題的得分就有保障了。3. 線性規(guī)劃建模與單純形法從設(shè)變量到最優(yōu)表一步步走計算題的大頭在線性規(guī)劃。它有兩種考法一種是給你實際情景讓你建模另一種是直接給數(shù)學模型讓你用單純形法迭代求最優(yōu)解。這兩類我都給出一道典型題目并把中間的迭代過程寫清楚。3.1 生產(chǎn)計劃建模題與標準形式轉(zhuǎn)換題目某工廠計劃生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)1件甲產(chǎn)品需消耗A原料3kg、B原料2kg利潤為50元生產(chǎn)1件乙產(chǎn)品需消耗A原料2kg、B原料4kg利潤為60元。該工廠現(xiàn)有A原料120kg、B原料160kg。問應如何安排生產(chǎn)使總利潤最大請建立線性規(guī)劃模型。這個題非常簡單但能完整體現(xiàn)建模的四個要素決策變量、目標函數(shù)、約束條件、非負約束。設(shè)生產(chǎn)甲產(chǎn)品x?件、乙產(chǎn)品x?件則模型為max z 50x? 60x?s.t. 3x? 2x? ≤ 1202x? 4x? ≤ 160x?, x? ≥ 0建模題的關(guān)鍵在于判斷“約束條件”與“目標函數(shù)”哪個該放一邊。很多同學容易把原料約束寫反其實記住一句話受限制的寫在約束條件里要優(yōu)化的寫在目標函數(shù)里。資源消耗不能超過資源總量這就是約束利潤要盡可能大這就是目標。進一步把它轉(zhuǎn)換成標準形式以備單純形法使用。由于兩個約束都是“≤”類型引入松弛變量x?、x?得到max z 50x? 60x?s.t. 3x? 2x? x? 1202x? 4x? x? 160x?, x?, x?, x? ≥ 0松弛變量x?、x?實際上表示被閑置的原料量它的系數(shù)是1目標函數(shù)系數(shù)為0不影響利潤。3.2 單純形法完整迭代以兩變量模型為例很多人對單純形法的印象是“表格特別多、符號容易搞混”其實只要抓牢三個要素就行基變量、進基出基規(guī)則、檢驗數(shù)。下面用一個更小巧的模型完整走一遍過程。題目求解線性規(guī)劃問題max z 3x? 2x?s.t. x? x? ≤ 4x? ≤ 2x? ≤ 3x?, x? ≥ 0先引入松弛變量x?、x?、x?標準形式為max z 3x? 2x?s.t. x? x? x? 4x? x? 2x? x? 3各變量 ≥ 0初始基可行解令x?和x?為非基變量取0則x?4x?2x?3初始目標值z0。初始單純形表為基變量x?x?x?x?x?右端項x?111004x?100102x?010013檢驗數(shù)-3-20000檢驗數(shù)中最小的是-3對應x?所以x?進基。接著確定出基變量用右端項除以x?列正系數(shù)4/142/12x?這一行x?系數(shù)為0不參與比值最小比值是2對應x?出基。主元是x?行的x?系數(shù)1。進行一次高斯消去讓x?列變成單位向量保持x?行不變將x?行減去x?行檢驗數(shù)行加上3倍x?行。得到第二張表基變量x?x?x?x?x?右端項x?011-102x?100102x?010013檢驗數(shù)0-20306第二張表里檢驗數(shù)最小-2對應x?進基。比值檢驗x?行2/12x?行3/13最小比值2所以x?出基。主元是x?行x?列的1。再次消去x?列變成單位向量x?行不變x?行減去x?行x?行x?系數(shù)為0不用動x?行減去x?行檢驗數(shù)行加上2倍x?行。結(jié)果基變量x?x?x?x?x?右端項x?011-102x?100102x?00-1111檢驗數(shù)0021010所有檢驗數(shù)都≥0迭代停止。最優(yōu)解為x?2、x?2、x?1松弛變量最優(yōu)目標值z10。虛線上方的x?0、x?0說明兩個資源約束都用滿了而x?1說明第三個資源x?≤3還有1單位剩余?？紙鼋ㄗh單純形法的計算量不算大但一定要規(guī)范列表格、標出主元。我見過太多同學代數(shù)不列檢驗數(shù)靠心算是基變量的系數(shù)列還是非基變量的系數(shù)列最后一步錯得離譜。寧可多寫一行也不要跳步。3.3 對偶問題與靈敏度分析?？夹问綄ε紗栴}是線性規(guī)劃的一個獨立考點常與靈敏度分析一起出現(xiàn)。它的核心是對稱關(guān)系max問題對應對偶的min問題約束方向和變量符號也有對應規(guī)則。題目寫出下面線性規(guī)劃問題的對偶問題。max z 4x? 3x?s.t. x? 2x? ≤ 103x? x? ≤ 15x?, x? ≥ 0設(shè)對偶變量為y?、y?分別對應原問題的兩個約束原問題目標為max、約束為“≤”則對偶問題的目標為min約束為“≥”目標系數(shù)和約束系數(shù)矩陣互為轉(zhuǎn)置。對偶模型為min w 10y? 15y?s.t. y? 3y? ≥ 42y? y? ≥ 3y?, y? ≥ 0靈敏度分析的考點則是某資源增加一個單位最優(yōu)目標值變化多少。答案就是該約束對應的影子價格也就是對偶最優(yōu)解。比如上面問題中如果對偶最優(yōu)解是y?1、y?1說明第一資源量從10增加到11時最優(yōu)利潤會增加1第二資源同理。這類題不需要重新求解單純形表直接用互補松弛定理或讀影子價格即可。4. 運輸問題與整數(shù)規(guī)劃方案尋找、最優(yōu)性檢驗與指派問題運輸問題是每年計算題的重頭戲本質(zhì)是一個特殊結(jié)構(gòu)的線性規(guī)劃。由于約束矩陣的特殊性考試不讓你用單純形法而是要求掌握表上作業(yè)法先求初始調(diào)運方案再用位勢法檢驗最后用閉回路調(diào)整。4.1 最小元素法求初始方案位勢法驗最優(yōu)題目某產(chǎn)品有三個產(chǎn)地A?、A?、A?產(chǎn)量分別為120、180銷往三個銷地B?、B?、B?銷量分別為100、150、50。單位運價如下表求使總運費最小的調(diào)運方案。產(chǎn)地\銷地B?B?B?產(chǎn)量A?865120A?576180銷量10015050300先檢查產(chǎn)銷平衡總產(chǎn)量120180300總銷量10015050300產(chǎn)銷平衡可以直接用表上作業(yè)法。最小元素法的思路是“哪個格子運價最低就先盡量往哪個格子運”。運價表中最低運價有兩個A?到B?是5A?到B?也是5任意選一個先運。這里選A?→B?運量為min(120,50)50于是B?需求完成A?剩余70。此時把B?列劃去。剩余運價中最低為A?→B?的5運量為min(180,100)100B?需求完成A?剩余80。劃去B?列。剩余運價中A?→B?為6A?→B?為7選擇A?→B?運量為min(70,150)70A?用完B?剩余80。最后A?→B?運80A?用完。初始調(diào)運方案為A?→B?運70A?→B?運50A?→B?運100A?→B?運80?？傔\費 70×6 50×5 100×5 80×7 420 250 500 560 1730。接下來用位勢法檢驗。基變量個數(shù)為4個應該等于mn-123-14恰好非退化設(shè)行位勢為u?、u?列位勢為v?、v?、v?。對每個基變量有u?v?c??。令u?0可解得A?→B?0v?6得v?6A?→B?0v?5得v?5A?→B?u?67得u?1A?→B?1v?5得v?4。然后計算非基變量的檢驗數(shù)σc??-(u?v?)A?→B?8-(04)4A?→B?6-(15)0。由于所有檢驗數(shù)≥0當前方案即為最優(yōu)方案最低運費1730。這里有個細節(jié)A?→B?的檢驗數(shù)為0說明存在另一個最優(yōu)方案但目標值相同?？荚囬喚頃r只要運費正確、方案合理一般都給滿分。4.2 當檢驗數(shù)出現(xiàn)負數(shù)閉回路調(diào)整怎么做如果檢驗數(shù)出現(xiàn)負數(shù)說明當前方案不是最優(yōu)。調(diào)整的方法是選檢驗數(shù)最小的非基變量進基從該格子出發(fā)找閉回路閉回路的偶數(shù)頂點上減去進基變量最小運量奇數(shù)頂點加上同樣運量得到新方案。舉例來說承接上題如果某一非基變量檢驗數(shù)為-2比如假設(shè)A?→B?檢驗數(shù)為-2注意上題實際是4那么從A?→B?出發(fā)沿水平或垂直方向找基變量頂點形成回路。假定回路頂點為A?→B?進基→A?→B?基→A?→B?基→A?→B?基→回到起點。奇數(shù)頂點運量分別為A?→B?的70、A?→B?的100取最小70于是進基變量A?→B?運量為70回路奇數(shù)頂點減去70偶數(shù)頂點加上70。這個調(diào)整過程雖然說起來簡單但考場上看錯行列坐標的人非常多我建議找回路時用筆把格子的行列號標出來每走一步都確認是不是基變量格子。4.3 指派問題匈牙利法的步驟與計算實例指派問題屬于整數(shù)規(guī)劃中的0-1規(guī)劃特例。3個人完成3項任務的效率矩陣如下求使總效率最大的最優(yōu)指派方案。題目某班組有3名工人甲、乙、丙需完成3項任務A、B、C。每個人完成不同任務的效率見下表求總效率最大的指派方案。工人\任務ABC甲483乙768丙574匈牙利法一般處理最小化問題最大化要先把矩陣轉(zhuǎn)換為最小化。轉(zhuǎn)換方式是取每行最大值或矩陣最大值減去該行元素把它變成“損失矩陣”。這里每行最大值分別為8、8、7轉(zhuǎn)換后矩陣為甲4 0 5乙1 2 0丙2 0 3接著逐行找最小值并減去第一行減去0第二行減去0第三行減去0矩陣不變。然后逐列找最小值并減去第一列min(4,1,2)1減去后第一列為3,0,1第二列min(0,2,0)0第三列min(5,0,3)0。得到甲3 0 5乙0 2 0丙1 0 3用最少的直線覆蓋所有0元素最少畫線數(shù)為33行或3列時已覆蓋等于矩陣階數(shù)可以進行試指派。從只有唯一0的行開始乙行只有一個0在A所以乙→A丙行有兩個0在B和C甲行只有一個0在B。先指派甲→B丙→C檢查安排為甲→B、乙→A、丙→C對應原效率87419。還有另一種丙→B、甲行就沒有0可選甲只有B被丙占用則甲無法指派所以不是最優(yōu)。因此最優(yōu)指派是甲→B、乙→A、丙→C最大總效率19。這個例子雖然簡單但能完整展示“移減去零→試指派”的邏輯。真正的考試題往往是4×4或5×5試指派時可能遇到覆蓋線數(shù)小于階數(shù)的情況那時需要繼續(xù)做“無零元素的調(diào)整”步驟本質(zhì)上是在未覆蓋元素中找最小值重復減加操作。碰到這類題時記住不要著急試指派先確認畫線數(shù)與階數(shù)相等否則一定漏了步驟。5. 圖、動態(tài)規(guī)劃與排隊論三類常見計算題的代表性解法這些板塊在不同學?？碱l差別很大但一旦考到題型通常非常固定。這里各給出一道具有代表性的題目。5.1 最短路問題Dijkstra標號法題目求下圖中從v?到v?的最短路圖中各邊權(quán)值已標出v?→v?權(quán)2v?→v?權(quán)5v?→v?權(quán)1v?→v?權(quán)6v?→v?權(quán)4v?→v?權(quán)3v?→v?權(quán)1v?→v?權(quán)5v?→v?權(quán)2。Dijkstra標號法的做法是給每個頂點維護一個當前最短距離標號每次從未標號的頂點中選距離最小的那個更新它鄰接頂點的距離。迭代過程如下初始d(v?)0其余頂點標為∞。第一輪選v?更新v?為2v?為5。第二輪未標號中最小是v?距離2選擇v?更新v?為min(5, 21)3更新v?為268。第三輪未標號最小是v?距離3更新v?為min(8, 34)7更新v?為336。第四輪未標號最小是v?距離6更新v?為min(7, 61)7更新v?為628。第五輪最小是v?距離7更新v?為min(8, 75)8。最終v?最短距離為8。對應的最短路有多條比如v?→v?→v?→v?→v?距離21328。Dijkstra的適用條件是邊權(quán)非負考試圖題基本都滿足?？紙鋈菀族e在“更新順序”上一定要先選當前最小標號點再用它去更新而不是按頂點序號順序更新。5.2 動態(tài)規(guī)劃資源分配/背包問題題目用動態(tài)規(guī)劃求解下列背包問題背包容量為10有3件物品重量分別為3、4、5價值分別為4、5、6每件物品最多取1件求最大總價值。動態(tài)規(guī)劃的核心是定義狀態(tài)、狀態(tài)轉(zhuǎn)移方程和邊界條件。設(shè)f(k, c)表示“考慮前k件物品、容量為c時的最大價值”。狀態(tài)轉(zhuǎn)移方程為f(k, c) max{ f(k-1, c), f(k-1, c-w_k) v_k }前提是c≥w_k填表過程第一件物品w3, v4容量0~2取0容量3~10取4。第二件物品w4, v5容量0~2取0容量3取4容量4~6可以取max(4, 05)5其中容量4、5取5容量6取5容量7~10可以取max(4, 45)97時取前一件加第二件459。第三件物品w5, v6容量0~2取0容量3取4容量4取5容量5~6取max(5,06)6容量7~8取max(9, 46)10容量9~10取max(9, 56)11。所以最優(yōu)總價值為11對應選擇第二件和第三件價值5611總重量459不超過容量10。這類題的得分點在于寫出階段、狀態(tài)、決策、狀態(tài)轉(zhuǎn)移方程和最終表。就算填表數(shù)字算錯方程寫對也能拿到大半過程分所以千萬別只寫答案不寫方程。5.3 排隊論M/M/1模型的基本指標題目某售票窗口顧客到達服從泊松流平均每小時到達12人服務時間服從負指數(shù)分布平均每小時服務20人。求系統(tǒng)空閑的概率、平均隊長、平均等待時間。M/M/1模型的關(guān)鍵參數(shù)是服務強度ρλ/μ。λ12人/小時μ20人/小時ρ12/200.6。系統(tǒng)空閑概率P?1-ρ0.4。平均隊長L?ρ/(1-ρ)0.6/0.41.5人。平均等待時間W_q L_q/λ而平均等待隊長L_q ρ2/(1-ρ)0.36/0.40.9人所以W_q0.9/120.075小時4.5分鐘。如果需要平均逗留時間W? 1/(μ-λ)1/(20-12)0.125小時7.5分鐘。這個題的易錯點是把隊長和等待隊長搞混。平均隊長L?包含正在接受服務的那個顧客而平均等待隊長L_q只包含排隊的人。考試時先寫公式再代數(shù)字避免最后答案對不上公式時丟分。6. 考場實戰(zhàn)策略計算題的表格規(guī)范與時間分配計算題能不能拿高分很大程度取決于考場上的書寫規(guī)范。單純形法、運輸問題、指派問題、動態(tài)規(guī)劃填表這幾類都有標準步驟評卷時按步驟給分。我整理了幾條實操建議都是自己在考試和輔導中總結(jié)出來的。第一每次迭代都完整列出單純形表并在表中標出主元行、主元列和主元。這樣即使最后最優(yōu)解算錯閱卷老師也能看到你迭代邏輯正確過程分不會少。不要跳步去合并表格那種寫法風險很大一步手滑整表作廢。第二運輸問題的初始調(diào)運方案畫表時注意標記哪行哪列已被劃去基變量數(shù)量要等于mn-1。如果沒有達到這個數(shù)量說明出現(xiàn)了退化需要把運量為0的格子當成基變量格子補足否則位勢法會出現(xiàn)解不出位勢的情況。很多同學就是在這里卡殼的。第三動態(tài)規(guī)劃題中狀態(tài)轉(zhuǎn)移方程一定要放在顯著位置。閱卷人往往先掃方程再看表格方程對了表格個別數(shù)值有誤也能拿到大部分分。計算最短路時建議在每個頂點旁標一個“當前最短距離前驅(qū)”最后回溯路徑時可以直接看清楚。第四關(guān)于時間分配。我建議根據(jù)分值倒推時間假設(shè)卷面滿分100、考試時間120分鐘大概1分對應1.2分鐘。線性規(guī)劃大題給20分就留20到25分鐘不要因為它出現(xiàn)在第一題就戀戰(zhàn)。填空、選擇最多半小時內(nèi)做完不會的先跳過計算題優(yōu)先做最熟練的題型。先把能拿的分穩(wěn)穩(wěn)拿到再回頭摳難題。第五考試時準備一張草稿紙專門做“計算復核”。比如單純形表的行變換每次消元后用“原行加主元的倍數(shù)”重新算一遍檢驗數(shù)或者運輸問題算完總費用再按原始運價表手算一遍這能篩掉至少一半的算術(shù)錯誤。運籌學的計算本身不難丟分基本都是粗心造成的。這類考試里還有一個常見的隱性陷阱題目給的是“利潤最大化”但表格里卻是“費用”或者給的是“最大運輸量”卻要求“最小運費”。讀題時花十秒鐘確認目標方向比做完一堆計算才發(fā)現(xiàn)方向反了要劃算得多。做題時把“max”或“min”圈出來就等于給全卷加了一層保險。運籌學復習到最后拼的不只是誰公式背得熟而是誰能把流程完整、規(guī)范地寫出來。把上面這些題從“看懂”變成“會算”再變成“算得又對又快”考試基本就穩(wěn)了。如果你手里有哪道題反復做不對多半是中間某步流程有遺漏回頭對照標準步驟比盲目刷十道新題更管用。 運籌學期末考研復習：線性規(guī)劃單純形法與運輸問題高頻考點匯總
每年到這個時間點后臺就會收到一波運籌學備考的消息。不是問“線性規(guī)劃單純形法最后一行怎么判最優(yōu)”就是問“運輸問題用最小元素法求完初始解位勢法到底怎么算檢驗數(shù)”。我這份匯總就是把期末試卷和考研真題里反復出現(xiàn)的填空題、計算題按題型剝開把答案和踩坑點一起放出來題目不多但每一道都值得動手做一遍。這份整理適合三類人一是考前突擊、需要快速過一遍考點的同學二是想檢驗自己復習質(zhì)量、專門找題練手的人三是已經(jīng)工作但準備考非全、需要拾起運籌學基礎(chǔ)的朋友。填空題部分覆蓋了概念、圖像性質(zhì)、對偶理論、靈敏度分析、排隊論這些“背了就有分”的點計算題部分則集中在單純形法、對偶問題、運輸問題、指派問題和動態(tài)規(guī)劃這幾個必考大類。每道題我都盡量給出“解題過程答案為什么這么做”不是單純把答案堆在最后讓你自己對。先提醒一句運籌學這門課最忌諱的就是只看不練。你覺得自己看懂了單純形法閉上書試試從建模寫到最優(yōu)解表格大概率在某一列上卡住。下面這些題建議先拿紙筆做一遍再對照答案看差異這樣收獲完全不一樣。1. 試卷結(jié)構(gòu)心里有數(shù)各知識板塊的出題權(quán)重與考察邏輯運籌學考卷雖然學校不同但出題套路相當穩(wěn)定。一般來說填空、選擇這類小題占總分30%左右計算題占60%以上剩下是建模題或簡答題。計算題里線性規(guī)劃純屬必考要么直接考單純形法計算要么考對偶理論加靈敏度分析這塊在多數(shù)試卷里占20到25分。運輸問題緊跟其后大概率考一個產(chǎn)銷平衡的求初始調(diào)運方案加位勢法檢驗15分左右。整數(shù)規(guī)劃、圖論、動態(tài)規(guī)劃、排隊論、存儲論等板塊中學校會根據(jù)課時多少選兩到三個來考。不同知識板塊的考察邏輯也很清晰。填空題側(cè)重概念辨析與公式記憶比如“滿足約束條件和非負條件的解叫什么”“產(chǎn)銷不平衡時要引進什么變量”考的是你對定義是否精準計算題則看你能不能把流程走完比如單純形法從初始可行解開始迭代中間任何一步算錯后面最優(yōu)解必然不對但多數(shù)老師會按步驟給分算出基變量、檢驗數(shù)這些中間結(jié)果也有分所以過程一定不能省。理解出題邏輯對復習方向很有幫助。我的建議是先把線性規(guī)劃和運輸問題這兩塊練到“閉著眼都能算”的程度再花時間背填空考點最后處理其他計算題板塊。因為線性規(guī)劃和運輸問題分值最重、題型最程序化性價比最高。2. 填空小題別忽略背下這些高頻考點就能穩(wěn)拿基礎(chǔ)分填空題分值看似不大但勝在數(shù)量多、覆蓋面廣。很多同學把精力全放在計算題上結(jié)果填空題失分嚴重非?？上АＯ旅孢@些是我從多套真題里篩選出的高頻考點每題都附答案和一句解析。2.1 基礎(chǔ)概念與模型辨析題目1在線性規(guī)劃問題中由所有約束條件和非負條件共同確定的變量取值范圍稱為____。答案可行域或稱可行解集。解析這里注意和“可行解”區(qū)分可行域是集合可行解只是其中的一個點。題目2若線性規(guī)劃問題存在可行解但其目標函數(shù)值無界則稱該問題____。答案有無界解或無最優(yōu)解。解析考試經(jīng)常會寫成“無最優(yōu)解”閱卷時也算對。但嚴格說教材先用“無界解”描述原因再得出結(jié)論“無最優(yōu)解”答題時寫后者更穩(wěn)妥。題目3線性規(guī)劃問題的標準形式中目標函數(shù)一律轉(zhuǎn)化為____形式約束條件一律轉(zhuǎn)化為____且所有決策變量____。答案求最大值等式約束加松弛變量/減剩余變量后非負。解析標準形式的三要素max、等式約束、變量非負這是單純形法計算的前提。如果題目給的是min要轉(zhuǎn)換成max再計算轉(zhuǎn)換方式是令z -z。題目4若線性規(guī)劃問題存在最優(yōu)解則最優(yōu)解必定能在可行域的某個____上達到。答案頂點極點。解析這是線性規(guī)劃基本定理的結(jié)論。圖解法中最優(yōu)解一定在交點處就是頂點。這一條是填空題的釘子戶。題目5線性規(guī)劃問題中若某一基變量取值為零則稱該基本可行解為____。答案退化的基本可行解退化解。解析退化問題在單純形法迭代時可能導致循環(huán)但考試一般只考概念。注意“退化解”是“基本可行解退化”不是“可行解退化”。2.2 對偶理論與影子價格題目6線性規(guī)劃原問題有最優(yōu)解則對偶問題____有最優(yōu)解且兩者最優(yōu)目標函數(shù)值____。答案也一定相等。解析這是對偶理論中的強對偶定理?？荚囂羁疹}經(jīng)常反過來考如果原問題目標函數(shù)無界對偶問題一定不可行。題目7影子價格的經(jīng)濟含義是指在其它條件不變的情況下某種資源每增加一個單位目標函數(shù)最優(yōu)值所____的數(shù)量。答案增加嚴格說是相應增加的量可正可負。解析影子價格等于對偶問題的最優(yōu)解對偶變量對應的是資源的邊際價值。注意如果約束是“≥”類型影子價格的含義有所不同但基礎(chǔ)題一般考察的是“≤”資源約束。題目8若原問題中某個約束條件為“≤”形式則其對偶變量滿足____約束。答案非負≥0。解析對偶變量符號與原問題約束方向有關(guān)。約束為“≤”且目標求max時對偶變量≥0約束為“”時對偶變量無符號限制。2.3 運輸問題與指派問題題目9在運輸問題中當總產(chǎn)量大于總銷量時可以通過增加一個____使其轉(zhuǎn)化為產(chǎn)銷平衡問題。答案虛擬銷地。解析虛擬銷地對應的運價通常設(shè)為0其銷量等于總產(chǎn)量與總銷量之差。虛銷地運量在實際方案中代表某產(chǎn)地沒有運出去的貨物量。題目10運輸問題中用位勢法計算檢驗數(shù)的原理是若所有非基變量的檢驗數(shù)____則當前調(diào)運方案為最優(yōu)方案。答案都大于等于零≥0對于求最小費用問題。解析這是運輸問題最優(yōu)性檢驗的核心結(jié)論。理解成“當前方案沒有改進空間”即可檢驗數(shù)小于0說明還有更省錢的調(diào)整方案。題目11指派問題的標準數(shù)學模型要求每項任務只能由一人完成每人只能承擔____項任務目標為總效率____。答案一最大或最小看題目設(shè)定。解析指派問題的系數(shù)矩陣是方陣如果人數(shù)與任務數(shù)不等需要添加虛擬的人或任務對應效率設(shè)為0。2.4 圖論、排隊論與動態(tài)規(guī)劃題目12在M/M/1排隊模型中第一個M表示到達過程服從____第二個M表示服務時間服從____數(shù)字1表示____。答案泊松流到達間隔為負指數(shù)分布負指數(shù)分布只有一個服務臺。解析這個題每年都有學?？?。需要記住為什么叫“M”是馬爾可夫性的意思說明過程無記憶性。題目13在動態(tài)規(guī)劃中某階段的狀態(tài)變量應具有____性質(zhì)即當前狀態(tài)已能完全決定未來決策與該階段之前的歷史無關(guān)。答案無后效性馬爾可夫性。解析這是動態(tài)規(guī)劃建模最核心的假設(shè)條件也是判斷一個問題能否用動態(tài)規(guī)劃求解的重要依據(jù)。題目14網(wǎng)絡圖中關(guān)鍵線路是總時差為____的工作線路它決定整個工程的工期。答案零。解析關(guān)鍵線路上的工作一點都不能拖延否則總工期延誤。計算題中求關(guān)鍵線路和總工期是重點。這十幾道填空題基本覆蓋了期末考試的高頻概念。你如果能把每道題涉及的章節(jié)都展開復習一遍填空題的得分就有保障了。3. 線性規(guī)劃建模與單純形法從設(shè)變量到最優(yōu)表一步步走計算題的大頭在線性規(guī)劃。它有兩種考法一種是給你實際情景讓你建模另一種是直接給數(shù)學模型讓你用單純形法迭代求最優(yōu)解。這兩類我都給出一道典型題目并把中間的迭代過程寫清楚。3.1 生產(chǎn)計劃建模題與標準形式轉(zhuǎn)換題目某工廠計劃生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)1件甲產(chǎn)品需消耗A原料3kg、B原料2kg利潤為50元生產(chǎn)1件乙產(chǎn)品需消耗A原料2kg、B原料4kg利潤為60元。該工廠現(xiàn)有A原料120kg、B原料160kg。問應如何安排生產(chǎn)使總利潤最大請建立線性規(guī)劃模型。這個題非常簡單但能完整體現(xiàn)建模的四個要素決策變量、目標函數(shù)、約束條件、非負約束。設(shè)生產(chǎn)甲產(chǎn)品x?件、乙產(chǎn)品x?件則模型為max z 50x? 60x?s.t. 3x? 2x? ≤ 1202x? 4x? ≤ 160x?, x? ≥ 0建模題的關(guān)鍵在于判斷“約束條件”與“目標函數(shù)”哪個該放一邊。很多同學容易把原料約束寫反其實記住一句話受限制的寫在約束條件里要優(yōu)化的寫在目標函數(shù)里。資源消耗不能超過資源總量這就是約束利潤要盡可能大這就是目標。進一步把它轉(zhuǎn)換成標準形式以備單純形法使用。由于兩個約束都是“≤”類型引入松弛變量x?、x?得到max z 50x? 60x?s.t. 3x? 2x? x? 1202x? 4x? x? 160x?, x?, x?, x? ≥ 0松弛變量x?、x?實際上表示被閑置的原料量它的系數(shù)是1目標函數(shù)系數(shù)為0不影響利潤。3.2 單純形法完整迭代以兩變量模型為例很多人對單純形法的印象是“表格特別多、符號容易搞混”其實只要抓牢三個要素就行基變量、進基出基規(guī)則、檢驗數(shù)。下面用一個更小巧的模型完整走一遍過程。題目求解線性規(guī)劃問題max z 3x? 2x?s.t. x? x? ≤ 4x? ≤ 2x? ≤ 3x?, x? ≥ 0先引入松弛變量x?、x?、x?標準形式為max z 3x? 2x?s.t. x? x? x? 4x? x? 2x? x? 3各變量 ≥ 0初始基可行解令x?和x?為非基變量取0則x?4x?2x?3初始目標值z0。初始單純形表為基變量x?x?x?x?x?右端項x?111004x?100102x?010013檢驗數(shù)-3-20000檢驗數(shù)中最小的是-3對應x?所以x?進基。接著確定出基變量用右端項除以x?列正系數(shù)4/142/12x?這一行x?系數(shù)為0不參與比值最小比值是2對應x?出基。主元是x?行的x?系數(shù)1。進行一次高斯消去讓x?列變成單位向量保持x?行不變將x?行減去x?行檢驗數(shù)行加上3倍x?行。得到第二張表基變量x?x?x?x?x?右端項x?011-102x?100102x?010013檢驗數(shù)0-20306第二張表里檢驗數(shù)最小-2對應x?進基。比值檢驗x?行2/12x?行3/13最小比值2所以x?出基。主元是x?行x?列的1。再次消去x?列變成單位向量x?行不變x?行減去x?行x?行x?系數(shù)為0不用動x?行減去x?行檢驗數(shù)行加上2倍x?行。結(jié)果基變量x?x?x?x?x?右端項x?011-102x?100102x?00-1111檢驗數(shù)0021010所有檢驗數(shù)都≥0迭代停止。最優(yōu)解為x?2、x?2、x?1松弛變量最優(yōu)目標值z10。虛線上方的x?0、x?0說明兩個資源約束都用滿了而x?1說明第三個資源x?≤3還有1單位剩余?？紙鼋ㄗh單純形法的計算量不算大但一定要規(guī)范列表格、標出主元。我見過太多同學代數(shù)不列檢驗數(shù)靠心算是基變量的系數(shù)列還是非基變量的系數(shù)列最后一步錯得離譜。寧可多寫一行也不要跳步。3.3 對偶問題與靈敏度分析?？夹问綄ε紗栴}是線性規(guī)劃的一個獨立考點常與靈敏度分析一起出現(xiàn)。它的核心是對稱關(guān)系max問題對應對偶的min問題約束方向和變量符號也有對應規(guī)則。題目寫出下面線性規(guī)劃問題的對偶問題。max z 4x? 3x?s.t. x? 2x? ≤ 103x? x? ≤ 15x?, x? ≥ 0設(shè)對偶變量為y?、y?分別對應原問題的兩個約束原問題目標為max、約束為“≤”則對偶問題的目標為min約束為“≥”目標系數(shù)和約束系數(shù)矩陣互為轉(zhuǎn)置。對偶模型為min w 10y? 15y?s.t. y? 3y? ≥ 42y? y? ≥ 3y?, y? ≥ 0靈敏度分析的考點則是某資源增加一個單位最優(yōu)目標值變化多少。答案就是該約束對應的影子價格也就是對偶最優(yōu)解。比如上面問題中如果對偶最優(yōu)解是y?1、y?1說明第一資源量從10增加到11時最優(yōu)利潤會增加1第二資源同理。這類題不需要重新求解單純形表直接用互補松弛定理或讀影子價格即可。4. 運輸問題與整數(shù)規(guī)劃方案尋找、最優(yōu)性檢驗與指派問題運輸問題是每年計算題的重頭戲本質(zhì)是一個特殊結(jié)構(gòu)的線性規(guī)劃。由于約束矩陣的特殊性考試不讓你用單純形法而是要求掌握表上作業(yè)法先求初始調(diào)運方案再用位勢法檢驗最后用閉回路調(diào)整。4.1 最小元素法求初始方案位勢法驗最優(yōu)題目某產(chǎn)品有三個產(chǎn)地A?、A?、A?產(chǎn)量分別為120、180銷往三個銷地B?、B?、B?銷量分別為100、150、50。單位運價如下表求使總運費最小的調(diào)運方案。產(chǎn)地\銷地B?B?B?產(chǎn)量A?865120A?576180銷量10015050300先檢查產(chǎn)銷平衡總產(chǎn)量120180300總銷量10015050300產(chǎn)銷平衡可以直接用表上作業(yè)法。最小元素法的思路是“哪個格子運價最低就先盡量往哪個格子運”。運價表中最低運價有兩個A?到B?是5A?到B?也是5任意選一個先運。這里選A?→B?運量為min(120,50)50于是B?需求完成A?剩余70。此時把B?列劃去。剩余運價中最低為A?→B?的5運量為min(180,100)100B?需求完成A?剩余80。劃去B?列。剩余運價中A?→B?為6A?→B?為7選擇A?→B?運量為min(70,150)70A?用完B?剩余80。最后A?→B?運80A?用完。初始調(diào)運方案為A?→B?運70A?→B?運50A?→B?運100A?→B?運80?？傔\費 70×6 50×5 100×5 80×7 420 250 500 560 1730。接下來用位勢法檢驗。基變量個數(shù)為4個應該等于mn-123-14恰好非退化設(shè)行位勢為u?、u?列位勢為v?、v?、v?。對每個基變量有u?v?c??。令u?0可解得A?→B?0v?6得v?6A?→B?0v?5得v?5A?→B?u?67得u?1A?→B?1v?5得v?4。然后計算非基變量的檢驗數(shù)σc??-(u?v?)A?→B?8-(04)4A?→B?6-(15)0。由于所有檢驗數(shù)≥0當前方案即為最優(yōu)方案最低運費1730。這里有個細節(jié)A?→B?的檢驗數(shù)為0說明存在另一個最優(yōu)方案但目標值相同?？荚囬喚頃r只要運費正確、方案合理一般都給滿分。4.2 當檢驗數(shù)出現(xiàn)負數(shù)閉回路調(diào)整怎么做如果檢驗數(shù)出現(xiàn)負數(shù)說明當前方案不是最優(yōu)。調(diào)整的方法是選檢驗數(shù)最小的非基變量進基從該格子出發(fā)找閉回路閉回路的偶數(shù)頂點上減去進基變量最小運量奇數(shù)頂點加上同樣運量得到新方案。舉例來說承接上題如果某一非基變量檢驗數(shù)為-2比如假設(shè)A?→B?檢驗數(shù)為-2注意上題實際是4那么從A?→B?出發(fā)沿水平或垂直方向找基變量頂點形成回路。假定回路頂點為A?→B?進基→A?→B?基→A?→B?基→A?→B?基→回到起點。奇數(shù)頂點運量分別為A?→B?的70、A?→B?的100取最小70于是進基變量A?→B?運量為70回路奇數(shù)頂點減去70偶數(shù)頂點加上70。這個調(diào)整過程雖然說起來簡單但考場上看錯行列坐標的人非常多我建議找回路時用筆把格子的行列號標出來每走一步都確認是不是基變量格子。4.3 指派問題匈牙利法的步驟與計算實例指派問題屬于整數(shù)規(guī)劃中的0-1規(guī)劃特例。3個人完成3項任務的效率矩陣如下求使總效率最大的最優(yōu)指派方案。題目某班組有3名工人甲、乙、丙需完成3項任務A、B、C。每個人完成不同任務的效率見下表求總效率最大的指派方案。工人\任務ABC甲483乙768丙574匈牙利法一般處理最小化問題最大化要先把矩陣轉(zhuǎn)換為最小化。轉(zhuǎn)換方式是取每行最大值或矩陣最大值減去該行元素把它變成“損失矩陣”。這里每行最大值分別為8、8、7轉(zhuǎn)換后矩陣為甲4 0 5乙1 2 0丙2 0 3接著逐行找最小值并減去第一行減去0第二行減去0第三行減去0矩陣不變。然后逐列找最小值并減去第一列min(4,1,2)1減去后第一列為3,0,1第二列min(0,2,0)0第三列min(5,0,3)0。得到甲3 0 5乙0 2 0丙1 0 3用最少的直線覆蓋所有0元素最少畫線數(shù)為33行或3列時已覆蓋等于矩陣階數(shù)可以進行試指派。從只有唯一0的行開始乙行只有一個0在A所以乙→A丙行有兩個0在B和C甲行只有一個0在B。先指派甲→B丙→C檢查安排為甲→B、乙→A、丙→C對應原效率87419。還有另一種丙→B、甲行就沒有0可選甲只有B被丙占用則甲無法指派所以不是最優(yōu)。因此最優(yōu)指派是甲→B、乙→A、丙→C最大總效率19。這個例子雖然簡單但能完整展示“移減去零→試指派”的邏輯。真正的考試題往往是4×4或5×5試指派時可能遇到覆蓋線數(shù)小于階數(shù)的情況那時需要繼續(xù)做“無零元素的調(diào)整”步驟本質(zhì)上是在未覆蓋元素中找最小值重復減加操作。碰到這類題時記住不要著急試指派先確認畫線數(shù)與階數(shù)相等否則一定漏了步驟。5. 圖、動態(tài)規(guī)劃與排隊論三類常見計算題的代表性解法這些板塊在不同學?？碱l差別很大但一旦考到題型通常非常固定。這里各給出一道具有代表性的題目。5.1 最短路問題Dijkstra標號法題目求下圖中從v?到v?的最短路圖中各邊權(quán)值已標出v?→v?權(quán)2v?→v?權(quán)5v?→v?權(quán)1v?→v?權(quán)6v?→v?權(quán)4v?→v?權(quán)3v?→v?權(quán)1v?→v?權(quán)5v?→v?權(quán)2。Dijkstra標號法的做法是給每個頂點維護一個當前最短距離標號每次從未標號的頂點中選距離最小的那個更新它鄰接頂點的距離。迭代過程如下初始d(v?)0其余頂點標為∞。第一輪選v?更新v?為2v?為5。第二輪未標號中最小是v?距離2選擇v?更新v?為min(5, 21)3更新v?為268。第三輪未標號最小是v?距離3更新v?為min(8, 34)7更新v?為336。第四輪未標號最小是v?距離6更新v?為min(7, 61)7更新v?為628。第五輪最小是v?距離7更新v?為min(8, 75)8。最終v?最短距離為8。對應的最短路有多條比如v?→v?→v?→v?→v?距離21328。Dijkstra的適用條件是邊權(quán)非負考試圖題基本都滿足?？紙鋈菀族e在“更新順序”上一定要先選當前最小標號點再用它去更新而不是按頂點序號順序更新。5.2 動態(tài)規(guī)劃資源分配/背包問題題目用動態(tài)規(guī)劃求解下列背包問題背包容量為10有3件物品重量分別為3、4、5價值分別為4、5、6每件物品最多取1件求最大總價值。動態(tài)規(guī)劃的核心是定義狀態(tài)、狀態(tài)轉(zhuǎn)移方程和邊界條件。設(shè)f(k, c)表示“考慮前k件物品、容量為c時的最大價值”。狀態(tài)轉(zhuǎn)移方程為f(k, c) max{ f(k-1, c), f(k-1, c-w_k) v_k }前提是c≥w_k填表過程第一件物品w3, v4容量0~2取0容量3~10取4。第二件物品w4, v5容量0~2取0容量3取4容量4~6可以取max(4, 05)5其中容量4、5取5容量6取5容量7~10可以取max(4, 45)97時取前一件加第二件459。第三件物品w5, v6容量0~2取0容量3取4容量4取5容量5~6取max(5,06)6容量7~8取max(9, 46)10容量9~10取max(9, 56)11。所以最優(yōu)總價值為11對應選擇第二件和第三件價值5611總重量459不超過容量10。這類題的得分點在于寫出階段、狀態(tài)、決策、狀態(tài)轉(zhuǎn)移方程和最終表。就算填表數(shù)字算錯方程寫對也能拿到大半過程分所以千萬別只寫答案不寫方程。5.3 排隊論M/M/1模型的基本指標題目某售票窗口顧客到達服從泊松流平均每小時到達12人服務時間服從負指數(shù)分布平均每小時服務20人。求系統(tǒng)空閑的概率、平均隊長、平均等待時間。M/M/1模型的關(guān)鍵參數(shù)是服務強度ρλ/μ。λ12人/小時μ20人/小時ρ12/200.6。系統(tǒng)空閑概率P?1-ρ0.4。平均隊長L?ρ/(1-ρ)0.6/0.41.5人。平均等待時間W_q L_q/λ而平均等待隊長L_q ρ2/(1-ρ)0.36/0.40.9人所以W_q0.9/120.075小時4.5分鐘。如果需要平均逗留時間W? 1/(μ-λ)1/(20-12)0.125小時7.5分鐘。這個題的易錯點是把隊長和等待隊長搞混。平均隊長L?包含正在接受服務的那個顧客而平均等待隊長L_q只包含排隊的人。考試時先寫公式再代數(shù)字避免最后答案對不上公式時丟分。6. 考場實戰(zhàn)策略計算題的表格規(guī)范與時間分配計算題能不能拿高分很大程度取決于考場上的書寫規(guī)范。單純形法、運輸問題、指派問題、動態(tài)規(guī)劃填表這幾類都有標準步驟評卷時按步驟給分。我整理了幾條實操建議都是自己在考試和輔導中總結(jié)出來的。第一每次迭代都完整列出單純形表并在表中標出主元行、主元列和主元。這樣即使最后最優(yōu)解算錯閱卷老師也能看到你迭代邏輯正確過程分不會少。不要跳步去合并表格那種寫法風險很大一步手滑整表作廢。第二運輸問題的初始調(diào)運方案畫表時注意標記哪行哪列已被劃去基變量數(shù)量要等于mn-1。如果沒有達到這個數(shù)量說明出現(xiàn)了退化需要把運量為0的格子當成基變量格子補足否則位勢法會出現(xiàn)解不出位勢的情況。很多同學就是在這里卡殼的。第三動態(tài)規(guī)劃題中狀態(tài)轉(zhuǎn)移方程一定要放在顯著位置。閱卷人往往先掃方程再看表格方程對了表格個別數(shù)值有誤也能拿到大部分分。計算最短路時建議在每個頂點旁標一個“當前最短距離前驅(qū)”最后回溯路徑時可以直接看清楚。第四關(guān)于時間分配。我建議根據(jù)分值倒推時間假設(shè)卷面滿分100、考試時間120分鐘大概1分對應1.2分鐘。線性規(guī)劃大題給20分就留20到25分鐘不要因為它出現(xiàn)在第一題就戀戰(zhàn)。填空、選擇最多半小時內(nèi)做完不會的先跳過計算題優(yōu)先做最熟練的題型。先把能拿的分穩(wěn)穩(wěn)拿到再回頭摳難題。第五考試時準備一張草稿紙專門做“計算復核”。比如單純形表的行變換每次消元后用“原行加主元的倍數(shù)”重新算一遍檢驗數(shù)或者運輸問題算完總費用再按原始運價表手算一遍這能篩掉至少一半的算術(shù)錯誤。運籌學的計算本身不難丟分基本都是粗心造成的。這類考試里還有一個常見的隱性陷阱題目給的是“利潤最大化”但表格里卻是“費用”或者給的是“最大運輸量”卻要求“最小運費”。讀題時花十秒鐘確認目標方向比做完一堆計算才發(fā)現(xiàn)方向反了要劃算得多。做題時把“max”或“min”圈出來就等于給全卷加了一層保險。運籌學復習到最后拼的不只是誰公式背得熟而是誰能把流程完整、規(guī)范地寫出來。把上面這些題從“看懂”變成“會算”再變成“算得又對又快”考試基本就穩(wěn)了。如果你手里有哪道題反復做不對多半是中間某步流程有遺漏回頭對照標準步驟比盲目刷十道新題更管用。