《型整數(shù)規(guī)劃PPT精選文檔.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《型整數(shù)規(guī)劃PPT精選文檔.ppt（48頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、第四節(jié)第四節(jié)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃決策變量只能取決策變量只能取0或或1的整數(shù)規(guī)劃，叫做的整數(shù)規(guī)劃，叫做0-1整數(shù)規(guī)整數(shù)規(guī)劃。決策變量稱為劃。決策變量稱為0-1變量變量(二進(jìn)制變量、邏輯變量二進(jìn)制變量、邏輯變量)。0-1變量作為邏輯變量，常被用來(lái)表示系統(tǒng)是否處于某變量作為邏輯變量，常被用來(lái)表示系統(tǒng)是否處于某個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。一、什么是一、什么是0-1整數(shù)規(guī)劃整數(shù)規(guī)劃1第四節(jié)第四節(jié)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃1、投資場(chǎng)所的選定相互排斥的計(jì)劃、投資場(chǎng)所的選定相互排斥的計(jì)劃例：某公司擬在市東、西、南三區(qū)建立門市部，擬議中有例：某公司擬在市東、

2、西、南三區(qū)建立門市部，擬議中有7個(gè)個(gè)位置位置Ai(i=1,2,7)可供選擇。規(guī)定可供選擇。規(guī)定在東區(qū)，由在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。如選用如選用Ai點(diǎn)，設(shè)備投資估計(jì)為點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為元，每年可獲利潤(rùn)估計(jì)為ci元，元，但投資總額不能超過(guò)但投資總額不能超過(guò)B元。問(wèn)應(yīng)選擇哪個(gè)點(diǎn)可使年利潤(rùn)最大？元。問(wèn)應(yīng)選擇哪個(gè)點(diǎn)可使年利潤(rùn)最大？0-1規(guī)劃的實(shí)際問(wèn)題：規(guī)劃的實(shí)際問(wèn)題：建模如下：建模如下：st.22 2

3、相互排斥的約束條件相互排斥的約束條件 如果有m個(gè)互相排斥的約束條件（0）若不生產(chǎn)第j種產(chǎn)品（即xj=0）j=1，2，3則問(wèn)題的模型為且為整數(shù)，j=1，2，3j=1，2，39應(yīng)用舉例例A 東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用4名大學(xué)生（代號(hào)1、2、3、4）和2名研究生（代號(hào)5、6）值班答疑。已知每人從周一至周五每天最多可安排的值班時(shí)間及每人每h值班的報(bào)酬如下表學(xué)生代號(hào)報(bào)酬（元/h)每天最多可安排的值班時(shí)間周一 周二 周三 周四 周五12345610109.99.810.811.36 0 6 0 770 6 0 6 04 8 3 0 55 5 6 0 43 0 4 8 040 6 0 6 310該實(shí)驗(yàn)室開(kāi)放時(shí)

4、間是上午8點(diǎn)至晚上10點(diǎn)，開(kāi)放時(shí)間內(nèi)須有且僅需一名學(xué)生值班，規(guī)定大學(xué)生每周值班不少于8h，研究生每周不少于7h，每名學(xué)生每周值班不超過(guò)3次，每次值班不少于2h，每天安排值班的學(xué)生不超過(guò)3人且其中必須有一名研究生，試為該實(shí)驗(yàn)室安排一張人員的值班表，使總支付的報(bào)酬最少解：設(shè)xij為學(xué)生i在周j的值班時(shí)間，安排學(xué)生i在周j值班否則用aij代表學(xué)生i在周j最多可安排的值班時(shí)間，ci為學(xué)生i的每h的報(bào)酬，則其數(shù)學(xué)模型為11不超過(guò)可安排時(shí)間大學(xué)生每周值班不少于8h研究生每周值班不少于7h實(shí)驗(yàn)室每天開(kāi)放14h每名學(xué)生一周值班不超過(guò)3次每天值班不超過(guò)3人每天有一名研究生值班12學(xué)生代號(hào)一 二 三 四 五123

5、4566 6 77 4 68 8 55 63 2 24 2 6 3 最優(yōu)結(jié)果為總支付報(bào)酬每周727.5元值班方案為：13例B 清遠(yuǎn)市下設(shè)八個(gè)區(qū)，下表給出救護(hù)車從一個(gè)區(qū)至另一個(gè)區(qū)的車程時(shí)間（min）該市擬建救護(hù)中心，要求各區(qū)離救護(hù)中心的車程時(shí)間必須在8min之內(nèi)，是為該市提供決策建議：至少建多少個(gè)救護(hù)中心，建于何處？至從 2 3 4 5 6 7 8 12345678 9 11 13 14 8 159 10 12 13 11 17 1410 7 7 8 12 1011 8 7 10 9 12 8 14 1613 10 714 12 14解：先根據(jù)表整理出若救護(hù)中心建于該區(qū)時(shí)，救護(hù)車程8min內(nèi)所能

