教案_整数规划

1、第一节第一节 问题的提出问题的提出 例子：某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表货物体积每箱（m3）重量每箱（吨）利润每箱（百元）甲424乙513托运限制206问两种货物托运多少箱，可使获得利润为最大？第五章 整数规划（Integer Programming)分类：1. 纯整数线性规划（Pure Integer Linear Programming） 2. 混合整数线性规划（Mixed Integer Linear Programming） 3. 0-1型整数线性规划（Zero-One Integer Linear Programming）解：设x1

2、，x2分别表示两种货物托运的箱数，那么其线性规划为取整数,0,622054.34max2121212121xxxxxxxxtsxxZ0,622054.34max21212121xxxxxxtsxxZ可得最优解为x*=（5/3，8/3)T。 如果选用“向上凑整”的方法可得到x(1)=(2,3)T, 则此时已破坏了体积约束, 超出可行域的范围; 如果“舍去小数”可得x(2)=(1,2)T, 则此时虽是可行解, 值为10，不是最优解, 因为当x*=(2,2)T是, 其利润为14.由于托运的箱数不能为分数，故上述规划问题是整数规划问题。若不考虑整数约束，其相应的线性规划问题为LP-1：第二节第二节 分

3、枝定界法分枝定界法(Branch and Bound method)引言：穷举法对小规模的问题可以。大规模问题则不行，如指派问题 n个人指派n件事，共有n！中指派方案。一、基本思想和算法依据 基本思想基本思想是：先求出相应的线性规划最优解，若此解不符合整数条件，那么其目标函数的值就是整数规划问题最优值的上界，而任意满足整数条件的可行解的目标函数值将是其下界（定界），然后将相应的线性规划问题进行分枝，分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界, 则剪掉此枝; 如果后续某一分枝问题的最优解满足整数条件，且其最优值大于上述下界，则用其取代上述下界，继续考虑其它分枝，直到最终求得最优

4、的整数解。 算法的依据算法的依据在于：“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是，对极大化问题，与整数规划问题相应的线性规划问题的目标函数值，是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。二、具体步骤（以例子说明）取整数,0,702075679.9040max2121212121xxxxxxxxtsxxZ 解： 第一步：先不考虑整数约束条件，求解相应的线性规划问题，得最优解和最优值如下x1=4.81, x2=1.82, Z=356 此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为 Z=356；用观察法可知x1=0，x2=0

5、是可行解，从而其整数规划问题目标函数的下界应为0，即0 Z* 3569x1+7x2=567x1+20 x2=70Z=40 x1+90 x2LP-1LP-2第二步：分枝与定界过程。 将其中一个非整数变量的解，比如x1, 进行分枝，即x14.81=4, x14.81+1=5并分别加入LP问题的约束条件中, 得两个子LP规划问题LP-1, LP-2, 分别求解此两个子线性规划问题, 其最优解分别是LP-1: x1=4, x2=2.1, Z1=349 LP-2: x1=5, x2=1.57, Z2=341没有得到全部决策变量均是整数的解。再次定出上下界0 Z* 349 继续对问题LP-1，LP-2进行

6、分枝。先对目标函数值大的进行分枝，即分别将 x22.1=2, x22.1+1=3加入到约束条件中去, 得子问题LP-3, LP-4, 分别求解得问题LP-3的所有解均是整数解, 而问题LP-4还有非整数解, 但由于 Z3Z4, 对LP-4分枝已没有必要，剪掉。 LP-3: x1=4, x2=2, Z3=340 （ 是整数解，定下界） LP-4: x1=1.42, x2=3, Z4=327（剪掉）上下界为 340 Z* 349 在对问题LP-2进行分枝, x2 1.57=1， x21.57+1=2, 得子问题LP-5, LP-6, 求解得LP-5: x1=5.44, x2=1, Z5=308 (

7、下界340, 剪掉) LP-6: 无可行解（剪掉）于是得到原整数规划问题的最优解为LP: x1=4, x2=2, Z3=340 x1=4.81LP: x2=1.82 Z=356LP-1: x1=4x1 4 x2=2.1 Z=349LP-2: x1=5x15 x2=1.57 Z=341LP-3: x1=4x1 4 x2=2x2 2 Z=340LP-6 x15 无可行解 剪掉 x22LP-4: x1=1.42x1 4 x2=3 剪掉x2 3 Z=327LP-5: x1=5.44x15 x2=1 剪掉x2 1 Z=308整个过程如下:步骤: 1 求解相应的线性规划问题的最优解和最优值, 如果a) 没

