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

CONTENTS物流運籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務(wù)指派運輸方案優(yōu)化運輸路徑規(guī)劃物流項目計劃技術(shù)物流需求預(yù)測庫存水平控制模塊四模塊二模塊三模塊五模塊六模塊七模塊八模塊九模塊一模塊四物流任務(wù)指派任務(wù)指派概述指派問題的匈牙利法0-1規(guī)劃問題應(yīng)用舉例單元四單元三單元二單元一知識點1．知道整數(shù)規(guī)劃問題的實踐意義。2．理解指派問題的含義及其數(shù)學(xué)模型的特征。3．掌握匈牙利法的算法步驟及特殊指派問題的處理方法。4．知道0-1規(guī)劃的實踐意義。5．掌握0-1規(guī)劃問題的模型構(gòu)建方法。6．知道隱枚舉法的求解過程。本單元知識點能力點、素質(zhì)點能力點：能用“指派問題”解決物流領(lǐng)域中人力、物力、財力等資源與工作任務(wù)、服務(wù)項目等的合理搭配問題，創(chuàng)造最大價值。能對物流固定設(shè)施選址問題建立“0-1規(guī)劃”模型。素質(zhì)點：擁有各司其職、各盡其責(zé)、勇于擔(dān)當(dāng)、團隊協(xié)作的職業(yè)精神。某連鎖經(jīng)營公司為實現(xiàn)最低物流成本、最好物流服務(wù)的“雙贏”目標(biāo)，欲將其超市業(yè)務(wù)覆蓋（服務(wù)）整個市區(qū)，為實現(xiàn)這一目標(biāo)，首先要在市內(nèi)增建幾個超市。公司進行了調(diào)研，得到尚未覆蓋到的居民區(qū)信息（編號為1，2，…，12）、可以建超市的候選地址（編號為A，B，…，H），和每個超市可以覆蓋的居民區(qū)的數(shù)據(jù)資料，并對各候選地址的建設(shè)成本作了估計，相關(guān)數(shù)據(jù)見表4-1。問在哪些候選地址增建超市才能既覆蓋每個居民區(qū)，又使總的建設(shè)成本最低？引導(dǎo)案例某連鎖經(jīng)營公司的增建倉庫問題表4-1選址資料引導(dǎo)案例某連鎖經(jīng)營公司選址資料候選地址編號候選地址可以覆蓋的居民區(qū)建設(shè)成本（百萬元）ABCDEFGH1，2，3，7，81，5，7，92，8，9，121，3，63，4，10，114，5，9，125，6，117，10，128.266.57.1497.36.2單元一任務(wù)指派概述一二三整數(shù)線性規(guī)劃問題指派問題的含義指派問題的數(shù)學(xué)模型整數(shù)線性規(guī)劃：指派問題和0-1規(guī)劃問題：一、整數(shù)線性規(guī)劃問題如果線性規(guī)劃模型中所有變量取值均為整數(shù)，則稱為純整數(shù)規(guī)劃問題，如果只有一部分變量要求為整數(shù)，則稱之為混合整數(shù)規(guī)劃問題。此外，當(dāng)模型中變量只取0或1的值時，稱為0-1規(guī)劃問題。整數(shù)線性規(guī)劃的特殊形式——指派問題和0-1規(guī)劃問題。二、指派問題的含義指派問題也稱分配問題，是整數(shù)規(guī)劃問題中特殊的0-1規(guī)劃問題。典型的指派問題是指：有n項不同的工作要做，恰好有n個人（或設(shè)備）可以分別完成其中的一項工作，但由于任務(wù)性質(zhì)和個人專長不同，因而由不同的人去完成不同的工作的效率（或所需的資源）是不一樣的。如何安排才能使工作總效率最高（或所需總資源最少）？三、指派問題的數(shù)學(xué)模型指派問題的決策變量其中i,j=1,2,…,n。用Z表示總成本，cij為第i個人做第j項工作的費用，則指派問題目標(biāo)為最小化時的一般模型是：三、指派問題的數(shù)學(xué)模型s.t.式（4.1）說明第i人只能做1項工作，式（4.2）說明第j項工作只能由1人去完成。

