运筹学本科整数规划

整数规划IntegerProgramming（IP）第五章整数规划1整数规划IntegerProgramming（IP）整数规划的数学模型及解的特点整数规划数学模型的一般形式（IP）问题Max（min）z=∑cjxj∑aijxj

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

≥0j=1，2，…，nxj中部分或全部取整数s.t.松弛问题Max（min）z=∑cjxj∑aijxj

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

≥0j=1，2，…，n2整数规划IntegerProgramming（IP）整数规划的数学模型及解的特点整数规划问题的类型纯整数线性规划——pureintegerlinearprogramming：全部决策变量都必须取整数值。混合整数线性规划——mixedintegerlinearprogramming：决策变量中一部分必须取整数值，另一部分可以不取整数值。0-1型整数线性规划——zero-oneintegerlinearprogramming：决策变量只能取值0或1

。3整数规划IntegerProgramming（IP）整数规划的例子例1、Page124工作时间和人员安排问题例2、Page124投资项目选择问题例3、Page125建厂选址问题4整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法branchandboundmethod分支定界法是一种隐枚举方法（implicitenumeration）或部分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。其关键是分支和定界。例——MaxZ=X1+X214X1+9X2

≤51-6X1+3X2

≤1X1，X2

≥0X1，X2取整数s.t.5整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划松弛问题MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0该整数规划松弛问题的解为：（X1，X2）=

（3/2，10/3）Z=29/66整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划松弛问题MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1，X2≥0（3/2，10/3）Z=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥2X1，X2≥0B2MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤1X1，X2≥0B2：解（1，7/3）ZB2=10/3B1：解（2，23/9）ZB1=41/97整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划（3/2，10/3）Z=29/6B1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1，X2≥0B2：解（1，7/3）ZB2=10/3B1：解（2，23/9）ZB1=41/9B11MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≥3X1，X2≥0B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≤2X1，X2≥0B12：解（33/14，2）ZB12=61/148整数规划IntegerProgramming（IP）整数规划问题的求解方法分支定界法图解整数规划（3/2，10/3）Z=29/6B2：解（1，7/3）ZB2=10/3B12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1，X2≥0B12：解（33/14，2）ZB12=61/14B121MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥3X2≤2X1，X2≥0B122MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤2X2≤2X1，X2≥0B121：解（3，1）ZB121=4B122：解（2，2）ZB122=4B1：解（2，23/9）ZB1=41/99整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach

割平面法求解整数规划问题时，若其松驰问题的最优解X*不满足整数要求时，则从X*的非整分量中选取一个，用以构造一个线性约束条件（Gomory割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而不会切割掉问题的任何整数解。10整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach

构造切割方程的步骤：1、令xi是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：xi+∑aikxk=bi……（1式）其中i∈Q（Q指非基变量下标集）k∈K（K指基变量下标集）11整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach

构造切割方程的步骤：2、将bi和aik都分解成整数部分N（不超过b的最大整数）与非负真分数部分f之和，即：bi=Ni+fi，其中0＜fi＜1………（2式）aik=Nik+fik，其中0≤fik＜1例如：若b=2.35，则N=2，f=0.35；若b=-1.45，则N=-2，f=0.5512整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach

构造切割方程的步骤：2、将（2式）代入（1式）得：xi+∑Nikxk-Ni=fi-∑fikxk……（3式）3、提出变量为整（当然含非负）的条件：由于（3式）中等式左边需整，而0＜fi＜1，故有

fi-∑fikxk≤0……（4式）此即为所需切割方程。13整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach

构造切割方程的步骤：（1）切割方程fi-∑fikxk≤0真正进行了切割，至少把非整数最优解这一点切割掉了。证明：（反证法）假设松驰问题的最优解X*未被切割掉，则由

fi-∑fikx*k≤0，又因为x*k=0，（因x*k为非基变量）有fi≤0，这与fi＞0矛盾。（2）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。14整数规划IntegerProgramming（IP）整数规划问题的求解方法割平面法cuttingplaneapproach例——求解IPMaxZ=X1+X2-X1+X2≤13X1+X2≤4X1，X2≥0X1，X2整数LPMaxZ=X1+X2-X1+X2≤13X1+X2≤4X1，X2≥015整数规划IntegerProgramming（IP）求解步骤：1、求解LP得到非整数最优解：

X=（3/4，7/4，0，0），MaxZ=5/2Cj1100I表CBXBB–1

bX1X2X3X40X31-11100X443101j01100B表1X13/410-1/41/41X27/4013/41/4j-5/200-1/2-1/216整数规划IntegerProgramming（IP）求解步骤：2、构造切割方程：

由B表中的第2个方程——X2+3/4X3+1/4X4=7/4有b2=7/4=1+3/4a23=3/4=0+3/4，a24=1/4=0+1/4因此，切割方程为——

3/4–3/4X3–1/4X4≤0增加松弛变量X5，并将如下方程的约束条件添加到B表中。

-3X3-1X4+X5=-3X5≥017整数规划IntegerProgramming（IP）求解步骤：3、求解新的松弛问题

Cj11000B表CBXBB–1