8、有可行解, 停止; b) 若有满足整数条件的最优解, 则已得到整数规划问题的最优解, 停止; c) 若有最优解, 但不满足整数条件, 记此最优值为原整数规划问题Z*的上界, 然后, 用观察法求出下界. 2 分枝、定界，直到得到最优解为止。 a）在以后的各枝中，若某一子规划问题的最优解满足整数条件，则用其最优值置换Z*的下界。b）若某一分枝的最优值小于Z*的下界，则剪掉此枝，即以后不在考虑此枝三、算法需要注意的几点（以极大化问题为例） 1 在计算过程中，若以得到一个整数可行解x(0)，其相应的目标函数值为Z0，那么在计算其它分枝过程中，如果解某一线性规划所得的目标函数值ZZ0，即可停止计算。因为

9、进一步的分枝结果的最优值只能比Z更差。2 若有若干个待求解的分枝，先选那一个待求解的分枝呢？选取目标函数值最大的那一枝。 例 求下列整数规划问题的解取整数,0,721342.46max2121212121xxxxxxxxtsxxZ cj 6 4 0 0 CB XB b x1 x2 x3 x4 4 6 x2 x1 2 5/2 0 1 1 0 1/3 -1/6 -1/3 2/3 初始表 0 0 0 -1/3 8/3 不考虑整数约束X1=5/2X2=2Z=23x1 2x1 3LP1LP2cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X5 2 5/2

10、-1/2 0 1 0 1 0 0 1/3 -1/6 1/6 -1/3 2/3 -2/3 0 0 1 0 0 -1/3 -8/3 0 cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X4 9/4 2 3/4 0 1 0 1 0 0 1/4 0 -1/4 0 0 1 -1/2 1 -3/2 0 0 -1 0 -4 Z=21cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X5 2 5/2 -1/2 0 1 0 1 0 0 1/3 -1/6 -1/6 -1/3 2/3 2/3 0 0 1 0 0 -1/3

11、-8/3 0 cj 6 4 0 0 0 CB XB b x1 x2 x3 x4 x5 4 6 0 X2 X1 X5 1 3 3 0 1 0 1 0 0 0 0 1 1 0 -4 2 -1 -6 0 0 0 -4 -2 Z=22不考虑整数约束X1=5/2X2=2Z=23第1个子问题X1=2X2=9/4Z=21第2个子问题X1=3X2=1Z=22x1 2x1 3练习：用分支定界法求解下述整数规划问题取整数,0,622054.34max2121212121xxxxxxxxtsxxZ x1=5/3LP: x2=8/3 Z=44/3LP-1: x1=1x1 1 x2=16/5 剪掉 Z=68/5LP-2

12、: x1=2x12 x2=2 Z=14第三节第三节 割平面解法割平面解法(Cutting Plane Approach) 割平面法是1958年美国学者R. E. Gomory提出的。 基本思想是：先不考虑变量的取整数约束，求解相应的线性规划，然后不断增加线性约束条件（即割平面），将原可行域割掉不含整数可行解的一部分，最终得到一个具有整数坐标顶点的可行域，而该顶点恰好是原整数规划问题的最优解。 例：求解取整数,0,431.max2121212121xxxxxxxxtsxxZ加松弛变量x3、x4，使其变成标准形（如有非整数的系数，则将其所在的方程乘以某一常数，变成具有整数系数的约束方程），用单纯形

13、法求解得cj1100CBXBbx1x2x3x400 x3x414-13111001初始表0110011x1x23/47/41001-1/43/41/41/4最终表-2/500-1/2-1/2最优解x1=3/4，x2=7/4，x3=x4=0，最优值为Z=5/2，是非整数解。 寻求割平面：由最终表得x1 - 1/4x3 + 1/4x4 = 3/4x2 + 3/4x3 + 1/4x4 = 7/4任选一取分数值的基变量，比如x1，将该式中所有变量的系数、右端常数项均改写成整数与非负真分数之和的形式，并移项得x1 - x3 = 3/4 -（3/4x3 + 1/4x4）（注（注：所有的x均是整数。x3、x

14、4可通过在原约束条件中乘以某一常数变成整数。）则整数约束条件可由下式替代 3/4 -（3/4x3 + 1/4x4）0 即得割平面方程-3x3 - x4 -3引入松弛变量x5，将其加入到原规划的约束条件中，利用上述最终表得左边项必是整数；0(3/4x3+1/4x4) 3/4内不包含任何整数-1+3/4cj11000CBXBbx1x2x3x4x500 x3x414-13111001初始表01100110 x1x2x53/47/4-3100010-1/43/4-31/41/4-1001最终表-5/200-1/2-1/20用对偶单纯形算法进行计算。x5作换出变量，x3换入变量，迭代得cj11000CB