6、覆蓋的區(qū)，見(jiàn)于下表救護(hù)中心設(shè)于該區(qū)救護(hù)車程8min內(nèi)所能覆蓋的區(qū)123456781 2 72 23 4 5 643 4 5 653 4 5 663 4 5 6 81 726 815設(shè) 該區(qū)設(shè)救護(hù)中心否則列出數(shù)學(xué)模型如下求解的結(jié)果為x1=1，x6=1，即至少在1、6兩個(gè)區(qū)各設(shè)一救護(hù)中心16第四節(jié)第四節(jié)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃二、二、0-1整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法隱枚舉法：只檢查變量取值的組合的一部分的方法。隱枚舉法：只檢查變量取值的組合的一部分的方法。17(x1,x2,x3)Z值abcd過(guò)濾條件過(guò)濾條件(0,0,0)0Z0(0,0,1)5Z5(0,1,0)-2(0,1,1)3(1,0,0)3Z

7、8(1,0,1)(1,1,0)81(1,1,1)6按目標(biāo)函數(shù)中各變量系數(shù)的大小重新排列各變量按目標(biāo)函數(shù)中各變量系數(shù)的大小重新排列各變量最大化問(wèn)題：由小到大最大化問(wèn)題：由小到大最小化問(wèn)題：由大到小最小化問(wèn)題：由大到小18解法二：重新排列xj的順序(系數(shù)遞減)190-1型整數(shù)規(guī)劃計(jì)算表目標(biāo)函數(shù)z 3x12x25x3 5x33x12x2 最大值的上限是8，第二大的值是55x33x12x28 點(diǎn)(x3,x1,x2)約束條件滿足條件?是否z值(1,1,0)8 8隱枚舉法：共計(jì)算5次(均滿足約束條件)。（最優(yōu)解為1，0，1，最優(yōu)值8）可根據(jù)計(jì)算逐漸改變過(guò)濾條件(該例因最大值的點(diǎn)滿足其他四個(gè)約束，即找到最大

8、化問(wèn)題的最好的整數(shù)解。就不需驗(yàn)證計(jì)算第二大值的點(diǎn)是否滿足約束條件)20例：求解下面的0-1型整數(shù)規(guī)劃 21解：按遞增序列排列 因?yàn)閤i取0或1，最小下界點(diǎn)為(0,0,0)，z值為0；其次為(0,0,1)點(diǎn)，z值為2；(0,1,0)點(diǎn)，z值為3；220-1型整數(shù)規(guī)劃計(jì)算表最優(yōu)解為：(0,0,1)最優(yōu)值為：2點(diǎn)(x3,x2,x1)約束條件滿足條件?是否z值過(guò)濾條件(0,0,0)0(1,0,1)22最小值0對(duì)應(yīng)的點(diǎn)不滿足 約束，改變過(guò)濾條件，再驗(yàn)證計(jì)算次小值2對(duì)應(yīng)的點(diǎn)滿足 約束，即找到最小化問(wèn)題的最好的整數(shù)解。逐漸改變過(guò)濾條件23第五節(jié)指派問(wèn)題第五節(jié)指派問(wèn)題一、什么是指派問(wèn)題一、什么是指派問(wèn)題某單位

9、需完成任務(wù)某單位需完成任務(wù)n項(xiàng)任務(wù)，恰好有項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)個(gè)人可承擔(dān)這些任務(wù)，由于每人的專長(zhǎng)不同，各人完成不同任務(wù)這些任務(wù)，由于每人的專長(zhǎng)不同，各人完成不同任務(wù)效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成使完成n項(xiàng)任務(wù)的總效率最高。這類問(wèn)題稱為項(xiàng)任務(wù)的總效率最高。這類問(wèn)題稱為指派問(wèn)題指派問(wèn)題(分派問(wèn)題、分配問(wèn)題分派問(wèn)題、分配問(wèn)題)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任務(wù)任務(wù)cij表示第表示第i個(gè)人完成第個(gè)人完成第j項(xiàng)項(xiàng)任務(wù)的效率。任務(wù)的效率。24第五節(jié)指派問(wèn)題第五節(jié)指派問(wèn)題二、指派

