第3章 整数规划

第3章整数规划主要介绍三种方法：1、分支定界法（branchandboundmethod）2、割平面法（cuttingplaneapproach）3、匈牙利法第3章整数规划§3.1

整数规划模型介绍§3.2

分支定界法§3.3

割平面法§3.4

匈牙利算法3§3.1

整数规划模型介绍

整数规划的一般形式（IP）问题Max（min）z=∑cjxj∑aijxj

≤（或=，≥）bii=1，2，…，mxj

≥0j=1，2，…，nxj

Zs.t.（LIP）松弛问题Max（min）z=∑cjxj∑aijxj

≤（或=，≥）bii=1，2，…，mxj

≥0j=1，2，…，ns.t.4§3.1

整数规划模型介绍（IP）问题与（LIP）问题关系（Min）1.(IP)问题的值

(LIP)问题的最优值。2.(LIP)问题最优解若是整数，则一定是(IP)问题的最优解。5§3.1

整数规划模型介绍整数规划分类纯整数线性规划：决策变量都取整数值。混合整数线性规划：决策变量中一部分取整数值，另一部分可以不取整数值。0-1整数线性规划：决策变量只能取值0或1

。

6§3.1

整数规划模型介绍整数规划引例背包问题厂址选择问题

组合投资问题（见教材107-108页）

Return7§3.2分支定界法

分支定界法是一种隐枚举方法或部分枚举方法，是枚举方法基础上的改进，是组合优化重要方法。其关键是分支和定界。例1

MinZ=-2X1-3X25X1+7X2≤354X1+9X2≤36X1

，X2≥0X1

，X2

Z8解：先求相应线性规划的最优解，为：取分割可行域，得到子问题Sub-1,Sub-2：

§3.2分支定界法Sub-2 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≥3x1x2≥0Sub-1 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1x2≥09§3.2分支定界法Sub-1的最优解为：取

分割可行域，得到两个子问题Sub-3,Sub-4

：Sub-3 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≤4x1x2≥0Sub-4 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x1x2≥010§3.2分支定界法Sub-3的最优解为：获得整数解，取得上界

，停止分枝！11§3.2分支定界法Sub-4的最优解为：Sub-6 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≥2x1x2≥0Sub-5 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1x2≥0取

分割可行域，得到两个子问题：Sub-5,Sub-612§3.2分支定界法Sub-5的最优解为：取

分割可行域，得到两个子问题：Sub-7,Sub-8Sub-7 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥5x1x2≥0Sub-8 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥6x1x2≥013§3.2分支定界法Sub-6的可行域是空集，停止分枝。Sub-7的最优解为：获得整数解，停止分枝！由于上界仍保持为14§3.2分支定界法Sub-8的最优解为：取

分割可行域，得到两个子问题：Sub-9,Sub-10Sub-10 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥6x2≤1x1x2≥0Sub-9 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥6x2≤0x2≥015§3.2分支定界法Sub-9的最优解为：获得整数解，停止分枝！由于上界仍保持为16§3.2分支定界法Sub-10的可行域是空集，停止分枝!

17§3.2分支定界法Sub-2的最优解为：

，停止分支！18§3.2分支定界法

至此已将所有可能分解的子问题都已分解到底，最后得到两个目标函数值相等的最优整数解：

（x1，x2）=（4，0）和（x1，x2）=(0，7)

他们的目标函数值都是-14。Return原问题Sub-1Sub-2Sub-3Sub-4Sub-5Sub-6Sub-7Sub-8Sub-9Sub-10剪枝(4,2)，-14(5,1)，-13无可行解(7,0)，-14无可行解19§3.3

割平面法割平面法思想

求解(IP)的松驰问题(LIP)：若最优解X*Z，则从X*的非整分量中选取一个构造线性约束（Gomory割平面），将其加入原(LIP)问题，形成一个新的线性规划并求解，（重复），直至得到整数最优解。

关键：新增的线性约束将切割掉部分非整数解，至少切割掉当前松驰问题的非整数最优解，而不会切割掉问题的任何整数解!20§3.3

割平面法

构造割平面的步骤：1、令xi

是(LIP)问题最优解中非整数值的一个基变量，得：

xi+∑aikxk=bi……………（1）其中，k∈B（B：非基变量下标集）21§3.3

割平面法构造割平面的步骤：2、将bi

和aik

分解成整数部分I（不超过b的最大整数）与非负真分数部分F之和：

bi=Ii+Fi

，其中0＜Fi

＜1……………..(2)aik=Iik+Fik

，其中0≤Fik

＜122§3.3

割平面法

构造割平面的步骤：3、将（2）代入（1）：

xi+∑Iikxk-Ii=Fi-∑Fikxk……（3）4、割平面方程：

Fi-∑Fikxk≤0……（4）！将（4）加入原来(LIP)问题继续求解。23§3.3

割平面法例2

用割平面法求解下列整数规划。IPMinZ=3X1+4X23X1+X2≥4X1+2X2≥4X1

，X2≥0X1

，X2

ZLIPMinZ=3X1+4X23X1+X2≥4X1+2X2≥4X1