15、XBbx1x2x3x4x5110 x1x2x31111000100011/301/31/121/4-1/3-2000-1/3-1/6已得到整数解，最优解为x1=1，x2=1，最优值为2。注：新约束-3x3-x4 -3的几何意义。 用x1，x2表示上述约束，得 x2 1，其图形见下图。3x1+x2=4-x1+x2=1x2 1求切平面的基本步骤： 1 令xi是相应线性规划问题最优解中为分数解的一个基变量，由单纯形最终表得到 xi+aikxk=bi，其中i为基变量的标号；k为非基变量的标号。 2 将bi和aik都分解成整数部分N与非负分数部分f之和，即 bi=Ni+fi， 其中0fi1 aik=Ni

16、k+fik, 其中0fik00 xj =0Min Z=(K1y1+c1x1 )+ （K2y2+c2x2 ）+（K3y3+c2x2 ）xj yjM 若有n个决策变量, 则可以产生2n个可能变量的组合, 故完全枚举是不可能的. 求解0-1整数规划问题的解法均是部分枚举法或称为隐枚举法(Implicit enumeration) 基本思想基本思想是: 在2n个可能的变量组合中, 往往只有一部分是可行解. 只要发现某个变量组合不满足其中的某一约束条件时, 就不必要检验其它的约束条件是否可行。 若发现一个可行解, 则根据它的目标函数值可以产生一个过滤条件(Filtering constraint), 对

17、于目标函数值比它差的的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界法）。 在以后求解过程中, 每当发现比原来更好的可行解, 则依次替代原来的过滤条件 (可减少运算次数, 较快地发现最优解)。0-1整数规划问题的解法整数规划问题的解法10,6434422.523max3213221321321321orxxxxxxxxxxxxxtsxxxZ以例子说明上述求解方法例1: 求解下述0-1整数规划问题解：求解过程见下表(x1,x2,x3)Z 值约束条件 过滤条件（0,0,0）0 Z0(0,0,1)5 Z5(0,1,0)-2 (0,1,1)3(1,0,0

18、)3(1,0,1)8 Z8(1,1,0)1(1,1,1)6所以，最优解为（x1，x2，x3)T=(1,0,1)T, 最优值为8. 注： 当决策变量(x1, x2 , x3)按(0,0,0), (0,0,1), (0,1,0), (0,1,1),.方式取值时, 为了减少计算次数, 通常将目标函数中的决策变量的顺序按其系数的大小重新排序, 以使最优解能较早出现。对最大化问题, 按从小到大的顺序排列；对极小化问题, 则相反。例2：求解下述0-1整数规划问题10,53584612.73min4321421432143214321orxxxxxxxxxxxxxxxtsxxxxZ解：重新排序为10,553

19、86412.37min4321412341234123412orxxxxxxxxxxxxxxxtsxxxxZ(x2,x1,x4 ,x3)Z 值约束条件 过滤条件（0,0,0,0）0 (0,0,0,1)-1 (0,0,1,0)1 (0,0,1,1)0(0,1,0,0)3(0,1,0,1)2 (0,1,1,0)4(0,1,1,1)3 Z3(1,0,0,0)7(1,0,0,1)6(1,0,1,0)8(1,0,1,1)7(1,1,0,0)10(1,1,0,1)9(1,1,1,0)11(1,1,1,1)10练习：求解下述整数规划问题02245 , 2 , 1103-2253. .31075min5432

20、1432154321Ljorxxx6xxx5xxxxtsxxxxxZj1 25432xxx-x第五节第五节 指派问题（指派问题（Assignment Problem）1. 标准指派问题的提法及模型 指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件事的费用为cij（i，j=1，2，n），要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。 njiorxxxtsxcZijnjijniijninjijij,2,1,1011.min1111L数学模型为:01ijx若指派第i个人做第j件事若不指派第i个人做第j件事(i,j=1,2, n) 设n2个0-1变量其中矩阵C称为是效

21、率矩阵或系数矩阵。 其解的形式可用0-1矩阵的形式来描述，即 (xij)nn。 标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题。1955年W. W. Kuhn利用匈牙利数学家D. Konig关于矩阵中独立零元素的定理, 提出了解指派问题的一种算法, 习惯上称之为匈牙利解法。2. 匈牙利解法 匈牙利解法的关键是指派问题最优解的以下性质：若从指派若从指派问题的系数矩阵问题的系数矩阵C=（cij）的某行（或某列）各元素分别减去一个）的某行（或某列）各元素分别减去一个常数常数k，得到一个新的矩阵，得到一个新的矩阵C=（cij)，则以，则以C和和C为系数矩阵的两为系数矩

