第5章整數(shù)規(guī)劃課件

第五章

整數(shù)規(guī)劃1第五章

整數(shù)規(guī)劃1§1整數(shù)規(guī)劃的數(shù)學(xué)模型一、整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)規(guī)劃(IntegerProgramming簡記IP)要求一部分或全部決策變量必須取整數(shù)的規(guī)劃問題2.松馳問題(SlackProblem)不考慮整數(shù)約束，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題(也稱伴隨規(guī)劃)3.整數(shù)線性規(guī)劃(ILP)若松馳問題是一個線性規(guī)劃問題2§1整數(shù)規(guī)劃的數(shù)學(xué)模型一、整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)規(guī)劃(In§1整數(shù)規(guī)劃的數(shù)學(xué)模型一、整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式為：中部分或全部取整數(shù)3§1整數(shù)規(guī)劃的數(shù)學(xué)模型一、整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)線性規(guī)劃數(shù)§1整數(shù)規(guī)劃的數(shù)學(xué)模型一、整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)線性規(guī)劃分為：純整數(shù)LP——PureIntegerLinearProgramming混合整數(shù)LP——MixedIntegerLinearProgramming0-1型整數(shù)LP——Zero-OneIntegerLinearProgramming4§1整數(shù)規(guī)劃的數(shù)學(xué)模型一、整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)線性規(guī)劃分§1整數(shù)規(guī)劃的數(shù)學(xué)模型二、整數(shù)規(guī)劃舉例例1：某廠生產(chǎn)A1和A2兩種產(chǎn)品，需要經(jīng)過B1，B2，B3三道工序加工，單件工時和利潤以及各工序每周工時限額見下表，問工廠應(yīng)如何安排生產(chǎn)，才能使總利潤最大？B1B2B3利潤A10.30.20.325A20.70.10.540工時限制2501001505§1整數(shù)規(guī)劃的數(shù)學(xué)模型二、整數(shù)規(guī)劃舉例例1：某廠生產(chǎn)A1和§1整數(shù)規(guī)劃的數(shù)學(xué)模型二、整數(shù)規(guī)劃舉例解：設(shè)工廠每周生產(chǎn)A1產(chǎn)品x1件，A2產(chǎn)品x2件。則該問題的數(shù)學(xué)模型為：且取整數(shù)值6§1整數(shù)規(guī)劃的數(shù)學(xué)模型二、整數(shù)規(guī)劃舉例解：設(shè)工廠每周生產(chǎn)A§1整數(shù)規(guī)劃的數(shù)學(xué)模型二、整數(shù)規(guī)劃舉例例2：見書P130例17§1整數(shù)規(guī)劃的數(shù)學(xué)模型二、整數(shù)規(guī)劃舉例例2：見書P130§1整數(shù)規(guī)劃的數(shù)學(xué)模型三、整數(shù)規(guī)劃解的特點1.整數(shù)規(guī)劃問題的可行解集合是它的松馳問題可行解集合的一個。2.整數(shù)規(guī)劃問題最優(yōu)解的目標(biāo)函數(shù)值松馳問題最優(yōu)解的目標(biāo)函數(shù)值。3.對松馳問題最優(yōu)解中非零分量取整，所得到的解不一定是整數(shù)規(guī)劃問題的最優(yōu)解，甚至也不一定是整數(shù)規(guī)劃問題的可行解。子集不優(yōu)于8§1整數(shù)規(guī)劃的數(shù)學(xué)模型三、整數(shù)規(guī)劃解的特點1.整數(shù)規(guī)劃問題例1:某廠擬用集裝箱托運甲乙兩種貨物,每箱的體積、重量、可獲利潤以及托運所受限制見表.問每集裝箱中兩種貨物各裝多少箱,可使所獲利潤最大?貨物/箱體積/米3重量/百斤利潤/百元甲5220乙4510托運限制/集裝箱24139例1:某廠擬用集裝箱托運甲乙兩種貨物,每箱的體積、重量、可獲解：設(shè)