，X2≥0

24§3.3

割平面法解:（1）先求解线性规划问题（LIP），得到最优单纯形表：Cj3400I表CBXBB–1

bX1X2X3X40X3431-100X44120-1

j03400B表1X14/510-2/51/51X28/5011/5-3/5

j44/500-2/5-9/525§3.3

割平面法(2)选择一个非整数的基变量，例如x2=8/5，构造割平面。增加松弛变量x5后将这个约束加到线性规划的最优单纯形表，得到b2=8/5=1+3/5，I2=1，F2=3/5a23=1/5=0+1/5，I23=0，F23=1/5a24=-3/5=-1+2/5，I24=-1，F24=2/526§3.3

割平面法(3)求解新的松弛问题Cj110001表CBXBB–1

bX1X2X3X4X51X14/510-2/51/501X28/5011/5-3/500X5-3/500[-1/5]-11

j44/500-2/5-9/502表1X121001-21X21010-110X330012-5

j10000-1-227§3.3

割平面法

整数规划最优解线性规划

最优解切割约束最优解：x1=2,x2=1Return28§3.4

匈牙利算法0-1变量只取0或1，常被用来表示系统是否处于某个特定的状态，或者是否取某个特定的决策方案。如xj=1当方案Sj被选中0否则29§3.4

匈牙利算法0-1整数规划例3

选址问题

WAL-MART拟在常州的天宁、钟楼、新区建立分店，有7个位置（地点）Ai（i=1，2，…，7）供选择。总部规定在天宁，由A1，A2，A3

三个点中至多选两个；在钟楼，由A4，A5

两个点中至少选一个；在新区，由A6，A7

两个点中至少选一个。如果选Ai

点，设备投资为ai

元，每年可获利润为ci

元，但投资总额不能超过A元。问公司选择哪几个点可使年总利润最大？30§3.4

匈牙利算法解：建立模型引入0-1变量1当Ai

点被选用

0否则xi=（i=1，2，…，7）maxz=∑cixi∑aixi≤Ax1+x2+x3≤2x4+x5≥1x6+x7≥1xi

{0，1}31§3.4

匈牙利算法例4

指派问题（assignmentproblem）

有n个人和n件事，已知第i人做第j事的费用为cij（i，j=1，2，…，n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如任务人员ABCD甲乙丙丁312971441481317161141513932§3.4

匈牙利算法解：建立模型

令1当指派第i人完成第j项任务

0否则xij=minz=∑∑cijxij∑xij=1，j=1，2，…，n∑xij=1，i=1，2，…，nxij

{0，1}33§3.4

匈牙利算法匈牙利算法

1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.König）的关于矩阵中独立零元素的定理，提出了求解指派问题算法——匈牙利算法。34§3.4

匈牙利算法

【性质】

若从指派问题的系数矩阵C=（cij

）n×n的某行（或某列）各元素分别减去一个常数k

，得到一个新的系数矩阵C’=（c’ij

）则以C和C’为系数矩阵的两个指派问题有相同的最优解。35§3.4

匈牙利算法算法步骤（1）变换系数矩阵C，使每行及每列至少有一个零元素，同时不出现负元素。（2）确定独立零元素组。若|独立零元素组|=n，结束；否则，转步骤（3）。（3）继续变换系数矩阵，然后返回步骤（2）。36§3.4

匈牙利算法例5求解下列指派问题（教材121页）。2151341041415914161378119013112601011057401422497min（cij

）=37§3.4

匈牙利算法例5（续）013112601011047401420042min01370606905320100=（c’ij

）38§3.4

匈牙利算法例5（续）01370606905320100此时圈0元素的个数m=n=4.39§3.4

匈牙利算法例5（续）00010100

10000010（xij

）=最优分配：40§3.4

匈牙利算法例6求下列指派问题（教材122页）。任务人员ABCDE甲乙丙丁戊128715479171410961267761461096910941§3.4

匈牙利算法例6（续）解：1279798966671712149151466104107109767645020223000010572980040636542§3.4

匈牙利算法例6（续）50202230000105729800406365

此时圈0元素（独立零元素）的个数m=4<n=5，不能确定最优指派方案！需要继续变换系数矩阵，以增加独立零元素个数。方法如下：43§3.4

匈牙利算法例6（续）对未加圈0的行打√号；对所有打√号行的所有含0的列打√号；对已打√号的列中含0的行打√号；重复2)和3)，直到无可以打√号行或列为止；对未打√号的行画一横线，对打√号的列画一竖线，即得能覆盖所有0的最少直线数目的直线集合。44§3.4

匈牙利算法例6（续）50202230000105729800406365√√√45§3.4

匈牙利算法例6（续）继续变换系数矩阵：

在未被直线覆盖的元素中找出一个最小元素在打√号行各元素都减去这一最小元素，在打√号列的各元素都加上这一最小元素（以保证0元素不变），得新系数矩阵。若得到n个独立的0元素，则获最优解；否则，重复上步骤继续变换系数矩阵。46§3.4

匈牙利算法例6（续）50202230000105729800406365√√√最小元素=27020243