運(yùn)籌學(xué)復(fù)習(xí)參考資料(參考版)
2025-04-20 12:13本頁(yè)面
【正文】 注：該問(wèn)題即“報(bào)童問(wèn)題”（關(guān)于報(bào)童進(jìn)報(bào)紙問(wèn)題的數(shù)學(xué)模型），即是相當(dāng)于將上題的進(jìn)“牛奶”改為進(jìn)“報(bào)紙”等等，解法思路是完全一致的，請(qǐng)注意！ 第 20 頁(yè) 共 20 頁(yè)。解法一：已知C=80， p=100，g=0，需求x（箱）25262728概率p（x）累計(jì)概率1根據(jù)單周期隨機(jī)型存儲(chǔ)模型 （“報(bào)童模型”）之離散型隨機(jī)存儲(chǔ)模型公式，可得即可以確定進(jìn)貨26箱，獲利的期望值最大。解法本質(zhì)是相同的。二、最短路問(wèn)題：（有向圖）TP標(biāo)號(hào)法（狄克斯托算法）——具體解題步驟請(qǐng)參看教材P125（這是本套資料少見的與教材完全相同的算法類型之一，務(wù)必看書掌握）只有完全理解了這種作法（思路：順向追蹤）才有可能做題，考試時(shí)數(shù)字無(wú)論如何變化都能作出正確求解！參考例題：例：教材P124圖4—8的例子（略）三、網(wǎng)絡(luò)最大流問(wèn)題：尋求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法（福特—富克爾遜算法）——具體解題步驟請(qǐng)參看教材P130。在余下的圖中，重復(fù)這個(gè)步驟，直到得到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹。列約簡(jiǎn)行約簡(jiǎn)解： 標(biāo)號(hào) 所畫（）0元素少于n，未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）：√√√未被直線覆蓋的最小元素為cij=1,在未被直線覆蓋處減去1,在直線交叉處加上1。類型一：求極小值的匈牙利法：（重點(diǎn)掌握這種基本問(wèn)題）例1：有甲、乙、丙、丁四個(gè)人，要派去完成A、B、C、D四項(xiàng)工作，他們完成的工時(shí)如下表：人務(wù)時(shí)工任 A B C D甲乙丙丁6 12 13 410 3 12 147 14 13 168 8 12 10試問(wèn)：應(yīng)如何分配任務(wù)可使總工時(shí)為最少？解：用“匈牙利法”求解。⑥未被直線覆蓋的最小元素為cij,在未被直線覆蓋處減去cij,在直線交叉處加上cij。作能覆蓋所有0元素的最少數(shù)直線集合。如能找出n個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的xij= 1，其余xij = 0，得最優(yōu)解，結(jié)束；否則下一步。作法：①行約簡(jiǎn)—系數(shù)矩陣各行元素減去所在行的最小元素，②列約簡(jiǎn)—再?gòu)乃镁仃嚨母髁袦p去所在列最小元素。六、目標(biāo)規(guī)劃問(wèn)題已知目標(biāo)規(guī)劃問(wèn)題min z= p1 d1 + p2d2 + p3（5d3 + 3d4 ） + p4 d1+x1 +2x2 + d1 d1+ =6x1 +2x2 + d2 d2+ =9x1 2x2 + d3 d3+ =4x2 + d4 d4+ =2x1 ，x2≥0，di , di+≥0 (i=1,2,3,4)分別用圖解法和單純形法求解x2d2+54d2d4+d3d1+3Ad4d12d3+B10 2 4 6 8 x1七（1）、整數(shù)規(guī)劃問(wèn)題（分枝定界法）：用分枝定界法求解整數(shù)規(guī)劃七（2）、工作指派問(wèn)題：工作指派問(wèn)題的數(shù)學(xué)模型——假定有n項(xiàng)工作需要完成，恰好有n個(gè)人每人可去完成其中一項(xiàng)工作，效果要好。求下面運(yùn)輸問(wèn)題的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v1=2v2=9v3=3v4=101934u1=01311310743u2=121923431u3=53741059633656則：，最小值為6，非基變量為，閉回路，最大調(diào)整量為1，得新解：，重新計(jì)算位勢(shì)及影響系數(shù)，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=721923431u3=53741059633656，最小值為5，非基變量為，閉回路，最大調(diào)整為2，得新解：重新計(jì)算位勢(shì)及影響系數(shù)，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=221923413u3=03741059633656，此時(shí)，故當(dāng)前解為最優(yōu)解。②檢驗(yàn)后調(diào)整運(yùn)輸方案的辦法是：在空格的閉回路中所有的偶點(diǎn)均加上奇點(diǎn)中的最小運(yùn)量，所
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1