10、問(wèn)題的數(shù)學(xué)模型二、指派問(wèn)題的數(shù)學(xué)模型=(Cij)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任務(wù)任務(wù)解：設(shè)解：設(shè)25例：某單位現(xiàn)在、例：某單位現(xiàn)在、四項(xiàng)工作需完成，、四項(xiàng)工作需完成，現(xiàn)在甲、乙、丙、丁四個(gè)現(xiàn)在甲、乙、丙、丁四個(gè)人均可完成這四項(xiàng)任務(wù)。人均可完成這四項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)所用的每人完成各項(xiàng)任務(wù)所用的時(shí)間如右表所示，問(wèn)應(yīng)指時(shí)間如右表所示，問(wèn)應(yīng)指派何人去完成何項(xiàng)任務(wù)，派何人去完成何項(xiàng)任務(wù)，使所需時(shí)間最少？使所需時(shí)間最少？甲甲215134乙乙1041415丙丙9141613丁丁78119ABCD任務(wù)任務(wù)人員人員滿足所有約束條件的可行解滿足所有約束條

11、件的可行解xij也可也可寫(xiě)成表格或矩陣形式，稱為寫(xiě)成表格或矩陣形式，稱為解矩陣解矩陣(xij)=就是上例的就是上例的一個(gè)可行解一個(gè)可行解矩陣矩陣第五節(jié)指派問(wèn)題第五節(jié)指派問(wèn)題(cij)=26第五節(jié)指派問(wèn)題第五節(jié)指派問(wèn)題指派問(wèn)題數(shù)學(xué)模型的性質(zhì)：指派問(wèn)題數(shù)學(xué)模型的性質(zhì)：若從指派問(wèn)題的系數(shù)的系數(shù)矩陣（若從指派問(wèn)題的系數(shù)的系數(shù)矩陣（cij）的一行（列）各元）的一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣（素中分別減去該行（列）的最小元素，得到新矩陣（bij），那），那么以（么以（bij）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。優(yōu)解

12、相同。獨(dú)立的獨(dú)立的0元素：元素：位于不同行不同列的位于不同行不同列的0元素稱為獨(dú)立的元素稱為獨(dú)立的0元素。元素。結(jié)論：結(jié)論：若能在系數(shù)矩陣若能在系數(shù)矩陣(bij)中找出中找出n個(gè)獨(dú)立的個(gè)獨(dú)立的0元素；則令解矩陣元素；則令解矩陣(xij)中對(duì)應(yīng)這中對(duì)應(yīng)這n個(gè)獨(dú)立的個(gè)獨(dú)立的0元素取值為元素取值為1，其它元素取值為，其它元素取值為0。將。將其代入目標(biāo)函數(shù)中得到其代入目標(biāo)函數(shù)中得到zk=0，它一定是最小。這就是以，它一定是最小。這就是以(bij)為為系數(shù)矩陣的指派問(wèn)題的最優(yōu)解。也就得到了問(wèn)題的最優(yōu)解。系數(shù)矩陣的指派問(wèn)題的最優(yōu)解。也就得到了問(wèn)題的最優(yōu)解。27第五節(jié)指派問(wèn)題第五節(jié)指派問(wèn)題三、指派問(wèn)題的解法

13、（匈牙利法）三、指派問(wèn)題的解法（匈牙利法）第一步第一步:使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列都出現(xiàn)元素。使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列都出現(xiàn)元素。（）從系數(shù)矩陣的每行元素減去該行的最小元素；（）從系數(shù)矩陣的每行元素減去該行的最小元素；（）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。（）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。2497min24min28經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；元素；只需找出只需找出n個(gè)獨(dú)立的個(gè)獨(dú)立的0元素，若能找出，就以這些獨(dú)立的元素，若能找出，就以這些獨(dú)立的0元素元素對(duì)應(yīng)解矩陣中的元素為

14、對(duì)應(yīng)解矩陣中的元素為1，其作為，其作為0，這就得到最優(yōu)解。找獨(dú)，這就得到最優(yōu)解。找獨(dú)立立0元素的步驟如下：元素的步驟如下：第二步：進(jìn)行試指派，以尋求最優(yōu)解。第二步：進(jìn)行試指派，以尋求最優(yōu)解。第五節(jié)指派問(wèn)題第五節(jié)指派問(wèn)題0（1）從只有一個(gè)從只有一個(gè)0元素的行開(kāi)始，給這個(gè)元素的行開(kāi)始，給這個(gè)0元素加圈，記作元素加圈，記作.然然后再劃去后再劃去所在列的其它所在列的其它0元素，記作元素，記作 。（2）給只有一個(gè)給只有一個(gè)0元素的列的元素的列的0元素加圈，記作元素加圈，記作；然后劃去；然后劃去所在行的所在行的0元素，記作元素，記作 。0（3）反復(fù)反復(fù)(1),(2)兩步，直到所有兩步，直到所有0元素都被圈

