整數(shù)規(guī)劃的求解整數(shù)規(guī)劃的定義一二課件

0-1整數(shù)規(guī)劃的求解項目三任務(wù)20-1整數(shù)規(guī)劃問題的求解0-1整數(shù)規(guī)劃的定義一二引入案例例3-4中郵速遞物流打算投資100萬元建設(shè)物流配送中心，經(jīng)考察有A1、A2、A3、A4四個可選擇的建設(shè)地點，每個地點的投資及三年后的獲利見下表，問應(yīng)該如何選擇使得三年后的總收益最大？可選擇建設(shè)地點投資三年后獲利A150200A260220A340180A430110請試著建立數(shù)學(xué)模型？解：設(shè)該問題的數(shù)學(xué)模型為：一、0-1整數(shù)規(guī)劃的定義如果整數(shù)規(guī)劃問題中的所有決策變量僅限于取0或者1兩個值，則稱此問題為0-1整數(shù)規(guī)劃，簡稱0-1規(guī)劃，其變量稱為0-1變量。如果整數(shù)規(guī)劃問題中的部分決策變量為0-1變量，則稱為0-1混合整數(shù)規(guī)劃0-1整數(shù)規(guī)劃的數(shù)學(xué)模型列舉法：把有限個解全部列舉出來，帶入約束條件和目標函數(shù)即可得出最優(yōu)解。隱枚舉法：列出所有可行解，按順序找出第一個可行解對應(yīng)的目標函數(shù)值作為過濾條件，后續(xù)可行解對應(yīng)的目標函數(shù)值必須優(yōu)于該過濾條件，否則舍棄，以此類推，選取新的過濾條件，判斷完所有的可行解即可得到最優(yōu)解。WINQSB軟件求解二、0-1整數(shù)規(guī)劃問題的求解例3-5分別用列舉法和隱枚舉法求解該0-1規(guī)劃問題1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111列舉法求解過程（x1,x2,x3)T各約束條件值滿足條件Z值(1)(2)(3)(4)是√否×(0,0,0)T0000√0(0,0,1)T

-1100√5(0,1,0)T

2414√-2(0,1,1)T15×(1,0,0)T

1110√3(1,0,1)T

0211√8(1,1,0)T3×(1,1,1)T

26×隱枚舉法求解過程課堂練習(xí)請分別用列舉法和隱枚舉法求解線性規(guī)劃列舉法求解過程（x1,x2,x3)T各約束條件值滿足條件Z值(1)(2)(3)是√否×(0,0,0)T000×(0,0,1)T

331√4(0,1,0)T

-511√3(0,1,1)T-24×(1,0,0)T

24×(1,0,1)T

5×(1,1,0)T-35×(1,1,1)T

08××√9（1，1，1）×√5（1，1，0）×6（1，0，1）2（1，0，0）×√7（0，1，1）3（0，1，0）z≥4√√√4（0，0，1）×√√0（0，0，0）過濾條件約束條件z(x1,x2,x3)隱枚舉法：