管理運(yùn)籌學(xué)整數(shù)規(guī)劃ppt課件

1、第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃 1 整數(shù)規(guī)劃的圖解法 2整數(shù)規(guī)劃的計(jì)算機(jī)求解 3整數(shù)規(guī)劃的運(yùn)用 4整數(shù)規(guī)劃的分枝定界法1 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法例例1. 某工廠在方案期內(nèi)要安排甲、乙兩種儀器設(shè)備的消費(fèi)，知消費(fèi)儀器設(shè)備某工廠在方案期內(nèi)要安排甲、乙兩種儀器設(shè)備的消費(fèi)，知消費(fèi)儀器設(shè)備需求需求A、B兩種材兩種材料的耗費(fèi)以及資料的耗費(fèi)以及資源的限制，如右源的限制，如右表。表。問題：工廠應(yīng)分問題：工廠應(yīng)分別消費(fèi)多少件甲、乙種儀器設(shè)備才別消費(fèi)多少件甲、乙種儀器設(shè)備才能使工廠獲利最多？能使工廠獲利最多？甲乙資源限制材料 A3210材料 B025單件獲利1 萬元1 萬元解、解、目的函數(shù)：目的函數(shù)：

2、 Max z = x1 + x2 約束條件：約束條件： s.t. 3 x1 + 2 x2 10 2 x2 5 x1，x2 0 為整數(shù)為整數(shù)不思索整數(shù)約束得到最優(yōu)解：不思索整數(shù)約束得到最優(yōu)解： x1 =1.667， x2 = 2.5；z = 4.167思索整數(shù)約束得到最優(yōu)解： x1 = 2， x2 = 2； z = 4整數(shù)規(guī)劃的最優(yōu)目的值小于相應(yīng)線性規(guī)劃的最優(yōu)目的值(相當(dāng)于附加一個約束)2 2整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的計(jì)算機(jī)求解例例2 2： Max z = 15x1 + 10 x2 + 7x3 Max z = 15x1 + 10 x2 + 7x3 s.t. s.t. 5x1 - 10 x2

3、+ 7x3 8 5x1 - 10 x2 + 7x3 8 6x1 + 4x2 + 8x3 12 6x1 + 4x2 + 8x3 12 -3x1 + 2x2 + 2x3 10 -3x1 + 2x2 + 2x3 10 x1,x2,x3 0 x1,x2,x3 0 為整數(shù)為整數(shù)例例2 2： Max z = 15x1 + 10 x2 + 7x3 Max z = 15x1 + 10 x2 + 7x3 s.t. s.t. 5x1 - 10 x2 + 7x3 8 5x1 - 10 x2 + 7x3 8 6x1 + 4x2 + 8x3 12 6x1 + 4x2 + 8x3 12 -3x1 + 2x2 + 2x3

4、10 -3x1 + 2x2 + 2x3 10 x1,x2,x3 0 x1,x2,x3 0 x3 x3 為整數(shù)為整數(shù) x1 x1 為為0-10-1變量變量用軟件求解得： x1 = 0 x2 = 3 x3 = 0 z = 30用軟件求解得： x1 = 1 x2 = 1.5 x3 = 0 z = 303 3整數(shù)規(guī)劃的運(yùn)用整數(shù)規(guī)劃的運(yùn)用(1)(1) 一、投資場所的選擇 例4、京成畜產(chǎn)品公司方案在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置 Aj (j1，2，3，10)可供選擇，思索到各地域居民的消費(fèi)程度及居民居住密集度，規(guī)定： 在東區(qū)由A1 ， A2 ，A3 三個點(diǎn)至多項(xiàng)選擇擇兩個； 在

