中農(nóng)大水資源和環(huán)境模型與優(yōu)化課件第3講 動態(tài)規(guī)劃和整數(shù)規(guī)劃

第3講

動態(tài)規(guī)劃和整數(shù)規(guī)劃1第一節(jié)

動態(tài)規(guī)劃23在系統(tǒng)分析中，動態(tài)規(guī)劃是一種應用很廣的數(shù)學方法。它廣泛應用與資源分配、生產(chǎn)計劃、貨物運輸和儲存等方面。它是把一個復雜的系統(tǒng)分析問題分解為一個多階段的決策過程。并按一定的順序或時序，從第一階段開始，逐次求出沒階段的最優(yōu)決策，并經(jīng)歷各個階段，從而求得整個系統(tǒng)的最優(yōu)策略。動態(tài)規(guī)劃的基本原理是貝爾曼（Bellman）所提出的最優(yōu)化原理：“一個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論初始狀態(tài)和初始決策如何，對以第一個決策所形成的的狀態(tài)作為初始狀態(tài)的過程而言，其余的決策必須構(gòu)成優(yōu)策略”動態(tài)規(guī)劃的基本概念4根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)變量，分為離散決策過程和連續(xù)決策過程。根據(jù)決策過程的演變是確定性的還是隨機性的，又可分為確定性決策過程和隨機性決策過程。組合起來可分為離散確定性離散隨機性連續(xù)確定性連續(xù)隨機性動態(tài)規(guī)劃模型的分類

