1、第14，15個整數(shù)編程(a)，1概述2切割平面方法第3季度劃分方法4隱藏枚舉方法，1概述(1)，1，如果定義計(jì)劃中的變量(部分或全部)限制為整數(shù)，則稱為整數(shù)儀表盤。在線性規(guī)劃模型中，如果變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。其次，沒有特殊說明的整數(shù)規(guī)劃分類通常是指整數(shù)線性規(guī)劃。對于整數(shù)線性標(biāo)準(zhǔn)模型，可分為兩大類。變量完全限定為整數(shù)，稱為純(完全)整數(shù)編程。變量部分限于稱為混合整數(shù)編程的整數(shù)。1概述(2)，3，整數(shù)編程特征整數(shù)編程標(biāo)準(zhǔn)格式(實(shí)際整數(shù)線性編程)AX=b，X0，CTX=min，XJ為整數(shù)(j=1，)原始線性規(guī)劃最優(yōu)解均為整數(shù)時(shí)，整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。整數(shù)編程沒有可行的解決

2、方案。1概述(3)，示例2-1原始線性配置為2x4x2=5，X0，CTX=x1 x2=min的最佳實(shí)際解決方案為x1=0，x2=5/4，雖然有可行的解決方案(當(dāng)然有最佳解決方案)，但最佳解決方案值會惡化。示例2-2原始線性配置為2x1 4x2=6、x0、CTX=x1 x2=min的最佳實(shí)際解決方案為x1=0、x2=3/2、min CTX=3/2。整數(shù)限制為x1=1、x2=1和min CTX=2。1概述(4)、2整數(shù)編程最佳解決方案不能根據(jù)實(shí)數(shù)最佳解決方案簡單地舍入。實(shí)例2-3項(xiàng)目裝載問題：每個項(xiàng)目的價(jià)值和重量分別為VJ和wj (j=1，n)，運(yùn)載工具的最大裝載重量為：要最大限度地提高每個項(xiàng)目的

3、總價(jià)值，需要裝入多少項(xiàng)目？要使Xj表示類j項(xiàng)的安裝數(shù)，可以使用整數(shù)配置，例如xj0，定理(2)，1概述(5)，如果不限制為整數(shù)，則最佳解決方案的基本組成部分XM是JM，如果xj=0限制為整數(shù)，則必須仔細(xì)計(jì)算(后面介紹該方法)。例如，示例2-3為51x 1 50x 250 x 3100 150 x 1100 x 299 x 3=max XJ 0，1概述(6)，如果整數(shù)不受限制，則m=1，比率為150/510但是，如果項(xiàng)目不能截?cái)?，因此限制為整?shù)，則最佳解決方案為x1=0、x2=2、x3=0?？傊禐?00。如本例所示，整數(shù)規(guī)劃最優(yōu)解在最優(yōu)實(shí)際實(shí)數(shù)解中不能簡單地得到四舍五入到4周5的結(jié)果。因此，要解

4、決整數(shù)編程，必須開發(fā)新的技術(shù)。1概述(7)、4、解決方法分類：1切面方法主要是純整數(shù)線性編程第二季度邊界方法是純整數(shù)線性編程3隱藏枚舉方法解決方案“01”整數(shù)編程：過濾器隱藏枚舉方法；分支隱藏枚舉法4匈牙利法解決分配問題(“01”計(jì)劃特殊情況)。5 Monte Carlo方法解決各種類型的計(jì)劃。2切平面法，這種方法適合解決純整數(shù)編程問題?；鞠敕ㄊ窍葎h除整數(shù)約束，解決一般線性編程問題。如果所有最佳解決方案都是整數(shù)，則結(jié)束。否則，基于此非最佳整數(shù)變量在原始約束條件中增加剪切約束，然后繼續(xù)求解直到結(jié)束。三種劃分方法(1)、分支劃分方法已成功地應(yīng)用于解決當(dāng)前整數(shù)計(jì)劃問題、生產(chǎn)日程問題、旅行推銷員問題

5、、工廠地點(diǎn)問題、背包問題和分配問題等。因此，分支定界算法是求解整數(shù)編程最有用的算法之一?，F(xiàn)在，聯(lián)合示例是算法的思想。示例2-5求解以下整數(shù)編程目標(biāo)函數(shù)min z=x1 4x2約束2x1 x28 x1 2x26 x1、x20和整數(shù)，第三季度劃分方法(2)，解決方案1)不限于整數(shù)，通過一般線性編程解決，最佳解決方案為x1=10此解決方案顯示了圖2-4中的節(jié)點(diǎn)。三種區(qū)分方法(3)、2) x1和x2當(dāng)前不是整數(shù)，因此不滿足整數(shù)要求，選擇一個進(jìn)取的分支。設(shè)定X10/3=3和x110/3=4 3) x13的目標(biāo)函數(shù)min z=x1 4x2限制條件2x1 x28 x1 2x26 x13 x1、x20和整數(shù)的