5、西區(qū)由A4 ， A5 兩個點(diǎn)中至少選一個； 在南區(qū)由A6 ， A7 兩個點(diǎn)中至少選一個； 在北區(qū)由A8 ， A9 ， A10 三個點(diǎn)中至少選兩個。 Aj 各點(diǎn)的設(shè)備投資及每年可獲利潤由于地點(diǎn)不同都是不一樣的，預(yù)測情況見右表所示 (單位：萬元)。但投資總額不能超越720萬元，問應(yīng)選擇哪幾個銷售點(diǎn)，可使年利潤為最大?A1A2A3A4A5A6A7A8A9A10投資額10012015080709080140160180利潤36405022203025485861解：設(shè)：解：設(shè)：0-1變量變量 xi = 1 (Ai 點(diǎn)被選用或點(diǎn)被選用或 0 (Ai 點(diǎn)沒被選用。點(diǎn)沒被選用。 這樣我們可建立如下的數(shù)學(xué)模型

6、：這樣我們可建立如下的數(shù)學(xué)模型：Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 xj 為為0-1變量，變量，i = 1,2,3,10二、固定本錢問題 例5高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機(jī)器設(shè)備，制造一個容器所需的各種資源

7、的數(shù)量如右表所示。不思索固定費(fèi)用，每種容器售出一只所得的利潤分別為 4萬元、5萬元、6萬元，可運(yùn)用的金屬板有500噸，勞動力有300人月，機(jī)器有100臺月，此外不論每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號是l00萬元，中號為 150 萬元，大號為200萬元。如今要制定一個消費(fèi)方案，使獲得的利潤為最大。 解：這是一個整數(shù)規(guī)劃的問題。 設(shè)x1，x2， x3 分別為小號容器、中號容器和大號容器的消費(fèi)數(shù)量。 各種容器的固定費(fèi)用只需在消費(fèi)該種容器時才投入，為了闡明固定費(fèi)用的這種性質(zhì)，設(shè) yi = 1(當(dāng)消費(fèi)第 i種容器, 即 xi 0 時) 或0當(dāng)不消費(fèi)第 i種容器即 xi = 0 時 引

8、入約束 xi M yi ，i =1，2，3，M充分大，以保證當(dāng) yi = 0 時，xi = 0 。 這樣我們可建立如下的數(shù)學(xué)模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 為0-1變量，i = 1,2,33 3整數(shù)規(guī)劃的運(yùn)用整數(shù)規(guī)劃的運(yùn)用(2)(2)資源小號容器中號容器大號容器金屬板（噸）248勞動力（人月）234機(jī)器設(shè)備（臺月）123例6有四個工人，要分

9、別指派他們完成四項(xiàng)不同的任務(wù)，每人做各項(xiàng)任務(wù)所消耗的時間如右表所示，問應(yīng)如何指派任務(wù)，才干使總的耗費(fèi)時間為最少。 解：引入解：引入01變量變量 xij，并令，并令 xij = 1(當(dāng)指派第當(dāng)指派第 i人去完成第人去完成第j項(xiàng)任務(wù)時項(xiàng)任務(wù)時)或或0當(dāng)不指派第當(dāng)不指派第 i人去完成第人去完成第j項(xiàng)任務(wù)時項(xiàng)任務(wù)時) 這可以表示為一個這可以表示為一個0-1整數(shù)規(guī)劃問題：整數(shù)規(guī)劃問題：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+

10、 x12+ x13+ x14= 1 (甲只能干一項(xiàng)任務(wù)甲只能干一項(xiàng)任務(wù)) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)任務(wù)乙只能干一項(xiàng)任務(wù)) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)任務(wù)丙只能干一項(xiàng)任務(wù)) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)任務(wù)丁只能干一項(xiàng)任務(wù)) x11+ x21+ x31+ x41= 1 ( A任務(wù)只能一人干任務(wù)只能一人干) x12+ x22+ x32+ x42= 1 ( B任務(wù)只能一人干任務(wù)只能一人干) x13+ x23+ x33+ x43= 1 ( C任務(wù)只能一人干任務(wù)只能一人干) x14+ x24+ x34+ x4

