運籌學(xué)復(fù)習參考資料-資料下載頁
2025-04-17 12:13本頁面
【正文】 好有n個人每人可去完成其中一項工作，效果要好。工作指派問題的特殊解法——“匈牙利法”（考?。。┙忸}步驟：使系數(shù)矩陣（效率矩陣）各行、各列出現(xiàn)零元素。作法：①行約簡—系數(shù)矩陣各行元素減去所在行的最小元素，②列約簡—再從所得矩陣的各列減去所在列最小元素。試求最優(yōu)解。如能找出n個位于不同行不同列的零元素，令對應(yīng)的xij= 1，其余xij = 0，得最優(yōu)解，結(jié)束；否則下一步。作法：由獨立0元素的行（列）開始，獨立0元素處畫（ ）標記 ，在有（ ）的行列中劃去（也可打*）其它0元素；再在剩余的0元素中重復(fù)此做法，直至不能標記（ ）為止。作能覆蓋所有0元素的最少數(shù)直線集合。作法：① 對沒有（ ）的行打√號；②對已打√號的行中所有0元素的所在列打√號；③再對打有√號的列中0元素的所在行打√號；④重復(fù)②、③直到得不出新的打√號的行(列)為止；⑤對沒有打√號的行畫一橫線，對打√號的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)。⑥未被直線覆蓋的最小元素為cij,在未被直線覆蓋處減去cij,在直線交叉處加上cij。重復(fù)3，直到求得最優(yōu)解。類型一：求極小值的匈牙利法：（重點掌握這種基本問題）例1：有甲、乙、丙、丁四個人，要派去完成A、B、C、D四項工作，他們完成的工時如下表：人務(wù)時工任 A B C D甲乙丙丁6 12 13 410 3 12 147 14 13 168 8 12 10試問：應(yīng)如何分配任務(wù)可使總工時為最少？解：用“匈牙利法”求解。已知條件可用系數(shù)矩陣（效率矩陣）表示為：行約簡列約簡（cij）= ABCD標號甲乙丙丁 ∴使總工時為最少的分配任務(wù)方案為：甲→D，乙→B，丙→A，丁→C此時總工時數(shù)W=4+3+7+12=26例2：求效率矩陣的最優(yōu)解。列約簡行約簡解： 標號 所畫（）0元素少于n，未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）：√√√未被直線覆蓋的最小元素為cij=1,在未被直線覆蓋處減去1,在直線交叉處加上1。標號 ∴得最優(yōu)解：類型二：求極大值的匈牙利法：min z=－max（－z）（cij）→（M－cij）=（bij），（cij）中最大的元素為Mmax z===－ 第二部分 動態(tài)規(guī)劃只要求掌握動態(tài)規(guī)劃的最短路問題——用“圖上標號法”解決：具體解題步驟請參看教材（這是本套資料少見的與教材完全相同的算法類型之一，務(wù)必看書掌握）只有完全理解了這種作法（思路：逆向追蹤）才有可能做題，考試時數(shù)字無論如何變化都能作出正確求解！第二部分到此結(jié)束第三部分 網(wǎng)絡(luò)分析一、求最小生成樹（最小支撐樹、最小樹）問題：破圈法——任取一個圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個步驟，直到得到一個不含圈的圖為止，這時的圖便是最小樹。參考例題：例：求下圖的最小生成樹：67941510v2v1v3v5v4v6328解：用“破圈法”求得最小生成樹為：9415v2v1v3v5v4v62已得最小樹，此時權(quán)w=1+2+4+5+9=21為最小。二、最短路問題：（有向圖）TP標號法（狄克斯托算法）——具體解題步驟請參看教材P125（這是本套資料少見的與教材完全相同的算法類型之一，務(wù)必看書掌握）只有完全理解了這種作法（思路：順向追蹤）才有可能做題，考試時數(shù)字無論如何變化都能作出正確求解！參考例題：例：教材P124圖4—8的例子（略）三、網(wǎng)絡(luò)最大流問題：尋求網(wǎng)絡(luò)最大流的標號法（福特—富克爾遜算法）——具體解題步驟請參看教材P130。（教材用有序數(shù)對（fij，cij）表示（流量，容量），但我們解題算法格式按南郵要求，用大多數(shù)《運籌學(xué)》書籍中的標準格式，即用有序數(shù)對（cij，fij）表示（容量，流量）。解法本質(zhì)是相同的。）只有完全理解了這種作法（思路：標號檢查、迭代調(diào)整）才有可能做題，考試時數(shù)字無論如何變化都能作出正確求解！第三部分到第四部分 存儲論（簡介）隨機存儲模型參考例題：例：一食品店要決定每天牛奶的進貨量，該店根據(jù)過去的銷售經(jīng)驗，知道需求量的概率分布如下：需求x（箱）25262728p（x）若進貨每箱80元，售價100元，又若當天不能售出因牛奶變質(zhì)而全部損失，試確定每天進貨量。解法一：已知C=80， p=100，g=0，需求x（箱）25262728概率p（x）累計概率1根據(jù)單周期隨機型存儲模型 （“報童模型”）之離散型隨機存儲模型公式，可得即可以確定進貨26箱，獲利的期望值最大。解法二：k=100－80=20，h=80.==∵P{x=25}=＜≤P{x=25}+P{x=26}=∴可以確定進貨26箱，獲利的期望值最大。注：該問題即“報童問題”（關(guān)于報童進報紙問題的數(shù)學(xué)模型），即是相當于將上題的進“牛奶”改為進“報紙”等等，解法思路是完全一致的，請注意！ 第 20 頁 共 20
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1