《物流運(yùn)籌方法與工具》第3版 課件 模塊四單元三 0-1規(guī)劃問(wèn)題

物流運(yùn)籌方法與工具（第3版）目錄

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

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

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

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

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

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

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）是一個(gè)可行解，相應(yīng)的目標(biāo)函數(shù)值Z=0可作為初始過(guò)濾值。

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

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

故它不會(huì)是最優(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為新的過(guò)濾值。

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

≤3x1+5x3

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

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

√

√

√√

√

√

√—

—

—

—√

√

√

√—

—

—