11、4= 1 ( D任務(wù)只能一人干任務(wù)只能一人干) xij 為為0-1變量，變量，i,j = 1,2,3,4 * * * 求解可用求解可用軟件中整數(shù)規(guī)劃方法。軟件中整數(shù)規(guī)劃方法。 3 3整數(shù)規(guī)劃的運(yùn)用整數(shù)規(guī)劃的運(yùn)用(3)(3) 工作工人ABCD甲15182124乙19232218丙26171619丁19212317三、指派問題三、指派問題 有有 n n 項(xiàng)不同的義務(wù)，恰好項(xiàng)不同的義務(wù)，恰好 n n 個人可分別承當(dāng)這些義務(wù)，但由于每個人可分別承當(dāng)這些義務(wù)，但由于每人專長不同，完成各項(xiàng)義務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必需指派每個人人專長不同，完成各項(xiàng)義務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必需指派每個人去完成一項(xiàng)

12、義務(wù)，怎樣把去完成一項(xiàng)義務(wù)，怎樣把 n n 項(xiàng)義務(wù)指派給項(xiàng)義務(wù)指派給 n n 個人，使得完成個人，使得完成 n n 項(xiàng)義務(wù)的項(xiàng)義務(wù)的總的效率最高，這就是指派問題?？偟男首罡撸@就是指派問題。 四、分布系統(tǒng)設(shè)計(jì)例7某企業(yè)在 A1 地已有一個工廠，其產(chǎn)品的消費(fèi)才干為 30 千箱，為了擴(kuò)展消費(fèi)，計(jì)劃在 A2，A3，A4，A5地中再選擇幾個地方建廠。知在 A2 ， A3，A4，A5地建廠的固定本錢分別為175千元、300千元、375千元、500千元，另外， A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)(每千箱運(yùn)費(fèi))如右表所示。 a) 問應(yīng)該在哪幾個地方建廠，在

13、滿足銷量的前提下，使得其總的固定本錢和總的運(yùn)輸費(fèi)用之和最小? b) 假設(shè)由于政策要求必需在A2，A3地建一個廠，應(yīng)在哪幾個地方建廠? 解：解： a) 設(shè)設(shè) xij為從為從Ai 運(yùn)往運(yùn)往Bj 的運(yùn)輸量的運(yùn)輸量(單位千箱單位千箱)， yi = 1(當(dāng)當(dāng)Ai 被選中時被選中時)或或0當(dāng)當(dāng)Ai 沒被選中時沒被選中時) 這可以表示為一個整數(shù)規(guī)劃問題：這可以表示為一個整數(shù)規(guī)劃問題：Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10 x51 +4x52+2x53其中前

14、其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。s.t. x11+ x12+ x13 30 ( A1 廠的產(chǎn)量限制廠的產(chǎn)量限制) x21+ x22+ x23 10y2 ( A2 廠的產(chǎn)量限制廠的產(chǎn)量限制) b添加約束：添加約束：y2+y3=1 x31+ x32+ x33 20y3 ( A3 廠的產(chǎn)量限制廠的產(chǎn)量限制) x41+ x42+ x43 30y4 ( A4 廠的產(chǎn)量限制廠的產(chǎn)量限制) x51+ x52+ x53 40y5 ( A5 廠的產(chǎn)量限制廠的產(chǎn)量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 銷地的限制銷地的限制) x

15、12+ x22+ x32+ x42 + x52 = 20 ( B2 銷地的限制銷地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 銷地的限制銷地的限制) xij 0 yi為為0-1變量，變量，i = 1,2,3,4,5；j = 1,2,3 * * * 求解可用求解可用軟件中整數(shù)規(guī)劃方法。軟件中整數(shù)規(guī)劃方法。 3 3整數(shù)規(guī)劃的運(yùn)用整數(shù)規(guī)劃的運(yùn)用(4)(4) 銷地產(chǎn)地B1B2B3產(chǎn)量(千噸)A184330A252310A343420A497530A5104240銷量(千噸)3020203 3整數(shù)規(guī)劃的運(yùn)用整數(shù)規(guī)劃的運(yùn)用(5)(5)五、投資問題五、投資問題 例例8 8

