物流運籌方法與工具（第3版）目錄

CONTENTS物流運籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務指派運輸方案優(yōu)化運輸路徑規(guī)劃物流項目計劃物流需求預測庫存水平控制模塊四模塊二模塊三模塊五模塊六模塊七模塊八模塊九模塊一模塊四物流任務指派任務指派概述指派問題的匈牙利法0-1規(guī)劃問題應用舉例單元四單元三單元一單元二知識點1．知道整數(shù)規(guī)劃問題的實踐意義。2．理解指派問題的含義及其數(shù)學模型的特征。3．掌握匈牙利法的算法步驟及特殊指派問題的處理方法。4．知道0-1規(guī)劃的實踐意義。5．掌握0-1規(guī)劃問題的模型構(gòu)建方法。6．知道隱枚舉法的求解過程。本單元知識點能力點、素質(zhì)點能力點：能用“指派問題”解決物流領(lǐng)域中人力、物力、財力等資源與工作任務、服務項目等的合理搭配問題，創(chuàng)造最大價值。能對物流固定設(shè)施選址問題建立“0-1規(guī)劃”模型。素質(zhì)點：擁有各司其職、各盡其責、勇于擔當、團隊協(xié)作的職業(yè)精神。單元二指派問題的匈牙利法一二三匈牙利法步驟匈牙利法求解過程特殊指派問題的處理定理1

：定理2

：一、匈牙利法步驟如果從分配問題效率矩陣[cij]的每一行(列)元素中分別減去(或加上)一個常數(shù)ui(vj)得到一個新的效率矩陣[bij]，其中bij=cij-ui-vj，則[bij]的最優(yōu)解等價于[cij]的最優(yōu)解，其中cij及bij均非負。若矩陣A的元素可分成“0”與非“0”兩部分，則覆蓋零元素的最少直線數(shù)等于位于不同行不同列的零元素(稱為獨立元素)的最大個數(shù)。一、匈牙利法步驟匈牙利方法求解指派問題的步驟為：第一步：將效率矩陣[cij]每行的各元素減去該行的最小元素，再將所得矩陣每列的各元素減去該列的最小元素。

第二步：用最少條數(shù)的直線覆蓋全部的零元素。方法如下：（1）檢查效率矩陣C的每行、每列，在零元素最少的行(列)中任選一個零元素并對其打上括號，將該“0”所在行、列其他零元素全部打上“×”，同時對打括號及“×”的零元素所在行或列畫一條直線。（2）重復步驟（1），在剩下的沒有被直線覆蓋的行、列中再找最少的零元素，打上括號、打上“×”及畫線，直到所有的零元素被直線覆蓋。如果效率矩陣每行（或列）都有一個打括號的零元素，則上述步驟得到的打括號的零元素都位于不同行不同列，令對應打括號零元素的變量xij等于1就得到了問題的最優(yōu)解；如果效率矩陣中打括號的零元素個數(shù)小于m，轉(zhuǎn)入第三步。第三步：利用定理1對矩陣進行變換，增加獨立零元素的個數(shù)。二、匈牙利法求解過程例4-2

用匈牙利法求解例4-1。解：該問題的價值系數(shù)矩陣為

二、匈牙利法求解過程按步驟（一），得：二、匈牙利法求解過程因C2每列已含0元素，不必對列進行簡約化。

按步驟（二），得：二、匈牙利法求解過程

覆蓋所有0元的最少直線數(shù)m=4,4<5,按步驟（三）中m<n方案，得：二、匈牙利法求解過程

回到步驟（二）：覆蓋所有0元的最少直線數(shù)m=5=n，回到步驟（二）中m=n方案，得：二、匈牙利法求解過程

即相應最優(yōu)解為：x13=x25=x32=x41=x54=1,其余xij=0回顧：故在該分配問題中，最優(yōu)目標函數(shù)值為3+3+3+4+4=17；即讓甲去完成任務C，乙去完成任務E，丙去完成任務B，丁去完成任務A，戊去完成任務D，這樣可使總用時量最少（17小時）。三、特殊指派問題的處理1．求解最大值指派問題可轉(zhuǎn)化為求解最小值指派問題。只要取

M=max{cij|i,j=1,2,…,n}然后令

dij=M-cij

(i,j=1,2,…,n)則對應于系數(shù)矩陣D=(dij)n×n的最小值分配就是原問題的最大值分配。三、特殊指派問題的處理2．某人一定不能完成某項任務時，若原問題求最小值，令對應的效率為一個大M即可；若原問題求最大值，令對應的效率為0即可。例4-3三、特殊指派問題的處理3．指派問題的人數(shù)和任務數(shù)不相等的情況。設(shè)指派問題中人數(shù)為m，任務數(shù)為