分別為甲、乙兩種貨物的托運箱數(shù).則這是一個純整數(shù)規(guī)劃問題。其數(shù)學(xué)模型為:（1）10解：設(shè)分別為甲、乙兩種貨物的托運箱數(shù).則這是一個若暫且不考慮

取整數(shù)這一條件。則(1)就變?yōu)橄铝芯€性規(guī)劃:（2）將式(2)稱為(1)的松馳問題，解(2)得到最優(yōu)解:（3）但它不滿足(1)的整數(shù)要求。因此它不是(1)的最優(yōu)解。11若暫且不考慮取整數(shù)這一條件。則(1)就變?yōu)橄铝芯€若取X1=(5,0)T，它不滿足(1)中的約束條件1。

若取X2=(4,0)T，X2是(1)的可行解,但它卻不是(1)的最優(yōu)解。

因為當(dāng)X2=(4,0)T

時,Z=80,當(dāng)X3=(4,1)T時,Z′=90>Z,即松馳問題的最優(yōu)解通過“舍零取整”得到的X1,X2都不是(1)的最優(yōu)解。因此通過松馳問題最優(yōu)解的“舍零取整”的辦法,一般得不到原整數(shù)規(guī)劃問題的最優(yōu)解。12若取X1=(5,0)T，它不滿足(1)中的約束條件1。k0