16、某公司在今后五年內(nèi)思索給以下的工程投資。知：某公司在今后五年內(nèi)思索給以下的工程投資。知： 工程工程A A：從第一年到第四年每年年初需求投資，并于次年末回收本利：從第一年到第四年每年年初需求投資，并于次年末回收本利115%115%，但要求第一年投資最低金額，但要求第一年投資最低金額為為4 4萬元，第二、三、四年不限；萬元，第二、三、四年不限； 工程工程B B：第三年初需求投資，到第五年未能回收本利：第三年初需求投資，到第五年未能回收本利128128，但規(guī)定最低投資金額為，但規(guī)定最低投資金額為3 3萬元，最高金額為萬元，最高金額為5 5萬元；萬元； 工程工程 C C：第二年初需求投資，到第五年未能

17、回收本利：第二年初需求投資，到第五年未能回收本利140%140%，但規(guī)定其投資額或?yàn)?，但?guī)定其投資額或?yàn)? 2萬元或?yàn)槿f元或?yàn)? 4萬元或萬元或?yàn)闉? 6萬元或?yàn)槿f元或?yàn)? 8萬元。萬元。 工程工程 D D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%6%，此項(xiàng)投資金額不限。，此項(xiàng)投資金額不限。 該部門現(xiàn)有資金該部門現(xiàn)有資金1010萬元，問它應(yīng)如何確定給這些工程的每年投資額，使到第五年末擁有的資金本利總?cè)f元，問它應(yīng)如何確定給這些工程的每年投資額，使到第五年末擁有的資金本利總額為最大額為最大? ? 解：解：1) 設(shè)設(shè)xiA、xiB、xiC、x

18、iD ( i 1，2，3，4，5)分別表示第分別表示第 i 年年初給工程年年初給工程A，B，C，D的投資額；的投資額； 設(shè)設(shè)yiA， yiB，是，是01變量，并規(guī)定取變量，并規(guī)定取 1 時分別表示第時分別表示第 i 年給年給A、B投資，否那么取投資，否那么取 0 i = 1, 2, 3, 4, 5。 設(shè)設(shè)yiC 是非負(fù)整數(shù)變量，并規(guī)定：是非負(fù)整數(shù)變量，并規(guī)定：2年投資年投資C工程工程8萬元時，取值為萬元時，取值為4； 2年投資年投資C工程工程6萬元時，取值為萬元時，取值為3； 2年投資年投資C工程工程4萬元時，取值為萬元時，取值為2； 2年投資年投資C工程工程2萬元時，取值為萬元時，取值為1；

19、 2年不投資年不投資C工程時，工程時， 取值為取值為0； 這樣我們建立如下的決策變量：這樣我們建立如下的決策變量： 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 A x1A x2A x3A x4A B x3B C x2C (=20000y2C) D x1D x2D x3D x4D x5D 3 3整數(shù)規(guī)劃的運(yùn)用整數(shù)規(guī)劃的運(yùn)用(6)(6)2 2約束條件：約束條件：第一年：年初有第一年：年初有100000100000元，元，D D工程在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是工程在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x1A+ x1D x1A+ x1D =

20、100000= 100000；第二年：第二年：A A次年末才可收回投資故第二年年初的資金為次年末才可收回投資故第二年年初的資金為1.06x1D1.06x1D，于是，于是x2A+x2C+x2D = 1.06x1Dx2A+x2C+x2D = 1.06x1D；第三年：年初的資金為第三年：年初的資金為 1.15x1A+1.06x2D 1.15x1A+1.06x2D，于是，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D x3A+x3B+x3D = 1.15x1A+ 1.06x2D；第四年：年初的資金為第四年：年初的資金為 1.15x2A+1.06x3D 1.15x2A+1.06x3D

21、，于是，于是 x4A + x4D = 1.15x2A+ 1.06x3D x4A + x4D = 1.15x2A+ 1.06x3D；第五年：年初的資金為第五年：年初的資金為 1.15x3A+1.06x4D 1.15x3A+1.06x4D，于是，于是 x5D = 1.15x3A+ 1.06x4D x5D = 1.15x3A+ 1.06x4D；關(guān)于工程關(guān)于工程A A的投資額規(guī)定的投資額規(guī)定: x1A 40000y1A : x1A 40000y1A ，x1A 200000y1A x1A 200000y1A ，200000200000是足夠大的數(shù)；是足夠大的數(shù)； 保證當(dāng)保證當(dāng) y1A = 0 y1A =