6、兩個子集。第三季度和邊界方法(4)、尋找最佳解決方案，沒有整數(shù)限制。x1=3，x2=3/2，z=9(參見圖2-2)。此解決方案顯示了圖2-4中的節(jié)點(diǎn)。第三季度和界限方法(5)，4) x14的目標(biāo)函數(shù)min z=x1 4x2約束條件2x1 x28 x1 2x26 x14 x20 x1 x2為整數(shù)。第三季度和邊界方法(6)，、解決相應(yīng)的線性編程，不受整數(shù)限制，并以圖形方式觀察無解決方案(見圖2-3)。圖2-4中顯示了此解決方案。第三季度劃分方法(7)，5)節(jié)點(diǎn)，x23/2=1目標(biāo)函數(shù)min z=x1 4x2約束2 x1x28 x12x26x11x1，x20和整數(shù)。使用圖形方法不知道子集的話，讀者可

7、以自己創(chuàng)建。第三季度劃分方法(8)，6)節(jié)點(diǎn)，x23/2 1=2目的函數(shù)min z=x1 4x2約束2x1 x28 x1 2x26 x13 x22 X10，全部完成。圖形方法如圖2-5所示，最佳解決方案為x1=2、x2=2和z=10。第三季度和邊界方法(9)、(圖2-4，3季度和邊界方法(10)、總結(jié)了解決示例2-5中整數(shù)編程的分支和邊界方法的特點(diǎn)。(I)完全整數(shù)規(guī)劃和混合整數(shù)規(guī)劃都可以解決。(ii)求解每個子集的最佳整數(shù)解，首先是拋棄整數(shù)約束，用線性規(guī)劃解尋找不受約束的最佳解。此時(shí)，目標(biāo)函數(shù)值是該子集所有可能解決方案的目標(biāo)下限(對于最小值計(jì)劃)。(iii)如果子集的非整數(shù)最佳解決方案的下限超

8、過到目前為止獲得的最佳可能整數(shù)解決方案目標(biāo)值，或子集未解，則此子集將被截?cái)?也稱為修剪)。如果第三季度劃分方法(11)、(iv)子集的非整數(shù)最優(yōu)解決方案滿足變量的整數(shù)要求，則稱為整數(shù)編程的可行解決方案，如果相應(yīng)的目標(biāo)函數(shù)值低于可行的整數(shù)解決方案目標(biāo)，則替換原始最佳解決方案，否則截?cái)嘧蛹?v)如果不是子集的整數(shù)的最優(yōu)解不滿足整數(shù)要求，但未截?cái)?，則選擇不滿足整數(shù)要求的變量進(jìn)行分支。(VI)此方法只能用于整數(shù)線性編程。4隱藏的枚舉方法(1)、隱藏的枚舉方法適用于解決特殊整數(shù)編程01計(jì)劃。首先，01計(jì)劃的實(shí)際來源實(shí)例2-6投資地點(diǎn)選擇(互不相容計(jì)劃)的實(shí)例。一個部門計(jì)劃在東部、西部和南部3區(qū)創(chuàng)建門，

9、可選擇的位置共有7個，并將設(shè)置為Ai (i=1，2，7)。根據(jù)計(jì)劃承付款，在東部地區(qū)，有三個候選地點(diǎn)A1、A2和A3的多個選擇。在西部地區(qū)，A4、A5的2個候選人中至少選擇了1個。在南區(qū)，從2個候選地點(diǎn)A6，A7中至少選出1個。4隱藏的枚舉方法(2)，知道，選擇Ai點(diǎn)設(shè)備投資不能超過bi元，年度ci元，總投資額不能超過b元。問：選擇幾個點(diǎn)投資，以最大限度地提高年總利潤？首先，引入01變量Xi (i=1，2，7)，以便將問題創(chuàng)建為01整數(shù)編程模型。目標(biāo)函數(shù)max z=，4隱藏枚舉法(3)，約束投資限制，x1 x2 x32東部約束x4 x51西部約束x71南部約束xi=0或1 (i=1，)符合x1

