百度關(guān)鍵詞怎么做排名愛站工具seo綜合查詢
整數(shù)規(guī)劃——第一章 引言
整數(shù)規(guī)劃是帶整數(shù)變量的最優(yōu)化問題，即最大化或最小化一個全部或部分變量為整數(shù)的多元函數(shù)受約束于一組等式和不等式條件的最優(yōu)化問題。許多經(jīng)濟(jì)、管理、交通、通信和工程中的最優(yōu)化問題都可以用整數(shù)規(guī)劃來建模。
考慮一個電視機(jī)工廠的生產(chǎn)計劃問題，如果線性規(guī)劃模型給出的最優(yōu)生產(chǎn)計劃是每天生產(chǎn)102。4臺，則可以選擇每天102或103臺的生產(chǎn)計劃。另一方面，若考慮的問題是倉庫的選址問題，設(shè)線性規(guī)劃給出的最優(yōu)解是在甲地點建或買0。6個倉庫，在乙地點建或買0。4個倉庫，因倉庫的個數(shù)必須是整數(shù)，這時線性規(guī)劃的解不能提供任何有用的決策方案。實際上，除了可以描述決策變量的離散性外，整數(shù)變量可以幫助我們刻畫最優(yōu)化建模中的許多約束條件，如邏輯關(guān)系、固定費用、可選變量的上界、順序和排序關(guān)系、分片線性函數(shù)等。
整數(shù)規(guī)劃的歷史可以追溯到20世紀(jì)50年代，運籌學(xué)創(chuàng)始人和線性規(guī)劃單純形算法發(fā)明者Dantzig首先發(fā)現(xiàn)可以用0-1變量來刻畫最優(yōu)化模型中的固定費用、變量上界、非凸分片線性函數(shù)等。他和Fulkerson及Johnson對旅行售貨員問題(TSP)的研究成為后來的分枝割方法和現(xiàn)代混合整數(shù)規(guī)劃算法的開端。1958年，Gomory發(fā)現(xiàn)了第一個一般線性整數(shù)規(guī)劃的收斂算法——割平面方法。隨著整數(shù)規(guī)劃理論和算法的發(fā)展，整數(shù)規(guī)劃已成為應(yīng)用最廣泛的最優(yōu)化方法之一，特別是近年來整數(shù)規(guī)劃算法技術(shù)和軟件系統(tǒng)（如CPLEX)的發(fā)展和推廣，整數(shù)規(guī)劃在生產(chǎn)企業(yè)、服務(wù)、運營管理、交通、通信等領(lǐng)域得到了極大的應(yīng)用和發(fā)展。
1.1 分類與建模
1.1.1 線性混合整數(shù)規(guī)劃
線性混合整數(shù)規(guī)劃（Mixed integer program/programming，MIP）的一般形式為：
( MIP ) min ? c T x + h T y , s . t . A x + G y ≤ b , x ∈ Z + n , y ∈ R + p , \begin{aligned} (\text{MIP})\quad\quad& \min \ c^T x+h^Ty,\\\ & s.t.\quad Ax+Gy\le b,\ x\in \Z^n_+,y\in \R^p_+, \end{aligned} (MIP)??min?cTx+hTy,s.t.Ax+Gy≤b,?x∈Z+n?,y∈R+p?,?
其中 Z + n \Z^n_+ Z+n? 是 n n n 維非負(fù)整數(shù)向量集合， R + p \R^p_+ R+p? 是 p p p 維非負(fù)實數(shù)向量集合。
如果問題（MIP）中沒有連續(xù)決策變量，則（MIP）就是一個（純）線性整數(shù)規(guī)劃：
( IP ) min ? c T x , s . t . A x ≤ b , x ∈ Z + n , \begin{aligned} (\text{IP})\quad\quad& \min \ c^T x,\\\ & s.t.\quad Ax\le b,\ x\in \Z^n_+, \end{aligned} (IP)??min?cTx,s.t.Ax≤b,?x∈Z+n?,?
背包問題 設(shè)有一個背包，其承重為 b b b ?？紤]n件物品，其中第 j j j 件的重量為 α j α_j αj? ，價值為 c j c_j cj?。問如何選取物品裝入背包，使背包內(nèi)物品的總價值最大？
設(shè)
x j = { 1 , 若選取第 j 件物品， 0 , 若不選取 . x_j=\begin{cases} 1,&若選取第j件物品，\\ 0,&若不選取. \end{cases} xj?={1,0,?若選取第j件物品，若不選取.?
則背包問題可以表示為下列線性0-1規(guī)劃：
max ? ∑ j = 1 n c j x j , s . t . ∑ j = 1 n a j x j ≤ b , x ∈ { 0 , 1 } n . \begin{aligned}&\max \sum_{j=1}^n c_jx_j,\\ &s.t.\ \sum_{j=1}^n a_jx_j\le b,\\ &\quad\quad x\in \{0,1\}^n. \end{aligned} ?maxj=1∑n?cj?xj?,s.t.?j=1∑n?aj?xj?≤b,x∈{0,1}n.?
指派問題 設(shè)有 m m m 臺機(jī)器， n n n 個工件，第 i i i 臺機(jī)器的可用工時數(shù)為 b i b_i bi? ，第 i i i 臺機(jī)器完成第 j j j 件工件需要的工時數(shù)為 a i j a_{ij} aij? ，費用為 c i j c_{ij} cij? 。問如何最優(yōu)指派機(jī)器生產(chǎn)。
設(shè)
x i j = { 1 , 若第? i 個機(jī)器加工第? j 件工件， 0 , 其他 . x_{ij}=\begin{cases} 1,&若第\ i\ 個機(jī)器加工第\ j\ 件工件，\\ 0,&其他. \end{cases} xij?={1,0,?若第?i?個機(jī)器加工第?j?件工件，其他.?
則指派問題可以表示為如下0-1規(guī)劃問題：
min ? ∑ i = 1 n ∑ j = 1 n c i j x i j , s . t . ∑ j = 1 n a i j x i j ≤ b i , i = 1 , . . . , m , ∑ i = 1 m x i j = 1 , j = 1 , . . . , n , x ∈ { 0 , 1 } n . \begin{aligned}&\min \sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij},\\ &s.t.\ \sum_{j=1}^n a_{ij}x_{ij}\le b_i,\ i = 1,...,m,\\ &\quad\quad\sum_{i = 1}^m x_{ij} =1,j=1,...,n, \\ &\quad\quad x\in \{0,1\}^n. \end{aligned} ?mini=1∑n?j=1∑n?cij?xij?,s.t.?j=1∑n?aij?xij?≤bi?,?i=1,...,m,i=1∑m?xij?=1,j=1,...,n,x∈{0,1}n.?
集合覆蓋問題 設(shè)某地區(qū)劃分為若干個區(qū)域，需要建立若干個應(yīng)急服務(wù)中心（如消防站、急救中心等），每個中心的建立都需要一筆建站費用，設(shè)候選中心的位置已知，每個中心可以服務(wù)的區(qū)域預(yù)先知道，問如何選取中心使該應(yīng)急服務(wù)能覆蓋整個地區(qū)且使建站費用最小。
記 M = { 1 , ? ? ? , m } M=\{1,···,m\} M={1,???,m} 為該地區(qū)中的區(qū)域， N = { 1 , ? ? ? , n } N=\{1,···,n\} N={1,???,n} 是可選的中心，設(shè) S ≤ M S≤M S≤M 為中心 j ∈ N j∈N j∈N 可以服務(wù)的區(qū)域集合， c j c_j cj? 是中心 j j j 的建站費用，定義0-1關(guān)聯(lián)矩陣 A = ( a i j ) A=(a_{ij}) A=(aij?) ，其中如果 i ∈ S j i∈S_j i∈Sj?， a i j = 1 a_{ij}=1 aij?=1 ，否則 a i j = 0 a_{ij}=0 aij?=0 。
設(shè)
x j = { 1 , 若選取中心 j ， 0 , 其他 . x_j=\begin{cases} 1,&若選取中心j，\\ 0,&其他. \end{cases} xj?={1,0,?若選取中心j，其他.?
則問題可以表述為：
min ? ∑ j = 1 n c j x j , s . t . ∑ j = 1 n a i j x j ≥ 1 , i = 1 , . . . , m , x ∈ { 0 , 1 } n . \begin{aligned}&\min \sum_{j=1}^n c_jx_j,\\ &s.t.\ \sum_{j=1}^n a_{ij}x_j\ge 1,i=1,...,m,\\ &\quad\quad x\in \{0,1\}^n. \end{aligned} ?minj=1∑n?cj?xj?,s.t.?j=1∑n?aij?xj?≥1,i=1,...,m,x∈{0,1}n.?
旅行售貨員問題（TSP） 設(shè)有一個旅行售貨員需要去n個城市推銷他的產(chǎn)品，他必須而且只能訪問每個城市一次，并最后返回出發(fā)城市.設(shè)每個城市直接到達(dá)另一個城市的距離已知（如不能直接到達(dá)，則可設(shè)其距離為+∞），他應(yīng)該如何選擇旅行路線使得總的旅行距離最短？
設(shè)城市 i i i 到城市 j j j 的距離為 c i j c_{ij} cij?，設(shè)
x i j = { 1 , 若他的旅游路線包括了直接從城市 i 到城市 j 的行程， 0 , 其他 . x_{ij}=\begin{cases} 1,&若他的旅游路線包括了直接從城市 i 到城市 j的行程，\\ 0,&其他. \end{cases} xij?={1,0,?若他的旅游路線包括了直接從城市i到城市j的行程，其他.?
約束條件：
離開城市 i i i 一次：
∑ j =? i x i j = 1 , i = 1 , . . . , n \sum_{j\not= i}x_{ij}=1,\ i=1,...,n j=i∑?xij?=1,?i=1,...,n
到達(dá)城市 j j j 一次：
∑ i =? j x i j = 1 , j = 1 , . . . , n \sum_{i\not= j}x_{ij}=1,\ j=1,...,n i=j∑?xij?=1,?j=1,...,n
上面的約束條件使得每個城市正好經(jīng)過一次，但仍可能包括含圈但不聯(lián)通的路
線，我們需要用下面的約束條件來去除這種情況發(fā)生：∑ i ∈ S ∑ j ∈? S x i j ≥ 1 , ? S ? N = { 1 , . . . , n } , S =? ? \sum_{i\in S}\sum_{j\not\in S}x_{ij}\ge 1,\quad \forall S\sub N=\{1,...,n\},S\not =\emptyset i∈S∑?j∈S∑?xij?≥1,?S?N={1,...,n},S=?
或者
∑ i ∈ S ∑ j ∈ S x i j ≤ ∣ S ∣ ? 1 , ? S ? N , 2 ≤ ∣ S ∣ ≤ n ? 1 \sum_{i\in S}\sum_{j\in S} x_{ij}\le |S|-1,\quad \forall S\sub N,\quad 2\le|S|\le n-1 i∈S∑?j∈S∑?xij?≤∣S∣?1,?S?N,2≤∣S∣≤n?1
從而旅行售貨員問題可以表示為：
min ? ∑ i = 1 n ∑ j = 1 n c i j x i j , s . t . ∑ j =? i x i j = 1 , i = 1 , . . . , n , ∑ i =? j m x i j = 1 , j = 1 , . . . , n , ∑ i ∈ S ∑ j ∈ S x i j ≤ ∣ S ∣ ? 1 , ? S ? N , 2 ≤ ∣ S ∣ ≤ n ? 1 , x ∈ { 0 , 1 } n . \begin{aligned}&\min \sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij},\\ &s.t.\ \sum_{j\not=i} x_{ij}=1,\ i = 1,...,n,\\ &\quad\quad\sum_{i \not= j}^m x_{ij} =1,j=1,...,n, \\ &\quad\quad\sum_{i\in S}\sum_{j\in S} x_{ij}\le |S|-1,\quad \forall S\sub N,\quad 2\le|S|\le n-1,\\ &\quad\quad x\in \{0,1\}^n. \end{aligned} ?mini=1∑n?j=1∑n?cij?xij?,s.t.?j=i∑?xij?=1,?i=1,...,n,i=j∑m?xij?=1,j=1,...,n,i∈S∑?j∈S∑?xij?≤∣S∣?1,?S?N,2≤∣S∣≤n?1,x∈{0,1}n.?
1.1.2 非線性整數(shù)規(guī)劃
一般非線性混合整數(shù)規(guī)劃(Mixed-Integer Nonlinear Programming)問題可表示為;
( MINLP ) min ? f ( x , y ) , s . t . g i ( x , y ) ≤ b i , i = 1 , . . . , m , x ∈ X , y ∈ Y \begin{aligned} (\text{MINLP})\quad\quad& \min f(x,y),\\\ & s.t.\quad g_i(x,y)\le b_i,\quad i =1,...,m,\\ &\quad\quad\ \ \ x \in X,\quad y\in Y \end{aligned} (MINLP)??minf(x,y),s.t.gi?(x,y)≤bi?,i=1,...,m,???x∈X,y∈Y?
此處的 f , g i , i = 1 , . . . , m f,g_i,i=1,...,m f,gi?,i=1,...,m 是 R n + q \R^{n+q} Rn+q 上的實值函數(shù)， X X X 是 Z n \Z^n Zn 的子集， Y Y Y 是 R q \R^q Rq 的子集。
當(dāng)（MINLP）中沒有連續(xù)變量 y y y 時，（MINLP）即是一個（純）非線性整數(shù)規(guī)劃：
( NLIP ) min ? f ( x , y ) , s . t . g i ( x , y ) ≤ b i , i = 1 , . . . , m , x ∈ X , y ∈ Y \begin{aligned} (\text{NLIP})\quad\quad& \min f(x,y),\\\ & s.t.\quad g_i(x,y)\le b_i,\quad i =1,...,m,\\ &\quad\quad\ \ \ x \in X,\quad y\in Y \end{aligned} (NLIP)??minf(x,y),s.t.gi?(x,y)≤bi?,i=1,...,m,???x∈X,y∈Y?
最大割問題 設(shè) G = ( V , E ) G=(V,E) G=(V,E) 是有 n n n 個頂點的無向圖，設(shè)邊 ( i , j ) (i,j) (i,j) 上的權(quán)為 w i j ( w i j = w j i ≥ 0 ) w_{ij}(w_{ij}=w_{ji}\ge 0) wij?(wij?=wji?≥0)。圖 G G G 的一個割 ( S , S ′ ) (S,S') (S,S′) 是指 n n n 個頂點上的一個分割： S ∩ S ′ = ? , S ∪ S ′ = V S\cap S'=\empty,S\cup S'=V S∩S′=?,S∪S′=V。最大割問題是求一個分割 ( S , S ′ ) (S,S') (S,S′) 使連接 S S S 和 S ′ S' S′ 之間的所有邊上的權(quán)最大。
設(shè) $x_i = 1\ \text{if} \ \ i\in S,\ x_i = -1 \ \text{if} \ \ i\in S’ $，則分割 ( S , S ′ ) (S,S') (S,S′) 上的權(quán)為：
1 2 ( 1 2 ∑ i , j = 1 n w i j ? 1 2 ∑ i , j = 1 n w i j x i x j ) = 1 4 ∑ i , j = 1 n w i j ( 1 ? x i x j ) . \frac{1}{2}(\frac{1}{2}\sum_{i,j=1}^n w_{ij}-\frac{1}{2}\sum_{i,j=1}^n w_{ij} x_ix_j)=\frac{1}{4}\sum_{i,j=1}^n w_{ij}(1-x_ix_j). 21?(21?i,j=1∑n?wij??21?i,j=1∑n?wij?xi?xj?)=41?i,j=1∑n?wij?(1?xi?xj?).
所以最大割問題可以表示為：
max ? 1 4 ∑ i , j = 1 n w i j ( 1 ? x i x j ) , s . t . x ∈ { ? 1 , 1 } n . \begin{aligned} &\max\ \frac{1}{4}\sum_{i,j=1}^n w_{ij}(1-x_ix_j),\\ & s.t.\ x\in \{-1,1\}^n. \end{aligned} ?max?41?i,j=1∑n?wij?(1?xi?xj?),s.t.?x∈{?1,1}n.?
最大割問題是組合優(yōu)化中著名的NP難問題，l995年，Goemans和Williamson對
最大割問題的SDP松弛給出了一個漂亮的結(jié)果：
f o p t ≤ f S D P ≤ α f o p t , α = 1.138 ? ? ? , f_{opt}≤f_{SDP}≤\alpha f_{opt},\alpha=1.138···, fopt?≤fSDP?≤αfopt?,α=1.138???,
這里 f o p t f_{opt} fopt? 是最大割問題的最優(yōu)值， f S D P f_{SDP} fSDP?是SDP松弛問題的最優(yōu)值
可靠性網(wǎng)絡(luò) 考慮有 n n n 個子系統(tǒng)的網(wǎng)絡(luò).設(shè) r i ( 0 < r i < 1 ) r_i(0<r_i<1) ri?(0<ri?<1) 是第 i i i 個子系統(tǒng)中的部件可靠性， x i x_i xi? 表示第 i i i 個子系統(tǒng)的冗余部件的個數(shù)。網(wǎng)絡(luò)可靠性優(yōu)化問題是求最優(yōu)的冗余向量 x = ( x 1 , ? ? ? , x n ) T x=(x_1,···,x_n)^T x=(x1?,???,xn?)T 使網(wǎng)絡(luò)的整體可靠性最大。
第 i i i 個子系統(tǒng)的可靠性為
R i ( x i ) = 1 ? ( 1 ? r i ) x i , i = 1 , . . . , n R_i(x_i)=1-(1-r_i)^{x_i},\ i=1,...,n Ri?(xi?)=1?(1?ri?)xi?,?i=1,...,n
整個網(wǎng)絡(luò)的可靠性 R s ( x ) R_s(x) Rs?(x) 是關(guān)于 R 1 ( x 1 ) , . . . , R n ( x n ) R_1(x_1),...,R_n(x_n) R1?(x1?),...,Rn?(xn?) 的增函數(shù)，下圖所示的網(wǎng)絡(luò)的可靠性為
R s = R 6 R 7 + R 1 R 2 R 3 ( Q 6 + R 6 Q 7 ) + R 1 R 4 R 7 Q 6 ( Q 2 + R 2 Q 3 ) R_s = R_6R_7+R_1R_2R_3(Q_6+R_6Q_7)+R_1R_4R_7Q_6(Q_2+R_2Q_3) Rs?=R6?R7?+R1?R2?R3?(Q6?+R6?Q7?)+R1?R4?R7?Q6?(Q2?+R2?Q3?)
其中 Q i = 1 ? R i ， i = 1 , . . . , n Q_i = 1-R_i，i=1,...,n Qi?=1?Ri?，i=1,...,n，對應(yīng)的最優(yōu)冗余問題為：max ? R s ( x ) = f ( R 1 ( x 1 ) , . . . , R n ( x n ) ) , s . t . g i ( x ) = ∑ j = 1 n g i j ( x j ) ≤ b i , i = 1 , . . . , m , x ∈ X = { x ∈ Z n ∣ 1 ≤ l j ≤ x j ≤ u j , j = 1 , . . . , n } \begin{aligned} &\max\ R_s(x)=f(R_1(x_1),...,R_n(x_n)),\\ & s.t.\ g_i(x)=\sum_{j=1}^ng_{ij}(x_j)\le b_i,\quad i=1,...,m,\\ &\quad\quad x\in X=\{x\in \Z^n|1\le l_j\le x_j\le u_j,j=1,...,n\} \end{aligned} ?max?Rs?(x)=f(R1?(x1?),...,Rn?(xn?)),s.t.?gi?(x)=j=1∑n?gij?(xj?)≤bi?,i=1,...,m,x∈X={x∈Zn∣1≤lj?≤xj?≤uj?,j=1,...,n}?
其中 g i ( x ) , i = 1 , . . . , m g_i(x),i=1,...,m gi?(x),i=1,...,m 代表不同的資源消耗函數(shù)，例如費用、體積、重量等。
1.2 問題的挑戰(zhàn)性
很多整數(shù)規(guī)劃問題往往看上去很簡單，數(shù)學(xué)模型也不復(fù)雜，如0-1背包問題、最大割問題等，但求解這類問題其實非常困難.絕大部分整數(shù)規(guī)劃問題的可行域都只有有限多個可行點（決策方案），一個簡單幼稚的想法是枚舉所有的可行點，但是這樣會使求解難度指數(shù)增加。大部分整數(shù)規(guī)劃問題的困難在于：我們本質(zhì)上只能使用枚舉法或隱枚舉法的思想來求解問題最優(yōu)解，故當(dāng)問題的規(guī)模越來越大時，算法的計算時間急劇增加。與此形成對照的是連續(xù)優(yōu)化問題，我們知道，最簡單的連續(xù)優(yōu)化問題的可行點的個數(shù)也是無窮多個，但尋找可行域中的最優(yōu)點并不需要借助枚舉法的思想，因為利用微積分的工具可以刻畫出最優(yōu)點需要滿足的一組容易驗證的最優(yōu)性條件，如KKT條件。故只有當(dāng)算法需要枚舉或部分枚舉這些可行點時，可行域中可行點的個數(shù)才和問題的難度有關(guān)。
另外一個樸素的想法是“四舍五入”：求解相應(yīng)的連續(xù)優(yōu)化問題（丟掉整數(shù)約束)，然后對求得的解進(jìn)行四舍五入，得到一個整數(shù)解.這個方法有兩個問題：(1)一般很難通過四舍五入得到一個滿足約束條件的可行解；(2)即使能求得一個可行解，其質(zhì)量往往很差，即可能離最優(yōu)解的距離很遠(yuǎn)，甚至和隨機(jī)產(chǎn)生的可行解差不多。貪心算法往往可以幫助我們求到一個問題的近似解。例如，在0-1背包問題中，可以先進(jìn)行排序：
c j 1 a j 1 ≥ c j 2 a j 2 ≥ . . . ≥ c j n a j n \frac{c_{j1}}{a_{j1}}\ge\frac{c_{j2}}{a_{j2}}\ge ... \ge\frac{c_{jn}}{a_{jn}} aj1?cj1??≥aj2?cj2??≥...≥ajn?cjn??
然后按照從大到小的順序 j 1 , . . . , j n j_1,...,j_n j1?,...,jn? 選取物品知道背包的容量 b b b 不能再裝下一個物品。
在實際應(yīng)用中提出的很多整數(shù)規(guī)劃問題的規(guī)模一般都很大，直接利用現(xiàn)有的算法和軟件求解往往是不可能的.這就促使人們研究有效快速的近似算法或啟發(fā)式算法以尋找問題的一個近似最優(yōu)解或較好的可行解，如近年來發(fā)展起來的基于半定規(guī)劃的隨機(jī)化算法和各種針對具體整數(shù)規(guī)劃和組合優(yōu)化問題的近似算法。
參考資料
- 整數(shù)規(guī)劃 孫小玲，李瑞 北京，科學(xué)出版社 2010
- Wolsey L A. Integer programming[M]. John Wiley & Sons, 2020.