22、 0時，時， x1A = 0 x1A = 0 ；當(dāng)；當(dāng)y1A = 1y1A = 1時，時，x1A 40000 x1A 40000 。 關(guān)于工程關(guān)于工程B B的投資額規(guī)定的投資額規(guī)定: x3B 30000y3B : x3B 30000y3B ，x3B 50000y3B x3B 50000y3B ； 保證當(dāng)保證當(dāng) y3B = 0 y3B = 0時，時， x3B = 0 x3B = 0 ；當(dāng)；當(dāng)y3B = 1y3B = 1時，時，50000 x3B 30000 50000 x3B 30000 。 關(guān)于工程關(guān)于工程C C的投資額規(guī)定的投資額規(guī)定: x2C = 20000y2C : x2C = 2000

23、0y2C ，y2C = 0y2C = 0，1 1，2 2，3 3，4 4。3 3目的函數(shù)及模型：目的函數(shù)及模型： Max z = 1.15x4A+ 1.40 x2C+ 1.28x3B + 1.06x5D Max z = 1.15x4A+ 1.40 x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000 s.t. x1A+ x1D = 100000； x2A+x2C+x2D = 1.06x1D x2A+x2C+x2D = 1.06x1D； x3A+x3B+x3D = 1.15x1A+ 1.06x2D x3A+x3B+x3D = 1.15x1A+ 1.06x2D

24、； x4A+x4D = 1.15x2A+ 1.06x3D x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D x5D = 1.15x3A+ 1.06x4D； x1A 40000y1A x1A 40000y1A ， x1A 200000y1A x1A 200000y1A ， x3B 30000y3B x3B 30000y3B ， x3B 50000y3B x3B 50000y3B ； x2C = 20000y2C x2C = 20000y2C ， yiA yiA， yiB = 0 yiB = 0 或或 1 1，i = 1,2,3,4,5i = 1

25、,2,3,4,5 y2C = 0 y2C = 0，1 1，2 2，3 3，4 4 xiA xiA ，xiB xiB ，xiC xiC ，xiD 0 ( i = 1xiD 0 ( i = 1、2 2、3 3、4 4、5 5 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(1)(1)問題A Min z = c1 x1 + c2 x2 + + cn xn 記 問題B為去掉整數(shù)約束的問題A s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2

26、 ， ，xn 0 為整數(shù)在分枝定界法過程中求解問題(B)，應(yīng)有以下情況之一： (B)無可行解，那么(A)亦無可行解，停頓對此問題 的計(jì)算； (B)有最優(yōu)解，并滿足整數(shù)約束，即同時為(A)的最優(yōu)解，那么z*同時是當(dāng)前問題(A)最優(yōu)目的值的上界和下界。停頓對這個問題的計(jì)算； (B)有最優(yōu)解 x 及最優(yōu)值 z 但不符合整數(shù)條件。這時得到當(dāng)前問題(A)最優(yōu)目的值的一個下界 z z ,于是經(jīng)過以下判別可對此問題進(jìn)一步計(jì)算。分枝定界法的計(jì)算過程： 1、對原問題(A)，求解松弛問題(B)。根據(jù)上面分析，假設(shè)出現(xiàn)情況，那么停機(jī)。假設(shè)情況發(fā)生，得到(A)問題最優(yōu)值的一個下界。我們?nèi)握?A)問題的一個可行解，那么

27、對應(yīng)的目的函數(shù)值是(A)最優(yōu)值的一個上界 z 。即得到 z z* z。(注：找(A)問題的可行解往往需求較大的計(jì)算量，這時可簡單記 z+，而先不用費(fèi)很大力量去求較好的上界。從以下分析可以看到，找到一個好的最優(yōu)目的值上界，將對算法的快速求得目的非常有效。)，轉(zhuǎn)2，進(jìn)展以下普通步的迭代； 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(2)(2)2、對當(dāng)前問題進(jìn)展分枝和定界： 分技：無妨設(shè)當(dāng)前問題為(A)，其松弛問題(B)的最優(yōu)解不符合整數(shù)約束，任取非整數(shù)的分量 xr 。構(gòu)造兩個附加約束： xr xr 和 xr xr+1 ，對(A)分別參與這兩個約束，可得到兩個子問題(A1)和(A2)，顯然這兩個