22、阵的两个指派问题有相同的最优解。个指派问题有相同的最优解。（这种变化不影响约束方程组，而只是使目标函数值减少了常数k，所以，最优解并不改变。）作变换，其不变性是最优解对于指派问题，由于系数矩阵均非负，故若能在在系数矩阵中找到n个位于不同行和不同列的零元素（独立的0元素），则对应的指派方案总费用为零，从而一定是最优的。匈牙利法匈牙利法的步骤如下： 步1：变换系数矩阵。对系数矩阵中的每行元素分别减去该行的最小元素；再对系数矩阵中的每列元素分别减去该列中的最小元素。若某行或某列已有0元素，就不必要在减了（不能出现负元素）。 步2：在变换后的系数矩阵中确定独立0元素（试指派）。若独立0元素已有n个，则

23、已得出最优解；若独立0元素的个数少于n个，转步3。 确定独立0元素的方法：当n较小时，可用观察法、或试探法；当n较大时，可按下列顺序进行 从只有一个0元素的行（列）开始，给这个0元素加圈，记作，然后划去所在的列（行）的其它0元素，记作。给只有一个0元素的列（行）的0加圈，记作，然后划去所在行的0元素，记作。反复进行，直到系数矩阵中的所有0元素都被圈去或划去为止。 如遇到行或列中0元素都不只一个（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中的其它0元素。被划圈的0元素即是独立的0元素。 步3：作最少数目的直线，覆盖所有0元素（目的是确定系数矩阵的下一个变换），可按下述方法

24、进行1） 对没有的行打“”号；2） 在已打“”号的行中，对 所在列打“”3）在已打“”号的列中，对所在的行打“”号；4）重复2）3），直到再也找不到可以打“”号的行或列为止；5）对没有打“”的行划一横线，对打“”的列划一纵线，这样就得到覆盖所有0元素的最少直线数。 步4：继续变换系数矩阵，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打“”列的各元素都加上这一最小元素，以保持原来0元素不变（为了消除负元素）。得到新的系数矩阵，返回步2。 以例说明匈牙利法的应用。91071041066141591412177666989797

25、12例1：求解效率矩阵为如下的指派问题的最优指派方案。解：第一步：系数矩阵的变换（目的是得到某行或列均有0元素）910710410661415914121776669897971256360400892751000003220205第二步：确定独立0元素56360400892751000003220205元素的个数m=4，而n=5，进行第三步。第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵的下一个变换。第四步：对上述矩阵进行变换，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打“”列的各元素都加上这一最小元素，以保

26、持原来0元素不变（消除负元素）。得到新的系数矩阵。（它的最优解和原问题相同，为什么？）563604008927510000032202050000100100100000100000010由解矩阵可得指派方案和最优值为32。34140400811053800003420207 例2 某大型工程有五个工程项目，决定向社会公开招标，有五家建筑能力相当的建筑公司分别获得中标承建。已知建筑公司Ai（I=1，2，3，4，5）的报价cij（百万元）见表，问该部门应该怎样分配建造任务，才能使总的建造费用最小？ 工程公司B1B2B3B4B5A14871512A279171410A3691287A4671461

27、0A569121065 ,2, 1,105 ,2, 115 ,2, 11.61084min515155541211LLLLjiorxixjxtsxxxxZijjijiij61012961061476781296101417971215784解：第一步：系数矩阵的变换（目的是得到某行或列均有0元素）04320405001232037710811030第二步：确定独立0元素, 即加圈元素的个数m=4，而n=5，进行第三步。04320405001232037710811030第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵的下一个变换。第四步：对上述矩阵进行变换，目的是增加独立0元素个数。方

28、法是在未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中都减去这一元素，而在打“”列的各元素都加上这一最小元素，以保持原来0元素不变（消除负元素）。得到新的系数矩阵。（它的最优解和原问题相同，为什么？因为仅在目标函数系数中进行操作）04320405001232037710811030043204050001211266018110300432140501012102660081103104321405010121026600811031此矩阵中已有5个独立的0元素，故可得指派问题的最优指派方案为：1000001000000010001000100也就是说，最优指派方案为：让A1承建B

29、3， A2承建B2，A3承建B1，A4承建B4，A5承建B5。这样安排建造费用为最小，即7+9+6+6+6=34（百万元）3. 一般的指派问题 在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们转化为标准形式，然后用匈牙利解法求解。 最大化指派问题 设最大化指派问题系数矩阵C中最大元素为m。令矩阵B=(bij)=(m-cij), 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。 人数和事数不等的指派问题 若人少事多，则添上一些虚拟的“人”。这些虚拟的人作各事的费用系数可取0，理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的“事”。这些虚拟的事被各人做的费用系数同样也取0。 一个人可做几件事的指派问题 若某个人可做几件事，则可将该人看做相同的几个人来接受指派。这几个人作同一件事的费用系数当然都一样。 某事一定不能由某人作的指派问题 若某事一定不能由某个人做，则可将相应的费用系数取做足够大的数M。 例3：对于例2的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，而让技术力量较强的建设公司A1，A2，A3参加招标承建，