模塊四物流任務(wù)指派任務(wù)指派概述指派問題的匈牙利法0-1規(guī)劃問題應(yīng)用舉例單元四單元三單元一單元二知識點1．知道整數(shù)規(guī)劃問題的實踐意義。2．理解指派問題的含義及其數(shù)學(xué)模型的特征。3．掌握匈牙利法的算法步驟及特殊指派問題的處理方法。4．知道0-1規(guī)劃的實踐意義。5．掌握0-1規(guī)劃問題的模型構(gòu)建方法。6．知道隱枚舉法的求解過程。本單元知識點能力點、素質(zhì)點能力點：能用“指派問題”解決物流領(lǐng)域中人力、物力、財力等資源與工作任務(wù)、服務(wù)項目等的合理搭配問題，創(chuàng)造最大價值。能對物流固定設(shè)施選址問題建立“0-1規(guī)劃”模型。素質(zhì)點：擁有各司其職、各盡其責(zé)、勇于擔(dān)當(dāng)、團隊協(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）重復(fù)步驟（1），在剩下的沒有被直線覆蓋的行、列中再找最少的零元素，打上括號、打上“×”及畫線，直到所有的零元素被直線覆蓋。如果效率矩陣每行（或列）都有一個打括號的零元素，則上述步驟得到的打括號的零元素都位于不同行不同列，令對應(yīng)打括號零元素的變量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īng)最優(yōu)解為：x13=x25=x32=x41=x54=1,其余xij=0回顧：故在該分配問題中，最優(yōu)目標(biāo)函數(shù)值為3+3+3+4+4=17；即讓甲去完成任務(wù)C，乙去完成任務(wù)E，丙去完成任務(wù)B，丁去完成任務(wù)A，戊去完成任務(wù)D，這樣可使總用時量最少（17小時）。三、特殊指派問題的處理1．求解最大值指派問題可轉(zhuǎn)化為求解最小值指派問題。只要取

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

dij=M-cij

(i,j=1,2,…,n)則對應(yīng)于系數(shù)矩陣D=(dij)n×n的最小值分配就是原問題的最大值分配。三、特殊指派問題的處理2．某人一定不能完成某項任務(wù)時，若原問題求最小值，令對應(yīng)的效率為一個大M即可；若原問題求最大值，令對應(yīng)的效率為0即可。例4-3三、特殊指派問題的處理3．指派問題的人數(shù)和任務(wù)數(shù)不相等的情況。設(shè)指派問題中人數(shù)為m，任務(wù)數(shù)為n，當(dāng)m>n時虛擬m-n項任務(wù)，對應(yīng)的效率為0；當(dāng)m<n時，虛擬n-m個人，對應(yīng)的效率為0，將原問題化為人數(shù)與任務(wù)數(shù)相等的平衡問題再求解。模塊四物流任務(wù)指派任務(wù)指派概述指派問題的匈牙利法0-1規(guī)劃問題應(yīng)用舉例單元四單元一單元二單元三知識點1．知道整數(shù)規(guī)劃問題的實踐意義。2．理解指派問題的含義及其數(shù)學(xué)模型的特征。3．掌握匈牙利法的算法步驟及特殊指派問題的處理方法。4．知道0-1規(guī)劃的實踐意義。5．掌握0-1規(guī)劃問題的模型構(gòu)建方法。6．知道隱枚舉法的求解過程。本單元知識點本章能力點1．能用“指派問題”解決物流領(lǐng)域中人力、物力、財力等資源與工作任務(wù)、服務(wù)項目等的合理搭配問題，創(chuàng)造最大價值。2．能對物流固定設(shè)施選址問題建立“0-1規(guī)劃”模型。本節(jié)能力點能力點、素質(zhì)點能力點：能用“指派問題”解決物流領(lǐng)域中人力、物力、財力等資源與工作任務(wù)、服務(wù)項目等的合理搭配問題，創(chuàng)造最大價值。能對物流固定設(shè)施選址問題建立“0-1規(guī)劃”模型。素質(zhì)點：擁有各司其職、各盡其責(zé)、勇于擔(dān)當(dāng)、團隊協(xié)作的職業(yè)精神。單元三0－1規(guī)劃問題一、0-1規(guī)劃的數(shù)學(xué)模型二、0-1規(guī)劃的隱枚舉法0-1變量:一、0-1規(guī)劃的數(shù)學(xué)模型如果在整數(shù)規(guī)劃模型中，所有的變量都是取0或1的邏輯變量，則該問題稱為0-1規(guī)劃問題。對邏輯變量我們也稱為0-1變量。一、0-1規(guī)劃的數(shù)學(xué)模型例4-4