28、子問題的可行解集的并是(A)的可行解集； 定界：根據(jù)前面分析，對每個當(dāng)前問題(A)可以經(jīng)過求解松弛問題(B)，以及找(A)的可行解得到當(dāng)前問題的上、下界 z和 z 。 對普通迭代步，設(shè)根據(jù)分枝定界方法得到了原問題(A)的一個同層子問題(AI )，i1，2，.，n 之和的分解。這里的同層子問題是指每個子問題(AI)都是(A)經(jīng)過一樣分枝次數(shù)得到的。 3、比較與剪枝： 對當(dāng)前子問題進(jìn)展調(diào)查，假設(shè)不需再進(jìn)展計(jì)算，那么稱之為剪枝。普通遇到以下情況就需剪枝： (B)無可行解； (B)的最優(yōu)解符合整數(shù)約束； (B)的最優(yōu)值 z z 。 經(jīng)過比較，假設(shè)子問題不剪枝那么前往 2 。 分枝定界法當(dāng)一切子問題都剪

29、枝了，即沒有需求處置的子問題時，到達(dá)當(dāng)前上界 z 的可行解即原問題的最優(yōu)解， 算法終了。4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(3)(3) 分枝定界法是求整數(shù)規(guī)劃的一種常用的有效的方法，既能處理純整數(shù)規(guī)劃的問題，也能處理混合整數(shù)規(guī)劃的問題。例：Min f = -5x1-4x2s.t. 3x1+4x2 24 9x1+5x2 45 x1,x2 0 整數(shù)4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(4)(4) 隱枚舉法是求解01規(guī)劃最常用的方法之一 對于 n 個決策變量的完全 01 規(guī)劃，其可行點(diǎn)最多有 2n 個，當(dāng) n 較大時其計(jì)算量大得驚人。隱枚舉法的根本思想是根據(jù)01規(guī)劃的特點(diǎn)，進(jìn)展

30、分技逐漸求解。1、用于隱枚舉法的01規(guī)劃規(guī)范方式： 為了計(jì)算的方便，需求把普通的 01規(guī)劃問題等價(jià)地化成以下規(guī)范方式 Min f = c1 x1 + c2 x2 + + cn xn cj 0 j = 1,2,n s.t. ai1 x1 + ai2 x2 + + ain xn bi i = 1,2,m x1 ，x2 ， ，xn = 0 或 1下面闡明一個完全的01規(guī)劃問題可以化為等價(jià)的規(guī)范方式： (1)假設(shè)目的函數(shù)求最大：Max z，可令 f = - z，變?yōu)榍笞钚?Min f ； (2)假設(shè)目的函數(shù)的系數(shù)有負(fù)值時，如 cj 0。那么，可以令相應(yīng)的 yj = 1- xj ； (3)當(dāng)某個約束不等

31、式是“時，只需兩端同乘以 -1，即變?yōu)椤?； (4)當(dāng)某個約束是等式約束時，可得到兩個方向相反的不等式。4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(5)(5)隱枚舉法的根本過程：隱枚舉法的根本過程： 1、將、將01規(guī)劃問題化為規(guī)范方式，設(shè)其最優(yōu)解為規(guī)劃問題化為規(guī)范方式，設(shè)其最優(yōu)解為 x*，最優(yōu)目的值為，最優(yōu)目的值為 f* 。顯然。顯然 x = 0 時，目的值時，目的值 f 0 是不思索線性不等式約束的最小解，于是是不思索線性不等式約束的最小解，于是 f* 0。假設(shè)。假設(shè) x = 0 是可行解，那末是可行解，那末 f 0是該問題的最優(yōu)解，終了計(jì)算。否那么，置一切分量為自是該問題的最優(yōu)解，終了

