安徽省建设厅网站官网,房地产新闻发布会,湖北省住房建设厅网站,网站开发与维护是做什么工作整数规划——第一章 引言
整数规划是带整数变量的最优化问题#xff0c;即最大化或最小化一个全部或部分变量为整数的多元函数受约束于一组等式和不等式条件的最优化问题。许多经济、管理、交通、通信和工程中的最优化问题都可以用整数规划来建模。
考虑一个电视机工厂的生产…整数规划——第一章 引言
整数规划是带整数变量的最优化问题即最大化或最小化一个全部或部分变量为整数的多元函数受约束于一组等式和不等式条件的最优化问题。许多经济、管理、交通、通信和工程中的最优化问题都可以用整数规划来建模。
考虑一个电视机工厂的生产计划问题如果线性规划模型给出的最优生产计划是每天生产102。4台则可以选择每天102或103台的生产计划。另一方面若考虑的问题是仓库的选址问题设线性规划给出的最优解是在甲地点建或买0。6个仓库在乙地点建或买0。4个仓库因仓库的个数必须是整数这时线性规划的解不能提供任何有用的决策方案。实际上除了可以描述决策变量的离散性外整数变量可以帮助我们刻画最优化建模中的许多约束条件如逻辑关系、固定费用、可选变量的上界、顺序和排序关系、分片线性函数等。
整数规划的历史可以追溯到20世纪50年代运筹学创始人和线性规划单纯形算法发明者Dantzig首先发现可以用0-1变量来刻画最优化模型中的固定费用、变量上界、非凸分片线性函数等。他和Fulkerson及Johnson对旅行售货员问题(TSP)的研究成为后来的分枝割方法和现代混合整数规划算法的开端。1958年Gomory发现了第一个一般线性整数规划的收敛算法——割平面方法。随着整数规划理论和算法的发展整数规划已成为应用最广泛的最优化方法之一特别是近年来整数规划算法技术和软件系统如CPLEX)的发展和推广整数规划在生产企业、服务、运营管理、交通、通信等领域得到了极大的应用和发展。
1.1 分类与建模
1.1.1 线性混合整数规划
线性混合整数规划Mixed integer program/programmingMIP的一般形式为 ( 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 xh^Ty,\\\ s.t.\quad AxGy\le b,\ x\in \Z^n_,y\in \R^p_, \end{aligned} (MIP) min cTxhTy,s.t.AxGy≤b, x∈Zn,y∈Rp,
其中 Z n \Z^n_ Zn 是 n n n 维非负整数向量集合 R p \R^p_ Rp 是 p p p 维非负实数向量集合。
如果问题MIP中没有连续决策变量则MIP就是一个纯线性整数规划 ( 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∈Zn, 背包问题 设有一个背包其承重为 b b b 。考虑n件物品其中第 j j j 件的重量为 α j α_j αj 价值为 c j c_j cj。问如何选取物品装入背包使背包内物品的总价值最大 设 x j { 1 , 若选取第 j 件物品 0 , 若不选取 . x_j\begin{cases} 1,若选取第j件物品\\ 0,若不选取. \end{cases} xj{1,0,若选取第j件物品若不选取. 则背包问题可以表示为下列线性0-1规划 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_{j1}^n c_jx_j,\\ s.t.\ \sum_{j1}^n a_jx_j\le b,\\ \quad\quad x\in \{0,1\}^n. \end{aligned} maxj1∑ncjxj,s.t. j1∑najxj≤b,x∈{0,1}n. 指派问题 设有 m m m 台机器 n n n 个工件第 i i i 台机器的可用工时数为 b i b_i bi 第 i i i 台机器完成第 j j j 件工件需要的工时数为 a i j a_{ij} aij 费用为 c i j c_{ij} cij 。问如何最优指派机器生产。 设 x i j { 1 , 若第 i 个机器加工第 j 件工件 0 , 其他 . x_{ij}\begin{cases} 1,若第\ i\ 个机器加工第\ j\ 件工件\\ 0,其他. \end{cases} xij{1,0,若第 i 个机器加工第 j 件工件其他. 则指派问题可以表示为如下0-1规划问题 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_{i1}^n\sum_{j1}^n c_{ij}x_{ij},\\ s.t.\ \sum_{j1}^n a_{ij}x_{ij}\le b_i,\ i 1,...,m,\\ \quad\quad\sum_{i 1}^m x_{ij} 1,j1,...,n, \\ \quad\quad x\in \{0,1\}^n. \end{aligned} mini1∑nj1∑ncijxij,s.t. j1∑naijxij≤bi, i1,...,m,i1∑mxij1,j1,...,n,x∈{0,1}n. 集合覆盖问题 设某地区划分为若干个区域需要建立若干个应急服务中心如消防站、急救中心等每个中心的建立都需要一笔建站费用设候选中心的位置已知每个中心可以服务的区域预先知道问如何选取中心使该应急服务能覆盖整个地区且使建站费用最小。 记 M { 1 , ⋅ ⋅ ⋅ , m } M\{1,···,m\} M{1,⋅⋅⋅,m} 为该地区中的区域 N { 1 , ⋅ ⋅ ⋅ , n } N\{1,···,n\} N{1,⋅⋅⋅,n} 是可选的中心设 S ≤ M S≤M S≤M 为中心 j ∈ N j∈N j∈N 可以服务的区域集合 c j c_j cj 是中心 j j j 的建站费用定义0-1关联矩阵 A ( a i j ) A(a_{ij}) A(aij) 其中如果 i ∈ S j i∈S_j i∈Sj a i j 1 a_{ij}1 aij1 否则 a i j 0 a_{ij}0 aij0 。 设 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_{j1}^n c_jx_j,\\ s.t.\ \sum_{j1}^n a_{ij}x_j\ge 1,i1,...,m,\\ \quad\quad x\in \{0,1\}^n. \end{aligned} minj1∑ncjxj,s.t. j1∑naijxj≥1,i1,...,m,x∈{0,1}n. 旅行售货员问题TSP 设有一个旅行售货员需要去n个城市推销他的产品他必须而且只能访问每个城市一次并最后返回出发城市.设每个城市直接到达另一个城市的距离已知如不能直接到达则可设其距离为∞他应该如何选择旅行路线使得总的旅行距离最短 设城市 i i i 到城市 j j j 的距离为 c i j c_{ij} cij设 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,\ i1,...,n ji∑xij1, i1,...,n 到达城市 j j j 一次 ∑ i ̸ j x i j 1 , j 1 , . . . , n \sum_{i\not j}x_{ij}1,\ j1,...,n ij∑xij1, j1,...,n 上面的约束条件使得每个城市正好经过一次但仍可能包括含圈但不联通的路 线我们需要用下面的约束条件来去除这种情况发生 ∑ 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_{i1}^n\sum_{j1}^n c_{ij}x_{ij},\\ s.t.\ \sum_{j\noti} x_{ij}1,\ i 1,...,n,\\ \quad\quad\sum_{i \not j}^m x_{ij} 1,j1,...,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} mini1∑nj1∑ncijxij,s.t. ji∑xij1, i1,...,n,ij∑mxij1,j1,...,n,i∈S∑j∈S∑xij≤∣S∣−1,∀S⊂N,2≤∣S∣≤n−1,x∈{0,1}n. 1.1.2 非线性整数规划
一般非线性混合整数规划(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,i1,...,m, x∈X,y∈Y
此处的 f , g i , i 1 , . . . , m f,g_i,i1,...,m f,gi,i1,...,m 是 R n q \R^{nq} Rnq 上的实值函数 X X X 是 Z n \Z^n Zn 的子集 Y Y Y 是 R q \R^q Rq 的子集。
当MINLP中没有连续变量 y y y 时MINLP即是一个纯非线性整数规划 ( 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,i1,...,m, x∈X,y∈Y 最大割问题 设 G ( V , E ) G(V,E) G(V,E) 是有 n n n 个顶点的无向图设边 ( i , j ) (i,j) (i,j) 上的权为 w i j ( w i j w j i ≥ 0 ) w_{ij}(w_{ij}w_{ji}\ge 0) wij(wijwji≥0)。图 G G G 的一个割 ( S , S ′ ) (S,S) (S,S′) 是指 n n n 个顶点上的一个分割 S ∩ S ′ ∅ , S ∪ S ′ V S\cap S\empty,S\cup SV S∩S′∅,S∪S′V。最大割问题是求一个分割 ( S , S ′ ) (S,S) (S,S′) 使连接 S S S 和 S ′ S S′ 之间的所有边上的权最大。 设 $x_i 1\ \text{if} \ \ i\in S,\ x_i -1 \ \text{if} \ \ i\in S’ $则分割 ( S , S ′ ) (S,S) (S,S′) 上的权为 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,j1}^n w_{ij}-\frac{1}{2}\sum_{i,j1}^n w_{ij} x_ix_j)\frac{1}{4}\sum_{i,j1}^n w_{ij}(1-x_ix_j). 21(21i,j1∑nwij−21i,j1∑nwijxixj)41i,j1∑nwij(1−xixj). 所以最大割问题可以表示为 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,j1}^n w_{ij}(1-x_ix_j),\\ s.t.\ x\in \{-1,1\}^n. \end{aligned} max 41i,j1∑nwij(1−xixj),s.t. x∈{−1,1}n. 最大割问题是组合优化中著名的NP难问题l995年Goemans和Williamson对 最大割问题的SDP松弛给出了一个漂亮的结果 f o p t ≤ f S D P ≤ α f o p t , α 1.138 ⋅ ⋅ ⋅ , f_{opt}≤f_{SDP}≤\alpha f_{opt},\alpha1.138···, fopt≤fSDP≤αfopt,α1.138⋅⋅⋅, 这里 f o p t f_{opt} fopt 是最大割问题的最优值 f S D P f_{SDP} fSDP是SDP松弛问题的最优值 可靠性网络 考虑有 n n n 个子系统的网络.设 r i ( 0 r i 1 ) r_i(0r_i1) ri(0ri1) 是第 i i i 个子系统中的部件可靠性 x i x_i xi 表示第 i i i 个子系统的冗余部件的个数。网络可靠性优化问题是求最优的冗余向量 x ( x 1 , ⋅ ⋅ ⋅ , x n ) T x(x_1,···,x_n)^T x(x1,⋅⋅⋅,xn)T 使网络的整体可靠性最大。 第 i i i 个子系统的可靠性为 R i ( x i ) 1 − ( 1 − r i ) x i , i 1 , . . . , n R_i(x_i)1-(1-r_i)^{x_i},\ i1,...,n Ri(xi)1−(1−ri)xi, i1,...,n 整个网络的可靠性 R s ( x ) R_s(x) Rs(x) 是关于 R 1 ( x 1 ) , . . . , R n ( x n ) R_1(x_1),...,R_n(x_n) R1(x1),...,Rn(xn) 的增函数下图所示的网络的可靠性为 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_7R_1R_2R_3(Q_6R_6Q_7)R_1R_4R_7Q_6(Q_2R_2Q_3) RsR6R7R1R2R3(Q6R6Q7)R1R4R7Q6(Q2R2Q3) 其中 Q i 1 − R i i 1 , . . . , n Q_i 1-R_ii1,...,n Qi1−Rii1,...,n对应的最优冗余问题为 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_{j1}^ng_{ij}(x_j)\le b_i,\quad i1,...,m,\\ \quad\quad x\in X\{x\in \Z^n|1\le l_j\le x_j\le u_j,j1,...,n\} \end{aligned} max Rs(x)f(R1(x1),...,Rn(xn)),s.t. gi(x)j1∑ngij(xj)≤bi,i1,...,m,x∈X{x∈Zn∣1≤lj≤xj≤uj,j1,...,n} 其中 g i ( x ) , i 1 , . . . , m g_i(x),i1,...,m gi(x),i1,...,m 代表不同的资源消耗函数例如费用、体积、重量等。 1.2 问题的挑战性
很多整数规划问题往往看上去很简单数学模型也不复杂如0-1背包问题、最大割问题等但求解这类问题其实非常困难.绝大部分整数规划问题的可行域都只有有限多个可行点决策方案一个简单幼稚的想法是枚举所有的可行点但是这样会使求解难度指数增加。大部分整数规划问题的困难在于我们本质上只能使用枚举法或隐枚举法的思想来求解问题最优解故当问题的规模越来越大时算法的计算时间急剧增加。与此形成对照的是连续优化问题我们知道最简单的连续优化问题的可行点的个数也是无穷多个但寻找可行域中的最优点并不需要借助枚举法的思想因为利用微积分的工具可以刻画出最优点需要满足的一组容易验证的最优性条件如KKT条件。故只有当算法需要枚举或部分枚举这些可行点时可行域中可行点的个数才和问题的难度有关。
另外一个朴素的想法是“四舍五入”求解相应的连续优化问题丢掉整数约束)然后对求得的解进行四舍五入得到一个整数解.这个方法有两个问题(1)一般很难通过四舍五入得到一个满足约束条件的可行解(2)即使能求得一个可行解其质量往往很差即可能离最优解的距离很远甚至和随机产生的可行解差不多。贪心算法往往可以帮助我们求到一个问题的近似解。例如在0-1背包问题中可以先进行排序 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}} aj1cj1≥aj2cj2≥...≥ajncjn 然后按照从大到小的顺序 j 1 , . . . , j n j_1,...,j_n j1,...,jn 选取物品知道背包的容量 b b b 不能再装下一个物品。
在实际应用中提出的很多整数规划问题的规模一般都很大直接利用现有的算法和软件求解往往是不可能的.这就促使人们研究有效快速的近似算法或启发式算法以寻找问题的一个近似最优解或较好的可行解如近年来发展起来的基于半定规划的随机化算法和各种针对具体整数规划和组合优化问题的近似算法。
参考资料
整数规划 孙小玲李瑞 北京科学出版社 2010Wolsey L A. Integer programming[M]. John Wiley Sons, 2020.