某道路修筑公司在同一時間內(nèi)可參加A1、A2、A3、A4四項道路工程的投標(biāo)。這些項目要求的工期相同。公司根據(jù)招標(biāo)文件和本公司的技術(shù)水平對每項工程進行了詳細的研究和計算，將各項工程的預(yù)期利潤、主要程序的工程量及本企業(yè)的施工能力列于表4-5。試建立使總利潤最大的數(shù)學(xué)模型。表4-5信息資料工程項目預(yù)期利潤/萬元砂/m3礫石/m3黏土/m3A1542002802500A282300880480A3748003001500A4923009005200施工能力1200016009000一、0-1規(guī)劃的數(shù)學(xué)模型解：引入0-1變量則該問題可以描述成如下的線性規(guī)劃模型maxZ=5

s.t.二、0-1規(guī)劃的隱枚舉法求解步驟如下：（1）找一個初始可行解

，得到目標(biāo)函數(shù)值的下界Z0(最小值問題則為上界)。（2）列出2n個變量取值的組合，當(dāng)組合解

對應(yīng)的目標(biāo)值Zi小于Z0(max)時，認為不可行，當(dāng)Zi大于等于Z0(max)時，再檢驗是否滿足約束條件，得到0-1規(guī)劃的可行解。（3）依據(jù)Zi的值確定最優(yōu)解。這里的下界Z0可以動態(tài)移動，當(dāng)某個Zi大于Z0時，則將Zi作為新的下界。二、0-1規(guī)劃的隱枚舉法例4-5

用隱枚舉法求解0-1規(guī)劃問題

maxZ=3x1-2x2+5x3二、0-1規(guī)劃的隱枚舉法s.t.解：根據(jù)目標(biāo)函數(shù)中xi系數(shù)的遞增順序，重新排列變量的次序，得maxZ=-2x2+3x1+5x3二、0-1規(guī)劃的隱枚舉法

按上述各變量的遞增順序列出的解有：（0，0，0），（0，0，1），（0，1，0），（0，1，1），（1，0，0），（1，0，1），（1，1，0），（1，1，1）。

顯然（0，0，0）是一個可行解，相應(yīng)的目標(biāo)函數(shù)值Z=0可作為初始過濾值。

目標(biāo)函數(shù)在（x2,x1,x3）=（0，0，1）處的值Z=5，且它是一個可行解，因5>0，故用5取代0為新的過濾值。

繼續(xù)查目標(biāo)函數(shù)在（x2,x1,x3）=（0，1，0）處的值，得Z=3，因3<5，

故它不會是最優(yōu)解，也不必查（0，1，0）是否為可行解。二、0-1規(guī)劃的隱枚舉法

再查目標(biāo)函數(shù)在（x2,x1,x3）=（0，1，1）處的值Z=8，因8>5，需查（0，1，1）是否為可行解，易知它是可行解，故用8取代5為新的過濾值。

由目標(biāo)函數(shù)maxZ=-2x2+3x1+5x3

≤3x1+5x3

