整數(shù)線性規(guī)劃整數(shù)約束整數(shù)約束是現(xiàn)實(shí)問題中一種常見的物理約束例如：產(chǎn)品生產(chǎn)或購(gòu)買問題中的產(chǎn)品數(shù)量選址問題中的地址選擇與否等為什么前面的家具生產(chǎn)案例中沒有添加整數(shù)約束？問題為什么前面的家具生產(chǎn)案例中沒有添加整數(shù)約束？對(duì)決策變量是否應(yīng)該加整數(shù)約束是由什么決定的？添加整數(shù)約束會(huì)使問題的求解分析變得更簡(jiǎn)單還是更復(fù)雜？整數(shù)線性規(guī)劃至少有一個(gè)決策變量是整數(shù)的線性規(guī)劃模型全整數(shù)線性規(guī)劃所有決策變量均為整數(shù)混合整數(shù)線性規(guī)劃既有整數(shù)決策變量，又有非整數(shù)決策變量0-1整數(shù)線性規(guī)劃所有決策變量均為0-1變量（也稱二進(jìn)制變量）案例：電力規(guī)劃某地區(qū)正在制定未來十年的電力規(guī)劃根據(jù)電力需求預(yù)測(cè)，發(fā)電裝機(jī)容量至少需要增加400萬千瓦才能滿足未來十年的需求候選技術(shù)方案可新建一座水電站，該站最多可安裝4臺(tái)30萬千瓦的機(jī)組設(shè)備還可新建一座火電站，該站最多可安裝6臺(tái)90萬千瓦的機(jī)組設(shè)備備選方案工程特點(diǎn)固定成本(百萬元)單機(jī)設(shè)備投資(百萬元)單機(jī)容量(萬千瓦)允許裝機(jī)臺(tái)數(shù)單機(jī)十年運(yùn)行成本（百萬元/臺(tái)）1新建水電站3680304202新建火電站2460906180全整數(shù)線性規(guī)劃：建模

LP松弛的圖解法LP松弛：去掉整數(shù)要求后得到的線性規(guī)劃求解步驟：確定頂點(diǎn)比較各頂點(diǎn)處的解LP松弛的計(jì)算機(jī)求解（驗(yàn)證）LP松弛的圖解法最優(yōu)解為R點(diǎn)(0,4.44)最優(yōu)成本：1089.6最優(yōu)解：(0,4)?(0,5)???全整數(shù)線性規(guī)劃的圖解法

最優(yōu)解為O點(diǎn)(2,4)全整數(shù)線性規(guī)劃的圖解法可行解集合為孤立的點(diǎn)集而非連續(xù)區(qū)域分析：LP松弛的最優(yōu)解的近似解不一定最優(yōu)LP松弛的最優(yōu)解是最優(yōu)整數(shù)解的上限（或下限）計(jì)算機(jī)求解OptimalObjectiveValue：1220Variable

Value

x1 2x2 40-1整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題的一種特殊情況決策變量的取值只能是0或10-1變量能很好地模擬實(shí)際問題中的二元決策問題工程規(guī)劃銀行、商鋪等選址分布式系統(tǒng)設(shè)計(jì)和產(chǎn)品設(shè)計(jì)……案例：工程規(guī)劃重新進(jìn)行調(diào)研和分析后得到了一些新的數(shù)據(jù)：水電站有2個(gè)候選地址，火電站有3個(gè)候選地址可以分別在這5個(gè)不同的地址建設(shè)不同規(guī)模的發(fā)電站還有一些其他的需求：總體發(fā)電機(jī)容量至少需要增加400萬千瓦前期工程投入的固定成本不能超過120百萬元任何發(fā)電站一旦建立，將按照其最大裝機(jī)數(shù)進(jìn)行裝配備選方案工程特點(diǎn)固定成本(百萬元)單機(jī)設(shè)備投資(百萬元)單機(jī)容量(萬千瓦)裝機(jī)臺(tái)數(shù)單機(jī)10年運(yùn)行成本（百萬元/臺(tái)）1水電站電站W(wǎng)23280303203火電站F124609061804火電站F222609051805火電站F32060904180數(shù)學(xué)建模

Objective

value：1278

VariableValue W1

1

W2

0

F1

0

F2

1

F3

0

0-1線性規(guī)劃的靈活性分析多重選擇約束互斥約束n選k約束條件約束和并行約束0-1線性規(guī)劃的靈活性分析多重選擇約束有多個(gè)（例如：3個(gè)）可擴(kuò)建的倉(cāng)庫(kù)W1：是否通過擴(kuò)建第1個(gè)倉(cāng)庫(kù)的方案W2：是否通過擴(kuò)建第2個(gè)倉(cāng)庫(kù)的方案W3：是否通過擴(kuò)建第3個(gè)倉(cāng)庫(kù)的方案互斥約束n選k約束條件約束和并行約束0-1線性規(guī)劃的靈活性分析多重選擇約束互斥約束W1+W2+W3=1；或 W1+W2+W3≤1 n選k約束條件約束和并行約束0-1線性規(guī)劃的靈活性分析多重選擇約束互斥約束n選k約束有n個(gè)可擴(kuò)建的倉(cāng)庫(kù)，要求擴(kuò)建k個(gè)W1+W2+…+Wn=k條件約束和并行約束0-1線性規(guī)劃的靈活性分析多重選擇約束互斥約束 n選k約束條件約束：W≤P只有工廠擴(kuò)建了，倉(cāng)庫(kù)才能擴(kuò)建并行約束：W=P如果擴(kuò)建了工廠，就必須擴(kuò)建倉(cāng)庫(kù)并且，如果擴(kuò)建了倉(cāng)庫(kù)，就必須擴(kuò)建工廠靈敏度分析實(shí)例：有4個(gè)方案和一個(gè)預(yù)算約束最優(yōu)解：170x1=1,x2=1,x3=1,x4=0如何進(jìn)行敏感度分析？（SolverTable）靈敏度分析：?jiǎn)巫兞考s束條件右端值x1x2x3x4目標(biāo)函數(shù)值981110170991110170100111017010110012001021001200靈敏度分析：雙變量目標(biāo)函數(shù)值96981001021043016016016019019032162162162192192341641641641941943616616616619619638168168168198198401701701702002004217217217220220244174174174204204461761761762062064817817817820820850180180180210210目標(biāo)函數(shù)系數(shù)(40)和約束條件右端值(100)

同時(shí)變化整數(shù)規(guī)劃求解：分支定界法基本思想：利用LP松弛解的特點(diǎn)進(jìn)行迭代搜索和提前終止R（0,4.44）縱坐標(biāo)非整數(shù)原問題S（1.33,4）橫坐標(biāo)非整數(shù)子問題1U（0,5）z*=1260子問題2x2≤4x2≥5

整數(shù)規(guī)劃求解：分支定界法基本思想：利用LP松弛解的特點(diǎn)進(jìn)行迭代搜索和提前終止R（0,4.44）縱坐標(biāo)非整數(shù)原問題S（1.33,4）橫坐標(biāo)非整數(shù)子問題1U（0,5）z*=1260子問題2x2≤4x2≥5T（2,