15、出和劃掉為止。元素都被圈出和劃掉為止。（4）若各行各列均有多于若各行各列均有多于2個(gè)的個(gè)的0元素未被圈出或劃掉，中任選元素未被圈出或劃掉，中任選其中任意一個(gè)其中任意一個(gè)0元素加圈。元素加圈。（5）若若元素的數(shù)目元素的數(shù)目m等于矩陣的階數(shù)等于矩陣的階數(shù)n，那么指派問(wèn)題的最優(yōu)，那么指派問(wèn)題的最優(yōu)解已得到，若解已得到，若m4）,x23又又M為任意大為任意大正數(shù)，則問(wèn)題正數(shù)，則問(wèn)題可表達(dá)為：可表達(dá)為：42第六節(jié)應(yīng)用舉例第六節(jié)應(yīng)用舉例4、用以表示固定費(fèi)用的函數(shù)、用以表示固定費(fèi)用的函數(shù)生產(chǎn)費(fèi)用函數(shù)：生產(chǎn)費(fèi)用函數(shù)：引入變量引入變量yj43復(fù)習(xí)題復(fù)習(xí)題一、判斷下列說(shuō)法是否正確一、判斷下列說(shuō)法是否正確1、整數(shù)規(guī)

16、劃的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)、整數(shù)規(guī)劃的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問(wèn)題（松弛問(wèn)題）的解的目標(biāo)函數(shù)值。劃問(wèn)題（松弛問(wèn)題）的解的目標(biāo)函數(shù)值。2、用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題時(shí)，、用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問(wèn)題目標(biāo)函數(shù)值的任何一個(gè)可行解的目標(biāo)函數(shù)值是該問(wèn)題目標(biāo)函數(shù)值的下界。下界。3、用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題，、用分枝定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)，通?？扇稳∑渲幸粋€(gè)作為當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí)，通常可任取其中一個(gè)作為下界值，再進(jìn)行比較、剪枝。下界值，再進(jìn)行比較、剪枝。4、用割平面法求

17、解整數(shù)規(guī)劃時(shí)，構(gòu)造的割平面有可、用割平面法求解整數(shù)規(guī)劃時(shí)，構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)解。能切去一些不屬于最優(yōu)解的整數(shù)解。44復(fù)習(xí)題復(fù)習(xí)題一、判斷下列說(shuō)法是否正確一、判斷下列說(shuō)法是否正確5、用割平面法求解純整數(shù)規(guī)劃時(shí)，要求包括松弛變、用割平面法求解純整數(shù)規(guī)劃時(shí)，要求包括松弛變量在內(nèi)的全部變量必須取整數(shù)值。量在內(nèi)的全部變量必須取整數(shù)值。6、指派問(wèn)題效率矩陣的每個(gè)元素都乘上同一常數(shù)、指派問(wèn)題效率矩陣的每個(gè)元素都乘上同一常數(shù)k，將不影響最優(yōu)指派方案。，將不影響最優(yōu)指派方案。7、指派問(wèn)題數(shù)學(xué)模型的形式同運(yùn)輸問(wèn)題十分相似，、指派問(wèn)題數(shù)學(xué)模型的形式同運(yùn)輸問(wèn)題十分相似，故也可以用表上作業(yè)法求解。故也可以用表上作業(yè)法求解。8、求解、求解0-1規(guī)劃的隱枚舉法是分枝定界法的特例。規(guī)劃的隱枚舉法是分枝定界法的特例。9、分枝定界法在需要分枝時(shí)必須滿足：一是分枝后、分枝定界法在需要分枝時(shí)必須滿足：一是分枝后的各子問(wèn)題必須容易求解；二是各子問(wèn)題解的集合的各子問(wèn)題必須容易求解；二是各子問(wèn)題解的集合必須覆蓋原問(wèn)題的解。必須覆蓋原問(wèn)題的解。45復(fù)習(xí)題復(fù)習(xí)題2、用匈牙利法求解最小化的指派問(wèn)題，效率矩陣如下：、用匈牙利法求解最小化的指派問(wèn)題，效率矩陣如下：46min7674647復(fù)習(xí)題復(fù)習(xí)題3、應(yīng)用建模：教材、應(yīng)用建模：教材128頁(yè)頁(yè)4.1648