≤3×1+5×1=8可知，目標(biāo)函數(shù)值不會超過8，即過濾值8不能再改進。8就是最后的過濾值。

所以目標(biāo)函數(shù)的最優(yōu)值Z=8，最優(yōu)解X=（x2,x1,x3）=（0，1，1）。二、0-1規(guī)劃的隱枚舉法上述解題過程示于表4-6中。表中“√”表示滿足該約束條件，“—”表示不必檢查是否滿足約束條件。表4-6隱枚舉過程解（x2,x1,x3）約束條件Z值①

②

③

④（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）√

√

√

√√

√

√

√—

—

—

—√

√

√

√—

—

—

——

—

—

——

—

—

——

—

—

—0（初始濾值）5（新濾值）38（最后濾值）模塊四物流任務(wù)指派任務(wù)指派概述指派問題的匈牙利法0-1規(guī)劃問題應(yīng)用舉例單元一單元三單元二單元四知識點1．知道整數(shù)規(guī)劃問題的實踐意義。2．理解指派問題的含義及其數(shù)學(xué)模型的特征。3．掌握匈牙利法的算法步驟及特殊指派問題的處理方法。4．知道0-1規(guī)劃的實踐意義。5．掌握0-1規(guī)劃問題的模型構(gòu)建方法。6．知道隱枚舉法的求解過程。能力點、素質(zhì)點能力點：能用“指派問題”解決物流領(lǐng)域中人力、物力、財力等資源與工作任務(wù)、服務(wù)項目等的合理搭配問題，創(chuàng)造最大價值。能對物流固定設(shè)施選址問題建立“0-1規(guī)劃”模型。素質(zhì)點：擁有各司其職、各盡其責(zé)、勇于擔(dān)當(dāng)、團隊協(xié)作的職業(yè)精神。單元四應(yīng)用舉例一、指派問題在物流資源調(diào)配中的應(yīng)用二、0-1規(guī)劃在物流設(shè)施選址中的應(yīng)用一、指派問題在物流資源調(diào)配中的應(yīng)用

某物流企業(yè)根據(jù)地域的需求計劃在四個區(qū)域設(shè)立四個專業(yè)儲存?zhèn)}庫，考慮的商品有電器、服裝、食品、家具及計算機5個類別。通過市場調(diào)查，家具不宜儲存在丙處，計算機不宜儲存在丁處，不同商品投資到各點的年利潤（萬元）預(yù)測值見表4-7，該物流企業(yè)如何做出投資決策才能使年利潤最大。一、指派問題在物流資源調(diào)配中的應(yīng)用表4-7年利潤表

區(qū)域商品甲乙丙丁電器120300360400服裝80350420260食品150160380300家具90200180計算機220260270一、指派問題在物流資源調(diào)配中的應(yīng)用1．令c43=c54=0。2．令M=420，轉(zhuǎn)換成求最小值問題，得到效率表（機會損失表）。3．虛擬一個地點戊，轉(zhuǎn)換成平衡的指派問題。轉(zhuǎn)換后得到表4-8。

區(qū)域商品甲乙丙丁戊電器30012060200服裝3407001600食品270260401200家具3302204202400計算機2001601504200一、指派問題在物流資源調(diào)配中的應(yīng)用用匈牙利算法求得最優(yōu)解為：x14=x22=x33=x45=x51=1,其余xij=0，Z=400+350+380+0+220＝1350。最優(yōu)投資方案為地點甲投資計算機倉庫，地點乙投資服裝倉庫，地點丙投資食品倉庫，地點丁投資電器倉庫，年利潤總額預(yù)測值為1350萬元。二、0-1規(guī)劃在物流設(shè)施選址中的應(yīng)用某物流公司打算在沈陽或大連設(shè)立銷售分公司（也許在兩個城市都設(shè)立銷售分公司），以增加市場份額，決策層同時也計劃在每個新設(shè)分公司的城市最多建一個配送中心（當(dāng)然也可以不建）。每種選擇公司收益的凈現(xiàn)值、