5在生產(chǎn)和科學實驗中，有一類活動的過程，由于它的特殊性，可將過程分為若干個互相聯(lián)系的階段，在它的每一個階段都需要作出決策，從而使整個過程達到最好的活動效果。因此，各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線。這種把一個問題可看作是一個前后關聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，也稱序貫決策過程。多階段的決策過程6下圖表示擬建一條輸水道，從水源A處將一定量水輸送到需水區(qū)G。由于地形、地質(zhì)和土地利用等因素的不同，可以有各種不同的引水路線方案，圖中的B、C、D、E、F表示輸水路線可能通過的地點，標在連線上的數(shù)字代表該段的修建費用。求修建費用最小的輸水路線方案。輸水路線選擇問題輸水線路選擇簡圖71.階段把所給問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。階段的劃分，一般是根據(jù)時間和空間的自然特征來劃分，但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。如輸水線路的方案選擇問題中可分為6個階段來求解，k分別等于1、2、3、4、5、6。動態(tài)規(guī)劃的基本概念階段1階段2階段3階段4階段5階段682．狀態(tài)狀態(tài)表示每個階段開始所處的自然狀況或客觀條件，它描述了研究問題過程的狀況，又稱不可控因素。在輸水線路的方案選擇問題中，狀態(tài)就是某階段的出發(fā)位置。它既是該階段某支路的起點，又是前一階段某支路的終點。通常一個階段有若干個狀態(tài)，第一階段有一個狀態(tài)就是點A，第二階段有兩個狀態(tài)，即點集合｛B1，B2｝，一般第k階段的狀態(tài)就是第k階段所有始點的集合。動態(tài)規(guī)劃的基本概念階段1階段2階段3階段4階段5階段69描述過程狀態(tài)的變量稱為狀態(tài)變量。它可用一個數(shù)、一組數(shù)或一向量(多維情形)來描述。常用Sk表示第k階段的狀態(tài)變量。如在例1中第三階段有四個狀態(tài)，則狀態(tài)變量Sk可取四個值，即C1、C2、C3、C4。點集合｛C1，C2，C3，C4｝就稱為第三階段的可達狀態(tài)集合。記為S3＝｛C1，C2，C3，C4｝。有時為了方便起見，將該階段的狀態(tài)編上號碼1，2…這時也可記S3＝｛1，2，3，4｝。第k階段的可達狀態(tài)集合就記為Sk馬爾科夫性這里所說的狀態(tài)應具有下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響。換句話說，過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展，當前的狀態(tài)是以往歷史的一個總結(jié)。這個性質(zhì)稱為無后效性(即馬爾科夫性)。動態(tài)規(guī)劃的基本概念103．決策決策表示當過程處于某一階段的某個狀態(tài)時，可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變量，稱為決策變量。它可用一個數(shù)、一組數(shù)或一向量來描述。常用uk（sk）表示第k階段當狀態(tài)處于sk時的決策變量。它是狀態(tài)變量的函數(shù)。在實際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有uk（sk）∈Dk(sk)。動態(tài)規(guī)劃的基本概念113．決策如在例1第二階段中，若從狀態(tài)B1出發(fā)，就可作出三種不同的決策，其允許決策集合D2(B1)＝｛C1，C2，C3｝，若選取的點為C2，則C2是狀態(tài)B1在決策u2(B1)作用下的一個新的狀態(tài)，記作u2(B1)=C2。動態(tài)規(guī)劃的基本概念12動態(tài)規(guī)劃的基本概念4．策略策略是一個按順序排列的決策組成的集合。由過程的第k階段開始到終止狀態(tài)為止的過程，稱為問題的后部子過程。由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過程策略，簡稱子策略，記為，即當k=1時，此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為，即在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，用P表示。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。13動態(tài)規(guī)劃的基本概念5．狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。若給定第k階段狀態(tài)變量的值，如果該段的決策變量uk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1的值也就完全確定。即sk+1的值隨sk和uk的值變化而變化。這種確定的對應關系，記為上式描述了由k階段到k+1階段的階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)。如例1中，狀態(tài)轉(zhuǎn)移方程為14動態(tài)規(guī)劃的基本概念6．指標函數(shù)和最優(yōu)值函數(shù)用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)。它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。常用Vk,n表示，即對于要構(gòu)成動態(tài)規(guī)劃模型的指標函數(shù)，應具有可分離性，并滿足遞推關系。即Vk,n可以表示為sk、uk、Vk+1,n的函數(shù)，記為在實際問題中很多指標函數(shù)都滿足這個性質(zhì)。15動態(tài)規(guī)劃的基本概念(1)過程和它的任一子過程的指標是它所包含的各階段的指標的和。即其中表示第j階段的階段指標，這時上式可寫成(2)過程和它的任一子過程的指標是它所包含的各階段的指標的乘積。即這時就可寫成 常見的指標函數(shù)形式16動態(tài)規(guī)劃的基本概念指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為。它表示從第k階段的狀態(tài)sk開始到第n階段的終止狀態(tài)的過程，采取最優(yōu)策略所得到的指標函數(shù)值。即“opt”是最優(yōu)化(optimization)的縮寫，可根據(jù)題意而取min或max。17動態(tài)規(guī)劃的基本思想和基本方程結(jié)合最佳輸水路線問題介紹動態(tài)規(guī)劃方法的基本思想。生活中的常識告訴我們，最佳輸水路線有一個重要特性：如果由起點A經(jīng)過P點和H點而到達終點G是一條最佳輸水路線，則由點P出發(fā)經(jīng)過H點到達終點G的這條子路線，對于從點P出發(fā)到達終點的所有可能選擇的不同路線來說，必定也是最佳輸水路線。例如，在最佳輸水路線問題中，若找到了A→B1→C2→D1→E2→F2→G是由A到G的最佳輸水路線，則一個最優(yōu)策略的子策略總是最優(yōu)的，D1→E2→F2→G應該是由D1出發(fā)到G點的所有可能選擇的不同路線中的最佳輸水路線。證明：（用反證法）如果不是這樣，則從點P到G點有另一條距離更短的路線存在，把它和原來最佳輸水路線由A點到達P點的那部分連接起來，就會得到一條由A點到G點的新路線，它比原來那條最佳輸水路線的距離還要短些。這與假設矛盾，是不可能的。18動態(tài)規(guī)劃的基本思想和基本方程根據(jù)最佳輸水路線這一特性，尋找最佳輸水路線的方法，就是從最后一段開始，用由后向前逐步遞推的方法，求出各點到G點的最佳輸水路線，最后求得由A點到G點的最佳輸水路線。所以，動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易罴演斔肪€的一種方法，下面按照動態(tài)規(guī)劃的方法，將例1從最后一段開始計算，由后向前逐步推移至A點。19動態(tài)規(guī)劃的基本思想和基本方程當k=6時，由F1到終點G只有一條路線，故。同理，當k=5時，出發(fā)點有三個。若從E1出發(fā)，則有兩個選擇①至F1，②至F2，則其相應的決策為這說明，由E1至終點G的最佳輸水距離為7，其最佳輸水路線是20動態(tài)規(guī)劃的基本思想和基本方程同理，從E2和E3出發(fā)，則有其相應的決策為且21動態(tài)規(guī)劃的基本思想和基本方程當k=4時，有當k=3時，有當k=2時，有當k=1時，出發(fā)點有一個A點，則且。于是得到從起點A到終點G的最佳輸水距離為18。

