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

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

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

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

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

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

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

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

maxZ=3x1-2x2+5x3二、0-1規(guī)劃的隱枚舉法s.t.解：根據目標函數中xi系數的遞增順序，重新排列變量的次序，得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）是一個可行解，相應的目標函數值Z=0可作為初始過濾值。

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

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

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

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

由目標函數maxZ=-2x2+3x1+5x3

≤3x1+5x3

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

所以目標函數的最優(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）√

√

√

√√

√

√

√—

—

—

—√

√

√

√—

—

—