10、，x2，x3=(1，0，0)約束，因此是可行的解決方案，z=3。2)如果由于最大值問題而尋找最佳解決方案，則目標(biāo)值z3的所有解決方案可以在不檢查是否滿足約束條件的情況下刪除。也就是說，可能不是最佳解決方案，因此需要添加約束條件(目標(biāo)值下限)。3x12x2 5x33此樣式稱為過濾條件，它過濾組合中創(chuàng)建的所有目標(biāo)z3。，此示例使用此方法解決，如表2-1所示?？梢愿倪M(jìn)4個隱藏的枚舉方法(6)、表格2-1，4隱藏的枚舉方法(7)、3過濾器，并對表格2-1大于3的所有組合執(zhí)行約束檢查。實(shí)際上，您可以在運(yùn)算中修改它，并且應(yīng)使用到目前為止發(fā)生的最大可能解決方案目標(biāo)值作為以后運(yùn)算的篩選器。4)要驗(yàn)證篩選器條件

11、，首先計(jì)算每個組合的目標(biāo)值，因此必須首先計(jì)算目標(biāo)值z較大的組合。這樣可以提前提高過濾器閾值，從而減少計(jì)算量。因此，組合變量x1、x2、x3以表2-1格式排列時(shí)，(x2、x1、x3)的改進(jìn)計(jì)算必須按表2-2中所示的系數(shù)單位升序排列。4隱藏枚舉法(8)，表2-2作為增強(qiáng)的過濾器，示例2-7，z3 z5 z8，4隱藏枚舉法(9)，表濾波enum方法簡單實(shí)用，但即使變量數(shù)多，計(jì)算量仍然很大。為此，下面介紹了分支隱藏枚舉方法的其他方法。4隱藏枚舉法(10)，3，0 1計(jì)劃求解法的第二個(分支隱藏枚舉法)基本思路：將原始0 1計(jì)劃問題創(chuàng)建為標(biāo)準(zhǔn)形狀(分支隱藏枚舉法的標(biāo)準(zhǔn)形狀)，然后在可能的最佳用途函數(shù)組合

12、中檢查(不一定是可能的)，直到找到可能的解決方案為了清楚起見，下面結(jié)合示例說明了該步驟。1示例2-8已知的0 1整數(shù)編程模型包括目標(biāo)函數(shù)min z=4x1 3x22x3，4隱藏枚舉(11)，約束2x15x23x44x1x23x31所有XJ=0，1j=1，2在此范例中，目標(biāo)函數(shù)min z=4x1 3x2 2x3限制條件Q1=42x 15x 23q 2=-34x 1x23x 330 Q3=-1x2x 30 x1，x2，x3的1，0，4隱藏列舉(13此時(shí)，如果z=0，請確保滿足約束，即Qi0。用以下內(nèi)容替換XJ=0:Q1=40 Q2=-30 Q3=-10不是可行的解決方案。因此，x1、x2和x3是未

13、定義的值，稱為自由形式變量。請參見圖2-7中的節(jié)點(diǎn)。4隱藏枚舉法(14)，3)判斷當(dāng)前節(jié)點(diǎn)是否能拉動此步驟的目的是如果所有自由變量都設(shè)置為0，那么如果不可能，是否有其他值的解決方案？如果自由變量此時(shí)不可用，則表示無法解決離開該節(jié)點(diǎn)的問題。檢查方法是在未滿足的約束Qi中，將具有正系數(shù)的變量從0更改為1(這可能導(dǎo)致qi0 Q3=-1 1=10，4隱藏枚舉方法(15)，原始Q10，仍然為0，節(jié)點(diǎn)可能的解決方案)4)節(jié)點(diǎn)分支在給定節(jié)點(diǎn)上，一次組合一個變量和已設(shè)定值的變量，創(chuàng)建兩個分支。究竟選擇什么自由變量來分支呢？通常使用考試方法，其中比較有效的方法是“可行的距離法”。如果將候選自由變量集設(shè)置為t=1，2，3，該方法的選擇規(guī)則在t中選擇變量值為1，則未滿足的約束Qi值將是距零點(diǎn)的最小距離(在可執(zhí)行點(diǎn)被視為0的約束滿足Qi)。4隱藏枚舉方法(16)，節(jié)點(diǎn)的分支測試：變量x1=1點(diǎn)(剩馀0)可執(zhí)行距離Q1=4-2=20(滿足)0 Q25)節(jié)點(diǎn)中，x3=1是規(guī)定值，x1、x2是自由變量，先令都是0。此時(shí)，檢查可行性，例如x1=0、x2=0、x3=1、z=4x1 3x2 2x3=2，然后用三個約束替換此解決方案。Q1=4-3=10