22動態(tài)規(guī)劃的基本思想和基本方程為了找出最佳輸水路線，再按計算的順序反推之，可求出最優(yōu)決策函數(shù)序列，即由組成一個最優(yōu)策略。因而，找出相應的最佳輸水路線為

23動態(tài)規(guī)劃的基本思想和基本方程從上面的計算過程中可以看出，在求解的各個階段，我們利用了k階段與k+1階段之間的遞推關系：一般情況，k階段與k+1階段的遞推關系式可寫成邊界條件為

遞推關系式(式-1)稱為動態(tài)規(guī)劃的基本方程。

24動態(tài)規(guī)劃方法基本思想歸納：1.動態(tài)規(guī)劃方法的關鍵在于正確地寫出基本的遞推關系式和恰當?shù)倪吔鐥l件(簡言之為基本方程)。要做到這一點，必須先將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題化成一族同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。2.在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來各段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的。動態(tài)規(guī)劃的基本思想和基本方程25動態(tài)規(guī)劃的基本思想和基本方程在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。如最佳輸水路線問題，初始狀態(tài)A已知，則按下面箭頭所指的方向逐次變換有從而可得最優(yōu)策略為｛u1(A),u2(B1),…,u0’(F2)｝，相應的最佳輸水路線為26動態(tài)規(guī)劃的方法比窮舉法有以下優(yōu)點：(1)減少了計算量。計算例1若用窮舉法，就要對48條路線進行比較，運算在計算機上進行時，比較運算要進行47次；求各條路線的距離，即使用逐段累加方法，也要進行6+12+24+48+48＝138次加法運算。用動態(tài)規(guī)劃方法來計算，比較運算(從k=5段開始向前算)共進行3+3+4+4+1＝15次。每次比較運算相應有兩次加法運算，再去掉中間重復兩次(即B1→C1，B2→C4各多算了一次)，實際只有28次加法運算。可見，動態(tài)規(guī)劃方法比窮舉法減少了計算量。而且隨著段數(shù)的增加，計算量將大大地減少。(2)豐富了計算結(jié)果。在逆序(或順序)解法中，我們得到的不僅僅是由A點(或G點)出發(fā)到G點(或A點)的最佳輸水路線及相應的最佳輸水距離，而且得到了從所有各中間點出發(fā)到G點(或A點)的最佳輸水路線及相應的距離。這就是說，求出的不是一個最優(yōu)策略，而是一族的最優(yōu)策略。動態(tài)規(guī)劃的基本思想和基本方程27建立動態(tài)規(guī)劃模型的五個要點：(1)將問題的過程劃分成恰當?shù)碾A段；(2)正確選擇狀態(tài)變量sk，使它既能描述過程的演變，又要滿足無后效性；(3)確定決策變量uk及每階段的允許決策集合Dk(sk)；(4)正確寫出狀態(tài)轉(zhuǎn)移方程；(5)正確寫出指標函數(shù)Vk,n的關系，它應滿足下面三個性質(zhì)：①是定義在全過程和所有后部子過程上的數(shù)量函數(shù)；②要具有可分離性，并滿足遞推關系。即