={(0,0),(0,1),(0,2),(1,0),(1,l),(1,2),(2,0),(2,1),(3,0),(3,1),(4,0),(4,l)}將C點“舍零取整”后得到的X1=(5,0)T不在K0中,而X2=(4,0)T在K0中,但不是(1)的最優(yōu)解,最優(yōu)解在B點。松馳問題(2)的可行域K如圖,(4.8,0)(4,0)則原整數(shù)規(guī)劃(1)的可行域K0應(yīng)是K中有限個格點(整數(shù)點）的集合。圖中“*”為整數(shù)點(格點)。例2：見書P132例413k0={(0,0),(0,1),(0,2),(1,0),(由于整數(shù)規(guī)劃問題(1)可行解的個數(shù)較少，故可用“窮舉法”來求解,即將

K0中所有整數(shù)點的目標(biāo)函數(shù)值都計算出來,然后逐一比較找出最優(yōu)解。取=0,1,2,3,4其組合最多為15個(其中有不可行的點)。=0,1,2但對大型問題，這種組合數(shù)的個數(shù)可能大得驚人!如在指派問題中，有n項任務(wù)指派n個人去完成，不同的指派方案共有n!種。當(dāng)n=20時，這個數(shù)超過2×1018。如果用窮舉法每一個方案都計算一遍，就是用每秒億次的計算機，也要幾十年。14由于整數(shù)規(guī)劃問題(1)可行解的個數(shù)較少，故可用“窮舉法”來求顯然“窮舉法”并不是一種普遍有效的方法。因此研究求解整數(shù)規(guī)劃的一般方法是有實際意義的。自20世紀(jì)60年代以來，已發(fā)展了一些常用的解整數(shù)規(guī)劃的算法，如各種類型的割平面法、分枝定界法、解0-1規(guī)劃的隱枚舉法、分解方法、群論方法、動態(tài)規(guī)劃方法等等。近十年來有人發(fā)展了一些近似算法及用計算機模擬法，也取得了較好的效果。

15顯然“窮舉法”并不是一種普遍有效的方法。因此研究求解整數(shù)規(guī)劃§2解純整數(shù)規(guī)劃的割平面法割平面法在1958年由R.E.Gomory首先提出。一、割平面法的思想若松馳問題的最優(yōu)解不滿足整數(shù)約束，就設(shè)法在問題上增加一個約束，把包含這個非整數(shù)解的一部分可行域從原來的可行域中割掉，但不割掉任何一個整數(shù)可行解，這個新增加的約束條件就稱為割平面約束或Gomory約束。16§2解純整數(shù)規(guī)劃的割平面法割平面法在1958年由R.E.且為整數(shù)p(3/4,7/4)****q(1,1)17且為整數(shù)p(3/4,7/4)****q(1,1)17二、割平面法步驟1.解松馳問題的最優(yōu)解；2.若X*的所有分量均為整數(shù)，則滿足整數(shù)約束，X*即為整數(shù)規(guī)劃的最優(yōu)解。若存在X*的某個分量為小數(shù)，則選取分?jǐn)?shù)部分最大的分量，構(gòu)造新的約束條件；3.將新的約束條件加入松馳問題中，形成一個新的線性規(guī)劃，對這個新的線性規(guī)劃求解；4.若新的解滿足整數(shù)約束，則此解為整數(shù)規(guī)劃的最優(yōu)解，否則重復(fù)第2，3步，直到獲得最優(yōu)解為止。18二、割平面法步驟1.解松馳問題的最優(yōu)解；18三、新約束條件的構(gòu)造在松馳問題的最優(yōu)單純形表中，m個約束方程可表示為：其中Q為m個基變量的下標(biāo)集合，K為n-m個非基變量的下標(biāo)集合。19三、新約束條件的構(gòu)造在松馳問題的最優(yōu)單純形表中，m個約束方程三、新約束條件的構(gòu)造若不是整數(shù)，其對應(yīng)的約束方程：分解和成兩部分，一部分是不超過該數(shù)的最大整數(shù)，另一部分是余下的正小數(shù)。即：20三、新約束條件的構(gòu)造若不三、新約束條件的構(gòu)造且為整數(shù)且為整數(shù)構(gòu)造新的約束條件為：割平面約束21三、新約束條件的構(gòu)造且為整數(shù)且為整數(shù)構(gòu)造新的約束條件為：割平四、新增約束條件的性質(zhì)性質(zhì)1：原松馳問題的非整數(shù)最優(yōu)解不滿足新增約束條件。性質(zhì)2：原松馳問題的整數(shù)可行解均滿足新增的約束條件，也就是說，整數(shù)可行解始終保留在每次形成的線性規(guī)劃的可行域中。22四、新增約束條件的性質(zhì)性質(zhì)1：原松馳問題的非整數(shù)最優(yōu)解不滿足下面說明新增約束：能夠“割掉”松馳問題中的非整數(shù)可行解。證明：設(shè)X*為松馳問題的最優(yōu)解，將其代入新增約束有：，（因非基變量取值為0）這與矛盾，即X*不滿足新增約束。注：經(jīng)驗表明若從最優(yōu)單純形表上選擇具有最大小數(shù)部分的非整數(shù)分量所在行構(gòu)造割平面約束，往往可以提高“切割”效果，減少“切割”次數(shù)。23下面說明新增約束：證明：設(shè)X*為松馳問題的最優(yōu)解，將其代入新例1：用割平面法求解整數(shù)規(guī)劃且為整數(shù)解：引入松馳變量x3，x4，將問題化為標(biāo)準(zhǔn)形式，用單純形法解其松馳問題，得最優(yōu)單純形表如下：24例1：用割平面法求解整數(shù)規(guī)劃且為整數(shù)解：引入松馳變量x3，xcj1100CBXBbx1x2x3x411x2x17/43/401103/4-1/41/41/400-1/2-1/2割平面約束為：引入松馳變量x5，得割平面方程：x1,x2的最大分量均為3/4，不妨選取x2，得：25cj1100CBXBbx1x2x3x41x27/4013/4cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/400100-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3000-1/3-2/326cj11000CBXBbx1x2x3x4x51x27/401例2：用割平面法求解整數(shù)規(guī)劃且為整數(shù)解：引入松馳變量x3，x4，x5，將問題化為標(biāo)準(zhǔn)形式，用單純形法解其松馳問題，得最優(yōu)單純形表如下：27例2：用割平面法求解整數(shù)規(guī)劃且為整數(shù)解：引入松馳變量x3，xcj3-1000CBXBbx1x2x3x4x53-10x1x2x413/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7割平面約束為：引入松馳變量x6，得割平面方程：28cj3-1000CBXBbx1x2x3x4x53x113/7cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/7029cj3-10000CBXBbx1x2x3x4x5X63x11cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x4x510-53100001000-1/2-21/20010000113/211-7/200-5/70-3/7030cj3-10000CBXBbx1x2x3x4x5X63x11cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x3x515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4割平面約束為：引入松馳變量x7，得割平面方程：31cj3-10000CBXBbx1x2x3x4x5X63x11cj3-100000CBXBbx1x2x3x4x5x6x73-1000x1x2x3x5x715/45/27/4-3/41000001000001000-1/4-1/21/4-1/4000101-5/4-11/2-3/4-1/400001000-1/40-17/4032cj3-100000CBXBbx1x2x3x4x5x6x73cj3-100000CBXBbx1x2x3x4x5x6x73-1000x1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-400000-4-1上表中給出的最優(yōu)解x=(1,2,4,3,1,0,0)已滿足整數(shù)約束，因而，原整數(shù)規(guī)劃問題的最優(yōu)解為：x1=1,x2=2,maxz=133cj3-100000CBXBbx1x2x3x4x5x6x73*****34*****34§3分枝定界法

在20世紀(jì)60年代初LandDoig

和

Dakin

等人提出了分枝定界法。由于該方法靈活且便于用計算機求解，所以目前已成為解整數(shù)規(guī)劃的重要方法之一。分枝定界法既可用來解純整數(shù)規(guī)劃，也可用來解混合整數(shù)規(guī)劃。

分枝定界法的主要思路是首先求解整數(shù)規(guī)劃的伴隨規(guī)劃,如果求得的最優(yōu)解不符合整數(shù)條件,則：

增加新約束——縮小可行域;

將原整數(shù)規(guī)劃問題分枝——分為兩個子規(guī)劃,再解子規(guī)劃的伴隨規(guī)劃；

通過求解一系列子規(guī)劃的伴隨規(guī)劃及不斷地定界。最后得到原整數(shù)規(guī)劃問題的整數(shù)最優(yōu)解。

35§3分枝定界法在20世紀(jì)60年代初LandDoig例1：某公司計劃建筑兩種類型的宿舍。甲種每幢占地0.25×103m2,乙種每幢地0.4×103m2。該公司擁有土地3×103m2.計劃甲種宿舍不超過8幢，乙種宿舍不超過4幢。甲種宿舍每幢利潤為10萬元，乙種宿舍利潤為每幢20萬元。問該公司應(yīng)計劃甲、乙兩種類型宿舍各建多少幢時，能使公司獲利最大?36例1：某公司計劃建筑兩種類型的宿舍。甲種每幢占地0.25×1解：設(shè)計劃甲種宿舍建

幢,乙種宿舍建

幢,則本題數(shù)學(xué)模型為:這是一個純整數(shù)規(guī)劃問題,稱為問題

。將(1)中約束條件的系數(shù)全化為整數(shù),改為：（1）37解：設(shè)計劃甲種宿舍建幢,乙種宿舍建幢,則本題數(shù)學(xué)這然后去掉整數(shù)條件,得到問題

的伴隨規(guī)劃(2),稱之為問題（2）38然后去掉整數(shù)條件,得到問題的伴隨規(guī)劃(2),稱之為（84(5.6,4)求解問題

,得到最優(yōu)解及最優(yōu)值：3984(5.6,4)求解問題,得到最優(yōu)解及最優(yōu)值：1.計算原問題

目標(biāo)函數(shù)值的初始上界因為問題

的最優(yōu)解不滿足整數(shù)條件,因此

不是的最優(yōu)解,又因為

的可行域

問題

的可行域

,故問題

的最優(yōu)值不會超過問題

的最優(yōu)值。即有：因此可令

作為

的初始上界

。即：一般說來,若問題

無可行解,則問題

也無可行解,停止計算。若問題

的最優(yōu)解

滿足問題

的整數(shù)條件,則

也是問題

的最優(yōu)解,停止計算。401.計算原問題目標(biāo)函數(shù)值的初始上界因為問題2.計算原問題

目標(biāo)函數(shù)值的初始下界若能從問題

的約束條件中觀察到一個整數(shù)可行解，則可將其目標(biāo)函數(shù)值作為問題

目標(biāo)函數(shù)值的初始下界，否則可令初始下界Z=-∞。給定下界的目的，是希望在求解過程中尋找比當(dāng)前

更好的原問題的目標(biāo)函數(shù)值。對于本例,很容易得到一個明顯的可行解X=(0,0)T,Z=0。問題

的最優(yōu)目標(biāo)函數(shù)值決不會比它小,故可令

=0.412.計算原問題目標(biāo)函數(shù)值的初始下界若能從問題3.增加約束條件將原問題分枝當(dāng)問題

的最優(yōu)解

不滿足整數(shù)條件時,在

中任選一個不符合整數(shù)條件的變量。如本例選

，顯然問題

的整數(shù)最優(yōu)解只能是

或

,而絕不會在5與6之間。因此當(dāng)將可行域

切去

部分時,并沒有切去

的整數(shù)可行解?？梢杂梅謩e增加約束條件

及

來達(dá)到在

切去

部分的目的。

切去

后就分為

及

兩部分,即問題

分為問題

及問題

兩枝子規(guī)劃。

423.增加約束條件將原問題分枝當(dāng)問題的最優(yōu)解不滿問題問題則問題

的可行域為

見圖。43問題問題則問題的可行域為見圖。84(5.6,4)K1K256解為:解為:(5,4)(6,3.75)4484(5.6,4)K1K256解為:解為:(5,4)(6問題

的解

是整數(shù)最優(yōu)解,它當(dāng)然也是問題

的整數(shù)可行解,故

的整數(shù)最優(yōu)解同時問題

也被查清,成為“樹葉”。因為

,不滿足整數(shù)條件,故問題

分別增加約束條件：及。建立相應(yīng)的伴隨規(guī)劃——問題

與45問題的解是整數(shù)最優(yōu)解,它當(dāng)然也是問題問題問題它們的可行域分別為因為

，問題

無可行解，此問題已是“樹葉”，已被查清。46問題問題它們的可行域分別為因為，問題無84B1K263K3求解問題

,得到最優(yōu)解(7.2,3)4784B1K263K3求解問題,得到最優(yōu)解(7.2,3因為

,不滿足整數(shù)條件,故問題

分別增加約束條件：及。建立相應(yīng)的伴隨規(guī)劃——問題

與問題問題48因為,不滿足整數(shù)條件,故問題分84B1B263K37K5K6解為:(7,3)(8,2.5)4984B1B263K37K5K6解為:(7,3)(8,2.5當(dāng)解完一對分枝后,得到

因此所有分枝均已查明。故已得到問題

的最優(yōu)解:或故該公司應(yīng)建甲種宿舍7幢、乙種宿舍3幢;或甲種5幢、乙種4幢時,獲利最大，獲利為130萬元。50當(dāng)解完一對分枝后,得到問題問題問題問題問題問題問題不可行51問題問題問題問題問題問題問題不可行51分枝定界法步驟:第1步:將原整數(shù)線性規(guī)劃問題稱為問題

。去掉問題的整數(shù)條件,得到伴隨規(guī)劃問題

。第2步:求解問題

,有以下幾種可能:(l)

沒有可行解,則

也沒有可行解,停止計算。(2)

得到

的最優(yōu)解,且滿足問題

的整數(shù)條件,則

的最優(yōu)解也是

的最優(yōu)解,停止計算。(3)得到不滿足問題

的整數(shù)條件的

的最優(yōu)解,記它的目標(biāo)函數(shù)值為

,這時需要對問題

(從而對問題

)進行分枝，轉(zhuǎn)下一步。52分枝定界法步驟:第1步:將原整數(shù)線性規(guī)劃問題稱為問題。去第3步:確定初始上下界

與

以

作為上界

，觀察出問題

的一個整數(shù)可行解,將其目標(biāo)函數(shù)值記為下界

。若觀察不到,則可記

=-∞，轉(zhuǎn)下一步。 第4步:將問題

分枝在

的最優(yōu)解

中,任選一個不符合整數(shù)條件的變量

,其值為

,以

表示小于

的最大整數(shù)。構(gòu)造兩個約束條件：53第3步:確定初始上下界與以作為上界，觀將這兩個約束條件分別加到問題

的約束條件集中,得到

的兩個分枝:問題

與

。對每個分枝問題求解,得到以下幾種可能:(1)

分枝無可行解——該分枝是“樹葉”。(2)求得該分枝的最優(yōu)解,且滿足

的整數(shù)條件。將該最優(yōu)解的目標(biāo)函數(shù)值作為新的下界

,該分枝也是“樹葉”。(3)求得該分枝的最優(yōu)解,且不滿足

的整數(shù)條件,但其目標(biāo)函數(shù)值不大于當(dāng)前下界

,則該分枝是“枯枝”需要剪枝。54將這兩個約束條件分別加到問題的約束條件集中,得到對每(4)求得不滿足

整數(shù)條件的該分枝的最優(yōu)解,且其目標(biāo)函數(shù)值大于當(dāng)前下界

,則該分枝需要繼續(xù)進行分枝。若得到的是前三種情形之一,表明該分枝情況已探明,不需要繼續(xù)分枝。若求解一對分枝的結(jié)果表明這一對分枝都需要繼續(xù)分枝，則可先對目標(biāo)函數(shù)值大的那個分枝進行計算，且沿著該分枝一直繼續(xù)進行下去，直到全部探明情況為止。再返過來求解目標(biāo)函數(shù)值較小的那個分枝。55(4)求得不滿足整數(shù)條件的該分枝的最優(yōu)解,且其目標(biāo)函第5步:修改上、下界

修改下界

：每求出一次符合整數(shù)條件的可行解時,都要考慮修改下界

,選擇迄今為止最好的整數(shù)可行解相應(yīng)的目標(biāo)函數(shù)值作下界

。(2)修改上界

：每求解完一對分枝,都要考慮修改上界

上界的值應(yīng)是迄今為止所有未被分枝的問題的目標(biāo)函數(shù)值中最大的一個。在每解完一對分枝，修改完上、下界

和后,若已有

此時所有分枝均已查明,即得到了問題

的最優(yōu)值求解結(jié)束。56第5步:修改上、下界修改下界：每求出一次符合整數(shù)條件若仍有

,則說明仍有分枝沒查明，需要繼續(xù)分枝,將需要進行分枝的問題稱為問題B0，回到第4步。57若仍有,則說明仍有分枝沒查明，需要繼續(xù)分枝,將P138例6A(3/2,10/3)z=29/6B(2,23/9)z=41/9C(1,7/3)z=10/358P138例6A(3/2,10/3)z=29/6B(2,23P138例6C(1,7/3)z=10/3D(33/14,2)z=61/14E(3,1)z=4F(2,2)z=459P138例6C(1,7/3)z=10/3D(33/14,2§40-1型整數(shù)規(guī)劃一、0-1型整數(shù)規(guī)劃的概念0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，它的變量xj僅取值0或1，這時xj稱為0-1變量（或二進制變量，邏輯變量）。xj僅取0或1，可表示為：它和一般的整數(shù)規(guī)劃的約束條件在形式上是一致的。為整數(shù)P130例2在實際問題中，如果引入0-1變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論。60§40-1型整數(shù)規(guī)劃一、0-1型整數(shù)規(guī)劃的概念0-1型整二、引入0-1變量的實際問題1.投資場所的選定——相互排斥的計劃例1:某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置A1,…，A7可供選擇。規(guī)定:在東區(qū)：由A1,A2,A3三個點中至多選兩個；在西區(qū)：由A4,A5兩個點中至少選一個；在南區(qū)：由A6,A7兩個點中至少選一個。如選用Ai點，設(shè)施投資估計為bi元，每平方米可獲利潤估計為Ci元，但投資總額不能超過B元，問應(yīng)選擇哪幾個點可使年利潤最大？61二、引入0-1變量的實際問題1.投資場所的選定——相互排斥的解：引入0-1變量，令：點被選用點不被選用于是問題的數(shù)學(xué)模型為：(i=1,2,…,7)62解：引入0-1變量，令：點被選用點不被選用于是問題的數(shù)學(xué)模型二、引入0-1變量的實際問題2.相互排斥的約束條件或為了統(tǒng)一在一個問題中，引入0-1變量y，則上述約束條件可改寫為：其中M是充分大的數(shù)。P142例763二、引入0-1變量的實際問題2.相互排斥的約束條件或為了統(tǒng)一二、引入0-1變量的實際問題3.固定費用問題P143例84.工件排序問題P144例9(略)64二、引入0-1變量的實際問題3.固定費用問題P143例84三、0-1型整數(shù)規(guī)劃的過濾隱枚舉法設(shè)0-1型整數(shù)規(guī)劃：解的步驟：(1)列出n個分量的2n種組合，算出相應(yīng)的目標(biāo)函數(shù)值。(2)X*為任一組合，判斷X*是否滿足所有約束條件，若滿足則轉(zhuǎn)下一步，否則舍棄該組合。65三、0-1型整數(shù)規(guī)劃的過濾隱枚舉法設(shè)0-1型整數(shù)規(guī)劃：解的步三、0-1型整數(shù)規(guī)劃的過濾隱枚舉法解的步驟：(3)設(shè)Z*=CX*，將Z≥Z*作為過濾條件。(4)對其它組合，若不滿足過濾條件，則舍棄；對滿足過濾條件的，看其是否滿足所有約束，不滿足舍棄。設(shè)滿足所有約束的組合為X',將Z'=CX'作為新的過濾條件。(5)檢查所有可能的組合，最終可得最優(yōu)解。66三、0-1型整數(shù)規(guī)劃的過濾隱枚舉法解的步驟：(3)設(shè)Z*=C例2：求解0-1型整數(shù)規(guī)劃(a)(b)(c)(d)注：為了進一步減少運算量，對于最大化（最小化）問題，常按目標(biāo)函數(shù)中各變量系數(shù)從小到大（從大到?。┑捻樞蛑匦屡帕懈髯兞浚允棺顑?yōu)解可能較早出現(xiàn)。67例2：求解0-1型整數(shù)規(guī)劃(a)注：為了進一步減少運算量，對例3：求解0-1型整數(shù)規(guī)劃(a)(b)(c)68例3：求解0-1型整數(shù)規(guī)劃(a)68四、0-1型整數(shù)規(guī)劃的分枝定界解法解的步驟：(1)目標(biāo)函數(shù)極小化，約束條件為≥。(2)目標(biāo)函數(shù)系數(shù)非負(fù)化。(3)目標(biāo)函數(shù)中，變量按系數(shù)從小到大排列，約束條件中各變量的排列順序也做相應(yīng)變化。(4)令所有變量為零，檢查約束條件是否滿足，若滿足此解即為最優(yōu)解，否則轉(zhuǎn)下一步。69四、0-1型整數(shù)規(guī)劃的分枝定界解法解的步驟：(1)目標(biāo)函數(shù)極四、0-1型整數(shù)規(guī)劃的分枝定界解法解的步驟：(5)按在目標(biāo)函數(shù)中排列順序（從左到右）依次令各變量分別取“0”或“1”，將問題分為兩個子問題，各自檢查是否滿足約束條件，若滿足，則保留所有可行解中目標(biāo)函數(shù)值最小的分枝進行定界，將可行解中目標(biāo)函數(shù)值大的分枝剪去。若不滿足，則對目標(biāo)函數(shù)值較小的分枝優(yōu)先進行下一步分枝。直到所有分枝均檢查清楚為止。這時保留下來的分枝即為最優(yōu)解。70四、0-1型整數(shù)規(guī)劃的分枝定界解法解的步驟：(5)按在目標(biāo)函例4：用分枝定界法求解0-1型整數(shù)規(guī)劃例5：用分枝定界法求解0-1型整數(shù)規(guī)劃71例4：用分枝定界法求解0-1型整數(shù)規(guī)劃例5：用分枝定界法求解注：當(dāng)發(fā)生下列三種情況之一時，該分枝不再繼續(xù)往下分，或保留或剪枝(1)該分枝為可行解，這時應(yīng)保留所有可行解中目標(biāo)函數(shù)值最小的分枝，將可行解中目標(biāo)函數(shù)值大的分枝剪去。(2)不管是否為可行解，分枝目標(biāo)函數(shù)值已超過保留下來的可行解的目標(biāo)函數(shù)值的分枝剪去。(3)當(dāng)該分枝中某些變量的值已確定的情況下，其余變量不管取什么值都無法滿足一個或幾個約束時，即該分枝無可行解，實行剪枝。72注：當(dāng)發(fā)生下列三種情況之一時，該分枝不再繼續(xù)往下分，或保留或§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型在現(xiàn)實生活中，有各種性質(zhì)的指派問題，如，有若干項工作需要分配給若干人來完成；有若干項合同需要選擇若干個投票者來承包；有若干班級需要安排各教室上課等。指派問題的標(biāo)準(zhǔn)形式是：有n個和n件事，已知第i做第j件事的費用為cij(i,j=1,2,…,n)，要求確定人和事之間的一一指派方案，使完成這n件事的總費用最少。73§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型在現(xiàn)實生活§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型一般稱矩陣為指派問題的效率矩陣（coefficientmatrix）矩陣C中，第i行中各元素表示第i個人做各事的費用；第j列各元素表示第j事由各人做的費用。74§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型一般稱矩陣§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型令：i,j=1,2,…,n指派問題的數(shù)學(xué)模型為：(a)(b)(c)(d)每件事有且只有一個人去做每個人做且只做一件事75§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型令：i,j§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型對于問題的每一個可行解，可用解矩陣來表示：矩陣每列元素中有且只有一個

，以滿足約束條件

。矩陣每行元素中有且只有一個

，以滿足約束條件

。指派問題有

可行解。11(b)(c)n!76§5指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型對于問題的§5指派問題二、指派問題的匈牙利解法指派問題是0-1規(guī)劃的特例，也是運輸問題的特例，因此可用整數(shù)規(guī)劃或運輸問題的解法求解，然而這就如同用單純形法解運輸問題一樣是不夠合算的，利用指派問題的特點可有更簡便的解法——匈牙利解法。匈牙利解法的基本原理就是效率矩陣的任一行(或列)減去(或加上)任一常數(shù)對原指派問題的最優(yōu)解不會發(fā)生影響。77§5指派問題二、指派問題的匈牙利解法指派問題是0-1規(guī)劃§5指派問題三、匈牙利解法的一般步驟(1)變換系數(shù)矩陣先對各行元素分別減去本行中的最小元素；再對各列元素分別減去本列中的最小元素；這樣，系數(shù)矩陣中每行及每列中至少有一個零元素，同時不出現(xiàn)負(fù)元素。(2)在變換后的系數(shù)矩陣中確定獨立零元素若獨立零元素有n個，則已得出最優(yōu)解；若獨立零元素少于n個，則轉(zhuǎn)下一步。(3)作能覆蓋所有零元素的最少直接數(shù)目的直線集合78§5指派問題三、匈牙利解法的一般步驟(1)變換系數(shù)矩陣(§5指派問題三、匈牙利解法的一般步驟(1)變換系數(shù)矩陣先對各行元素分別減去本行中的最小元素；再對各列元素分別減去本列中的最小元素；這樣，系數(shù)矩陣中每行及每列中至少