《运筹学》课程授课教案（讲稿）第13讲 整数规划

课程名称：《运筹学》第13讲次授课题目整数规划本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，会建立整数规划模型，学会用割平面法、分支定界法求解整数规划问题。[重点及难点】割平面法、分支定界法。内容[本讲课程的引入]引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量可获利润及托运限制如下：体积重量利润甲5220乙45102413托运限制两种货物各托运多少箱使利润最大？Max Z=20x, +10x25x, +4x,≤242x, +5x,≤13x,x≥0x,x为整数[本讲课程的内容]整数规划的数学模型-1、整数规划问题整数规划问题（IP）：是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。重点研究：整数线性规划问题2、整数线性规划问题的模型max(min) Z-Zc*)-1(2a*) (2,)b -1..mj-1x,≥0x,中取部分或全部为整数j=1,2,.n

课程名称：《运筹学》 第 13 讲次 授课题目 整数规划 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，会建立整数规划模型，学会用割平面法、分支定界法 求解整数规划问题。 [重点及难点] 割平面法、分支定界法。 内 容 [本讲课程的引入] [本讲课程的内容] 一、 整数规划的数学模型 1、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。 松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。 重点研究：整数线性规划问题 2、整数线性规划问题的模型

内容3、整数规划问题的类型：(1)纯整数规划问题minZ=x,+x,+xg+x+xs+xo+x,+xg(X)≥ 8X+X≥8Xf + X2+ Xg≥7Xi+x2+ Xg+ X ≥1X2+ X+ Xy+ Xg≥2X3+ X+ Xs+x≥1X4+Xg+X+X,≥5Xg+X+X+Xg≥10X+ X,+xg≥10X,+xg≥6Xg≥6x≥0(i=1,.,8)且为整数(2)0-1型整数线性规划例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj，此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之，不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？Max Z-Eeyj（1对项目/投资X(Zax<B【0对项目/不投资x≥xiX+x≥1Xg+xg +x,=2XF0或1 (j=1,2,..n)(3）混合整数规划例3：工厂A1和A2生产某种物资，由于该种物资供不应求，还需要建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(i-1,2,3,4)。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小

内 容 (2) 0-1 型整数线性规划 例 2：现有资金总额为 B。可供选择的投资项目有 n 个，项目 j 所需投资额和预期收益 分别为 aj 和 cj ,此外，因种种原因，有 3 个附加条件：若选择项目 1 必须同时选择项目 2， 反之，不一定；项目 3 和项目 4 中至少选择一个；第三，项目 5、6、7 中恰好选择两个。 应当怎样选择投资项目，才能使总预期收益最大？ (3) 混合整数规划 例 3: 工厂 A1 和 A2 生产某种物资，由于该种物资供不应求，还需要建一家工厂。由 两个待选方案 A3 和 A4。物资需求地为 Bj(j=1,2,3,4)。工厂 A3 和 A4 的生产费用估计为 1200 万元或 1500 万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用） 最小

内容生产B3B1B2B4能力A129344008357A26007612A32005425A4200300150 350400需求量min Z-Zcjxj, +[1200y+1500(1-y)]y——0-1变量X11+ X21+ X31+ X41=350X12+ X22+ X32+ X42=400y=『1若建工厂A;X13+ X23+ X33+ X43=300（o若建工厂AX14+ X24+ X34+ X44=150设x为由A送往B，的物资数量。X1+ X12+ X13+ X14=400X21+ X22+ X23+ X24=600X31+X32+X33+X34=200yX41+ X42+ X43+ X44=200(1-y)X≥0,y=0或1割平面法二、1、基本思想找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。由松弛问题的可行域向整数规划的可行域逼近二、割平面求解举例Max Z=xi+x2Max Z=x,+x2[-xtx,≤1-x;+x2+x3 =1松弛问题3xjtx2 ≤43x;+x2 +x,=4Xx≥0且为整数X,x,≥0

内 容 二、 割平面法 1、基本思想 找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松 弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在 内的非整数解。 由松弛问题的可行域向整数规划的可行域逼近 B1 B2 B3 B4 生产 能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 需求量 350 400 300 150

内“容不考虑整数解约束，解松弛问题的最优单纯形表为1100CBbXBX1X2X3X4-111010X3031041X41100a...........1103/4-1/41/4X17/403/41/411X200Z=5/2-1/2-1/2a得到非整数的最优解：max z=5/2X,=3/4，×,=7/4,×3=X4=0,103/4-1/41/41Xi01/417/413/4X200Z=5/20-1/2-1/2得到非整数的最优解：X,=3/4,x,=7/4,x,=x=0,max z=5/2不能满足整数最优解的要求。为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解可从最终计算表中得到非整数变量对应的关系式：113xr4tt4t=4317X2+43+4*=4为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和313X +(-1+x+X44443.134+=1+x,+43+4然后将整数部分与分数部分分开，移到等式左右两边得到：3(31x-x4745+x43(31-1=X+4A4

内 容

内容现考虑整数条件要求xl、x2都是非负整数，于是由条件可知x3、x4也都是非负整数,这一点对以下推导是必要的，如不都是整数，则应在引入x3、x4之前乘以适当常数，使之都是整数。在上式中（其实只考虑一式即可）从等式左边看是整数；等式右边也应是整数。但在等式右边的()内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件可由下式所代替；331x)≤0x+444·即-3×3-×4≤-3这就得到一个切割方程（或称为切割约束），将它作为增加约束条件，再解例3。引入松弛变量x5，得到等式-3x3-×,+x,=3将这新的约束方程加到最终计算表110Ci00XbbCsX1X2X3X4X5013/41-1/41/40Xi17/4013/41/40X20010-3-3-1Xs005/20-1/2-1/2CZi·11000?CBbXB+5X1X2X3X410011/4X13/4-1/400111/47/43/4X2[-3]0-300-11X5000Z=5/2-1/2-1/2a11010X11/31/121101001/4×2010011/3-1/3X3000Z=2-1/3-1/30

内 容 现考虑整数条件 要求 x1、x2 都是非负整数，于是由条件可知 x3、x4 也都是非负整数,这一点对以 下推导是必要的，如不都是整数，则应在引入 x3、x4 之前乘以适当常数，使之都 是整数。 在上式中(其实只考虑一式即可)从等式左边看是整数；等式右边也应是整数。但在 等式右边的(·)内是正数；所以等式右边必是非正数。就是说，右边的整数值最大 是零。于是整数条件可由下式所代替；

内容由于X1、X2的值已都是整数，解题已完成。三、分支定界法1、基本思想定界：为求解纯整数规划和混合整数规划问题(A)，先求出其松弛问题（B）的最优解，作为问题A的最优目标函数值的上界，同时选择任意整数可行解作为A的最优目标函数值的下界。分支：将应为整数解，但尚是非整数解之一的决策变量取值分区，并入松弛问题中，形成两个分支松弛问题，分别求解。依结果来调整上下界。二、 举例MaxZ=40x,+90x2例1：9x)+7x2≤567xj+20x≤70xj,x,≥0xx都为整数MaxZ=40x,+90x2松弛问题B为9x)+7x2≤567xj+20x,≤70[X≥0最优解x,=4.81，x2=1.82，Zo=3560≤z*≤356在松弛问题B的解中x,=4.81。于是对原问题增加两个约束条件×≤4，×15可将原问题分解为两个子问题B，和B（即两支），问题B问题Bz1-349z2-341x1-4.00x1-5.00x2-1.57x22.10显然没有得到全部变量是整数的解。因z,>z,故将乙改为349，那么必存在最优整数解z*，并且0*349

内 容 三、分支定界法 1、基本思想 定界：为求解纯整数规划和混合整数规划问题(A)，先求出其松弛问题（B）的最 优解，作为问题 A 的最优目标函数值的上界，同时选择任意整数可行解作为 A 的最优目 标函数值的下界。 分支：将应为整数解，但尚是非整数解之一的决策变量取值分区，并入松弛问题 中，形成两个分支松弛问题，分别求解。依结果来调整上下界

内容问题B问题Bz1-349z2-3410≤z*≤349x1=4.00x1-5.00x2-2.10x2-1.57继续对问题B,和B,进行分解因z,>Z,，故先分解B,为两支。增加条件x,≤2者，称为问题B3；增加条件×，≥3者称为问题B4。问题B问题Bz1-340z2-327剪掉B4，不再考虑x1-4x1=1.42x2-2x2-3340≤z*≤341问题B问题Bz1349z2-341340≤z*≤341x1=4.00x1-5.00x2-2.10x2-1.57对B,问题增加两个约束条件x2≥2, x2≤1问题B问题Bz1-308无可行剪掉Bs，Be，不再考虑解x1-5.44x2-1X,=4, X2=2, Z=340

内 容

容内问题BZ=356Z=0X-4.81,=1.82Z=356X,≤4X,≥5Z=349问题B,问题B2Z-0X,=4,x,=2.1Z=349x,=5,x,-1.57 Z=341X≤2X r≥3≤IZ=349≥2问题B问题B4Z-340X,=1.42X,=4,问题Bs问题BX2=2X=3X,=5.44无可行Z=327Z-340Z*=340解x2=1Z-308分枝定界法求解问题的步骤：将要求解的整数规划问题称为问题A，将其松弛问题称为问题B，若（1）B没有可行解，这时A也没有可行解，停止（2）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解（3）B有最优解，但不符合A的整数条件，记它目标函数值为最优值上界，观察一下界值。Z7≤2第一步:分枝，在B中选择一个不符合整数条件的变量x，其值为bj，【b］表示小于b,的最大整数，构造两个约束条件。x,≤[b,],x,≥[b,]+1将此两个约束条件加入B，在不考虑整数条件的情况下，求解两个后继问题B1和B2定界，以每个后继问题为一分枝标明求解结果，与其他问题解的结果中，找出目标函数最大者作为新的上界，从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界，若无可行解，下界仍为零。第二步：比较与剪枝，各分枝的最优目标函数中若有小于下界者，则剪掉这枝，此后无需再考虑。若大于下界，且不符合整数条件，则重复第一步，直至找到最优解为止。练习：用分枝定界法求解整数规划问题

内 容 分枝定界法求解问题的步骤： 将要求解的整数规划问题称为问题 A，将其松弛问题称为问题 B，若 （1）B 没有可行解，这时 A 也没有可行解，停止 （2）B 有最优解，并符合问题 A 的整数条件，B 的最优解即为 A 的最优解 （3）B 有最优解，但不符合 A 的整数条件，记它目标函数值为最优值上界，观察一 下界值。 练习：用分枝定界法求解整数规划问题

内容max Z =x, +x,[14x, +9x, ≤51 -6x, + 3x, ≤1[],,≥0且全为整数【本讲小结】今天我们给大家重点介绍了整数规划问题及其求解方法割平面法和分支定界法。[本讲课程的作业］求解MaxZ=3xf-x2(3x)-2x2≤35x,+4x,≥102x,+x,≤5X1,x2≥0且为整数

内 容 [本讲小结] 今天我们给大家重点介绍了整数规划问题及其求解方法割平面法和分支定 界法。 [本讲课程的作业] 求解              , 0且全为整数 6 3 1 14 9 51 max 1 2 1 2 1 2 1 2 x x x x x x Z x x