32、計(jì)算。否那么，置一切分量為自在變量。轉(zhuǎn)在變量。轉(zhuǎn)2； 2、任選一自在變量、任選一自在變量 xk ，令，令 xk 為固定變量，分別固定為為固定變量，分別固定為 xk = 0 與與 xk 1，令一切，令一切自在變量取零值，那么得到兩個分枝。對每個分枝的試探解進(jìn)展檢驗(yàn)把自在變自在變量取零值，那么得到兩個分枝。對每個分枝的試探解進(jìn)展檢驗(yàn)把自在變量逐次定為固定變量的順序可以是恣意的，在不進(jìn)展先驗(yàn)調(diào)查時，常按目的變量量逐次定為固定變量的順序可以是恣意的，在不進(jìn)展先驗(yàn)調(diào)查時，常按目的變量從小到大的順序進(jìn)展。轉(zhuǎn)從小到大的順序進(jìn)展。轉(zhuǎn)3； 3、檢驗(yàn)當(dāng)前試探解時，遇到以下、檢驗(yàn)當(dāng)前試探解時，遇到以下4種情況就剪枝

33、，即不用再向下分枝，在剪枝的子種情況就剪枝，即不用再向下分枝，在剪枝的子問題下方標(biāo)志問題下方標(biāo)志“： 情況一：假設(shè)子問題的試探解可行，即滿足一切線性不等式約束，那么此問題的目情況一：假設(shè)子問題的試探解可行，即滿足一切線性不等式約束，那么此問題的目的值是原問題最優(yōu)目的值的一個上界記為的值是原問題最優(yōu)目的值的一個上界記為 f 即即 f* f 。把。把 f 的值記在子問題的值記在子問題框的旁邊，并在下方標(biāo)志上框的旁邊，并在下方標(biāo)志上“；4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(6)(6) 情況二：假設(shè)試探解不可行，且存在一個線性不等式約束，將一切固定變量值代入后，所得到的不等式中一切負(fù)系數(shù)之和

34、大于右端項(xiàng)或假設(shè)無負(fù)系數(shù)時，最小的系數(shù)大于右端項(xiàng)，那么此問題的任何分枝都是不可行的問題。于是在此問題框的下方標(biāo)志“； 情況三：假設(shè)試探解不可行，且它的目的值與目的函數(shù)中對該當(dāng)前自在變量的任一個系數(shù)之和大于一切已得到的上界中最小者時，闡明在當(dāng)前問題的根底上，固定任何自在變量都不能夠?qū)δ康暮瘮?shù)有改善，于是在該問題框的下方標(biāo)志“； 情況四：假設(shè)試探解不可行，但一切變量已被置為固定變量，也應(yīng)剪枝，于是在該問題框的下方標(biāo)志“。 把已標(biāo)志“的子問題，稱為已探明的枝。轉(zhuǎn)4。 4、進(jìn)一步調(diào)查。假設(shè)一切的枝均為已探明的枝，那么停機(jī)終了計(jì)算。找出一切子問題框邊標(biāo)志 f 值的問題，比較得到其中最小者，其對應(yīng)的試探解

35、即原問題的最優(yōu)解，相應(yīng)值即原問題的最優(yōu)目的值 f*；假設(shè)沒有標(biāo)志 f 值的框，那么闡明原問題無最優(yōu)解，實(shí)踐上原問題無可行解。 假設(shè)仍存在尚未探明的分枝，那么可任選一個未探明的分枝。轉(zhuǎn)2。4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(7)(7)0-10-1規(guī)劃的隱枚舉法規(guī)劃的隱枚舉法例：例：Max z=100 x1+30 x2+40 x3+45x4Max z=100 x1+30 x2+40 x3+45x4s.t. s.t. 50 x1+30 x2+25x3+10 x49550 x1+30 x2+25x3+10 x495 7x1+ 2x2+ 3x3+ 7x1+ 2x2+ 3x3+ 4x4114x41