③函數(shù)對于變量Vk+1,n要嚴格單調(diào)。動態(tài)規(guī)劃的基本思想和基本方程28動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理動態(tài)規(guī)劃的最優(yōu)性原理：“作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?！?/p>

簡言之，一個最優(yōu)策略的子策略總是最優(yōu)的。動態(tài)規(guī)劃的基本方程或者說最優(yōu)性定理才是動態(tài)規(guī)劃的理論基礎

29動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理動態(tài)規(guī)劃的最優(yōu)性定理：設階段數(shù)為n的多階段決策過程，其階段編號為

k=0，1，…，n-1允許策略為最優(yōu)策略的充要條件是對任意一個k有

式中，它是由給定的初始狀態(tài)s0和子策略所確定的k段狀態(tài)。當V是效益函數(shù)時，opt取max；當V是損失函數(shù)時，opt取min。30

動態(tài)規(guī)劃舉例——最優(yōu)配水問題31

動態(tài)規(guī)劃舉例——最優(yōu)配水問題32用逆序法將上述問題寫成遞推方程形式，對于第N階段只有一個用戶N，其效益取決于分配的水量，即在第N-1階段，則有兩個用戶。如果我們分配給N-1用戶水量為dN-1，其收入為gN-1(dN-1)，并留下水量q-dN-1分配給用戶N。應用最優(yōu)化原理，從兩個用戶到的最優(yōu)收入為依此類推，可以寫出一般的遞推方程形式，有動態(tài)規(guī)劃舉例——最優(yōu)配水問題33

動態(tài)規(guī)劃舉例——最優(yōu)配水問題第二節(jié)

整數(shù)規(guī)劃3435在第一節(jié)課討論的LP問題中，對決策變量只限于不能取負值的連續(xù)型數(shù)值，即可以是正分數(shù)或正小數(shù)。然而在許多經(jīng)濟管理的實際問題中，決策變量只有非負整數(shù)才有實際意義。對求整數(shù)最優(yōu)解的問題，稱為整數(shù)規(guī)劃(IntegerProgramming)(簡記為IP)。IP問題數(shù)學模型的一般形式為：求一組變量x1,x2,…,xn，人們對IP感興趣，還因為有些經(jīng)濟管理中的實際問題的解必須滿足如邏輯條件和順序要求等一些特殊的約束條件。此時需引進邏輯變量（又稱0-1變量），以“0”表示“非”，以“1”表示“是”。凡決策變量均是0-1變量的IP為0-1規(guī)劃。整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃又可分為以下幾類：（1）純整數(shù)規(guī)劃(pureintegerlinearprogramming)或稱為全整數(shù)線性規(guī)劃(allintegerlinearprogramming)：所有的決策變量都為整數(shù)；（2）混合整數(shù)規(guī)劃(mixedintegerlinearprogramming)：僅一部分決策變量為整數(shù)；（3）0-1整數(shù)規(guī)劃：決策變量取值僅限于0或1。本節(jié)最后講到的指派問題就是一個0-1規(guī)劃問題。嚴格地說，IP是個非線性問題。這是因為IP的可行解集是由一些離散的非負整數(shù)所組成，不是一個凸集。迄今為止，求解IP問題尚無統(tǒng)一的有效方法。36整數(shù)規(guī)劃分類例1：某集裝箱運輸公司，箱型標準體積24m3，限制重量13T,現(xiàn)有兩種貨物可以裝運，甲貨物體積5m3、重量2T、每件利潤2000元；乙貨物體積4m3、重量5T、每件利潤1000元，如何裝運獲利最多？

maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13

x1，x2≥0且為整數(shù)

解此LP問題，得：x1=4.8，x2=0

顯然不是可行解整數(shù)規(guī)劃求解——圖解法37整數(shù)規(guī)劃求解——圖解法x1

