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