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

第3講

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

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

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

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

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

遞推關(guān)系式(式-1)稱(chēng)為動(dòng)態(tài)規(guī)劃的基本方程。

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

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

簡(jiǎn)言之，一個(gè)最優(yōu)策略的子策略總是最優(yōu)的。動(dòng)態(tài)規(guī)劃的基本方程或者說(shuō)最優(yōu)性定理才是動(dòng)態(tài)規(guī)劃的理論基礎(chǔ)

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

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

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

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

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

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

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

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

≤13

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

解此LP問(wèn)題，得：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）點(diǎn)是LP問(wèn)題的可行解，不是IP問(wèn)題的可行解，B（4，1）才是IP的最優(yōu)解純整數(shù)規(guī)劃的可行解就是可行域中的整數(shù)點(diǎn)非整數(shù)點(diǎn)不是可行解，對(duì)于求解沒(méi)有意義，故切割掉可行域中的非可行解，不妨礙整數(shù)規(guī)劃問(wèn)題的優(yōu)化IP問(wèn)題的最優(yōu)解不優(yōu)于LP問(wèn)題的最優(yōu)解整數(shù)規(guī)劃求解——圖解法39例1用分枝定界法求解下列問(wèn)題A：解：先求解相應(yīng)的線(xiàn)性規(guī)劃為問(wèn)題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：無(wú)可行解x2≥7整數(shù)規(guī)劃求解——分枝定界法45460-1型整數(shù)線(xiàn)性規(guī)劃是整數(shù)線(xiàn)性規(guī)劃中的特殊情形，它的變量xi僅取值0或1。這時(shí)xi稱(chēng)為0-1變量，或稱(chēng)二進(jìn)制變量。xi僅取值0或1這個(gè)條件可由下述約束條件所代替:xi≤1,xi≥0，整數(shù)它和一般整數(shù)線(xiàn)性規(guī)劃的約束條件形式是一致的。在實(shí)際問(wèn)題中，如果引入0-1變量，就可以把有各種情況需要分別討論的線(xiàn)性規(guī)劃問(wèn)題統(tǒng)一在一個(gè)問(wèn)題中討論了。在本節(jié)我們先介紹引入0-1變量的實(shí)際問(wèn)題，再研究解法。0-1型整數(shù)線(xiàn)性規(guī)劃471.水源地的選定——相互排斥的計(jì)劃例：某供水公司擬在市東、西、南三區(qū)建立水源地，擬議中有7個(gè)位置(點(diǎn))Ai(i=1，2，…，7)可供選擇。規(guī)定：在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。如選用Ai點(diǎn)，水源地投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過(guò)B元。問(wèn)應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大?引入0-1變量的實(shí)際問(wèn)題48解：先引入0-1變量xi(i=1,2，…，7)

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

minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)引入0-1變量的實(shí)際問(wèn)題52求解0-1型整數(shù)線(xiàn)性規(guī)劃最容易想到的方法（和一般整數(shù)線(xiàn)性規(guī)劃的情形一樣），就是窮舉法，即檢查變量取值為0或1的每一種組合，并比較目標(biāo)函數(shù)值以求得最優(yōu)解。這就需要檢查變量取值的2n個(gè)組合。當(dāng)變量個(gè)數(shù)n較大(例如n＞10)時(shí)，這幾乎是不可能的。因此，需要設(shè)計(jì)一些特殊的方法，只需要檢查變量取值組合中的一部分，就能求到問(wèn)題的最優(yōu)解。這樣的方法稱(chēng)為隱枚舉法(implicitenumeration)。分枝定界法就是一種隱枚舉法。4.20-1型整數(shù)線(xiàn)性規(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ī)劃中一個(gè)重要命題,尤其對(duì)于水資源缺乏的城市,其是市政規(guī)劃中重要的一環(huán),不僅對(duì)于城市的整個(gè)供水系統(tǒng)具有決定性作用,對(duì)于其他市政規(guī)劃也有較大的影響。多水源供水系統(tǒng)的建立涉及到供水安全性、經(jīng)濟(jì)性等多方面內(nèi)容。多水源優(yōu)化配置是指,遵循自然規(guī)律和經(jīng)濟(jì)規(guī)律,通過(guò)工程和非工程措施,借助于先進(jìn)的決策理論和計(jì)算機(jī)技術(shù),干預(yù)水資源的時(shí)空分配,統(tǒng)一調(diào)配地表水、地下水、再生水、外流域調(diào)水、微咸水和海水等可開(kāi)發(fā)水源,以合理的費(fèi)用保質(zhì)保量地適時(shí)滿(mǎn)足不同用戶(hù)的用水需求。混合整數(shù)規(guī)劃多水源供水優(yōu)化模型56

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

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