1

23

4

5

6

7231BAZ=2000x1+1000x25x1+4x2＝242x1+5x2

＝13x238圖解法的啟示A（4.8，0）點是LP問題的可行解，不是IP問題的可行解，B（4，1）才是IP的最優(yōu)解純整數(shù)規(guī)劃的可行解就是可行域中的整數(shù)點非整數(shù)點不是可行解，對于求解沒有意義，故切割掉可行域中的非可行解，不妨礙整數(shù)規(guī)劃問題的優(yōu)化IP問題的最優(yōu)解不優(yōu)于LP問題的最優(yōu)解整數(shù)規(guī)劃求解——圖解法39例1用分枝定界法求解下列問題A：解：先求解相應的線性規(guī)劃為問題B：用圖解法得到最優(yōu)解X＝（3.57,7.14），z0=35.7，如下圖所示。整數(shù)規(guī)劃求解——分枝定界法408.3310最優(yōu)解X=(3.57,7.14),Z0=35.7oABC10x1x2整數(shù)規(guī)劃求解——分枝定界法41

42整數(shù)規(guī)劃求解——分枝定界法8.3310o10x1x234B1B2整數(shù)規(guī)劃求解——分枝定界法4344

整數(shù)規(guī)劃求解——分枝定界法B：X=(3.57,7.14)Z0=35.7B1：X=(3,7.6)Z1=34.8B2：X=(4,6.5)Z2=35.5x1≤3x1≥4B3：X=(4.33,6)Z3=35.33x2≤6B5：X=(4,6)Z5=34B6：X=(5,5)Z6=35x1≤4x1≥5B4：無可行解x2≥7整數(shù)規(guī)劃求解——分枝定界法45460-1型整數(shù)線性規(guī)劃是整數(shù)線性規(guī)劃中的特殊情形，它的變量xi僅取值0或1。這時xi稱為0-1變量，或稱二進制變量。xi僅取值0或1這個條件可由下述約束條件所代替:xi≤1,xi≥0，整數(shù)它和一般整數(shù)線性規(guī)劃的約束條件形式是一致的。在實際問題中，如果引入0-1變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論了。在本節(jié)我們先介紹引入0-1變量的實際問題，再研究解法。0-1型整數(shù)線性規(guī)劃471.水源地的選定——相互排斥的計劃例：某供水公司擬在市東、西、南三區(qū)建立水源地，擬議中有7個位置(點)Ai(i=1，2，…，7)可供選擇。規(guī)定：在東區(qū)，由A1，A2，A3三個點中至多選兩個；在西區(qū)，由A4，A5兩個點中至少選一個；在南區(qū)，由A6，A7兩個點中至少選一個。如選用Ai點，水源地投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問應選擇哪幾個點可使年利潤為最大?引入0-1變量的實際問題48解：先引入0-1變量xi(i=1,2，…，7)