bX1X2X3X4X51X13/410-1/41/401X27/4013/41/400X5-300-3-11j-5/200-1/2-1/20新B表1X111001/3-1/121X2101001/40X310011/3-1/3j-2000-1/3-1/618整数规划IntegerProgramming（IP）0-1整数规划问题0-1变量及其应用0-1变量作为逻辑变量（Logicalvariable），常常被引用来表示系统是否处于某个特定的状态，或者决策变量是否取某个特定的方案。如xj=1当决策取方案Pj时0当决策不取方案Pj时19整数规划IntegerProgramming（IP）0-1整数规划问题0-1变量及其应用例1选址问题某公司在城市的东、西、南三区建立门市部。拟议中有7个位置（地点）Ai（i=1，2，…，7）可供选择。公司规定在东区，由A1，A2，A3三个点中至多选两个；在南区，由A4，A5两个点中至少选一个；在西区，由A6，A7两个点中至少选一个。如果选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问公司选择哪几个点可使年总利润最大？20整数规划IntegerProgramming（IP）0-1整数规划问题0-1变量及其应用建立模型引入0-1变量1当Ai点被选用0当Ai没点被选用xi=（i=1，2，…，7）maxz=∑cixi∑bixi≤Bx1+x2+x3≤2x4+x5≥1x6+x7≥1xi=0，或121整数规划IntegerProgramming（IP）0-1整数规划问题0-1变量及其应用例7应用0-1变量解决含互斥约束条件问题设：工序B有两种方式完成方式（1）的工时约束为0.3X1+0.5X2≤150方式（2）的工时约束为0.2X1+0.4X2≤120问题是完成工序B只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划模型中呢？22整数规划IntegerProgramming（IP）0-1整数规划问题0-1变量及其应用例7应用0-1变量解决含互斥约束条件问题引入0-1变量y1=0若工序B采用方式（1）完成1若工序B不采用方式（1）完成y2=0若工序B采用方式（2）完成1若工序B不采用方式（2）完成23整数规划IntegerProgramming（IP）0-1整数规划问题0-1变量及其应用例7应用0-1变量解决含互斥约束条件问题于是前面两个互斥的约束条件可以统一为如下三个约束条件：0.3X1+0.5X2≤150+M1y1

0.2X1+0.4X2≤120+M2y2

y1+y2=1其中M1，M2都是足够大的正数。24整数规划IntegerProgramming（IP）指派问题（assignmentproblem）指派问题的标准形式及其数学模型指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i人做第j事的费用为Cij（i，j=1，2，…，n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如任务人员ABCD甲乙丙丁210971541481314161141513925整数规划IntegerProgramming（IP）指派问题（assignmentproblem）指派问题的标准形式及其数学模型指派问题的标准形式，令1当指派第i人完成第j项任务0当不指派第i人完成第j项任务xij=minz=∑∑cijxij∑xij=1，j=1，2，…，n∑xij=1，i=1，2，…，nxij=1或026整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法标准的指派问题是一类特殊的0-1整数规划问题，可以用多种相应的解法来求解。但是，这些方法都没有充分利用指派问题的特殊性质来有效减少计算量。1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.König）的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙利解法。27整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵C=（cij）n×n的某行（或某列）各元素分别减去（或加上）一个常数k，得到一个新的系数矩阵C’=（c’ij）则以C和C’为系数矩阵的两个指派问题有相同的最优解（两个问题的目标值不相同）。28整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤步骤一：变换系数矩阵。使其每行及每列至少有一个零元素，同时不出现负元素。步骤二：进行试指派，即确定独立零元素（矩阵中不在同一行和同一列）。步骤三：继续变换系数矩阵，然后返回步骤二。29整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤以上例说明步骤2151341041415914161378119013112601011057401422497min（cij）=30整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤以上例说明步骤013112601011047401420042min01370606905320100=（c’ij）31整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤以上例说明步骤01370606905320100此时加圈0元素的个数m=n=4，所以得到最优解32整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤以上例说明步骤00010100

10000010（xij）=33整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤例任务人员ABCDE甲乙丙丁戊128715479171410961267761461096910934整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤1279798966671712149151466104107109767645020223000010572980040636535整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤50202230000105729800406365此时加圈0元素的个数m=4，而n=5，所以解题没有完成。独立零元素（加圈零元素）少于n个，表示还不能确定最优指派方案。此时需确定能覆盖所有零元素的最少直线数目的直线集合。方法如下：36整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤对没有加圈零元素的所有行打√号；对所有打√号行的所有含零元素的列打√号；再对已打√号的列中含零元素的行打√号；重复2）和3），直到再也不能找到可以打√号行或列为止；对未打√号的行画一横线，对已打√号的列画一竖线，这样就得到能覆盖所有零元素的最少直线数目的直线集合。37整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤50202230000105729800406365√√√12338整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤继续变换系数矩阵。其方法是在未被直线覆盖的元素中找出一个最小元素。然后在打√号行各元素都减去此最小元素，而在打√号列的各元素都加上此最小元素，以保证原来的0元素不变。这样得到新系数矩阵（其最优解和原问题相同）。若得到n个独立的0元素，则已得最优解，否则重复该步骤继续变换系数矩阵。39整数规划IntegerProgramming（IP）指派问题（assignmentproblem）匈牙利解法的一般步骤50202230000105729800406365√√√最小元素=270