于是問題可列成：引入0-1變量的實際問題492.供水容量擴大問題——相互排斥的約束條件在規(guī)劃期T內(nèi)有，N項水資源工程需要建設，有些水資源工程需要擴大現(xiàn)有規(guī)模，以滿足日益增長的水資源需求。需要決策在滿足需水要求條件下，哪些工程需要擴建能夠使得建設費用最小的方案。假設系統(tǒng)需水量的增長是時間t的函數(shù)D(t)，在規(guī)劃期開始（現(xiàn)時）t=0時的需水量D(0)已得到滿足。令X為規(guī)劃期內(nèi)某時間t已投入使用的工程，其最大供水能力為Z(X)。S為需要擴建的水資源工程（為簡化問題，暫時不考慮工程的建設時間），擴建的供水能力為Z(S)，工程的建設費用是投入使用容量的函數(shù)C(X)。為便于方案的比較，去規(guī)劃期的開始年為標準年（現(xiàn)時）。顯然擴容與否是一個典型的0-1規(guī)劃問題，擴容與不擴容是相互排斥的具體的實例將在介紹完區(qū)間規(guī)劃以后講解引入0-1變量的實際問題503.固定費用的問題在討論線性規(guī)劃時，有些問題是要求使成本為最小。這時，通常設固定成本為常數(shù)，不必在線性規(guī)劃模型中明顯列出。但有些固定費用(固定成本)問題不能用一般線性規(guī)劃來描述，可改變?yōu)榛旌险麛?shù)線性規(guī)劃來解決。例某工廠為生產(chǎn)某種產(chǎn)品，有幾種生產(chǎn)方式供選擇。如選定投資高的生產(chǎn)方式(選購自動化程度高的設備)，由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動成本就降低；反之，如選定投資低的生產(chǎn)方式，分配到每件產(chǎn)品的變動成本可能增加，所以必須全面考慮。今設有三種方式可供選擇，令xj表示采用第j種方式時的產(chǎn)量；cj表示采用第j種方式時每件產(chǎn)品的變動成本；kj表示采用第j種方式時的固定成本。引入0-1變量的實際問題51為了說明成本的特點，暫不考慮其他約束條件。采用各種生產(chǎn)方式的總成本分別為在構(gòu)成目標函數(shù)時，為了統(tǒng)一在一個問題中討論，引入0-1變量yj，令于是，目標函數(shù)為

minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)引入0-1變量的實際問題52求解0-1型整數(shù)線性規(guī)劃最容易想到的方法（和一般整數(shù)線性規(guī)劃的情形一樣），就是窮舉法，即檢查變量取值為0或1的每一種組合，并比較目標函數(shù)值以求得最優(yōu)解。這就需要檢查變量取值的2n個組合。當變量個數(shù)n較大(例如n＞10)時，這幾乎是不可能的。因此，需要設計一些特殊的方法，只需要檢查變量取值組合中的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法(implicitenumeration)。分枝定界法就是一種隱枚舉法。4.20-1型整數(shù)線性規(guī)劃的解法53GeneralMethodtoSolveILP(MILP)applythebasicmethod(simplex/graphical)tosolvetheoriginalmodel;justifytheDV(decisionvariable)ifintegerthenstop,else(non-integer)thenadd[a,a+1]totheconstraints;addthenewconstraintstomothermodel;Goto1→secondarysolution→goto2;afteralltheDVarejustified→stop;compareallthesolutionthatmeettherequirements.ILP解法54Application→fivestepsdeterminetheDV;formulateobjectivefunction;developtheconstraints;non-negativityofDVsolvethemodel.ILP步驟：55多水源供水系統(tǒng)的構(gòu)建是城市給水工程規(guī)劃中一個重要命題,尤其對于水資源缺乏的城市,其是市政規(guī)劃中重要的一環(huán),不僅對于城市的整個供水系統(tǒng)具有決定性作用,對于其他市政規(guī)劃也有較大的影響。多水源供水系統(tǒng)的建立涉及到供水安全性、經(jīng)濟性等多方面內(nèi)容。多水源優(yōu)化配置是指,遵循自然規(guī)律和經(jīng)濟規(guī)律,通過工程和非工程措施,借助于先進的決策理論和計算機技術,干預水資源的時空分配,統(tǒng)一調(diào)配地表水、地下水、再生水、外流域調(diào)水、微咸水和海水等可開發(fā)水源,以合理的費用保質(zhì)保量地適時滿足不同用戶的用水需求?；旌险麛?shù)規(guī)劃多水源供水優(yōu)化模型56

混合整數(shù)規(guī)劃多水源供水優(yōu)化模型

57約束條件1）需水量與供水量平衡約束供水系統(tǒng)的供水量應該與用戶實際需水量一致，具體體現(xiàn)為：用戶需水量小子或等于各水源向各水廠輸送的水量之總和，即：2）各水廠供水能力約束各水源向第j水廠的輸水總量應大于或者等于該水廠的需水量Q需，即：3）水量取值約束基于實際情況，各水廠的處理規(guī)模應大于或等于零，第i水源向第j水廠的輸水量Q